This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[C++ PATCH] Reimplement ADL


This patch reimplements ADL.

I replace the existing adl_lookup object with a new name_lookup object, and move all the workers into it as member fns.

In terms of implementation, ADL requires us to look in a bunch of places, and we obviously want to look in each place only once. The current implementation uses a vector, which it scans to see if we've met the class or namespace before. Not even a hash table!

Anyway, this implementation introduces LOOKUP_SEEN_P and LOOKUP_FOUND_P to directly mark the DECL node. Hence determination is now O(1) rather than O(N^2). We still have a vector to recall which decls we need to unmark at the end of the lookup. We need two markers on a class, because depending on how we found it we may need to search additional things about it. (These two maker bits will be used in later changes too.)

One quirk is that ADL can be recursive. ADL can cause template instantiation, which can in turn cause a different ADL to happen. The new testcase is an example of this. So, we need to detect this and undo/redo the outer DECL marking during the inner ADL. Thus implementing a simple chain of ADLs and using their record of which decls got marked to undo/redo. The fiddly bit there is recording whether LOOKUP_FOUND_P was set or not (LOOKUP_SEEN_P will be). To record that I simply push those DECLS with lookup_found_p set onto the stack. They'll thus appear twice, and we can infer from the second sighting that it had FOUND_P set (and pop the stack). The recursion is a rare event, so we optimize the non-recursive case.

I use a static vec for the scopes of outermost lookup object. That'll avoid malloc/free for every lookup in the usual case. Inner lookups get their own stack (but as mentioned are rare).

I still keep the old code's determination of whether a found fn was in the original lookup or not. That will go away soon. As will the iteration over inline namespaces.

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

	gcc/cp/
	* cp-tree.h (LOOKUP_SEEN_P, LOOKUP_FOUND_P): New.
	* name-lookup.h (lookup_arg_dependent): Return plain tree.
	* name-lookup.c (arg_lookup, arg_assoc, arg_assoc_args,
	arg_assoc_args_vec, arg_assoc_type, add_function,
	arg_assoc_namespace, arg_assoc_class_only, arg_assoc_bases,
	arg_assoc_class, arg_assoc_template_arg, arg_assoc,
	lookup_arg_dependent_1): Delete.
	(name_lookup): New lookup object.
	(name_lookup::preserve_state, name_lookup::restore_state,
	name_lookup::mark_seen, name_lookup::find_and_mark,
	name_lookup::add_fns, name_lookup::adl_namespace_only,
	name_lookup::adl_namespace, name_lookup::adl_class_only,
	name_lookup::adl_bases, name_lookup::adl_class,
	name_lookup::adl_expr, name_lookup::adl_type,
	name_lookup::adl_template_arg, name_lookup::search_adl): New.
	(lookup_arg_dependent): Return a plain tree.  Adjust.
	(is_associated_namespace): Move later.
	gcc/cp/
	* g++.dg/lookup/koenig14.C: New.

Index: cp/cp-tree.h
===================================================================
--- cp/cp-tree.h	(revision 248452)
+++ cp/cp-tree.h	(working copy)
@@ -395,6 +395,7 @@ extern GTY(()) tree cp_global_trees[CPTI
       DECL_TINFO_P (in VAR_DECL)
       FUNCTION_REF_QUALIFIED (in FUNCTION_TYPE, METHOD_TYPE)
       OVL_LOOKUP_P (in OVERLOAD)
+      LOOKUP_FOUND_P (in RECORD_TYPE, UNION_TYPE, NAMESPACE_DECL)
    5: C_IS_RESERVED_WORD (in IDENTIFIER_NODE)
       DECL_VTABLE_OR_VTT_P (in VAR_DECL)
       FUNCTION_RVALUE_QUALIFIED (in FUNCTION_TYPE, METHOD_TYPE)
@@ -648,10 +649,17 @@ typedef struct ptrmem_cst * ptrmem_cst_t
     && MAIN_NAME_P (DECL_NAME (NODE))			\
     && flag_hosted)
 
-/* The overloaded FUNCTION_DECL.  */
+/* Lookup walker marking.  */
+#define LOOKUP_SEEN_P(NODE) TREE_VISITED(NODE)
+#define LOOKUP_FOUND_P(NODE) \
+  TREE_LANG_FLAG_4 (TREE_CHECK3(NODE,RECORD_TYPE,UNION_TYPE,NAMESPACE_DECL))
+
+/* These two accessors should only be used by OVL manipulators.
+   Other users should use iterators and convenience functions.  */
 #define OVL_FUNCTION(NODE) \
   (((struct tree_overload*)OVERLOAD_CHECK (NODE))->function)
 #define OVL_CHAIN(NODE)      TREE_CHAIN (NODE)
+
 /* Polymorphic access to FUNCTION and CHAIN.  */
 #define OVL_CURRENT(NODE)	\
   ((TREE_CODE (NODE) == OVERLOAD) ? OVL_FUNCTION (NODE) : (NODE))
