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