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