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