contrib/gcc/cp/search.c

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