[C++ PATCH] Reimplement qualified namespace lookup

[Nathan Sidwell <nathan at acm dot org>]

This patch reimplements qualified namespace lookup.  It extends the 
name_lookup object I introduced for ADL.

qualified namespace lookup is essentially a flood-fill algorithm, where 
if nothing is found in namespace X you follow the using directives 
therein.  You stop when you find something (or there's no using 
directives to follow).  As you can see implementing this requires 
knowing if you've met X before -- and if you have, whether searching 
from there found something or not.

The current algorithm maintains 5 vectors (count them, 5!) to record 
where one's been and where one needs to go.  Along with the O(N^2) 'have 
I been here' check.

This implementation uses the new LOOKUP_SEEN_P and LOOKUP_FOUND_P 
markers to just tag the NAMESPACE_DECL directly.  We don't need a work 
queue -- recursion does just fine.  Using directives can create a loop, 
which one will traverse if there is nothing found.  That is handled 
naturally by this algorithm.

There is still some awkwardness with following using directive, because 
of the current implementation of unqualified lookup.  And concatenating 
lookups is still maintaining 1D overloads.

nathan
--
Nathan Sidwell

2017-05-25  Nathan Sidwell  <nathan@acm.org>

	Reimplement qualified namespace lookup.
	* name-lookup.c (name_lookup::flags): New member.  Adjust ctor.
	(name_lookup::ambiguous, name_lookup::add_value,
	name_lookup::add_type, name_lookup::process_binding): New.
	(name_lookup::search_namespace_only,
	name_lookup::search_namespace, name_lookup::search_usings): New.
	(name_lookup::search_qualified): New.
	(do_nonmember_using_decl, suggest_alternatives_for,
	lookup_qualified_name): Adjust.
	(tree_vec_contains): Delete.
	(qualified_lookup_using_namespace): Rename to ...
	(qualified_namespace_lookup): ... here.  Reimplement.

Index: name-lookup.c
===================================================================
--- name-lookup.c	(revision 248457)
+++ name-lookup.c	(working copy)
@@ -48,18 +48,6 @@ struct scope_binding {
 };
 #define EMPTY_SCOPE_BINDING { NULL_TREE, NULL_TREE }
 
-static bool lookup_using_namespace (tree, struct scope_binding *, tree,
-				    tree, int);
-static bool qualified_lookup_using_namespace (tree, tree,
-					      struct scope_binding *, int);
-static void consider_binding_level (tree name,
-				    best_match <tree, const char *> &bm,
-				    cp_binding_level *lvl,
-				    bool look_within_fields,
-				    enum lookup_name_fuzzy_kind kind);
-static tree push_using_directive (tree);
-static void diagnose_name_conflict (tree, tree);
-
 /* Create a local binding level for NAME.  */
 
 static cxx_binding *
@@ -166,6 +154,7 @@ public:
   tree name;	/* The identifier being looked for.  */
   tree value;	/* A (possibly ambiguous) set of things found.  */
   tree type;	/* A type that has been found.  */
+  int flags;	/* Lookup flags.  */
   vec<tree, va_heap, vl_embed> *scopes;
   name_lookup *previous; /* Previously active lookup.  */
   hash_set<tree> *fn_set;
@@ -177,8 +166,8 @@ protected:
   static name_lookup *active;
 
 public:
-  name_lookup (tree n)
-  : name (n), value (NULL_TREE), type (NULL_TREE),
+  name_lookup (tree n, int f = 0)
+  : name (n), value (NULL_TREE), type (NULL_TREE), flags (f),
     scopes (NULL), previous (NULL), fn_set (NULL)
   {
     preserve_state ();
@@ -222,7 +211,22 @@ private:
   void preserve_state ();
   void restore_state ();
 
- private:
+private:
+  static tree ambiguous (tree thing, tree current);
+  void add_value (tree new_val);
+  void add_type (tree new_type);
+  bool process_binding (tree val_bind, tree type_bind);
+
+  /* Look in only namespace.  */
+  bool search_namespace_only (tree scope);
+  /* Look in namespace and its (recursive) inlines. Ignore using
+     directives.  Return true if something found (inc dups). */
+  bool search_namespace (tree scope);
+  /* Look in the using directives of namespace + inlines using
+     qualified lookup rules.  */
+  bool search_usings (tree scope);
+
+private:
   void add_fns (tree);
 
   void adl_expr (tree);
@@ -235,6 +239,10 @@ private:
   void adl_namespace_only (tree);
 
 public:
+  /* Search namespace + inlines + maybe usings as qualified lookup.  */
+  bool search_qualified (tree scope, bool usings = true);
+
+  /* ADL lookup of ARGS.  */
   tree search_adl (tree fns, vec<tree, va_gc> *args);
 };
 
