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       && !IS_SIGNATURE_POINTER (DECL_REAL_CONTEXT (rval))
1462       && !IS_SIGNATURE_REFERENCE (DECL_REAL_CONTEXT (rval))
1463       && !enforce_access (xbasetype, rval))
1464     return error_mark_node;
1465
1466   if (errstr && protect)
1467     {
1468       cp_error (errstr, name, type);
1469       if (lfi.ambiguous)
1470         print_candidates (lfi.ambiguous);
1471       rval = error_mark_node;
1472     }
1473
1474   /* If the thing we found was found via the implicit typename
1475      extension, build the typename type.  */
1476   if (rval && lfi.from_dep_base_p && !DECL_CLASS_TEMPLATE_P (rval))
1477     rval = TYPE_STUB_DECL (build_typename_type (BINFO_TYPE (basetype_path),
1478                                                 name, name,
1479                                                 TREE_TYPE (rval)));
1480
1481   if (rval && is_overloaded_fn (rval))
1482     {
1483       rval = scratch_tree_cons (basetype_path, rval, NULL_TREE);
1484       SET_BASELINK_P (rval);
1485     }
1486
1487   return rval;
1488 }
1489
1490 /* Like lookup_member, except that if we find a function member we
1491    return NULL_TREE.  */
1492
1493 tree
1494 lookup_field (xbasetype, name, protect, want_type)
1495      register tree xbasetype, name;
1496      int protect, want_type;
1497 {
1498   tree rval = lookup_member (xbasetype, name, protect, want_type);
1499
1500   /* Ignore functions.  */
1501   if (rval && TREE_CODE (rval) == TREE_LIST)
1502     return NULL_TREE;
1503
1504   return rval;
1505 }
1506
1507 /* Like lookup_member, except that if we find a non-function member we
1508    return NULL_TREE.  */
1509
1510 tree
1511 lookup_fnfields (xbasetype, name, protect)
1512      register tree xbasetype, name;
1513      int protect;
1514 {
1515   tree rval = lookup_member (xbasetype, name, protect, /*want_type=*/0);
1516
1517   /* Ignore non-functions.  */
1518   if (rval && TREE_CODE (rval) != TREE_LIST)
1519     return NULL_TREE;
1520
1521   return rval;
1522 }
1523
1524 /* TYPE is a class type. Return the index of the fields within
1525    the method vector with name NAME, or -1 is no such field exists.  */
1526
1527 int
1528 lookup_fnfields_1 (type, name)
1529      tree type, name;
1530 {
1531   tree method_vec
1532     = CLASS_TYPE_P (type) ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE;
1533
1534   if (method_vec != 0)
1535     {
1536       register int i;
1537       register tree *methods = &TREE_VEC_ELT (method_vec, 0);
1538       int len = TREE_VEC_LENGTH (method_vec);
1539       tree tmp;
1540
1541 #ifdef GATHER_STATISTICS
1542       n_calls_lookup_fnfields_1++;
1543 #endif /* GATHER_STATISTICS */
1544
1545       /* Constructors are first...  */
1546       if (name == ctor_identifier)
1547         return methods[0] ? 0 : -1;
1548
1549       /* and destructors are second.  */
1550       if (name == dtor_identifier)
1551         return methods[1] ? 1 : -1;
1552
1553       for (i = 2; i < len && methods[i]; ++i)
1554         {
1555 #ifdef GATHER_STATISTICS
1556           n_outer_fields_searched++;
1557 #endif /* GATHER_STATISTICS */
1558
1559           tmp = OVL_CURRENT (methods[i]);
1560           if (DECL_NAME (tmp) == name)
1561             return i;
1562
1563           /* If the type is complete and we're past the conversion ops,
1564              switch to binary search.  */
1565           if (! DECL_CONV_FN_P (tmp)
1566               && TYPE_SIZE (type))
1567             {
1568               int lo = i + 1, hi = len;
1569
1570               while (lo < hi)
1571                 {
1572                   i = (lo + hi) / 2;
1573
1574 #ifdef GATHER_STATISTICS
1575                   n_outer_fields_searched++;
1576 #endif /* GATHER_STATISTICS */
1577
1578                   tmp = DECL_NAME (OVL_CURRENT (methods[i]));
1579
1580                   if (tmp > name)
1581                     hi = i;
1582                   else if (tmp < name)
1583                     lo = i + 1;
1584                   else
1585                     return i;
1586                 }
1587               break;
1588             }
1589         }
1590
1591       /* If we didn't find it, it might have been a template
1592          conversion operator.  (Note that we don't look for this case
1593          above so that we will always find specializations first.)  */
1594       if (IDENTIFIER_TYPENAME_P (name))
1595         {
1596           for (i = 2; i < len && methods[i]; ++i)
1597             {
1598               tmp = OVL_CURRENT (methods[i]);
1599               if (! DECL_CONV_FN_P (tmp))
1600                 {
1601                   /* Since all conversion operators come first, we know
1602                      there is no such operator.  */
1603                   break;
1604                 }
1605               else if (TREE_CODE (tmp) == TEMPLATE_DECL)
1606                 return i;
1607             }
1608         }
1609     }
1610
1611   return -1;
1612 }
1613 \f
1614 /* Walk the class hierarchy dominated by TYPE.  FN is called for each
1615    type in the hierarchy, in a breadth-first preorder traversal.  .
1616    If it ever returns a non-NULL value, that value is immediately
1617    returned and the walk is terminated.  At each node FN, is passed a
1618    BINFO indicating the path from the curently visited base-class to
1619    TYPE.  The TREE_CHAINs of the BINFOs may be used for scratch space;
1620    they are otherwise unused.  Before each base-class is walked QFN is
1621    called.  If the value returned is non-zero, the base-class is
1622    walked; otherwise it is not.  If QFN is NULL, it is treated as a
1623    function which always returns 1.  Both FN and QFN are passed the
1624    DATA whenever they are called.  */
1625
1626 static tree
1627 bfs_walk (binfo, fn, qfn, data)
1628      tree binfo;
1629      tree (*fn) PROTO((tree, void *));
1630      tree (*qfn) PROTO((tree, void *));
1631      void *data;
1632 {
1633   size_t head;
1634   size_t tail;
1635   tree rval = NULL_TREE;
1636   /* An array of the base classes of BINFO.  These will be built up in
1637      breadth-first order, except where QFN prunes the search.  */
1638   varray_type bfs_bases;
1639
1640   /* Start with enough room for ten base classes.  That will be enough
1641      for most hierarchies.  */
1642   VARRAY_TREE_INIT (bfs_bases, 10, "search_stack");
1643
1644   /* Put the first type into the stack.  */
1645   VARRAY_TREE (bfs_bases, 0) = binfo;
1646   tail = 1;
1647
1648   for (head = 0; head < tail; ++head)
1649     {
1650       int i;
1651       int n_baselinks;
1652       tree binfos;
1653
1654       /* Pull the next type out of the queue.  */
1655       binfo = VARRAY_TREE (bfs_bases, head);
1656
1657       /* If this is the one we're looking for, we're done.  */
1658       rval = (*fn) (binfo, data);
1659       if (rval)
1660         break;
1661
1662       /* Queue up the base types.  */
1663       binfos = BINFO_BASETYPES (binfo);
1664       n_baselinks = binfos ? TREE_VEC_LENGTH (binfos): 0;
1665       for (i = 0; i < n_baselinks; i++)
1666         {
1667           tree base_binfo = TREE_VEC_ELT (binfos, i);
1668
1669           if (qfn)
1670             base_binfo = (*qfn) (base_binfo, data);
1671
1672           if (base_binfo)
1673             {
1674               if (tail == VARRAY_SIZE (bfs_bases))
1675                 VARRAY_GROW (bfs_bases, 2 * VARRAY_SIZE (bfs_bases));
1676               VARRAY_TREE (bfs_bases, tail) = base_binfo;
1677               ++tail;
1678             }
1679         }
1680     }
1681
1682   /* Clean up.  */
1683   VARRAY_FREE (bfs_bases);
1684
1685   return rval;
1686 }
1687
1688 /* Exactly like bfs_walk, except that a depth-first traversal is
1689    performed, and PREFN is called in preorder, while POSTFN is called
1690    in postorder.  */
1691
1692 static tree
1693 dfs_walk_real (binfo, prefn, postfn, qfn, data)
1694      tree binfo;
1695      tree (*prefn) PROTO((tree, void *));
1696      tree (*postfn) PROTO((tree, void *));
1697      tree (*qfn) PROTO((tree, void *));
1698      void *data;
1699 {
1700   int i;
1701   int n_baselinks;
1702   tree binfos;
1703   tree rval = NULL_TREE;
1704
1705   /* Call the pre-order walking function.  */
1706   if (prefn)
1707     {
1708       rval = (*prefn) (binfo, data);
1709       if (rval)
1710         return rval;
1711     }
1712
1713   /* Process the basetypes.  */
1714   binfos = BINFO_BASETYPES (binfo);
1715   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos): 0;
1716   for (i = 0; i < n_baselinks; i++)
1717     {
1718       tree base_binfo = TREE_VEC_ELT (binfos, i);
1719
1720       if (qfn)
1721         base_binfo = (*qfn) (base_binfo, data);
1722
1723       if (base_binfo)
1724         {
1725           rval = dfs_walk_real (base_binfo, prefn, postfn, qfn, data);
1726           if (rval)
1727             return rval;
1728         }
1729     }
1730
1731   /* Call the post-order walking function.  */
1732   if (postfn)
1733     rval = (*postfn) (binfo, data);
1734
1735   return rval;
1736 }
1737
1738 /* Exactly like bfs_walk, except that a depth-first post-order traversal is
1739    performed.  */
1740
1741 tree
1742 dfs_walk (binfo, fn, qfn, data)
1743      tree binfo;
1744      tree (*fn) PROTO((tree, void *));
1745      tree (*qfn) PROTO((tree, void *));
1746      void *data;
1747 {
1748   return dfs_walk_real (binfo, 0, fn, qfn, data);
1749 }
1750
1751 struct gvnt_info
1752 {
1753   /* The name of the function we are looking for.  */
1754   tree name;
1755   /* The overloaded functions we have found.  */
1756   tree fields;
1757 };
1758
1759 /* Called from get_virtuals_named_this via bfs_walk.  */
1760
1761 static tree
1762 get_virtuals_named_this_r (binfo, data)
1763      tree binfo;
1764      void *data;
1765 {
1766   struct gvnt_info *gvnti = (struct gvnt_info *) data;
1767   tree type = BINFO_TYPE (binfo);
1768   int idx;
1769
1770   idx = lookup_fnfields_here (BINFO_TYPE (binfo), gvnti->name);
1771   if (idx >= 0)
1772     gvnti->fields
1773       = scratch_tree_cons (binfo,
1774                            TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type),
1775                                          idx),
1776                            gvnti->fields);
1777
1778   return NULL_TREE;
1779 }
1780
1781 /* Return the virtual functions with the indicated NAME in the type
1782    indicated by BINFO.  The result is a TREE_LIST whose TREE_PURPOSE
1783    indicates the base class from which the TREE_VALUE (an OVERLOAD or
1784    just a FUNCTION_DECL) originated.  */
1785
1786 static tree
1787 get_virtuals_named_this (binfo, name)
1788      tree binfo;
1789      tree name;
1790 {
1791   struct gvnt_info gvnti;
1792   tree fields;
1793
1794   gvnti.name = name;
1795   gvnti.fields = NULL_TREE;
1796
1797   bfs_walk (binfo, get_virtuals_named_this_r, 0, &gvnti);
1798
1799   /* Get to the function decls, and return the first virtual function
1800      with this name, if there is one.  */
1801   for (fields = gvnti.fields; fields; fields = next_baselink (fields))
1802     {
1803       tree fndecl;
1804
1805       for (fndecl = TREE_VALUE (fields); fndecl; fndecl = OVL_NEXT (fndecl))
1806         if (DECL_VINDEX (OVL_CURRENT (fndecl)))
1807           return fields;
1808     }
1809   return NULL_TREE;
1810 }
1811
1812 static tree
1813 get_virtual_destructor (binfo, data)
1814      tree binfo;
1815      void *data ATTRIBUTE_UNUSED;
1816 {
1817   tree type = BINFO_TYPE (binfo);
1818   if (TYPE_HAS_DESTRUCTOR (type)
1819       && DECL_VINDEX (TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), 1)))
1820     return TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), 1);
1821   return 0;
1822 }
1823
1824 static tree
1825 tree_has_any_destructor_p (binfo, data)
1826      tree binfo;
1827      void *data ATTRIBUTE_UNUSED;
1828 {
1829   tree type = BINFO_TYPE (binfo);
1830   return TYPE_NEEDS_DESTRUCTOR (type) ? binfo : NULL_TREE;
1831 }
1832
1833 /* Returns > 0 if a function with type DRETTYPE overriding a function
1834    with type BRETTYPE is covariant, as defined in [class.virtual].
1835
1836    Returns 1 if trivial covariance, 2 if non-trivial (requiring runtime
1837    adjustment), or -1 if pedantically invalid covariance.  */
1838
1839 static int
1840 covariant_return_p (brettype, drettype)
1841      tree brettype, drettype;
1842 {
1843   tree binfo;
1844
1845   if (TREE_CODE (brettype) == FUNCTION_DECL
1846       || TREE_CODE (brettype) == THUNK_DECL)
1847     {
1848       brettype = TREE_TYPE (TREE_TYPE (brettype));
1849       drettype = TREE_TYPE (TREE_TYPE (drettype));
1850     }
1851   else if (TREE_CODE (brettype) == METHOD_TYPE)
1852     {
1853       brettype = TREE_TYPE (brettype);
1854       drettype = TREE_TYPE (drettype);
1855     }
1856
1857   if (same_type_p (brettype, drettype))
1858     return 0;
1859
1860   if (! (TREE_CODE (brettype) == TREE_CODE (drettype)
1861          && (TREE_CODE (brettype) == POINTER_TYPE
1862              || TREE_CODE (brettype) == REFERENCE_TYPE)
1863          && TYPE_QUALS (brettype) == TYPE_QUALS (drettype)))
1864     return 0;
1865
1866   if (! can_convert (brettype, drettype))
1867     return 0;
1868
1869   brettype = TREE_TYPE (brettype);
1870   drettype = TREE_TYPE (drettype);
1871
1872   /* If not pedantic, allow any standard pointer conversion.  */
1873   if (! IS_AGGR_TYPE (drettype) || ! IS_AGGR_TYPE (brettype))
1874     return -1;
1875
1876   binfo = get_binfo (brettype, drettype, 1);
1877
1878   /* If we get an error_mark_node from get_binfo, it already complained,
1879      so let's just succeed.  */
1880   if (binfo == error_mark_node)
1881     return 1;
1882
1883   if (! BINFO_OFFSET_ZEROP (binfo) || TREE_VIA_VIRTUAL (binfo))
1884     return 2;
1885   return 1;
1886 }
1887
1888 /* Check that virtual overrider OVERRIDER is acceptable for base function
1889    BASEFN. Issue diagnostic, and return zero, if unacceptable.  */
1890
1891 int
1892 check_final_overrider (overrider, basefn)
1893      tree overrider, basefn;
1894 {
1895   tree over_type = TREE_TYPE (overrider);
1896   tree base_type = TREE_TYPE (basefn);
1897   tree over_return = TREE_TYPE (over_type);
1898   tree base_return = TREE_TYPE (base_type);
1899   tree over_throw = TYPE_RAISES_EXCEPTIONS (over_type);
1900   tree base_throw = TYPE_RAISES_EXCEPTIONS (base_type);
1901   int i;
1902
1903   if (same_type_p (base_return, over_return))
1904     /* OK */;
1905   else if ((i = covariant_return_p (base_return, over_return)))
1906     {
1907       if (i == 2)
1908         sorry ("adjusting pointers for covariant returns");
1909
1910       if (pedantic && i == -1)
1911         {
1912           cp_pedwarn_at ("invalid covariant return type for `virtual %#D'", overrider);
1913           cp_pedwarn_at ("  overriding `virtual %#D' (must be pointer or reference to class)", basefn);
1914         }
1915     }
1916   else if (IS_AGGR_TYPE_2 (base_return, over_return)
1917            && same_or_base_type_p (base_return, over_return))
1918     {
1919       cp_error_at ("invalid covariant return type for `virtual %#D'", overrider);
1920       cp_error_at ("  overriding `virtual %#D' (must use pointer or reference)", basefn);
1921       return 0;
1922     }
1923   else if (IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider)) == NULL_TREE)
1924     {
1925       cp_error_at ("conflicting return type specified for `virtual %#D'", overrider);
1926       cp_error_at ("  overriding `virtual %#D'", basefn);
1927       SET_IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider),
1928                                   DECL_CLASS_CONTEXT (overrider));
1929       return 0;
1930     }
1931
1932   /* Check throw specifier is subset.  */
1933   /* XXX At the moment, punt on an overriding artificial function. We
1934      don't generate its exception specifier, so can't check it properly.  */
1935   if (! DECL_ARTIFICIAL (overrider)
1936       && !comp_except_specs (base_throw, over_throw, 0))
1937     {
1938       cp_error_at ("looser throw specifier for `virtual %#F'", overrider);
1939       cp_error_at ("  overriding `virtual %#F'", basefn);
1940       return 0;
1941     }
1942   return 1;
1943 }
1944
1945 /* Given a class type TYPE, and a function decl FNDECL, look for a
1946    virtual function in TYPE's hierarchy which FNDECL could match as a
1947    virtual function.  It doesn't matter which one we find.
1948
1949    DTORP is nonzero if we are looking for a destructor.  Destructors
1950    need special treatment because they do not match by name.  */
1951
1952 tree
1953 get_matching_virtual (binfo, fndecl, dtorp)
1954      tree binfo, fndecl;
1955      int dtorp;
1956 {
1957   tree tmp = NULL_TREE;
1958
1959   if (TREE_CODE (fndecl) == TEMPLATE_DECL)
1960     /* In [temp.mem] we have:
1961
1962          A specialization of a member function template does not
1963          override a virtual function from a base class.  */
1964     return NULL_TREE;
1965
1966   /* Breadth first search routines start searching basetypes
1967      of TYPE, so we must perform first ply of search here.  */
1968   if (dtorp)
1969     return bfs_walk (binfo, get_virtual_destructor,
1970                      tree_has_any_destructor_p, 0);
1971   else
1972     {
1973       tree drettype, dtypes, btypes, instptr_type;
1974       tree baselink, best = NULL_TREE;
1975       tree declarator = DECL_NAME (fndecl);
1976       if (IDENTIFIER_VIRTUAL_P (declarator) == 0)
1977         return NULL_TREE;
1978
1979       baselink = get_virtuals_named_this (binfo, declarator);
1980       if (baselink == NULL_TREE)
1981         return NULL_TREE;
1982
1983       drettype = TREE_TYPE (TREE_TYPE (fndecl));
1984       dtypes = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
1985       if (DECL_STATIC_FUNCTION_P (fndecl))
1986         instptr_type = NULL_TREE;
1987       else
1988         instptr_type = TREE_TYPE (TREE_VALUE (dtypes));
1989
1990       for (; baselink; baselink = next_baselink (baselink))
1991         {
1992           tree tmps;
1993           for (tmps = TREE_VALUE (baselink); tmps; tmps = OVL_NEXT (tmps))
1994             {
1995               tmp = OVL_CURRENT (tmps);
1996               if (! DECL_VINDEX (tmp))
1997                 continue;
1998
1999               btypes = TYPE_ARG_TYPES (TREE_TYPE (tmp));
2000               if (instptr_type == NULL_TREE)
2001                 {
2002                   if (compparms (TREE_CHAIN (btypes), dtypes))
2003                     /* Caller knows to give error in this case.  */
2004                     return tmp;
2005                   return NULL_TREE;
2006                 }
2007
2008               if (/* The first parameter is the `this' parameter,
2009                      which has POINTER_TYPE, and we can therefore
2010                      safely use TYPE_QUALS, rather than
2011                      CP_TYPE_QUALS.  */
2012                   (TYPE_QUALS (TREE_TYPE (TREE_VALUE (btypes)))
2013                    == TYPE_QUALS (instptr_type))
2014                   && compparms (TREE_CHAIN (btypes), TREE_CHAIN (dtypes)))
2015                 {
2016                   check_final_overrider (fndecl, tmp);
2017
2018                   /* FNDECL overrides this function.  We continue to
2019                      check all the other functions in order to catch
2020                      errors; it might be that in some other baseclass
2021                      a virtual function was declared with the same
2022                      parameter types, but a different return type.  */
2023                   best = tmp;
2024                 }
2025             }
2026         }
2027
2028       return best;
2029     }
2030 }
2031
2032 /* Return the list of virtual functions which are abstract in type
2033    TYPE that come from non virtual base classes.  See
2034    expand_direct_vtbls_init for the style of search we do.  */
2035
2036 static tree
2037 get_abstract_virtuals_1 (binfo, do_self, abstract_virtuals)
2038      tree binfo;
2039      int do_self;
2040      tree abstract_virtuals;
2041 {
2042   tree binfos = BINFO_BASETYPES (binfo);
2043   int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
2044
2045   for (i = 0; i < n_baselinks; i++)
2046     {
2047       tree base_binfo = TREE_VEC_ELT (binfos, i);
2048       int is_not_base_vtable
2049         = i != CLASSTYPE_VFIELD_PARENT (BINFO_TYPE (binfo));
2050       if (! TREE_VIA_VIRTUAL (base_binfo))
2051         abstract_virtuals
2052           = get_abstract_virtuals_1 (base_binfo, is_not_base_vtable,
2053                                      abstract_virtuals);
2054     }
2055   /* Should we use something besides CLASSTYPE_VFIELDS? */
2056   if (do_self && CLASSTYPE_VFIELDS (BINFO_TYPE (binfo)))
2057     {
2058       tree virtuals = BINFO_VIRTUALS (binfo);
2059
2060       skip_rtti_stuff (&virtuals, BINFO_TYPE (binfo));
2061
2062       while (virtuals)
2063         {
2064           tree base_fndecl = TREE_VALUE (virtuals);
2065           if (DECL_ABSTRACT_VIRTUAL_P (base_fndecl))
2066             abstract_virtuals = tree_cons (NULL_TREE, base_fndecl,
2067                                            abstract_virtuals);
2068           virtuals = TREE_CHAIN (virtuals);
2069         }
2070     }
2071   return abstract_virtuals;
2072 }
2073
2074 /* Return the list of virtual functions which are abstract in type TYPE.
2075    This information is cached, and so must be built on a
2076    non-temporary obstack.  */
2077
2078 tree
2079 get_abstract_virtuals (type)
2080      tree type;
2081 {
2082   tree vbases;
2083   tree abstract_virtuals = NULL;
2084
2085   /* First get all from non-virtual bases.  */
2086   abstract_virtuals
2087     = get_abstract_virtuals_1 (TYPE_BINFO (type), 1, abstract_virtuals);
2088
2089   for (vbases = CLASSTYPE_VBASECLASSES (type); vbases; vbases = TREE_CHAIN (vbases))
2090     {
2091       tree virtuals = BINFO_VIRTUALS (vbases);
2092
2093       skip_rtti_stuff (&virtuals, BINFO_TYPE (vbases));
2094
2095       while (virtuals)
2096         {
2097           tree base_fndecl = TREE_VALUE (virtuals);
2098           if (DECL_NEEDS_FINAL_OVERRIDER_P (base_fndecl))
2099             cp_error ("`%#D' needs a final overrider", base_fndecl);
2100           else if (DECL_ABSTRACT_VIRTUAL_P (base_fndecl))
2101             abstract_virtuals = tree_cons (NULL_TREE, base_fndecl,
2102                                            abstract_virtuals);
2103           virtuals = TREE_CHAIN (virtuals);
2104         }
2105     }
2106   return nreverse (abstract_virtuals);
2107 }
2108
2109 static tree
2110 next_baselink (baselink)
2111      tree baselink;
2112 {
2113   tree tmp = TREE_TYPE (baselink);
2114   baselink = TREE_CHAIN (baselink);
2115   while (tmp)
2116     {
2117       /* @@ does not yet add previous base types.  */
2118       baselink = tree_cons (TREE_PURPOSE (tmp), TREE_VALUE (tmp),
2119                             baselink);
2120       TREE_TYPE (baselink) = TREE_TYPE (tmp);
2121       tmp = TREE_CHAIN (tmp);
2122     }
2123   return baselink;
2124 }
2125 \f
2126 /* DEPTH-FIRST SEARCH ROUTINES.  */
2127
2128 /* This routine converts a pointer to be a pointer of an immediate
2129    base class.  The normal convert_pointer_to routine would diagnose
2130    the conversion as ambiguous, under MI code that has the base class
2131    as an ambiguous base class.  */
2132
2133 static tree
2134 convert_pointer_to_single_level (to_type, expr)
2135      tree to_type, expr;
2136 {
2137   tree derived;
2138   tree binfo_of_derived;
2139   int i;
2140
2141   derived = TREE_TYPE (TREE_TYPE (expr));
2142   binfo_of_derived = TYPE_BINFO (derived);
2143   my_friendly_assert (BINFO_INHERITANCE_CHAIN (binfo_of_derived) == NULL_TREE,
2144                       980827);
2145   for (i = CLASSTYPE_N_BASECLASSES (derived) - 1; i >= 0; --i)
2146     {
2147       tree binfo = BINFO_BASETYPE (binfo_of_derived, i);
2148       my_friendly_assert (BINFO_INHERITANCE_CHAIN (binfo) == binfo_of_derived,
2149                           980827);
2150       if (same_type_p (BINFO_TYPE (binfo), to_type))
2151         return build_vbase_path (PLUS_EXPR,
2152                                  build_pointer_type (to_type),
2153                                  expr, binfo, 1);
2154     }
2155
2156   my_friendly_abort (19990607);
2157
2158   /* NOTREACHED */
2159   return NULL_TREE;
2160 }
2161
2162 tree markedp (binfo, data)
2163      tree binfo;
2164      void *data ATTRIBUTE_UNUSED;
2165 {
2166   return BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2167 }
2168
2169 static tree
2170 unmarkedp (binfo, data)
2171      tree binfo;
2172      void *data ATTRIBUTE_UNUSED;
2173 {
2174   return !BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2175 }
2176
2177 static tree
2178 marked_vtable_pathp (binfo, data)
2179      tree binfo;
2180      void *data ATTRIBUTE_UNUSED;
2181 {
2182   return BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2183 }
2184
2185 static tree
2186 unmarked_vtable_pathp (binfo, data)
2187      tree binfo;
2188      void *data ATTRIBUTE_UNUSED;
2189 {
2190   return !BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2191 }
2192
2193 static tree
2194 marked_new_vtablep (binfo, data)
2195      tree binfo;
2196      void *data ATTRIBUTE_UNUSED;
2197 {
2198   return BINFO_NEW_VTABLE_MARKED (binfo) ? binfo : NULL_TREE;
2199 }
2200
2201 static tree
2202 unmarked_new_vtablep (binfo, data)
2203      tree binfo;
2204      void *data ATTRIBUTE_UNUSED;
2205 {
2206   return !BINFO_NEW_VTABLE_MARKED (binfo) ? binfo : NULL_TREE;
2207 }
2208
2209 static tree
2210 marked_pushdecls_p (binfo, data)
2211      tree binfo;
2212      void *data ATTRIBUTE_UNUSED;
2213 {
2214   return (CLASS_TYPE_P (BINFO_TYPE (binfo))
2215           && BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2216 }
2217
2218 static tree
2219 unmarked_pushdecls_p (binfo, data)
2220      tree binfo;
2221      void *data ATTRIBUTE_UNUSED;
2222 {
2223   return (CLASS_TYPE_P (BINFO_TYPE (binfo))
2224           && !BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2225 }
2226
2227 #if 0
2228 static int dfs_search_slot_nonempty_p (binfo) tree binfo;
2229 { return CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (binfo)) != 0; }
2230 #endif
2231
2232 static tree
2233 dfs_debug_unmarkedp (binfo, data)
2234      tree binfo;
2235      void *data ATTRIBUTE_UNUSED;
2236 {
2237   return (!CLASSTYPE_DEBUG_REQUESTED (BINFO_TYPE (binfo))
2238           ? binfo : NULL_TREE);
2239 }
2240
2241 /* The worker functions for `dfs_walk'.  These do not need to
2242    test anything (vis a vis marking) if they are paired with
2243    a predicate function (above).  */
2244
2245 #if 0
2246 static void
2247 dfs_mark (binfo) tree binfo;
2248 { SET_BINFO_MARKED (binfo); }
2249 #endif
2250
2251 tree
2252 dfs_unmark (binfo, data)
2253      tree binfo;
2254      void *data ATTRIBUTE_UNUSED;
2255 {
2256   CLEAR_BINFO_MARKED (binfo);
2257   return NULL_TREE;
2258 }
2259
2260 #if 0
2261 static void
2262 dfs_mark_vtable_path (binfo) tree binfo;
2263 { SET_BINFO_VTABLE_PATH_MARKED (binfo); }
2264
2265 static void
2266 dfs_unmark_vtable_path (binfo) tree binfo;
2267 { CLEAR_BINFO_VTABLE_PATH_MARKED (binfo); }
2268
2269 static void
2270 dfs_mark_new_vtable (binfo) tree binfo;
2271 { SET_BINFO_NEW_VTABLE_MARKED (binfo); }
2272
2273 static void
2274 dfs_unmark_new_vtable (binfo) tree binfo;
2275 { CLEAR_BINFO_NEW_VTABLE_MARKED (binfo); }
2276
2277 static void
2278 dfs_clear_search_slot (binfo) tree binfo;
2279 { CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (binfo)) = 0; }
2280 #endif
2281
2282 static tree
2283 dfs_debug_mark (binfo, data)
2284      tree binfo;
2285      void *data ATTRIBUTE_UNUSED;
2286 {
2287   tree t = BINFO_TYPE (binfo);
2288
2289   /* Use heuristic that if there are virtual functions,
2290      ignore until we see a non-inline virtual function.  */
2291   tree methods = CLASSTYPE_METHOD_VEC (t);
2292
2293   CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2294
2295   if (methods == 0)
2296     return NULL_TREE;
2297
2298   /* If interface info is known, either we've already emitted the debug
2299      info or we don't need to.  */
2300   if (CLASSTYPE_INTERFACE_KNOWN (t))
2301     return NULL_TREE;
2302
2303   /* If debug info is requested from this context for this type, supply it.
2304      If debug info is requested from another context for this type,
2305      see if some third context can supply it.  */
2306   if (current_function_decl == NULL_TREE
2307       || DECL_CLASS_CONTEXT (current_function_decl) != t)
2308     {
2309       if (TREE_VEC_ELT (methods, 1))
2310         methods = TREE_VEC_ELT (methods, 1);
2311       else if (TREE_VEC_ELT (methods, 0))
2312         methods = TREE_VEC_ELT (methods, 0);
2313       else
2314         methods = TREE_VEC_ELT (methods, 2);
2315       methods = OVL_CURRENT (methods);
2316       while (methods)
2317         {
2318           if (DECL_VINDEX (methods)
2319               && DECL_THIS_INLINE (methods) == 0
2320               && DECL_ABSTRACT_VIRTUAL_P (methods) == 0)
2321             {
2322               /* Somebody, somewhere is going to have to define this
2323                  virtual function.  When they do, they will provide
2324                  the debugging info.  */
2325               return NULL_TREE;
2326             }
2327           methods = TREE_CHAIN (methods);
2328         }
2329     }
2330   /* We cannot rely on some alien method to solve our problems,
2331      so we must write out the debug info ourselves.  */
2332   TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = 0;
2333   rest_of_type_compilation (t, toplevel_bindings_p ());
2334
2335   return NULL_TREE;
2336 }
2337 \f
2338 struct vbase_info
2339 {
2340   tree decl_ptr;
2341   tree inits;
2342   tree vbase_types;
2343 };
2344
2345 /*  Attach to the type of the virtual base class, the pointer to the
2346     virtual base class.  */
2347
2348 static tree
2349 dfs_find_vbases (binfo, data)
2350      tree binfo;
2351      void *data;
2352 {
2353   struct vbase_info *vi = (struct vbase_info *) data;
2354   tree binfos = BINFO_BASETYPES (binfo);
2355   int i, n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
2356
2357   for (i = n_baselinks-1; i >= 0; i--)
2358     {
2359       tree base_binfo = TREE_VEC_ELT (binfos, i);
2360
2361       if (TREE_VIA_VIRTUAL (base_binfo)
2362           && CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (base_binfo)) == 0)
2363         {
2364           tree vbase = BINFO_TYPE (base_binfo);
2365           tree binfo = binfo_member (vbase, vi->vbase_types);
2366
2367           CLASSTYPE_SEARCH_SLOT (vbase)
2368             = build (PLUS_EXPR, build_pointer_type (vbase),
2369                      vi->decl_ptr, BINFO_OFFSET (binfo));
2370         }
2371     }
2372   SET_BINFO_VTABLE_PATH_MARKED (binfo);
2373   SET_BINFO_NEW_VTABLE_MARKED (binfo);
2374
2375   return NULL_TREE;
2376 }
2377
2378 static tree
2379 dfs_init_vbase_pointers (binfo, data)
2380      tree binfo;
2381      void *data;
2382 {
2383   struct vbase_info *vi = (struct vbase_info *) data;
2384   tree type = BINFO_TYPE (binfo);
2385   tree fields = TYPE_FIELDS (type);
2386   tree this_vbase_ptr;
2387
2388   CLEAR_BINFO_VTABLE_PATH_MARKED (binfo);
2389
2390 #if 0
2391   /* See finish_struct_1 for when we can enable this.  */
2392   /* If we have a vtable pointer first, skip it.  */
2393   if (VFIELD_NAME_P (DECL_NAME (fields)))
2394     fields = TREE_CHAIN (fields);
2395 #endif
2396
2397   if (BINFO_INHERITANCE_CHAIN (binfo))
2398     {
2399       this_vbase_ptr = TREE_CHAIN (BINFO_INHERITANCE_CHAIN (binfo));
2400       if (TREE_VIA_VIRTUAL (binfo))
2401         this_vbase_ptr = CLASSTYPE_SEARCH_SLOT (type);
2402       else
2403         this_vbase_ptr = convert_pointer_to_single_level (type,
2404                                                           this_vbase_ptr);
2405       TREE_CHAIN (binfo) = this_vbase_ptr;
2406     }
2407   else
2408     this_vbase_ptr = TREE_CHAIN (binfo);
2409
2410   if (fields == NULL_TREE
2411       || DECL_NAME (fields) == NULL_TREE
2412       || ! VBASE_NAME_P (DECL_NAME (fields)))
2413     return NULL_TREE;
2414
2415   if (build_pointer_type (type)
2416       != TYPE_MAIN_VARIANT (TREE_TYPE (this_vbase_ptr)))
2417     my_friendly_abort (125);
2418
2419   while (fields && DECL_NAME (fields) && VBASE_NAME_P (DECL_NAME (fields)))
2420     {
2421       tree ref = build (COMPONENT_REF, TREE_TYPE (fields),
2422                         build_indirect_ref (this_vbase_ptr, NULL_PTR), fields);
2423       tree init = CLASSTYPE_SEARCH_SLOT (TREE_TYPE (TREE_TYPE (fields)));
2424       vi->inits = tree_cons (binfo_member (TREE_TYPE (TREE_TYPE (fields)),
2425                                            vi->vbase_types),
2426                              build_modify_expr (ref, NOP_EXPR, init),
2427                              vi->inits);
2428       fields = TREE_CHAIN (fields);
2429     }
2430
2431   return NULL_TREE;
2432 }
2433
2434 /* Sometimes this needs to clear both VTABLE_PATH and NEW_VTABLE.  Other
2435    times, just NEW_VTABLE, but optimizer should make both with equal
2436    efficiency (though it does not currently).  */
2437
2438 static tree
2439 dfs_clear_vbase_slots (binfo, data)
2440      tree binfo;
2441      void *data ATTRIBUTE_UNUSED;
2442 {
2443   tree type = BINFO_TYPE (binfo);
2444   CLASSTYPE_SEARCH_SLOT (type) = 0;
2445   CLEAR_BINFO_VTABLE_PATH_MARKED (binfo);
2446   CLEAR_BINFO_NEW_VTABLE_MARKED (binfo);
2447   return NULL_TREE;
2448 }
2449
2450 tree
2451 init_vbase_pointers (type, decl_ptr)
2452      tree type;
2453      tree decl_ptr;
2454 {
2455   if (TYPE_USES_VIRTUAL_BASECLASSES (type))
2456     {
2457       struct vbase_info vi;
2458       int old_flag = flag_this_is_variable;
2459       tree binfo = TYPE_BINFO (type);
2460       flag_this_is_variable = -2;
2461
2462       /* Find all the virtual base classes, marking them for later
2463          initialization.  */
2464       vi.decl_ptr = decl_ptr;
2465       vi.vbase_types = CLASSTYPE_VBASECLASSES (type);
2466       vi.inits = NULL_TREE;
2467
2468       dfs_walk (binfo, dfs_find_vbases, unmarked_vtable_pathp, &vi);
2469
2470       /* Build up a list of the initializers.  */
2471       TREE_CHAIN (binfo) = decl_ptr;
2472       dfs_walk_real (binfo,
2473                      dfs_init_vbase_pointers, 0,
2474                      marked_vtable_pathp,
2475                      &vi);
2476
2477       dfs_walk (binfo, dfs_clear_vbase_slots, marked_new_vtablep, 0);
2478       flag_this_is_variable = old_flag;
2479       return vi.inits;
2480     }
2481   return 0;
2482 }
2483
2484 /* get the virtual context (the vbase that directly contains the
2485    DECL_CLASS_CONTEXT of the FNDECL) that the given FNDECL is declared in,
2486    or NULL_TREE if there is none.
2487
2488    FNDECL must come from a virtual table from a virtual base to ensure that
2489    there is only one possible DECL_CLASS_CONTEXT.
2490
2491    We know that if there is more than one place (binfo) the fndecl that the
2492    declared, they all refer to the same binfo.  See get_class_offset_1 for
2493    the check that ensures this.  */
2494
2495 static tree
2496 virtual_context (fndecl, t, vbase)
2497      tree fndecl, t, vbase;
2498 {
2499   tree path;
2500   if (get_base_distance (DECL_CLASS_CONTEXT (fndecl), t, 0, &path) < 0)
2501     {
2502       /* DECL_CLASS_CONTEXT can be ambiguous in t.  */
2503       if (get_base_distance (DECL_CLASS_CONTEXT (fndecl), vbase, 0, &path) >= 0)
2504         {
2505           while (path)
2506             {
2507               /* Not sure if checking path == vbase is necessary here, but just in
2508                  case it is.  */
2509               if (TREE_VIA_VIRTUAL (path) || path == vbase)
2510                 return binfo_member (BINFO_TYPE (path), CLASSTYPE_VBASECLASSES (t));
2511               path = BINFO_INHERITANCE_CHAIN (path);
2512             }
2513         }
2514       /* This shouldn't happen, I don't want errors! */
2515       warning ("recoverable compiler error, fixups for virtual function");
2516       return vbase;
2517     }
2518   while (path)
2519     {
2520       if (TREE_VIA_VIRTUAL (path))
2521         return binfo_member (BINFO_TYPE (path), CLASSTYPE_VBASECLASSES (t));
2522       path = BINFO_INHERITANCE_CHAIN (path);
2523     }
2524   return 0;
2525 }
2526
2527 /* Fixups upcast offsets for one vtable.
2528    Entries may stay within the VBASE given, or
2529    they may upcast into a direct base, or
2530    they may upcast into a different vbase.
2531
2532    We only need to do fixups in case 2 and 3.  In case 2, we add in
2533    the virtual base offset to effect an upcast, in case 3, we add in
2534    the virtual base offset to effect an upcast, then subtract out the
2535    offset for the other virtual base, to effect a downcast into it.
2536
2537    This routine mirrors fixup_vtable_deltas in functionality, though
2538    this one is runtime based, and the other is compile time based.
2539    Conceivably that routine could be removed entirely, and all fixups
2540    done at runtime.
2541
2542    VBASE_OFFSETS is an association list of virtual bases that contains
2543    offset information for the virtual bases, so the offsets are only
2544    calculated once.  The offsets are computed by where we think the
2545    vbase should be (as noted by the CLASSTYPE_SEARCH_SLOT) minus where
2546    the vbase really is.  */
2547
2548 static void
2549 expand_upcast_fixups (binfo, addr, orig_addr, vbase, vbase_addr, t,
2550                       vbase_offsets)
2551      tree binfo, addr, orig_addr, vbase, vbase_addr, t, *vbase_offsets;
2552 {
2553   tree virtuals = BINFO_VIRTUALS (binfo);
2554   tree vc;
2555   tree delta;
2556   unsigned HOST_WIDE_INT n;
2557
2558   delta = purpose_member (vbase, *vbase_offsets);
2559   if (! delta)
2560     {
2561       delta = CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (vbase));
2562       delta = build (MINUS_EXPR, ptrdiff_type_node, delta, vbase_addr);
2563       delta = save_expr (delta);
2564       delta = tree_cons (vbase, delta, *vbase_offsets);
2565       *vbase_offsets = delta;
2566     }
2567
2568   n = skip_rtti_stuff (&virtuals, BINFO_TYPE (binfo));
2569
2570   while (virtuals)
2571     {
2572       tree current_fndecl = TREE_VALUE (virtuals);
2573
2574       if (current_fndecl
2575           && current_fndecl != abort_fndecl
2576           && (vc=virtual_context (current_fndecl, t, vbase)) != vbase)
2577         {
2578           /* This may in fact need a runtime fixup.  */
2579           tree idx = build_int_2 (n, 0);
2580           tree vtbl = BINFO_VTABLE (binfo);
2581           tree nvtbl = lookup_name (DECL_NAME (vtbl), 0);
2582           tree aref, ref, naref;
2583           tree old_delta, new_delta;
2584           tree init;
2585
2586           if (nvtbl == NULL_TREE
2587               || nvtbl == IDENTIFIER_GLOBAL_VALUE (DECL_NAME (vtbl)))
2588             {
2589               /* Dup it if it isn't in local scope yet.  */
2590               nvtbl = build_decl
2591                 (VAR_DECL, DECL_NAME (vtbl),
2592                  TYPE_MAIN_VARIANT (TREE_TYPE (vtbl)));
2593               DECL_ALIGN (nvtbl) = MAX (TYPE_ALIGN (double_type_node),
2594                                         DECL_ALIGN (nvtbl));
2595               TREE_READONLY (nvtbl) = 0;
2596               DECL_ARTIFICIAL (nvtbl) = 1;
2597               nvtbl = pushdecl (nvtbl);
2598               init = NULL_TREE;
2599               cp_finish_decl (nvtbl, init, NULL_TREE, 0,
2600                               LOOKUP_ONLYCONVERTING);
2601
2602               /* We don't set DECL_VIRTUAL_P and DECL_CONTEXT on nvtbl
2603                  because they wouldn't be useful; everything that wants to
2604                  look at the vtable will look at the decl for the normal
2605                  vtable.  Setting DECL_CONTEXT also screws up
2606                  decl_function_context.  */
2607
2608               init = build (MODIFY_EXPR, TREE_TYPE (nvtbl),
2609                             nvtbl, vtbl);
2610               TREE_SIDE_EFFECTS (init) = 1;
2611               expand_expr_stmt (init);
2612               /* Update the vtable pointers as necessary.  */
2613               ref = build_vfield_ref
2614                 (build_indirect_ref (addr, NULL_PTR),
2615                  DECL_CONTEXT (CLASSTYPE_VFIELD (BINFO_TYPE (binfo))));
2616               expand_expr_stmt
2617                 (build_modify_expr (ref, NOP_EXPR, nvtbl));
2618             }
2619           assemble_external (vtbl);
2620           aref = build_array_ref (vtbl, idx);
2621           naref = build_array_ref (nvtbl, idx);
2622           old_delta = build_component_ref (aref, delta_identifier,
2623                                            NULL_TREE, 0);
2624           new_delta = build_component_ref (naref, delta_identifier,
2625                                            NULL_TREE, 0);
2626
2627           /* This is a upcast, so we have to add the offset for the
2628              virtual base.  */
2629           old_delta = build_binary_op (PLUS_EXPR, old_delta,
2630                                        TREE_VALUE (delta));
2631           if (vc)
2632             {
2633               /* If this is set, we need to subtract out the delta
2634                  adjustments for the other virtual base that we
2635                  downcast into.  */
2636               tree vc_delta = purpose_member (vc, *vbase_offsets);
2637               if (! vc_delta)
2638                 {
2639                   tree vc_addr = convert_pointer_to_real (vc, orig_addr);
2640                   vc_delta = CLASSTYPE_SEARCH_SLOT (BINFO_TYPE (vc));
2641                   vc_delta = build (MINUS_EXPR, ptrdiff_type_node,
2642                                     vc_delta, vc_addr);
2643                   vc_delta = save_expr (vc_delta);
2644                   *vbase_offsets = tree_cons (vc, vc_delta, *vbase_offsets);
2645                 }
2646               else
2647                 vc_delta = TREE_VALUE (vc_delta);
2648
2649               /* This is a downcast, so we have to subtract the offset
2650                  for the virtual base.  */
2651               old_delta = build_binary_op (MINUS_EXPR, old_delta, vc_delta);
2652             }
2653
2654           TREE_READONLY (new_delta) = 0;
2655           TREE_TYPE (new_delta) =
2656             cp_build_qualified_type (TREE_TYPE (new_delta),
2657                                      CP_TYPE_QUALS (TREE_TYPE (new_delta))
2658                                      & ~TYPE_QUAL_CONST);
2659           expand_expr_stmt (build_modify_expr (new_delta, NOP_EXPR,
2660                                                old_delta));
2661         }
2662       ++n;
2663       virtuals = TREE_CHAIN (virtuals);
2664     }
2665 }
2666
2667 /* Fixup upcast offsets for all direct vtables.  Patterned after
2668    expand_direct_vtbls_init.  */
2669
2670 static void
2671 fixup_virtual_upcast_offsets (real_binfo, binfo, init_self, can_elide, addr, orig_addr, type, vbase, vbase_offsets)
2672      tree real_binfo, binfo;
2673      int init_self, can_elide;
2674      tree addr, orig_addr, type, vbase, *vbase_offsets;
2675 {
2676   tree real_binfos = BINFO_BASETYPES (real_binfo);
2677   tree binfos = BINFO_BASETYPES (binfo);
2678   int i, n_baselinks = real_binfos ? TREE_VEC_LENGTH (real_binfos) : 0;
2679
2680   for (i = 0; i < n_baselinks; i++)
2681     {
2682       tree real_base_binfo = TREE_VEC_ELT (real_binfos, i);
2683       tree base_binfo = TREE_VEC_ELT (binfos, i);
2684       int is_not_base_vtable
2685         = i != CLASSTYPE_VFIELD_PARENT (BINFO_TYPE (real_binfo));
2686       if (! TREE_VIA_VIRTUAL (real_base_binfo))
2687         fixup_virtual_upcast_offsets (real_base_binfo, base_binfo,
2688                                       is_not_base_vtable, can_elide, addr,
2689                                       orig_addr, type, vbase, vbase_offsets);
2690     }
2691 #if 0
2692   /* Before turning this on, make sure it is correct.  */
2693   if (can_elide && ! BINFO_MODIFIED (binfo))
2694     return;
2695 #endif
2696   /* Should we use something besides CLASSTYPE_VFIELDS? */
2697   if (init_self && CLASSTYPE_VFIELDS (BINFO_TYPE (real_binfo)))
2698     {
2699       tree new_addr = convert_pointer_to_real (binfo, addr);
2700       expand_upcast_fixups (real_binfo, new_addr, orig_addr, vbase, addr,
2701                             type, vbase_offsets);
2702     }
2703 }
2704
2705 /* Build a COMPOUND_EXPR which when expanded will generate the code
2706    needed to initialize all the virtual function table slots of all
2707    the virtual baseclasses.  MAIN_BINFO is the binfo which determines
2708    the virtual baseclasses to use; TYPE is the type of the object to
2709    which the initialization applies.  TRUE_EXP is the true object we
2710    are initializing, and DECL_PTR is the pointer to the sub-object we
2711    are initializing.
2712
2713    When USE_COMPUTED_OFFSETS is non-zero, we can assume that the
2714    object was laid out by a top-level constructor and the computed
2715    offsets are valid to store vtables.  When zero, we must store new
2716    vtables through virtual baseclass pointers.  */
2717
2718 void
2719 expand_indirect_vtbls_init (binfo, true_exp, decl_ptr)
2720      tree binfo;
2721      tree true_exp, decl_ptr;
2722 {
2723   tree type = BINFO_TYPE (binfo);
2724
2725   /* This function executes during the finish_function() segment,
2726      AFTER the auto variables and temporary stack space has been marked
2727      unused...If space is needed for the virtual function tables,
2728      some of them might fit within what the compiler now thinks
2729      are available stack slots... These values are actually initialized at
2730      the beginnning of the function, so when the automatics use their space,
2731      they will overwrite the values that are placed here. Marking all
2732      temporary space as unavailable prevents this from happening. */
2733
2734   mark_all_temps_used();
2735
2736   if (TYPE_USES_VIRTUAL_BASECLASSES (type))
2737     {
2738       rtx fixup_insns = NULL_RTX;
2739       tree vbases = CLASSTYPE_VBASECLASSES (type);
2740       struct vbase_info vi;
2741       vi.decl_ptr = (true_exp ? build_unary_op (ADDR_EXPR, true_exp, 0)
2742                      : decl_ptr);
2743       vi.vbase_types = vbases;
2744
2745       dfs_walk (binfo, dfs_find_vbases, unmarked_new_vtablep, &vi);
2746
2747       /* Initialized with vtables of type TYPE.  */
2748       for (; vbases; vbases = TREE_CHAIN (vbases))
2749         {
2750           tree addr;
2751
2752           addr = convert_pointer_to_vbase (TREE_TYPE (vbases), vi.decl_ptr);
2753
2754           /* Do all vtables from this virtual base.  */
2755           /* This assumes that virtual bases can never serve as parent
2756              binfos.  (in the CLASSTYPE_VFIELD_PARENT sense)  */
2757           expand_direct_vtbls_init (vbases, TYPE_BINFO (BINFO_TYPE (vbases)),
2758                                     1, 0, addr);
2759
2760           /* Now we adjust the offsets for virtual functions that
2761              cross virtual boundaries on an implicit upcast on vf call
2762              so that the layout of the most complete type is used,
2763              instead of assuming the layout of the virtual bases from
2764              our current type.  */
2765
2766           if (flag_vtable_thunks)
2767             {
2768               /* We don't have dynamic thunks yet!
2769                  So for now, just fail silently.  */
2770             }
2771           else
2772             {
2773               tree vbase_offsets = NULL_TREE;
2774               push_to_sequence (fixup_insns);
2775               fixup_virtual_upcast_offsets (vbases,
2776                                             TYPE_BINFO (BINFO_TYPE (vbases)),
2777                                             1, 0, addr, vi.decl_ptr,
2778                                             type, vbases, &vbase_offsets);
2779               fixup_insns = get_insns ();
2780               end_sequence ();
2781             }
2782         }
2783
2784       if (fixup_insns)
2785         {
2786           extern tree in_charge_identifier;
2787           tree in_charge_node = lookup_name (in_charge_identifier, 0);
2788           if (! in_charge_node)
2789             {
2790               warning ("recoverable internal compiler error, nobody's in charge!");
2791               in_charge_node = integer_zero_node;
2792             }
2793           in_charge_node = build_binary_op (EQ_EXPR, in_charge_node, integer_zero_node);
2794           expand_start_cond (in_charge_node, 0);
2795           emit_insns (fixup_insns);
2796           expand_end_cond ();
2797         }
2798
2799       dfs_walk (binfo, dfs_clear_vbase_slots, marked_new_vtablep, 0);
2800     }
2801 }
2802
2803 /* get virtual base class types.
2804    This adds type to the vbase_types list in reverse dfs order.
2805    Ordering is very important, so don't change it.  */
2806
2807 static tree
2808 dfs_get_vbase_types (binfo, data)
2809      tree binfo;
2810      void *data;
2811 {
2812   tree *vbase_types = (tree *) data;
2813
2814   if (TREE_VIA_VIRTUAL (binfo) && ! BINFO_VBASE_MARKED (binfo))
2815     {
2816       tree new_vbase = make_binfo (integer_zero_node, binfo,
2817                                    BINFO_VTABLE (binfo),
2818                                    BINFO_VIRTUALS (binfo));
2819       TREE_CHAIN (new_vbase) = *vbase_types;
2820       TREE_VIA_VIRTUAL (new_vbase) = 1;
2821       *vbase_types = new_vbase;
2822       SET_BINFO_VBASE_MARKED (binfo);
2823     }
2824   SET_BINFO_MARKED (binfo);
2825   return NULL_TREE;
2826 }
2827
2828 /* Return a list of binfos for the virtual base classes for TYPE, in
2829    depth-first search order.  The list is freshly allocated, so
2830    no modification is made to  the current binfo hierarchy.  */
2831
2832 tree
2833 get_vbase_types (type)
2834      tree type;
2835 {
2836   tree vbase_types;
2837   tree vbases;
2838   tree binfo;
2839
2840   binfo = TYPE_BINFO (type);
2841   vbase_types = NULL_TREE;
2842   dfs_walk (binfo, dfs_get_vbase_types, unmarkedp, &vbase_types);
2843   dfs_walk (binfo, dfs_unmark, markedp, 0);
2844   /* Rely upon the reverse dfs ordering from dfs_get_vbase_types, and now
2845      reverse it so that we get normal dfs ordering.  */
2846   vbase_types = nreverse (vbase_types);
2847
2848   /* unmark marked vbases */
2849   for (vbases = vbase_types; vbases; vbases = TREE_CHAIN (vbases))
2850     CLEAR_BINFO_VBASE_MARKED (vbases);
2851
2852   return vbase_types;
2853 }
2854 \f
2855 /* If we want debug info for a type TYPE, make sure all its base types
2856    are also marked as being potentially interesting.  This avoids
2857    the problem of not writing any debug info for intermediate basetypes
2858    that have abstract virtual functions.  Also mark member types.  */
2859
2860 void
2861 note_debug_info_needed (type)
2862      tree type;
2863 {
2864   tree field;
2865
2866   if (current_template_parms)
2867     return;
2868
2869   if (TYPE_BEING_DEFINED (type))
2870     /* We can't go looking for the base types and fields just yet.  */
2871     return;
2872
2873   /* We can't do the TYPE_DECL_SUPPRESS_DEBUG thing with DWARF, which
2874      does not support name references between translation units.  Well, we
2875      could, but that would mean putting global labels in the debug output
2876      before each exported type and each of its functions and static data
2877      members.  */
2878   if (write_symbols == DWARF_DEBUG || write_symbols == DWARF2_DEBUG
2879       || write_symbols == NO_DEBUG)
2880     return;
2881
2882   dfs_walk (TYPE_BINFO (type), dfs_debug_mark, dfs_debug_unmarkedp, 0);
2883   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2884     {
2885       tree ttype;
2886       if (TREE_CODE (field) == FIELD_DECL
2887           && IS_AGGR_TYPE (ttype = target_type (TREE_TYPE (field)))
2888           && dfs_debug_unmarkedp (TYPE_BINFO (ttype), 0))
2889         note_debug_info_needed (ttype);
2890     }
2891 }
2892 \f
2893 /* Subroutines of push_class_decls ().  */
2894
2895 /* Returns 1 iff BINFO is a base we shouldn't really be able to see into,
2896    because it (or one of the intermediate bases) depends on template parms.  */
2897
2898 static int
2899 dependent_base_p (binfo)
2900      tree binfo;
2901 {
2902   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2903     {
2904       if (currently_open_class (TREE_TYPE (binfo)))
2905         break;
2906       if (uses_template_parms (TREE_TYPE (binfo)))
2907         return 1;
2908     }
2909   return 0;
2910 }
2911
2912 static void
2913 setup_class_bindings (name, type_binding_p)
2914      tree name;
2915      int type_binding_p;
2916 {
2917   tree type_binding = NULL_TREE;
2918   tree value_binding;
2919
2920   /* If we've already done the lookup for this declaration, we're
2921      done.  */
2922   if (IDENTIFIER_CLASS_VALUE (name))
2923     return;
2924
2925   /* First, deal with the type binding.  */
2926   if (type_binding_p)
2927     {
2928       type_binding = lookup_member (current_class_type, name,
2929                                     /*protect=*/2,
2930                                     /*want_type=*/1);
2931       if (TREE_CODE (type_binding) == TREE_LIST
2932           && TREE_TYPE (type_binding) == error_mark_node)
2933         /* NAME is ambiguous.  */
2934         push_class_level_binding (name, type_binding);
2935       else
2936         pushdecl_class_level (type_binding);
2937     }
2938
2939   /* Now, do the value binding.  */
2940   value_binding = lookup_member (current_class_type, name,
2941                                  /*protect=*/2,
2942                                  /*want_type=*/0);
2943
2944   if (type_binding_p
2945       && (TREE_CODE (value_binding) == TYPE_DECL
2946           || (TREE_CODE (value_binding) == TREE_LIST
2947               && TREE_TYPE (value_binding) == error_mark_node
2948               && (TREE_CODE (TREE_VALUE (value_binding))
2949                   == TYPE_DECL))))
2950     /* We found a type-binding, even when looking for a non-type
2951        binding.  This means that we already processed this binding
2952        above.  */
2953     my_friendly_assert (type_binding_p, 19990401);
2954   else
2955     {
2956       if (TREE_CODE (value_binding) == TREE_LIST
2957           && TREE_TYPE (value_binding) == error_mark_node)
2958         /* NAME is ambiguous.  */
2959         push_class_level_binding (name, value_binding);
2960       else
2961         {
2962           if (BASELINK_P (value_binding))
2963             /* NAME is some overloaded functions.  */
2964             value_binding = TREE_VALUE (value_binding);
2965           pushdecl_class_level (value_binding);
2966         }
2967     }
2968 }
2969
2970 /* Push class-level declarations for any names appearing in BINFO that
2971    are TYPE_DECLS.  */
2972
2973 static tree
2974 dfs_push_type_decls (binfo, data)
2975      tree binfo;
2976      void *data ATTRIBUTE_UNUSED;
2977 {
2978   tree type;
2979   tree fields;
2980
2981   type = BINFO_TYPE (binfo);
2982   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2983     if (DECL_NAME (fields) && TREE_CODE (fields) == TYPE_DECL
2984         && !(!same_type_p (type, current_class_type)
2985              && template_self_reference_p (type, fields)))
2986       setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/1);
2987
2988   /* We can't just use BINFO_MARKED because envelope_add_decl uses
2989      DERIVED_FROM_P, which calls get_base_distance.  */
2990   SET_BINFO_PUSHDECLS_MARKED (binfo);
2991
2992   return NULL_TREE;
2993 }
2994
2995 /* Push class-level declarations for any names appearing in BINFO that
2996    are not TYPE_DECLS.  */
2997
2998 static tree
2999 dfs_push_decls (binfo, data)
3000      tree binfo;
3001      void *data;
3002 {
3003   tree type;
3004   tree method_vec;
3005   int dep_base_p;
3006
3007   type = BINFO_TYPE (binfo);
3008   dep_base_p = (processing_template_decl && type != current_class_type
3009                 && dependent_base_p (binfo));
3010   if (!dep_base_p)
3011     {
3012       tree fields;
3013       for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
3014         if (DECL_NAME (fields)
3015             && TREE_CODE (fields) != TYPE_DECL
3016             && TREE_CODE (fields) != USING_DECL)
3017           setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/0);
3018         else if (TREE_CODE (fields) == FIELD_DECL
3019                  && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
3020           dfs_push_decls (TYPE_BINFO (TREE_TYPE (fields)), data);
3021
3022       method_vec = (CLASS_TYPE_P (type)
3023                     ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE);
3024       if (method_vec)
3025         {
3026           tree *methods;
3027           tree *end;
3028
3029           /* Farm out constructors and destructors.  */
3030           end = TREE_VEC_END (method_vec);
3031
3032           for (methods = &TREE_VEC_ELT (method_vec, 2);
3033                *methods && methods != end;
3034                methods++)
3035             setup_class_bindings (DECL_NAME (OVL_CURRENT (*methods)),
3036                                   /*type_binding_p=*/0);
3037         }
3038     }
3039
3040   CLEAR_BINFO_PUSHDECLS_MARKED (binfo);
3041
3042   return NULL_TREE;
3043 }
3044
3045 /* When entering the scope of a class, we cache all of the
3046    fields that that class provides within its inheritance
3047    lattice.  Where ambiguities result, we mark them
3048    with `error_mark_node' so that if they are encountered
3049    without explicit qualification, we can emit an error
3050    message.  */
3051
3052 void
3053 push_class_decls (type)
3054      tree type;
3055 {
3056   struct obstack *ambient_obstack = current_obstack;
3057   search_stack = push_search_level (search_stack, &search_obstack);
3058
3059   /* Build up all the relevant bindings and such on the cache
3060      obstack.  That way no memory is wasted when we throw away the
3061      cache later.  */
3062   push_cache_obstack ();
3063
3064   /* Enter type declarations and mark.  */
3065   dfs_walk (TYPE_BINFO (type), dfs_push_type_decls, unmarked_pushdecls_p, 0);
3066
3067   /* Enter non-type declarations and unmark.  */
3068   dfs_walk (TYPE_BINFO (type), dfs_push_decls, marked_pushdecls_p, 0);
3069
3070   /* Undo the call to push_cache_obstack above.  */
3071   pop_obstacks ();
3072
3073   current_obstack = ambient_obstack;
3074 }
3075
3076 /* Here's a subroutine we need because C lacks lambdas.  */
3077
3078 static tree
3079 dfs_unuse_fields (binfo, data)
3080      tree binfo;
3081      void *data ATTRIBUTE_UNUSED;
3082 {
3083   tree type = TREE_TYPE (binfo);
3084   tree fields;
3085
3086   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
3087     {
3088       if (TREE_CODE (fields) != FIELD_DECL)
3089         continue;
3090
3091       TREE_USED (fields) = 0;
3092       if (DECL_NAME (fields) == NULL_TREE
3093           && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
3094         unuse_fields (TREE_TYPE (fields));
3095     }
3096
3097   return NULL_TREE;
3098 }
3099
3100 void
3101 unuse_fields (type)
3102      tree type;
3103 {
3104   dfs_walk (TYPE_BINFO (type), dfs_unuse_fields, unmarkedp, 0);
3105 }
3106
3107 void
3108 pop_class_decls ()
3109 {
3110   /* We haven't pushed a search level when dealing with cached classes,
3111      so we'd better not try to pop it.  */
3112   if (search_stack)
3113     search_stack = pop_search_level (search_stack);
3114 }
3115
3116 void
3117 print_search_statistics ()
3118 {
3119 #ifdef GATHER_STATISTICS
3120   fprintf (stderr, "%d fields searched in %d[%d] calls to lookup_field[_1]\n",
3121            n_fields_searched, n_calls_lookup_field, n_calls_lookup_field_1);
3122   fprintf (stderr, "%d fnfields searched in %d calls to lookup_fnfields\n",
3123            n_outer_fields_searched, n_calls_lookup_fnfields);
3124   fprintf (stderr, "%d calls to get_base_type\n", n_calls_get_base_type);
3125 #else /* GATHER_STATISTICS */
3126   fprintf (stderr, "no search statistics\n");
3127 #endif /* GATHER_STATISTICS */
3128 }
3129
3130 void
3131 init_search_processing ()
3132 {
3133   gcc_obstack_init (&search_obstack);
3134   _vptr_name = get_identifier ("_vptr");
3135 }
3136
3137 void
3138 reinit_search_statistics ()
3139 {
3140 #ifdef GATHER_STATISTICS
3141   n_fields_searched = 0;
3142   n_calls_lookup_field = 0, n_calls_lookup_field_1 = 0;
3143   n_calls_lookup_fnfields = 0, n_calls_lookup_fnfields_1 = 0;
3144   n_calls_get_base_type = 0;
3145   n_outer_fields_searched = 0;
3146   n_contexts_saved = 0;
3147 #endif /* GATHER_STATISTICS */
3148 }
3149
3150 #define scratch_tree_cons expr_tree_cons
3151
3152 static tree
3153 add_conversions (binfo, data)
3154      tree binfo;
3155      void *data;
3156 {
3157   int i;
3158   tree method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
3159   tree *conversions = (tree *) data;
3160
3161   /* Some builtin types have no method vector, not even an empty one.  */
3162   if (!method_vec)
3163     return NULL_TREE;
3164
3165   for (i = 2; i < TREE_VEC_LENGTH (method_vec); ++i)
3166     {
3167       tree tmp = TREE_VEC_ELT (method_vec, i);
3168       tree name;
3169
3170       if (!tmp || ! DECL_CONV_FN_P (OVL_CURRENT (tmp)))
3171         break;
3172
3173       name = DECL_NAME (OVL_CURRENT (tmp));
3174
3175       /* Make sure we don't already have this conversion.  */
3176       if (! IDENTIFIER_MARKED (name))
3177         {
3178           *conversions = scratch_tree_cons (binfo, tmp, *conversions);
3179           IDENTIFIER_MARKED (name) = 1;
3180         }
3181     }
3182   return NULL_TREE;
3183 }
3184
3185 /* Return a TREE_LIST containing all the non-hidden user-defined
3186    conversion functions for TYPE (and its base-classes).  The
3187    TREE_VALUE of each node is a FUNCTION_DECL or an OVERLOAD
3188    containing the conversion functions.  The TREE_PURPOSE is the BINFO
3189    from which the conversion functions in this node were selected.  */
3190
3191 tree
3192 lookup_conversions (type)
3193      tree type;
3194 {
3195   tree t;
3196   tree conversions = NULL_TREE;
3197
3198   if (TYPE_SIZE (type))
3199     bfs_walk (TYPE_BINFO (type), add_conversions, 0, &conversions);
3200
3201   for (t = conversions; t; t = TREE_CHAIN (t))
3202     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (t)))) = 0;
3203
3204   return conversions;
3205 }
3206
3207 struct overlap_info
3208 {
3209   tree compare_type;
3210   int found_overlap;
3211 };
3212
3213 /* Check whether the empty class indicated by EMPTY_BINFO is also present
3214    at offset 0 in COMPARE_TYPE, and set found_overlap if so.  */
3215
3216 static tree
3217 dfs_check_overlap (empty_binfo, data)
3218      tree empty_binfo;
3219      void *data;
3220 {
3221   struct overlap_info *oi = (struct overlap_info *) data;
3222   tree binfo;
3223   for (binfo = TYPE_BINFO (oi->compare_type);
3224        ;
3225        binfo = BINFO_BASETYPE (binfo, 0))
3226     {
3227       if (BINFO_TYPE (binfo) == BINFO_TYPE (empty_binfo))
3228         {
3229           oi->found_overlap = 1;
3230           break;
3231         }
3232       else if (BINFO_BASETYPES (binfo) == NULL_TREE)
3233         break;
3234     }
3235
3236   return NULL_TREE;
3237 }
3238
3239 /* Trivial function to stop base traversal when we find something.  */
3240
3241 static tree
3242 dfs_no_overlap_yet (binfo, data)
3243      tree binfo;
3244      void *data;
3245 {
3246   struct overlap_info *oi = (struct overlap_info *) data;
3247   return !oi->found_overlap ? binfo : NULL_TREE;
3248 }
3249
3250 /* Returns nonzero if EMPTY_TYPE or any of its bases can also be found at
3251    offset 0 in NEXT_TYPE.  Used in laying out empty base class subobjects.  */
3252
3253 int
3254 types_overlap_p (empty_type, next_type)
3255      tree empty_type, next_type;
3256 {
3257   struct overlap_info oi;
3258
3259   if (! IS_AGGR_TYPE (next_type))
3260     return 0;
3261   oi.compare_type = next_type;
3262   oi.found_overlap = 0;
3263   dfs_walk (TYPE_BINFO (empty_type), dfs_check_overlap,
3264             dfs_no_overlap_yet, &oi);
3265   return oi.found_overlap;
3266 }
3267
3268 struct bfv_info {
3269   tree vbases;
3270   tree var;
3271 };
3272
3273 static tree
3274 dfs_bfv_queue_p (binfo, data)
3275      tree binfo;
3276      void *data;
3277 {
3278   struct bfv_info *bfvi = (struct bfv_info *) data;
3279
3280   /* Use the real virtual base class objects, not the placeholders in
3281      the usual hierarchy.  */
3282   if (TREE_VIA_VIRTUAL (binfo))
3283     return binfo_member (BINFO_TYPE (binfo), bfvi->vbases);
3284
3285   return binfo;
3286 }
3287
3288 /* Passed to dfs_walk_real by binfo_for_vtable; determine if bvtable
3289    comes from BINFO.  */
3290
3291 static tree
3292 dfs_bfv_helper (binfo, data)
3293      tree binfo;
3294      void *data;
3295 {
3296   struct bfv_info *bfvi = (struct bfv_info *) data;
3297
3298   if (BINFO_VTABLE (binfo) == bfvi->var)
3299     return binfo;
3300   return NULL_TREE;
3301 }
3302
3303 /* Given a vtable VAR, determine which binfo it comes from.  */
3304
3305 tree
3306 binfo_for_vtable (var)
3307      tree var;
3308 {
3309   tree type;
3310   struct bfv_info bfvi;
3311
3312   type = DECL_CONTEXT (var);
3313   bfvi.vbases = CLASSTYPE_VBASECLASSES (type);
3314   bfvi.var = var;
3315   return dfs_walk_real (TYPE_BINFO (type),
3316                         0, dfs_bfv_helper, dfs_bfv_queue_p, &bfvi);
3317 }