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 #include "stack.h"
  40
  41 /* Obstack used for remembering decision points of breadth-first.  */
  42
  43 static struct obstack search_obstack;
  44
  45 /* Methods for pushing and popping objects to and from obstacks.  */
  46
  47 struct stack_level *
  48 push_stack_level (obstack, tp, size)
  49      struct obstack *obstack;
  50      char *tp;  /* Sony NewsOS 5.0 compiler doesn't like void * here.  */
  51      int size;
  52 {
  53   struct stack_level *stack;
  54   obstack_grow (obstack, tp, size);
  55   stack = (struct stack_level *) ((char*)obstack_next_free (obstack) - size);
  56   obstack_finish (obstack);
  57   stack->obstack = obstack;
  58   stack->first = (tree *) obstack_base (obstack);
  59   stack->limit = obstack_room (obstack) / sizeof (tree *);
  60   return stack;
  61 }
  62
  63 struct stack_level *
  64 pop_stack_level (stack)
  65      struct stack_level *stack;
  66 {
  67   struct stack_level *tem = stack;
  68   struct obstack *obstack = tem->obstack;
  69   stack = tem->prev;
  70   obstack_free (obstack, tem);
  71   return stack;
  72 }
  73
  74 #define search_level stack_level
  75 static struct search_level *search_stack;
  76
  77 struct vbase_info
  78 {
  79   /* The class dominating the hierarchy.  */
  80   tree type;
  81   /* A pointer to a complete object of the indicated TYPE.  */
  82   tree decl_ptr;
  83   tree inits;
  84 };
  85
  86 static tree get_vbase_1 PARAMS ((tree, tree, unsigned int *));
  87 static tree lookup_field_1 PARAMS ((tree, tree));
  88 static int is_subobject_of_p PARAMS ((tree, tree, tree));
  89 static tree dfs_check_overlap PARAMS ((tree, void *));
  90 static tree dfs_no_overlap_yet PARAMS ((tree, void *));
  91 static int get_base_distance_recursive
  92         PARAMS ((tree, int, int, int, int *, tree *, tree,
  93                int, int *, int, int));
  94 static int dynamic_cast_base_recurse PARAMS ((tree, tree, int, tree *));
  95 static tree marked_pushdecls_p PARAMS ((tree, void *));
  96 static tree unmarked_pushdecls_p PARAMS ((tree, void *));
  97 static tree dfs_debug_unmarkedp PARAMS ((tree, void *));
  98 static tree dfs_debug_mark PARAMS ((tree, void *));
  99 static tree dfs_get_vbase_types PARAMS ((tree, void *));
 100 static tree dfs_push_type_decls PARAMS ((tree, void *));
 101 static tree dfs_push_decls PARAMS ((tree, void *));
 102 static tree dfs_unuse_fields PARAMS ((tree, void *));
 103 static tree add_conversions PARAMS ((tree, void *));
 104 static int covariant_return_p PARAMS ((tree, tree));
 105 static int check_final_overrider PARAMS ((tree, tree));
 106 static int look_for_overrides_r PARAMS ((tree, tree));
 107 static struct search_level *push_search_level
 108         PARAMS ((struct stack_level *, struct obstack *));
 109 static struct search_level *pop_search_level
 110         PARAMS ((struct stack_level *));
 111 static tree bfs_walk
 112         PARAMS ((tree, tree (*) (tree, void *), tree (*) (tree, void *),
 113                void *));
 114 static tree lookup_field_queue_p PARAMS ((tree, void *));
 115 static int shared_member_p PARAMS ((tree));
 116 static tree lookup_field_r PARAMS ((tree, void *));
 117 static tree canonical_binfo PARAMS ((tree));
 118 static tree shared_marked_p PARAMS ((tree, void *));
 119 static tree shared_unmarked_p PARAMS ((tree, void *));
 120 static int  dependent_base_p PARAMS ((tree));
 121 static tree dfs_accessible_queue_p PARAMS ((tree, void *));
 122 static tree dfs_accessible_p PARAMS ((tree, void *));
 123 static tree dfs_access_in_type PARAMS ((tree, void *));
 124 static access_kind access_in_type PARAMS ((tree, tree));
 125 static tree dfs_canonical_queue PARAMS ((tree, void *));
 126 static tree dfs_assert_unmarked_p PARAMS ((tree, void *));
 127 static void assert_canonical_unmarked PARAMS ((tree));
 128 static int protected_accessible_p PARAMS ((tree, tree, tree));
 129 static int friend_accessible_p PARAMS ((tree, tree, tree));
 130 static void setup_class_bindings PARAMS ((tree, int));
 131 static int template_self_reference_p PARAMS ((tree, tree));
 132 static tree get_shared_vbase_if_not_primary PARAMS ((tree, void *));
 133 static tree dfs_find_vbase_instance PARAMS ((tree, void *));
 134 static tree dfs_get_pure_virtuals PARAMS ((tree, void *));
 135 static tree dfs_build_inheritance_graph_order PARAMS ((tree, void *));
 136
 137 /* Allocate a level of searching.  */
 138
 139 static struct search_level *
 140 push_search_level (stack, obstack)
 141      struct stack_level *stack;
 142      struct obstack *obstack;
 143 {
 144   struct search_level tem;
 145
 146   tem.prev = stack;
 147   return push_stack_level (obstack, (char *)&tem, sizeof (tem));
 148 }
 149
 150 /* Discard a level of search allocation.  */
 151
 152 static struct search_level *
 153 pop_search_level (obstack)
 154      struct stack_level *obstack;
 155 {
 156   register struct search_level *stack = pop_stack_level (obstack);
 157
 158   return stack;
 159 }
 160 \f
 161 /* Variables for gathering statistics.  */
 162 #ifdef GATHER_STATISTICS
 163 static int n_fields_searched;
 164 static int n_calls_lookup_field, n_calls_lookup_field_1;
 165 static int n_calls_lookup_fnfields, n_calls_lookup_fnfields_1;
 166 static int n_calls_get_base_type;
 167 static int n_outer_fields_searched;
 168 static int n_contexts_saved;
 169 #endif /* GATHER_STATISTICS */
 170
 171 \f
 172 /* Get a virtual binfo that is found inside BINFO's hierarchy that is
 173    the same type as the type given in PARENT.  To be optimal, we want
 174    the first one that is found by going through the least number of
 175    virtual bases.
 176
 177    This uses a clever algorithm that updates *depth when we find the vbase,
 178    and cuts off other paths of search when they reach that depth.  */
 179
 180 static tree
 181 get_vbase_1 (parent, binfo, depth)
 182      tree parent, binfo;
 183      unsigned int *depth;
 184 {
 185   tree binfos;
 186   int i, n_baselinks;
 187   tree rval = NULL_TREE;
 188   int virtualp = TREE_VIA_VIRTUAL (binfo) != 0;
 189
 190   *depth -= virtualp;
 191   if (virtualp && BINFO_TYPE (binfo) == parent)
 192     {
 193       *depth = 0;
 194       return binfo;
 195     }
 196
 197   binfos = BINFO_BASETYPES (binfo);
 198   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 199
 200   /* Process base types.  */
 201   for (i = 0; i < n_baselinks; i++)
 202     {
 203       tree base_binfo = TREE_VEC_ELT (binfos, i);
 204       tree nrval;
 205
 206       if (*depth == 0)
 207         break;
 208
 209       nrval = get_vbase_1 (parent, base_binfo, depth);
 210       if (nrval)
 211         rval = nrval;
 212     }
 213   *depth += virtualp;
 214   return rval;
 215 }
 216
 217 /* Return the shortest path to vbase PARENT within BINFO, ignoring
 218    access and ambiguity.  */
 219
 220 tree
 221 get_vbase (parent, binfo)
 222      tree parent;
 223      tree binfo;
 224 {
 225   unsigned int d = (unsigned int)-1;
 226   return get_vbase_1 (parent, binfo, &d);
 227 }
 228
 229 /* Convert EXPR to a virtual base class of type TYPE.  We know that
 230    EXPR is a non-null POINTER_TYPE to RECORD_TYPE.  We also know that
 231    the type of what expr points to has a virtual base of type TYPE.  */
 232
 233 tree
 234 convert_pointer_to_vbase (type, expr)
 235      tree type;
 236      tree expr;
 237 {
 238   tree vb = get_vbase (type, TYPE_BINFO (TREE_TYPE (TREE_TYPE (expr))));
 239   return convert_pointer_to_real (vb, expr);
 240 }
 241
 242 /* Check whether the type given in BINFO is derived from PARENT.  If
 243    it isn't, return 0.  If it is, but the derivation is MI-ambiguous
 244    AND protect != 0, emit an error message and return error_mark_node.
 245
 246    Otherwise, if TYPE is derived from PARENT, return the actual base
 247    information, unless a one of the protection violations below
 248    occurs, in which case emit an error message and return error_mark_node.
 249
 250    If PROTECT is 1, then check if access to a public field of PARENT
 251    would be private.  Also check for ambiguity.  */
 252
 253 tree
 254 get_binfo (parent, binfo, protect)
 255      register tree parent, binfo;
 256      int protect;
 257 {
 258   tree type = NULL_TREE;
 259   int dist;
 260   tree rval = NULL_TREE;
 261
 262   if (TREE_CODE (parent) == TREE_VEC)
 263     parent = BINFO_TYPE (parent);
 264   else if (! IS_AGGR_TYPE_CODE (TREE_CODE (parent)))
 265     my_friendly_abort (89);
 266
 267   if (TREE_CODE (binfo) == TREE_VEC)
 268     type = BINFO_TYPE (binfo);
 269   else if (IS_AGGR_TYPE_CODE (TREE_CODE (binfo)))
 270     type = binfo;
 271   else
 272     my_friendly_abort (90);
 273
 274   dist = get_base_distance (parent, binfo, protect, &rval);
 275
 276   if (dist == -3)
 277     {
 278       cp_error ("fields of `%T' are inaccessible in `%T' due to private inheritance",
 279                 parent, type);
 280       return error_mark_node;
 281     }
 282   else if (dist == -2 && protect)
 283     {
 284       cp_error ("type `%T' is ambiguous base class for type `%T'", parent,
 285                 type);
 286       return error_mark_node;
 287     }
 288
 289   return rval;
 290 }
 291
 292 /* This is the newer depth first get_base_distance routine.  */
 293
 294 static int
 295 get_base_distance_recursive (binfo, depth, is_private, rval,
 296                              rval_private_ptr, new_binfo_ptr, parent,
 297                              protect, via_virtual_ptr, via_virtual,
 298                              current_scope_in_chain)
 299      tree binfo;
 300      int depth, is_private, rval;
 301      int *rval_private_ptr;
 302      tree *new_binfo_ptr, parent;
 303      int protect, *via_virtual_ptr, via_virtual;
 304      int current_scope_in_chain;
 305 {
 306   tree binfos;
 307   int i, n_baselinks;
 308
 309   if (protect == 1
 310       && !current_scope_in_chain
 311       && is_friend (BINFO_TYPE (binfo), current_scope ()))
 312     current_scope_in_chain = 1;
 313
 314   if (BINFO_TYPE (binfo) == parent || binfo == parent)
 315     {
 316       int better = 0;
 317
 318       if (rval == -1)
 319         /* This is the first time we've found parent.  */
 320         better = 1;
 321       else if (tree_int_cst_equal (BINFO_OFFSET (*new_binfo_ptr),
 322                                    BINFO_OFFSET (binfo))
 323                && *via_virtual_ptr && via_virtual)
 324         {
 325           /* A new path to the same vbase.  If this one has better
 326              access or is shorter, take it.  */
 327
 328           if (protect)
 329             better = *rval_private_ptr - is_private;
 330           if (better == 0)
 331             better = rval - depth;
 332         }
 333       else
 334         {
 335           /* Ambiguous base class.  */
 336           rval = depth = -2;
 337
 338           /* If we get an ambiguity between virtual and non-virtual base
 339              class, return the non-virtual in case we are ignoring
 340              ambiguity.  */
 341           better = *via_virtual_ptr - via_virtual;
 342         }
 343
 344       if (better > 0)
 345         {
 346           rval = depth;
 347           *rval_private_ptr = is_private;
 348           *new_binfo_ptr = binfo;
 349           *via_virtual_ptr = via_virtual;
 350         }
 351
 352       return rval;
 353     }
 354
 355   binfos = BINFO_BASETYPES (binfo);
 356   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 357   depth += 1;
 358
 359   /* Process base types.  */
 360   for (i = 0; i < n_baselinks; i++)
 361     {
 362       tree base_binfo = TREE_VEC_ELT (binfos, i);
 363
 364       int via_private
 365         = ((protect == 1
 366             && (is_private
 367                 || (!TREE_VIA_PUBLIC (base_binfo)
 368                     && !(TREE_VIA_PROTECTED (base_binfo)
 369                          && current_scope_in_chain)
 370                     && !is_friend (BINFO_TYPE (binfo), current_scope ()))))
 371            || (protect > 1
 372                && (is_private || !TREE_VIA_PUBLIC (base_binfo))));
 373
 374       int this_virtual = via_virtual || TREE_VIA_VIRTUAL (base_binfo);
 375
 376       rval = get_base_distance_recursive (base_binfo, depth, via_private,
 377                                           rval, rval_private_ptr,
 378                                           new_binfo_ptr, parent,
 379                                           protect, via_virtual_ptr,
 380                                           this_virtual,
 381                                           current_scope_in_chain);
 382
 383       /* If we've found a non-virtual, ambiguous base class, we don't need
 384          to keep searching.  */
 385       if (rval == -2 && *via_virtual_ptr == 0)
 386         return rval;
 387     }
 388
 389   return rval;
 390 }
 391
 392 /* Return the number of levels between type PARENT and the type given
 393    in BINFO, following the leftmost path to PARENT not found along a
 394    virtual path, if there are no real PARENTs (all come from virtual
 395    base classes), then follow the shortest public path to PARENT.
 396
 397    Return -1 if TYPE is not derived from PARENT.
 398    Return -2 if PARENT is an ambiguous base class of TYPE, and PROTECT is
 399     non-negative.
 400    Return -3 if PARENT is not accessible in TYPE, and PROTECT is non-zero.
 401
 402    If PATH_PTR is non-NULL, then also build the list of types
 403    from PARENT to TYPE, with TREE_VIA_VIRTUAL and TREE_VIA_PUBLIC
 404    set.
 405
 406    If PROTECT is greater than 1, ignore any special access the current
 407    scope might have when determining whether PARENT is inaccessible.
 408
 409    PARENT can also be a binfo, in which case that exact parent is found
 410    and no other.  convert_pointer_to_real uses this functionality.
 411
 412    If BINFO is a binfo, its BINFO_INHERITANCE_CHAIN will be left alone.  */
 413
 414 int
 415 get_base_distance (parent, binfo, protect, path_ptr)
 416      register tree parent, binfo;
 417      int protect;
 418      tree *path_ptr;
 419 {
 420   int rval;
 421   int rval_private = 0;
 422   tree type = NULL_TREE;
 423   tree new_binfo = NULL_TREE;
 424   int via_virtual;
 425   int watch_access = protect;
 426
 427   /* Should we be completing types here?  */
 428   if (TREE_CODE (parent) != TREE_VEC)
 429     parent = complete_type (TYPE_MAIN_VARIANT (parent));
 430   else
 431     complete_type (TREE_TYPE (parent));
 432
 433   if (TREE_CODE (binfo) == TREE_VEC)
 434     type = BINFO_TYPE (binfo);
 435   else if (IS_AGGR_TYPE_CODE (TREE_CODE (binfo)))
 436     {
 437       type = complete_type (binfo);
 438       binfo = TYPE_BINFO (type);
 439
 440       if (path_ptr)
 441         my_friendly_assert (BINFO_INHERITANCE_CHAIN (binfo) == NULL_TREE,
 442                             980827);
 443     }
 444   else
 445     my_friendly_abort (92);
 446
 447   if (parent == type || parent == binfo)
 448     {
 449       /* If the distance is 0, then we don't really need
 450          a path pointer, but we shouldn't let garbage go back.  */
 451       if (path_ptr)
 452         *path_ptr = binfo;
 453       return 0;
 454     }
 455
 456   if (path_ptr && watch_access == 0)
 457     watch_access = 1;
 458
 459   rval = get_base_distance_recursive (binfo, 0, 0, -1,
 460                                       &rval_private, &new_binfo, parent,
 461                                       watch_access, &via_virtual, 0,
 462                                       0);
 463
 464   /* Access restrictions don't count if we found an ambiguous basetype.  */
 465   if (rval == -2 && protect >= 0)
 466     rval_private = 0;
 467
 468   if (rval && protect && rval_private)
 469     return -3;
 470
 471   if (path_ptr)
 472     *path_ptr = new_binfo;
 473   return rval;
 474 }
 475
 476 /* Worker function for get_dynamic_cast_base_type.  */
 477
 478 static int
 479 dynamic_cast_base_recurse (subtype, binfo, via_virtual, offset_ptr)
 480      tree subtype;
 481      tree binfo;
 482      int via_virtual;
 483      tree *offset_ptr;
 484 {
 485   tree binfos;
 486   int i, n_baselinks;
 487   int worst = -2;
 488
 489   if (BINFO_TYPE (binfo) == subtype)
 490     {
 491       if (via_virtual)
 492         return -1;
 493       else
 494         {
 495           *offset_ptr = BINFO_OFFSET (binfo);
 496           return 0;
 497         }
 498     }
 499
 500   binfos = BINFO_BASETYPES (binfo);
 501   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 502   for (i = 0; i < n_baselinks; i++)
 503     {
 504       tree base_binfo = TREE_VEC_ELT (binfos, i);
 505       int rval;
 506
 507       if (!TREE_VIA_PUBLIC (base_binfo))
 508         continue;
 509       rval = dynamic_cast_base_recurse
 510              (subtype, base_binfo,
 511               via_virtual || TREE_VIA_VIRTUAL (base_binfo), offset_ptr);
 512       if (worst == -2)
 513         worst = rval;
 514       else if (rval >= 0)
 515         worst = worst >= 0 ? -3 : worst;
 516       else if (rval == -1)
 517         worst = -1;
 518       else if (rval == -3 && worst != -1)
 519         worst = -3;
 520     }
 521   return worst;
 522 }
 523
 524 /* The dynamic cast runtime needs a hint about how the static SUBTYPE type
 525    started from is related to the required TARGET type, in order to optimize
 526    the inheritance graph search. This information is independant of the
 527    current context, and ignores private paths, hence get_base_distance is
 528    inappropriate. Return a TREE specifying the base offset, BOFF.
 529    BOFF >= 0, there is only one public non-virtual SUBTYPE base at offset BOFF,
 530       and there are no public virtual SUBTYPE bases.
 531    BOFF == -1, SUBTYPE occurs as multiple public virtual or non-virtual bases.
 532    BOFF == -2, SUBTYPE is not a public base.
 533    BOFF == -3, SUBTYPE occurs as multiple public non-virtual bases.  */
 534
 535 tree
 536 get_dynamic_cast_base_type (subtype, target)
 537      tree subtype;
 538      tree target;
 539 {
 540   tree offset = NULL_TREE;
 541   int boff = dynamic_cast_base_recurse (subtype, TYPE_BINFO (target),
 542                                         0, &offset);
 543
 544   if (!boff)
 545     return offset;
 546   offset = build_int_2 (boff, -1);
 547   TREE_TYPE (offset) = ssizetype;
 548   return offset;
 549 }
 550
 551 /* Search for a member with name NAME in a multiple inheritance lattice
 552    specified by TYPE.  If it does not exist, return NULL_TREE.
 553    If the member is ambiguously referenced, return `error_mark_node'.
 554    Otherwise, return the FIELD_DECL.  */
 555
 556 /* Do a 1-level search for NAME as a member of TYPE.  The caller must
 557    figure out whether it can access this field.  (Since it is only one
 558    level, this is reasonable.)  */
 559
 560 static tree
 561 lookup_field_1 (type, name)
 562      tree type, name;
 563 {
 564   register tree field;
 565
 566   if (TREE_CODE (type) == TEMPLATE_TYPE_PARM
 567       || TREE_CODE (type) == BOUND_TEMPLATE_TEMPLATE_PARM)
 568     /* The TYPE_FIELDS of a TEMPLATE_TYPE_PARM are not fields at all;
 569        instead TYPE_FIELDS is the TEMPLATE_PARM_INDEX.  (Miraculously,
 570        the code often worked even when we treated the index as a list
 571        of fields!)  */
 572     return NULL_TREE;
 573
 574   if (TYPE_NAME (type)
 575       && DECL_LANG_SPECIFIC (TYPE_NAME (type))
 576       && DECL_SORTED_FIELDS (TYPE_NAME (type)))
 577     {
 578       tree *fields = &TREE_VEC_ELT (DECL_SORTED_FIELDS (TYPE_NAME (type)), 0);
 579       int lo = 0, hi = TREE_VEC_LENGTH (DECL_SORTED_FIELDS (TYPE_NAME (type)));
 580       int i;
 581
 582       while (lo < hi)
 583         {
 584           i = (lo + hi) / 2;
 585
 586 #ifdef GATHER_STATISTICS
 587           n_fields_searched++;
 588 #endif /* GATHER_STATISTICS */
 589
 590           if (DECL_NAME (fields[i]) > name)
 591             hi = i;
 592           else if (DECL_NAME (fields[i]) < name)
 593             lo = i + 1;
 594           else
 595             {
 596               /* We might have a nested class and a field with the
 597                  same name; we sorted them appropriately via
 598                  field_decl_cmp, so just look for the last field with
 599                  this name.  */
 600               while (i + 1 < hi
 601                      && DECL_NAME (fields[i+1]) == name)
 602                 ++i;
 603               return fields[i];
 604             }
 605         }
 606       return NULL_TREE;
 607     }
 608
 609   field = TYPE_FIELDS (type);
 610
 611 #ifdef GATHER_STATISTICS
 612   n_calls_lookup_field_1++;
 613 #endif /* GATHER_STATISTICS */
 614   while (field)
 615     {
 616 #ifdef GATHER_STATISTICS
 617       n_fields_searched++;
 618 #endif /* GATHER_STATISTICS */
 619       my_friendly_assert (DECL_P (field), 0);
 620       if (DECL_NAME (field) == NULL_TREE
 621           && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
 622         {
 623           tree temp = lookup_field_1 (TREE_TYPE (field), name);
 624           if (temp)
 625             return temp;
 626         }
 627       if (TREE_CODE (field) == USING_DECL
 628           && !(CLASSTYPE_TEMPLATE_INFO (type)
 629                && uses_template_parms (type)))
 630         /* For now, we're just treating member using declarations as
 631            old ARM-style access declarations.  Thus, there's no reason
 632            to return a USING_DECL, and the rest of the compiler can't
 633            handle it.  Once the class is defined, these are purged
 634            from TYPE_FIELDS anyhow; see handle_using_decl.
 635
 636            Inside a template class, however, we have to return the
 637            USING_DECL because otherwise:
 638
 639              struct A { int i; };
 640              template <typename T> struct B : public A {};
 641              template <typename T> struct C : public B<T> {
 642                using B<T>::i;
 643                void f() { i = 3; }
 644              };
 645
 646            does not work -- there is no `i' in scope when `C<T>::f' is
 647            parsed.  */
 648         ;
 649       else if (DECL_NAME (field) == name)
 650         {
 651           if (TREE_CODE(field) == VAR_DECL
 652               && (TREE_STATIC (field) || DECL_EXTERNAL (field)))
 653             GNU_xref_ref(current_function_decl,
 654                          IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (field)));
 655           return field;
 656         }
 657       field = TREE_CHAIN (field);
 658     }
 659   /* Not found.  */
 660   if (name == vptr_identifier)
 661     {
 662       /* Give the user what s/he thinks s/he wants.  */
 663       if (TYPE_POLYMORPHIC_P (type))
 664         return TYPE_VFIELD (type);
 665     }
 666   return NULL_TREE;
 667 }
 668
 669 /* There are a number of cases we need to be aware of here:
 670                          current_class_type     current_function_decl
 671      global                     NULL                    NULL
 672      fn-local                   NULL                    SET
 673      class-local                SET                     NULL
 674      class->fn                  SET                     SET
 675      fn->class                  SET                     SET
 676
 677    Those last two make life interesting.  If we're in a function which is
 678    itself inside a class, we need decls to go into the fn's decls (our
 679    second case below).  But if we're in a class and the class itself is
 680    inside a function, we need decls to go into the decls for the class.  To
 681    achieve this last goal, we must see if, when both current_class_ptr and
 682    current_function_decl are set, the class was declared inside that
 683    function.  If so, we know to put the decls into the class's scope.  */
 684
 685 tree
 686 current_scope ()
 687 {
 688   if (current_function_decl == NULL_TREE)
 689     return current_class_type;
 690   if (current_class_type == NULL_TREE)
 691     return current_function_decl;
 692   if ((DECL_FUNCTION_MEMBER_P (current_function_decl)
 693        && same_type_p (DECL_CONTEXT (current_function_decl),
 694                        current_class_type))
 695       || (DECL_FRIEND_CONTEXT (current_function_decl)
 696           && same_type_p (DECL_FRIEND_CONTEXT (current_function_decl),
 697                           current_class_type)))
 698     return current_function_decl;
 699
 700   return current_class_type;
 701 }
 702
 703 /* Returns non-zero if we are currently in a function scope.  Note
 704    that this function returns zero if we are within a local class, but
 705    not within a member function body of the local class.  */
 706
 707 bool
 708 at_function_scope_p ()
 709 {
 710   tree cs = current_scope ();
 711   return cs && TREE_CODE (cs) == FUNCTION_DECL;
 712 }
 713
 714 /* Returns true if we are currently in a class-scope.  */
 715
 716 bool
 717 at_class_scope_p ()
 718 {
 719   tree cs = current_scope ();
 720   return cs && TYPE_P (cs);
 721 }
 722
 723 /* Return the scope of DECL, as appropriate when doing name-lookup.  */
 724
 725 tree
 726 context_for_name_lookup (decl)
 727      tree decl;
 728 {
 729   /* [class.union]
 730
 731      For the purposes of name lookup, after the anonymous union
 732      definition, the members of the anonymous union are considered to
 733      have been defined in the scope in which the anonymous union is
 734      declared.  */
 735   tree context = DECL_CONTEXT (decl);
 736
 737   while (context && TYPE_P (context) && ANON_AGGR_TYPE_P (context))
 738     context = TYPE_CONTEXT (context);
 739   if (!context)
 740     context = global_namespace;
 741
 742   return context;
 743 }
 744
 745 /* Return a canonical BINFO if BINFO is a virtual base, or just BINFO
 746    otherwise.  */
 747
 748 static tree
 749 canonical_binfo (binfo)
 750      tree binfo;
 751 {
 752   return (TREE_VIA_VIRTUAL (binfo)
 753           ? TYPE_BINFO (BINFO_TYPE (binfo)) : binfo);
 754 }
 755
 756 /* A queue function that simply ensures that we walk into the
 757    canonical versions of virtual bases.  */
 758
 759 static tree
 760 dfs_canonical_queue (binfo, data)
 761      tree binfo;
 762      void *data ATTRIBUTE_UNUSED;
 763 {
 764   return canonical_binfo (binfo);
 765 }
 766
 767 /* Called via dfs_walk from assert_canonical_unmarked.  */
 768
 769 static tree
 770 dfs_assert_unmarked_p (binfo, data)
 771      tree binfo;
 772      void *data ATTRIBUTE_UNUSED;
 773 {
 774   my_friendly_assert (!BINFO_MARKED (binfo), 0);
 775   return NULL_TREE;
 776 }
 777
 778 /* Asserts that all the nodes below BINFO (using the canonical
 779    versions of virtual bases) are unmarked.  */
 780
 781 static void
 782 assert_canonical_unmarked (binfo)
 783      tree binfo;
 784 {
 785   dfs_walk (binfo, dfs_assert_unmarked_p, dfs_canonical_queue, 0);
 786 }
 787
 788 /* If BINFO is marked, return a canonical version of BINFO.
 789    Otherwise, return NULL_TREE.  */
 790
 791 static tree
 792 shared_marked_p (binfo, data)
 793      tree binfo;
 794      void *data;
 795 {
 796   binfo = canonical_binfo (binfo);
 797   return markedp (binfo, data);
 798 }
 799
 800 /* If BINFO is not marked, return a canonical version of BINFO.
 801    Otherwise, return NULL_TREE.  */
 802
 803 static tree
 804 shared_unmarked_p (binfo, data)
 805      tree binfo;
 806      void *data;
 807 {
 808   binfo = canonical_binfo (binfo);
 809   return unmarkedp (binfo, data);
 810 }
 811
 812 /* The accessibility routines use BINFO_ACCESS for scratch space
 813    during the computation of the accssibility of some declaration.  */
 814
 815 #define BINFO_ACCESS(NODE) \
 816   ((access_kind) ((TREE_LANG_FLAG_1 (NODE) << 1) | TREE_LANG_FLAG_6 (NODE)))
 817
 818 /* Set the access associated with NODE to ACCESS.  */
 819
 820 #define SET_BINFO_ACCESS(NODE, ACCESS)                  \
 821   ((TREE_LANG_FLAG_1 (NODE) = (ACCESS & 2) != 0),       \
 822    (TREE_LANG_FLAG_6 (NODE) = (ACCESS & 1) != 0))
 823
 824 /* Called from access_in_type via dfs_walk.  Calculate the access to
 825    DATA (which is really a DECL) in BINFO.  */
 826
 827 static tree
 828 dfs_access_in_type (binfo, data)
 829      tree binfo;
 830      void *data;
 831 {
 832   tree decl = (tree) data;
 833   tree type = BINFO_TYPE (binfo);
 834   access_kind access = ak_none;
 835
 836   if (context_for_name_lookup (decl) == type)
 837     {
 838       /* If we have desceneded to the scope of DECL, just note the
 839          appropriate access.  */
 840       if (TREE_PRIVATE (decl))
 841         access = ak_private;
 842       else if (TREE_PROTECTED (decl))
 843         access = ak_protected;
 844       else
 845         access = ak_public;
 846     }
 847   else
 848     {
 849       /* First, check for an access-declaration that gives us more
 850          access to the DECL.  The CONST_DECL for an enumeration
 851          constant will not have DECL_LANG_SPECIFIC, and thus no
 852          DECL_ACCESS.  */
 853       if (DECL_LANG_SPECIFIC (decl) && !DECL_DISCRIMINATOR_P (decl))
 854         {
 855           tree decl_access = purpose_member (type, DECL_ACCESS (decl));
 856           if (decl_access)
 857             access = ((access_kind)
 858                       TREE_INT_CST_LOW (TREE_VALUE (decl_access)));
 859         }
 860
 861       if (!access)
 862         {
 863           int i;
 864           int n_baselinks;
 865           tree binfos;
 866
 867           /* Otherwise, scan our baseclasses, and pick the most favorable
 868              access.  */
 869           binfos = BINFO_BASETYPES (binfo);
 870           n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
 871           for (i = 0; i < n_baselinks; ++i)
 872             {
 873               tree base_binfo = TREE_VEC_ELT (binfos, i);
 874               access_kind base_access
 875                 = BINFO_ACCESS (canonical_binfo (base_binfo));
 876
 877               if (base_access == ak_none || base_access == ak_private)
 878                 /* If it was not accessible in the base, or only
 879                    accessible as a private member, we can't access it
 880                    all.  */
 881                 base_access = ak_none;
 882               else if (TREE_VIA_PROTECTED (base_binfo))
 883                 /* Public and protected members in the base are
 884                    protected here.  */
 885                 base_access = ak_protected;
 886               else if (!TREE_VIA_PUBLIC (base_binfo))
 887                 /* Public and protected members in the base are
 888                    private here.  */
 889                 base_access = ak_private;
 890
 891               /* See if the new access, via this base, gives more
 892                  access than our previous best access.  */
 893               if (base_access != ak_none
 894                   && (base_access == ak_public
 895                       || (base_access == ak_protected
 896                           && access != ak_public)
 897                       || (base_access == ak_private
 898                           && access == ak_none)))
 899                 {
 900                   access = base_access;
 901
 902                   /* If the new access is public, we can't do better.  */
 903                   if (access == ak_public)
 904                     break;
 905                 }
 906             }
 907         }
 908     }
 909
 910   /* Note the access to DECL in TYPE.  */
 911   SET_BINFO_ACCESS (binfo, access);
 912
 913   /* Mark TYPE as visited so that if we reach it again we do not
 914      duplicate our efforts here.  */
 915   SET_BINFO_MARKED (binfo);
 916
 917   return NULL_TREE;
 918 }
 919
 920 /* Return the access to DECL in TYPE.  */
 921
 922 static access_kind
 923 access_in_type (type, decl)
 924      tree type;
 925      tree decl;
 926 {
 927   tree binfo = TYPE_BINFO (type);
 928
 929   /* We must take into account
 930
 931        [class.paths]
 932
 933        If a name can be reached by several paths through a multiple
 934        inheritance graph, the access is that of the path that gives
 935        most access.
 936
 937     The algorithm we use is to make a post-order depth-first traversal
 938     of the base-class hierarchy.  As we come up the tree, we annotate
 939     each node with the most lenient access.  */
 940   dfs_walk_real (binfo, 0, dfs_access_in_type, shared_unmarked_p, decl);
 941   dfs_walk (binfo, dfs_unmark, shared_marked_p,  0);
 942   assert_canonical_unmarked (binfo);
 943
 944   return BINFO_ACCESS (binfo);
 945 }
 946
 947 /* Called from dfs_accessible_p via dfs_walk.  */
 948
 949 static tree
 950 dfs_accessible_queue_p (binfo, data)
 951      tree binfo;
 952      void *data ATTRIBUTE_UNUSED;
 953 {
 954   if (BINFO_MARKED (binfo))
 955     return NULL_TREE;
 956
 957   /* If this class is inherited via private or protected inheritance,
 958      then we can't see it, unless we are a friend of the subclass.  */
 959   if (!TREE_VIA_PUBLIC (binfo)
 960       && !is_friend (BINFO_TYPE (BINFO_INHERITANCE_CHAIN (binfo)),
 961                      current_scope ()))
 962     return NULL_TREE;
 963
 964   return canonical_binfo (binfo);
 965 }
 966
 967 /* Called from dfs_accessible_p via dfs_walk.  */
 968
 969 static tree
 970 dfs_accessible_p (binfo, data)
 971      tree binfo;
 972      void *data;
 973 {
 974   int protected_ok = data != 0;
 975   access_kind access;
 976
 977   SET_BINFO_MARKED (binfo);
 978   access = BINFO_ACCESS (binfo);
 979   if (access == ak_public || (access == ak_protected && protected_ok))
 980     return binfo;
 981   else if (access != ak_none
 982            && is_friend (BINFO_TYPE (binfo), current_scope ()))
 983     return binfo;
 984
 985   return NULL_TREE;
 986 }
 987
 988 /* Returns non-zero if it is OK to access DECL through an object
 989    indiated by BINFO in the context of DERIVED.  */
 990
 991 static int
 992 protected_accessible_p (decl, derived, binfo)
 993      tree decl;
 994      tree derived;
 995      tree binfo;
 996 {
 997   access_kind access;
 998
 999   /* We're checking this clause from [class.access.base]
1000
1001        m as a member of N is protected, and the reference occurs in a
1002        member or friend of class N, or in a member or friend of a
1003        class P derived from N, where m as a member of P is private or
1004        protected.
1005
1006     Here DERIVED is a possible P and DECL is m.  accessible_p will
1007     iterate over various values of N, but the access to m in DERIVED
1008     does not change.
1009
1010     Note that I believe that the passage above is wrong, and should read
1011     "...is private or protected or public"; otherwise you get bizarre results
1012     whereby a public using-decl can prevent you from accessing a protected
1013     member of a base.  (jason 2000/02/28)  */
1014
1015   /* If DERIVED isn't derived from m's class, then it can't be a P.  */
1016   if (!DERIVED_FROM_P (context_for_name_lookup (decl), derived))
1017     return 0;
1018
1019   access = access_in_type (derived, decl);
1020
1021   /* If m is inaccessible in DERIVED, then it's not a P.  */
1022   if (access == ak_none)
1023     return 0;
1024
1025   /* [class.protected]
1026
1027      When a friend or a member function of a derived class references
1028      a protected nonstatic member of a base class, an access check
1029      applies in addition to those described earlier in clause
1030      _class.access_) Except when forming a pointer to member
1031      (_expr.unary.op_), the access must be through a pointer to,
1032      reference to, or object of the derived class itself (or any class
1033      derived from that class) (_expr.ref_).  If the access is to form
1034      a pointer to member, the nested-name-specifier shall name the
1035      derived class (or any class derived from that class).  */
1036   if (DECL_NONSTATIC_MEMBER_P (decl))
1037     {
1038       /* We can tell through what the reference is occurring by
1039          chasing BINFO up to the root.  */
1040       tree t = binfo;
1041       while (BINFO_INHERITANCE_CHAIN (t))
1042         t = BINFO_INHERITANCE_CHAIN (t);
1043
1044       if (!DERIVED_FROM_P (derived, BINFO_TYPE (t)))
1045         return 0;
1046     }
1047
1048   return 1;
1049 }
1050
1051 /* Returns non-zero if SCOPE is a friend of a type which would be able
1052    to access DECL through the object indicated by BINFO.  */
1053
1054 static int
1055 friend_accessible_p (scope, decl, binfo)
1056      tree scope;
1057      tree decl;
1058      tree binfo;
1059 {
1060   tree befriending_classes;
1061   tree t;
1062
1063   if (!scope)
1064     return 0;
1065
1066   if (TREE_CODE (scope) == FUNCTION_DECL
1067       || DECL_FUNCTION_TEMPLATE_P (scope))
1068     befriending_classes = DECL_BEFRIENDING_CLASSES (scope);
1069   else if (TYPE_P (scope))
1070     befriending_classes = CLASSTYPE_BEFRIENDING_CLASSES (scope);
1071   else
1072     return 0;
1073
1074   for (t = befriending_classes; t; t = TREE_CHAIN (t))
1075     if (protected_accessible_p (decl, TREE_VALUE (t), binfo))
1076       return 1;
1077
1078   /* Nested classes are implicitly friends of their enclosing types, as
1079      per core issue 45 (this is a change from the standard).  */
1080   if (TYPE_P (scope))
1081     for (t = TYPE_CONTEXT (scope); t && TYPE_P (t); t = TYPE_CONTEXT (t))
1082       if (protected_accessible_p (decl, t, binfo))
1083         return 1;
1084
1085   if (TREE_CODE (scope) == FUNCTION_DECL
1086       || DECL_FUNCTION_TEMPLATE_P (scope))
1087     {
1088       /* Perhaps this SCOPE is a member of a class which is a
1089          friend.  */
1090       if (DECL_CLASS_SCOPE_P (decl)
1091           && friend_accessible_p (DECL_CONTEXT (scope), decl, binfo))
1092         return 1;
1093
1094       /* Or an instantiation of something which is a friend.  */
1095       if (DECL_TEMPLATE_INFO (scope))
1096         return friend_accessible_p (DECL_TI_TEMPLATE (scope), decl, binfo);
1097     }
1098   else if (CLASSTYPE_TEMPLATE_INFO (scope))
1099     return friend_accessible_p (CLASSTYPE_TI_TEMPLATE (scope), decl, binfo);
1100
1101   return 0;
1102 }
1103
1104 /* DECL is a declaration from a base class of TYPE, which was the
1105    class used to name DECL.  Return non-zero if, in the current
1106    context, DECL is accessible.  If TYPE is actually a BINFO node,
1107    then we can tell in what context the access is occurring by looking
1108    at the most derived class along the path indicated by BINFO.  */
1109
1110 int
1111 accessible_p (type, decl)
1112      tree type;
1113      tree decl;
1114
1115 {
1116   tree binfo;
1117   tree t;
1118
1119   /* Non-zero if it's OK to access DECL if it has protected
1120      accessibility in TYPE.  */
1121   int protected_ok = 0;
1122
1123   /* If we're not checking access, everything is accessible.  */
1124   if (!flag_access_control)
1125     return 1;
1126
1127   /* If this declaration is in a block or namespace scope, there's no
1128      access control.  */
1129   if (!TYPE_P (context_for_name_lookup (decl)))
1130     return 1;
1131
1132   if (!TYPE_P (type))
1133     {
1134       binfo = type;
1135       type = BINFO_TYPE (type);
1136     }
1137   else
1138     binfo = TYPE_BINFO (type);
1139
1140   /* [class.access.base]
1141
1142      A member m is accessible when named in class N if
1143
1144      --m as a member of N is public, or
1145
1146      --m as a member of N is private, and the reference occurs in a
1147        member or friend of class N, or
1148
1149      --m as a member of N is protected, and the reference occurs in a
1150        member or friend of class N, or in a member or friend of a
1151        class P derived from N, where m as a member of P is private or
1152        protected, or
1153
1154      --there exists a base class B of N that is accessible at the point
1155        of reference, and m is accessible when named in class B.
1156
1157     We walk the base class hierarchy, checking these conditions.  */
1158
1159   /* Figure out where the reference is occurring.  Check to see if
1160      DECL is private or protected in this scope, since that will
1161      determine whether protected access is allowed.  */
1162   if (current_class_type)
1163     protected_ok = protected_accessible_p (decl, current_class_type, binfo);
1164
1165   /* Now, loop through the classes of which we are a friend.  */
1166   if (!protected_ok)
1167     protected_ok = friend_accessible_p (current_scope (), decl, binfo);
1168
1169   /* Standardize the binfo that access_in_type will use.  We don't
1170      need to know what path was chosen from this point onwards.  */
1171   binfo = TYPE_BINFO (type);
1172
1173   /* Compute the accessibility of DECL in the class hierarchy
1174      dominated by type.  */
1175   access_in_type (type, decl);
1176   /* Walk the hierarchy again, looking for a base class that allows
1177      access.  */
1178   t = dfs_walk (binfo, dfs_accessible_p,
1179                 dfs_accessible_queue_p,
1180                 protected_ok ? &protected_ok : 0);
1181   /* Clear any mark bits.  Note that we have to walk the whole tree
1182      here, since we have aborted the previous walk from some point
1183      deep in the tree.  */
1184   dfs_walk (binfo, dfs_unmark, dfs_canonical_queue,  0);
1185   assert_canonical_unmarked (binfo);
1186
1187   return t != NULL_TREE;
1188 }
1189
1190 /* Returns the scope through which DECL is being accessed, or
1191    NULL_TREE if DECL is not a member.  If OBJECT_TYPE is non-NULL, we
1192    have just seen `x->' or `x.' and OBJECT_TYPE is the type of `*x',
1193    or `x', respectively.  If the DECL was named as `A::B' then
1194    NESTED_NAME_SPECIFIER is `A'.  */
1195
1196 tree
1197 determine_scope_through_which_access_occurs (decl,
1198                                              object_type,
1199                                              nested_name_specifier)
1200      tree decl;
1201      tree object_type;
1202      tree nested_name_specifier;
1203 {
1204   tree scope;
1205   tree qualifying_type = NULL_TREE;
1206
1207   /* Determine the SCOPE of DECL.  */
1208   scope = context_for_name_lookup (decl);
1209   /* If the SCOPE is not a type, then DECL is not a member.  */
1210   if (!TYPE_P (scope))
1211     return NULL_TREE;
1212   /* Figure out the type through which DECL is being accessed.  If we
1213      are processing a `->' or `.' expression, use the type of the
1214      left-hand side.  */
1215   if (object_type && DERIVED_FROM_P (scope, object_type))
1216     qualifying_type = object_type;
1217   /* Perhaps we are implicitly accessing the DECL because we are in a
1218      class derived from SCOPE.  */
1219   if (!qualifying_type && current_class_type)
1220     qualifying_type
1221       = currently_open_derived_class (scope);
1222   /* Otherwise, we are accessing the DECL via an explicit qualifying
1223      scope.  */
1224   if (!qualifying_type)
1225     qualifying_type = nested_name_specifier;
1226
1227   return qualifying_type;
1228 }
1229
1230 /* Routine to see if the sub-object denoted by the binfo PARENT can be
1231    found as a base class and sub-object of the object denoted by
1232    BINFO.  MOST_DERIVED is the most derived type of the hierarchy being
1233    searched.  */
1234
1235 static int
1236 is_subobject_of_p (parent, binfo, most_derived)
1237      tree parent, binfo, most_derived;
1238 {
1239   tree binfos;
1240   int i, n_baselinks;
1241
1242   if (parent == binfo)
1243     return 1;
1244
1245   binfos = BINFO_BASETYPES (binfo);
1246   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
1247
1248   /* Iterate the 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,
1258                              CANONICAL_BINFO (base_binfo, most_derived),
1259                              most_derived))
1260         return 1;
1261     }
1262   return 0;
1263 }
1264
1265 struct lookup_field_info {
1266   /* The type in which we're looking.  */
1267   tree type;
1268   /* The name of the field for which we're looking.  */
1269   tree name;
1270   /* If non-NULL, the current result of the lookup.  */
1271   tree rval;
1272   /* The path to RVAL.  */
1273   tree rval_binfo;
1274   /* If non-NULL, the lookup was ambiguous, and this is a list of the
1275      candidates.  */
1276   tree ambiguous;
1277   /* If non-zero, we are looking for types, not data members.  */
1278   int want_type;
1279   /* If non-zero, RVAL was found by looking through a dependent base.  */
1280   int from_dep_base_p;
1281   /* If something went wrong, a message indicating what.  */
1282   const char *errstr;
1283 };
1284
1285 /* Returns non-zero if BINFO is not hidden by the value found by the
1286    lookup so far.  If BINFO is hidden, then there's no need to look in
1287    it.  DATA is really a struct lookup_field_info.  Called from
1288    lookup_field via breadth_first_search.  */
1289
1290 static tree
1291 lookup_field_queue_p (binfo, data)
1292      tree binfo;
1293      void *data;
1294 {
1295   struct lookup_field_info *lfi = (struct lookup_field_info *) data;
1296
1297   /* Don't look for constructors or destructors in base classes.  */
1298   if (IDENTIFIER_CTOR_OR_DTOR_P (lfi->name))
1299     return NULL_TREE;
1300
1301   /* If this base class is hidden by the best-known value so far, we
1302      don't need to look.  */
1303   if (!lfi->from_dep_base_p && lfi->rval_binfo
1304       && is_subobject_of_p (binfo, lfi->rval_binfo, lfi->type))
1305     return NULL_TREE;
1306
1307   return CANONICAL_BINFO (binfo, lfi->type);
1308 }
1309
1310 /* Within the scope of a template class, you can refer to the to the
1311    current specialization with the name of the template itself.  For
1312    example:
1313
1314      template <typename T> struct S { S* sp; }
1315
1316    Returns non-zero if DECL is such a declaration in a class TYPE.  */
1317
1318 static int
1319 template_self_reference_p (type, decl)
1320      tree type;
1321      tree decl;
1322 {
1323   return  (CLASSTYPE_USE_TEMPLATE (type)
1324            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (type))
1325            && TREE_CODE (decl) == TYPE_DECL
1326            && DECL_ARTIFICIAL (decl)
1327            && DECL_NAME (decl) == constructor_name (type));
1328 }
1329
1330
1331 /* Nonzero for a class member means that it is shared between all objects
1332    of that class.
1333
1334    [class.member.lookup]:If the resulting set of declarations are not all
1335    from sub-objects of the same type, or the set has a  nonstatic  member
1336    and  includes members from distinct sub-objects, there is an ambiguity
1337    and the program is ill-formed.
1338
1339    This function checks that T contains no nonstatic members.  */
1340
1341 static int
1342 shared_member_p (t)
1343      tree t;
1344 {
1345   if (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == TYPE_DECL \
1346       || TREE_CODE (t) == CONST_DECL)
1347     return 1;
1348   if (is_overloaded_fn (t))
1349     {
1350       for (; t; t = OVL_NEXT (t))
1351         {
1352           tree fn = OVL_CURRENT (t);
1353           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn))
1354             return 0;
1355         }
1356       return 1;
1357     }
1358   return 0;
1359 }
1360
1361 /* DATA is really a struct lookup_field_info.  Look for a field with
1362    the name indicated there in BINFO.  If this function returns a
1363    non-NULL value it is the result of the lookup.  Called from
1364    lookup_field via breadth_first_search.  */
1365
1366 static tree
1367 lookup_field_r (binfo, data)
1368      tree binfo;
1369      void *data;
1370 {
1371   struct lookup_field_info *lfi = (struct lookup_field_info *) data;
1372   tree type = BINFO_TYPE (binfo);
1373   tree nval = NULL_TREE;
1374   int from_dep_base_p;
1375
1376   /* First, look for a function.  There can't be a function and a data
1377      member with the same name, and if there's a function and a type
1378      with the same name, the type is hidden by the function.  */
1379   if (!lfi->want_type)
1380     {
1381       int idx = lookup_fnfields_1 (type, lfi->name);
1382       if (idx >= 0)
1383         nval = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), idx);
1384     }
1385
1386   if (!nval)
1387     /* Look for a data member or type.  */
1388     nval = lookup_field_1 (type, lfi->name);
1389
1390   /* If there is no declaration with the indicated name in this type,
1391      then there's nothing to do.  */
1392   if (!nval)
1393     return NULL_TREE;
1394
1395   /* If we're looking up a type (as with an elaborated type specifier)
1396      we ignore all non-types we find.  */
1397   if (lfi->want_type && TREE_CODE (nval) != TYPE_DECL)
1398     {
1399       if (lfi->name == TYPE_IDENTIFIER (type))
1400         {
1401           /* If the aggregate has no user defined constructors, we allow
1402              it to have fields with the same name as the enclosing type.
1403              If we are looking for that name, find the corresponding
1404              TYPE_DECL.  */
1405           for (nval = TREE_CHAIN (nval); nval; nval = TREE_CHAIN (nval))
1406             if (DECL_NAME (nval) == lfi->name
1407                 && TREE_CODE (nval) == TYPE_DECL)
1408               break;
1409         }
1410       else
1411         nval = NULL_TREE;
1412       if (!nval)
1413         {
1414           nval = purpose_member (lfi->name, CLASSTYPE_TAGS (type));
1415           if (nval)
1416             nval = TYPE_MAIN_DECL (TREE_VALUE (nval));
1417           else
1418             return NULL_TREE;
1419         }
1420     }
1421
1422   /* You must name a template base class with a template-id.  */
1423   if (!same_type_p (type, lfi->type)
1424       && template_self_reference_p (type, nval))
1425     return NULL_TREE;
1426
1427   from_dep_base_p = dependent_base_p (binfo);
1428   if (lfi->from_dep_base_p && !from_dep_base_p)
1429     {
1430       /* If the new declaration is not found via a dependent base, and
1431          the old one was, then we must prefer the new one.  We weren't
1432          really supposed to be able to find the old one, so we don't
1433          want to be affected by a specialization.  Consider:
1434
1435            struct B { typedef int I; };
1436            template <typename T> struct D1 : virtual public B {};
1437            template <typename T> struct D :
1438            public D1, virtual pubic B { I i; };
1439
1440          The `I' in `D<T>' is unambigousuly `B::I', regardless of how
1441          D1 is specialized.  */
1442       lfi->from_dep_base_p = 0;
1443       lfi->rval = NULL_TREE;
1444       lfi->rval_binfo = NULL_TREE;
1445       lfi->ambiguous = NULL_TREE;
1446       lfi->errstr = 0;
1447     }
1448   else if (lfi->rval_binfo && !lfi->from_dep_base_p && from_dep_base_p)
1449     /* Similarly, if the old declaration was not found via a dependent
1450        base, and the new one is, ignore the new one.  */
1451     return NULL_TREE;
1452
1453   /* If the lookup already found a match, and the new value doesn't
1454      hide the old one, we might have an ambiguity.  */
1455   if (lfi->rval_binfo && !is_subobject_of_p (lfi->rval_binfo, binfo, lfi->type))
1456     {
1457       if (nval == lfi->rval && shared_member_p (nval))
1458         /* The two things are really the same.  */
1459         ;
1460       else if (is_subobject_of_p (binfo, lfi->rval_binfo, lfi->type))
1461         /* The previous value hides the new one.  */
1462         ;
1463       else
1464         {
1465           /* We have a real ambiguity.  We keep a chain of all the
1466              candidates.  */
1467           if (!lfi->ambiguous && lfi->rval)
1468             {
1469               /* This is the first time we noticed an ambiguity.  Add
1470                  what we previously thought was a reasonable candidate
1471                  to the list.  */
1472               lfi->ambiguous = tree_cons (NULL_TREE, lfi->rval, NULL_TREE);
1473               TREE_TYPE (lfi->ambiguous) = error_mark_node;
1474             }
1475
1476           /* Add the new value.  */
1477           lfi->ambiguous = tree_cons (NULL_TREE, nval, lfi->ambiguous);
1478           TREE_TYPE (lfi->ambiguous) = error_mark_node;
1479           lfi->errstr = "request for member `%D' is ambiguous";
1480         }
1481     }
1482   else
1483     {
1484       if (from_dep_base_p && TREE_CODE (nval) != TYPE_DECL
1485           /* We need to return a member template class so we can
1486              define partial specializations.  Is there a better
1487              way?  */
1488           && !DECL_CLASS_TEMPLATE_P (nval))
1489         /* The thing we're looking for isn't a type, so the implicit
1490            typename extension doesn't apply, so we just pretend we
1491            didn't find anything.  */
1492         return NULL_TREE;
1493
1494       lfi->rval = nval;
1495       lfi->from_dep_base_p = from_dep_base_p;
1496       lfi->rval_binfo = binfo;
1497     }
1498
1499   return NULL_TREE;
1500 }
1501
1502 /* Look for a member named NAME in an inheritance lattice dominated by
1503    XBASETYPE.  If PROTECT is 0 or two, we do not check access.  If it is
1504    1, we enforce accessibility.  If PROTECT is zero, then, for an
1505    ambiguous lookup, we return NULL.  If PROTECT is 1, we issue an
1506    error message.  If PROTECT is 2, we return a TREE_LIST whose
1507    TREE_TYPE is error_mark_node and whose TREE_VALUEs are the list of
1508    ambiguous candidates.
1509
1510    WANT_TYPE is 1 when we should only return TYPE_DECLs, if no
1511    TYPE_DECL can be found return NULL_TREE.  */
1512
1513 tree
1514 lookup_member (xbasetype, name, protect, want_type)
1515      register tree xbasetype, name;
1516      int protect, want_type;
1517 {
1518   tree rval, rval_binfo = NULL_TREE;
1519   tree type = NULL_TREE, basetype_path = NULL_TREE;
1520   struct lookup_field_info lfi;
1521
1522   /* rval_binfo is the binfo associated with the found member, note,
1523      this can be set with useful information, even when rval is not
1524      set, because it must deal with ALL members, not just non-function
1525      members.  It is used for ambiguity checking and the hidden
1526      checks.  Whereas rval is only set if a proper (not hidden)
1527      non-function member is found.  */
1528
1529   const char *errstr = 0;
1530
1531   if (xbasetype == current_class_type && TYPE_BEING_DEFINED (xbasetype)
1532       && IDENTIFIER_CLASS_VALUE (name))
1533     {
1534       tree field = IDENTIFIER_CLASS_VALUE (name);
1535       if (TREE_CODE (field) != FUNCTION_DECL
1536           && ! (want_type && TREE_CODE (field) != TYPE_DECL))
1537         /* We're in the scope of this class, and the value has already
1538            been looked up.  Just return the cached value.  */
1539         return field;
1540     }
1541
1542   if (TREE_CODE (xbasetype) == TREE_VEC)
1543     {
1544       type = BINFO_TYPE (xbasetype);
1545       basetype_path = xbasetype;
1546     }
1547   else if (IS_AGGR_TYPE_CODE (TREE_CODE (xbasetype)))
1548     {
1549       type = xbasetype;
1550       basetype_path = TYPE_BINFO (type);
1551       my_friendly_assert (BINFO_INHERITANCE_CHAIN (basetype_path) == NULL_TREE,
1552                           980827);
1553     }
1554   else
1555     my_friendly_abort (97);
1556
1557   complete_type (type);
1558
1559 #ifdef GATHER_STATISTICS
1560   n_calls_lookup_field++;
1561 #endif /* GATHER_STATISTICS */
1562
1563   memset ((PTR) &lfi, 0, sizeof (lfi));
1564   lfi.type = type;
1565   lfi.name = name;
1566   lfi.want_type = want_type;
1567   bfs_walk (basetype_path, &lookup_field_r, &lookup_field_queue_p, &lfi);
1568   rval = lfi.rval;
1569   rval_binfo = lfi.rval_binfo;
1570   if (rval_binfo)
1571     type = BINFO_TYPE (rval_binfo);
1572   errstr = lfi.errstr;
1573
1574   /* If we are not interested in ambiguities, don't report them;
1575      just return NULL_TREE.  */
1576   if (!protect && lfi.ambiguous)
1577     return NULL_TREE;
1578
1579   if (protect == 2)
1580     {
1581       if (lfi.ambiguous)
1582         return lfi.ambiguous;
1583       else
1584         protect = 0;
1585     }
1586
1587   if (errstr && protect)
1588     {
1589       cp_error (errstr, name, type);
1590       if (lfi.ambiguous)
1591         print_candidates (lfi.ambiguous);
1592       rval = error_mark_node;
1593     }
1594   /* FIXME: Avoid doing lookup in dependent bases in the first place.  */
1595   else if (lfi.from_dep_base_p && rval_binfo != basetype_path)
1596     rval = NULL_TREE;
1597
1598   /* FIXME: Remove this entirely.  */
1599 #if 0
1600   /* If the thing we found was found via the implicit typename
1601      extension, build the typename type.  */
1602   if (rval && lfi.from_dep_base_p && !DECL_CLASS_TEMPLATE_P (rval))
1603     rval = TYPE_STUB_DECL (build_typename_type (BINFO_TYPE (basetype_path),
1604                                                 name, name,
1605                                                 TREE_TYPE (rval)));
1606 #endif
1607
1608   if (rval && is_overloaded_fn (rval))
1609     rval = make_baselink (rval, rval_binfo, basetype_path,
1610                           (IDENTIFIER_TYPENAME_P (name)
1611                            ? TREE_TYPE (name) : NULL_TREE));
1612
1613   return rval;
1614 }
1615
1616 /* Like lookup_member, except that if we find a function member we
1617    return NULL_TREE.  */
1618
1619 tree
1620 lookup_field (xbasetype, name, protect, want_type)
1621      register tree xbasetype, name;
1622      int protect, want_type;
1623 {
1624   tree rval = lookup_member (xbasetype, name, protect, want_type);
1625
1626   /* Ignore functions.  */
1627   if (rval && TREE_CODE (rval) == TREE_LIST)
1628     return NULL_TREE;
1629
1630   return rval;
1631 }
1632
1633 /* Like lookup_member, except that if we find a non-function member we
1634    return NULL_TREE.  */
1635
1636 tree
1637 lookup_fnfields (xbasetype, name, protect)
1638      register tree xbasetype, name;
1639      int protect;
1640 {
1641   tree rval = lookup_member (xbasetype, name, protect, /*want_type=*/0);
1642
1643   /* Ignore non-functions.  */
1644   if (rval && !BASELINK_P (rval))
1645     return NULL_TREE;
1646
1647   return rval;
1648 }
1649
1650 /* TYPE is a class type. Return the index of the fields within
1651    the method vector with name NAME, or -1 is no such field exists.  */
1652
1653 int
1654 lookup_fnfields_1 (type, name)
1655      tree type, name;
1656 {
1657   tree method_vec
1658     = CLASS_TYPE_P (type) ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE;
1659
1660   if (method_vec != 0)
1661     {
1662       register int i;
1663       register tree *methods = &TREE_VEC_ELT (method_vec, 0);
1664       int len = TREE_VEC_LENGTH (method_vec);
1665       tree tmp;
1666
1667 #ifdef GATHER_STATISTICS
1668       n_calls_lookup_fnfields_1++;
1669 #endif /* GATHER_STATISTICS */
1670
1671       /* Constructors are first...  */
1672       if (name == ctor_identifier)
1673         return (methods[CLASSTYPE_CONSTRUCTOR_SLOT]
1674                 ? CLASSTYPE_CONSTRUCTOR_SLOT : -1);
1675       /* and destructors are second.  */
1676       if (name == dtor_identifier)
1677         return (methods[CLASSTYPE_DESTRUCTOR_SLOT]
1678                 ? CLASSTYPE_DESTRUCTOR_SLOT : -1);
1679
1680       for (i = CLASSTYPE_FIRST_CONVERSION_SLOT;
1681            i < len && methods[i];
1682            ++i)
1683         {
1684 #ifdef GATHER_STATISTICS
1685           n_outer_fields_searched++;
1686 #endif /* GATHER_STATISTICS */
1687
1688           tmp = OVL_CURRENT (methods[i]);
1689           if (DECL_NAME (tmp) == name)
1690             return i;
1691
1692           /* If the type is complete and we're past the conversion ops,
1693              switch to binary search.  */
1694           if (! DECL_CONV_FN_P (tmp)
1695               && COMPLETE_TYPE_P (type))
1696             {
1697               int lo = i + 1, hi = len;
1698
1699               while (lo < hi)
1700                 {
1701                   i = (lo + hi) / 2;
1702
1703 #ifdef GATHER_STATISTICS
1704                   n_outer_fields_searched++;
1705 #endif /* GATHER_STATISTICS */
1706
1707                   tmp = DECL_NAME (OVL_CURRENT (methods[i]));
1708
1709                   if (tmp > name)
1710                     hi = i;
1711                   else if (tmp < name)
1712                     lo = i + 1;
1713                   else
1714                     return i;
1715                 }
1716               break;
1717             }
1718         }
1719
1720       /* If we didn't find it, it might have been a template
1721          conversion operator.  (Note that we don't look for this case
1722          above so that we will always find specializations first.)  */
1723       if (IDENTIFIER_TYPENAME_P (name))
1724         {
1725           for (i = CLASSTYPE_FIRST_CONVERSION_SLOT;
1726                i < len && methods[i];
1727                ++i)
1728             {
1729               tmp = OVL_CURRENT (methods[i]);
1730               if (! DECL_CONV_FN_P (tmp))
1731                 {
1732                   /* Since all conversion operators come first, we know
1733                      there is no such operator.  */
1734                   break;
1735                 }
1736               else if (TREE_CODE (tmp) == TEMPLATE_DECL)
1737                 return i;
1738             }
1739         }
1740     }
1741
1742   return -1;
1743 }
1744 \f
1745 /* Walk the class hierarchy dominated by TYPE.  FN is called for each
1746    type in the hierarchy, in a breadth-first preorder traversal.  .
1747    If it ever returns a non-NULL value, that value is immediately
1748    returned and the walk is terminated.  At each node FN, is passed a
1749    BINFO indicating the path from the curently visited base-class to
1750    TYPE.  Before each base-class is walked QFN is called.  If the
1751    value returned is non-zero, the base-class is walked; otherwise it
1752    is not.  If QFN is NULL, it is treated as a function which always
1753    returns 1.  Both FN and QFN are passed the DATA whenever they are
1754    called.  */
1755
1756 static tree
1757 bfs_walk (binfo, fn, qfn, data)
1758      tree binfo;
1759      tree (*fn) PARAMS ((tree, void *));
1760      tree (*qfn) PARAMS ((tree, void *));
1761      void *data;
1762 {
1763   size_t head;
1764   size_t tail;
1765   tree rval = NULL_TREE;
1766   /* An array of the base classes of BINFO.  These will be built up in
1767      breadth-first order, except where QFN prunes the search.  */
1768   varray_type bfs_bases;
1769
1770   /* Start with enough room for ten base classes.  That will be enough
1771      for most hierarchies.  */
1772   VARRAY_TREE_INIT (bfs_bases, 10, "search_stack");
1773
1774   /* Put the first type into the stack.  */
1775   VARRAY_TREE (bfs_bases, 0) = binfo;
1776   tail = 1;
1777
1778   for (head = 0; head < tail; ++head)
1779     {
1780       int i;
1781       int n_baselinks;
1782       tree binfos;
1783
1784       /* Pull the next type out of the queue.  */
1785       binfo = VARRAY_TREE (bfs_bases, head);
1786
1787       /* If this is the one we're looking for, we're done.  */
1788       rval = (*fn) (binfo, data);
1789       if (rval)
1790         break;
1791
1792       /* Queue up the base types.  */
1793       binfos = BINFO_BASETYPES (binfo);
1794       n_baselinks = binfos ? TREE_VEC_LENGTH (binfos): 0;
1795       for (i = 0; i < n_baselinks; i++)
1796         {
1797           tree base_binfo = TREE_VEC_ELT (binfos, i);
1798
1799           if (qfn)
1800             base_binfo = (*qfn) (base_binfo, data);
1801
1802           if (base_binfo)
1803             {
1804               if (tail == VARRAY_SIZE (bfs_bases))
1805                 VARRAY_GROW (bfs_bases, 2 * VARRAY_SIZE (bfs_bases));
1806               VARRAY_TREE (bfs_bases, tail) = base_binfo;
1807               ++tail;
1808             }
1809         }
1810     }
1811
1812   /* Clean up.  */
1813   VARRAY_FREE (bfs_bases);
1814
1815   return rval;
1816 }
1817
1818 /* Exactly like bfs_walk, except that a depth-first traversal is
1819    performed, and PREFN is called in preorder, while POSTFN is called
1820    in postorder.  */
1821
1822 tree
1823 dfs_walk_real (binfo, prefn, postfn, qfn, data)
1824      tree binfo;
1825      tree (*prefn) PARAMS ((tree, void *));
1826      tree (*postfn) PARAMS ((tree, void *));
1827      tree (*qfn) PARAMS ((tree, void *));
1828      void *data;
1829 {
1830   int i;
1831   int n_baselinks;
1832   tree binfos;
1833   tree rval = NULL_TREE;
1834
1835   /* Call the pre-order walking function.  */
1836   if (prefn)
1837     {
1838       rval = (*prefn) (binfo, data);
1839       if (rval)
1840         return rval;
1841     }
1842
1843   /* Process the basetypes.  */
1844   binfos = BINFO_BASETYPES (binfo);
1845   n_baselinks = BINFO_N_BASETYPES (binfo);
1846   for (i = 0; i < n_baselinks; i++)
1847     {
1848       tree base_binfo = TREE_VEC_ELT (binfos, i);
1849
1850       if (qfn)
1851         base_binfo = (*qfn) (base_binfo, data);
1852
1853       if (base_binfo)
1854         {
1855           rval = dfs_walk_real (base_binfo, prefn, postfn, qfn, data);
1856           if (rval)
1857             return rval;
1858         }
1859     }
1860
1861   /* Call the post-order walking function.  */
1862   if (postfn)
1863     rval = (*postfn) (binfo, data);
1864
1865   return rval;
1866 }
1867
1868 /* Exactly like bfs_walk, except that a depth-first post-order traversal is
1869    performed.  */
1870
1871 tree
1872 dfs_walk (binfo, fn, qfn, data)
1873      tree binfo;
1874      tree (*fn) PARAMS ((tree, void *));
1875      tree (*qfn) PARAMS ((tree, void *));
1876      void *data;
1877 {
1878   return dfs_walk_real (binfo, 0, fn, qfn, data);
1879 }
1880
1881 /* Returns > 0 if a function with type DRETTYPE overriding a function
1882    with type BRETTYPE is covariant, as defined in [class.virtual].
1883
1884    Returns 1 if trivial covariance, 2 if non-trivial (requiring runtime
1885    adjustment), or -1 if pedantically invalid covariance.  */
1886
1887 static int
1888 covariant_return_p (brettype, drettype)
1889      tree brettype, drettype;
1890 {
1891   tree binfo;
1892
1893   if (TREE_CODE (brettype) == FUNCTION_DECL)
1894     {
1895       brettype = TREE_TYPE (TREE_TYPE (brettype));
1896       drettype = TREE_TYPE (TREE_TYPE (drettype));
1897     }
1898   else if (TREE_CODE (brettype) == METHOD_TYPE)
1899     {
1900       brettype = TREE_TYPE (brettype);
1901       drettype = TREE_TYPE (drettype);
1902     }
1903
1904   if (same_type_p (brettype, drettype))
1905     return 0;
1906
1907   if (! (TREE_CODE (brettype) == TREE_CODE (drettype)
1908          && (TREE_CODE (brettype) == POINTER_TYPE
1909              || TREE_CODE (brettype) == REFERENCE_TYPE)
1910          && TYPE_QUALS (brettype) == TYPE_QUALS (drettype)))
1911     return 0;
1912
1913   if (! can_convert (brettype, drettype))
1914     return 0;
1915
1916   brettype = TREE_TYPE (brettype);
1917   drettype = TREE_TYPE (drettype);
1918
1919   /* If not pedantic, allow any standard pointer conversion.  */
1920   if (! IS_AGGR_TYPE (drettype) || ! IS_AGGR_TYPE (brettype))
1921     return -1;
1922
1923   binfo = get_binfo (brettype, drettype, 1);
1924
1925   /* If we get an error_mark_node from get_binfo, it already complained,
1926      so let's just succeed.  */
1927   if (binfo == error_mark_node)
1928     return 1;
1929
1930   if (! BINFO_OFFSET_ZEROP (binfo) || TREE_VIA_VIRTUAL (binfo))
1931     return 2;
1932   return 1;
1933 }
1934
1935 /* Check that virtual overrider OVERRIDER is acceptable for base function
1936    BASEFN. Issue diagnostic, and return zero, if unacceptable.  */
1937
1938 static int
1939 check_final_overrider (overrider, basefn)
1940      tree overrider, basefn;
1941 {
1942   tree over_type = TREE_TYPE (overrider);
1943   tree base_type = TREE_TYPE (basefn);
1944   tree over_return = TREE_TYPE (over_type);
1945   tree base_return = TREE_TYPE (base_type);
1946   tree over_throw = TYPE_RAISES_EXCEPTIONS (over_type);
1947   tree base_throw = TYPE_RAISES_EXCEPTIONS (base_type);
1948   int i;
1949
1950   if (same_type_p (base_return, over_return))
1951     /* OK */;
1952   else if ((i = covariant_return_p (base_return, over_return)))
1953     {
1954       if (i == 2)
1955         sorry ("adjusting pointers for covariant returns");
1956
1957       if (pedantic && i == -1)
1958         {
1959           cp_pedwarn_at ("invalid covariant return type for `%#D'", overrider);
1960           cp_pedwarn_at ("  overriding `%#D' (must be pointer or reference to class)", basefn);
1961         }
1962     }
1963   else if (IS_AGGR_TYPE_2 (base_return, over_return)
1964            && same_or_base_type_p (base_return, over_return))
1965     {
1966       cp_error_at ("invalid covariant return type for `%#D'", overrider);
1967       cp_error_at ("  overriding `%#D' (must use pointer or reference)", basefn);
1968       return 0;
1969     }
1970   else if (IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider)) == NULL_TREE)
1971     {
1972       cp_error_at ("conflicting return type specified for `%#D'", overrider);
1973       cp_error_at ("  overriding `%#D'", basefn);
1974       SET_IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider),
1975                                   DECL_CONTEXT (overrider));
1976       return 0;
1977     }
1978
1979   /* Check throw specifier is subset.  */
1980   if (!comp_except_specs (base_throw, over_throw, 0))
1981     {
1982       cp_error_at ("looser throw specifier for `%#F'", overrider);
1983       cp_error_at ("  overriding `%#F'", basefn);
1984       return 0;
1985     }
1986   return 1;
1987 }
1988
1989 /* Given a class TYPE, and a function decl FNDECL, look for
1990    virtual functions in TYPE's hierarchy which FNDECL overrides.
1991    We do not look in TYPE itself, only its bases.
1992
1993    Returns non-zero, if we find any. Set FNDECL's DECL_VIRTUAL_P, if we
1994    find that it overrides anything.
1995
1996    We check that every function which is overridden, is correctly
1997    overridden.  */
1998
1999 int
2000 look_for_overrides (type, fndecl)
2001      tree type, fndecl;
2002 {
2003   tree binfo = TYPE_BINFO (type);
2004   tree basebinfos = BINFO_BASETYPES (binfo);
2005   int nbasebinfos = basebinfos ? TREE_VEC_LENGTH (basebinfos) : 0;
2006   int ix;
2007   int found = 0;
2008
2009   for (ix = 0; ix != nbasebinfos; ix++)
2010     {
2011       tree basetype = BINFO_TYPE (TREE_VEC_ELT (basebinfos, ix));
2012
2013       if (TYPE_POLYMORPHIC_P (basetype))
2014         found += look_for_overrides_r (basetype, fndecl);
2015     }
2016   return found;
2017 }
2018
2019 /* Look in TYPE for virtual functions with the same signature as FNDECL.
2020    This differs from get_matching_virtual in that it will only return
2021    a function from TYPE.  */
2022
2023 tree
2024 look_for_overrides_here (type, fndecl)
2025      tree type, fndecl;
2026 {
2027   int ix;
2028
2029   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fndecl))
2030     ix = CLASSTYPE_DESTRUCTOR_SLOT;
2031   else
2032     ix = lookup_fnfields_1 (type, DECL_NAME (fndecl));
2033   if (ix >= 0)
2034     {
2035       tree fns = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), ix);
2036
2037       for (; fns; fns = OVL_NEXT (fns))
2038         {
2039           tree fn = OVL_CURRENT (fns);
2040
2041           if (!DECL_VIRTUAL_P (fn))
2042             /* Not a virtual.  */;
2043           else if (DECL_CONTEXT (fn) != type)
2044             /* Introduced with a using declaration.  */;
2045           else if (DECL_STATIC_FUNCTION_P (fndecl))
2046             {
2047               tree btypes = TYPE_ARG_TYPES (TREE_TYPE (fn));
2048               tree dtypes = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
2049               if (compparms (TREE_CHAIN (btypes), dtypes))
2050                 return fn;
2051             }
2052           else if (same_signature_p (fndecl, fn))
2053             return fn;
2054         }
2055     }
2056   return NULL_TREE;
2057 }
2058
2059 /* Look in TYPE for virtual functions overridden by FNDECL. Check both
2060    TYPE itself and its bases. */
2061
2062 static int
2063 look_for_overrides_r (type, fndecl)
2064      tree type, fndecl;
2065 {
2066   tree fn = look_for_overrides_here (type, fndecl);
2067   if (fn)
2068     {
2069       if (DECL_STATIC_FUNCTION_P (fndecl))
2070         {
2071           /* A static member function cannot match an inherited
2072              virtual member function.  */
2073           cp_error_at ("`%#D' cannot be declared", fndecl);
2074           cp_error_at ("  since `%#D' declared in base class", fn);
2075         }
2076       else
2077         {
2078           /* It's definitely virtual, even if not explicitly set.  */
2079           DECL_VIRTUAL_P (fndecl) = 1;
2080           check_final_overrider (fndecl, fn);
2081         }
2082       return 1;
2083     }
2084
2085   /* We failed to find one declared in this class. Look in its bases.  */
2086   return look_for_overrides (type, fndecl);
2087 }
2088
2089 /* A queue function for dfs_walk that skips any nonprimary virtual
2090    bases and any already marked bases.  */
2091
2092 tree
2093 dfs_skip_nonprimary_vbases_unmarkedp (binfo, data)
2094      tree binfo;
2095      void *data ATTRIBUTE_UNUSED;
2096 {
2097   if (TREE_VIA_VIRTUAL (binfo) && !BINFO_PRIMARY_P (binfo))
2098     /* This is a non-primary virtual base.  Skip it.  */
2099     return NULL_TREE;
2100
2101   return unmarkedp (binfo, NULL);
2102 }
2103
2104 /* A queue function for dfs_walk that skips any nonprimary virtual
2105    bases and any unmarked bases.  */
2106
2107 tree
2108 dfs_skip_nonprimary_vbases_markedp (binfo, data)
2109      tree binfo;
2110      void *data ATTRIBUTE_UNUSED;
2111 {
2112   if (TREE_VIA_VIRTUAL (binfo) && !BINFO_PRIMARY_P (binfo))
2113     /* This is a non-primary virtual base.  Skip it.  */
2114     return NULL_TREE;
2115
2116   return markedp (binfo, NULL);
2117 }
2118
2119 /* If BINFO is a non-primary virtual baseclass (in the hierarchy
2120    dominated by TYPE), and no primary copy appears anywhere in the
2121    hierarchy, return the shared copy.  If a primary copy appears
2122    elsewhere, return NULL_TREE.  Otherwise, return BINFO itself; it is
2123    either a non-virtual base or a primary virtual base.  */
2124
2125 static tree
2126 get_shared_vbase_if_not_primary (binfo, data)
2127      tree binfo;
2128      void *data;
2129 {
2130   if (TREE_VIA_VIRTUAL (binfo) && !BINFO_PRIMARY_P (binfo))
2131     {
2132       tree type = (tree) data;
2133
2134       if (TREE_CODE (type) == TREE_LIST)
2135         type = TREE_PURPOSE (type);
2136
2137       /* This is a non-primary virtual base.  If there is no primary
2138          version, get the shared version.  */
2139       binfo = binfo_for_vbase (BINFO_TYPE (binfo), type);
2140       if (BINFO_PRIMARY_P (binfo))
2141         return NULL_TREE;
2142     }
2143
2144   return binfo;
2145 }
2146
2147 /* A queue function to use with dfs_walk that prevents travel into any
2148    nonprimary virtual base, or its baseclasses.  DATA should be the
2149    type of the complete object, or a TREE_LIST whose TREE_PURPOSE is
2150    the type of the complete object.  By using this function as a queue
2151    function, you will walk over exactly those BINFOs that actually
2152    exist in the complete object, including those for virtual base
2153    classes.  If you SET_BINFO_MARKED for each binfo you process, you
2154    are further guaranteed that you will walk into each virtual base
2155    class exactly once.  */
2156
2157 tree
2158 dfs_unmarked_real_bases_queue_p (binfo, data)
2159      tree binfo;
2160      void *data;
2161 {
2162   binfo = get_shared_vbase_if_not_primary (binfo, data);
2163   return binfo ? unmarkedp (binfo, NULL) : NULL_TREE;
2164 }
2165
2166 /* Like dfs_unmarked_real_bases_queue_p but walks only into things
2167    that are marked, rather than unmarked.  */
2168
2169 tree
2170 dfs_marked_real_bases_queue_p (binfo, data)
2171      tree binfo;
2172      void *data;
2173 {
2174   binfo = get_shared_vbase_if_not_primary (binfo, data);
2175   return binfo ? markedp (binfo, NULL) : NULL_TREE;
2176 }
2177
2178 /* A queue function that skips all virtual bases (and their
2179    bases).  */
2180
2181 tree
2182 dfs_skip_vbases (binfo, data)
2183      tree binfo;
2184      void *data ATTRIBUTE_UNUSED;
2185 {
2186   if (TREE_VIA_VIRTUAL (binfo))
2187     return NULL_TREE;
2188
2189   return binfo;
2190 }
2191
2192 /* Called via dfs_walk from dfs_get_pure_virtuals.  */
2193
2194 static tree
2195 dfs_get_pure_virtuals (binfo, data)
2196      tree binfo;
2197      void *data;
2198 {
2199   tree type = (tree) data;
2200
2201   /* We're not interested in primary base classes; the derived class
2202      of which they are a primary base will contain the information we
2203      need.  */
2204   if (!BINFO_PRIMARY_P (binfo))
2205     {
2206       tree virtuals;
2207
2208       for (virtuals = BINFO_VIRTUALS (binfo);
2209            virtuals;
2210            virtuals = TREE_CHAIN (virtuals))
2211         if (DECL_PURE_VIRTUAL_P (BV_FN (virtuals)))
2212           CLASSTYPE_PURE_VIRTUALS (type)
2213             = tree_cons (NULL_TREE, BV_FN (virtuals),
2214                          CLASSTYPE_PURE_VIRTUALS (type));
2215     }
2216
2217   SET_BINFO_MARKED (binfo);
2218
2219   return NULL_TREE;
2220 }
2221
2222 /* Set CLASSTYPE_PURE_VIRTUALS for TYPE.  */
2223
2224 void
2225 get_pure_virtuals (type)
2226      tree type;
2227 {
2228   tree vbases;
2229
2230   /* Clear the CLASSTYPE_PURE_VIRTUALS list; whatever is already there
2231      is going to be overridden.  */
2232   CLASSTYPE_PURE_VIRTUALS (type) = NULL_TREE;
2233   /* Now, run through all the bases which are not primary bases, and
2234      collect the pure virtual functions.  We look at the vtable in
2235      each class to determine what pure virtual functions are present.
2236      (A primary base is not interesting because the derived class of
2237      which it is a primary base will contain vtable entries for the
2238      pure virtuals in the base class.  */
2239   dfs_walk (TYPE_BINFO (type), dfs_get_pure_virtuals,
2240             dfs_unmarked_real_bases_queue_p, type);
2241   dfs_walk (TYPE_BINFO (type), dfs_unmark,
2242             dfs_marked_real_bases_queue_p, type);
2243
2244   /* Put the pure virtuals in dfs order.  */
2245   CLASSTYPE_PURE_VIRTUALS (type) = nreverse (CLASSTYPE_PURE_VIRTUALS (type));
2246
2247   for (vbases = CLASSTYPE_VBASECLASSES (type);
2248        vbases;
2249        vbases = TREE_CHAIN (vbases))
2250     {
2251       tree virtuals;
2252
2253       for (virtuals = BINFO_VIRTUALS (TREE_VALUE (vbases));
2254            virtuals;
2255            virtuals = TREE_CHAIN (virtuals))
2256         {
2257           tree base_fndecl = BV_FN (virtuals);
2258           if (DECL_NEEDS_FINAL_OVERRIDER_P (base_fndecl))
2259             cp_error ("`%#D' needs a final overrider", base_fndecl);
2260         }
2261     }
2262 }
2263 \f
2264 /* DEPTH-FIRST SEARCH ROUTINES.  */
2265
2266 tree
2267 markedp (binfo, data)
2268      tree binfo;
2269      void *data ATTRIBUTE_UNUSED;
2270 {
2271   return BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2272 }
2273
2274 tree
2275 unmarkedp (binfo, data)
2276      tree binfo;
2277      void *data ATTRIBUTE_UNUSED;
2278 {
2279   return !BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2280 }
2281
2282 tree
2283 marked_vtable_pathp (binfo, data)
2284      tree binfo;
2285      void *data ATTRIBUTE_UNUSED;
2286 {
2287   return BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2288 }
2289
2290 tree
2291 unmarked_vtable_pathp (binfo, data)
2292      tree binfo;
2293      void *data ATTRIBUTE_UNUSED;
2294 {
2295   return !BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2296 }
2297
2298 static tree
2299 marked_pushdecls_p (binfo, data)
2300      tree binfo;
2301      void *data ATTRIBUTE_UNUSED;
2302 {
2303   return (CLASS_TYPE_P (BINFO_TYPE (binfo))
2304           && BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2305 }
2306
2307 static tree
2308 unmarked_pushdecls_p (binfo, data)
2309      tree binfo;
2310      void *data ATTRIBUTE_UNUSED;
2311 {
2312   return (CLASS_TYPE_P (BINFO_TYPE (binfo))
2313           && !BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2314 }
2315
2316 /* The worker functions for `dfs_walk'.  These do not need to
2317    test anything (vis a vis marking) if they are paired with
2318    a predicate function (above).  */
2319
2320 tree
2321 dfs_unmark (binfo, data)
2322      tree binfo;
2323      void *data ATTRIBUTE_UNUSED;
2324 {
2325   CLEAR_BINFO_MARKED (binfo);
2326   return NULL_TREE;
2327 }
2328
2329 /* get virtual base class types.
2330    This adds type to the vbase_types list in reverse dfs order.
2331    Ordering is very important, so don't change it.  */
2332
2333 static tree
2334 dfs_get_vbase_types (binfo, data)
2335      tree binfo;
2336      void *data;
2337 {
2338   tree type = (tree) data;
2339
2340   if (TREE_VIA_VIRTUAL (binfo))
2341     CLASSTYPE_VBASECLASSES (type)
2342       = tree_cons (BINFO_TYPE (binfo),
2343                    binfo,
2344                    CLASSTYPE_VBASECLASSES (type));
2345   SET_BINFO_MARKED (binfo);
2346   return NULL_TREE;
2347 }
2348
2349 /* Called via dfs_walk from mark_primary_bases.  Builds the
2350    inheritance graph order list of BINFOs.  */
2351
2352 static tree
2353 dfs_build_inheritance_graph_order (binfo, data)
2354      tree binfo;
2355      void *data;
2356 {
2357   tree *last_binfo = (tree *) data;
2358
2359   if (*last_binfo)
2360     TREE_CHAIN (*last_binfo) = binfo;
2361   *last_binfo = binfo;
2362   SET_BINFO_MARKED (binfo);
2363   return NULL_TREE;
2364 }
2365
2366 /* Set CLASSTYPE_VBASECLASSES for TYPE.  */
2367
2368 void
2369 get_vbase_types (type)
2370      tree type;
2371 {
2372   tree last_binfo;
2373
2374   CLASSTYPE_VBASECLASSES (type) = NULL_TREE;
2375   dfs_walk (TYPE_BINFO (type), dfs_get_vbase_types, unmarkedp, type);
2376   /* Rely upon the reverse dfs ordering from dfs_get_vbase_types, and now
2377      reverse it so that we get normal dfs ordering.  */
2378   CLASSTYPE_VBASECLASSES (type) = nreverse (CLASSTYPE_VBASECLASSES (type));
2379   dfs_walk (TYPE_BINFO (type), dfs_unmark, markedp, 0);
2380   /* Thread the BINFOs in inheritance-graph order.  */
2381   last_binfo = NULL;
2382   dfs_walk_real (TYPE_BINFO (type),
2383                  dfs_build_inheritance_graph_order,
2384                  NULL,
2385                  unmarkedp,
2386                  &last_binfo);
2387   dfs_walk (TYPE_BINFO (type), dfs_unmark, markedp, NULL);
2388 }
2389
2390 /* Called from find_vbase_instance via dfs_walk.  */
2391
2392 static tree
2393 dfs_find_vbase_instance (binfo, data)
2394      tree binfo;
2395      void *data;
2396 {
2397   tree base = TREE_VALUE ((tree) data);
2398
2399   if (BINFO_PRIMARY_P (binfo)
2400       && same_type_p (BINFO_TYPE (binfo), base))
2401     return binfo;
2402
2403   return NULL_TREE;
2404 }
2405
2406 /* Find the real occurrence of the virtual BASE (a class type) in the
2407    hierarchy dominated by TYPE.  */
2408
2409 tree
2410 find_vbase_instance (base, type)
2411      tree base;
2412      tree type;
2413 {
2414   tree instance;
2415
2416   instance = binfo_for_vbase (base, type);
2417   if (!BINFO_PRIMARY_P (instance))
2418     return instance;
2419
2420   return dfs_walk (TYPE_BINFO (type),
2421                    dfs_find_vbase_instance,
2422                    NULL,
2423                    build_tree_list (type, base));
2424 }
2425
2426 \f
2427 /* Debug info for C++ classes can get very large; try to avoid
2428    emitting it everywhere.
2429
2430    Note that this optimization wins even when the target supports
2431    BINCL (if only slightly), and reduces the amount of work for the
2432    linker.  */
2433
2434 void
2435 maybe_suppress_debug_info (t)
2436      tree t;
2437 {
2438   /* We can't do the usual TYPE_DECL_SUPPRESS_DEBUG thing with DWARF, which
2439      does not support name references between translation units.  It supports
2440      symbolic references between translation units, but only within a single
2441      executable or shared library.
2442
2443      For DWARF 2, we handle TYPE_DECL_SUPPRESS_DEBUG by pretending
2444      that the type was never defined, so we only get the members we
2445      actually define.  */
2446   if (write_symbols == DWARF_DEBUG || write_symbols == NO_DEBUG)
2447     return;
2448
2449   /* We might have set this earlier in cp_finish_decl.  */
2450   TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 0;
2451
2452   /* If we already know how we're handling this class, handle debug info
2453      the same way.  */
2454   if (CLASSTYPE_INTERFACE_KNOWN (t))
2455     {
2456       if (CLASSTYPE_INTERFACE_ONLY (t))
2457         TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 1;
2458       /* else don't set it.  */
2459     }
2460   /* If the class has a vtable, write out the debug info along with
2461      the vtable.  */
2462   else if (TYPE_CONTAINS_VPTR_P (t))
2463     TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 1;
2464
2465   /* Otherwise, just emit the debug info normally.  */
2466 }
2467
2468 /* Note that we want debugging information for a base class of a class
2469    whose vtable is being emitted.  Normally, this would happen because
2470    calling the constructor for a derived class implies calling the
2471    constructors for all bases, which involve initializing the
2472    appropriate vptr with the vtable for the base class; but in the
2473    presence of optimization, this initialization may be optimized
2474    away, so we tell finish_vtable_vardecl that we want the debugging
2475    information anyway.  */
2476
2477 static tree
2478 dfs_debug_mark (binfo, data)
2479      tree binfo;
2480      void *data ATTRIBUTE_UNUSED;
2481 {
2482   tree t = BINFO_TYPE (binfo);
2483
2484   CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2485
2486   return NULL_TREE;
2487 }
2488
2489 /* Returns BINFO if we haven't already noted that we want debugging
2490    info for this base class.  */
2491
2492 static tree
2493 dfs_debug_unmarkedp (binfo, data)
2494      tree binfo;
2495      void *data ATTRIBUTE_UNUSED;
2496 {
2497   return (!CLASSTYPE_DEBUG_REQUESTED (BINFO_TYPE (binfo))
2498           ? binfo : NULL_TREE);
2499 }
2500
2501 /* Write out the debugging information for TYPE, whose vtable is being
2502    emitted.  Also walk through our bases and note that we want to
2503    write out information for them.  This avoids the problem of not
2504    writing any debug info for intermediate basetypes whose
2505    constructors, and thus the references to their vtables, and thus
2506    the vtables themselves, were optimized away.  */
2507
2508 void
2509 note_debug_info_needed (type)
2510      tree type;
2511 {
2512   if (TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (type)))
2513     {
2514       TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (type)) = 0;
2515       rest_of_type_compilation (type, toplevel_bindings_p ());
2516     }
2517
2518   dfs_walk (TYPE_BINFO (type), dfs_debug_mark, dfs_debug_unmarkedp, 0);
2519 }
2520 \f
2521 /* Subroutines of push_class_decls ().  */
2522
2523 /* Returns 1 iff BINFO is a base we shouldn't really be able to see into,
2524    because it (or one of the intermediate bases) depends on template parms.  */
2525
2526 static int
2527 dependent_base_p (binfo)
2528      tree binfo;
2529 {
2530   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2531     {
2532       if (currently_open_class (TREE_TYPE (binfo)))
2533         break;
2534       if (uses_template_parms (TREE_TYPE (binfo)))
2535         return 1;
2536     }
2537   return 0;
2538 }
2539
2540 static void
2541 setup_class_bindings (name, type_binding_p)
2542      tree name;
2543      int type_binding_p;
2544 {
2545   tree type_binding = NULL_TREE;
2546   tree value_binding;
2547
2548   /* If we've already done the lookup for this declaration, we're
2549      done.  */
2550   if (IDENTIFIER_CLASS_VALUE (name))
2551     return;
2552
2553   /* First, deal with the type binding.  */
2554   if (type_binding_p)
2555     {
2556       type_binding = lookup_member (current_class_type, name,
2557                                     /*protect=*/2,
2558                                     /*want_type=*/1);
2559       if (TREE_CODE (type_binding) == TREE_LIST
2560           && TREE_TYPE (type_binding) == error_mark_node)
2561         /* NAME is ambiguous.  */
2562         push_class_level_binding (name, type_binding);
2563       else
2564         pushdecl_class_level (type_binding);
2565     }
2566
2567   /* Now, do the value binding.  */
2568   value_binding = lookup_member (current_class_type, name,
2569                                  /*protect=*/2,
2570                                  /*want_type=*/0);
2571
2572   if (type_binding_p
2573       && (TREE_CODE (value_binding) == TYPE_DECL
2574           || (TREE_CODE (value_binding) == TREE_LIST
2575               && TREE_TYPE (value_binding) == error_mark_node
2576               && (TREE_CODE (TREE_VALUE (value_binding))
2577                   == TYPE_DECL))))
2578     /* We found a type-binding, even when looking for a non-type
2579        binding.  This means that we already processed this binding
2580        above.  */
2581     my_friendly_assert (type_binding_p, 19990401);
2582   else if (value_binding)
2583     {
2584       if (TREE_CODE (value_binding) == TREE_LIST
2585           && TREE_TYPE (value_binding) == error_mark_node)
2586         /* NAME is ambiguous.  */
2587         push_class_level_binding (name, value_binding);
2588       else
2589         {
2590           if (BASELINK_P (value_binding))
2591             /* NAME is some overloaded functions.  */
2592             value_binding = BASELINK_FUNCTIONS (value_binding);
2593           pushdecl_class_level (value_binding);
2594         }
2595     }
2596 }
2597
2598 /* Push class-level declarations for any names appearing in BINFO that
2599    are TYPE_DECLS.  */
2600
2601 static tree
2602 dfs_push_type_decls (binfo, data)
2603      tree binfo;
2604      void *data ATTRIBUTE_UNUSED;
2605 {
2606   tree type;
2607   tree fields;
2608   bool dep_base_p;
2609
2610   type = BINFO_TYPE (binfo);
2611   dep_base_p = (processing_template_decl
2612                 && type != current_class_type
2613                 && dependent_base_p (binfo));
2614   if (!dep_base_p)
2615     for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2616       if (DECL_NAME (fields) && TREE_CODE (fields) == TYPE_DECL
2617           && !(!same_type_p (type, current_class_type)
2618                && template_self_reference_p (type, fields)))
2619         setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/1);
2620
2621   /* We can't just use BINFO_MARKED because envelope_add_decl uses
2622      DERIVED_FROM_P, which calls get_base_distance.  */
2623   SET_BINFO_PUSHDECLS_MARKED (binfo);
2624
2625   return NULL_TREE;
2626 }
2627
2628 /* Push class-level declarations for any names appearing in BINFO that
2629    are not TYPE_DECLS.  */
2630
2631 static tree
2632 dfs_push_decls (binfo, data)
2633      tree binfo;
2634      void *data;
2635 {
2636   tree type;
2637   tree method_vec;
2638   bool dep_base_p;
2639
2640   type = BINFO_TYPE (binfo);
2641   dep_base_p = (processing_template_decl && type != current_class_type
2642                 && dependent_base_p (binfo));
2643   if (!dep_base_p)
2644     {
2645       tree fields;
2646       for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2647         if (DECL_NAME (fields)
2648             && TREE_CODE (fields) != TYPE_DECL)
2649           setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/0);
2650         else if (TREE_CODE (fields) == FIELD_DECL
2651                  && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
2652           dfs_push_decls (TYPE_BINFO (TREE_TYPE (fields)), data);
2653
2654       method_vec = (CLASS_TYPE_P (type)
2655                     ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE);
2656       if (method_vec)
2657         {
2658           tree *methods;
2659           tree *end;
2660
2661           /* Farm out constructors and destructors.  */
2662           end = TREE_VEC_END (method_vec);
2663
2664           for (methods = &TREE_VEC_ELT (method_vec, 2);
2665                *methods && methods != end;
2666                methods++)
2667             setup_class_bindings (DECL_NAME (OVL_CURRENT (*methods)),
2668                                   /*type_binding_p=*/0);
2669         }
2670     }
2671
2672   CLEAR_BINFO_PUSHDECLS_MARKED (binfo);
2673
2674   return NULL_TREE;
2675 }
2676
2677 /* When entering the scope of a class, we cache all of the
2678    fields that that class provides within its inheritance
2679    lattice.  Where ambiguities result, we mark them
2680    with `error_mark_node' so that if they are encountered
2681    without explicit qualification, we can emit an error
2682    message.  */
2683
2684 void
2685 push_class_decls (type)
2686      tree type;
2687 {
2688   search_stack = push_search_level (search_stack, &search_obstack);
2689
2690   /* Enter type declarations and mark.  */
2691   dfs_walk (TYPE_BINFO (type), dfs_push_type_decls, unmarked_pushdecls_p, 0);
2692
2693   /* Enter non-type declarations and unmark.  */
2694   dfs_walk (TYPE_BINFO (type), dfs_push_decls, marked_pushdecls_p, 0);
2695 }
2696
2697 /* Here's a subroutine we need because C lacks lambdas.  */
2698
2699 static tree
2700 dfs_unuse_fields (binfo, data)
2701      tree binfo;
2702      void *data ATTRIBUTE_UNUSED;
2703 {
2704   tree type = TREE_TYPE (binfo);
2705   tree fields;
2706
2707   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2708     {
2709       if (TREE_CODE (fields) != FIELD_DECL)
2710         continue;
2711
2712       TREE_USED (fields) = 0;
2713       if (DECL_NAME (fields) == NULL_TREE
2714           && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
2715         unuse_fields (TREE_TYPE (fields));
2716     }
2717
2718   return NULL_TREE;
2719 }
2720
2721 void
2722 unuse_fields (type)
2723      tree type;
2724 {
2725   dfs_walk (TYPE_BINFO (type), dfs_unuse_fields, unmarkedp, 0);
2726 }
2727
2728 void
2729 pop_class_decls ()
2730 {
2731   /* We haven't pushed a search level when dealing with cached classes,
2732      so we'd better not try to pop it.  */
2733   if (search_stack)
2734     search_stack = pop_search_level (search_stack);
2735 }
2736
2737 void
2738 print_search_statistics ()
2739 {
2740 #ifdef GATHER_STATISTICS
2741   fprintf (stderr, "%d fields searched in %d[%d] calls to lookup_field[_1]\n",
2742            n_fields_searched, n_calls_lookup_field, n_calls_lookup_field_1);
2743   fprintf (stderr, "%d fnfields searched in %d calls to lookup_fnfields\n",
2744            n_outer_fields_searched, n_calls_lookup_fnfields);
2745   fprintf (stderr, "%d calls to get_base_type\n", n_calls_get_base_type);
2746 #else /* GATHER_STATISTICS */
2747   fprintf (stderr, "no search statistics\n");
2748 #endif /* GATHER_STATISTICS */
2749 }
2750
2751 void
2752 init_search_processing ()
2753 {
2754   gcc_obstack_init (&search_obstack);
2755 }
2756
2757 void
2758 reinit_search_statistics ()
2759 {
2760 #ifdef GATHER_STATISTICS
2761   n_fields_searched = 0;
2762   n_calls_lookup_field = 0, n_calls_lookup_field_1 = 0;
2763   n_calls_lookup_fnfields = 0, n_calls_lookup_fnfields_1 = 0;
2764   n_calls_get_base_type = 0;
2765   n_outer_fields_searched = 0;
2766   n_contexts_saved = 0;
2767 #endif /* GATHER_STATISTICS */
2768 }
2769
2770 static tree
2771 add_conversions (binfo, data)
2772      tree binfo;
2773      void *data;
2774 {
2775   int i;
2776   tree method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
2777   tree *conversions = (tree *) data;
2778
2779   /* Some builtin types have no method vector, not even an empty one.  */
2780   if (!method_vec)
2781     return NULL_TREE;
2782
2783   for (i = 2; i < TREE_VEC_LENGTH (method_vec); ++i)
2784     {
2785       tree tmp = TREE_VEC_ELT (method_vec, i);
2786       tree name;
2787
2788       if (!tmp || ! DECL_CONV_FN_P (OVL_CURRENT (tmp)))
2789         break;
2790
2791       name = DECL_NAME (OVL_CURRENT (tmp));
2792
2793       /* Make sure we don't already have this conversion.  */
2794       if (! IDENTIFIER_MARKED (name))
2795         {
2796           *conversions = tree_cons (binfo, tmp, *conversions);
2797           IDENTIFIER_MARKED (name) = 1;
2798         }
2799     }
2800   return NULL_TREE;
2801 }
2802
2803 /* Return a TREE_LIST containing all the non-hidden user-defined
2804    conversion functions for TYPE (and its base-classes).  The
2805    TREE_VALUE of each node is a FUNCTION_DECL or an OVERLOAD
2806    containing the conversion functions.  The TREE_PURPOSE is the BINFO
2807    from which the conversion functions in this node were selected.  */
2808
2809 tree
2810 lookup_conversions (type)
2811      tree type;
2812 {
2813   tree t;
2814   tree conversions = NULL_TREE;
2815
2816   if (COMPLETE_TYPE_P (type))
2817     bfs_walk (TYPE_BINFO (type), add_conversions, 0, &conversions);
2818
2819   for (t = conversions; t; t = TREE_CHAIN (t))
2820     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (t)))) = 0;
2821
2822   return conversions;
2823 }
2824
2825 struct overlap_info
2826 {
2827   tree compare_type;
2828   int found_overlap;
2829 };
2830
2831 /* Check whether the empty class indicated by EMPTY_BINFO is also present
2832    at offset 0 in COMPARE_TYPE, and set found_overlap if so.  */
2833
2834 static tree
2835 dfs_check_overlap (empty_binfo, data)
2836      tree empty_binfo;
2837      void *data;
2838 {
2839   struct overlap_info *oi = (struct overlap_info *) data;
2840   tree binfo;
2841   for (binfo = TYPE_BINFO (oi->compare_type);
2842        ;
2843        binfo = BINFO_BASETYPE (binfo, 0))
2844     {
2845       if (BINFO_TYPE (binfo) == BINFO_TYPE (empty_binfo))
2846         {
2847           oi->found_overlap = 1;
2848           break;
2849         }
2850       else if (BINFO_BASETYPES (binfo) == NULL_TREE)
2851         break;
2852     }
2853
2854   return NULL_TREE;
2855 }
2856
2857 /* Trivial function to stop base traversal when we find something.  */
2858
2859 static tree
2860 dfs_no_overlap_yet (binfo, data)
2861      tree binfo;
2862      void *data;
2863 {
2864   struct overlap_info *oi = (struct overlap_info *) data;
2865   return !oi->found_overlap ? binfo : NULL_TREE;
2866 }
2867
2868 /* Returns nonzero if EMPTY_TYPE or any of its bases can also be found at
2869    offset 0 in NEXT_TYPE.  Used in laying out empty base class subobjects.  */
2870
2871 int
2872 types_overlap_p (empty_type, next_type)
2873      tree empty_type, next_type;
2874 {
2875   struct overlap_info oi;
2876
2877   if (! IS_AGGR_TYPE (next_type))
2878     return 0;
2879   oi.compare_type = next_type;
2880   oi.found_overlap = 0;
2881   dfs_walk (TYPE_BINFO (empty_type), dfs_check_overlap,
2882             dfs_no_overlap_yet, &oi);
2883   return oi.found_overlap;
2884 }
2885
2886 /* Given a vtable VAR, determine which of the inherited classes the vtable
2887    inherits (in a loose sense) functions from.
2888
2889    FIXME: This does not work with the new ABI.  */
2890
2891 tree
2892 binfo_for_vtable (var)
2893      tree var;
2894 {
2895   tree main_binfo = TYPE_BINFO (DECL_CONTEXT (var));
2896   tree binfos = TYPE_BINFO_BASETYPES (BINFO_TYPE (main_binfo));
2897   int n_baseclasses = CLASSTYPE_N_BASECLASSES (BINFO_TYPE (main_binfo));
2898   int i;
2899
2900   for (i = 0; i < n_baseclasses; i++)
2901     {
2902       tree base_binfo = TREE_VEC_ELT (binfos, i);
2903       if (base_binfo != NULL_TREE && BINFO_VTABLE (base_binfo) == var)
2904         return base_binfo;
2905     }
2906
2907   /* If no secondary base classes matched, return the primary base, if
2908      there is one.   */
2909   if (CLASSTYPE_HAS_PRIMARY_BASE_P (BINFO_TYPE (main_binfo)))
2910     return get_primary_binfo (main_binfo);
2911
2912   return main_binfo;
2913 }
2914
2915 /* Returns the binfo of the first direct or indirect virtual base derived
2916    from BINFO, or NULL if binfo is not via virtual.  */
2917
2918 tree
2919 binfo_from_vbase (binfo)
2920      tree binfo;
2921 {
2922   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2923     {
2924       if (TREE_VIA_VIRTUAL (binfo))
2925         return binfo;
2926     }
2927   return NULL_TREE;
2928 }
2929
2930 /* Returns the binfo of the first direct or indirect virtual base derived
2931    from BINFO up to the TREE_TYPE, LIMIT, or NULL if binfo is not
2932    via virtual.  */
2933
2934 tree
2935 binfo_via_virtual (binfo, limit)
2936      tree binfo;
2937      tree limit;
2938 {
2939   for (; binfo && (!limit || !same_type_p (BINFO_TYPE (binfo), limit));
2940        binfo = BINFO_INHERITANCE_CHAIN (binfo))
2941     {
2942       if (TREE_VIA_VIRTUAL (binfo))
2943         return binfo;
2944     }
2945   return NULL_TREE;
2946 }
2947
2948 /* Returns the BINFO (if any) for the virtual baseclass T of the class
2949    C from the CLASSTYPE_VBASECLASSES list.  */
2950
2951 tree
2952 binfo_for_vbase (basetype, classtype)
2953      tree basetype;
2954      tree classtype;
2955 {
2956   tree binfo;
2957
2958   binfo = purpose_member (basetype, CLASSTYPE_VBASECLASSES (classtype));
2959   return binfo ? TREE_VALUE (binfo) : NULL_TREE;
2960 }