gcc/cp/search.c

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