search.c

gcc-2.95.3 Linux下最常用的C编译器

/* Breadth-first and depth-first routines for
   searching multiple-inheritance lattice for GNU C++.
   Copyright (C) 1987, 89, 92-97, 1998, 1999 Free Software Foundation, Inc.
   Contributed by Michael Tiemann ([e-mail])

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* High-level class interface.  */

#include "config.h"
#include "system.h"
#include "tree.h"
#include "cp-tree.h"
#include "obstack.h"
#include "flags.h"
#include "rtl.h"
#include "output.h"
#include "toplev.h"
#include "varray.h"

#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free

extern struct obstack *current_obstack;
extern tree abort_fndecl;

#include "stack.h"

/* Obstack used for remembering decision points of breadth-first.  */

static struct obstack search_obstack;

/* Methods for pushing and popping objects to and from obstacks.  */

struct stack_level *
push_stack_level (obstack, tp, size)
     struct obstack *obstack;
     char *tp;  /* Sony NewsOS 5.0 compiler doesn't like void * here.  */
     int size;
{
  struct stack_level *stack;
  obstack_grow (obstack, tp, size);
  stack = (struct stack_level *) ((char*)obstack_next_free (obstack) - size);
  obstack_finish (obstack);
  stack->obstack = obstack;
  stack->first = (tree *) obstack_base (obstack);
  stack->limit = obstack_room (obstack) / sizeof (tree *);
  return stack;
}

struct stack_level *
pop_stack_level (stack)
     struct stack_level *stack;
{
  struct stack_level *tem = stack;
  struct obstack *obstack = tem->obstack;
  stack = tem->prev;
  obstack_free (obstack, tem);
  return stack;
}

#define search_level stack_level
static struct search_level *search_stack;

static tree get_abstract_virtuals_1 PROTO((tree, int, tree));
static tree next_baselink PROTO((tree));
static tree get_vbase_1 PROTO((tree, tree, unsigned int *));
static tree convert_pointer_to_vbase PROTO((tree, tree));
static tree lookup_field_1 PROTO((tree, tree));
static tree convert_pointer_to_single_level PROTO((tree, tree));
static int lookup_fnfields_here PROTO((tree, tree));
static int is_subobject_of_p PROTO((tree, tree));
static int hides PROTO((tree, tree));
static tree virtual_context PROTO((tree, tree, tree));
static tree dfs_check_overlap PROTO((tree, void *));
static tree dfs_no_overlap_yet PROTO((tree, void *));
static int get_base_distance_recursive
	PROTO((tree, int, int, int, int *, tree *, tree,
	       int, int *, int, int));
static void expand_upcast_fixups 
	PROTO((tree, tree, tree, tree, tree, tree, tree *));
static void fixup_virtual_upcast_offsets
	PROTO((tree, tree, int, int, tree, tree, tree, tree,
	       tree *));
static tree unmarkedp PROTO((tree, void *));
static tree marked_vtable_pathp PROTO((tree, void *));
static tree unmarked_vtable_pathp PROTO((tree, void *));
static tree marked_new_vtablep PROTO((tree, void *));
static tree unmarked_new_vtablep PROTO((tree, void *));
static tree marked_pushdecls_p PROTO((tree, void *));
static tree unmarked_pushdecls_p PROTO((tree, void *));
static tree dfs_debug_unmarkedp PROTO((tree, void *));
static tree dfs_debug_mark PROTO((tree, void *));
static tree dfs_find_vbases PROTO((tree, void *));
static tree dfs_clear_vbase_slots PROTO((tree, void *));
static tree dfs_init_vbase_pointers PROTO((tree, void *));
static tree dfs_get_vbase_types PROTO((tree, void *));
static tree dfs_push_type_decls PROTO((tree, void *));
static tree dfs_push_decls PROTO((tree, void *));
static tree dfs_unuse_fields PROTO((tree, void *));
static tree add_conversions PROTO((tree, void *));
static tree get_virtuals_named_this PROTO((tree, tree));
static tree get_virtual_destructor PROTO((tree, void *));
static tree tree_has_any_destructor_p PROTO((tree, void *));
static int covariant_return_p PROTO((tree, tree));
static struct search_level *push_search_level
	PROTO((struct stack_level *, struct obstack *));
static struct search_level *pop_search_level
	PROTO((struct stack_level *));
static tree bfs_walk
	PROTO((tree, tree (*) (tree, void *), tree (*) (tree, void *),
	       void *));
static tree lookup_field_queue_p PROTO((tree, void *));
static tree lookup_field_r PROTO((tree, void *));
static tree dfs_walk_real PROTO ((tree, 
				  tree (*) (tree, void *),
				  tree (*) (tree, void *),
				  tree (*) (tree, void *),
				  void *));
