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