cp-search.c

早期freebsd实现

  tree friends;

#ifdef GATHER_STATISTICS
  n_calls_get_base_type++;
#endif

  if (TREE_CODE (parent) == TREE_VEC)
    parent = BINFO_TYPE (parent);
  /* unions cannot participate in inheritance relationships */
  else if (TREE_CODE (parent) == UNION_TYPE)
    return 0;
  else if (TREE_CODE (parent) != RECORD_TYPE)
    my_friendly_abort (89);

  parent = TYPE_MAIN_VARIANT (parent);
  search_stack = push_search_level (search_stack, &search_obstack);

  if (TREE_CODE (binfo) == TREE_VEC)
    type = BINFO_TYPE (binfo);
  else if (TREE_CODE (binfo) == RECORD_TYPE)
    {
      type = binfo;
      binfo = TYPE_BINFO (type);
    }
  else my_friendly_abort (90);
  xtype = type;
  friends = current_class_type ? CLASSTYPE_FRIEND_CLASSES (type) : NULL_TREE;

  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);

	  if (BINFO_MARKED (base_binfo) == 0)
	    {
	      int via_private = is_private || !TREE_VIA_PUBLIC (base_binfo);

	      SET_BINFO_MARKED (base_binfo);

	      if (via_private == 0)
		;
	      else if (protect == 0)
		via_private = 0;
	      else if (protect == 1 && BINFO_TYPE (binfo) == current_class_type)
		/* The immediate base class of the class we are in
		   does let its public members through.  */
		via_private = 0;
#ifndef NOJJG
	      else if (protect
		       && friends != NULL_TREE
		       && BINFO_TYPE (binfo) == xtype
		       && value_member (current_class_type, friends))
		/* Friend types of the most derived type have access
		   to its baseclass pointers.  */
		via_private = 0;
#endif

	      otype = type;
	      obstack_ptr_grow (&search_obstack, base_binfo);
	      obstack_int_grow (&search_obstack, via_private);
	      tail += 2;
	      if (tail >= search_stack->limit)
		my_friendly_abort (91);
	    }
#if 0
	  /* This code cannot possibly be right.  Ambiguities can only be
	     checked by traversing the whole tree, and seeing if it pops
	     up twice. */
	  else if (protect && ! TREE_VIA_VIRTUAL (base_binfo))
	    {
	      error_with_aggr_type (parent, "type `%s' is ambiguous base class for type `%s'",
				    TYPE_NAME_STRING (xtype));
	      error ("(base class for types `%s' and `%s')",
		     TYPE_NAME_STRING (BINFO_TYPE (binfo)),
		     TYPE_NAME_STRING (otype));
	      rval = error_mark_node;
	      goto cleanup;
	    }
#endif
	}

    dont_queue:
      /* Process head of queue, if one exists.  */
      if (head >= tail)
	break;

      binfo = search_stack->first[head++];
      is_private = (HOST_WIDE_INT)search_stack->first[head++];
      if (BINFO_TYPE (binfo) == parent)
	{
	  if (rval == 0)
	    {
	      rval = binfo;
	      rval_private = is_private;
	    }
	  else
	    /* I believe it is the case that this error is only an error when
	       used by someone that wants error messages printed.  Routines that
	       call this one, that don't set protect want the first one found,
	       even if there are more.  */
	    if (protect)
	      {
		/* Found two or more possible return values.  */
		error_with_aggr_type (parent, "type `%s' is ambiguous base class for type `%s'",
				      TYPE_NAME_STRING (xtype));
		rval = error_mark_node;
		goto cleanup;
	      }
	  goto dont_queue;
	}
    }

 cleanup:
  {
    tree *tp = search_stack->first;
    tree *search_tail = tp + tail;

    while (tp < search_tail)
      {
	CLEAR_BINFO_MARKED (*tp);
	tp += 2;
      }
  }
  search_stack = pop_search_level (search_stack);

  if (rval == error_mark_node)
    return error_mark_node;

  if (rval && protect && rval_private)
    {
      if (protect == 3)
	{
	  tree binfos = BINFO_BASETYPES (TYPE_BINFO (xtype));
	  int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;

	  for (i = 0; i < n_baselinks; i++)
	    {
	      tree base_binfo = TREE_VEC_ELT (binfos, i);
	      if (parent == BINFO_TYPE (base_binfo))
		/* It's ok, since it's immediate.  */
		return rval;
	    }
	}
      error_with_aggr_type (xtype, "type `%s' is derived from private `%s'",
			    TYPE_NAME_STRING (parent));
      return error_mark_node;
    }

  return rval;
}

