cp-search.c

早期freebsd实现

	      else if (TREE_VIA_VIRTUAL (binfo))
		errstr = "member `%s' belongs to virtual and non-virtual baseclasses `%s'";
	      else
		errstr = "member `%s' belongs to MI-distinct base classes `%s'";
	    }
	  else
	    {
	      int index = lookup_fnfields_1 (type, name);

	      /* ??? This code is broken.  If CONTEXT is not the leftmost
		 baseclass, it makes all of its baseclasses appear to be
		 unrelated.  */
	      if (index >= 0 && binfo != get_binfo (type, context, 0))
		{
		  /* We found it in other than a baseclass of RVAL's.  */
		  rvals = my_tree_cons (basetype_path, TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), index), rvals);
		  if (CLASSTYPE_BASELINK_VEC (type))
		    TREE_TYPE (rvals) = TREE_VEC_ELT (CLASSTYPE_BASELINK_VEC (type), index);
		}
	    }
	  if (errstr && entry)
	    {
	      tree error_string = my_build_string (errstr);
	      TREE_TYPE (entry) = error_string;
	    }
	  if (errstr && find_ambiguous)
	    {
	      rvals = error_mark_node;
	      break;
	    }
	}
      else
	{
	  int index = lookup_fnfields_1 (type, name);
	  if (index >= 0)
	    {
	      rval = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), index);
	      rvals = my_tree_cons (basetype_path, rval, NULL_TREE);
	      if (TYPE_BINFO_BASETYPES (type) && CLASSTYPE_BASELINK_VEC (type))
		TREE_TYPE (rvals) = TREE_VEC_ELT (CLASSTYPE_BASELINK_VEC (type), index);
	      if (entry)
		TREE_VALUE (entry) = rvals;
	    }
	  else
	    rval = NULL_TREE;
	}
    }
  {
    tree *tp = search_stack->first;
    tree *search_tail = tp + tail;

    while (tp < search_tail)
      {
	CLEAR_BINFO_FIELDS_MARKED (TREE_VALUE (*tp));
	tp += 1;
      }
  }
  search_stack = pop_search_level (search_stack);

  if (entry)
    {
      if (errstr)
	{
	  tree error_string = my_build_string (errstr);
	  /* Save error message with entry.  */
	  TREE_TYPE (entry) = error_string;
	}
      else
	{
	  /* Mark entry as having no error string.  */
	  TREE_TYPE (entry) = NULL_TREE;
	}
    }

  if (errstr && protect)
    {
      error (errstr, IDENTIFIER_POINTER (name), TYPE_NAME_STRING (type));
      rvals = error_mark_node;
    }

  return rvals;
}

/* BREADTH-FIRST SEARCH ROUTINES.  */

/* Search a multiple inheritance hierarchy by breadth-first search.

   TYPE is an aggregate type, possibly in a multiple-inheritance hierarchy.
   TESTFN is a function, which, if true, means that our condition has been met,
   and its return value should be returned.
   QFN, if non-NULL, is a predicate dictating whether the type should
   even be queued.  */

HOST_WIDE_INT
breadth_first_search (binfo, testfn, qfn)
     tree binfo;
     int (*testfn)();
     int (*qfn)();
{
  int head = 0, tail = 0;
  int rval = 0;

  search_stack = push_search_level (search_stack, &search_obstack);

  while (1)
    {
      tree binfos = BINFO_BASETYPES (binfo);
      int n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
      int i;

      /* Process and/or queue base types.  */
      for (i = 0; i < n_baselinks; i++)
	{
	  tree base_binfo = TREE_VEC_ELT (binfos, i);

	  if (BINFO_MARKED (base_binfo) == 0
	      && (qfn == 0 || (*qfn) (binfo, i)))
	    {
	      SET_BINFO_MARKED (base_binfo);
	      obstack_ptr_grow (&search_obstack, binfo);
	      obstack_int_grow (&search_obstack, i);
	      tail += 2;
	      if (tail >= search_stack->limit)
		my_friendly_abort (100);
	    }
	}
      /* Process head of queue, if one exists.  */
      if (head >= tail)
	{
	  rval = 0;
	  break;
	}

      binfo = search_stack->first[head++];
      i = (HOST_WIDE_INT)search_stack->first[head++];
      if (rval = (*testfn) (binfo, i))
	break;
      binfo = BINFO_BASETYPE (binfo, i);
    }
  {
    tree *tp = search_stack->first;
    tree *search_tail = tp + tail;
    while (tp < search_tail)
      {
	tree binfo = *tp++;
	int i = (HOST_WIDE_INT)(*tp++);
	CLEAR_BINFO_MARKED (BINFO_BASETYPE (binfo, i));
      }
  }

  search_stack = pop_search_level (search_stack);
  return rval;
}