static tree dfs_bfv_queue_p PROTO ((tree, void *));
static tree dfs_bfv_helper PROTO ((tree, void *));
static tree get_virtuals_named_this_r PROTO ((tree, void *));
static tree context_for_name_lookup PROTO ((tree));
static tree canonical_binfo PROTO ((tree));
static tree shared_marked_p PROTO ((tree, void *));
static tree shared_unmarked_p PROTO ((tree, void *));
static int  dependent_base_p PROTO ((tree));
static tree dfs_accessible_queue_p PROTO ((tree, void *));
static tree dfs_accessible_p PROTO ((tree, void *));
static tree dfs_access_in_type PROTO ((tree, void *));
static tree access_in_type PROTO ((tree, tree));
static tree dfs_canonical_queue PROTO ((tree, void *));
static tree dfs_assert_unmarked_p PROTO ((tree, void *));
static void assert_canonical_unmarked PROTO ((tree));
static int protected_accessible_p PROTO ((tree, tree, tree, tree));
static int friend_accessible_p PROTO ((tree, tree, tree, tree));
static void setup_class_bindings PROTO ((tree, int));
static int template_self_reference_p PROTO ((tree, tree));
static void expand_direct_vtbls_init_thunks PROTO((tree, tree, int));
static void expand_indirect_vtbls_init_thunks PROTO((tree, tree, tree));


/* Allocate a level of searching.  */

static struct search_level *
push_search_level (stack, obstack)
     struct stack_level *stack;
     struct obstack *obstack;
{
  struct search_level tem;

  tem.prev = stack;
  return push_stack_level (obstack, (char *)&tem, sizeof (tem));
}

/* Discard a level of search allocation.  */

static struct search_level *
pop_search_level (obstack)
     struct stack_level *obstack;
{
  register struct search_level *stack = pop_stack_level (obstack);

  return stack;
}

static tree _vptr_name;

/* Variables for gathering statistics.  */
#ifdef GATHER_STATISTICS
static int n_fields_searched;
static int n_calls_lookup_field, n_calls_lookup_field_1;
static int n_calls_lookup_fnfields, n_calls_lookup_fnfields_1;
static int n_calls_get_base_type;
static int n_outer_fields_searched;
static int n_contexts_saved;
#endif /* GATHER_STATISTICS */


/* Get a virtual binfo that is found inside BINFO's hierarchy that is
   the same type as the type given in PARENT.  To be optimal, we want
   the first one that is found by going through the least number of
   virtual bases.

   This uses a clever algorithm that updates *depth when we find the vbase,
   and cuts off other paths of search when they reach that depth.  */

static tree
get_vbase_1 (parent, binfo, depth)
     tree parent, binfo;
     unsigned int *depth;
{
  tree binfos;
  int i, n_baselinks;
  tree rval = NULL_TREE;

  if (BINFO_TYPE (binfo) == parent && TREE_VIA_VIRTUAL (binfo))
    {
      *depth = 0;
      return binfo;
    }

  *depth = *depth - 1;

  binfos = BINFO_BASETYPES (binfo);
  n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;

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

      if (*depth == 0)
	break;

      nrval = get_vbase_1 (parent, base_binfo, depth);
      if (nrval)
	rval = nrval;
    }
  *depth = *depth+1;
  return rval;
}

/* Return the shortest path to vbase PARENT within BINFO, ignoring
   access and ambiguity.  */

tree
get_vbase (parent, binfo)
     tree parent;
     tree binfo;
{
  unsigned int d = (unsigned int)-1;
  return get_vbase_1 (parent, binfo, &d);
}

/* Convert EXPR to a virtual base class of type TYPE.  We know that
   EXPR is a non-null POINTER_TYPE to RECORD_TYPE.  We also know that
   the type of what expr points to has a virtual base of type TYPE.  */

static tree
convert_pointer_to_vbase (type, expr)
     tree type;
     tree expr;
{
  tree vb = get_vbase (type, TYPE_BINFO (TREE_TYPE (TREE_TYPE (expr))));
  return convert_pointer_to_real (vb, expr);
}

/* Check whether the type given in BINFO is derived from PARENT.  If
   it isn't, return 0.  If it is, but the derivation is MI-ambiguous
   AND protect != 0, emit an error message and return error_mark_node.

   Otherwise, if TYPE is derived from PARENT, return the actual base
   information, unless a one of the protection violations below
   occurs, in which case emit an error message and return error_mark_node.

   If PROTECT is 1, then check if access to a public field of PARENT
   would be private.  Also check for ambiguity.  */

