[C++ Patch] Fix conersion operator lookup

[Nathan Sidwell <nathan at codesourcery dot com>]

Mark,
Lookup for a particular conversion operator looped unnecessarily, but more
importantly lookup_conversions, which gathers all the visible conversions
would only DTRT in singly inherited hierarchies.

This replacement does the set of parallel lookups that need to be done,
complete with the hiding that happens with virtual bases.  Whilst there
I took advantage of TYPE_HAS_CONVERSION, to avoid unnecessary walking.

booted & tested on i686-pc-linux-gnu, ok?

nathan
--
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

2004-07-21  Nathan Sidwell  <nathan@codesourcery.com>

	* search.c (lookup_conversion_operator): Avoid two loops.
	(add_conversions): Remove.
	(check_hidden_convs, split_conversions,
	lookup_conversions_r):	New.
	(lookup_conversions): Use lookup_conversions_r.

Index: cp/search.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/search.c,v
retrieving revision 1.304
diff -c -3 -p -r1.304 search.c
*** cp/search.c	20 Jul 2004 12:25:30 -0000	1.304
--- cp/search.c	21 Jul 2004 15:00:05 -0000
*************** static base_kind lookup_base_r (tree, tr
*** 51,57 ****
  static int dynamic_cast_base_recurse (tree, tree, bool, tree *);
  static tree dfs_debug_unmarkedp (tree, int, void *);
  static tree dfs_debug_mark (tree, void *);
! static tree add_conversions (tree, void *);
  static int look_for_overrides_r (tree, tree);
  static tree bfs_walk (tree, tree (*) (tree, void *),
  		      tree (*) (tree, int, void *), void *);
--- 51,60 ----
  static int dynamic_cast_base_recurse (tree, tree, bool, tree *);
  static tree dfs_debug_unmarkedp (tree, int, void *);
  static tree dfs_debug_mark (tree, void *);
! static int check_hidden_convs (tree, int, int, tree, tree, tree);
! static tree split_conversions (tree, tree, tree, tree);
! static int lookup_conversions_r (tree, int, int,
! 				 tree, tree, tree, tree, tree *, tree *);
  static int look_for_overrides_r (tree, tree);
  static tree bfs_walk (tree, tree (*) (tree, void *),
  		      tree (*) (tree, int, void *), void *);
*************** lookup_fnfields (tree xbasetype, tree na
*** 1298,1344 ****
  static int
  lookup_conversion_operator (tree class_type, tree type)
  {
!   int pass;
!   int i;
!   tree fn;
!   VEC(tree) *methods;
  
!   methods = CLASSTYPE_METHOD_VEC (class_type);
! 
!   for (pass = 0; pass < 2; ++pass)
!     for (i = CLASSTYPE_FIRST_CONVERSION_SLOT; 
! 	 VEC_iterate (tree, methods, i, fn); ++i)
!       {
! 	/* All the conversion operators come near the beginning of the
! 	   class.  Therefore, if FN is not a conversion operator, there
! 	   is no matching conversion operator in CLASS_TYPE.  */
! 	fn = OVL_CURRENT (fn);
! 	if (!DECL_CONV_FN_P (fn))
! 	  break;
! 	
! 	if (pass == 0)
! 	  {
! 	    /* On the first pass we only consider exact matches.  If
! 	       the types match, this slot is the one where the right
! 	       conversion operators can be found.  */
! 	    if (TREE_CODE (fn) != TEMPLATE_DECL
! 		&& same_type_p (DECL_CONV_FN_TYPE (fn), type))
! 	      return i;
! 	  }
! 	else
! 	  {
! 	    /* On the second pass we look for template conversion
! 	       operators.  It may be possible to instantiate the
! 	       template to get the type desired.  All of the template
! 	       conversion operators share a slot.  By looking for
! 	       templates second we ensure that specializations are
! 	       preferred over templates.  */
! 	    if (TREE_CODE (fn) == TEMPLATE_DECL)
! 	      return i;
! 	  }
!       }
  
!   return -1;
  }
  
  /* TYPE is a class type. Return the index of the fields within
--- 1301,1335 ----
  static int
  lookup_conversion_operator (tree class_type, tree type)
  {
!   int tpl_slot = -1;
  
!   if (TYPE_HAS_CONVERSION (class_type))
!     {
!       int i;
!       tree fn;
!       VEC(tree) *methods = CLASSTYPE_METHOD_VEC (class_type);
!       
!       for (i = CLASSTYPE_FIRST_CONVERSION_SLOT;
! 	   VEC_iterate (tree, methods, i, fn); ++i)
! 	{
! 	  /* All the conversion operators come near the beginning of
! 	     the class.  Therefore, if FN is not a conversion
! 	     operator, there is no matching conversion operator in
! 	     CLASS_TYPE.  */
! 	  fn = OVL_CURRENT (fn);
! 	  if (!DECL_CONV_FN_P (fn))
! 	    break;
! 	  
! 	  if (TREE_CODE (fn) == TEMPLATE_DECL)
! 	    /* All the templated conversion functions are on the same
! 	       slot, so remember it.  */
! 	    tpl_slot = i;
! 	  else if (same_type_p (DECL_CONV_FN_TYPE (fn), type))
! 	    return i;
! 	}
!     }
  