Index: cp/name-lookup.c
===================================================================
--- cp/name-lookup.c	(revision 248452)
+++ cp/name-lookup.c	(working copy)
@@ -160,208 +160,274 @@ find_local_binding (cp_binding_level *b,
   return NULL;
 }
 
-/* [basic.lookup.koenig] */
-/* A nonzero return value in the functions below indicates an error.  */
-
-struct arg_lookup
+struct name_lookup
 {
-  tree name;
-  vec<tree, va_gc> *args;
-  vec<tree, va_gc> *namespaces;
-  vec<tree, va_gc> *classes;
-  tree functions;
+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.  */
+  vec<tree, va_heap, vl_embed> *scopes;
+  name_lookup *previous; /* Previously active lookup.  */
   hash_set<tree> *fn_set;
+
+protected:
+  /* Marked scope stack for outermost name lookup.  */
+  static vec<tree, va_heap, vl_embed> *shared_scopes;
+  /* Currently active lookup.  */
+  static name_lookup *active;
+
+public:
+  name_lookup (tree n)
+  : name (n), value (NULL_TREE), type (NULL_TREE),
+    scopes (NULL), previous (NULL), fn_set (NULL)
+  {
+    preserve_state ();
+  }
+  ~name_lookup ()
+  {
+    gcc_checking_assert (!fn_set);
+    restore_state ();
+  }
+
+private: /* Uncopyable, unmovable, unassignable. I am a rock. */
+  name_lookup (const name_lookup &);
+  name_lookup &operator= (const name_lookup &);
+
+protected:
+  static bool seen_p (tree scope)
+  {
+    return LOOKUP_SEEN_P (scope);
+  }
+  static bool found_p (tree scope)
+  {
+    return LOOKUP_FOUND_P (scope);
+  }
+  
+  void mark_seen (tree scope); /* Mark and add to scope vector. */
+  static void mark_found (tree scope)
+  {
+    gcc_checking_assert (seen_p (scope));
+    LOOKUP_FOUND_P (scope) = true;
+  }
+  bool see_and_mark (tree scope)
+  {
+    bool ret = seen_p (scope);
+    if (!ret)
+      mark_seen (scope);
+    return ret;
+  }
+  bool find_and_mark (tree scope);
+
+private:
+  void preserve_state ();
+  void restore_state ();
+
+ private:
+  void add_fns (tree);
+
+  void adl_expr (tree);
+  void adl_type (tree);
+  void adl_template_arg (tree);
+  void adl_class (tree);
+  void adl_bases (tree);
+  void adl_class_only (tree);
+  void adl_namespace (tree);
+  void adl_namespace_only (tree);
+
+public:
+  tree search_adl (tree fns, vec<tree, va_gc> *args);
 };
 
