gcc/cp/search.c

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