gcc/cp/search.c

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