-static bool arg_assoc (struct arg_lookup*, tree);
-static bool arg_assoc_args (struct arg_lookup*, tree);
-static bool arg_assoc_args_vec (struct arg_lookup*, vec<tree, va_gc> *);
-static bool arg_assoc_type (struct arg_lookup*, tree);
-static bool add_function (struct arg_lookup *, tree);
-static bool arg_assoc_namespace (struct arg_lookup *, tree);
-static bool arg_assoc_class_only (struct arg_lookup *, tree);
-static bool arg_assoc_bases (struct arg_lookup *, tree);
-static bool arg_assoc_class (struct arg_lookup *, tree);
-static bool arg_assoc_template_arg (struct arg_lookup*, tree);
+/* Scope stack shared by all outermost lookups.  This avoids us
+   allocating and freeing on every single lookup.  */
+vec<tree, va_heap, vl_embed> *name_lookup::shared_scopes;
+
+/* Currently active lookup.  */
+name_lookup *name_lookup::active;
+
+/* Name lookup is recursive, becase ADL can cause template
+   instatiation.  This is of course a rare event, so we optimize for
+   it not happening.  When we discover an active name-lookup, which
+   must be an ADL lookup,  we need to unmark the marked scopes and also
+   unmark the lookup we might have been accumulating.  */
+
+void
+name_lookup::preserve_state ()
+{
+  previous = active;
+  if (previous)
+    {
+      unsigned length = vec_safe_length (previous->scopes);
+      vec_safe_reserve (previous->scopes, length * 2);
+      for (unsigned ix = length; ix--;)
+	{
+	  tree decl = (*previous->scopes)[ix];
 
-/* Add a function to the lookup structure.
-   Returns true on error.  */
+	  gcc_checking_assert (LOOKUP_SEEN_P (decl));
+	  LOOKUP_SEEN_P (decl) = false;
 
-static bool
-add_function (struct arg_lookup *k, tree fn)
-{
-  if (!is_overloaded_fn (fn))
-    /* All names except those of (possibly overloaded) functions and
-       function templates are ignored.  */;
-  else if (k->fn_set && k->fn_set->add (fn))
-    /* It's already in the list.  */;
-  else if (!k->functions && TREE_CODE (fn) != TEMPLATE_DECL)
-    k->functions = fn;
-  else if (fn == k->functions)
-    ;
+	  /* Preserve the FOUND_P state on the interrupted lookup's
+	     stack.  */
+	  if (LOOKUP_FOUND_P (decl))
+	    {
+	      LOOKUP_FOUND_P (decl) = false;
+	      previous->scopes->quick_push (decl);
+	    }
+	}
+    }
   else
-    k->functions = lookup_add (fn, k->functions);
-
-  return false;
+    scopes = shared_scopes;
+  active = this;
 }
 
-/* Returns true iff CURRENT has declared itself to be an associated
-   namespace of SCOPE via a strong using-directive (or transitive chain
-   thereof).  Both are namespaces.  */
+/* Restore the marking state of a lookup we interrupted.  */
 
-bool
-is_associated_namespace (tree current, tree scope)
+void
+name_lookup::restore_state ()
 {
-  vec<tree, va_gc> *seen = make_tree_vector ();
-  vec<tree, va_gc> *todo = make_tree_vector ();
-  tree t;
-  bool ret;
+  /* Unmark and empty this lookup's scope stack.  */
+  for (unsigned ix = vec_safe_length (scopes); ix--;)
+    {
+      tree decl = scopes->pop ();
+      gcc_checking_assert (LOOKUP_SEEN_P (decl));
+      LOOKUP_SEEN_P (decl) = false;
+      LOOKUP_FOUND_P (decl) = false;
+    }
 
-  while (1)
+  active = previous;
+  if (previous)
     {
-      if (scope == current)
-	{
-	  ret = true;
-	  break;
-	}
-      vec_safe_push (seen, scope);
-      for (t = DECL_NAMESPACE_ASSOCIATIONS (scope); t; t = TREE_CHAIN (t))
-	if (!vec_member (TREE_PURPOSE (t), seen))
-	  vec_safe_push (todo, TREE_PURPOSE (t));
-      if (!todo->is_empty ())
-	{
-	  scope = todo->last ();
-	  todo->pop ();
-	}
-      else
+      unsigned length = vec_safe_length (previous->scopes);
+      for (unsigned ix = 0; ix != length; ix++)
 	{
-	  ret = false;
-	  break;
-	}
-    }
+	  tree decl = (*previous->scopes)[ix];
+	  if (LOOKUP_SEEN_P (decl))
+	    {
+	      /* The remainder of the scope stack must be recording
+		 FOUND_P decls, which we want to pop off.  */
+	      do
+		{
+		  tree decl = previous->scopes->pop ();
+		  gcc_checking_assert (LOOKUP_SEEN_P (decl)
+				       && !LOOKUP_FOUND_P (decl));
+		  LOOKUP_FOUND_P (decl) = true;
+		}
+	      while (++ix != length);
+	      break;
+	    }
 
-  release_tree_vector (seen);
-  release_tree_vector (todo);
+	  gcc_checking_assert (!LOOKUP_FOUND_P (decl));
+	  LOOKUP_SEEN_P (decl) = true;
+	}
 
-  return ret;
+      free (scopes);
+    }
+  else
+    shared_scopes = scopes;
 }
 
-/* Add functions of a namespace to the lookup structure.
-   Returns true on error.  */
+void
+name_lookup::mark_seen (tree scope)
+{
+  gcc_checking_assert (!seen_p (scope));
+  LOOKUP_SEEN_P (scope) = true;
+  vec_safe_push (scopes, scope);
+}
 
-static bool
-arg_assoc_namespace (struct arg_lookup *k, tree scope)
+bool
+name_lookup::find_and_mark (tree scope)
 {
-  tree value;
+  bool result = LOOKUP_FOUND_P (scope);
+  if (!result)
+    {
+      LOOKUP_FOUND_P (scope) = true;
+      if (!LOOKUP_SEEN_P (scope))
+	vec_safe_push (scopes, scope);
+    }
 
-  if (vec_member (scope, k->namespaces))
-    return false;
-  vec_safe_push (k->namespaces, scope);
-
-  /* Check out our super-users.  */
-  for (value = DECL_NAMESPACE_ASSOCIATIONS (scope); value;
-       value = TREE_CHAIN (value))
-    if (arg_assoc_namespace (k, TREE_PURPOSE (value)))
-      return true;
-
-  /* Also look down into inline namespaces.  */
-  for (value = DECL_NAMESPACE_USING (scope); value;
-       value = TREE_CHAIN (value))
-    if (is_associated_namespace (scope, TREE_PURPOSE (value)))
-      if (arg_assoc_namespace (k, TREE_PURPOSE (value)))
-	return true;
-
-  value = get_namespace_binding (scope, k->name);
-  if (!value)
-    return false;
+  return result;
+}
 