@@ -348,6 +356,207 @@ name_lookup::find_and_mark (tree scope)
   return result;
 }
 
+/* THING and CURRENT are ambiguous, concatenate them.  */
+
+tree
+name_lookup::ambiguous (tree thing, tree current)
+{
+  if (TREE_CODE (current) != TREE_LIST)
+    {
+      current = build_tree_list (NULL_TREE, current);
+      TREE_TYPE (current) = error_mark_node;
+    }
+  current = tree_cons (NULL_TREE, thing, current);
+  TREE_TYPE (current) = error_mark_node;
+
+  return current;
+}
+
+/* Add a NEW_VAL, a found value binding into the current value binding.  */
+
+void
+name_lookup::add_value (tree new_val)
+{
+  if (!value)
+    value = new_val;
+  else if (value == new_val)
+    ;
+  else if ((TREE_CODE (value) == TYPE_DECL
+	    && TREE_CODE (new_val) == TYPE_DECL
+	    && same_type_p (TREE_TYPE (value), TREE_TYPE (new_val))))
+    ;
+  else if (OVL_P (value) && OVL_P (new_val))
+    {
+      for (ovl_iterator iter (new_val); iter; ++iter)
+	value = lookup_add (*iter, value);
+    }
+  else
+    value = ambiguous (new_val, value);
+}
+
+/* Add a NEW_TYPE, a found type binding into the current type binding.  */
+
+void
+name_lookup::add_type (tree new_type)
+{
+  if (!type)
+    type = new_type;
+  else if (TREE_CODE (type) == TREE_LIST
+	   || !same_type_p (TREE_TYPE (type), TREE_TYPE (new_type)))
+    type = ambiguous (new_type, type);
+}
+
+/* Process a found binding containing NEW_VAL and NEW_TYPE.  Returns
+   true if we actually found something noteworthy.  */
+
+bool
+name_lookup::process_binding (tree new_val, tree new_type)
+{
+  /* Did we really see a type? */
+  if (new_type
+      && (LOOKUP_NAMESPACES_ONLY (flags)
+	  || (!(flags & LOOKUP_HIDDEN)
+	      && DECL_LANG_SPECIFIC (new_type)
+	      && DECL_ANTICIPATED (new_type))))
+    new_type = NULL_TREE;
+
+  if (new_val && !(flags & LOOKUP_HIDDEN))
+    new_val = ovl_skip_hidden (new_val);
+
+  /* Do we really see a value? */
+  if (new_val)
+    switch (TREE_CODE (new_val))
+      {
+      case TEMPLATE_DECL:
+	/* If we expect types or namespaces, and not templates,
+	   or this is not a template class.  */
+	if ((LOOKUP_QUALIFIERS_ONLY (flags)
+	     && !DECL_TYPE_TEMPLATE_P (new_val)))
+	  new_val = NULL_TREE;
+	break;
+      case TYPE_DECL:
+	if (LOOKUP_NAMESPACES_ONLY (flags)
+	    || (new_type && (flags & LOOKUP_PREFER_TYPES)))
+	  new_val = NULL_TREE;
+	break;
+      case NAMESPACE_DECL:
+	if (LOOKUP_TYPES_ONLY (flags))
+	  new_val = NULL_TREE;
+	break;
+      default:
+	if (LOOKUP_QUALIFIERS_ONLY (flags))
+	  new_val = NULL_TREE;
+      }
+
+  if (!new_val)
+    {
+      new_val = new_type;
+      new_type = NULL_TREE;
+    }
+
+  /* Merge into the lookup  */
+  if (new_val)
+    add_value (new_val);
+  if (new_type)
+    add_type (new_type);
+
+  return new_val != NULL_TREE;
+}
+
+/* Look in exactly namespace SCOPE.  */
+
+bool
+name_lookup::search_namespace_only (tree scope)
+{
+  bool found = false;
+
+  if (cxx_binding *binding = find_namespace_binding (scope, name))
+    found |= process_binding (binding->value, binding->type);
+
+  return found;
+}
+
+/* Conditionally look in namespace SCOPE and inline children.  */
+
+bool
+name_lookup::search_namespace (tree scope)
+{
+  if (see_and_mark (scope))
+    /* We've visited this scope before.  Return what we found then.  */
+    return found_p (scope);
+
+  /* Look in exactly namespace. */
+  bool found = search_namespace_only (scope);
+  
+  /* Look down into inline namespaces.  */
+  for (tree inner = NAMESPACE_LEVEL (scope)->namespaces;
+       inner; inner = TREE_CHAIN (inner))
+    if (DECL_NAMESPACE_INLINE_P (inner))
+      found |= search_namespace (inner);
+
+  if (found)
+    mark_found (scope);
+
+  return found;
+}
+
+/* Recursively follow using directives of SCOPE & its inline children.
+   Such following is essentially a flood-fill algorithm.  */
+
+bool
+name_lookup::search_usings (tree scope)
+{
+  /* We do not check seen_p here, as that was already set during the
+     namespace_only walk.  */
+  if (found_p (scope))
+    return true;
+
+  bool found = false;
+
+  /* Look in direct usings.  */
+  for (tree usings = DECL_NAMESPACE_USING (scope);
+       usings; usings = TREE_CHAIN (usings))
+    if (!TREE_INDIRECT_USING (usings))
+      found |= search_qualified (TREE_PURPOSE (usings), true);
+
+  /* Look in its inline children.  */
+  for (tree inner = NAMESPACE_LEVEL (scope)->namespaces;
+       inner; inner = TREE_CHAIN (inner))
+    if (DECL_NAMESPACE_INLINE_P (inner))
+      found |= search_usings (inner);
+
+  if (found)
+    mark_found (scope);
+
+  return found;
+}
+
+/* Qualified namespace lookup in SCOPE.
+   1) Look in SCOPE (+inlines).  If found, we're done.
+   2) Otherwise, if USINGS is true,
+      recurse for every using directive of SCOPE (+inlines).
+
+   Trickiness is (a) loops and (b) multiple paths to same namespace.
+   In both cases we want to not repeat any lookups, and know whether
+   to stop the caller's step #2.  Do this via the FOUND_P marker.  */
+
+bool
+name_lookup::search_qualified (tree scope, bool usings)
+{
+  bool found = false;
+
+  if (seen_p (scope))
+    found = found_p (scope);
+  else 
+    {
+      found = search_namespace (scope);
+      if (!found && usings)
+	found = search_usings (scope);
+    }
+
+  return found;
+}
+
 /* FNS is a value binding.  If it is a (set of overloaded) functions,
    add them into the current value.  */
 