!   return tpl_slot;
  }
  
  /* TYPE is a class type. Return the index of the fields within
*************** reinit_search_statistics (void)
*** 2044,2121 ****
  #endif /* GATHER_STATISTICS */
  }
  
  static tree
! add_conversions (tree binfo, void *data)
  {
!   size_t i;
!   VEC(tree) *method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
!   tree *conversions = (tree *) data;
!   tree tmp;
  
!   /* Some builtin types have no method vector, not even an empty one.  */
!   if (!method_vec)
!     return NULL_TREE;
  
    for (i = CLASSTYPE_FIRST_CONVERSION_SLOT; 
!        VEC_iterate (tree, method_vec, i, tmp);
         ++i)
      {
!       tree name;
  
!       if (!DECL_CONV_FN_P (OVL_CURRENT (tmp)))
  	break;
  
!       name = DECL_NAME (OVL_CURRENT (tmp));
! 
!       /* Make sure we don't already have this conversion.  */
!       if (! IDENTIFIER_MARKED (name))
  	{
! 	  tree t;
  
! 	  /* Make sure that we do not already have a conversion
! 	     operator for this type.  Merely checking the NAME is not
! 	     enough because two conversion operators to the same type
! 	     may not have the same NAME.  */
! 	  for (t = *conversions; t; t = TREE_CHAIN (t))
  	    {
! 	      tree fn;
! 	      for (fn = TREE_VALUE (t); fn; fn = OVL_NEXT (fn))
! 		if (same_type_p (TREE_TYPE (name),
! 				 DECL_CONV_FN_TYPE (OVL_CURRENT (fn))))
! 		  break;
! 	      if (fn)
! 		break;
  	    }
! 	  if (!t)
  	    {
! 	      *conversions = tree_cons (binfo, tmp, *conversions);
! 	      IDENTIFIER_MARKED (name) = 1;
  	    }
  	}
      }
!   return NULL_TREE;
  }
  
  /* Return a TREE_LIST containing all the non-hidden user-defined
     conversion functions for TYPE (and its base-classes).  The
!    TREE_VALUE of each node is a FUNCTION_DECL or an OVERLOAD
!    containing the conversion functions.  The TREE_PURPOSE is the BINFO
!    from which the conversion functions in this node were selected.  */
  
  tree
  lookup_conversions (tree type)
  {
!   tree t;
!   tree conversions = NULL_TREE;
! 
    complete_type (type);
!   if (TYPE_BINFO (type))
!     bfs_walk (TYPE_BINFO (type), add_conversions, 0, &conversions);
  
!   for (t = conversions; t; t = TREE_CHAIN (t))
!     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (t)))) = 0;
  
!   return conversions;
  }
  
  struct overlap_info 
--- 2035,2355 ----
  #endif /* GATHER_STATISTICS */
  }
  
