2017-06-02  Nathan Sidwell  <nathan@acm.org>

	* name-lookup.h (cp_binding_level): Lose namespaces field.
	* name-lookup.c (add_decl_to_level): Chain namespaces on the names
	list.
	(suggest_alternatives_for): Adjust for namespace list.  Do
	breadth-first search.
	* decl2.c (collect_source_refs): Namespaces are on the regulr
	list.
	(collect_ada_namespace): Likewise.

	* g++.dg/pr45330.C: Adjust.  Check breadth-firstness.

Index: cp/decl2.c
===================================================================
--- cp/decl2.c	(revision 248820)
+++ cp/decl2.c	(working copy)
@@ -4052,21 +4052,14 @@ cpp_check (tree t, cpp_operation op)
 static void 
 collect_source_refs (tree namespc) 
 {
-  tree t;
-
-  if (!namespc) 
-    return;
-
   /* Iterate over names in this name space.  */
-  for (t = NAMESPACE_LEVEL (namespc)->names; t; t = TREE_CHAIN (t))
-    if (!DECL_IS_BUILTIN (t) )
+  for (tree t = NAMESPACE_LEVEL (namespc)->names; t; t = TREE_CHAIN (t))
+    if (DECL_IS_BUILTIN (t))
+      ;
+    else if (TREE_CODE (t) == NAMESPACE_DECL && !DECL_NAMESPACE_ALIAS (t))
+      collect_source_refs (t);
+    else
       collect_source_ref (DECL_SOURCE_FILE (t));
-  
-  /* Dump siblings, if any */
-  collect_source_refs (TREE_CHAIN (namespc));
-
-  /* Dump children, if any */
-  collect_source_refs (NAMESPACE_LEVEL (namespc)->namespaces);
 }
 
 /* Collect decls relevant to SOURCE_FILE from all namespaces recursively,
@@ -4075,17 +4068,16 @@ collect_source_refs (tree namespc)
 static void
 collect_ada_namespace (tree namespc, const char *source_file)
 {
-  if (!namespc)
-    return;
-
-  /* Collect decls from this namespace */
-  collect_ada_nodes (NAMESPACE_LEVEL (namespc)->names, source_file);
-
-  /* Collect siblings, if any */
-  collect_ada_namespace (TREE_CHAIN (namespc), source_file);
+  tree decl = NAMESPACE_LEVEL (namespc)->names;
 
-  /* Collect children, if any */
-  collect_ada_namespace (NAMESPACE_LEVEL (namespc)->namespaces, source_file);
+  /* Collect decls from this namespace.  This will skip
+     NAMESPACE_DECLs (both aliases and regular, it cannot tell).  */
+  collect_ada_nodes (decl, source_file);
+
+  /* Now scan for namespace children, and dump them.  */
+  for (; decl; decl = TREE_CHAIN (decl))
+    if (TREE_CODE (decl) == NAMESPACE_DECL && !DECL_NAMESPACE_ALIAS (decl))
+      collect_ada_namespace (decl, source_file);
 }
 
 /* Returns true iff there is a definition available for variable or
Index: cp/name-lookup.c
===================================================================
--- cp/name-lookup.c	(revision 248820)
+++ cp/name-lookup.c	(working copy)
@@ -115,38 +115,28 @@ add_decl_to_level (cp_binding_level *b,
 {
   gcc_assert (b->kind != sk_class);
 
-  if (TREE_CODE (decl) == NAMESPACE_DECL && !DECL_NAMESPACE_ALIAS (decl))
-    {
-      /* Inner namespaces get their own chain, to make walking
-	 simpler.  */
-      DECL_CHAIN (decl) = b->namespaces;
-      b->namespaces = decl;
-    }
-  else
-    {
-      /* Make sure we don't create a circular list.  xref_tag can end
-	 up pushing the same artificial decl more than once.  We
-	 should have already detected that in update_binding.  */
-      gcc_assert (b->names != decl);
-
-      /* We build up the list in reverse order, and reverse it later if
-	 necessary.  */
-      TREE_CHAIN (decl) = b->names;
-      b->names = decl;
-
-      /* If appropriate, add decl to separate list of statics.  We
-	 include extern variables because they might turn out to be
-	 static later.  It's OK for this list to contain a few false
-	 positives.  */
-      if (b->kind == sk_namespace)
-	if ((VAR_P (decl)
-	     && (TREE_STATIC (decl) || DECL_EXTERNAL (decl)))
-	    || (TREE_CODE (decl) == FUNCTION_DECL
-		&& (!TREE_PUBLIC (decl)
-		    || decl_anon_ns_mem_p (decl)
-		    || DECL_DECLARED_INLINE_P (decl))))
-	  vec_safe_push (static_decls, decl);
-    }
+  /* Make sure we don't create a circular list.  xref_tag can end
+     up pushing the same artificial decl more than once.  We
+     should have already detected that in update_binding.  */
+  gcc_assert (b->names != decl);
+
+  /* We build up the list in reverse order, and reverse it later if
+     necessary.  */
+  TREE_CHAIN (decl) = b->names;
+  b->names = decl;
+
+  /* If appropriate, add decl to separate list of statics.  We
+     include extern variables because they might turn out to be
+     static later.  It's OK for this list to contain a few false
+     positives.  */
+  if (b->kind == sk_namespace
+      && ((VAR_P (decl)
+	   && (TREE_STATIC (decl) || DECL_EXTERNAL (decl)))
+	  || (TREE_CODE (decl) == FUNCTION_DECL
+	      && (!TREE_PUBLIC (decl)
+		  || decl_anon_ns_mem_p (decl)
+		  || DECL_DECLARED_INLINE_P (decl)))))
+    vec_safe_push (static_decls, decl);
 }
 
 /* Find the binding for NAME in the local binding level B.  */
