gcc/cp/search.c

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