+ /* Helper for lookup_conversions_r.  TO_TYPE is the type converted to
+    by a conversion op in base BINFO.  VIRTUAL_DEPTH is non-zero if
+    BINFO is morally virtual, and VIRTUALNESS is non-zero if virtual
+    bases have been encountered already in the tree walk.  PARENT_CONVS
+    is the list of lists of conversion functions that could hide CONV
+    and OTHER_CONVS is the list of lists of conversion functions that
+    could hide or be hidden by CONV, should virtualness be involved in
+    the hierarchy.  Merely checking the conversion op's name is not
+    enough because two conversion operators to the same type can have
+    different names.  Return non-zero if we are visible.  */
+ 
+ static int
+ check_hidden_convs (tree binfo, int virtual_depth, int virtualness,
+ 		    tree to_type, tree parent_convs, tree other_convs)
+ {
+   tree level, probe;
+ 
+   /* See if we are hidden by a parent conversion.  */
+   for (level = parent_convs; level; level = TREE_CHAIN (level))
+     for (probe = TREE_VALUE (level); probe; probe = TREE_CHAIN (probe))
+       if (same_type_p (to_type, TREE_TYPE (probe)))
+ 	return 0;
+ 
+   if (virtual_depth || virtualness)
+     {
+      /* In a virtual hierarchy, we could be hidden, or could hide a
+         conversion function on the other_convs list.  */
+       for (level = other_convs; level; level = TREE_CHAIN (level))
+ 	{
+ 	  int we_hide_them;
+ 	  int they_hide_us;
+ 	  tree *prev, other;
+ 	  
+ 	  if (!(virtual_depth || TREE_STATIC (level)))
+ 	    /* Neither is morally virtual, so cannot hide each other. */
+ 	    continue;
+ 	  
+ 	  if (!TREE_VALUE (level))
+ 	    /* They evaporated away already.  */
+ 	    continue;
+ 
+ 	  they_hide_us = (virtual_depth
+ 			  && original_binfo (binfo, TREE_PURPOSE (level)));
+ 	  we_hide_them = (!they_hide_us && TREE_STATIC (level)
+ 			  && original_binfo (TREE_PURPOSE (level), binfo));
+ 
+ 	  if (!(we_hide_them || they_hide_us))
+ 	    /* Neither is within the other, so no hiding can occur.  */
+ 	    continue;
+ 	  
+ 	  for (prev = &TREE_VALUE (level), other = *prev; other;)
+ 	    {
+ 	      if (same_type_p (to_type, TREE_TYPE (other)))
+ 		{
+ 		  if (they_hide_us)
+ 		    /* We are hidden. */
+ 		    return 0;
+ 
+ 		  if (we_hide_them)
+ 		    {
+ 		      /* We hide the other one.  */
+ 		      other = TREE_CHAIN (other);
+ 		      *prev = other;
+ 		      continue;
+ 		    }
+ 		}
+ 	      prev = &TREE_CHAIN (other);
+ 	      other = *prev;
+ 	    }
+ 	}
+     }
+   return 1;
+ }
+ 
+ /* Helper for lookup_conversions_r.  PARENT_CONVS is a list of lists
+    of conversion functions, the first slot will be for the current
+    binfo, if MY_CONVS is non-NULL.  CHILD_CONVS is the list of lists
+    of conversion functions from childen of the current binfo,
+    concatenated with conversions from elsewhere in the heirarchy --
+    that list begins with OTHER_CONVS.  Return a single list of lists
+    containing only conversions from the current binfo and its
+    children.  */
+ 
  static tree
