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