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