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