-  value = ovl_skip_hidden (value);
-  
-  for (; value; value = OVL_NEXT (value))
+/* FNS is a value binding.  If it is a (set of overloaded) functions,
+   add them into the current value.  */
+
+void
+name_lookup::add_fns (tree fns)
+{
+  if (!fns)
+    return;
+  else if (TREE_CODE (fns) == OVERLOAD)
     {
-      if (add_function (k, OVL_CURRENT (value)))
-	return true;
+      if (TREE_TYPE (fns) != unknown_type_node)
+	fns = OVL_FUNCTION (fns);
     }
+  else if (!DECL_DECLARES_FUNCTION_P (fns))
+    return;
 
-  return false;
+  /* Only add those that aren't already there.  */
+  for (ovl_iterator iter (fns); iter; ++iter)
+    if (!fn_set->add (*iter))
+      value = lookup_add (*iter, value);
 }
 
-/* Adds everything associated with a template argument to the lookup
-   structure.  Returns true on error.  */
+/* Add functions of a namespace to the lookup structure.  */
 
-static bool
-arg_assoc_template_arg (struct arg_lookup *k, tree arg)
+void
+name_lookup::adl_namespace_only (tree scope)
 {
-  /* [basic.lookup.koenig]
+  mark_seen (scope);
 
-     If T is a template-id, its associated namespaces and classes are
-     ... the namespaces and classes associated with the types of the
-     template arguments provided for template type parameters
-     (excluding template template parameters); the namespaces in which
-     any template template arguments are defined; and the classes in
-     which any member templates used as template template arguments
-     are defined.  [Note: non-type template arguments do not
-     contribute to the set of associated namespaces.  ]  */
+  /* Look down into inline namespaces.  */
+  for (tree inner = NAMESPACE_LEVEL (scope)->namespaces;
+       inner; inner = TREE_CHAIN (inner))
+    if (DECL_NAMESPACE_INLINE_P (inner))
+      adl_namespace_only (inner);
 
-  /* Consider first template template arguments.  */
-  if (TREE_CODE (arg) == TEMPLATE_TEMPLATE_PARM
-      || TREE_CODE (arg) == UNBOUND_CLASS_TEMPLATE)
-    return false;
-  else if (TREE_CODE (arg) == TEMPLATE_DECL)
-    {
-      tree ctx = CP_DECL_CONTEXT (arg);
+  if (cxx_binding *binding = find_namespace_binding (scope, name))
+    add_fns (ovl_skip_hidden (binding->value));
+}
 
-      /* It's not a member template.  */
-      if (TREE_CODE (ctx) == NAMESPACE_DECL)
-	return arg_assoc_namespace (k, ctx);
-      /* Otherwise, it must be member template.  */
-      else
-	return arg_assoc_class_only (k, ctx);
-    }
-  /* It's an argument pack; handle it recursively.  */
-  else if (ARGUMENT_PACK_P (arg))
-    {
-      tree args = ARGUMENT_PACK_ARGS (arg);
-      int i, len = TREE_VEC_LENGTH (args);
-      for (i = 0; i < len; ++i) 
-	if (arg_assoc_template_arg (k, TREE_VEC_ELT (args, i)))
-	  return true;
+/* Find the containing non-inlined namespace, add it and all its
+   inlinees.  */
 
-      return false;
-    }
-  /* It's not a template template argument, but it is a type template
-     argument.  */
-  else if (TYPE_P (arg))
-    return arg_assoc_type (k, arg);
-  /* It's a non-type template argument.  */
-  else
-    return false;
+void
+name_lookup::adl_namespace (tree scope)
+{
+  if (seen_p (scope))
+    return;
+
+  /* Find the containing non-inline namespace.  */
+  while (DECL_NAMESPACE_INLINE_P (scope))
+    scope = CP_DECL_CONTEXT (scope);
+
+  adl_namespace_only (scope);
 }
 
-/* Adds the class and its friends to the lookup structure.
-   Returns true on error.  */
+/* Adds the class and its friends to the lookup structure.  */
 
