gcc/cp/search.c

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