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