-static bool
-arg_assoc_class_only (struct arg_lookup *k, tree type)
+void
+name_lookup::adl_class_only (tree type)
 {
-  tree list, friends, context;
-
   /* Backend-built structures, such as __builtin_va_list, aren't
      affected by all this.  */
   if (!CLASS_TYPE_P (type))
-    return false;
+    return;
+
+  type = TYPE_MAIN_VARIANT (type);
+
+  if (see_and_mark (type))
+    return;
 
-  context = decl_namespace_context (type);
-  if (arg_assoc_namespace (k, context))
-    return true;
+  tree context = decl_namespace_context (type);
+  adl_namespace (context);
 
   complete_type (type);
 
-  /* Process friends.  */
-  for (list = DECL_FRIENDLIST (TYPE_MAIN_DECL (type)); list;
+  /* Add friends.  */
+  for (tree list = DECL_FRIENDLIST (TYPE_MAIN_DECL (type)); list;
        list = TREE_CHAIN (list))
-    if (k->name == FRIEND_NAME (list))
-      for (friends = FRIEND_DECLS (list); friends;
+    if (name == FRIEND_NAME (list))
+      for (tree friends = FRIEND_DECLS (list); friends;
 	   friends = TREE_CHAIN (friends))
 	{
 	  tree fn = TREE_VALUE (friends);
@@ -370,40 +436,34 @@ arg_assoc_class_only (struct arg_lookup
 	     (i.e. unqualified) declarations.  */
 	  if (CP_DECL_CONTEXT (fn) != context)
 	    continue;
+
 	  /* Template specializations are never found by name lookup.
 	     (Templates themselves can be found, but not template
 	     specializations.)  */
 	  if (TREE_CODE (fn) == FUNCTION_DECL && DECL_USE_TEMPLATE (fn))
 	    continue;
-	  if (add_function (k, fn))
-	    return true;
-	}
 
-  return false;
+	  add_fns (fn);
+	}
 }
 
 /* Adds the class and its bases to the lookup structure.
    Returns true on error.  */
 
-static bool
-arg_assoc_bases (struct arg_lookup *k, tree type)
+void
+name_lookup::adl_bases (tree type)
 {
-  if (arg_assoc_class_only (k, type))
-    return true;
+  adl_class_only (type);
 
-  if (TYPE_BINFO (type))
+  /* Process baseclasses.  */
+  if (tree binfo = TYPE_BINFO (type))
     {
-      /* Process baseclasses.  */
-      tree binfo, base_binfo;
+      tree base_binfo;
       int i;
 
-      for (binfo = TYPE_BINFO (type), i = 0;
-	   BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
-	if (arg_assoc_bases (k, BINFO_TYPE (base_binfo)))
-	  return true;
+      for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+	adl_bases (BINFO_TYPE (base_binfo));
     }
-
-  return false;
 }
 
 /* Adds everything associated with a class argument type to the lookup
@@ -422,271 +482,268 @@ arg_assoc_bases (struct arg_lookup *k, t
    non-type template arguments do not contribute to the set of associated
    namespaces.  --end note] */
 
-static bool
-arg_assoc_class (struct arg_lookup *k, tree type)
+void
+name_lookup::adl_class (tree type)
 {
-  tree list;
-  int i;
-
   /* Backend build structures, such as __builtin_va_list, aren't
      affected by all this.  */
   if (!CLASS_TYPE_P (type))
-    return false;
+    return;
+
+  type = TYPE_MAIN_VARIANT (type);
+  /* We don't set found here because we have to have set seen first,
+     which is done in the adl_bases walk.  */
+  if (found_p (type))
+    return;
 
-  if (vec_member (type, k->classes))
-    return false;
-  vec_safe_push (k->classes, type);
-
-  if (TYPE_CLASS_SCOPE_P (type)
-      && arg_assoc_class_only (k, TYPE_CONTEXT (type)))
-    return true;
+  adl_bases (type);
+  mark_found (type);
 
-  if (arg_assoc_bases (k, type))
-    return true;
+  if (TYPE_CLASS_SCOPE_P (type))
+    adl_class_only (TYPE_CONTEXT (type));
 
   /* Process template arguments.  */
   if (CLASSTYPE_TEMPLATE_INFO (type)
       && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (type)))
     {
-      list = INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type));
-      for (i = 0; i < TREE_VEC_LENGTH (list); ++i)
-	if (arg_assoc_template_arg (k, TREE_VEC_ELT (list, i)))
-	  return true;
+      tree list = INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type));
+      for (int i = 0; i < TREE_VEC_LENGTH (list); ++i)
+	adl_template_arg (TREE_VEC_ELT (list, i));
     }
-
-  return false;
 }
 