/* Functions to use in breadth first searches.  */
typedef tree (*pft)();
typedef int (*pfi)();

int tree_needs_constructor_p (binfo, i)
     tree binfo;
     int i;
{
  tree basetype;
  my_friendly_assert (i != 0, 296);
  basetype = BINFO_TYPE (BINFO_BASETYPE (binfo, i));
  return TYPE_NEEDS_CONSTRUCTOR (basetype);
}

static tree declarator;

static tree
get_virtuals_named_this (binfo, i)
     tree binfo;
     int i;
{
  tree fields;
  tree type = BINFO_TYPE (binfo);

  if (i >= 0)
    type = BINFO_TYPE (TREE_VEC_ELT (BINFO_BASETYPES (binfo), i));
  fields = lookup_fnfields (binfo, declarator, 0);

  if (fields == 0 || fields == error_mark_node)
    return 0;

  /* Get to the function decls, and return the first virtual function
     with this name, if there is one.  */
  while (fields)
    {
      tree fndecl;

      for (fndecl = TREE_VALUE (fields); fndecl; fndecl = DECL_CHAIN (fndecl))
	if (DECL_VINDEX (fndecl))
	  return fields;
      fields = next_baselink (fields);
    }
  return NULL_TREE;
}

static tree get_virtual_destructor (binfo, i)
     tree binfo;
     int i;
{
  tree type = BINFO_TYPE (binfo);
  if (i >= 0)
    type = BINFO_TYPE (TREE_VEC_ELT (BINFO_BASETYPES (binfo), i));
  if (TYPE_HAS_DESTRUCTOR (type)
      && DECL_VINDEX (TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), 0)))
    return TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), 0);
  return 0;
}

int tree_has_any_destructor_p (binfo, i)
     tree binfo;
     int i;
{
  tree type = BINFO_TYPE (binfo);
  if (i >= 0)
    type = BINFO_TYPE (TREE_VEC_ELT (BINFO_BASETYPES (binfo), i));
  return TYPE_NEEDS_DESTRUCTOR (type);
}

/* Given a class type TYPE, and a function decl FNDECL,
   look for the first function the TYPE's hierarchy which
   FNDECL could match as a virtual function.

   DTORP is nonzero if we are looking for a destructor.  Destructors
   need special treatment because they do not match by name.  */
