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