-/* Adds everything associated with a given type.
-   Returns 1 on error.  */
+void
+name_lookup::adl_expr (tree expr)
+{
+  if (!expr)
+    return;
+
+  gcc_assert (!TYPE_P (expr));
+
+  if (TREE_TYPE (expr) != unknown_type_node)
+    {
+      adl_type (TREE_TYPE (expr));
+      return;
+    }
+
+  if (TREE_CODE (expr) == ADDR_EXPR)
+    expr = TREE_OPERAND (expr, 0);
+  if (TREE_CODE (expr) == COMPONENT_REF
+      || TREE_CODE (expr) == OFFSET_REF)
+    expr = TREE_OPERAND (expr, 1);
+  expr = MAYBE_BASELINK_FUNCTIONS (expr);
 
-static bool
-arg_assoc_type (struct arg_lookup *k, tree type)
+  if (OVL_P (expr))
+    for (lkp_iterator iter (expr); iter; ++iter)
+      adl_type (TREE_TYPE (*iter));
+  else if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
+    {
+      /* The working paper doesn't currently say how to handle
+	 template-id arguments.  The sensible thing would seem to be
+	 to handle the list of template candidates like a normal
+	 overload set, and handle the template arguments like we do
+	 for class template specializations.  */
+
+      /* First the templates.  */
+      adl_expr (TREE_OPERAND (expr, 0));
+
+      /* Now the arguments.  */
+      if (tree args = TREE_OPERAND (expr, 1))
+	for (int ix = TREE_VEC_LENGTH (args); ix--;)
+	  adl_template_arg (TREE_VEC_ELT (args, ix));
+    }
+}
+
+void
+name_lookup::adl_type (tree type)
 {
-  /* As we do not get the type of non-type dependent expressions
-     right, we can end up with such things without a type.  */
   if (!type)
-    return false;
+    return;
 
   if (TYPE_PTRDATAMEM_P (type))
     {
       /* Pointer to member: associate class type and value type.  */
-      if (arg_assoc_type (k, TYPE_PTRMEM_CLASS_TYPE (type)))
-	return true;
-      return arg_assoc_type (k, TYPE_PTRMEM_POINTED_TO_TYPE (type));
-    }
-  else switch (TREE_CODE (type))
-    {
-    case ERROR_MARK:
-      return false;
-    case VOID_TYPE:
-    case INTEGER_TYPE:
-    case REAL_TYPE:
-    case COMPLEX_TYPE:
-    case VECTOR_TYPE:
-    case BOOLEAN_TYPE:
-    case FIXED_POINT_TYPE:
-    case DECLTYPE_TYPE:
-    case NULLPTR_TYPE:
-      return false;
+      adl_type (TYPE_PTRMEM_CLASS_TYPE (type));
+      adl_type (TYPE_PTRMEM_POINTED_TO_TYPE (type));
+      return;
+    }
+
+  switch (TREE_CODE (type))
+    {
     case RECORD_TYPE:
       if (TYPE_PTRMEMFUNC_P (type))
-	return arg_assoc_type (k, TYPE_PTRMEMFUNC_FN_TYPE (type));
+	{
+	  adl_type (TYPE_PTRMEMFUNC_FN_TYPE (type));
+	  return;
+	}
       /* FALLTHRU */
     case UNION_TYPE:
-      return arg_assoc_class (k, type);
-    case POINTER_TYPE:
-    case REFERENCE_TYPE:
-    case ARRAY_TYPE:
-      return arg_assoc_type (k, TREE_TYPE (type));
-    case ENUMERAL_TYPE:
-      if (TYPE_CLASS_SCOPE_P (type)
-	  && arg_assoc_class_only (k, TYPE_CONTEXT (type)))
-	return true;
-      return arg_assoc_namespace (k, decl_namespace_context (type));
+      adl_class (type);
+      return;
+
     case METHOD_TYPE:
       /* The basetype is referenced in the first arg type, so just
 	 fall through.  */
     case FUNCTION_TYPE:
       /* Associate the parameter types.  */
-      if (arg_assoc_args (k, TYPE_ARG_TYPES (type)))
-	return true;
-      /* Associate the return type.  */
-      return arg_assoc_type (k, TREE_TYPE (type));
-    case TEMPLATE_TYPE_PARM:
-    case BOUND_TEMPLATE_TEMPLATE_PARM:
-      return false;
-    case TYPENAME_TYPE:
-      return false;
+      for (tree args = TYPE_ARG_TYPES (type); args; args = TREE_CHAIN (args))
+	adl_type (TREE_VALUE (args));
+      /* FALLTHROUGH */
+
+    case POINTER_TYPE:
+    case REFERENCE_TYPE:
+    case ARRAY_TYPE:
+      adl_type (TREE_TYPE (type));
+      return;
+
+    case ENUMERAL_TYPE:
+      if (TYPE_CLASS_SCOPE_P (type))
+	adl_class_only (TYPE_CONTEXT (type));
+      adl_namespace (decl_namespace_context (type));
+      return;
+
     case LANG_TYPE:
       gcc_assert (type == unknown_type_node
 		  || type == init_list_type_node);
-      return false;
+      return;
+
     case TYPE_PACK_EXPANSION:
-      return arg_assoc_type (k, PACK_EXPANSION_PATTERN (type));
+      adl_type (PACK_EXPANSION_PATTERN (type));
+      return;
 
     default:
-      gcc_unreachable ();
+      break;
     }
-  return false;
 }
 
-/* Adds everything associated with arguments.  Returns true on error.  */
+/* Adds everything associated with a template argument to the lookup
+   structure.  */
 
-static bool
-arg_assoc_args (struct arg_lookup *k, tree args)
+void
+name_lookup::adl_template_arg (tree arg)
 {
-  for (; args; args = TREE_CHAIN (args))
-    if (arg_assoc (k, TREE_VALUE (args)))
-      return true;
-  return false;
+  /* [basic.lookup.koenig]
+
+     If T is a template-id, its associated namespaces and classes are
+     ... the namespaces and classes associated with the types of the
+     template arguments provided for template type parameters
+     (excluding template template parameters); the namespaces in which
+     any template template arguments are defined; and the classes in
+     which any member templates used as template template arguments
+     are defined.  [Note: non-type template arguments do not
+     contribute to the set of associated namespaces.  ]  */
+
+  /* Consider first template template arguments.  */
+  if (TREE_CODE (arg) == TEMPLATE_TEMPLATE_PARM
+      || TREE_CODE (arg) == UNBOUND_CLASS_TEMPLATE)
+    ;
+  else if (TREE_CODE (arg) == TEMPLATE_DECL)
+    {
+      tree ctx = CP_DECL_CONTEXT (arg);
+
+      /* It's not a member template.  */
+      if (TREE_CODE (ctx) == NAMESPACE_DECL)
+	adl_namespace (ctx);
+      /* Otherwise, it must be member template.  */
+      else
+	adl_class_only (ctx);
+    }
+  /* It's an argument pack; handle it recursively.  */
+  else if (ARGUMENT_PACK_P (arg))
+    {
+      tree args = ARGUMENT_PACK_ARGS (arg);
+      int i, len = TREE_VEC_LENGTH (args);
+      for (i = 0; i < len; ++i) 
+	adl_template_arg (TREE_VEC_ELT (args, i));
+    }
+  /* It's not a template template argument, but it is a type template
+     argument.  */
+  else if (TYPE_P (arg))
+    adl_type (arg);
 }
 