tree
get_binfo (parent, binfo, protect)
     register tree parent, binfo;
     int protect;
{
  tree type = NULL_TREE;
  int dist;
  tree rval = NULL_TREE;
  
  if (TREE_CODE (parent) == TREE_VEC)
    parent = BINFO_TYPE (parent);
  else if (! IS_AGGR_TYPE_CODE (TREE_CODE (parent)))
    my_friendly_abort (89);

  if (TREE_CODE (binfo) == TREE_VEC)
    type = BINFO_TYPE (binfo);
  else if (IS_AGGR_TYPE_CODE (TREE_CODE (binfo)))
    type = binfo;
  else
    my_friendly_abort (90);
  
  dist = get_base_distance (parent, binfo, protect, &rval);

  if (dist == -3)
    {
      cp_error ("fields of `%T' are inaccessible in `%T' due to private inheritance",
		parent, type);
      return error_mark_node;
    }
  else if (dist == -2 && protect)
    {
      cp_error ("type `%T' is ambiguous base class for type `%T'", parent,
		type);
      return error_mark_node;
    }

  return rval;
}

/* This is the newer depth first get_base_distance routine.  */

static int
get_base_distance_recursive (binfo, depth, is_private, rval,
			     rval_private_ptr, new_binfo_ptr, parent,
			     protect, via_virtual_ptr, via_virtual,
			     current_scope_in_chain)
     tree binfo;
     int depth, is_private, rval;
     int *rval_private_ptr;
     tree *new_binfo_ptr, parent;
     int protect, *via_virtual_ptr, via_virtual;
     int current_scope_in_chain;
{
  tree binfos;
  int i, n_baselinks;

  if (protect
      && !current_scope_in_chain
      && is_friend (BINFO_TYPE (binfo), current_scope ()))
    current_scope_in_chain = 1;

  if (BINFO_TYPE (binfo) == parent || binfo == parent)
    {
      int better = 0;

      if (rval == -1)
	/* This is the first time we've found parent.  */
	better = 1;
      else if (tree_int_cst_equal (BINFO_OFFSET (*new_binfo_ptr),
				   BINFO_OFFSET (binfo))
	       && *via_virtual_ptr && via_virtual)
	{
	  /* A new path to the same vbase.  If this one has better
	     access or is shorter, take it.  */

	  if (protect)
	    better = *rval_private_ptr - is_private;
	  if (better == 0)
	    better = rval - depth;
	}
      else
	{
	  /* Ambiguous base class.  */
	  rval = depth = -2;

	  /* If we get an ambiguity between virtual and non-virtual base
	     class, return the non-virtual in case we are ignoring
	     ambiguity.  */
	  better = *via_virtual_ptr - via_virtual;
	}

      if (better > 0)
	{
	  rval = depth;
	  *rval_private_ptr = is_private;
	  *new_binfo_ptr = binfo;
	  *via_virtual_ptr = via_virtual;
	}

      return rval;
    }

  binfos = BINFO_BASETYPES (binfo);
  n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
  depth += 1;

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

      int via_private
	= (protect
	   && (is_private
	       || (!TREE_VIA_PUBLIC (base_binfo)
		   && !(TREE_VIA_PROTECTED (base_binfo)
			&& current_scope_in_chain)
		   && !is_friend (BINFO_TYPE (binfo), current_scope ()))));
      int this_virtual = via_virtual || TREE_VIA_VIRTUAL (base_binfo);

      rval = get_base_distance_recursive (base_binfo, depth, via_private,
					  rval, rval_private_ptr,
					  new_binfo_ptr, parent,
					  protect, via_virtual_ptr,
					  this_virtual,
					  current_scope_in_chain);

      /* If we've found a non-virtual, ambiguous base class, we don't need
	 to keep searching.  */
      if (rval == -2 && *via_virtual_ptr == 0)
	return rval;
    }

  return rval;
}

/* Return the number of levels between type PARENT and the type given
   in BINFO, following the leftmost path to PARENT not found along a
   virtual path, if there are no real PARENTs (all come from virtual
   base classes), then follow the shortest public path to PARENT.

   Return -1 if TYPE is not derived from PARENT.
   Return -2 if PARENT is an ambiguous base class of TYPE, and PROTECT is
    non-negative.
   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_VIRTUAL and TREE_VIA_PUBLIC
   set.

   PARENT can also be a binfo, in which case that exact parent is found
   and no other.  convert_pointer_to_real uses this functionality.

   If BINFO is a binfo, its BINFO_INHERITANCE_CHAIN will be left alone.  */

int
get_base_distance (parent, binfo, protect, path_ptr)
     register tree parent, binfo;
     int protect;
     tree *path_ptr;
{
  int rval;
  int rval_private = 0;
  tree type = NULL_TREE;
  tree new_binfo = NULL_TREE;
  int via_virtual;
  int watch_access = protect;

  /* Should we be completing types here?  */
  if (TREE_CODE (parent) != TREE_VEC)
    parent = complete_type (TYPE_MAIN_VARIANT (parent));
  else
    complete_type (TREE_TYPE (parent));

  if (TREE_CODE (binfo) == TREE_VEC)