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