gcc/cp/search.c

   1 /* Breadth-first and depth-first routines for
   2    searching multiple-inheritance lattice for GNU C++.
   3    Copyright (C) 1987, 89, 92-97, 1998, 1999 Free Software Foundation, Inc.
   4    Contributed by Michael Tiemann (tiemann@cygnus.com)
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 /* High-level class interface.  */
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "tree.h"
  28 #include "cp-tree.h"
  29 #include "obstack.h"
  30 #include "flags.h"
  31 #include "rtl.h"
  32 #include "output.h"
  33 #include "toplev.h"
  34 #include "varray.h"
  35
  36 #define obstack_chunk_alloc xmalloc
  37 #define obstack_chunk_free free
  38
  39 extern struct obstack *current_obstack;
  40 extern tree abort_fndecl;
  41
  42 #include "stack.h"
  43
  44 /* Obstack used for remembering decision points of breadth-first.  */
  45
  46 static struct obstack search_obstack;
  47
  48 /* Methods for pushing and popping objects to and from obstacks.  */
  49
  50 struct stack_level *
  51 push_stack_level (obstack, tp, size)
  52      struct obstack *obstack;
  53      char *tp;  /* Sony NewsOS 5.0 compiler doesn't like void * here.  */
  54      int size;
  55 {
  56   struct stack_level *stack;
  57   obstack_grow (obstack, tp, size);
  58   stack = (struct stack_level *) ((char*)obstack_next_free (obstack) - size);
  59   obstack_finish (obstack);
  60   stack->obstack = obstack;
  61   stack->first = (tree *) obstack_base (obstack);
  62   stack->limit = obstack_room (obstack) / sizeof (tree *);
  63   return stack;
  64 }
  65
  66 struct stack_level *
  67 pop_stack_level (stack)
  68      struct stack_level *stack;
  69 {
  70   struct stack_level *tem = stack;
  71   struct obstack *obstack = tem->obstack;
  72   stack = tem->prev;
  73   obstack_free (obstack, tem);
  74   return stack;
  75 }
  76
  77 #define search_level stack_level
  78 static struct search_level *search_stack;
  79
  80 static tree get_abstract_virtuals_1 PROTO((tree, int, tree));
  81 static tree next_baselink PROTO((tree));
  82 static tree get_vbase_1 PROTO((tree, tree, unsigned int *));
  83 static tree convert_pointer_to_vbase PROTO((tree, tree));
  84 static tree lookup_field_1 PROTO((tree, tree));
  85 static tree convert_pointer_to_single_level PROTO((tree, tree));
  86 static int lookup_fnfields_here PROTO((tree, tree));
  87 static int is_subobject_of_p PROTO((tree, tree));
  88 static int hides PROTO((tree, tree));
  89 static tree virtual_context PROTO((tree, tree, tree));
  90 static tree dfs_check_overlap PROTO((tree, void *));
  91 static tree dfs_no_overlap_yet PROTO((tree, void *));
  92 static int get_base_distance_recursive
  93         PROTO((tree, int, int, int, int *, tree *, tree,
  94                int, int *, int, int));
  95 static void expand_upcast_fixups
  96         PROTO((tree, tree, tree, tree, tree, tree, tree *));
  97 static void fixup_virtual_upcast_offsets
  98         PROTO((tree, tree, int, int, tree, tree, tree, tree,
  99                tree *));
 100 static tree unmarkedp PROTO((tree, void *));
 101 static tree marked_vtable_pathp PROTO((tree, void *));
 102 static tree unmarked_vtable_pathp PROTO((tree, void *));
 103 static tree marked_new_vtablep PROTO((tree, void *));
 104 static tree unmarked_new_vtablep PROTO((tree, void *));
 105 static tree marked_pushdecls_p PROTO((tree, void *));
 106 static tree unmarked_pushdecls_p PROTO((tree, void *));
 107 static tree dfs_debug_unmarkedp PROTO((tree, void *));
 108 static tree dfs_debug_mark PROTO((tree, void *));
 109 static tree dfs_find_vbases PROTO((tree, void *));
 110 static tree dfs_clear_vbase_slots PROTO((tree, void *));
 111 static tree dfs_init_vbase_pointers PROTO((tree, void *));
 112 static tree dfs_get_vbase_types PROTO((tree, void *));
 113 static tree dfs_push_type_decls PROTO((tree, void *));
 114 static tree dfs_push_decls PROTO((tree, void *));
 115 static tree dfs_unuse_fields PROTO((tree, void *));
 116 static tree add_conversions PROTO((tree, void *));
 117 static tree get_virtuals_named_this PROTO((tree, tree));
 118 static tree get_virtual_destructor PROTO((tree, void *));
 119 static tree tree_has_any_destructor_p PROTO((tree, void *));
 120 static int covariant_return_p PROTO((tree, tree));
 121 static struct search_level *push_search_level
 122         PROTO((struct stack_level *, struct obstack *));
 123 static struct search_level *pop_search_level
 124         PROTO((struct stack_level *));
 125 static tree bfs_walk
 126         PROTO((tree, tree (*) (tree, void *), tree (*) (tree, void *),
 127                void *));
 128 static tree lookup_field_queue_p PROTO((tree, void *));
 129 static tree lookup_field_r PROTO((tree, void *));
 130 static tree dfs_walk_real PROTO ((tree,
 131                                   tree (*) (tree, void *),
 132                                   tree (*) (tree, void *),
 133                                   tree (*) (tree, void *),
 134                                   void *));
 135 static tree dfs_bfv_queue_p PROTO ((tree, void *));
 136 static tree dfs_bfv_helper PROTO ((tree, void *));
 137 static tree get_virtuals_named_this_r PROTO ((tree, void *));
 138 static tree context_for_name_lookup PROTO ((tree));
 139 static tree canonical_binfo PROTO ((tree));
 140 static tree shared_marked_p PROTO ((tree, void *));
 141 static tree shared_unmarked_p PROTO ((tree, void *));
 142 static int  dependent_base_p PROTO ((tree));
 143 static tree dfs_accessible_queue_p PROTO ((tree, void *));
 144 static tree dfs_accessible_p PROTO ((tree, void *));
 145 static tree dfs_access_in_type PROTO ((tree, void *));
 146 static tree access_in_type PROTO ((tree, tree));
 147 static tree dfs_canonical_queue PROTO ((tree, void *));
 148 static tree dfs_assert_unmarked_p PROTO ((tree, void *));
 149 static void assert_canonical_unmarked PROTO ((tree));
 150 static int protected_accessible_p PROTO ((tree, tree, tree, tree));
 151 static int friend_accessible_p PROTO ((tree, tree, tree, tree));
 152 static void setup_class_bindings PROTO ((tree, int));
 153 static int template_self_reference_p PROTO ((tree, tree));
 154
 155 /* Allocate a level of searching.  */
 156
 157 static struct search_level *
 158 push_search_level (stack, obstack)
 159      struct stack_level *stack;
 160      struct obstack *obstack;
 161 {
 162   struct search_level tem;
 163
 164   tem.prev = stack;
 165   return push_stack_level (obstack, (char *)&tem, sizeof (tem));
 166 }
 167
 168 /* Discard a level of search allocation.  */
 169
 170 static struct search_level *
 171 pop_search_level (obstack)
 172      struct stack_level *obstack;
 173 {
 174   register struct search_level *stack = pop_stack_level (obstack);
 175
 176   return stack;
 177 }
 178 \f
 179 static tree _vptr_name;
 180
 181 /* Variables for gathering statistics.  */
 182 #ifdef GATHER_STATISTICS
 183 static int n_fields_searched;
 184 static int n_calls_lookup_field, n_calls_lookup_field_1;
 185 static int n_calls_lookup_fnfields, n_calls_lookup_fnfields_1;
 186 static int n_calls_get_base_type;
 187 static int n_outer_fields_searched;
 188 static int n_contexts_saved;
 189 #endif /* GATHER_STATISTICS */
 190
 191 \f
 192 /* Get a virtual binfo that is found inside BINFO's hierarchy that is
 193    the same type as the type given in PARENT.  To be optimal, we want
 194    the first one that is found by going through the least number of
 195    virtual bases.
 196
 197    This uses a clever algorithm that updates *depth when we find the vbase,
 198    and cuts off other paths of search when they reach that depth.  */
 199
 200 static tree
 201 get_vbase_1 (parent, binfo, depth)
 202      tree parent, binfo;
 203      unsigned int *depth;
 204 {
 205   tree binfos;
 206   int i, n_baselinks;
 207   tree rval = NULL_TREE;
 208
 209   if (BINFO_TYPE (binfo) == parent && TREE_VIA_VIRTUAL (binfo))
 210     {
 211       *depth = 0;
 212       return binfo;
 213     }
 214
 215   *depth = *depth - 1;
 216
 217   binfos = BINFO_BASETYPES (binfo);
 218   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 219
 220   /* Process base types.  */
 221   for (i = 0; i < n_baselinks; i++)
 222     {
 223       tree base_binfo = TREE_VEC_ELT (binfos, i);
 224       tree nrval;
 225
 226       if (*depth == 0)
 227         break;
 228
 229       nrval = get_vbase_1 (parent, base_binfo, depth);
 230       if (nrval)
 231         rval = nrval;
 232     }
 233   *depth = *depth+1;
 234   return rval;
 235 }
 236
 237 /* Return the shortest path to vbase PARENT within BINFO, ignoring
 238    access and ambiguity.  */
 239
 240 tree
 241 get_vbase (parent, binfo)
 242      tree parent;
 243      tree binfo;
 244 {
 245   unsigned int d = (unsigned int)-1;
 246   return get_vbase_1 (parent, binfo, &d);
 247 }
 248
 249 /* Convert EXPR to a virtual base class of type TYPE.  We know that
 250    EXPR is a non-null POINTER_TYPE to RECORD_TYPE.  We also know that
 251    the type of what expr points to has a virtual base of type TYPE.  */
 252
 253 static tree
 254 convert_pointer_to_vbase (type, expr)
 255      tree type;
 256      tree expr;
 257 {
 258   tree vb = get_vbase (type, TYPE_BINFO (TREE_TYPE (TREE_TYPE (expr))));
 259   return convert_pointer_to_real (vb, expr);
 260 }
 261
 262 /* Check whether the type given in BINFO is derived from PARENT.  If
 263    it isn't, return 0.  If it is, but the derivation is MI-ambiguous
 264    AND protect != 0, emit an error message and return error_mark_node.
 265
 266    Otherwise, if TYPE is derived from PARENT, return the actual base
 267    information, unless a one of the protection violations below
 268    occurs, in which case emit an error message and return error_mark_node.
 269
 270    If PROTECT is 1, then check if access to a public field of PARENT
 271    would be private.  Also check for ambiguity.  */
 272
 273 tree
 274 get_binfo (parent, binfo, protect)
 275      register tree parent, binfo;
 276      int protect;
 277 {
 278   tree type = NULL_TREE;
 279   int dist;
 280   tree rval = NULL_TREE;
 281
 282   if (TREE_CODE (parent) == TREE_VEC)
 283     parent = BINFO_TYPE (parent);
 284   else if (! IS_AGGR_TYPE_CODE (TREE_CODE (parent)))
 285     my_friendly_abort (89);
 286
 287   if (TREE_CODE (binfo) == TREE_VEC)
 288     type = BINFO_TYPE (binfo);
 289   else if (IS_AGGR_TYPE_CODE (TREE_CODE (binfo)))
 290     type = binfo;
 291   else
 292     my_friendly_abort (90);
 293
 294   dist = get_base_distance (parent, binfo, protect, &rval);
 295
 296   if (dist == -3)
 297     {
 298       cp_error ("fields of `%T' are inaccessible in `%T' due to private inheritance",
 299                 parent, type);
 300       return error_mark_node;
 301     }
 302   else if (dist == -2 && protect)
 303     {
 304       cp_error ("type `%T' is ambiguous base class for type `%T'", parent,
 305                 type);
 306       return error_mark_node;
 307     }
 308
 309   return rval;
 310 }
 311
 312 /* This is the newer depth first get_base_distance routine.  */
 313
 314 static int
 315 get_base_distance_recursive (binfo, depth, is_private, rval,
 316                              rval_private_ptr, new_binfo_ptr, parent,
 317                              protect, via_virtual_ptr, via_virtual,
 318                              current_scope_in_chain)
 319      tree binfo;
 320      int depth, is_private, rval;
 321      int *rval_private_ptr;
 322      tree *new_binfo_ptr, parent;
 323      int protect, *via_virtual_ptr, via_virtual;
 324      int current_scope_in_chain;
 325 {
 326   tree binfos;
 327   int i, n_baselinks;
 328
 329   if (protect
 330       && !current_scope_in_chain
 331       && is_friend (BINFO_TYPE (binfo), current_scope ()))
 332     current_scope_in_chain = 1;
 333
 334   if (BINFO_TYPE (binfo) == parent || binfo == parent)
 335     {
 336       int better = 0;
 337
 338       if (rval == -1)
 339         /* This is the first time we've found parent.  */
 340         better = 1;
 341       else if (tree_int_cst_equal (BINFO_OFFSET (*new_binfo_ptr),
 342                                    BINFO_OFFSET (binfo))
 343                && *via_virtual_ptr && via_virtual)
 344         {
 345           /* A new path to the same vbase.  If this one has better
 346              access or is shorter, take it.  */
 347
 348           if (protect)
 349             better = *rval_private_ptr - is_private;
 350           if (better == 0)
 351             better = rval - depth;
 352         }
 353       else
 354         {
 355           /* Ambiguous base class.  */
 356           rval = depth = -2;
 357
 358           /* If we get an ambiguity between virtual and non-virtual base
 359              class, return the non-virtual in case we are ignoring
 360              ambiguity.  */
 361           better = *via_virtual_ptr - via_virtual;
 362         }
 363
 364       if (better > 0)
 365         {
 366           rval = depth;
 367           *rval_private_ptr = is_private;
 368           *new_binfo_ptr = binfo;
 369           *via_virtual_ptr = via_virtual;
 370         }
 371
 372       return rval;
 373     }
 374
 375   binfos = BINFO_BASETYPES (binfo);
 376   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 377   depth += 1;
 378
 379   /* Process base types.  */
 380   for (i = 0; i < n_baselinks; i++)
 381     {
 382       tree base_binfo = TREE_VEC_ELT (binfos, i);
 383
 384       int via_private
 385         = (protect
 386            && (is_private
 387                || (!TREE_VIA_PUBLIC (base_binfo)
 388                    && !(TREE_VIA_PROTECTED (base_binfo)
 389                         && current_scope_in_chain)
 390                    && !is_friend (BINFO_TYPE (binfo), current_scope ()))));
 391       int this_virtual = via_virtual || TREE_VIA_VIRTUAL (base_binfo);
 392
 393       rval = get_base_distance_recursive (base_binfo, depth, via_private,
 394                                           rval, rval_private_ptr,
 395                                           new_binfo_ptr, parent,
 396                                           protect, via_virtual_ptr,
 397                                           this_virtual,
 398                                           current_scope_in_chain);
 399
 400       /* If we've found a non-virtual, ambiguous base class, we don't need
 401          to keep searching.  */
 402       if (rval == -2 && *via_virtual_ptr == 0)
 403         return rval;
 404     }
 405
 406   return rval;
 407 }
 408
 409 /* Return the number of levels between type PARENT and the type given
 410    in BINFO, following the leftmost path to PARENT not found along a
 411    virtual path, if there are no real PARENTs (all come from virtual
 412    base classes), then follow the shortest public path to PARENT.
 413
 414    Return -1 if TYPE is not derived from PARENT.
 415    Return -2 if PARENT is an ambiguous base class of TYPE, and PROTECT is
 416     non-negative.
 417    Return -3 if PARENT is private to TYPE, and PROTECT is non-zero.
 418
 419    If PATH_PTR is non-NULL, then also build the list of types
 420    from PARENT to TYPE, with TREE_VIA_VIRTUAL and TREE_VIA_PUBLIC
 421    set.
 422
 423    PARENT can also be a binfo, in which case that exact parent is found
 424    and no other.  convert_pointer_to_real uses this functionality.
 425
 426    If BINFO is a binfo, its BINFO_INHERITANCE_CHAIN will be left alone.  */
 427
 428 int
 429 get_base_distance (parent, binfo, protect, path_ptr)
 430      register tree parent, binfo;
 431      int protect;
 432      tree *path_ptr;
 433 {
 434   int rval;
 435   int rval_private = 0;
 436   tree type = NULL_TREE;
 437   tree new_binfo = NULL_TREE;
 438   int via_virtual;
 439   int watch_access = protect;
 440
 441   /* Should we be completing types here?  */
 442   if (TREE_CODE (parent) != TREE_VEC)
 443     parent = complete_type (TYPE_MAIN_VARIANT (parent));
 444   else
 445     complete_type (TREE_TYPE (parent));
 446
 447   if (TREE_CODE (binfo) == TREE_VEC)
 448     type = BINFO_TYPE (binfo);
 449   else if (IS_AGGR_TYPE_CODE (TREE_CODE (binfo)))
 450     {
 451       type = complete_type (binfo);
 452       binfo = TYPE_BINFO (type);
 453
 454       if (path_ptr)
 455         my_friendly_assert (BINFO_INHERITANCE_CHAIN (binfo) == NULL_TREE,
 456                             980827);
 457     }
 458   else
 459     my_friendly_abort (92);
 460
 461   if (parent == type || parent == binfo)
 462     {
 463       /* If the distance is 0, then we don't really need
 464          a path pointer, but we shouldn't let garbage go back.  */
 465       if (path_ptr)
 466         *path_ptr = binfo;
 467       return 0;
 468     }
 469
 470   if (path_ptr)
 471     watch_access = 1;
 472
 473   rval = get_base_distance_recursive (binfo, 0, 0, -1,
 474                                       &rval_private, &new_binfo, parent,
 475                                       watch_access, &via_virtual, 0,
 476                                       0);
 477
 478   /* Access restrictions don't count if we found an ambiguous basetype.  */
 479   if (rval == -2 && protect >= 0)
 480     rval_private = 0;
 481
 482   if (rval && protect && rval_private)
 483     return -3;
 484
 485   /* If they gave us the real vbase binfo, which isn't in the main binfo
 486      tree, deal with it.  This happens when we are called from
 487      expand_upcast_fixups.  */
 488   if (rval == -1 && TREE_CODE (parent) == TREE_VEC
 489       && parent == binfo_member (BINFO_TYPE (parent),
 490                                  CLASSTYPE_VBASECLASSES (type)))
 491     {
 492       my_friendly_assert (BINFO_INHERITANCE_CHAIN (parent) == binfo, 980827);
 493       new_binfo = parent;
 494       rval = 1;
 495     }
 496
 497   if (path_ptr)
 498     *path_ptr = new_binfo;
 499   return rval;
 500 }
 501
 502 /* Search for a member with name NAME in a multiple inheritance lattice
 503    specified by TYPE.  If it does not exist, return NULL_TREE.
 504    If the member is ambiguously referenced, return `error_mark_node'.
 505    Otherwise, return the FIELD_DECL.  */
 506
 507 /* Do a 1-level search for NAME as a member of TYPE.  The caller must
 508    figure out whether it can access this field.  (Since it is only one
 509    level, this is reasonable.)  */
 510
 511 static tree
 512 lookup_field_1 (type, name)
 513      tree type, name;
 514 {
 515   register tree field;
 516
 517   if (TREE_CODE (type) == TEMPLATE_TYPE_PARM
 518       || TREE_CODE (type) == TEMPLATE_TEMPLATE_PARM)
 519     /* The TYPE_FIELDS of a TEMPLATE_TYPE_PARM are not fields at all;
 520        instead TYPE_FIELDS is the TEMPLATE_PARM_INDEX.  (Miraculously,
 521        the code often worked even when we treated the index as a list
 522        of fields!)  */
 523     return NULL_TREE;
 524
 525   field = TYPE_FIELDS (type);
 526
 527 #ifdef GATHER_STATISTICS
 528   n_calls_lookup_field_1++;
 529 #endif /* GATHER_STATISTICS */
 530   while (field)
 531     {
 532 #ifdef GATHER_STATISTICS
 533       n_fields_searched++;
 534 #endif /* GATHER_STATISTICS */
 535       my_friendly_assert (TREE_CODE_CLASS (TREE_CODE (field)) == 'd', 0);
 536       if (DECL_NAME (field) == NULL_TREE
 537           && TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
 538         {
 539           tree temp = lookup_field_1 (TREE_TYPE (field), name);
 540           if (temp)
 541             return temp;
 542         }
 543       if (TREE_CODE (field) == USING_DECL)
 544         /* For now, we're just treating member using declarations as
 545            old ARM-style access declarations.  Thus, there's no reason
 546            to return a USING_DECL, and the rest of the compiler can't
 547            handle it.  Once the class is defined, these are purged
 548            from TYPE_FIELDS anyhow; see handle_using_decl.  */
 549         ;
 550       else if (DECL_NAME (field) == name)
 551         {
 552           if ((TREE_CODE(field) == VAR_DECL || TREE_CODE(field) == CONST_DECL)
 553               && DECL_ASSEMBLER_NAME (field) != NULL)
 554             GNU_xref_ref(current_function_decl,
 555                          IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (field)));
 556           return field;
 557         }
 558       field = TREE_CHAIN (field);
 559     }
 560   /* Not found.  */
 561   if (name == _vptr_name)
 562     {
 563       /* Give the user what s/he thinks s/he wants.  */
 564       if (TYPE_VIRTUAL_P (type))
 565         return CLASSTYPE_VFIELD (type);
 566     }
 567   return NULL_TREE;
 568 }
 569
 570 /* There are a number of cases we need to be aware of here:
 571                          current_class_type     current_function_decl
 572      global                     NULL                    NULL
 573      fn-local                   NULL                    SET
 574      class-local                SET                     NULL
 575      class->fn                  SET                     SET
 576      fn->class                  SET                     SET
 577
 578    Those last two make life interesting.  If we're in a function which is
 579    itself inside a class, we need decls to go into the fn's decls (our
 580    second case below).  But if we're in a class and the class itself is
 581    inside a function, we need decls to go into the decls for the class.  To
 582    achieve this last goal, we must see if, when both current_class_ptr and
 583    current_function_decl are set, the class was declared inside that
 584    function.  If so, we know to put the decls into the class's scope.  */
 585
 586 tree
 587 current_scope ()
 588 {
 589   if (current_function_decl == NULL_TREE)
 590     return current_class_type;
 591   if (current_class_type == NULL_TREE)
 592     return current_function_decl;
 593   if (DECL_CLASS_CONTEXT (current_function_decl) == current_class_type)
 594     return current_function_decl;
 595
 596   return current_class_type;
 597 }
 598
 599 /* Return the scope of DECL, as appropriate when doing name-lookup.  */
 600
 601 static tree
 602 context_for_name_lookup (decl)
 603      tree decl;
 604 {
 605   /* [class.union]
 606
 607      For the purposes of name lookup, after the anonymous union
 608      definition, the members of the anonymous union are considered to
 609      have been defined in the scope in which teh anonymous union is
 610      declared.  */
 611   tree context = DECL_REAL_CONTEXT (decl);
 612
 613   while (TYPE_P (context) && ANON_UNION_TYPE_P (context))
 614     context = TYPE_CONTEXT (context);
 615   if (!context)
 616     context = global_namespace;
 617
 618   return context;
 619 }
 620
 621 /* Return a canonical BINFO if BINFO is a virtual base, or just BINFO
 622    otherwise.  */
 623
 624 static tree
 625 canonical_binfo (binfo)
 626      tree binfo;
 627 {
 628   return (TREE_VIA_VIRTUAL (binfo)
 629           ? TYPE_BINFO (BINFO_TYPE (binfo)) : binfo);
 630 }
 631
 632 /* A queue function that simply ensures that we walk into the
 633    canonical versions of virtual bases.  */
 634
 635 static tree
 636 dfs_canonical_queue (binfo, data)
 637      tree binfo;
 638      void *data ATTRIBUTE_UNUSED;
 639 {
 640   return canonical_binfo (binfo);
 641 }
 642
 643 /* Called via dfs_walk from assert_canonical_unmarked.  */
 644
 645 static tree
 646 dfs_assert_unmarked_p (binfo, data)
 647      tree binfo;
 648      void *data ATTRIBUTE_UNUSED;
 649 {
 650   my_friendly_assert (!BINFO_MARKED (binfo), 0);
 651   return NULL_TREE;
 652 }
 653
 654 /* Asserts that all the nodes below BINFO (using the canonical
 655    versions of virtual bases) are unmarked.  */
 656
 657 static void
 658 assert_canonical_unmarked (binfo)
 659      tree binfo;
 660 {
 661   dfs_walk (binfo, dfs_assert_unmarked_p, dfs_canonical_queue, 0);
 662 }
 663
 664 /* If BINFO is marked, return a canonical version of BINFO.
 665    Otherwise, return NULL_TREE.  */
 666
 667 static tree
 668 shared_marked_p (binfo, data)
 669      tree binfo;
 670      void *data;
 671 {
 672   binfo = canonical_binfo (binfo);
 673   return markedp (binfo, data) ? binfo : NULL_TREE;
 674 }
 675
 676 /* If BINFO is not marked, return a canonical version of BINFO.
 677    Otherwise, return NULL_TREE.  */
 678
 679 static tree
 680 shared_unmarked_p (binfo, data)
 681      tree binfo;
 682      void *data;
 683 {
 684   binfo = canonical_binfo (binfo);
 685   return unmarkedp (binfo, data) ? binfo : NULL_TREE;
 686 }
 687
 688 /* Called from access_in_type via dfs_walk.  Calculate the access to
 689    DATA (which is really a DECL) in BINFO.  */
 690
 691 static tree
 692 dfs_access_in_type (binfo, data)
 693      tree binfo;
 694      void *data;
 695 {
 696   tree decl = (tree) data;
 697   tree type = BINFO_TYPE (binfo);
 698   tree access = NULL_TREE;
 699
 700   if (context_for_name_lookup (decl) == type)
 701     {
 702       /* If we have desceneded to the scope of DECL, just note the
 703          appropriate access.  */
 704       if (TREE_PRIVATE (decl))
 705         access = access_private_node;
 706       else if (TREE_PROTECTED (decl))
 707         access = access_protected_node;
 708       else
 709         access = access_public_node;
 710     }
 711   else
 712     {
 713       /* First, check for an access-declaration that gives us more
 714          access to the DECL.  The CONST_DECL for an enumeration
 715          constant will not have DECL_LANG_SPECIFIC, and thus no
 716          DECL_ACCESS.  */
 717       if (DECL_LANG_SPECIFIC (decl))
 718         {
 719           access = purpose_member (type, DECL_ACCESS (decl));
 720           if (access)
 721             access = TREE_VALUE (access);
 722         }
 723
 724       if (!access)
 725         {
 726           int i;
 727           int n_baselinks;
 728           tree binfos;
 729
 730           /* Otherwise, scan our baseclasses, and pick the most favorable
 731              access.  */
 732           binfos = BINFO_BASETYPES (binfo);
 733           n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 734           for (i = 0; i < n_baselinks; ++i)
 735             {
 736               tree base_binfo = TREE_VEC_ELT (binfos, i);
 737               tree base_access = TREE_CHAIN (canonical_binfo (base_binfo));
 738
 739               if (!base_access || base_access == access_private_node)
 740                 /* If it was not accessible in the base, or only
 741                    accessible as a private member, we can't access it
 742                    all.  */
 743                 base_access = NULL_TREE;
 744               else if (TREE_VIA_PROTECTED (base_binfo))
 745                 /* Public and protected members in the base are
 746                    protected here.  */
 747                 base_access = access_protected_node;
 748               else if (!TREE_VIA_PUBLIC (base_binfo))
 749                 /* Public and protected members in the base are
 750                    private here.  */
 751                 base_access = access_private_node;
 752
 753               /* See if the new access, via this base, gives more
 754                  access than our previous best access.  */
 755               if (base_access &&
 756                   (base_access == access_public_node
 757                    || (base_access == access_protected_node
 758                        && access != access_public_node)
 759                    || (base_access == access_private_node
 760                        && !access)))
 761                 {
 762                   access = base_access;
 763
 764                   /* If the new access is public, we can't do better.  */
 765                   if (access == access_public_node)
 766                     break;
 767                 }
 768             }
 769         }
 770     }
 771
 772   /* Note the access to DECL in TYPE.  */
 773   TREE_CHAIN (binfo) = access;
 774
 775   /* Mark TYPE as visited so that if we reach it again we do not
 776      duplicate our efforts here.  */
 777   SET_BINFO_MARKED (binfo);
 778
 779   return NULL_TREE;
 780 }
 781
 782 /* Return the access to DECL in TYPE.  */
 783
 784 static tree
 785 access_in_type (type, decl)
 786      tree type;
 787      tree decl;
 788 {
 789   tree binfo = TYPE_BINFO (type);
 790
 791   /* We must take into account
 792
 793        [class.paths]
 794
 795        If a name can be reached by several paths through a multiple
 796        inheritance graph, the access is that of the path that gives
 797        most access.
 798
 799     The algorithm we use is to make a post-order depth-first traversal
 800     of the base-class hierarchy.  As we come up the tree, we annotate
 801     each node with the most lenient access.  */
 802   dfs_walk_real (binfo, 0, dfs_access_in_type, shared_unmarked_p, decl);
 803   dfs_walk (binfo, dfs_unmark, shared_marked_p,  0);
 804   assert_canonical_unmarked (binfo);
 805
 806   return TREE_CHAIN (binfo);
 807 }
 808
 809 /* Called from dfs_accessible_p via dfs_walk.  */
 810
 811 static tree
 812 dfs_accessible_queue_p (binfo, data)
 813      tree binfo;
 814      void *data ATTRIBUTE_UNUSED;
 815 {
 816   if (BINFO_MARKED (binfo))
 817     return NULL_TREE;
 818
 819   /* If this class is inherited via private or protected inheritance,
 820      then we can't see it, unless we are a friend of the subclass.  */
 821   if (!TREE_VIA_PUBLIC (binfo)
 822       && !is_friend (BINFO_TYPE (BINFO_INHERITANCE_CHAIN (binfo)),
 823                      current_scope ()))
 824     return NULL_TREE;
 825
 826   return canonical_binfo (binfo);
 827 }
 828
 829 /* Called from dfs_accessible_p via dfs_walk.  */
 830
 831 static tree
 832 dfs_accessible_p (binfo, data)
 833      tree binfo;
 834      void *data;
 835 {
 836   int protected_ok = data != 0;
 837   tree access;
 838
 839   /* We marked the binfos while computing the access in each type.
 840      So, we unmark as we go now.  */
 841   SET_BINFO_MARKED (binfo);
 842
 843   access = TREE_CHAIN (binfo);
 844   if (access == access_public_node
 845       || (access == access_protected_node && protected_ok))
 846     return binfo;
 847   else if (access && is_friend (BINFO_TYPE (binfo), current_scope ()))
 848     return binfo;
 849
 850   return NULL_TREE;
 851 }
 852
 853 /* Returns non-zero if it is OK to access DECL when named in TYPE
 854    through an object indiated by BINFO in the context of DERIVED.  */
 855
 856 static int
 857 protected_accessible_p (type, decl, derived, binfo)
 858      tree type;
 859      tree decl;
 860      tree derived;
 861      tree binfo;
 862 {
 863   tree access;
 864
 865   /* We're checking this clause from [class.access.base]
 866
 867        m as a member of N is protected, and the reference occurs in a
 868        member or friend of class N, or in a member or friend of a
 869        class P derived from N, where m as a member of P is private or
 870        protected.
 871
 872     If DERIVED isn't derived from TYPE, then it certainly does not
 873     apply.  */
 874   if (!DERIVED_FROM_P (type, derived))
 875     return 0;
 876
 877   access = access_in_type (derived, decl);
 878   if (same_type_p (derived, type))
 879     {
 880       if (access != access_private_node)
 881         return 0;
 882     }
 883   else if (access != access_private_node
 884            && access != access_protected_node)
 885     return 0;
 886
 887   /* [class.protected]
 888
 889      When a friend or a member function of a derived class references
 890      a protected nonstatic member of a base class, an access check
 891      applies in addition to those described earlier in clause
 892      _class.access_.4) Except when forming a pointer to member
 893      (_expr.unary.op_), the access must be through a pointer to,
 894      reference to, or object of the derived class itself (or any class
 895      derived from that class) (_expr.ref_).  If the access is to form
 896      a pointer to member, the nested-name-specifier shall name the
 897      derived class (or any class derived from that class).  */
 898   if (DECL_NONSTATIC_MEMBER_P (decl))
 899     {
 900       /* We can tell through what the reference is occurring by
 901          chasing BINFO up to the root.  */
 902       tree t = binfo;
 903       while (BINFO_INHERITANCE_CHAIN (t))
 904         t = BINFO_INHERITANCE_CHAIN (t);
 905
 906       if (!DERIVED_FROM_P (derived, BINFO_TYPE (t)))
 907         return 0;
 908     }
 909
 910   return 1;
 911 }
 912
 913 /* Returns non-zero if SCOPE is a friend of a type which would be able
 914    to acces DECL, named in TYPE, through the object indicated by
 915    BINFO.  */
 916
 917 static int
 918 friend_accessible_p (scope, type, decl, binfo)
 919      tree scope;
 920      tree type;
 921      tree decl;
 922      tree binfo;
 923 {
 924   tree befriending_classes;
 925   tree t;
 926
 927   if (!scope)
 928     return 0;
 929
 930   if (TREE_CODE (scope) == FUNCTION_DECL
 931       || DECL_FUNCTION_TEMPLATE_P (scope))
 932     befriending_classes = DECL_BEFRIENDING_CLASSES (scope);
 933   else if (TYPE_P (scope))
 934     befriending_classes = CLASSTYPE_BEFRIENDING_CLASSES (scope);
 935   else
 936     return 0;
 937
 938   for (t = befriending_classes; t; t = TREE_CHAIN (t))
 939     if (protected_accessible_p (type, decl, TREE_VALUE (t), binfo))
 940       return 1;
 941
 942   if (TREE_CODE (scope) == FUNCTION_DECL
 943       || DECL_FUNCTION_TEMPLATE_P (scope))
 944     {
 945       /* Perhaps this SCOPE is a member of a class which is a
 946          friend.  */
 947       if (friend_accessible_p (DECL_CLASS_CONTEXT (scope), type,
 948                                decl, binfo))
 949         return 1;
 950
 951       /* Or an instantiation of something which is a friend.  */
 952       if (DECL_TEMPLATE_INFO (scope))
 953         return friend_accessible_p (DECL_TI_TEMPLATE (scope),
 954                                     type, decl, binfo);
 955     }
 956   else if (CLASSTYPE_TEMPLATE_INFO (scope))
 957     return friend_accessible_p (CLASSTYPE_TI_TEMPLATE (scope),
 958                                 type, decl, binfo);
 959
 960   return 0;
 961 }
 962
 963 /* DECL is a declaration from a base class of TYPE, which was the
 964    classs used to name DECL.  Return non-zero if, in the current
 965    context, DECL is accessible.  If TYPE is actually a BINFO node,
 966    then we can tell in what context the access is occurring by looking
 967    at the most derived class along the path indicated by BINFO.  */
 968
 969 int
 970 accessible_p (type, decl)
 971      tree type;
 972      tree decl;
 973
 974 {
 975   tree binfo;
 976   tree t;
 977
 978   /* Non-zero if it's OK to access DECL if it has protected
 979      accessibility in TYPE.  */
 980   int protected_ok = 0;
 981
 982   /* If we're not checking access, everything is accessible.  */
 983   if (!flag_access_control)
 984     return 1;
 985
 986   /* If this declaration is in a block or namespace scope, there's no
 987      access control.  */
 988   if (!TYPE_P (context_for_name_lookup (decl)))
 989     return 1;
 990
 991   /* We don't do access control for types yet.  */
 992   if (TREE_CODE (decl) == TYPE_DECL)
 993     return 1;
 994
 995   if (!TYPE_P (type))
 996     {
 997       binfo = type;
 998       type = BINFO_TYPE (type);
 999     }
1000   else
1001     binfo = TYPE_BINFO (type);
1002
1003   /* [class.access.base]
1004
1005      A member m is accessible when named in class N if
1006
1007      --m as a member of N is public, or
1008
1009      --m as a member of N is private, and the reference occurs in a
1010        member or friend of class N, or
1011
1012      --m as a member of N is protected, and the reference occurs in a
1013        member or friend of class N, or in a member or friend of a
1014        class P derived from N, where m as a member of P is private or
1015        protected, or
1016
1017      --there exists a base class B of N that is accessible at the point
1018        of reference, and m is accessible when named in class B.
1019
1020     We walk the base class hierarchy, checking these conditions.  */
1021
1022   /* Figure out where the reference is occurring.  Check to see if
1023      DECL is private or protected in this scope, since that will
1024      determine whether protected access in TYPE allowed.  */
1025   if (current_class_type)
1026     protected_ok
1027       = protected_accessible_p (type, decl, current_class_type,
1028                                 binfo);
1029
1030   /* Now, loop through the classes of which we are a friend.  */
1031   if (!protected_ok)
1032     protected_ok = friend_accessible_p (current_scope (),
1033                                         type, decl, binfo);
1034
1035   /* Standardize on the same that will access_in_type will use.  We
1036      don't need to know what path was chosen from this point onwards.  */
1037   binfo = TYPE_BINFO (type);
1038
1039   /* Compute the accessibility of DECL in the class hierarchy
1040      dominated by type.  */
1041   access_in_type (type, decl);
1042   /* Walk the hierarchy again, looking for a base class that allows
1043      access.  */
1044   t = dfs_walk (binfo, dfs_accessible_p,
1045                 dfs_accessible_queue_p,
1046                 protected_ok ? &protected_ok : 0);
1047   /* Clear any mark bits.  Note that we have to walk the whole tree
1048      here, since we have aborted the previous walk from some point
1049      deep in the tree.  */
1050   dfs_walk (binfo, dfs_unmark, dfs_canonical_queue,  0);
1051   assert_canonical_unmarked (binfo);
1052
1053   return t != NULL_TREE;
1054 }
1055
1056 /* Routine to see if the sub-object denoted by the binfo PARENT can be
1057    found as a base class and sub-object of the object denoted by
1058    BINFO.  This routine relies upon binfos not being shared, except
1059    for binfos for virtual bases.  */
1060
1061 static int
1062 is_subobject_of_p (parent, binfo)
1063      tree parent, binfo;
1064 {
1065   tree binfos = BINFO_BASETYPES (binfo);
1066   int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
1067
1068   if (TREE_VIA_VIRTUAL (parent))
1069     parent = TYPE_BINFO (TREE_TYPE (parent));
1070   if (TREE_VIA_VIRTUAL (binfo))
1071     binfo = TYPE_BINFO (TREE_TYPE (binfo));
1072
1073   if (parent == binfo)
1074     return 1;
1075
1076   /* Process and/or queue base types.  */
1077   for (i = 0; i < n_baselinks; i++)
1078     {
1079       tree base_binfo = canonical_binfo (TREE_VEC_ELT (binfos, i));
1080       if (is_subobject_of_p (parent, base_binfo))
1081         return 1;
1082     }
1083   return 0;
1084 }
1085
1086 /* See if a one FIELD_DECL hides another.  This routine is meant to
1087    correspond to ANSI working paper Sept 17, 1992 10p4.  The two
1088    binfos given are the binfos corresponding to the particular places
1089    the FIELD_DECLs are found.  This routine relies upon binfos not
1090    being shared, except for virtual bases.  */
1091
1092 static int
1093 hides (hider_binfo, hidee_binfo)
1094      tree hider_binfo, hidee_binfo;
1095 {
1096   /* hider hides hidee, if hider has hidee as a base class and
1097      the instance of hidee is a sub-object of hider.  The first
1098      part is always true is the second part is true.
1099
1100      When hider and hidee are the same (two ways to get to the exact
1101      same member) we consider either one as hiding the other.  */
1102   return is_subobject_of_p (hidee_binfo, hider_binfo);
1103 }
1104
1105 /* Very similar to lookup_fnfields_1 but it ensures that at least one
1106    function was declared inside the class given by TYPE.  It really should
1107    only return functions that match the given TYPE.  */
1108
1109 static int
1110 lookup_fnfields_here (type, name)
1111      tree type, name;
1112 {
1113   int idx = lookup_fnfields_1 (type, name);
1114   tree fndecls;
1115
1116   /* ctors and dtors are always only in the right class.  */
1117   if (idx <= 1)
1118     return idx;
1119   fndecls = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), idx);
1120   while (fndecls)
1121     {
1122       if (TYPE_MAIN_VARIANT (DECL_CLASS_CONTEXT (OVL_CURRENT (fndecls)))
1123           == TYPE_MAIN_VARIANT (type))
1124         return idx;
1125       fndecls = OVL_CHAIN (fndecls);
1126     }
1127   return -1;
1128 }
1129
1130 struct lookup_field_info {
1131   /* The type in which we're looking.  */
1132   tree type;
1133   /* The name of the field for which we're looking.  */
1134   tree name;
1135   /* If non-NULL, the current result of the lookup.  */
1136   tree rval;
1137   /* The path to RVAL.  */
1138   tree rval_binfo;
1139   /* If non-NULL, the lookup was ambiguous, and this is a list of the
1140      candidates.  */
1141   tree ambiguous;
1142   /* If non-zero, we are looking for types, not data members.  */
1143   int want_type;
1144   /* If non-zero, RVAL was found by looking through a dependent base.  */
1145   int from_dep_base_p;
1146   /* If something went wrong, a message indicating what.  */
1147   const char *errstr;
1148 };
1149
1150 /* Returns non-zero if BINFO is not hidden by the value found by the
1151    lookup so far.  If BINFO is hidden, then there's no need to look in
1152    it.  DATA is really a struct lookup_field_info.  Called from
1153    lookup_field via breadth_first_search.  */
1154
1155 static tree
1156 lookup_field_queue_p (binfo, data)
1157      tree binfo;
1158      void *data;
1159 {
1160   struct lookup_field_info *lfi = (struct lookup_field_info *) data;
1161
1162   /* Don't look for constructors or destructors in base classes.  */
1163   if (lfi->name == ctor_identifier || lfi->name == dtor_identifier)
1164     return NULL_TREE;
1165
1166   /* If this base class is hidden by the best-known value so far, we
1167      don't need to look.  */
1168   if (!lfi->from_dep_base_p && lfi->rval_binfo
1169       && hides (lfi->rval_binfo, binfo))
1170     return NULL_TREE;
1171
1172   if (TREE_VIA_VIRTUAL (binfo))
1173     return binfo_member (BINFO_TYPE (binfo),
1174                          CLASSTYPE_VBASECLASSES (lfi->type));
1175   else
1176     return binfo;
1177 }
1178
1179 /* Within the scope of a template class, you can refer to the
1180    particular to the current specialization with the name of the
1181    template itself.  For example:
1182
1183      template <typename T> struct S { S* sp; }
1184
1185    Returns non-zero if DECL is such a declaration in a class TYPE.  */
1186
1187 static int
1188 template_self_reference_p (type, decl)
1189      tree type;
1190      tree decl;
1191 {
1192   return  (CLASSTYPE_USE_TEMPLATE (type)
1193            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (type))
1194            && TREE_CODE (decl) == TYPE_DECL
1195            && DECL_ARTIFICIAL (decl)
1196            && DECL_NAME (decl) == constructor_name (type));
1197 }
1198
1199 /* DATA is really a struct lookup_field_info.  Look for a field with
1200    the name indicated there in BINFO.  If this function returns a
1201    non-NULL value it is the result of the lookup.  Called from
1202    lookup_field via breadth_first_search.  */
1203
1204 static tree
1205 lookup_field_r (binfo, data)
1206      tree binfo;
1207      void *data;
1208 {
1209   struct lookup_field_info *lfi = (struct lookup_field_info *) data;
1210   tree type = BINFO_TYPE (binfo);
1211   tree nval = NULL_TREE;
1212   int from_dep_base_p;
1213
1214   /* First, look for a function.  There can't be a function and a data
1215      member with the same name, and if there's a function and a type
1216      with the same name, the type is hidden by the function.  */
1217   if (!lfi->want_type)
1218     {
1219       int idx = lookup_fnfields_here (type, lfi->name);
1220       if (idx >= 0)
1221         nval = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), idx);
1222     }
1223
1224   if (!nval)
1225     /* Look for a data member or type.  */
1226     nval = lookup_field_1 (type, lfi->name);
1227
1228   /* If there is no declaration with the indicated name in this type,
1229      then there's nothing to do.  */
1230   if (!nval)
1231     return NULL_TREE;
1232
1233   /* If we're looking up a type (as with an elaborated type specifier)
1234      we ignore all non-types we find.  */
1235   if (lfi->want_type && TREE_CODE (nval) != TYPE_DECL)
1236     {
1237       nval = purpose_member (lfi->name, CLASSTYPE_TAGS (type));
1238       if (nval)
1239         nval = TYPE_MAIN_DECL (TREE_VALUE (nval));
1240       else
1241         return NULL_TREE;
1242     }
1243
1244   /* You must name a template base class with a template-id.  */
1245   if (!same_type_p (type, lfi->type)
1246       && template_self_reference_p (type, nval))
1247     return NULL_TREE;
1248
1249   from_dep_base_p = dependent_base_p (binfo);
1250   if (lfi->from_dep_base_p && !from_dep_base_p)
1251     {
1252       /* If the new declaration is not found via a dependent base, and
1253          the old one was, then we must prefer the new one.  We weren't
1254          really supposed to be able to find the old one, so we don't
1255          want to be affected by a specialization.  Consider:
1256
1257            struct B { typedef int I; };
1258            template <typename T> struct D1 : virtual public B {};
1259            template <typename T> struct D :
1260            public D1, virtual pubic B { I i; };
1261
1262          The `I' in `D<T>' is unambigousuly `B::I', regardless of how
1263          D1 is specialized.  */
1264       lfi->from_dep_base_p = 0;
1265       lfi->rval = NULL_TREE;
1266       lfi->rval_binfo = NULL_TREE;
1267       lfi->ambiguous = NULL_TREE;
1268       lfi->errstr = 0;
1269     }
1270   else if (lfi->rval_binfo && !lfi->from_dep_base_p && from_dep_base_p)
1271     /* Similarly, if the old declaration was not found via a dependent
1272        base, and the new one is, ignore the new one.  */
1273     return NULL_TREE;
1274
1275   /* If the lookup already found a match, and the new value doesn't
1276      hide the old one, we might have an ambiguity.  */
1277   if (lfi->rval_binfo && !hides (binfo, lfi->rval_binfo))
1278     {
1279       if (nval == lfi->rval && SHARED_MEMBER_P (nval))
1280         /* The two things are really the same.  */
1281         ;
1282       else if (hides (lfi->rval_binfo, binfo))
1283         /* The previous value hides the new one.  */
1284         ;
1285       else
1286         {
1287           /* We have a real ambiguity.  We keep a chain of all the
1288              candidates.  */
1289           if (!lfi->ambiguous && lfi->rval)
1290             /* This is the first time we noticed an ambiguity.  Add
1291                what we previously thought was a reasonable candidate
1292                to the list.  */
1293             lfi->ambiguous = scratch_tree_cons (NULL_TREE, lfi->rval,
1294                                                 NULL_TREE);
1295           /* Add the new value.  */
1296           lfi->ambiguous = scratch_tree_cons (NULL_TREE, nval,
1297                                               lfi->ambiguous);
1298           lfi->errstr = "request for member `%D' is ambiguous";
1299         }
1300     }
1301   else
1302     {
1303       /* If the thing we're looking for is a virtual base class, then
1304          we know we've got what we want at this point; there's no way
1305          to get an ambiguity.  */
1306       if (VBASE_NAME_P (lfi->name))
1307         {
1308           lfi->rval = nval;
1309           return nval;
1310         }
1311
1312       if (from_dep_base_p && TREE_CODE (nval) != TYPE_DECL
1313           /* We need to return a member template class so we can
1314              define partial specializations.  Is there a better
1315              way?  */
1316           && !DECL_CLASS_TEMPLATE_P (nval))
1317         /* The thing we're looking for isn't a type, so the implicit
1318            typename extension doesn't apply, so we just pretend we
1319            didn't find anything.  */
1320         return NULL_TREE;
1321
1322       lfi->rval = nval;
1323       lfi->from_dep_base_p = from_dep_base_p;
1324       lfi->rval_binfo = binfo;
1325     }
1326
1327   return NULL_TREE;
1328 }
1329
1330 /* Look for a memer named NAME in an inheritance lattice dominated by
1331    XBASETYPE.  PROTECT is 0 or two, we do not check access.  If it is
1332    1, we enforce accessibility.  If PROTECT is zero, then, for an
1333    ambiguous lookup, we return NULL.  If PROTECT is 1, we issue an
1334    error message.  If PROTECT is two 2, we return a TREE_LIST whose
1335    TREE_PURPOSE is error_mark_node and whose TREE_VALUE is the list of
1336    ambiguous candidates.
1337
1338    WANT_TYPE is 1 when we should only return TYPE_DECLs, if no
1339    TYPE_DECL can be found return NULL_TREE.  */
1340
1341 tree
1342 lookup_member (xbasetype, name, protect, want_type)
1343      register tree xbasetype, name;
1344      int protect, want_type;
1345 {
1346   tree rval, rval_binfo = NULL_TREE;
1347   tree type = NULL_TREE, basetype_path = NULL_TREE;
1348   struct lookup_field_info lfi;
1349
1350   /* rval_binfo is the binfo associated with the found member, note,
1351      this can be set with useful information, even when rval is not
1352      set, because it must deal with ALL members, not just non-function
1353      members.  It is used for ambiguity checking and the hidden
1354      checks.  Whereas rval is only set if a proper (not hidden)
1355      non-function member is found.  */
1356
1357   const char *errstr = 0;
1358
1359   if (xbasetype == current_class_type && TYPE_BEING_DEFINED (xbasetype)
1360       && IDENTIFIER_CLASS_VALUE (name))
1361     {
1362       tree field = IDENTIFIER_CLASS_VALUE (name);
1363       if (TREE_CODE (field) != FUNCTION_DECL
1364           && ! (want_type && TREE_CODE (field) != TYPE_DECL))
1365         return field;
1366     }
1367
1368   if (TREE_CODE (xbasetype) == TREE_VEC)
1369     {
1370       type = BINFO_TYPE (xbasetype);
1371       basetype_path = xbasetype;
1372     }
1373   else if (IS_AGGR_TYPE_CODE (TREE_CODE (xbasetype)))
1374     {
1375       type = xbasetype;
1376       basetype_path = TYPE_BINFO (type);
1377       my_friendly_assert (BINFO_INHERITANCE_CHAIN (basetype_path) == NULL_TREE,
1378                           980827);
1379     }
1380   else
1381     my_friendly_abort (97);
1382
1383   complete_type (type);
1384
1385 #ifdef GATHER_STATISTICS
1386   n_calls_lookup_field++;
1387 #endif /* GATHER_STATISTICS */
1388
1389   bzero ((PTR) &lfi, sizeof (lfi));
1390   lfi.type = type;
1391   lfi.name = name;
1392   lfi.want_type = want_type;
1393   bfs_walk (basetype_path, &lookup_field_r, &lookup_field_queue_p, &lfi);
1394   rval = lfi.rval;
1395   rval_binfo = lfi.rval_binfo;
1396   if (rval_binfo)
1397     type = BINFO_TYPE (rval_binfo);
1398   errstr = lfi.errstr;
1399
1400   /* If we are not interested in ambiguities, don't report them;
1401      just return NULL_TREE.  */
1402   if (!protect && lfi.ambiguous)
1403     return NULL_TREE;
1404
1405   if (protect == 2)
1406     {
1407       if (lfi.ambiguous)
1408         {
1409           /* This flag tells hack_identifier that the lookup is
1410              ambiguous.  */
1411           TREE_NONLOCAL_FLAG (lfi.ambiguous) = 1;
1412           return scratch_tree_cons (error_mark_node,
1413                                     lfi.ambiguous,
1414                                     NULL_TREE);
1415         }
1416       else
1417         protect = 0;
1418     }
1419
1420   /* [class.access]
1421
1422      In the case of overloaded function names, access control is
1423      applied to the function selected by overloaded resolution.  */
1424   if (rval && protect && !is_overloaded_fn (rval)
1425       && !IS_SIGNATURE_POINTER (DECL_REAL_CONTEXT (rval))
1426       && !IS_SIGNATURE_REFERENCE (DECL_REAL_CONTEXT (rval))
1427       && !enforce_access (xbasetype, rval))
1428     return error_mark_node;
1429
1430   if (errstr && protect)
1431     {
1432       cp_error (errstr, name, type);
1433       if (lfi.ambiguous)
1434         print_candidates (lfi.ambiguous);
1435       rval = error_mark_node;
1436     }
1437
1438   /* If the thing we found was found via the implicit typename
1439      extension, build the typename type.  */
1440   if (rval && lfi.from_dep_base_p && !DECL_CLASS_TEMPLATE_P (rval))
1441     rval = TYPE_STUB_DECL (build_typename_type (BINFO_TYPE (basetype_path),
1442                                                 name, name,
1443                                                 TREE_TYPE (rval)));
1444
1445   if (rval && is_overloaded_fn (rval))
1446     {
1447       rval = scratch_tree_cons (basetype_path, rval, NULL_TREE);
1448       SET_BASELINK_P (rval);
1449     }
1450
1451   return rval;
1452 }
1453
1454 /* Like lookup_member, except that if we find a function member we
1455    return NULL_TREE.  */
1456
1457 tree
1458 lookup_field (xbasetype, name, protect, want_type)
1459      register tree xbasetype, name;
1460      int protect, want_type;
1461 {
1462   tree rval = lookup_member (xbasetype, name, protect, want_type);
1463
1464   /* Ignore functions.  */
1465   if (rval && TREE_CODE (rval) == TREE_LIST)
1466     return NULL_TREE;
1467
1468   return rval;
1469 }
1470
1471 /* Like lookup_member, except that if we find a non-function member we
1472    return NULL_TREE.  */
1473
1474 tree
1475 lookup_fnfields (xbasetype, name, protect)
1476      register tree xbasetype, name;
1477      int protect;
1478 {
1479   tree rval = lookup_member (xbasetype, name, protect, /*want_type=*/0);
1480
1481   /* Ignore non-functions.  */
1482   if (rval && TREE_CODE (rval) != TREE_LIST)
1483     return NULL_TREE;
1484
1485   return rval;
1486 }
1487
1488 /* Try to find NAME inside a nested class.  */
1489
1490 tree
1491 lookup_nested_field (name, complain)
1492      tree name;
1493      int complain;
1494 {
1495   register tree t;
1496
1497   tree id = NULL_TREE;
1498   if (TYPE_MAIN_DECL (current_class_type))
1499     {
1500       /* Climb our way up the nested ladder, seeing if we're trying to
1501          modify a field in an enclosing class.  If so, we should only
1502          be able to modify if it's static.  */
1503       for (t = TYPE_MAIN_DECL (current_class_type);
1504            t && DECL_CONTEXT (t);
1505            t = TYPE_MAIN_DECL (DECL_CONTEXT (t)))
1506         {
1507           if (TREE_CODE (DECL_CONTEXT (t)) != RECORD_TYPE)
1508             break;
1509
1510           /* N.B.: lookup_field will do the access checking for us */
1511           id = lookup_field (DECL_CONTEXT (t), name, complain, 0);
1512           if (id == error_mark_node)
1513             {
1514               id = NULL_TREE;
1515               continue;
1516             }
1517
1518           if (id != NULL_TREE)
1519             {
1520               if (TREE_CODE (id) == FIELD_DECL
1521                   && ! TREE_STATIC (id)
1522                   && TREE_TYPE (id) != error_mark_node)
1523                 {
1524                   if (complain)
1525                     {
1526                       /* At parse time, we don't want to give this error, since
1527                          we won't have enough state to make this kind of
1528                          decision properly.  But there are times (e.g., with
1529                          enums in nested classes) when we do need to call
1530                          this fn at parse time.  So, in those cases, we pass
1531                          complain as a 0 and just return a NULL_TREE.  */
1532                       cp_error ("assignment to non-static member `%D' of enclosing class `%T'",
1533                                 id, DECL_CONTEXT (t));
1534                       /* Mark this for do_identifier().  It would otherwise
1535                          claim that the variable was undeclared.  */
1536                       TREE_TYPE (id) = error_mark_node;
1537                     }
1538                   else
1539                     {
1540                       id = NULL_TREE;
1541                       continue;
1542                     }
1543                 }
1544               break;
1545             }
1546         }
1547     }
1548
1549   return id;
1550 }
1551
1552 /* TYPE is a class type. Return the index of the fields within
1553    the method vector with name NAME, or -1 is no such field exists.  */
1554
1555 int
1556 lookup_fnfields_1 (type, name)
1557      tree type, name;
1558 {
1559   register tree method_vec
1560     = CLASS_TYPE_P (type) ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE;
1561
1562   if (method_vec != 0)
1563     {
1564       register tree *methods = &TREE_VEC_ELT (method_vec, 0);
1565       register tree *end = TREE_VEC_END (method_vec);
1566
1567 #ifdef GATHER_STATISTICS
1568       n_calls_lookup_fnfields_1++;
1569 #endif /* GATHER_STATISTICS */
1570
1571       /* Constructors are first...  */
1572       if (*methods && name == ctor_identifier)
1573         return 0;
1574
1575       /* and destructors are second.  */
1576       if (*++methods && name == dtor_identifier)
1577         return 1;
1578
1579       while (++methods != end && *methods)
1580         {
1581 #ifdef GATHER_STATISTICS
1582           n_outer_fields_searched++;
1583 #endif /* GATHER_STATISTICS */
1584           if (DECL_NAME (OVL_CURRENT (*methods)) == name)
1585             break;
1586         }
1587
1588       /* If we didn't find it, it might have been a template
1589          conversion operator.  (Note that we don't look for this case
1590          above so that we will always find specializations first.)  */
1591       if ((methods == end || !*methods)
1592           && IDENTIFIER_TYPENAME_P (name))
1593         {
1594           methods = &TREE_VEC_ELT (method_vec, 0) + 1;
1595
1596           while (++methods != end && *methods)
1597             {
1598               tree method_name = DECL_NAME (OVL_CURRENT (*methods));
1599
1600               if (!IDENTIFIER_TYPENAME_P (method_name))
1601                 {
1602                   /* Since all conversion operators come first, we know
1603                      there is no such operator.  */
1604                   methods = end;
1605                   break;
1606                 }
1607               else if (TREE_CODE (OVL_CURRENT (*methods)) == TEMPLATE_DECL)
1608                 break;
1609             }
1610         }
1611
1612       if (methods != end && *methods)
1613         return methods - &TREE_VEC_ELT (method_vec, 0);
1614     }
1615
1616   return -1;
1617 }
1618 \f
1619 /* Walk the class hierarchy dominated by TYPE.  FN is called for each
1620    type in the hierarchy, in a breadth-first preorder traversal.  .
1621    If it ever returns a non-NULL value, that value is immediately
1622    returned and the walk is terminated.  At each node FN, is passed a
1623    BINFO indicating the path from the curently visited base-class to
1624    TYPE.  The TREE_CHAINs of the BINFOs may be used for scratch space;
1625    they are otherwise unused.  Before each base-class is walked QFN is
1626    called.  If the value returned is non-zero, the base-class is
1627    walked; otherwise it is not.  If QFN is NULL, it is treated as a
1628    function which always returns 1.  Both FN and QFN are passed the
1629    DATA whenever they are called.  */
1630
1631 static tree
1632 bfs_walk (binfo, fn, qfn, data)
1633      tree binfo;
1634      tree (*fn) PROTO((tree, void *));
1635      tree (*qfn) PROTO((tree, void *));
1636      void *data;
1637 {
1638   size_t head;
1639   size_t tail;
1640   tree rval = NULL_TREE;
1641   /* An array of the base classes of BINFO.  These will be built up in
1642      breadth-first order, except where QFN prunes the search.  */
1643   varray_type bfs_bases;
1644
1645   /* Start with enough room for ten base classes.  That will be enough
1646      for most hierarchies.  */
1647   VARRAY_TREE_INIT (bfs_bases, 10, "search_stack");
1648
1649   /* Put the first type into the stack.  */
1650   VARRAY_TREE (bfs_bases, 0) = binfo;
1651   tail = 1;
1652
1653   for (head = 0; head < tail; ++head)
1654     {
1655       int i;
1656       int n_baselinks;
1657       tree binfos;
1658
1659       /* Pull the next type out of the queue.  */
1660       binfo = VARRAY_TREE (bfs_bases, head);
1661
1662       /* If this is the one we're looking for, we're done.  */
1663       rval = (*fn) (binfo, data);
1664       if (rval)
1665         break;
1666
1667       /* Queue up the base types.  */
1668       binfos = BINFO_BASETYPES (binfo);
1669       n_baselinks = binfos ? TREE_VEC_LENGTH (binfos): 0;
1670       for (i = 0; i < n_baselinks; i++)
1671         {
1672           tree base_binfo = TREE_VEC_ELT (binfos, i);
1673
1674           if (qfn)
1675             base_binfo = (*qfn) (base_binfo, data);
1676
1677           if (base_binfo)
1678             {
1679               if (tail == VARRAY_SIZE (bfs_bases))
1680                 VARRAY_GROW (bfs_bases, 2 * VARRAY_SIZE (bfs_bases));
1681               VARRAY_TREE (bfs_bases, tail) = base_binfo;
1682               ++tail;
1683             }
1684         }
1685     }
1686
1687   /* Clean up.  */
1688   VARRAY_FREE (bfs_bases);
1689
1690   return rval;
1691 }
1692
1693 /* Exactly like bfs_walk, except that a depth-first traversal is
1694    performed, and PREFN is called in preorder, while POSTFN is called
1695    in postorder.  */
1696
1697 static tree
1698 dfs_walk_real (binfo, prefn, postfn, qfn, data)
1699      tree binfo;
1700      tree (*prefn) PROTO((tree, void *));
1701      tree (*postfn) PROTO((tree, void *));
1702      tree (*qfn) PROTO((tree, void *));
1703      void *data;
1704 {
1705   int i;
1706   int n_baselinks;
1707   tree binfos;
1708   tree rval = NULL_TREE;
1709
1710   /* Call the pre-order walking function.  */
1711   if (prefn)
1712     {
1713       rval = (*prefn) (binfo, data);
1714       if (rval)
1715         return rval;
1716     }
1717
1718   /* Process the basetypes.  */
1719   binfos = BINFO_BASETYPES (binfo);
1720   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos): 0;
1721   for (i = 0; i < n_baselinks; i++)
1722     {
1723       tree base_binfo = TREE_VEC_ELT (binfos, i);
1724
1725       if (qfn)
1726         base_binfo = (*qfn) (base_binfo, data);
1727
1728       if (base_binfo)
1729         {
1730           rval = dfs_walk_real (base_binfo, prefn, postfn, qfn, data);
1731           if (rval)
1732             return rval;
1733         }
1734     }
1735
1736   /* Call the post-order walking function.  */
1737   if (postfn)
1738     rval = (*postfn) (binfo, data);
1739
1740   return rval;
1741 }
1742
1743 /* Exactly like bfs_walk, except that a depth-first post-order traversal is
1744    performed.  */
1745
1746 tree
1747 dfs_walk (binfo, fn, qfn, data)
1748      tree binfo;
1749      tree (*fn) PROTO((tree, void *));
1750      tree (*qfn) PROTO((tree, void *));
1751      void *data;
1752 {
1753   return dfs_walk_real (binfo, 0, fn, qfn, data);
1754 }
1755
1756 struct gvnt_info
1757 {
1758   /* The name of the function we are looking for.  */
1759   tree name;
1760   /* The overloaded functions we have found.  */
1761   tree fields;
1762 };
1763
1764 /* Called from get_virtuals_named_this via bfs_walk.  */
1765
1766 static tree
1767 get_virtuals_named_this_r (binfo, data)
1768      tree binfo;
1769      void *data;
1770 {
1771   struct gvnt_info *gvnti = (struct gvnt_info *) data;
1772   tree type = BINFO_TYPE (binfo);
1773   int idx;
1774
1775   idx = lookup_fnfields_here (BINFO_TYPE (binfo), gvnti->name);
1776   if (idx >= 0)
1777     gvnti->fields
1778       = scratch_tree_cons (binfo,
1779                            TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type),
1780                                          idx),
1781                            gvnti->fields);
1782
1783   return NULL_TREE;
1784 }
1785
1786 /* Return the virtual functions with the indicated NAME in the type
1787    indicated by BINFO.  The result is a TREE_LIST whose TREE_PURPOSE
1788    indicates the base class from which the TREE_VALUE (an OVERLOAD or
1789    just a FUNCTION_DECL) originated.  */
1790
1791 static tree
1792 get_virtuals_named_this (binfo, name)
1793      tree binfo;
1794      tree name;
1795 {
1796   struct gvnt_info gvnti;
1797   tree fields;
1798
1799   gvnti.name = name;
1800   gvnti.fields = NULL_TREE;
1801
1802   bfs_walk (binfo, get_virtuals_named_this_r, 0, &gvnti);
1803
1804   /* Get to the function decls, and return the first virtual function
1805      with this name, if there is one.  */
1806   for (fields = gvnti.fields; fields; fields = next_baselink (fields))
1807     {
1808       tree fndecl;
1809
1810       for (fndecl = TREE_VALUE (fields); fndecl; fndecl = OVL_NEXT (fndecl))
1811         if (DECL_VINDEX (OVL_CURRENT (fndecl)))
1812           return fields;
1813     }
1814   return NULL_TREE;
1815 }
1816
1817 static tree
1818 get_virtual_destructor (binfo, data)
1819      tree binfo;
1820      void *data ATTRIBUTE_UNUSED;
1821 {
1822   tree type = BINFO_TYPE (binfo);
1823   if (TYPE_HAS_DESTRUCTOR (type)
1824       && DECL_VINDEX (TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), 1)))
1825     return TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), 1);
1826   return 0;
1827 }
1828
1829 static tree
1830 tree_has_any_destructor_p (binfo, data)
1831      tree binfo;
1832      void *data ATTRIBUTE_UNUSED;
1833 {
1834   tree type = BINFO_TYPE (binfo);
1835   return TYPE_NEEDS_DESTRUCTOR (type) ? binfo : NULL_TREE;
1836 }
1837
1838 /* Returns > 0 if a function with type DRETTYPE overriding a function
1839    with type BRETTYPE is covariant, as defined in [class.virtual].
1840
1841    Returns 1 if trivial covariance, 2 if non-trivial (requiring runtime
1842    adjustment), or -1 if pedantically invalid covariance.  */
1843
1844 static int
1845 covariant_return_p (brettype, drettype)
1846      tree brettype, drettype;
1847 {
1848   tree binfo;
1849
1850   if (TREE_CODE (brettype) == FUNCTION_DECL
1851       || TREE_CODE (brettype) == THUNK_DECL)
1852     {
1853       brettype = TREE_TYPE (TREE_TYPE (brettype));
1854       drettype = TREE_TYPE (TREE_TYPE (drettype));
1855     }
1856   else if (TREE_CODE (brettype) == METHOD_TYPE)
1857     {
1858       brettype = TREE_TYPE (brettype);
1859       drettype = TREE_TYPE (drettype);
1860     }
1861
1862   if (same_type_p (brettype, drettype))
1863     return 0;
1864
1865   if (! (TREE_CODE (brettype) == TREE_CODE (drettype)
1866          && (TREE_CODE (brettype) == POINTER_TYPE
1867              || TREE_CODE (brettype) == REFERENCE_TYPE)
1868          && TYPE_QUALS (brettype) == TYPE_QUALS (drettype)))
1869     return 0;
1870
1871   if (! can_convert (brettype, drettype))
1872     return 0;
1873
1874   brettype = TREE_TYPE (brettype);
1875   drettype = TREE_TYPE (drettype);
1876
1877   /* If not pedantic, allow any standard pointer conversion.  */
1878   if (! IS_AGGR_TYPE (drettype) || ! IS_AGGR_TYPE (brettype))
1879     return -1;
1880
1881   binfo = get_binfo (brettype, drettype, 1);
1882
1883   /* If we get an error_mark_node from get_binfo, it already complained,
1884      so let's just succeed.  */
1885   if (binfo == error_mark_node)
1886     return 1;
1887
1888   if (! BINFO_OFFSET_ZEROP (binfo) || TREE_VIA_VIRTUAL (binfo))
1889     return 2;
1890   return 1;
1891 }
1892
1893 /* Given a class type TYPE, and a function decl FNDECL, look for a
1894    virtual function in TYPE's hierarchy which FNDECL could match as a
1895    virtual function.  It doesn't matter which one we find.
1896
1897    DTORP is nonzero if we are looking for a destructor.  Destructors
1898    need special treatment because they do not match by name.  */
1899
1900 tree
1901 get_matching_virtual (binfo, fndecl, dtorp)
1902      tree binfo, fndecl;
1903      int dtorp;
1904 {
1905   tree tmp = NULL_TREE;
1906   int i;
1907
1908   if (TREE_CODE (fndecl) == TEMPLATE_DECL)
1909     /* In [temp.mem] we have:
1910
1911          A specialization of a member function template does not
1912          override a virtual function from a base class.  */
1913     return NULL_TREE;
1914
1915   /* Breadth first search routines start searching basetypes
1916      of TYPE, so we must perform first ply of search here.  */
1917   if (dtorp)
1918     return bfs_walk (binfo, get_virtual_destructor,
1919                      tree_has_any_destructor_p, 0);
1920   else
1921     {
1922       tree drettype, dtypes, btypes, instptr_type;
1923       tree basetype = DECL_CLASS_CONTEXT (fndecl);
1924       tree baselink, best = NULL_TREE;
1925       tree name = DECL_ASSEMBLER_NAME (fndecl);
1926       tree declarator = DECL_NAME (fndecl);
1927       if (IDENTIFIER_VIRTUAL_P (declarator) == 0)
1928         return NULL_TREE;
1929
1930       baselink = get_virtuals_named_this (binfo, declarator);
1931       if (baselink == NULL_TREE)
1932         return NULL_TREE;
1933
1934       drettype = TREE_TYPE (TREE_TYPE (fndecl));
1935       dtypes = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
1936       if (DECL_STATIC_FUNCTION_P (fndecl))
1937         instptr_type = NULL_TREE;
1938       else
1939         instptr_type = TREE_TYPE (TREE_VALUE (dtypes));
1940
1941       for (; baselink; baselink = next_baselink (baselink))
1942         {
1943           tree tmps;
1944           for (tmps = TREE_VALUE (baselink); tmps; tmps = OVL_NEXT (tmps))
1945             {
1946               tmp = OVL_CURRENT (tmps);
1947               if (! DECL_VINDEX (tmp))
1948                 continue;
1949
1950               btypes = TYPE_ARG_TYPES (TREE_TYPE (tmp));
1951               if (instptr_type == NULL_TREE)
1952                 {
1953                   if (compparms (TREE_CHAIN (btypes), dtypes))
1954                     /* Caller knows to give error in this case.  */
1955                     return tmp;
1956                   return NULL_TREE;
1957                 }
1958
1959               if (/* The first parameter is the `this' parameter,
1960                      which has POINTER_TYPE, and we can therefore
1961                      safely use TYPE_QUALS, rather than
1962                      CP_TYPE_QUALS.  */
1963                   (TYPE_QUALS (TREE_TYPE (TREE_VALUE (btypes)))
1964                    == TYPE_QUALS (instptr_type))
1965                   && compparms (TREE_CHAIN (btypes), TREE_CHAIN (dtypes)))
1966                 {
1967                   tree brettype = TREE_TYPE (TREE_TYPE (tmp));
1968                   if (same_type_p (brettype, drettype))
1969                     /* OK */;
1970                   else if ((i = covariant_return_p (brettype, drettype)))
1971                     {
1972                       if (i == 2)
1973                         sorry ("adjusting pointers for covariant returns");
1974
1975                       if (pedantic && i == -1)
1976                         {
1977                           cp_pedwarn_at ("invalid covariant return type for `%#D' (must be pointer or reference to class)", fndecl);
1978                           cp_pedwarn_at ("  overriding `%#D'", tmp);
1979                         }
1980                     }
1981                   else if (IS_AGGR_TYPE_2 (brettype, drettype)
1982                            && same_or_base_type_p (brettype, drettype))
1983                     {
1984                       error ("invalid covariant return type (must use pointer or reference)");
1985                       cp_error_at ("  overriding `%#D'", tmp);
1986                       cp_error_at ("  with `%#D'", fndecl);
1987                     }
1988                   else if (IDENTIFIER_ERROR_LOCUS (name) == NULL_TREE)
1989                     {
1990                       cp_error_at ("conflicting return type specified for virtual function `%#D'", fndecl);
1991                       cp_error_at ("  overriding definition as `%#D'", tmp);
1992                       SET_IDENTIFIER_ERROR_LOCUS (name, basetype);
1993                     }
1994
1995                   /* FNDECL overrides this function.  We continue to
1996                      check all the other functions in order to catch
1997                      errors; it might be that in some other baseclass
1998                      a virtual function was declared with the same
1999                      parameter types, but a different return type.  */
2000                   best = tmp;
2001                 }
2002             }
2003         }
2004
2005       return best;
2006     }
2007 }
2008
2009 /* Return the list of virtual functions which are abstract in type
2010    TYPE that come from non virtual base classes.  See
2011    expand_direct_vtbls_init for the style of search we do.  */
2012
2013 static tree
2014 get_abstract_virtuals_1 (binfo, do_self, abstract_virtuals)
2015      tree binfo;
2016      int do_self;
2017      tree abstract_virtuals;
2018 {
2019   tree binfos = BINFO_BASETYPES (binfo);
2020   int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
2021
2022   for (i = 0; i < n_baselinks; i++)
2023     {
2024       tree base_binfo = TREE_VEC_ELT (binfos, i);
2025       int is_not_base_vtable
2026         = i != CLASSTYPE_VFIELD_PARENT (BINFO_TYPE (binfo));
2027       if (! TREE_VIA_VIRTUAL (base_binfo))
2028         abstract_virtuals
2029           = get_abstract_virtuals_1 (base_binfo, is_not_base_vtable,
2030                                      abstract_virtuals);
2031     }
2032   /* Should we use something besides CLASSTYPE_VFIELDS? */
2033   if (do_self && CLASSTYPE_VFIELDS (BINFO_TYPE (binfo)))
2034     {
2035       tree virtuals = BINFO_VIRTUALS (binfo);
2036
2037       skip_rtti_stuff (&virtuals);
2038
2039       while (virtuals)
2040         {
2041           tree base_pfn = FNADDR_FROM_VTABLE_ENTRY (TREE_VALUE (virtuals));
2042           tree base_fndecl = TREE_OPERAND (base_pfn, 0);
2043           if (DECL_ABSTRACT_VIRTUAL_P (base_fndecl))
2044             abstract_virtuals = tree_cons (NULL_TREE, base_fndecl, abstract_virtuals);
2045           virtuals = TREE_CHAIN (virtuals);
2046         }
2047     }
2048   return abstract_virtuals;
2049 }
2050
2051 /* Return the list of virtual functions which are abstract in type TYPE.
2052    This information is cached, and so must be built on a
2053    non-temporary obstack.  */
2054
2055 tree
2056 get_abstract_virtuals (type)
2057      tree type;
2058 {
2059   tree vbases;
2060   tree abstract_virtuals = NULL;
2061
2062   /* First get all from non-virtual bases.  */
2063   abstract_virtuals
2064     = get_abstract_virtuals_1 (TYPE_BINFO (type), 1, abstract_virtuals);
2065
2066   for (vbases = CLASSTYPE_VBASECLASSES (type); vbases; vbases = TREE_CHAIN (vbases))
2067     {
2068       tree virtuals = BINFO_VIRTUALS (vbases);
2069
2070       skip_rtti_stuff (&virtuals);
2071
2072       while (virtuals)
2073         {
2074           tree base_pfn = FNADDR_FROM_VTABLE_ENTRY (TREE_VALUE (virtuals));
2075           tree base_fndecl = TREE_OPERAND (base_pfn, 0);
2076           if (DECL_NEEDS_FINAL_OVERRIDER_P (base_fndecl))
2077             cp_error ("`%#D' needs a final overrider", base_fndecl);
2078           else if (DECL_ABSTRACT_VIRTUAL_P (base_fndecl))
2079             abstract_virtuals = tree_cons (NULL_TREE, base_fndecl, abstract_virtuals);
2080           virtuals = TREE_CHAIN (virtuals);
2081         }
2082     }
2083   return nreverse (abstract_virtuals);
2084 }
2085
2086 static tree
2087 next_baselink (baselink)
2088      tree baselink;
2089 {
2090   tree tmp = TREE_TYPE (baselink);
2091   baselink = TREE_CHAIN (baselink);
2092   while (tmp)
2093     {
2094       /* @@ does not yet add previous base types.  */
2095       baselink = tree_cons (TREE_PURPOSE (tmp), TREE_VALUE (tmp),
2096                             baselink);
2097       TREE_TYPE (baselink) = TREE_TYPE (tmp);
2098       tmp = TREE_CHAIN (tmp);
2099     }
2100   return baselink;
2101 }
2102 \f
2103 /* DEPTH-FIRST SEARCH ROUTINES.  */
2104
2105 /* This routine converts a pointer to be a pointer of an immediate
2106    base class.  The normal convert_pointer_to routine would diagnose
2107    the conversion as ambiguous, under MI code that has the base class
2108    as an ambiguous base class.  */
2109
2110 static tree
2111 convert_pointer_to_single_level (to_type, expr)
2112      tree to_type, expr;
2113 {
2114   tree binfo_of_derived;
2115   tree last;
2116
2117   binfo_of_derived = TYPE_BINFO (TREE_TYPE (TREE_TYPE (expr)));
2118   last = get_binfo (to_type, TREE_TYPE (TREE_TYPE (expr)), 0);
2119   my_friendly_assert (BINFO_INHERITANCE_CHAIN (last) == binfo_of_derived,
2120                       980827);
2121   my_friendly_assert (BINFO_INHERITANCE_CHAIN (binfo_of_derived) == NULL_TREE,
2122                       980827);
2123   return build_vbase_path (PLUS_EXPR, build_pointer_type (to_type), expr,
2124                            last, 1);
2125 }
2126
2127 tree markedp (binfo, data)
2128      tree binfo;
2129      void *data ATTRIBUTE_UNUSED;
2130 {
2131   return BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2132 }
2133
2134 static tree
2135 unmarkedp (binfo, data)
2136      tree binfo;
2137      void *data ATTRIBUTE_UNUSED;
2138 {
2139   return !BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2140 }
2141
2142 static tree
2143 marked_vtable_pathp (binfo, data)
2144      tree binfo;
2145      void *data ATTRIBUTE_UNUSED;
2146 {
2147   return BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2148 }
2149
2150 static tree
2151 unmarked_vtable_pathp (binfo, data)
2152      tree binfo;
2153      void *data ATTRIBUTE_UNUSED;
2154 {
2155   return !BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2156 }
2157
2158 static tree
2159 marked_new_vtablep (binfo, data)
2160      tree binfo;
2161      void *data ATTRIBUTE_UNUSED;
2162 {
2163   return BINFO_NEW_VTABLE_MARKED (binfo) ? binfo : NULL_TREE;
2164 }
2165
2166 static tree
2167 unmarked_new_vtablep (binfo, data)
2168      tree binfo;
2169      void *data ATTRIBUTE_UNUSED;
2170 {
2171   return !BINFO_NEW_VTABLE_MARKED (binfo) ? binfo : NULL_TREE;
2172 }
2173
2174 static tree
2175 marked_pushdecls_p (binfo, data)
2176      tree binfo;
2177      void *data ATTRIBUTE_UNUSED;
2178 {
2179   return BINFO_PUSHDECLS_MARKED (binfo) ? binfo : NULL_TREE;
2180 }
2181
2182 static tree
2183 unmarked_pushdecls_p (binfo, data)
2184      tree binfo;
2185      void *data ATTRIBUTE_UNUSED;
2186 {
2187   return !BINFO_PUSHDECLS_MARKED (binfo) ? binfo : NULL_TREE;
2188 }
2189
2190 #if 0
2191 static int dfs_search_slot_nonempty_p (binfo) tree binfo;
2192 { return CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (binfo)) != 0; }
2193 #endif
2194
2195 static tree
2196 dfs_debug_unmarkedp (binfo, data)
2197      tree binfo;
2198      void *data ATTRIBUTE_UNUSED;
2199 {
2200   return (!CLASSTYPE_DEBUG_REQUESTED (BINFO_TYPE (binfo))
2201           ? binfo : NULL_TREE);
2202 }
2203
2204 /* The worker functions for `dfs_walk'.  These do not need to
2205    test anything (vis a vis marking) if they are paired with
2206    a predicate function (above).  */
2207
2208 #if 0
2209 static void
2210 dfs_mark (binfo) tree binfo;
2211 { SET_BINFO_MARKED (binfo); }
2212 #endif
2213
2214 tree
2215 dfs_unmark (binfo, data)
2216      tree binfo;
2217      void *data ATTRIBUTE_UNUSED;
2218 {
2219   CLEAR_BINFO_MARKED (binfo);
2220   return NULL_TREE;
2221 }
2222
2223 #if 0
2224 static void
2225 dfs_mark_vtable_path (binfo) tree binfo;
2226 { SET_BINFO_VTABLE_PATH_MARKED (binfo); }
2227
2228 static void
2229 dfs_unmark_vtable_path (binfo) tree binfo;
2230 { CLEAR_BINFO_VTABLE_PATH_MARKED (binfo); }
2231
2232 static void
2233 dfs_mark_new_vtable (binfo) tree binfo;
2234 { SET_BINFO_NEW_VTABLE_MARKED (binfo); }
2235
2236 static void
2237 dfs_unmark_new_vtable (binfo) tree binfo;
2238 { CLEAR_BINFO_NEW_VTABLE_MARKED (binfo); }
2239
2240 static void
2241 dfs_clear_search_slot (binfo) tree binfo;
2242 { CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (binfo)) = 0; }
2243 #endif
2244
2245 static tree
2246 dfs_debug_mark (binfo, data)
2247      tree binfo;
2248      void *data ATTRIBUTE_UNUSED;
2249 {
2250   tree t = BINFO_TYPE (binfo);
2251
2252   /* Use heuristic that if there are virtual functions,
2253      ignore until we see a non-inline virtual function.  */
2254   tree methods = CLASSTYPE_METHOD_VEC (t);
2255
2256   CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2257
2258   if (methods == 0)
2259     return NULL_TREE;
2260
2261   /* If interface info is known, either we've already emitted the debug
2262      info or we don't need to.  */
2263   if (CLASSTYPE_INTERFACE_KNOWN (t))
2264     return NULL_TREE;
2265
2266   /* If debug info is requested from this context for this type, supply it.
2267      If debug info is requested from another context for this type,
2268      see if some third context can supply it.  */
2269   if (current_function_decl == NULL_TREE
2270       || DECL_CLASS_CONTEXT (current_function_decl) != t)
2271     {
2272       if (TREE_VEC_ELT (methods, 1))
2273         methods = TREE_VEC_ELT (methods, 1);
2274       else if (TREE_VEC_ELT (methods, 0))
2275         methods = TREE_VEC_ELT (methods, 0);
2276       else
2277         methods = TREE_VEC_ELT (methods, 2);
2278       methods = OVL_CURRENT (methods);
2279       while (methods)
2280         {
2281           if (DECL_VINDEX (methods)
2282               && DECL_THIS_INLINE (methods) == 0
2283               && DECL_ABSTRACT_VIRTUAL_P (methods) == 0)
2284             {
2285               /* Somebody, somewhere is going to have to define this
2286                  virtual function.  When they do, they will provide
2287                  the debugging info.  */
2288               return NULL_TREE;
2289             }
2290           methods = TREE_CHAIN (methods);
2291         }
2292     }
2293   /* We cannot rely on some alien method to solve our problems,
2294      so we must write out the debug info ourselves.  */
2295   TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = 0;
2296   rest_of_type_compilation (t, toplevel_bindings_p ());
2297
2298   return NULL_TREE;
2299 }
2300 \f
2301 struct vbase_info
2302 {
2303   tree decl_ptr;
2304   tree inits;
2305   tree vbase_types;
2306 };
2307
2308 /*  Attach to the type of the virtual base class, the pointer to the
2309     virtual base class.  */
2310
2311 static tree
2312 dfs_find_vbases (binfo, data)
2313      tree binfo;
2314      void *data;
2315 {
2316   struct vbase_info *vi = (struct vbase_info *) data;
2317   tree binfos = BINFO_BASETYPES (binfo);
2318   int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
2319
2320   for (i = n_baselinks-1; i >= 0; i--)
2321     {
2322       tree base_binfo = TREE_VEC_ELT (binfos, i);
2323
2324       if (TREE_VIA_VIRTUAL (base_binfo)
2325           && CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (base_binfo)) == 0)
2326         {
2327           tree vbase = BINFO_TYPE (base_binfo);
2328           tree binfo = binfo_member (vbase, vi->vbase_types);
2329
2330           CLASSTYPE_SEARCH_SLOT (vbase)
2331             = build (PLUS_EXPR, build_pointer_type (vbase),
2332                      vi->decl_ptr, BINFO_OFFSET (binfo));
2333         }
2334     }
2335   SET_BINFO_VTABLE_PATH_MARKED (binfo);
2336   SET_BINFO_NEW_VTABLE_MARKED (binfo);
2337
2338   return NULL_TREE;
2339 }
2340
2341 static tree
2342 dfs_init_vbase_pointers (binfo, data)
2343      tree binfo;
2344      void *data;
2345 {
2346   struct vbase_info *vi = (struct vbase_info *) data;
2347   tree type = BINFO_TYPE (binfo);
2348   tree fields = TYPE_FIELDS (type);
2349   tree this_vbase_ptr;
2350
2351   CLEAR_BINFO_VTABLE_PATH_MARKED (binfo);
2352
2353 #if 0
2354   /* See finish_struct_1 for when we can enable this.  */
2355   /* If we have a vtable pointer first, skip it.  */
2356   if (VFIELD_NAME_P (DECL_NAME (fields)))
2357     fields = TREE_CHAIN (fields);
2358 #endif
2359
2360   if (BINFO_INHERITANCE_CHAIN (binfo))
2361     {
2362       this_vbase_ptr = TREE_CHAIN (BINFO_INHERITANCE_CHAIN (binfo));
2363       if (TREE_VIA_VIRTUAL (binfo))
2364         this_vbase_ptr = CLASSTYPE_SEARCH_SLOT (type);
2365       else
2366         this_vbase_ptr = convert_pointer_to_single_level (type,
2367                                                           this_vbase_ptr);
2368       TREE_CHAIN (binfo) = this_vbase_ptr;
2369     }
2370   else
2371     this_vbase_ptr = TREE_CHAIN (binfo);
2372
2373   if (fields == NULL_TREE
2374       || DECL_NAME (fields) == NULL_TREE
2375       || ! VBASE_NAME_P (DECL_NAME (fields)))
2376     return NULL_TREE;
2377
2378   if (build_pointer_type (type)
2379       != TYPE_MAIN_VARIANT (TREE_TYPE (this_vbase_ptr)))
2380     my_friendly_abort (125);
2381
2382   while (fields && DECL_NAME (fields) && VBASE_NAME_P (DECL_NAME (fields)))
2383     {
2384       tree ref = build (COMPONENT_REF, TREE_TYPE (fields),
2385                         build_indirect_ref (this_vbase_ptr, NULL_PTR), fields);
2386       tree init = CLASSTYPE_SEARCH_SLOT (TREE_TYPE (TREE_TYPE (fields)));
2387       vi->inits = tree_cons (binfo_member (TREE_TYPE (TREE_TYPE (fields)),
2388                                            vi->vbase_types),
2389                              build_modify_expr (ref, NOP_EXPR, init),
2390                              vi->inits);
2391       fields = TREE_CHAIN (fields);
2392     }
2393
2394   return NULL_TREE;
2395 }
2396
2397 /* Sometimes this needs to clear both VTABLE_PATH and NEW_VTABLE.  Other
2398    times, just NEW_VTABLE, but optimizer should make both with equal
2399    efficiency (though it does not currently).  */
2400
2401 static tree
2402 dfs_clear_vbase_slots (binfo, data)
2403      tree binfo;
2404      void *data ATTRIBUTE_UNUSED;
2405 {
2406   tree type = BINFO_TYPE (binfo);
2407   CLASSTYPE_SEARCH_SLOT (type) = 0;
2408   CLEAR_BINFO_VTABLE_PATH_MARKED (binfo);
2409   CLEAR_BINFO_NEW_VTABLE_MARKED (binfo);
2410   return NULL_TREE;
2411 }
2412
2413 tree
2414 init_vbase_pointers (type, decl_ptr)
2415      tree type;
2416      tree decl_ptr;
2417 {
2418   if (TYPE_USES_VIRTUAL_BASECLASSES (type))
2419     {
2420       struct vbase_info vi;
2421       int old_flag = flag_this_is_variable;
2422       tree binfo = TYPE_BINFO (type);
2423       flag_this_is_variable = -2;
2424
2425       /* Find all the virtual base classes, marking them for later
2426          initialization.  */
2427       vi.decl_ptr = decl_ptr;
2428       vi.vbase_types = CLASSTYPE_VBASECLASSES (type);
2429       vi.inits = NULL_TREE;
2430
2431       dfs_walk (binfo, dfs_find_vbases, unmarked_vtable_pathp, &vi);
2432
2433       /* Build up a list of the initializers.  */
2434       TREE_CHAIN (binfo) = decl_ptr;
2435       dfs_walk_real (binfo,
2436                      dfs_init_vbase_pointers, 0,
2437                      marked_vtable_pathp,
2438                      &vi);
2439
2440       dfs_walk (binfo, dfs_clear_vbase_slots, marked_new_vtablep, 0);
2441       flag_this_is_variable = old_flag;
2442       return vi.inits;
2443     }
2444   return 0;
2445 }
2446
2447 /* get the virtual context (the vbase that directly contains the
2448    DECL_CLASS_CONTEXT of the FNDECL) that the given FNDECL is declared in,
2449    or NULL_TREE if there is none.
2450
2451    FNDECL must come from a virtual table from a virtual base to ensure that
2452    there is only one possible DECL_CLASS_CONTEXT.
2453
2454    We know that if there is more than one place (binfo) the fndecl that the
2455    declared, they all refer to the same binfo.  See get_class_offset_1 for
2456    the check that ensures this.  */
2457
2458 static tree
2459 virtual_context (fndecl, t, vbase)
2460      tree fndecl, t, vbase;
2461 {
2462   tree path;
2463   if (get_base_distance (DECL_CLASS_CONTEXT (fndecl), t, 0, &path) < 0)
2464     {
2465       /* DECL_CLASS_CONTEXT can be ambiguous in t.  */
2466       if (get_base_distance (DECL_CLASS_CONTEXT (fndecl), vbase, 0, &path) >= 0)
2467         {
2468           while (path)
2469             {
2470               /* Not sure if checking path == vbase is necessary here, but just in
2471                  case it is.  */
2472               if (TREE_VIA_VIRTUAL (path) || path == vbase)
2473                 return binfo_member (BINFO_TYPE (path), CLASSTYPE_VBASECLASSES (t));
2474               path = BINFO_INHERITANCE_CHAIN (path);
2475             }
2476         }
2477       /* This shouldn't happen, I don't want errors! */
2478       warning ("recoverable compiler error, fixups for virtual function");
2479       return vbase;
2480     }
2481   while (path)
2482     {
2483       if (TREE_VIA_VIRTUAL (path))
2484         return binfo_member (BINFO_TYPE (path), CLASSTYPE_VBASECLASSES (t));
2485       path = BINFO_INHERITANCE_CHAIN (path);
2486     }
2487   return 0;
2488 }
2489
2490 /* Fixups upcast offsets for one vtable.
2491    Entries may stay within the VBASE given, or
2492    they may upcast into a direct base, or
2493    they may upcast into a different vbase.
2494
2495    We only need to do fixups in case 2 and 3.  In case 2, we add in
2496    the virtual base offset to effect an upcast, in case 3, we add in
2497    the virtual base offset to effect an upcast, then subtract out the
2498    offset for the other virtual base, to effect a downcast into it.
2499
2500    This routine mirrors fixup_vtable_deltas in functionality, though
2501    this one is runtime based, and the other is compile time based.
2502    Conceivably that routine could be removed entirely, and all fixups
2503    done at runtime.
2504
2505    VBASE_OFFSETS is an association list of virtual bases that contains
2506    offset information for the virtual bases, so the offsets are only
2507    calculated once.  The offsets are computed by where we think the
2508    vbase should be (as noted by the CLASSTYPE_SEARCH_SLOT) minus where
2509    the vbase really is.  */
2510
2511 static void
2512 expand_upcast_fixups (binfo, addr, orig_addr, vbase, vbase_addr, t,
2513                       vbase_offsets)
2514      tree binfo, addr, orig_addr, vbase, vbase_addr, t, *vbase_offsets;
2515 {
2516   tree virtuals = BINFO_VIRTUALS (binfo);
2517   tree vc;
2518   tree delta;
2519   unsigned HOST_WIDE_INT n;
2520
2521   delta = purpose_member (vbase, *vbase_offsets);
2522   if (! delta)
2523     {
2524       delta = CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (vbase));
2525       delta = build (MINUS_EXPR, ptrdiff_type_node, delta, vbase_addr);
2526       delta = save_expr (delta);
2527       delta = tree_cons (vbase, delta, *vbase_offsets);
2528       *vbase_offsets = delta;
2529     }
2530
2531   n = skip_rtti_stuff (&virtuals);
2532
2533   while (virtuals)
2534     {
2535       tree current_fndecl = TREE_VALUE (virtuals);
2536       current_fndecl = FNADDR_FROM_VTABLE_ENTRY (current_fndecl);
2537       current_fndecl = TREE_OPERAND (current_fndecl, 0);
2538       if (current_fndecl
2539           && current_fndecl != abort_fndecl
2540           && (vc=virtual_context (current_fndecl, t, vbase)) != vbase)
2541         {
2542           /* This may in fact need a runtime fixup.  */
2543           tree idx = build_int_2 (n, 0);
2544           tree vtbl = BINFO_VTABLE (binfo);
2545           tree nvtbl = lookup_name (DECL_NAME (vtbl), 0);
2546           tree aref, ref, naref;
2547           tree old_delta, new_delta;
2548           tree init;
2549
2550           if (nvtbl == NULL_TREE
2551               || nvtbl == IDENTIFIER_GLOBAL_VALUE (DECL_NAME (vtbl)))
2552             {
2553               /* Dup it if it isn't in local scope yet.  */
2554               nvtbl = build_decl
2555                 (VAR_DECL, DECL_NAME (vtbl),
2556                  TYPE_MAIN_VARIANT (TREE_TYPE (vtbl)));
2557               DECL_ALIGN (nvtbl) = MAX (TYPE_ALIGN (double_type_node),
2558                                         DECL_ALIGN (nvtbl));
2559               TREE_READONLY (nvtbl) = 0;
2560               DECL_ARTIFICIAL (nvtbl) = 1;
2561               nvtbl = pushdecl (nvtbl);
2562               init = NULL_TREE;
2563               cp_finish_decl (nvtbl, init, NULL_TREE, 0,
2564                               LOOKUP_ONLYCONVERTING);
2565
2566               /* We don't set DECL_VIRTUAL_P and DECL_CONTEXT on nvtbl
2567                  because they wouldn't be useful; everything that wants to
2568                  look at the vtable will look at the decl for the normal
2569                  vtable.  Setting DECL_CONTEXT also screws up
2570                  decl_function_context.  */
2571
2572               init = build (MODIFY_EXPR, TREE_TYPE (nvtbl),
2573                             nvtbl, vtbl);
2574               TREE_SIDE_EFFECTS (init) = 1;
2575               expand_expr_stmt (init);
2576               /* Update the vtable pointers as necessary.  */
2577               ref = build_vfield_ref
2578                 (build_indirect_ref (addr, NULL_PTR),
2579                  DECL_CONTEXT (CLASSTYPE_VFIELD (BINFO_TYPE (binfo))));
2580               expand_expr_stmt
2581                 (build_modify_expr (ref, NOP_EXPR, nvtbl));
2582             }
2583           assemble_external (vtbl);
2584           aref = build_array_ref (vtbl, idx);
2585           naref = build_array_ref (nvtbl, idx);
2586           old_delta = build_component_ref (aref, delta_identifier,
2587                                            NULL_TREE, 0);
2588           new_delta = build_component_ref (naref, delta_identifier,
2589                                            NULL_TREE, 0);
2590
2591           /* This is a upcast, so we have to add the offset for the
2592              virtual base.  */
2593           old_delta = build_binary_op (PLUS_EXPR, old_delta,
2594                                        TREE_VALUE (delta), 0);
2595           if (vc)
2596             {
2597               /* If this is set, we need to subtract out the delta
2598                  adjustments for the other virtual base that we
2599                  downcast into.  */
2600               tree vc_delta = purpose_member (vc, *vbase_offsets);
2601               if (! vc_delta)
2602                 {
2603                   tree vc_addr = convert_pointer_to_real (vc, orig_addr);
2604                   vc_delta = CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (vc));
2605                   vc_delta = build (MINUS_EXPR, ptrdiff_type_node,
2606                                     vc_delta, vc_addr);
2607                   vc_delta = save_expr (vc_delta);
2608                   *vbase_offsets = tree_cons (vc, vc_delta, *vbase_offsets);
2609                 }
2610               else
2611                 vc_delta = TREE_VALUE (vc_delta);
2612
2613               /* This is a downcast, so we have to subtract the offset
2614                  for the virtual base.  */
2615               old_delta = build_binary_op (MINUS_EXPR, old_delta, vc_delta, 0);
2616             }
2617
2618           TREE_READONLY (new_delta) = 0;
2619           TREE_TYPE (new_delta) =
2620             cp_build_qualified_type (TREE_TYPE (new_delta),
2621                                      CP_TYPE_QUALS (TREE_TYPE (new_delta))
2622                                      & ~TYPE_QUAL_CONST);
2623           expand_expr_stmt (build_modify_expr (new_delta, NOP_EXPR,
2624                                                old_delta));
2625         }
2626       ++n;
2627       virtuals = TREE_CHAIN (virtuals);
2628     }
2629 }
2630
2631 /* Fixup upcast offsets for all direct vtables.  Patterned after
2632    expand_direct_vtbls_init.  */
2633
2634 static void
2635 fixup_virtual_upcast_offsets (real_binfo, binfo, init_self, can_elide, addr, orig_addr, type, vbase, vbase_offsets)
2636      tree real_binfo, binfo;
2637      int init_self, can_elide;
2638      tree addr, orig_addr, type, vbase, *vbase_offsets;
2639 {
2640   tree real_binfos = BINFO_BASETYPES (real_binfo);
2641   tree binfos = BINFO_BASETYPES (binfo);
2642   int i, n_baselinks = real_binfos ? TREE_VEC_LENGTH (real_binfos) : 0;
2643
2644   for (i = 0; i < n_baselinks; i++)
2645     {
2646       tree real_base_binfo = TREE_VEC_ELT (real_binfos, i);
2647       tree base_binfo = TREE_VEC_ELT (binfos, i);
2648       int is_not_base_vtable
2649         = i != CLASSTYPE_VFIELD_PARENT (BINFO_TYPE (real_binfo));
2650       if (! TREE_VIA_VIRTUAL (real_base_binfo))
2651         fixup_virtual_upcast_offsets (real_base_binfo, base_binfo,
2652                                       is_not_base_vtable, can_elide, addr,
2653                                       orig_addr, type, vbase, vbase_offsets);
2654     }
2655 #if 0
2656   /* Before turning this on, make sure it is correct.  */
2657   if (can_elide && ! BINFO_MODIFIED (binfo))
2658     return;
2659 #endif
2660   /* Should we use something besides CLASSTYPE_VFIELDS? */
2661   if (init_self && CLASSTYPE_VFIELDS (BINFO_TYPE (real_binfo)))
2662     {
2663       tree new_addr = convert_pointer_to_real (binfo, addr);
2664       expand_upcast_fixups (real_binfo, new_addr, orig_addr, vbase, addr,
2665                             type, vbase_offsets);
2666     }
2667 }
2668
2669 /* Build a COMPOUND_EXPR which when expanded will generate the code
2670    needed to initialize all the virtual function table slots of all
2671    the virtual baseclasses.  MAIN_BINFO is the binfo which determines
2672    the virtual baseclasses to use; TYPE is the type of the object to
2673    which the initialization applies.  TRUE_EXP is the true object we
2674    are initializing, and DECL_PTR is the pointer to the sub-object we
2675    are initializing.
2676
2677    When USE_COMPUTED_OFFSETS is non-zero, we can assume that the
2678    object was laid out by a top-level constructor and the computed
2679    offsets are valid to store vtables.  When zero, we must store new
2680    vtables through virtual baseclass pointers.  */
2681
2682 void
2683 expand_indirect_vtbls_init (binfo, true_exp, decl_ptr)
2684      tree binfo;
2685      tree true_exp, decl_ptr;
2686 {
2687   tree type = BINFO_TYPE (binfo);
2688
2689   /* This function executes during the finish_function() segment,
2690      AFTER the auto variables and temporary stack space has been marked
2691      unused...If space is needed for the virtual function tables,
2692      some of them might fit within what the compiler now thinks
2693      are available stack slots... These values are actually initialized at
2694      the beginnning of the function, so when the automatics use their space,
2695      they will overwrite the values that are placed here. Marking all
2696      temporary space as unavailable prevents this from happening. */
2697
2698   mark_all_temps_used();
2699
2700   if (TYPE_USES_VIRTUAL_BASECLASSES (type))
2701     {
2702       rtx fixup_insns = NULL_RTX;
2703       tree vbases = CLASSTYPE_VBASECLASSES (type);
2704       struct vbase_info vi;
2705       vi.decl_ptr = (true_exp ? build_unary_op (ADDR_EXPR, true_exp, 0)
2706                      : decl_ptr);
2707       vi.vbase_types = vbases;
2708
2709       dfs_walk (binfo, dfs_find_vbases, unmarked_new_vtablep, &vi);
2710
2711       /* Initialized with vtables of type TYPE.  */
2712       for (; vbases; vbases = TREE_CHAIN (vbases))
2713         {
2714           tree addr;
2715
2716           addr = convert_pointer_to_vbase (TREE_TYPE (vbases), vi.decl_ptr);
2717
2718           /* Do all vtables from this virtual base.  */
2719           /* This assumes that virtual bases can never serve as parent
2720              binfos.  (in the CLASSTYPE_VFIELD_PARENT sense)  */
2721           expand_direct_vtbls_init (vbases, TYPE_BINFO (BINFO_TYPE (vbases)),
2722                                     1, 0, addr);
2723
2724           /* Now we adjust the offsets for virtual functions that
2725              cross virtual boundaries on an implicit upcast on vf call
2726              so that the layout of the most complete type is used,
2727              instead of assuming the layout of the virtual bases from
2728              our current type.  */
2729
2730           if (flag_vtable_thunks)
2731             {
2732               /* We don't have dynamic thunks yet!
2733                  So for now, just fail silently.  */
2734             }
2735           else
2736             {
2737               tree vbase_offsets = NULL_TREE;
2738               push_to_sequence (fixup_insns);
2739               fixup_virtual_upcast_offsets (vbases,
2740                                             TYPE_BINFO (BINFO_TYPE (vbases)),
2741                                             1, 0, addr, vi.decl_ptr,
2742                                             type, vbases, &vbase_offsets);
2743               fixup_insns = get_insns ();
2744               end_sequence ();
2745             }
2746         }
2747
2748       if (fixup_insns)
2749         {
2750           extern tree in_charge_identifier;
2751           tree in_charge_node = lookup_name (in_charge_identifier, 0);
2752           if (! in_charge_node)
2753             {
2754               warning ("recoverable internal compiler error, nobody's in charge!");
2755               in_charge_node = integer_zero_node;
2756             }
2757           in_charge_node = build_binary_op (EQ_EXPR, in_charge_node, integer_zero_node, 1);
2758           expand_start_cond (in_charge_node, 0);
2759           emit_insns (fixup_insns);
2760           expand_end_cond ();
2761         }
2762
2763       dfs_walk (binfo, dfs_clear_vbase_slots, marked_new_vtablep, 0);
2764     }
2765 }
2766
2767 /* get virtual base class types.
2768    This adds type to the vbase_types list in reverse dfs order.
2769    Ordering is very important, so don't change it.  */
2770
2771 static tree
2772 dfs_get_vbase_types (binfo, data)
2773      tree binfo;
2774      void *data;
2775 {
2776   tree *vbase_types = (tree *) data;
2777
2778   if (TREE_VIA_VIRTUAL (binfo) && ! BINFO_VBASE_MARKED (binfo))
2779     {
2780       tree new_vbase = make_binfo (integer_zero_node, binfo,
2781                                    BINFO_VTABLE (binfo),
2782                                    BINFO_VIRTUALS (binfo));
2783       TREE_CHAIN (new_vbase) = *vbase_types;
2784       TREE_VIA_VIRTUAL (new_vbase) = 1;
2785       *vbase_types = new_vbase;
2786       SET_BINFO_VBASE_MARKED (binfo);
2787     }
2788   SET_BINFO_MARKED (binfo);
2789   return NULL_TREE;
2790 }
2791
2792 /* Return a list of binfos for the virtual base classes for TYPE, in
2793    depth-first search order.  The list is freshly allocated, so
2794    no modification is made to  the current binfo hierarchy.  */
2795
2796 tree
2797 get_vbase_types (type)
2798      tree type;
2799 {
2800   tree vbase_types;
2801   tree vbases;
2802   tree binfo;
2803
2804   binfo = TYPE_BINFO (type);
2805   vbase_types = NULL_TREE;
2806   dfs_walk (binfo, dfs_get_vbase_types, unmarkedp, &vbase_types);
2807   dfs_walk (binfo, dfs_unmark, markedp, 0);
2808   /* Rely upon the reverse dfs ordering from dfs_get_vbase_types, and now
2809      reverse it so that we get normal dfs ordering.  */
2810   vbase_types = nreverse (vbase_types);
2811
2812   /* unmark marked vbases */
2813   for (vbases = vbase_types; vbases; vbases = TREE_CHAIN (vbases))
2814     CLEAR_BINFO_VBASE_MARKED (vbases);
2815
2816   return vbase_types;
2817 }
2818 \f
2819 /* If we want debug info for a type TYPE, make sure all its base types
2820    are also marked as being potentially interesting.  This avoids
2821    the problem of not writing any debug info for intermediate basetypes
2822    that have abstract virtual functions.  Also mark member types.  */
2823
2824 void
2825 note_debug_info_needed (type)
2826      tree type;
2827 {
2828   tree field;
2829
2830   if (current_template_parms)
2831     return;
2832
2833   if (TYPE_BEING_DEFINED (type))
2834     /* We can't go looking for the base types and fields just yet.  */
2835     return;
2836
2837   /* We can't do the TYPE_DECL_SUPPRESS_DEBUG thing with DWARF, which
2838      does not support name references between translation units.  Well, we
2839      could, but that would mean putting global labels in the debug output
2840      before each exported type and each of its functions and static data
2841      members.  */
2842   if (write_symbols == DWARF_DEBUG || write_symbols == DWARF2_DEBUG)
2843     return;
2844
2845   dfs_walk (TYPE_BINFO (type), dfs_debug_mark, dfs_debug_unmarkedp, 0);
2846   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2847     {
2848       tree ttype;
2849       if (TREE_CODE (field) == FIELD_DECL
2850           && IS_AGGR_TYPE (ttype = target_type (TREE_TYPE (field)))
2851           && dfs_debug_unmarkedp (TYPE_BINFO (ttype), 0))
2852         note_debug_info_needed (ttype);
2853     }
2854 }
2855 \f
2856 /* Subroutines of push_class_decls ().  */
2857
2858 /* Returns 1 iff BINFO is a base we shouldn't really be able to see into,
2859    because it (or one of the intermediate bases) depends on template parms.  */
2860
2861 static int
2862 dependent_base_p (binfo)
2863      tree binfo;
2864 {
2865   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2866     {
2867       if (currently_open_class (TREE_TYPE (binfo)))
2868         break;
2869       if (uses_template_parms (TREE_TYPE (binfo)))
2870         return 1;
2871     }
2872   return 0;
2873 }
2874
2875 static void
2876 setup_class_bindings (name, type_binding_p)
2877      tree name;
2878      int type_binding_p;
2879 {
2880   tree type_binding = NULL_TREE;
2881   tree value_binding;
2882
2883   /* If we've already done the lookup for this declaration, we're
2884      done.  */
2885   if (IDENTIFIER_CLASS_VALUE (name))
2886     return;
2887
2888   /* First, deal with the type binding.  */
2889   if (type_binding_p)
2890     {
2891       type_binding = lookup_member (current_class_type, name,
2892                                     /*protect=*/2,
2893                                     /*want_type=*/1);
2894       if (TREE_CODE (type_binding) == TREE_LIST
2895           && TREE_PURPOSE (type_binding) == error_mark_node)
2896         /* NAME is ambiguous.  */
2897         push_class_level_binding (name, TREE_VALUE (type_binding));
2898       else
2899         pushdecl_class_level (type_binding);
2900     }
2901
2902   /* Now, do the value binding.  */
2903   value_binding = lookup_member (current_class_type, name,
2904                                  /*protect=*/2,
2905                                  /*want_type=*/0);
2906
2907   if (type_binding_p
2908       && (TREE_CODE (value_binding) == TYPE_DECL
2909           || (TREE_CODE (value_binding) == TREE_LIST
2910               && TREE_PURPOSE (value_binding) == error_mark_node
2911               && (TREE_CODE (TREE_VALUE (TREE_VALUE (value_binding)))
2912                   == TYPE_DECL))))
2913     /* We found a type-binding, even when looking for a non-type
2914        binding.  This means that we already processed this binding
2915        above.  */
2916     my_friendly_assert (type_binding_p, 19990401);
2917   else
2918     {
2919       if (TREE_CODE (value_binding) == TREE_LIST
2920           && TREE_PURPOSE (value_binding) == error_mark_node)
2921         /* NAME is ambiguous.  */
2922         push_class_level_binding (name, TREE_VALUE (value_binding));
2923       else
2924         {
2925           if (TREE_CODE (value_binding) == TREE_LIST)
2926             /* NAME is some overloaded functions.  */
2927             value_binding = TREE_VALUE (value_binding);
2928           pushdecl_class_level (value_binding);
2929         }
2930     }
2931 }
2932
2933 /* Push class-level declarations for any names appearing in BINFO that
2934    are TYPE_DECLS.  */
2935
2936 static tree
2937 dfs_push_type_decls (binfo, data)
2938      tree binfo;
2939      void *data ATTRIBUTE_UNUSED;
2940 {
2941   tree type;
2942   tree fields;
2943
2944   type = BINFO_TYPE (binfo);
2945   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2946     if (DECL_NAME (fields) && TREE_CODE (fields) == TYPE_DECL
2947         && !(!same_type_p (type, current_class_type)
2948              && template_self_reference_p (type, fields)))
2949       setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/1);
2950
2951   /* We can't just use BINFO_MARKED because envelope_add_decl uses
2952      DERIVED_FROM_P, which calls get_base_distance.  */
2953   SET_BINFO_PUSHDECLS_MARKED (binfo);
2954
2955   return NULL_TREE;
2956 }
2957
2958 /* Push class-level declarations for any names appearing in BINFO that
2959    are not TYPE_DECLS.  */
2960
2961 static tree
2962 dfs_push_decls (binfo, data)
2963      tree binfo;
2964      void *data;
2965 {
2966   tree type;
2967   tree method_vec;
2968   int dep_base_p;
2969
2970   type = BINFO_TYPE (binfo);
2971   dep_base_p = (processing_template_decl && type != current_class_type
2972                 && dependent_base_p (binfo));
2973   if (!dep_base_p)
2974     {
2975       tree fields;
2976       for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2977         if (DECL_NAME (fields)
2978             && TREE_CODE (fields) != TYPE_DECL
2979             && TREE_CODE (fields) != USING_DECL)
2980           setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/0);
2981         else if (TREE_CODE (fields) == FIELD_DECL
2982                  && ANON_UNION_TYPE_P (TREE_TYPE (fields)))
2983           dfs_push_decls (TYPE_BINFO (TREE_TYPE (fields)), data);
2984
2985       method_vec = (CLASS_TYPE_P (type)
2986                     ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE);
2987       if (method_vec)
2988         {
2989           tree *methods;
2990           tree *end;
2991
2992           /* Farm out constructors and destructors.  */
2993           end = TREE_VEC_END (method_vec);
2994
2995           for (methods = &TREE_VEC_ELT (method_vec, 2);
2996                *methods && methods != end;
2997                methods++)
2998             setup_class_bindings (DECL_NAME (OVL_CURRENT (*methods)),
2999                                   /*type_binding_p=*/0);
3000         }
3001     }
3002
3003   CLEAR_BINFO_PUSHDECLS_MARKED (binfo);
3004
3005   return NULL_TREE;
3006 }
3007
3008 /* When entering the scope of a class, we cache all of the
3009    fields that that class provides within its inheritance
3010    lattice.  Where ambiguities result, we mark them
3011    with `error_mark_node' so that if they are encountered
3012    without explicit qualification, we can emit an error
3013    message.  */
3014
3015 void
3016 push_class_decls (type)
3017      tree type;
3018 {
3019   struct obstack *ambient_obstack = current_obstack;
3020   search_stack = push_search_level (search_stack, &search_obstack);
3021
3022   /* Build up all the relevant bindings and such on the cache
3023      obstack.  That way no memory is wasted when we throw away the
3024      cache later.  */
3025   maybe_push_cache_obstack ();
3026
3027   /* Push class fields into CLASS_VALUE scope, and mark.  */
3028   dfs_walk (TYPE_BINFO (type), dfs_push_type_decls, unmarked_pushdecls_p, 0);
3029
3030   /* Compress fields which have only a single entry
3031      by a given name, and unmark.  */
3032   dfs_walk (TYPE_BINFO (type), dfs_push_decls, marked_pushdecls_p, 0);
3033
3034   /* Undo the call to maybe_push_cache_obstack above.  */
3035   pop_obstacks ();
3036
3037   current_obstack = ambient_obstack;
3038 }
3039
3040 /* Here's a subroutine we need because C lacks lambdas.  */
3041
3042 static tree
3043 dfs_unuse_fields (binfo, data)
3044      tree binfo;
3045      void *data ATTRIBUTE_UNUSED;
3046 {
3047   tree type = TREE_TYPE (binfo);
3048   tree fields;
3049
3050   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
3051     {
3052       if (TREE_CODE (fields) != FIELD_DECL)
3053         continue;
3054
3055       TREE_USED (fields) = 0;
3056       if (DECL_NAME (fields) == NULL_TREE
3057           && TREE_CODE (TREE_TYPE (fields)) == UNION_TYPE)
3058         unuse_fields (TREE_TYPE (fields));
3059     }
3060
3061   return NULL_TREE;
3062 }
3063
3064 void
3065 unuse_fields (type)
3066      tree type;
3067 {
3068   dfs_walk (TYPE_BINFO (type), dfs_unuse_fields, unmarkedp, 0);
3069 }
3070
3071 void
3072 pop_class_decls ()
3073 {
3074   /* We haven't pushed a search level when dealing with cached classes,
3075      so we'd better not try to pop it.  */
3076   if (search_stack)
3077     search_stack = pop_search_level (search_stack);
3078 }
3079
3080 void
3081 print_search_statistics ()
3082 {
3083 #ifdef GATHER_STATISTICS
3084   fprintf (stderr, "%d fields searched in %d[%d] calls to lookup_field[_1]\n",
3085            n_fields_searched, n_calls_lookup_field, n_calls_lookup_field_1);
3086   fprintf (stderr, "%d fnfields searched in %d calls to lookup_fnfields\n",
3087            n_outer_fields_searched, n_calls_lookup_fnfields);
3088   fprintf (stderr, "%d calls to get_base_type\n", n_calls_get_base_type);
3089 #else /* GATHER_STATISTICS */
3090   fprintf (stderr, "no search statistics\n");
3091 #endif /* GATHER_STATISTICS */
3092 }
3093
3094 void
3095 init_search_processing ()
3096 {
3097   gcc_obstack_init (&search_obstack);
3098   _vptr_name = get_identifier ("_vptr");
3099 }
3100
3101 void
3102 reinit_search_statistics ()
3103 {
3104 #ifdef GATHER_STATISTICS
3105   n_fields_searched = 0;
3106   n_calls_lookup_field = 0, n_calls_lookup_field_1 = 0;
3107   n_calls_lookup_fnfields = 0, n_calls_lookup_fnfields_1 = 0;
3108   n_calls_get_base_type = 0;
3109   n_outer_fields_searched = 0;
3110   n_contexts_saved = 0;
3111 #endif /* GATHER_STATISTICS */
3112 }
3113
3114 #define scratch_tree_cons expr_tree_cons
3115
3116 static tree
3117 add_conversions (binfo, data)
3118      tree binfo;
3119      void *data;
3120 {
3121   int i;
3122   tree method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
3123   tree *conversions = (tree *) data;
3124
3125   for (i = 2; i < TREE_VEC_LENGTH (method_vec); ++i)
3126     {
3127       tree tmp = TREE_VEC_ELT (method_vec, i);
3128       tree name;
3129
3130       if (!tmp || ! DECL_CONV_FN_P (OVL_CURRENT (tmp)))
3131         break;
3132
3133       name = DECL_NAME (OVL_CURRENT (tmp));
3134
3135       /* Make sure we don't already have this conversion.  */
3136       if (! IDENTIFIER_MARKED (name))
3137         {
3138           *conversions = scratch_tree_cons (binfo, tmp, *conversions);
3139           IDENTIFIER_MARKED (name) = 1;
3140         }
3141     }
3142   return NULL_TREE;
3143 }
3144
3145 tree
3146 lookup_conversions (type)
3147      tree type;
3148 {
3149   tree t;
3150   tree conversions = NULL_TREE;
3151
3152   if (TYPE_SIZE (type))
3153     bfs_walk (TYPE_BINFO (type), add_conversions, 0, &conversions);
3154
3155   for (t = conversions; t; t = TREE_CHAIN (t))
3156     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (t)))) = 0;
3157
3158   return conversions;
3159 }
3160
3161 struct overlap_info
3162 {
3163   tree compare_type;
3164   int found_overlap;
3165 };
3166
3167 /* Check whether the empty class indicated by EMPTY_BINFO is also present
3168    at offset 0 in COMPARE_TYPE, and set found_overlap if so.  */
3169
3170 static tree
3171 dfs_check_overlap (empty_binfo, data)
3172      tree empty_binfo;
3173      void *data;
3174 {
3175   struct overlap_info *oi = (struct overlap_info *) data;
3176   tree binfo;
3177   for (binfo = TYPE_BINFO (oi->compare_type);
3178        ;
3179        binfo = BINFO_BASETYPE (binfo, 0))
3180     {
3181       if (BINFO_TYPE (binfo) == BINFO_TYPE (empty_binfo))
3182         {
3183           oi->found_overlap = 1;
3184           break;
3185         }
3186       else if (BINFO_BASETYPES (binfo) == NULL_TREE)
3187         break;
3188     }
3189
3190   return NULL_TREE;
3191 }
3192
3193 /* Trivial function to stop base traversal when we find something.  */
3194
3195 static tree
3196 dfs_no_overlap_yet (binfo, data)
3197      tree binfo;
3198      void *data;
3199 {
3200   struct overlap_info *oi = (struct overlap_info *) data;
3201   return !oi->found_overlap ? binfo : NULL_TREE;
3202 }
3203
3204 /* Returns nonzero if EMPTY_TYPE or any of its bases can also be found at
3205    offset 0 in NEXT_TYPE.  Used in laying out empty base class subobjects.  */
3206
3207 int
3208 types_overlap_p (empty_type, next_type)
3209      tree empty_type, next_type;
3210 {
3211   struct overlap_info oi;
3212
3213   if (! IS_AGGR_TYPE (next_type))
3214     return 0;
3215   oi.compare_type = next_type;
3216   oi.found_overlap = 0;
3217   dfs_walk (TYPE_BINFO (empty_type), dfs_check_overlap,
3218             dfs_no_overlap_yet, &oi);
3219   return oi.found_overlap;
3220 }
3221
3222 struct bfv_info {
3223   tree vbases;
3224   tree var;
3225 };
3226
3227 static tree
3228 dfs_bfv_queue_p (binfo, data)
3229      tree binfo;
3230      void *data;
3231 {
3232   struct bfv_info *bfvi = (struct bfv_info *) data;
3233
3234   /* Use the real virtual base class objects, not the placeholders in
3235      the usual hierarchy.  */
3236   if (TREE_VIA_VIRTUAL (binfo))
3237     return binfo_member (BINFO_TYPE (binfo), bfvi->vbases);
3238
3239   return binfo;
3240 }
3241
3242 /* Passed to dfs_walk_real by binfo_for_vtable; determine if bvtable
3243    comes from BINFO.  */
3244
3245 static tree
3246 dfs_bfv_helper (binfo, data)
3247      tree binfo;
3248      void *data;
3249 {
3250   struct bfv_info *bfvi = (struct bfv_info *) data;
3251
3252   if (BINFO_VTABLE (binfo) == bfvi->var)
3253     return binfo;
3254   return NULL_TREE;
3255 }
3256
3257 /* Given a vtable VAR, determine which binfo it comes from.  */
3258
3259 tree
3260 binfo_for_vtable (var)
3261      tree var;
3262 {
3263   tree type;
3264   struct bfv_info bfvi;
3265
3266   type = DECL_CONTEXT (var);
3267   bfvi.vbases = CLASSTYPE_VBASECLASSES (type);
3268   return dfs_walk_real (TYPE_BINFO (type),
3269                         0, dfs_bfv_helper, dfs_bfv_queue_p, &bfvi);
3270 }