! split_conversions (tree my_convs, tree parent_convs,
! 		   tree child_convs, tree other_convs)
  {
!   tree t;
!   tree prev;
!   
!   /* Remove the original other_convs portion from child_convs.  */
!   for (prev = NULL, t = child_convs;
!        t != other_convs; prev = t, t = TREE_CHAIN (t))
!     continue;
!   
!   if (prev)
!     TREE_CHAIN (prev) = NULL_TREE;
!   else
!     child_convs = NULL_TREE;
  
!   /* Attach the child convs to any we had at this level.  */
!   if (my_convs)
!     {
!       my_convs = parent_convs;
!       TREE_CHAIN (my_convs) = child_convs;
!     }
!   else
!     my_convs = child_convs;
!   
!   return my_convs;
! }
! 
! /* Worker for lookup_conversions.  Lookup conversion functions in
!    BINFO and its children.  VIRTUAL_DEPTH is non-zero, if BINFO is in
!    a morally virtual base, and VIRTUALNESS is non-zero, if we've
!    encountered virtual bases already in the tree walk.  PARENT_CONVS &
!    PARENT_TPL_CONVS are lists of list of conversions within parent
!    binfos.  OTHER_CONVS and OTHER_TPL_CONVS are conversions found
!    elsewhere in the tree.  Return the conversions found within this
!    portion of the graph in CONVS and TPL_CONVS.  Return non-zero is we
!    encountered virtualness.  We keep template and non-template
!    conversions separate, to avoid unnecessary type comparisons.
! 
!    The located conversion functions are held in lists of lists.  The
!    TREE_VALUE of the outer list is the list of conversion functions
!    found in a particular binfo.  The TREE_PURPOSE of both the outer
!    and inner lists is the binfo at which those conversions were
!    found.  TREE_STATIC is set for those lists within of morally
!    virtual binfos.  The TREE_VALUE of the inner list is the conversion
!    function or overload itself.  The TREE_TYPE of each inner list node
!    is the converted-to type.  */
! 
! static int
! lookup_conversions_r (tree binfo,
! 		      int virtual_depth, int virtualness,
! 		      tree parent_convs, tree parent_tpl_convs,
! 		      tree other_convs, tree other_tpl_convs,
! 		      tree *convs, tree *tpl_convs)
! {
!   int my_virtualness = 0;
!   tree my_convs = NULL_TREE;
!   tree my_tpl_convs = NULL_TREE;
!   tree child_convs = NULL_TREE;
!   tree child_tpl_convs = NULL_TREE;
!   unsigned i;
!   tree base_binfo;
!   VEC(tree) *method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
!   tree conv;
  
+   /* If we have no conversion operators, then don't look.  */
+   if (!TYPE_HAS_CONVERSION (BINFO_TYPE (binfo)))
+     {
+       *convs = *tpl_convs = NULL_TREE;
+       
+       return 0;
+     }
+   
+   if (BINFO_VIRTUAL_P (binfo))
+     virtual_depth++;
+   
+   /* First, locate the unhidden ones at this level.  */
    for (i = CLASSTYPE_FIRST_CONVERSION_SLOT; 
!        VEC_iterate (tree, method_vec, i, conv);
         ++i)
      {
!       tree cur = OVL_CURRENT (conv);
  
!       if (!DECL_CONV_FN_P (cur))
  	break;
  
!       if (TREE_CODE (cur) == TEMPLATE_DECL)
  	{
! 	  /* Only template conversions can be overloaded, and we must
! 	     flatten them out and check each one individually.  */
! 	  tree tpls;
  
! 	  for (tpls = conv; tpls; tpls = OVL_NEXT (tpls))
  	    {
! 	      tree tpl = OVL_CURRENT (tpls);
! 	      tree type = DECL_CONV_FN_TYPE (tpl);
! 	      
! 	      if (check_hidden_convs (binfo, virtual_depth, virtualness,
! 				      type, parent_tpl_convs, other_tpl_convs))
! 		{
! 		  my_tpl_convs = tree_cons (binfo, tpl, my_tpl_convs);
! 		  TREE_TYPE (my_tpl_convs) = type;
! 		  if (virtual_depth)
! 		    {
! 		      TREE_STATIC (my_tpl_convs) = 1;
! 		      my_virtualness = 1;
! 		    }
! 		}
  	    }
! 	}
!       else
! 	{
! 	  tree name = DECL_NAME (cur);
! 
! 	  if (!IDENTIFIER_MARKED (name))
  	    {
! 	      tree type = DECL_CONV_FN_TYPE (cur);
! 	      
! 	      if (check_hidden_convs (binfo, virtual_depth, virtualness,
! 				      type, parent_convs, other_convs))
! 		{
! 		  my_convs = tree_cons (binfo, conv, my_convs);
! 		  TREE_TYPE (my_convs) = type;
! 		  if (virtual_depth)
! 		    {
! 		      TREE_STATIC (my_convs) = 1;
! 		      my_virtualness = 1;
! 		    }
! 		  IDENTIFIER_MARKED (name) = 1;
! 		}
  	    }
  	}
      }
! 
!   if (my_convs)
!     {
!       parent_convs = tree_cons (binfo, my_convs, parent_convs);
!       if (virtual_depth)
! 	TREE_STATIC (parent_convs) = 1;
!     }
!   
!   if (my_tpl_convs)
!     {
!       parent_tpl_convs = tree_cons (binfo, my_tpl_convs, parent_tpl_convs);
!       if (virtual_depth)
! 	TREE_STATIC (parent_convs) = 1;
!     }
! 
!   child_convs = other_convs;
!   child_tpl_convs = other_tpl_convs;
!   
!   /* Now iterate over each base, looking for more conversions.  */
!   for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
!     {
!       tree base_convs, base_tpl_convs;
!       unsigned base_virtualness;
! 
!       base_virtualness = lookup_conversions_r (base_binfo,
! 					       virtual_depth, virtualness,
! 					       parent_convs, parent_tpl_convs,
! 					       child_convs, child_tpl_convs,
! 					       &base_convs, &base_tpl_convs);
!       if (base_virtualness)
! 	my_virtualness = virtualness = 1;
!       child_convs = chainon (base_convs, child_convs);
!       child_tpl_convs = chainon (base_tpl_convs, child_tpl_convs);
!     }
! 
!   /* Unmark the conversions found at this level  */
!   for (conv = my_convs; conv; conv = TREE_CHAIN (conv))
!     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (conv)))) = 0;
! 
!   *convs = split_conversions (my_convs, parent_convs,
! 			      child_convs, other_convs);
!   *tpl_convs = split_conversions (my_tpl_convs, parent_tpl_convs,
! 				  child_tpl_convs, other_tpl_convs);
!   
!   return my_virtualness;
  }
  
  /* Return a TREE_LIST containing all the non-hidden user-defined
     conversion functions for TYPE (and its base-classes).  The
!    TREE_VALUE of each node is the FUNCTION_DECL of the conversion
!    function.  The TREE_PURPOSE is the BINFO from which the conversion
!    functions in this node were selected.  This function is effectively
!    performing a set of member lookups as lookup_fnfield does, but
!    using the type being converted to as the unique key, rather than the
!    field name.  */
  
  tree
  lookup_conversions (tree type)
  {
!   tree convs, tpl_convs;
!   tree list = NULL_TREE;
!   
    complete_type (type);
!   if (!TYPE_BINFO (type))
!     return NULL_TREE;
!   
!   lookup_conversions_r (TYPE_BINFO (type), 0, 0,
! 			NULL_TREE, NULL_TREE, NULL_TREE, NULL_TREE,
! 			&convs, &tpl_convs);
!   
!   /* Flatten the list-of-lists */
!   for (; convs; convs = TREE_CHAIN (convs))
!     {
!       tree probe, next;
! 
!       for (probe = TREE_VALUE (convs); probe; probe = next)
! 	{
! 	  next = TREE_CHAIN (probe);
! 
! 	  TREE_CHAIN (probe) = list;
! 	  list = probe;
! 	}
!     }
!   
!   for (; tpl_convs; tpl_convs = TREE_CHAIN (tpl_convs))
!     {
!       tree probe, next;
  
!       for (probe = TREE_VALUE (tpl_convs); probe; probe = next)
! 	{
! 	  next = TREE_CHAIN (probe);
  
! 	  TREE_CHAIN (probe) = list;
! 	  list = probe;
! 	}
!     }
!   
!   return list;
  }
  
  struct overlap_info 

