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