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