gcc/cp/search.c

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