gcc/cp/search.c

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