-/* Adds everything associated with an argument vector.  Returns true
-   on error.  */
+/* Perform ADL lookup.  FNS is the existing lookup result and ARGS are
+   the call arguments.  */
 
-static bool
-arg_assoc_args_vec (struct arg_lookup *k, vec<tree, va_gc> *args)
+tree
+name_lookup::search_adl (tree fns, vec<tree, va_gc> *args)
 {
-  unsigned int ix;
-  tree arg;
+  value = fns;
 
-  FOR_EACH_VEC_SAFE_ELT (args, ix, arg)
-    if (arg_assoc (k, arg))
-      return true;
-  return false;
-}
-
-/* Adds everything associated with a given tree_node.  Returns 1 on error.  */
-
-static bool
-arg_assoc (struct arg_lookup *k, tree n)
-{
-  if (n == error_mark_node)
-    return false;
-
-  if (TYPE_P (n))
-    return arg_assoc_type (k, n);
-
-  if (! type_unknown_p (n))
-    return arg_assoc_type (k, TREE_TYPE (n));
-
-  if (TREE_CODE (n) == ADDR_EXPR)
-    n = TREE_OPERAND (n, 0);
-  if (TREE_CODE (n) == COMPONENT_REF)
-    n = TREE_OPERAND (n, 1);
-  if (TREE_CODE (n) == OFFSET_REF)
-    n = TREE_OPERAND (n, 1);
-  while (TREE_CODE (n) == TREE_LIST)
-    n = TREE_VALUE (n);
-  if (BASELINK_P (n))
-    n = BASELINK_FUNCTIONS (n);
-
-  if (TREE_CODE (n) == FUNCTION_DECL)
-    return arg_assoc_type (k, TREE_TYPE (n));
-  if (TREE_CODE (n) == TEMPLATE_ID_EXPR)
-    {
-      /* The working paper doesn't currently say how to handle template-id
-	 arguments.  The sensible thing would seem to be to handle the list
-	 of template candidates like a normal overload set, and handle the
-	 template arguments like we do for class template
-	 specializations.  */
-      tree templ = TREE_OPERAND (n, 0);
-      tree args = TREE_OPERAND (n, 1);
-      int ix;
+  /* Add the current overload set into the hash table.  */
+  fn_set = new hash_set<tree>;
+  for (lkp_iterator iter (fns); iter; ++iter)
+    fn_set->add (*iter);
 
-      /* First the templates.  */
-      if (arg_assoc (k, templ))
-	return true;
+  unsigned ix;
+  tree arg;
 
-      /* Now the arguments.  */
-      if (args)
-	for (ix = TREE_VEC_LENGTH (args); ix--;)
-	  if (arg_assoc_template_arg (k, TREE_VEC_ELT (args, ix)) == 1)
-	    return true;
-    }
-  else if (TREE_CODE (n) == OVERLOAD)
-    {
-      for (; n; n = OVL_NEXT (n))
-	if (arg_assoc_type (k, TREE_TYPE (OVL_CURRENT (n))))
-	  return true;
-    }
-
-  return false;
-}
-
-/* Performs Koenig lookup depending on arguments, where fns
-   are the functions found in normal lookup.  */
-
-static cp_expr
-lookup_arg_dependent_1 (tree name, tree fns, vec<tree, va_gc> *args)
-{
-  struct arg_lookup k;
-
-  /* Remove any hidden friend functions from the list of functions
-     found so far.  They will be added back by arg_assoc_class as
-     appropriate.  */
-  fns = ovl_skip_hidden (fns);
-
-  k.name = name;
-  k.args = args;
-  k.functions = fns;
-  k.classes = make_tree_vector ();
-
-  /* We previously performed an optimization here by setting
-     NAMESPACES to the current namespace when it was safe. However, DR
-     164 says that namespaces that were already searched in the first
-     stage of template processing are searched again (potentially
-     picking up later definitions) in the second stage. */
-  k.namespaces = make_tree_vector ();
-
-  /* We used to allow duplicates and let joust discard them, but
-     since the above change for DR 164 we end up with duplicates of
-     all the functions found by unqualified lookup.  So keep track
-     of which ones we've seen.  */
-  if (fns)
-    {
-      tree ovl;
-      /* We shouldn't be here if lookup found something other than
-	 namespace-scope functions.  */
-      gcc_assert (DECL_NAMESPACE_SCOPE_P (OVL_CURRENT (fns)));
-      k.fn_set = new hash_set<tree>;
-      for (ovl = fns; ovl; ovl = OVL_NEXT (ovl))
-	k.fn_set->add (OVL_CURRENT (ovl));
-    }
-  else
-    k.fn_set = NULL;
+  FOR_EACH_VEC_ELT_REVERSE (*args, ix, arg)
+    /* OMP reduction operators put a type as the first arg.  I don't
+       suppose we should ADL on that?  */
+    if (!TYPE_P (arg))
+      adl_expr (arg);
 
-  arg_assoc_args_vec (&k, args);
+  delete fn_set;
+  fn_set = NULL;
 
-  fns = k.functions;
-  
-  if (fns
-      && !VAR_P (fns)
-      && !is_overloaded_fn (fns))
-    {
-      error ("argument dependent lookup finds %q+D", fns);
-      error ("  in call to %qD", name);
-      fns = error_mark_node;
-    }
+  fns = value;
 
-  release_tree_vector (k.classes);
-  release_tree_vector (k.namespaces);
-  delete k.fn_set;
-    
   return fns;
 }
 
