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 FNDECL.
1959    This differs from get_matching_virtual in that it will only return
1960    a function from TYPE.  */
1961
1962 tree
1963 look_for_overrides_here (type, fndecl)
1964      tree type, fndecl;
1965 {
1966   int ix;
1967
1968   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fndecl))
1969     ix = CLASSTYPE_DESTRUCTOR_SLOT;
1970   else
1971     ix = lookup_fnfields_1 (type, DECL_NAME (fndecl));
1972   if (ix >= 0)
1973     {
1974       tree fns = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), ix);
1975
1976       for (; fns; fns = OVL_NEXT (fns))
1977         {
1978           tree fn = OVL_CURRENT (fns);
1979
1980           if (!DECL_VIRTUAL_P (fn))
1981             /* Not a virtual.  */;
1982           else if (DECL_CONTEXT (fn) != type)
1983             /* Introduced with a using declaration.  */;
1984           else if (DECL_STATIC_FUNCTION_P (fndecl))
1985             {
1986               tree btypes = TYPE_ARG_TYPES (TREE_TYPE (fn));
1987               tree dtypes = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
1988               if (compparms (TREE_CHAIN (btypes), dtypes))
1989                 return fn;
1990             }
1991           else if (same_signature_p (fndecl, fn))
1992             return fn;
1993         }
1994     }
1995   return NULL_TREE;
1996 }
1997
1998 /* Look in TYPE for virtual functions overridden by FNDECL. Check both
1999    TYPE itself and its bases.  */
2000
2001 static int
2002 look_for_overrides_r (type, fndecl)
2003      tree type, fndecl;
2004 {
2005   tree fn = look_for_overrides_here (type, fndecl);
2006   if (fn)
2007     {
2008       if (DECL_STATIC_FUNCTION_P (fndecl))
2009         {
2010           /* A static member function cannot match an inherited
2011              virtual member function.  */
2012           cp_error_at ("`%#D' cannot be declared", fndecl);
2013           cp_error_at ("  since `%#D' declared in base class", fn);
2014         }
2015       else
2016         {
2017           /* It's definitely virtual, even if not explicitly set.  */
2018           DECL_VIRTUAL_P (fndecl) = 1;
2019           check_final_overrider (fndecl, fn);
2020         }
2021       return 1;
2022     }
2023
2024   /* We failed to find one declared in this class. Look in its bases.  */
2025   return look_for_overrides (type, fndecl);
2026 }
2027
2028 /* A queue function to use with dfs_walk that only walks into
2029    canonical bases.  DATA should be the type of the complete object,
2030    or a TREE_LIST whose TREE_PURPOSE is the type of the complete
2031    object.  By using this function as a queue function, you will walk
2032    over exactly those BINFOs that actually exist in the complete
2033    object, including those for virtual base classes.  If you
2034    SET_BINFO_MARKED for each binfo you process, you are further
2035    guaranteed that you will walk into each virtual base class exactly
2036    once.  */
2037
2038 tree
2039 dfs_unmarked_real_bases_queue_p (binfo, data)
2040      tree binfo;
2041      void *data;
2042 {
2043   if (TREE_VIA_VIRTUAL (binfo))
2044     {
2045       tree type = (tree) data;
2046
2047       if (TREE_CODE (type) == TREE_LIST)
2048         type = TREE_PURPOSE (type);
2049       binfo = binfo_for_vbase (BINFO_TYPE (binfo), type);
2050     }
2051   return unmarkedp (binfo, NULL);
2052 }
2053
2054 /* Like dfs_unmarked_real_bases_queue_p but walks only into things
2055    that are marked, rather than unmarked.  */
2056
2057 tree
2058 dfs_marked_real_bases_queue_p (binfo, data)
2059      tree binfo;
2060      void *data;
2061 {
2062   if (TREE_VIA_VIRTUAL (binfo))
2063     {
2064       tree type = (tree) data;
2065
2066       if (TREE_CODE (type) == TREE_LIST)
2067         type = TREE_PURPOSE (type);
2068       binfo = binfo_for_vbase (BINFO_TYPE (binfo), type);
2069     }
2070   return markedp (binfo, NULL);
2071 }
2072
2073 /* A queue function that skips all virtual bases (and their
2074    bases).  */
2075
2076 tree
2077 dfs_skip_vbases (binfo, data)
2078      tree binfo;
2079      void *data ATTRIBUTE_UNUSED;
2080 {
2081   if (TREE_VIA_VIRTUAL (binfo))
2082     return NULL_TREE;
2083
2084   return binfo;
2085 }
2086
2087 /* Called via dfs_walk from dfs_get_pure_virtuals.  */
2088
2089 static tree
2090 dfs_get_pure_virtuals (binfo, data)
2091      tree binfo;
2092      void *data;
2093 {
2094   tree type = (tree) data;
2095
2096   /* We're not interested in primary base classes; the derived class
2097      of which they are a primary base will contain the information we
2098      need.  */
2099   if (!BINFO_PRIMARY_P (binfo))
2100     {
2101       tree virtuals;
2102
2103       for (virtuals = BINFO_VIRTUALS (binfo);
2104            virtuals;
2105            virtuals = TREE_CHAIN (virtuals))
2106         if (DECL_PURE_VIRTUAL_P (BV_FN (virtuals)))
2107           CLASSTYPE_PURE_VIRTUALS (type)
2108             = tree_cons (NULL_TREE, BV_FN (virtuals),
2109                          CLASSTYPE_PURE_VIRTUALS (type));
2110     }
2111
2112   SET_BINFO_MARKED (binfo);
2113
2114   return NULL_TREE;
2115 }
2116
2117 /* Set CLASSTYPE_PURE_VIRTUALS for TYPE.  */
2118
2119 void
2120 get_pure_virtuals (type)
2121      tree type;
2122 {
2123   tree vbases;
2124
2125   /* Clear the CLASSTYPE_PURE_VIRTUALS list; whatever is already there
2126      is going to be overridden.  */
2127   CLASSTYPE_PURE_VIRTUALS (type) = NULL_TREE;
2128   /* Now, run through all the bases which are not primary bases, and
2129      collect the pure virtual functions.  We look at the vtable in
2130      each class to determine what pure virtual functions are present.
2131      (A primary base is not interesting because the derived class of
2132      which it is a primary base will contain vtable entries for the
2133      pure virtuals in the base class.  */
2134   dfs_walk (TYPE_BINFO (type), dfs_get_pure_virtuals,
2135             dfs_unmarked_real_bases_queue_p, type);
2136   dfs_walk (TYPE_BINFO (type), dfs_unmark,
2137             dfs_marked_real_bases_queue_p, type);
2138
2139   /* Put the pure virtuals in dfs order.  */
2140   CLASSTYPE_PURE_VIRTUALS (type) = nreverse (CLASSTYPE_PURE_VIRTUALS (type));
2141
2142   for (vbases = CLASSTYPE_VBASECLASSES (type);
2143        vbases;
2144        vbases = TREE_CHAIN (vbases))
2145     {
2146       tree virtuals;
2147
2148       for (virtuals = BINFO_VIRTUALS (TREE_VALUE (vbases));
2149            virtuals;
2150            virtuals = TREE_CHAIN (virtuals))
2151         {
2152           tree base_fndecl = BV_FN (virtuals);
2153           if (DECL_NEEDS_FINAL_OVERRIDER_P (base_fndecl))
2154             error ("`%#D' needs a final overrider", base_fndecl);
2155         }
2156     }
2157 }
2158 \f
2159 /* DEPTH-FIRST SEARCH ROUTINES.  */
2160
2161 tree
2162 markedp (binfo, data)
2163      tree binfo;
2164      void *data ATTRIBUTE_UNUSED;
2165 {
2166   return BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2167 }
2168
2169 tree
2170 unmarkedp (binfo, data)
2171      tree binfo;
2172      void *data ATTRIBUTE_UNUSED;
2173 {
2174   return !BINFO_MARKED (binfo) ? binfo : NULL_TREE;
2175 }
2176
2177 tree
2178 marked_vtable_pathp (binfo, data)
2179      tree binfo;
2180      void *data ATTRIBUTE_UNUSED;
2181 {
2182   return BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2183 }
2184
2185 tree
2186 unmarked_vtable_pathp (binfo, data)
2187      tree binfo;
2188      void *data ATTRIBUTE_UNUSED;
2189 {
2190   return !BINFO_VTABLE_PATH_MARKED (binfo) ? binfo : NULL_TREE;
2191 }
2192
2193 static tree
2194 marked_pushdecls_p (binfo, data)
2195      tree binfo;
2196      void *data ATTRIBUTE_UNUSED;
2197 {
2198   return (CLASS_TYPE_P (BINFO_TYPE (binfo))
2199           && BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2200 }
2201
2202 static tree
2203 unmarked_pushdecls_p (binfo, data)
2204      tree binfo;
2205      void *data ATTRIBUTE_UNUSED;
2206 {
2207   return (CLASS_TYPE_P (BINFO_TYPE (binfo))
2208           && !BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2209 }
2210
2211 /* The worker functions for `dfs_walk'.  These do not need to
2212    test anything (vis a vis marking) if they are paired with
2213    a predicate function (above).  */
2214
2215 tree
2216 dfs_unmark (binfo, data)
2217      tree binfo;
2218      void *data ATTRIBUTE_UNUSED;
2219 {
2220   CLEAR_BINFO_MARKED (binfo);
2221   return NULL_TREE;
2222 }
2223
2224 /* get virtual base class types.
2225    This adds type to the vbase_types list in reverse dfs order.
2226    Ordering is very important, so don't change it.  */
2227
2228 static tree
2229 dfs_get_vbase_types (binfo, data)
2230      tree binfo;
2231      void *data;
2232 {
2233   tree type = (tree) data;
2234
2235   if (TREE_VIA_VIRTUAL (binfo))
2236     CLASSTYPE_VBASECLASSES (type)
2237       = tree_cons (BINFO_TYPE (binfo),
2238                    binfo,
2239                    CLASSTYPE_VBASECLASSES (type));
2240   SET_BINFO_MARKED (binfo);
2241   return NULL_TREE;
2242 }
2243
2244 /* Called via dfs_walk from mark_primary_bases.  Builds the
2245    inheritance graph order list of BINFOs.  */
2246
2247 static tree
2248 dfs_build_inheritance_graph_order (binfo, data)
2249      tree binfo;
2250      void *data;
2251 {
2252   tree *last_binfo = (tree *) data;
2253
2254   if (*last_binfo)
2255     TREE_CHAIN (*last_binfo) = binfo;
2256   *last_binfo = binfo;
2257   SET_BINFO_MARKED (binfo);
2258   return NULL_TREE;
2259 }
2260
2261 /* Set CLASSTYPE_VBASECLASSES for TYPE.  */
2262
2263 void
2264 get_vbase_types (type)
2265      tree type;
2266 {
2267   tree last_binfo;
2268
2269   CLASSTYPE_VBASECLASSES (type) = NULL_TREE;
2270   dfs_walk (TYPE_BINFO (type), dfs_get_vbase_types, unmarkedp, type);
2271   /* Rely upon the reverse dfs ordering from dfs_get_vbase_types, and now
2272      reverse it so that we get normal dfs ordering.  */
2273   CLASSTYPE_VBASECLASSES (type) = nreverse (CLASSTYPE_VBASECLASSES (type));
2274   dfs_walk (TYPE_BINFO (type), dfs_unmark, markedp, 0);
2275   /* Thread the BINFOs in inheritance-graph order.  */
2276   last_binfo = NULL;
2277   dfs_walk_real (TYPE_BINFO (type),
2278                  dfs_build_inheritance_graph_order,
2279                  NULL,
2280                  unmarkedp,
2281                  &last_binfo);
2282   dfs_walk (TYPE_BINFO (type), dfs_unmark, markedp, NULL);
2283 }
2284
2285 /* Called from find_vbase_instance via dfs_walk.  */
2286
2287 static tree
2288 dfs_find_vbase_instance (binfo, data)
2289      tree binfo;
2290      void *data;
2291 {
2292   tree base = TREE_VALUE ((tree) data);
2293
2294   if (BINFO_PRIMARY_P (binfo)
2295       && same_type_p (BINFO_TYPE (binfo), base))
2296     return binfo;
2297
2298   return NULL_TREE;
2299 }
2300
2301 /* Find the real occurrence of the virtual BASE (a class type) in the
2302    hierarchy dominated by TYPE.  */
2303
2304 tree
2305 find_vbase_instance (base, type)
2306      tree base;
2307      tree type;
2308 {
2309   tree instance;
2310
2311   instance = binfo_for_vbase (base, type);
2312   if (!BINFO_PRIMARY_P (instance))
2313     return instance;
2314
2315   return dfs_walk (TYPE_BINFO (type),
2316                    dfs_find_vbase_instance,
2317                    NULL,
2318                    build_tree_list (type, base));
2319 }
2320
2321 \f
2322 /* Debug info for C++ classes can get very large; try to avoid
2323    emitting it everywhere.
2324
2325    Note that this optimization wins even when the target supports
2326    BINCL (if only slightly), and reduces the amount of work for the
2327    linker.  */
2328
2329 void
2330 maybe_suppress_debug_info (t)
2331      tree t;
2332 {
2333   /* We can't do the usual TYPE_DECL_SUPPRESS_DEBUG thing with DWARF, which
2334      does not support name references between translation units.  It supports
2335      symbolic references between translation units, but only within a single
2336      executable or shared library.
2337
2338      For DWARF 2, we handle TYPE_DECL_SUPPRESS_DEBUG by pretending
2339      that the type was never defined, so we only get the members we
2340      actually define.  */
2341   if (write_symbols == DWARF_DEBUG || write_symbols == NO_DEBUG)
2342     return;
2343
2344   /* We might have set this earlier in cp_finish_decl.  */
2345   TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 0;
2346
2347   /* If we already know how we're handling this class, handle debug info
2348      the same way.  */
2349   if (CLASSTYPE_INTERFACE_KNOWN (t))
2350     {
2351       if (CLASSTYPE_INTERFACE_ONLY (t))
2352         TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 1;
2353       /* else don't set it.  */
2354     }
2355   /* If the class has a vtable, write out the debug info along with
2356      the vtable.  */
2357   else if (TYPE_CONTAINS_VPTR_P (t))
2358     TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 1;
2359
2360   /* Otherwise, just emit the debug info normally.  */
2361 }
2362
2363 /* Note that we want debugging information for a base class of a class
2364    whose vtable is being emitted.  Normally, this would happen because
2365    calling the constructor for a derived class implies calling the
2366    constructors for all bases, which involve initializing the
2367    appropriate vptr with the vtable for the base class; but in the
2368    presence of optimization, this initialization may be optimized
2369    away, so we tell finish_vtable_vardecl that we want the debugging
2370    information anyway.  */
2371
2372 static tree
2373 dfs_debug_mark (binfo, data)
2374      tree binfo;
2375      void *data ATTRIBUTE_UNUSED;
2376 {
2377   tree t = BINFO_TYPE (binfo);
2378
2379   CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2380
2381   return NULL_TREE;
2382 }
2383
2384 /* Returns BINFO if we haven't already noted that we want debugging
2385    info for this base class.  */
2386
2387 static tree
2388 dfs_debug_unmarkedp (binfo, data)
2389      tree binfo;
2390      void *data ATTRIBUTE_UNUSED;
2391 {
2392   return (!CLASSTYPE_DEBUG_REQUESTED (BINFO_TYPE (binfo))
2393           ? binfo : NULL_TREE);
2394 }
2395
2396 /* Write out the debugging information for TYPE, whose vtable is being
2397    emitted.  Also walk through our bases and note that we want to
2398    write out information for them.  This avoids the problem of not
2399    writing any debug info for intermediate basetypes whose
2400    constructors, and thus the references to their vtables, and thus
2401    the vtables themselves, were optimized away.  */
2402
2403 void
2404 note_debug_info_needed (type)
2405      tree type;
2406 {
2407   if (TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (type)))
2408     {
2409       TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (type)) = 0;
2410       rest_of_type_compilation (type, toplevel_bindings_p ());
2411     }
2412
2413   dfs_walk (TYPE_BINFO (type), dfs_debug_mark, dfs_debug_unmarkedp, 0);
2414 }
2415 \f
2416 /* Subroutines of push_class_decls ().  */
2417
2418 /* Returns 1 iff BINFO is a base we shouldn't really be able to see into,
2419    because it (or one of the intermediate bases) depends on template parms.  */
2420
2421 static int
2422 dependent_base_p (binfo)
2423      tree binfo;
2424 {
2425   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2426     {
2427       if (currently_open_class (TREE_TYPE (binfo)))
2428         break;
2429       if (uses_template_parms (TREE_TYPE (binfo)))
2430         return 1;
2431     }
2432   return 0;
2433 }
2434
2435 static void
2436 setup_class_bindings (name, type_binding_p)
2437      tree name;
2438      int type_binding_p;
2439 {
2440   tree type_binding = NULL_TREE;
2441   tree value_binding;
2442
2443   /* If we've already done the lookup for this declaration, we're
2444      done.  */
2445   if (IDENTIFIER_CLASS_VALUE (name))
2446     return;
2447
2448   /* First, deal with the type binding.  */
2449   if (type_binding_p)
2450     {
2451       type_binding = lookup_member (current_class_type, name,
2452                                     /*protect=*/2,
2453                                     /*want_type=*/1);
2454       if (TREE_CODE (type_binding) == TREE_LIST
2455           && TREE_TYPE (type_binding) == error_mark_node)
2456         /* NAME is ambiguous.  */
2457         push_class_level_binding (name, type_binding);
2458       else
2459         pushdecl_class_level (type_binding);
2460     }
2461
2462   /* Now, do the value binding.  */
2463   value_binding = lookup_member (current_class_type, name,
2464                                  /*protect=*/2,
2465                                  /*want_type=*/0);
2466
2467   if (type_binding_p
2468       && (TREE_CODE (value_binding) == TYPE_DECL
2469           || DECL_CLASS_TEMPLATE_P (value_binding)
2470           || (TREE_CODE (value_binding) == TREE_LIST
2471               && TREE_TYPE (value_binding) == error_mark_node
2472               && (TREE_CODE (TREE_VALUE (value_binding))
2473                   == TYPE_DECL))))
2474     /* We found a type-binding, even when looking for a non-type
2475        binding.  This means that we already processed this binding
2476        above.  */;
2477   else if (value_binding)
2478     {
2479       if (TREE_CODE (value_binding) == TREE_LIST
2480           && TREE_TYPE (value_binding) == error_mark_node)
2481         /* NAME is ambiguous.  */
2482         push_class_level_binding (name, value_binding);
2483       else
2484         {
2485           if (BASELINK_P (value_binding))
2486             /* NAME is some overloaded functions.  */
2487             value_binding = BASELINK_FUNCTIONS (value_binding);
2488           pushdecl_class_level (value_binding);
2489         }
2490     }
2491 }
2492
2493 /* Push class-level declarations for any names appearing in BINFO that
2494    are TYPE_DECLS.  */
2495
2496 static tree
2497 dfs_push_type_decls (binfo, data)
2498      tree binfo;
2499      void *data ATTRIBUTE_UNUSED;
2500 {
2501   tree type;
2502   tree fields;
2503
2504   type = BINFO_TYPE (binfo);
2505   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2506     if (DECL_NAME (fields) && TREE_CODE (fields) == TYPE_DECL
2507         && !(!same_type_p (type, current_class_type)
2508              && template_self_reference_p (type, fields)))
2509       setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/1);
2510
2511   /* We can't just use BINFO_MARKED because envelope_add_decl uses
2512      DERIVED_FROM_P, which calls get_base_distance.  */
2513   SET_BINFO_PUSHDECLS_MARKED (binfo);
2514
2515   return NULL_TREE;
2516 }
2517
2518 /* Push class-level declarations for any names appearing in BINFO that
2519    are not TYPE_DECLS.  */
2520
2521 static tree
2522 dfs_push_decls (binfo, data)
2523      tree binfo;
2524      void *data;
2525 {
2526   tree type;
2527   tree method_vec;
2528   int dep_base_p;
2529
2530   type = BINFO_TYPE (binfo);
2531   dep_base_p = (processing_template_decl && type != current_class_type
2532                 && dependent_base_p (binfo));
2533   if (!dep_base_p)
2534     {
2535       tree fields;
2536       for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2537         if (DECL_NAME (fields)
2538             && TREE_CODE (fields) != TYPE_DECL
2539             && TREE_CODE (fields) != USING_DECL
2540             && !DECL_ARTIFICIAL (fields))
2541           setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/0);
2542         else if (TREE_CODE (fields) == FIELD_DECL
2543                  && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
2544           dfs_push_decls (TYPE_BINFO (TREE_TYPE (fields)), data);
2545
2546       method_vec = (CLASS_TYPE_P (type)
2547                     ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE);
2548       if (method_vec)
2549         {
2550           tree *methods;
2551           tree *end;
2552
2553           /* Farm out constructors and destructors.  */
2554           end = TREE_VEC_END (method_vec);
2555
2556           for (methods = &TREE_VEC_ELT (method_vec, 2);
2557                *methods && methods != end;
2558                methods++)
2559             setup_class_bindings (DECL_NAME (OVL_CURRENT (*methods)),
2560                                   /*type_binding_p=*/0);
2561         }
2562     }
2563
2564   CLEAR_BINFO_PUSHDECLS_MARKED (binfo);
2565
2566   return NULL_TREE;
2567 }
2568
2569 /* When entering the scope of a class, we cache all of the
2570    fields that that class provides within its inheritance
2571    lattice.  Where ambiguities result, we mark them
2572    with `error_mark_node' so that if they are encountered
2573    without explicit qualification, we can emit an error
2574    message.  */
2575
2576 void
2577 push_class_decls (type)
2578      tree type;
2579 {
2580   search_stack = push_search_level (search_stack, &search_obstack);
2581
2582   /* Enter type declarations and mark.  */
2583   dfs_walk (TYPE_BINFO (type), dfs_push_type_decls, unmarked_pushdecls_p, 0);
2584
2585   /* Enter non-type declarations and unmark.  */
2586   dfs_walk (TYPE_BINFO (type), dfs_push_decls, marked_pushdecls_p, 0);
2587 }
2588
2589 /* Here's a subroutine we need because C lacks lambdas.  */
2590
2591 static tree
2592 dfs_unuse_fields (binfo, data)
2593      tree binfo;
2594      void *data ATTRIBUTE_UNUSED;
2595 {
2596   tree type = TREE_TYPE (binfo);
2597   tree fields;
2598
2599   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2600     {
2601       if (TREE_CODE (fields) != FIELD_DECL || DECL_ARTIFICIAL (fields))
2602         continue;
2603
2604       TREE_USED (fields) = 0;
2605       if (DECL_NAME (fields) == NULL_TREE
2606           && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
2607         unuse_fields (TREE_TYPE (fields));
2608     }
2609
2610   return NULL_TREE;
2611 }
2612
2613 void
2614 unuse_fields (type)
2615      tree type;
2616 {
2617   dfs_walk (TYPE_BINFO (type), dfs_unuse_fields, unmarkedp, 0);
2618 }
2619
2620 void
2621 pop_class_decls ()
2622 {
2623   /* We haven't pushed a search level when dealing with cached classes,
2624      so we'd better not try to pop it.  */
2625   if (search_stack)
2626     search_stack = pop_search_level (search_stack);
2627 }
2628
2629 void
2630 print_search_statistics ()
2631 {
2632 #ifdef GATHER_STATISTICS
2633   fprintf (stderr, "%d fields searched in %d[%d] calls to lookup_field[_1]\n",
2634            n_fields_searched, n_calls_lookup_field, n_calls_lookup_field_1);
2635   fprintf (stderr, "%d fnfields searched in %d calls to lookup_fnfields\n",
2636            n_outer_fields_searched, n_calls_lookup_fnfields);
2637   fprintf (stderr, "%d calls to get_base_type\n", n_calls_get_base_type);
2638 #else /* GATHER_STATISTICS */
2639   fprintf (stderr, "no search statistics\n");
2640 #endif /* GATHER_STATISTICS */
2641 }
2642
2643 void
2644 init_search_processing ()
2645 {
2646   gcc_obstack_init (&search_obstack);
2647 }
2648
2649 void
2650 reinit_search_statistics ()
2651 {
2652 #ifdef GATHER_STATISTICS
2653   n_fields_searched = 0;
2654   n_calls_lookup_field = 0, n_calls_lookup_field_1 = 0;
2655   n_calls_lookup_fnfields = 0, n_calls_lookup_fnfields_1 = 0;
2656   n_calls_get_base_type = 0;
2657   n_outer_fields_searched = 0;
2658   n_contexts_saved = 0;
2659 #endif /* GATHER_STATISTICS */
2660 }
2661
2662 static tree
2663 add_conversions (binfo, data)
2664      tree binfo;
2665      void *data;
2666 {
2667   int i;
2668   tree method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
2669   tree *conversions = (tree *) data;
2670
2671   /* Some builtin types have no method vector, not even an empty one.  */
2672   if (!method_vec)
2673     return NULL_TREE;
2674
2675   for (i = 2; i < TREE_VEC_LENGTH (method_vec); ++i)
2676     {
2677       tree tmp = TREE_VEC_ELT (method_vec, i);
2678       tree name;
2679
2680       if (!tmp || ! DECL_CONV_FN_P (OVL_CURRENT (tmp)))
2681         break;
2682
2683       name = DECL_NAME (OVL_CURRENT (tmp));
2684
2685       /* Make sure we don't already have this conversion.  */
2686       if (! IDENTIFIER_MARKED (name))
2687         {
2688           *conversions = tree_cons (binfo, tmp, *conversions);
2689           IDENTIFIER_MARKED (name) = 1;
2690         }
2691     }
2692   return NULL_TREE;
2693 }
2694
2695 /* Return a TREE_LIST containing all the non-hidden user-defined
2696    conversion functions for TYPE (and its base-classes).  The
2697    TREE_VALUE of each node is a FUNCTION_DECL or an OVERLOAD
2698    containing the conversion functions.  The TREE_PURPOSE is the BINFO
2699    from which the conversion functions in this node were selected.  */
2700
2701 tree
2702 lookup_conversions (type)
2703      tree type;
2704 {
2705   tree t;
2706   tree conversions = NULL_TREE;
2707
2708   if (COMPLETE_TYPE_P (type))
2709     bfs_walk (TYPE_BINFO (type), add_conversions, 0, &conversions);
2710
2711   for (t = conversions; t; t = TREE_CHAIN (t))
2712     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (t)))) = 0;
2713
2714   return conversions;
2715 }
2716
2717 struct overlap_info
2718 {
2719   tree compare_type;
2720   int found_overlap;
2721 };
2722
2723 /* Check whether the empty class indicated by EMPTY_BINFO is also present
2724    at offset 0 in COMPARE_TYPE, and set found_overlap if so.  */
2725
2726 static tree
2727 dfs_check_overlap (empty_binfo, data)
2728      tree empty_binfo;
2729      void *data;
2730 {
2731   struct overlap_info *oi = (struct overlap_info *) data;
2732   tree binfo;
2733   for (binfo = TYPE_BINFO (oi->compare_type);
2734        ;
2735        binfo = BINFO_BASETYPE (binfo, 0))
2736     {
2737       if (BINFO_TYPE (binfo) == BINFO_TYPE (empty_binfo))
2738         {
2739           oi->found_overlap = 1;
2740           break;
2741         }
2742       else if (BINFO_BASETYPES (binfo) == NULL_TREE)
2743         break;
2744     }
2745
2746   return NULL_TREE;
2747 }
2748
2749 /* Trivial function to stop base traversal when we find something.  */
2750
2751 static tree
2752 dfs_no_overlap_yet (binfo, data)
2753      tree binfo;
2754      void *data;
2755 {
2756   struct overlap_info *oi = (struct overlap_info *) data;
2757   return !oi->found_overlap ? binfo : NULL_TREE;
2758 }
2759
2760 /* Returns nonzero if EMPTY_TYPE or any of its bases can also be found at
2761    offset 0 in NEXT_TYPE.  Used in laying out empty base class subobjects.  */
2762
2763 int
2764 types_overlap_p (empty_type, next_type)
2765      tree empty_type, next_type;
2766 {
2767   struct overlap_info oi;
2768
2769   if (! IS_AGGR_TYPE (next_type))
2770     return 0;
2771   oi.compare_type = next_type;
2772   oi.found_overlap = 0;
2773   dfs_walk (TYPE_BINFO (empty_type), dfs_check_overlap,
2774             dfs_no_overlap_yet, &oi);
2775   return oi.found_overlap;
2776 }
2777
2778 /* Given a vtable VAR, determine which of the inherited classes the vtable
2779    inherits (in a loose sense) functions from.
2780
2781    FIXME: This does not work with the new ABI.  */
2782
2783 tree
2784 binfo_for_vtable (var)
2785      tree var;
2786 {
2787   tree main_binfo = TYPE_BINFO (DECL_CONTEXT (var));
2788   tree binfos = TYPE_BINFO_BASETYPES (BINFO_TYPE (main_binfo));
2789   int n_baseclasses = CLASSTYPE_N_BASECLASSES (BINFO_TYPE (main_binfo));
2790   int i;
2791
2792   for (i = 0; i < n_baseclasses; i++)
2793     {
2794       tree base_binfo = TREE_VEC_ELT (binfos, i);
2795       if (base_binfo != NULL_TREE && BINFO_VTABLE (base_binfo) == var)
2796         return base_binfo;
2797     }
2798
2799   /* If no secondary base classes matched, return the primary base, if
2800      there is one.  */
2801   if (CLASSTYPE_HAS_PRIMARY_BASE_P (BINFO_TYPE (main_binfo)))
2802     return get_primary_binfo (main_binfo);
2803
2804   return main_binfo;
2805 }
2806
2807 /* Returns the binfo of the first direct or indirect virtual base derived
2808    from BINFO, or NULL if binfo is not via virtual.  */
2809
2810 tree
2811 binfo_from_vbase (binfo)
2812      tree binfo;
2813 {
2814   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2815     {
2816       if (TREE_VIA_VIRTUAL (binfo))
2817         return binfo;
2818     }
2819   return NULL_TREE;
2820 }
2821
2822 /* Returns the binfo of the first direct or indirect virtual base derived
2823    from BINFO up to the TREE_TYPE, LIMIT, or NULL if binfo is not
2824    via virtual.  */
2825
2826 tree
2827 binfo_via_virtual (binfo, limit)
2828      tree binfo;
2829      tree limit;
2830 {
2831   for (; binfo && (!limit || !same_type_p (BINFO_TYPE (binfo), limit));
2832        binfo = BINFO_INHERITANCE_CHAIN (binfo))
2833     {
2834       if (TREE_VIA_VIRTUAL (binfo))
2835         return binfo;
2836     }
2837   return NULL_TREE;
2838 }
2839
2840 /* Returns the BINFO (if any) for the virtual baseclass T of the class
2841    C from the CLASSTYPE_VBASECLASSES list.  */
2842
2843 tree
2844 binfo_for_vbase (basetype, classtype)
2845      tree basetype;
2846      tree classtype;
2847 {
2848   tree binfo;
2849
2850   binfo = purpose_member (basetype, CLASSTYPE_VBASECLASSES (classtype));
2851   return binfo ? TREE_VALUE (binfo) : NULL_TREE;
2852 }