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