tree
get_first_matching_virtual (binfo, fndecl, dtorp)
     tree binfo, fndecl;
     int dtorp;
{
  tree tmp = NULL_TREE;

  /* Breadth first search routines start searching basetypes
     of TYPE, so we must perform first ply of search here.  */
  if (dtorp)
    {
      if (tree_has_any_destructor_p (binfo, -1))
	tmp = get_virtual_destructor (binfo, -1);

      if (tmp)
	{
	  if (get_base_distance (DECL_CONTEXT (tmp),
				 DECL_CONTEXT (fndecl), 0, 0) > 0)
	    DECL_CONTEXT (fndecl) = DECL_CONTEXT (tmp);
	  return tmp;
	}

      tmp = (tree) breadth_first_search (binfo,
					 (pfi) get_virtual_destructor,
					 tree_has_any_destructor_p);
      if (tmp)
	DECL_CONTEXT (fndecl) = DECL_CONTEXT (tmp);
      return tmp;
    }
  else
    {
      tree drettype, dtypes, btypes, instptr_type;
      tree basetype = DECL_CLASS_CONTEXT (fndecl);
      tree baselink, best = NULL_TREE;
      tree name = DECL_ASSEMBLER_NAME (fndecl);

      declarator = DECL_NAME (fndecl);
      if (IDENTIFIER_VIRTUAL_P (declarator) == 0)
	return 0;

      drettype = TREE_TYPE (TREE_TYPE (fndecl));
      dtypes = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
      if (DECL_STATIC_FUNCTION_P (fndecl))
	instptr_type = NULL_TREE;
      else
	instptr_type = TREE_TYPE (TREE_VALUE (dtypes));

      for (baselink = get_virtuals_named_this (binfo, -1);
	   baselink; baselink = next_baselink (baselink))
	{
	  for (tmp = TREE_VALUE (baselink); tmp; tmp = DECL_CHAIN (tmp))
	    {
	      if (! DECL_VINDEX (tmp))
		continue;

	      btypes = TYPE_ARG_TYPES (TREE_TYPE (tmp));
	      if (instptr_type == NULL_TREE)
		{
		  if (compparms (TREE_CHAIN (btypes), dtypes, 3))
		    /* Caller knows to give error in this case.  */
		    return tmp;
		  return NULL_TREE;
		}

	      if ((TYPE_READONLY (TREE_TYPE (TREE_VALUE (btypes)))
		   == TYPE_READONLY (instptr_type))
		  && compparms (TREE_CHAIN (btypes), TREE_CHAIN (dtypes), 3))
		{
		  if (IDENTIFIER_ERROR_LOCUS (name) == NULL_TREE
		      && ! comptypes (TREE_TYPE (TREE_TYPE (tmp)), drettype, 1))
		    {
		      error_with_decl (fndecl, "conflicting return type specified for virtual function `%s'");
		      SET_IDENTIFIER_ERROR_LOCUS (name, basetype);
		    }
		  break;
		}
	    }
	  if (tmp)
	    {
	      /* If this is ambiguous, we will warn about it later.  */
	      if (best)
		{
		  if (get_base_distance (DECL_CLASS_CONTEXT (best),
					 DECL_CLASS_CONTEXT (tmp), 0, 0) > 0)
		    best = tmp;
		}
	      else
		best = tmp;
	    }
	}
      if (IDENTIFIER_ERROR_LOCUS (name) == NULL_TREE
	  && best == NULL_TREE && warn_overloaded_virtual)
	{
	  error_with_decl (fndecl, "conflicting specification deriving virtual function `%s'");
	  SET_IDENTIFIER_ERROR_LOCUS (name, basetype);
	}
      if (best)
	{
	  DECL_CONTEXT (fndecl) = DECL_CONTEXT (best);
	}
      return best;
    }
}

/* Return the list of virtual functions which are abstract in type TYPE.
   This information is cached, and so must be built on a
   non-temporary obstack.  */