@@ -692,6 +901,17 @@ name_lookup::search_adl (tree fns, vec<t
   return fns;
 }
 
+static bool lookup_using_namespace (tree, struct scope_binding *, tree,
+				    tree, int);
+static bool qualified_namespace_lookup (tree, name_lookup *);
+static void consider_binding_level (tree name,
+				    best_match <tree, const char *> &bm,
+				    cp_binding_level *lvl,
+				    bool look_within_fields,
+				    enum lookup_name_fuzzy_kind kind);
+static tree push_using_directive (tree);
+static void diagnose_name_conflict (tree, tree);
+
 /* ADL lookup of NAME.  FNS is the result of regular lookup, and we
    don't add duplicates to it.  ARGS is the vector of call
    arguments (which will not be empty).  */
@@ -3073,9 +3293,9 @@ validate_nonmember_using_decl (tree decl
 static void
 do_nonmember_using_decl (tree scope, tree name, tree *value_p, tree *type_p)
 {
-  struct scope_binding lookup = EMPTY_SCOPE_BINDING;
+  name_lookup lookup (name, 0);
 
-  if (!qualified_lookup_using_namespace (name, scope, &lookup, 0))
+  if (!qualified_namespace_lookup (scope, &lookup))
     /* Lookup error */
     return;
 
@@ -4547,16 +4767,14 @@ suggest_alternatives_for (location_t loc
 	 && n_searched < max_to_search)
     {
       tree scope = namespaces_to_search.pop ();
-      struct scope_binding binding = EMPTY_SCOPE_BINDING;
+      name_lookup lookup (name, 0);
       cp_binding_level *level = NAMESPACE_LEVEL (scope);
 
-      /* Look in this namespace.  */
-      qualified_lookup_using_namespace (name, scope, &binding, 0);
-
       n_searched++;
 
-      if (binding.value)
-	candidates.safe_push (binding.value);
+      /* 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))
@@ -4824,13 +5042,13 @@ lookup_qualified_name (tree scope, tree
 
   if (TREE_CODE (scope) == NAMESPACE_DECL)
     {
-      struct scope_binding binding = EMPTY_SCOPE_BINDING;
-
       int flags = lookup_flags (prefer_type, /*namespaces_only*/false);
       if (find_hidden)
 	flags |= LOOKUP_HIDDEN;
-      if (qualified_lookup_using_namespace (name, scope, &binding, flags))
-	t = binding.value;
+      name_lookup lookup (name, flags);
+
+      if (qualified_namespace_lookup (scope, &lookup))
+	t = lookup.value;
     }
   else if (cxx_dialect != cxx98 && TREE_CODE (scope) == ENUMERAL_TYPE)
     t = lookup_enumerator (scope, name);
@@ -4870,99 +5088,19 @@ lookup_using_namespace (tree name, struc
   return val->value != error_mark_node;
 }
 
-/* Returns true iff VEC contains TARGET.  */
-
-static bool
-tree_vec_contains (vec<tree, va_gc> *vec, tree target)
-{
-  unsigned int i;
-  tree elt;
-  FOR_EACH_VEC_SAFE_ELT (vec,i,elt)
-    if (elt == target)
-      return true;
-  return false;
-}
-
 /* [namespace.qual]
    Accepts the NAME to lookup and its qualifying SCOPE.
    Returns the name/type pair found into the cxx_binding *RESULT,
    or false on error.  */
 
 static bool
-qualified_lookup_using_namespace (tree name, tree scope,
-				  struct scope_binding *result, int flags)
+qualified_namespace_lookup (tree scope, name_lookup *lookup)
 {
-  /* Maintain a list of namespaces visited...  */
-  vec<tree, va_gc> *seen = NULL;
-  vec<tree, va_gc> *seen_inline = NULL;
-  /* ... and a list of namespace yet to see.  */
-  vec<tree, va_gc> *todo = NULL;
-  vec<tree, va_gc> *todo_maybe = NULL;
-  vec<tree, va_gc> *todo_inline = NULL;
-  tree usings;
   timevar_start (TV_NAME_LOOKUP);
-  /* Look through namespace aliases.  */
-  scope = ORIGINAL_NAMESPACE (scope);
-
-  query_oracle (name);
-
-  /* Algorithm: Starting with SCOPE, walk through the set of used
-     namespaces.  For each used namespace, look through its inline
-     namespace set for any bindings and usings.  If no bindings are
-     found, add any usings seen to the set of used namespaces.  */
-  vec_safe_push (todo, scope);
-
-  while (todo->length ())
-    {
-      bool found_here;
-      scope = todo->pop ();
-      if (tree_vec_contains (seen, scope))
-	continue;
-      vec_safe_push (seen, scope);
-      vec_safe_push (todo_inline, scope);
-
-      found_here = false;
-      while (todo_inline->length ())
-	{
-	  cxx_binding *binding;
-
-	  scope = todo_inline->pop ();
-	  if (tree_vec_contains (seen_inline, scope))
-	    continue;
-	  vec_safe_push (seen_inline, scope);
-
-	  binding = find_namespace_binding (scope, name);
-	  if (binding)
-	    {
-	      ambiguous_decl (result, binding, flags);
-	      if (result->type || result->value)
-		found_here = true;
-	    }
-
-	  for (usings = DECL_NAMESPACE_USING (scope); usings;
-	       usings = TREE_CHAIN (usings))
-	    if (!TREE_INDIRECT_USING (usings))
-	      {
-		if (is_associated_namespace (scope, TREE_PURPOSE (usings)))
-		  vec_safe_push (todo_inline, TREE_PURPOSE (usings));
-		else
-		  vec_safe_push (todo_maybe, TREE_PURPOSE (usings));
-	      }
-	}
-
-      if (found_here)
-	vec_safe_truncate (todo_maybe, 0);
-      else
-	while (vec_safe_length (todo_maybe))
-	  vec_safe_push (todo, todo_maybe->pop ());
-    }
-  vec_free (todo);
-  vec_free (todo_maybe);
-  vec_free (todo_inline);
-  vec_free (seen);
-  vec_free (seen_inline);
+  query_oracle (lookup->name);
+  bool found = lookup->search_qualified (ORIGINAL_NAMESPACE (scope));
   timevar_stop (TV_NAME_LOOKUP);
-  return result->value != error_mark_node;
+  return found;
 }
 
 /* Helper function for lookup_name_fuzzy.