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