@@ -4708,70 +4698,74 @@ suggest_alternatives_for (location_t loc
 			  bool suggest_misspellings)
 {
   vec<tree> candidates = vNULL;
-  vec<tree> namespaces_to_search = vNULL;
-  int max_to_search = PARAM_VALUE (CXX_MAX_NAMESPACES_FOR_DIAGNOSTIC_HELP);
-  int n_searched = 0;
-  tree t;
-  unsigned ix;
-
-  namespaces_to_search.safe_push (global_namespace);
-
-  while (!namespaces_to_search.is_empty ()
-	 && n_searched < max_to_search)
-    {
-      tree scope = namespaces_to_search.pop ();
-      name_lookup lookup (name, 0);
-      cp_binding_level *level = NAMESPACE_LEVEL (scope);
-
-      n_searched++;
-
-      /* Look in this namespace.  */
-      if (qualified_namespace_lookup (scope, &lookup))
-	candidates.safe_push (lookup.value);
-
-      /* Add child namespaces.  */
-      for (t = level->namespaces; t; t = DECL_CHAIN (t))
-	namespaces_to_search.safe_push (t);
-    }
-
-  /* If we stopped before we could examine all namespaces, inform the
-     user.  Do this even if we don't have any candidates, since there
-     might be more candidates further down that we weren't able to
-     find.  */
-  if (n_searched >= max_to_search
-      && !namespaces_to_search.is_empty ())
-    inform (location,
-	    "maximum limit of %d namespaces searched for %qE",
-	    max_to_search, name);
+  vec<tree> worklist = vNULL;
+  unsigned limit = PARAM_VALUE (CXX_MAX_NAMESPACES_FOR_DIAGNOSTIC_HELP);
+  bool limited = false;
+
+  /* Breadth-first search of namespaces.  Up to limit namespaces
+     searched (limit zero == unlimited).  */
+  worklist.safe_push (global_namespace);
+  for (unsigned ix = 0; ix != worklist.length (); ix++)
+    {
+      tree ns = worklist[ix];
+
+      if (tree value = ovl_skip_hidden (find_namespace_value (ns, name)))
+	candidates.safe_push (value);
+
+      if (!limited)
+	{
+	  /* Look for child namespaces.  We have to do this
+	     indirectly because they are chained in reverse order,
+	     which is confusing to the user.  */
+	  vec<tree> children = vNULL;
+
+	  for (tree decl = NAMESPACE_LEVEL (ns)->names;
+	       decl; decl = TREE_CHAIN (decl))
+	    if (TREE_CODE (decl) == NAMESPACE_DECL
+		&& !DECL_NAMESPACE_ALIAS (decl))
+	      children.safe_push (decl);
 
-  namespaces_to_search.release ();
-
-  /* Nothing useful to report for NAME.  Report on likely misspellings,
-     or do nothing.  */
-  if (candidates.is_empty ())
-    {
-      if (suggest_misspellings)
-	{
-	  const char *fuzzy_name = lookup_name_fuzzy (name, FUZZY_LOOKUP_NAME);
-	  if (fuzzy_name)
+	  while (!limited && !children.is_empty ())
 	    {
-	      gcc_rich_location richloc (location);
-	      richloc.add_fixit_replace (fuzzy_name);
-	      inform_at_rich_loc (&richloc, "suggested alternative: %qs",
-				  fuzzy_name);
+	      if (worklist.length () == limit)
+		{
+		  /* Unconditionally warn that the search was truncated.  */
+		  inform (location,
+			  "maximum limit of %d namespaces searched for %qE",
+			  limit, name);
+		  limited = true;
+		}
+	      else
+		worklist.safe_push (children.pop ());
 	    }
+	  children.release ();
 	}
-      return;
     }
+  worklist.release ();
 
-  inform_n (location, candidates.length (),
-	    "suggested alternative:",
-	    "suggested alternatives:");
+  if (candidates.length ())
+    {
+      inform_n (location, candidates.length (),
+		"suggested alternative:",
+		"suggested alternatives:");
+      for (unsigned ix = 0; ix != candidates.length (); ix++)
+	{
+	  tree val = candidates[ix];
 
-  FOR_EACH_VEC_ELT (candidates, ix, t)
-    inform (location_of (t), "  %qE", t);
+	  inform (location_of (val), "  %qE", val);
+	}
+      candidates.release ();
+    }
+  else if (!suggest_misspellings)
+    ;
+  else if (const char *fuzzy = lookup_name_fuzzy (name, FUZZY_LOOKUP_NAME))
+    {
+      /* Show a spelling correction.  */
+      gcc_rich_location richloc (location);
 
-  candidates.release ();
+      richloc.add_fixit_replace (fuzzy);
+      inform_at_rich_loc (&richloc, "suggested alternative: %qs", fuzzy);
+    }
 }
 
 /* Subroutine of maybe_suggest_missing_header for handling unrecognized names
Index: cp/name-lookup.h
===================================================================
--- cp/name-lookup.h	(revision 248820)
+++ cp/name-lookup.h	(working copy)
@@ -188,9 +188,6 @@ struct GTY(()) cp_binding_level {
       are wrapped in TREE_LISTs; the TREE_VALUE is the OVERLOAD.  */
   tree names;
 
-  /* A chain of NAMESPACE_DECL nodes.  */
-  tree namespaces;
-
   /* A list of USING_DECL nodes.  */
   tree usings;
 
Index: testsuite/g++.dg/pr45330.C
===================================================================
--- testsuite/g++.dg/pr45330.C	(revision 248820)
+++ testsuite/g++.dg/pr45330.C	(working copy)
@@ -1,17 +1,23 @@
 // { dg-do compile }
-// Search std, __cxxabiv1, and global namespaces, plus one more.
-// { dg-options "--param cxx-max-namespaces-for-diagnostic-help=4" }
+// Search std, __cxxabiv1, and global namespaces, plus two more,
+// breadth first
 
-#define NSPACE(NAME) namespace NAME { int foo; }
+// { dg-options "--param cxx-max-namespaces-for-diagnostic-help=5" }
+
+// ::, std and __cxxabiv1
 
 namespace A
 {
   int foo;			// { dg-message "A::foo" "suggested alternative" }
+  namespace A0
+  {
+    int foo; // not me
+  }
 }
 
 namespace B
 {
-  int foo;
+  int foo;			// { dg-message "B::foo" "suggested alternative" }
 }
 
 namespace C
@@ -32,6 +38,6 @@ namespace E
 int bar()
 {
   return foo;			// { dg-error "was not declared" }
-  // { dg-message "maximum limit of 4 namespaces" "maximum limit" { target *-*-* } .-1 }
+  // { dg-message "maximum limit of 5 namespaces" "maximum limit" { target *-*-* } .-1 }
   // { dg-message "suggested alternative" "suggested alternative" { target *-*-* } .-2 }
 }
