contrib/gcc/cp/search.c

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