tree
get_abstract_virtuals (type)
     tree type;
{
  /* For each layer of base class (i.e., the first base class, and each
     virtual base class from that one), modify the virtual function table
     of the derived class to contain the new virtual function.
     A class has as many vfields as it has virtual base classes (total).  */
  tree vfields, vbases, base, tmp;
  tree vfield = CLASSTYPE_VFIELD (type);
  tree fcontext = vfield ? DECL_FCONTEXT (vfield) : NULL_TREE;
  tree abstract_virtuals = CLASSTYPE_ABSTRACT_VIRTUALS (type);

  for (vfields = CLASSTYPE_VFIELDS (type); vfields; vfields = TREE_CHAIN (vfields))
    {
      int normal;

      /* Find the right base class for this derived class, call it BASE.  */
      base = VF_BASETYPE_VALUE (vfields);
      if (base == type)
	continue;

      /* We call this case NORMAL iff this virtual function table
	 pointer field has its storage reserved in this class.
	 This is normally the case without virtual baseclasses
	 or off-center multiple baseclasses.  */
      normal = (base == fcontext
		&& (VF_BINFO_VALUE (vfields) == NULL_TREE
		    || ! TREE_VIA_VIRTUAL (VF_BINFO_VALUE (vfields))));

      if (normal)
	tmp = TREE_CHAIN (TYPE_BINFO_VIRTUALS (type));
      else
	{
	  /* n.b.: VF_BASETYPE_VALUE (vfields) is the first basetype
	     that provides the virtual function table, whereas
	     VF_DERIVED_VALUE (vfields) is an immediate base type of TYPE
	     that dominates VF_BASETYPE_VALUE (vfields).  The list of
	     vfields we want lies between these two values.  */
	  tree binfo = get_binfo (VF_NORMAL_VALUE (vfields), type, 0);
	  tmp = TREE_CHAIN (BINFO_VIRTUALS (binfo));
	}

      /* Get around dossier entry if there is one.  */
      if (flag_dossier)
	tmp = TREE_CHAIN (tmp);

      while (tmp)
	{
	  tree base_pfn = FNADDR_FROM_VTABLE_ENTRY (TREE_VALUE (tmp));
	  tree base_fndecl = TREE_OPERAND (base_pfn, 0);
	  if (DECL_ABSTRACT_VIRTUAL_P (base_fndecl))
	    abstract_virtuals = tree_cons (NULL_TREE, base_fndecl, abstract_virtuals);
	  tmp = TREE_CHAIN (tmp);
	}
    }
  for (vbases = CLASSTYPE_VBASECLASSES (type); vbases; vbases = TREE_CHAIN (vbases))
    {
      if (! BINFO_VIRTUALS (vbases))
	continue;

      tmp = TREE_CHAIN (BINFO_VIRTUALS (vbases));
      while (tmp)
	{
	  tree base_pfn = FNADDR_FROM_VTABLE_ENTRY (TREE_VALUE (tmp));
	  tree base_fndecl = TREE_OPERAND (base_pfn, 0);
	  if (DECL_ABSTRACT_VIRTUAL_P (base_fndecl))
	    abstract_virtuals = tree_cons (NULL_TREE, base_fndecl, abstract_virtuals);
	  tmp = TREE_CHAIN (tmp);
	}
    }
  return nreverse (abstract_virtuals);
}

/* For the type TYPE, return a list of member functions available from
   base classes with name NAME.  The TREE_VALUE of the list is a chain of
   member functions with name NAME.  The TREE_PURPOSE of the list is a
   basetype, or a list of base types (in reverse order) which were
   traversed to reach the chain of member functions.  If we reach a base
   type which provides a member function of name NAME, and which has at
   most one base type itself, then we can terminate the search.  */

tree
get_baselinks (type_as_binfo_list, type, name)
     tree type_as_binfo_list;
     tree type, name;
{
  tree hash_tree_cons ();
  int head = 0, tail = 0, index;
  tree rval = 0, nval = 0;
  tree basetypes = type_as_binfo_list;
  tree binfo = TYPE_BINFO (type);

  search_stack = push_search_level (search_stack, &search_obstack);

  while (1)
    {
      tree binfos = BINFO_BASETYPES (binfo);
      int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;

      /* Process and/or queue base types.  */
      for (i = 0; i < n_baselinks; i++)
	{
	  tree base_binfo = TREE_VEC_ELT (binfos, i);
	  tree btypes;

	  btypes = hash_tree_cons (TREE_VIA_PUBLIC (base_binfo),
				   TREE_VIA_VIRTUAL (base_binfo),
				   TREE_VIA_PROTECTED (base_binfo),
				   NULL_TREE, base_binfo,
				   basetypes);
	  obstack_ptr_grow (&search_obstack, btypes);
	  search_stack->first = (tree *)obstack_base (&search_obstack);
	  tail += 1;
	}

    dont_queue:
      /* Process head of queue, if one exists.