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