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