/* -------------------------------------------------- */
/* These two routines are ONLY here to check for ambiguities for
   get_base_distance, as it probably cannot check by itself for
   all ambiguities.  When get_base_distance is sure to check for all,
   these routines can go.  (mrs) */

tree
get_binfo2_recursive (binfo, parent, type)
     register tree binfo, parent;
     tree type;
{
  tree rval = NULL_TREE;
  tree nrval;
  tree binfos = BINFO_BASETYPES (binfo);
  int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;

  if (BINFO_TYPE (binfo) == parent)
    {
      return binfo;
    }

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

      if (BINFO_MARKED (base_binfo) == 0)
	{
	  SET_BINFO_MARKED (base_binfo);

	  nrval = get_binfo2_recursive (base_binfo, parent, type);

	  if (nrval == error_mark_node)
	    return nrval;
	  if (nrval)
	    if (rval == 0)
	      {
		rval = nrval;
	      }
	    else
	      return error_mark_node;
	}
    }
  return rval;
}

tree
get_binfo2 (parent, binfo)
     register tree parent, binfo;
{
  tree type;
  tree rval = NULL_TREE;

  if (TREE_CODE (parent) == TREE_VEC)
    parent = BINFO_TYPE (parent);
  /* unions cannot participate in inheritance relationships */
  else if (TREE_CODE (parent) == UNION_TYPE)
    return 0;
  else if (TREE_CODE (parent) != RECORD_TYPE)
    my_friendly_abort (89);

  parent = TYPE_MAIN_VARIANT (parent);

  if (TREE_CODE (binfo) == TREE_VEC)
    type = BINFO_TYPE (binfo);
  else if (TREE_CODE (binfo) == RECORD_TYPE)
    {
      type = binfo;
      binfo = TYPE_BINFO (type);
    }
  else my_friendly_abort (90);

  rval = get_binfo2_recursive (binfo, parent, type);

  dfs_walk (binfo, dfs_unmark, markedp);

  return rval;
}

/* -------------------------------------------------- */

/* Return the number of levels between type PARENT and the type given
   in BINFO, following the leftmost path to PARENT.  If PARENT is its
   own main type variant, then if PARENT appears in different places
   from TYPE's point of view, the leftmost PARENT will be the one
   chosen.

   The term `leftmost' should be defined in g++int.texi and the
   significance should be explained.  If it is, this message should be
   deleted, if not, and you understand the term, please add
   documentation for it in g++int.texi.  Also, the part about the
   ``PARENT is its own main type variant'' should give reasons when
   and why this happens, and why it is important, and a better
   explaination of what this routine does both when that is true and
   when it is not.

   Return -1 if TYPE is not derived from PARENT.
   Return -2 if PARENT is an ambiguous base class of TYPE.
   Return -3 if PARENT is private to TYPE, and protect is non-zero.

   If PATH_PTR is non-NULL, then also build the list of types
   from PARENT to TYPE, with TREE_VIA_VIRUAL and TREE_VIA_PUBLIC
   set.

   It is unclear whether or not the path should be built if -2 and/or
   -3 is returned.  Maybe, maybe not.  I suspect that there is code
   that relies upon it being built, such as prepare_fresh_vtable.
   (mrs)

   Also, it would appear that we only sometimes want -2.  The question is
   under what exact conditions do we want to see -2, and when do we not
   want to see -2.  (mrs)

   It is also unlikely that this thing finds all ambiguties, as I
   don't trust any deviation from the method used in get_binfo.  It
   would be nice to use that method here, as it is simple and straight
   forward.  The code here and in recursive_bounded_basetype_p is not.
   For now, I shall include an extra call to find ambiguities.  (mrs)
   */