// { dg-do compile }

// Copyright (C) 2004 Free Software Foundation, Inc.
// Contributed by Nathan Sidwell 21 Jul 2004 <nathan@codesourcery.com>

// Failed to spot ambiguous conversion

struct A1 
{
  operator int () const; // { dg-error "A1::operator" "" }
};

struct A2
{
  operator int () const; // { dg-error "A2::operator" "" }
};

struct B : A1, A2 
{
};

int Foo (B const &b)
{
  return b; // { dg-error "ambiguous" "" }
}

// { dg-do compile }

// Copyright (C) 2004 Free Software Foundation, Inc.
// Contributed by Nathan Sidwell 21 Jul 2004 <nathan@codesourcery.com>

// { dg-final { scan-assembler "_ZNK2A1cviEv" } }

struct A1 
{
  operator int () const; // this one
};

struct A2 : A1
{
  template<typename T> operator T () const;
};

int Foo (A2 const &b)
{
  return b;
}

// { dg-do compile }

// Copyright (C) 2004 Free Software Foundation, Inc.
// Contributed by Nathan Sidwell 21 Jul 2004 <nathan@codesourcery.com>

// { dg-final { scan-assembler "_ZNK2A1IiEcviEv" } }

template <typename T> struct A1 
{
  operator T () const;  // this one
};

struct A2 : A1<int>
{
  template<typename T> operator T () const;
};

int Foo (A2 const &b)
{
  return b;
}

// { dg-do compile }

// Copyright (C) 2004 Free Software Foundation, Inc.
// Contributed by Nathan Sidwell 21 Jul 2004 <nathan@codesourcery.com>

// { dg-final { scan-assembler "_ZNK1AcviEv" } }
// { dg-final { scan-assembler-not "_ZNK1VcviEv" } }

struct V 
{
  operator int () const;
};

struct A : virtual V
{
  operator int () const; // this one
};

struct B1 : A, virtual V
{
};

struct B2 : virtual V, A
{
};


int Foo (B1 const &b)
{
  return b;
}
int Foo (B2 const &b)
{
  return b;
}