[C++ PATCH] Reimplement ADL

[Jakub Jelinek]

On Thu, May 25, 2017 at 09:03:31AM -0400, Nathan Sidwell wrote:
> 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.

I believe this broke
FAIL: libgomp.c++/udr-12.C (test for excess errors)
UNRESOLVED: libgomp.c++/udr-12.C compilation failed to produce executable
FAIL: libgomp.c++/udr-13.C (test for excess errors)
UNRESOLVED: libgomp.c++/udr-13.C compilation failed to produce executable
FAIL: libgomp.c++/udr-16.C (test for excess errors)
UNRESOLVED: libgomp.c++/udr-16.C compilation failed to produce executable
FAIL: libgomp.c++/udr-2.C (test for excess errors)
UNRESOLVED: libgomp.c++/udr-2.C compilation failed to produce executable
FAIL: libgomp.c++/udr-3.C (test for excess errors)
UNRESOLVED: libgomp.c++/udr-3.C compilation failed to produce executable
FAIL: libgomp.c++/udr-6.C (test for excess errors)
UNRESOLVED: libgomp.c++/udr-6.C compilation failed to produce executable
The OpenMP UDRs can't be found anymore with the patch.

Can you please have a look?

> 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.

	Jakub