int
get_base_distance (parent, binfo, protect, path_ptr)
     register tree parent, binfo;
     int protect;
     tree *path_ptr;
{
  int head, tail;
  int is_private = 0;
  int rval = -1;
  int depth = 0;
  int rval_private = 0;
  tree type, basetype_path;
  tree friends;
  int use_leftmost;

  if (TYPE_READONLY (parent) || TYPE_VOLATILE (parent))
    parent = TYPE_MAIN_VARIANT (parent);
  use_leftmost = (parent == TYPE_MAIN_VARIANT (parent));

  if (TREE_CODE (binfo) == TREE_VEC)
    type = BINFO_TYPE (binfo);
  else if (TREE_CODE (binfo) == RECORD_TYPE)
    {
      type = binfo;
      binfo = TYPE_BINFO (type);
    }
  else my_friendly_abort (92);

  friends = current_class_type ? CLASSTYPE_FRIEND_CLASSES (type) : NULL_TREE;

  if (path_ptr)
    {
      basetype_path = TYPE_BINFO (type);
      BINFO_INHERITANCE_CHAIN (basetype_path) = NULL_TREE;
    }

  if (TYPE_MAIN_VARIANT (parent) == type)
    {
      /* If the distance is 0, then we don't really need
	 a path pointer, but we shouldn't let garbage go back.  */
      if (path_ptr)
	*path_ptr = basetype_path;
      return 0;
    }

  search_stack = push_search_level (search_stack, &search_obstack);

  /* Keep space for TYPE.  */
  obstack_ptr_grow (&search_obstack, binfo);
  obstack_int_grow (&search_obstack, 0);
  obstack_int_grow (&search_obstack, 0);
  if (path_ptr)
    {
      obstack_ptr_grow (&search_obstack, 0);
      head = 4;
    }
  else head = 3;
  tail = head;

  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);

	  if (BINFO_MARKED (base_binfo) == 0)
	    {
	      int via_private = is_private || !TREE_VIA_PUBLIC (base_binfo);

	      SET_BINFO_MARKED (base_binfo);

	      if (via_private == 0)
		;
	      else if (protect == 0)
		via_private = 0;

	      obstack_ptr_grow (&search_obstack, base_binfo);
	      obstack_int_grow (&search_obstack, depth);
	      obstack_int_grow (&search_obstack, via_private);
	      tail += 3;
	      if (path_ptr)
		{
		  obstack_ptr_grow (&search_obstack, basetype_path);
		  tail += 1;
		}
	      if (tail >= search_stack->limit)
		my_friendly_abort (93);
	    }
#if 0
	  /* This code cannot possibly be right.  Ambiguities can only be
	     checked by traversing the whole tree, and seeing if it pops
	     up twice. */
	  else if (! TREE_VIA_VIRTUAL (base_binfo))
	    {
	      rval = -2;
	      goto done;
	    }
#endif
	}

      /* Process head of queue, if one exists.  */
      if (head >= tail)
	break;

      binfo = search_stack->first[head++];
      depth = (HOST_WIDE_INT)search_stack->first[head++] + 1;
      is_private = (HOST_WIDE_INT)search_stack->first[head++];
      if (path_ptr)
	{
	  basetype_path = search_stack->first[head++];
	  BINFO_INHERITANCE_CHAIN (binfo) = basetype_path;
	  basetype_path = binfo;
	}
      if (BINFO_TYPE (binfo) == parent)
	{
	  /* It is wrong to set this and break, the proper thing to do
	     would be to set it only if it has not been set before,
	     and if is has been set, an ambiguity exists, and just
	     continue searching the tree for more of them as is done
	     in get_binfo.  But until the code below can cope, this
	     can't be done. Also, it is not clear what should happen if
	     use_leftmost is set.  */
	  rval = depth;
	  rval_private = is_private;
	  break;
	}
    }
#if 0
  /* Unneeded now, as we know the above code in the #if 0 is wrong.  */
 done:
#endif
  {
    int increment = path_ptr ? 4 : 3;
    tree *tp = search_stack->first;
    tree *search_tail = tp + tail;

    /* We can skip the first entry, since it wasn't marked.  */
    tp += increment;

    basetype_path = binfo;
    while (tp < search_tail)
      {
	CLEAR_BINFO_MARKED (*tp);
	tp += increment;
      }

    /* Now, guarantee that we are following the leftmost path in the
       chain.  Algorithm: the search stack holds tuples in BFS order.
       The last tuple on the search stack contains the tentative binfo
       for the basetype we are looking for.  We know that starting
       with FIRST, each tuple with only a single basetype must be on
       the leftmost path.  Each time we come to a split, we select
       the tuple for the leftmost basetype that can reach the ultimate
       basetype.  */

    if (use_leftmost
	&& rval > 0
	&& (! BINFO_OFFSET_ZEROP (binfo) || TREE_VIA_VIRTUAL (binfo)))
      {
	tree tp_binfos;

	/* Farm out the tuples with a single basetype.  */
	for (tp = search_stack->first; tp < search_tail; tp += increment)
	  {
	    tp_binfos = BINFO_BASETYPES (*tp);
	    if (tp_binfos && TREE_VEC_LENGTH (tp_binfos) > 1)
	      break;
	  }

	if (tp < search_tail)
	  {
	    /* Pick the best path.  */
	    tree base_binfo;
	    int i;
	    for (i = 0; i < TREE_VEC_LENGTH (tp_binfos); i++)
	      {
		base_binfo = TREE_VEC_ELT (tp_binfos, i);