-/* Wrapper for lookup_arg_dependent_1.  */
+/* 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).  */
 
-cp_expr
+tree
 lookup_arg_dependent (tree name, tree fns, vec<tree, va_gc> *args)
 {
-  cp_expr ret;
-  bool subtime;
-  subtime = timevar_cond_start (TV_NAME_LOOKUP);
-  ret = lookup_arg_dependent_1 (name, fns, args);
+  bool subtime = timevar_cond_start (TV_NAME_LOOKUP);
+  name_lookup lookup (name);
+  fns = lookup.search_adl (fns, args);
   timevar_cond_stop (TV_NAME_LOOKUP, subtime);
+  return fns;
+}
+
+/* Returns true iff CURRENT has declared itself to be an associated
+   namespace of SCOPE via a strong using-directive (or transitive chain
+   thereof).  Both are namespaces.  */
+
+bool
+is_associated_namespace (tree current, tree scope)
+{
+  vec<tree, va_gc> *seen = make_tree_vector ();
+  vec<tree, va_gc> *todo = make_tree_vector ();
+  tree t;
+  bool ret;
+
+  while (1)
+    {
+      if (scope == current)
+	{
+	  ret = true;
+	  break;
+	}
+      vec_safe_push (seen, scope);
+      for (t = DECL_NAMESPACE_ASSOCIATIONS (scope); t; t = TREE_CHAIN (t))
+	if (!vec_member (TREE_PURPOSE (t), seen))
+	  vec_safe_push (todo, TREE_PURPOSE (t));
+      if (!todo->is_empty ())
+	{
+	  scope = todo->last ();
+	  todo->pop ();
+	}
+      else
+	{
+	  ret = false;
+	  break;
+	}
+    }
+
+  release_tree_vector (seen);
+  release_tree_vector (todo);
+
   return ret;
 }
 
Index: cp/name-lookup.h
===================================================================
--- cp/name-lookup.h	(revision 248452)
+++ cp/name-lookup.h	(working copy)
@@ -324,7 +324,7 @@ extern void pop_decl_namespace (void);
 extern void do_namespace_alias (tree, tree);
 extern tree do_class_using_decl (tree, tree);
 extern void do_using_directive (tree);
-extern cp_expr lookup_arg_dependent (tree, tree, vec<tree, va_gc> *);
+extern tree lookup_arg_dependent (tree, tree, vec<tree, va_gc> *);
 extern bool is_associated_namespace (tree, tree);
 extern tree innermost_non_namespace_value (tree);
 extern cxx_binding *outer_binding (tree, cxx_binding *, bool);
Index: testsuite/g++.dg/lookup/koenig14.C
===================================================================
--- testsuite/g++.dg/lookup/koenig14.C	(revision 0)
+++ testsuite/g++.dg/lookup/koenig14.C	(working copy)
@@ -0,0 +1,30 @@
+// ADL can be recursive (via instantiation), make sure that works.
+
+namespace X
+{
+  class B {};
+  
+  void frob ();
+  int frob (B); // Inner ADL resolves here
+}
+
+void frob (int);
+void frob (float);
+
+namespace Y
+{
+  struct A {};
+  void frob (void*, void *, void *); // Outer ADL resolves here
+}
+
+template <typename T, typename U>
+struct C : U
+{
+  int ary[sizeof frob(T())]; // ADL occurs here during instantiation
+};
+
+void Foo (C<X::B, Y::A> *p, X::B *q)
+{
+  frob(q, p, q); // ADL causes instantation of C<...>
+  // We will have already searched X by the time the instantation happens
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]