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