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