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