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