gcc/cp/pt.c

   1 /* Handle parameterized types (templates) for GNU C++.
   2    Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
   3    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* Known bugs or deficiencies include:
  23    * templates for class static data don't work (methods only)
  24    * duplicated method templates can crash the compiler
  25    * interface/impl data is taken from file defining the template
  26    * all methods must be provided in header files; can't use a source
  27      file that contains only the method templates and "just win"
  28    * method templates must be seen before the expansion of the
  29      class template is done
  30  */
  31
  32 #include "config.h"
  33 #include <stdio.h>
  34 #include "obstack.h"
  35
  36 #include "tree.h"
  37 #include "flags.h"
  38 #include "cp-tree.h"
  39 #include "decl.h"
  40 #include "parse.h"
  41 #include "lex.h"
  42 #include "output.h"
  43 #include "defaults.h"
  44
  45 extern struct obstack permanent_obstack;
  46
  47 extern int lineno;
  48 extern char *input_filename;
  49 struct pending_inline *pending_template_expansions;
  50
  51 int processing_template_decl;
  52 int processing_template_defn;
  53
  54 /* This is a kludge to handle instantiation of template methods that are
  55    used before their definition.  It should not be necessary after the
  56    template rewrite.  */
  57 static tree template_classes;
  58
  59 #define obstack_chunk_alloc xmalloc
  60 #define obstack_chunk_free free
  61
  62 static int unify ();
  63 static void add_pending_template ();
  64
  65 void overload_template_name (), pop_template_decls ();
  66
  67 /* We've got a template header coming up; set obstacks up to save the
  68    nodes created permanently.  (There might be cases with nested templates
  69    where we don't have to do this, but they aren't implemented, and it
  70    probably wouldn't be worth the effort.)  */
  71 void
  72 begin_template_parm_list ()
  73 {
  74   pushlevel (0);
  75   push_obstacks (&permanent_obstack, &permanent_obstack);
  76   pushlevel (0);
  77 }
  78
  79 /* Process information from new template parameter NEXT and append it to the
  80    LIST being built.  The rules for use of a template parameter type name
  81    by later parameters are not well-defined for us just yet.  However, the
  82    only way to avoid having to parse expressions of unknown complexity (and
  83    with tokens of unknown types) is to disallow it completely.  So for now,
  84    that is what is assumed.  */
  85 tree
  86 process_template_parm (list, next)
  87      tree list, next;
  88 {
  89   tree parm;
  90   tree decl = 0;
  91   tree defval;
  92   int is_type;
  93   parm = next;
  94   my_friendly_assert (TREE_CODE (parm) == TREE_LIST, 259);
  95   defval = TREE_PURPOSE (parm);
  96   parm = TREE_VALUE (parm);
  97   is_type = TREE_PURPOSE (parm) == class_type_node;
  98   if (!is_type)
  99     {
 100       tree tinfo = 0;
 101       my_friendly_assert (TREE_CODE (TREE_PURPOSE (parm)) == TREE_LIST, 260);
 102       /* is a const-param */
 103       parm = grokdeclarator (TREE_VALUE (parm), TREE_PURPOSE (parm),
 104                              PARM, 0, NULL_TREE, NULL_TREE);
 105       /* A template parameter is not modifiable.  */
 106       TREE_READONLY (parm) = 1;
 107       if (IS_AGGR_TYPE (TREE_TYPE (parm)))
 108         {
 109           sorry ("aggregate template parameter types");
 110           TREE_TYPE (parm) = void_type_node;
 111         }
 112       tinfo = make_node (TEMPLATE_CONST_PARM);
 113       my_friendly_assert (TREE_PERMANENT (tinfo), 260.5);
 114       if (TREE_PERMANENT (parm) == 0)
 115         {
 116           parm = copy_node (parm);
 117           TREE_PERMANENT (parm) = 1;
 118         }
 119       TREE_TYPE (tinfo) = TREE_TYPE (parm);
 120       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
 121       DECL_INITIAL (decl) = tinfo;
 122       DECL_INITIAL (parm) = tinfo;
 123     }
 124   else
 125     {
 126       tree t = make_node (TEMPLATE_TYPE_PARM);
 127       decl = build_decl (TYPE_DECL, TREE_VALUE (parm), t);
 128       TYPE_MAIN_DECL (t) = decl;
 129       parm = decl;
 130     }
 131   SET_DECL_ARTIFICIAL (decl);
 132   pushdecl (decl);
 133   parm = build_tree_list (defval, parm);
 134   return chainon (list, parm);
 135 }
 136
 137 /* The end of a template parameter list has been reached.  Process the
 138    tree list into a parameter vector, converting each parameter into a more
 139    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
 140    as PARM_DECLs.  */
 141
 142 tree
 143 end_template_parm_list (parms)
 144      tree parms;
 145 {
 146   int nparms = 0;
 147   int saw_default = 0;
 148   tree saved_parmlist;
 149   tree parm;
 150   for (parm = parms; parm; parm = TREE_CHAIN (parm))
 151     nparms++;
 152   saved_parmlist = make_tree_vec (nparms);
 153
 154   for (parm = parms, nparms = 0; parm; parm = TREE_CHAIN (parm), nparms++)
 155     {
 156       tree p = TREE_VALUE (parm);
 157       if (TREE_PURPOSE (parm))
 158         saw_default = 1;
 159       else if (saw_default)
 160         {
 161           error ("if a default argument is given for one template parameter");
 162           error ("default arguments must be given for all subsequent");
 163           error ("parameters as well");
 164         }
 165
 166       if (TREE_CODE (p) == TYPE_DECL)
 167         {
 168           tree t = TREE_TYPE (p);
 169           TEMPLATE_TYPE_SET_INFO (t, saved_parmlist, nparms);
 170         }
 171       else
 172         {
 173           tree tinfo = DECL_INITIAL (p);
 174           DECL_INITIAL (p) = NULL_TREE;
 175           TEMPLATE_CONST_SET_INFO (tinfo, saved_parmlist, nparms);
 176         }
 177       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
 178     }
 179   set_current_level_tags_transparency (1);
 180   processing_template_decl++;
 181   return saved_parmlist;
 182 }
 183
 184 /* end_template_decl is called after a template declaration is seen.
 185    D1 is template header; D2 is class_head_sans_basetype or a
 186    TEMPLATE_DECL with its DECL_RESULT field set.  */
 187 void
 188 end_template_decl (d1, d2, is_class, defn)
 189      tree d1, d2, is_class;
 190      int defn;
 191 {
 192   tree decl;
 193   struct template_info *tmpl;
 194
 195   tmpl = (struct template_info *) obstack_alloc (&permanent_obstack,
 196                                             sizeof (struct template_info));
 197   tmpl->text = 0;
 198   tmpl->length = 0;
 199   tmpl->aggr = is_class;
 200
 201   /* cloned from reinit_parse_for_template */
 202   tmpl->filename = input_filename;
 203   tmpl->lineno = lineno;
 204   tmpl->parm_vec = d1;          /* [eichin:19911015.2306EST] */
 205
 206   if (d2 == NULL_TREE || d2 == error_mark_node)
 207     {
 208       decl = 0;
 209       goto lose;
 210     }
 211
 212   if (is_class)
 213     {
 214       decl = build_lang_decl (TEMPLATE_DECL, d2, NULL_TREE);
 215       GNU_xref_decl (current_function_decl, decl);
 216     }
 217   else
 218     {
 219       if (TREE_CODE (d2) == TEMPLATE_DECL)
 220         decl = d2;
 221       else
 222         {
 223           /* Class destructor templates and operator templates are
 224              slipping past as non-template nodes.  Process them here, since
 225              I haven't figured out where to catch them earlier.  I could
 226              go do that, but it's a choice between getting that done and
 227              staying only N months behind schedule.  Sorry....  */
 228           enum tree_code code;
 229           my_friendly_assert (TREE_CODE (d2) == CALL_EXPR, 263);
 230           code = TREE_CODE (TREE_OPERAND (d2, 0));
 231           my_friendly_assert (code == BIT_NOT_EXPR
 232                   || code == OP_IDENTIFIER
 233                   || code == SCOPE_REF, 264);
 234           d2 = grokdeclarator (d2, NULL_TREE, MEMFUNCDEF, 0, NULL_TREE, NULL_TREE);
 235           decl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (d2),
 236                                   TREE_TYPE (d2));
 237           DECL_TEMPLATE_RESULT (decl) = d2;
 238           DECL_CONTEXT (decl) = DECL_CONTEXT (d2);
 239           DECL_CLASS_CONTEXT (decl) = DECL_CLASS_CONTEXT (d2);
 240           DECL_NAME (decl) = DECL_NAME (d2);
 241           TREE_TYPE (decl) = TREE_TYPE (d2);
 242           if (interface_unknown && flag_external_templates
 243               && ! flag_alt_external_templates
 244               && ! DECL_IN_SYSTEM_HEADER (decl))
 245             warn_if_unknown_interface (decl);
 246           TREE_PUBLIC (decl) = TREE_PUBLIC (d2) = flag_external_templates && !interface_unknown;
 247           DECL_EXTERNAL (decl) = (DECL_EXTERNAL (d2)
 248                                   && !(DECL_CLASS_CONTEXT (d2)
 249                                        && !DECL_THIS_EXTERN (d2)));
 250         }
 251
 252       /* All routines creating TEMPLATE_DECL nodes should now be using
 253          build_lang_decl, which will have set this up already.  */
 254       my_friendly_assert (DECL_LANG_SPECIFIC (decl) != 0, 265);
 255
 256       /* @@ Somewhere, permanent allocation isn't being used.  */
 257       if (! DECL_TEMPLATE_IS_CLASS (decl)
 258           && TREE_CODE (DECL_TEMPLATE_RESULT (decl)) == FUNCTION_DECL)
 259         {
 260           tree result = DECL_TEMPLATE_RESULT (decl);
 261           /* Will do nothing if allocation was already permanent.  */
 262           DECL_ARGUMENTS (result) = copy_to_permanent (DECL_ARGUMENTS (result));
 263         }
 264
 265       /* If this is for a method, there's an extra binding level here.  */
 266       if (DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl)) != NULL_TREE)
 267         {
 268           /* @@ Find out where this should be getting set!  */
 269           tree r = DECL_TEMPLATE_RESULT (decl);
 270           if (DECL_LANG_SPECIFIC (r) && DECL_CLASS_CONTEXT (r) == NULL_TREE)
 271             DECL_CLASS_CONTEXT (r) = DECL_CONTEXT (r);
 272         }
 273     }
 274   DECL_TEMPLATE_INFO (decl) = tmpl;
 275   DECL_TEMPLATE_PARMS (decl) = d1;
 276
 277   /* So that duplicate_decls can do the right thing.  */
 278   if (defn)
 279     DECL_INITIAL (decl) = error_mark_node;
 280
 281   /* If context of decl is non-null (i.e., method template), add it
 282      to the appropriate class template, and pop the binding levels.  */
 283   if (! is_class && DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl)) != NULL_TREE)
 284     {
 285       tree ctx = DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl));
 286       tree tmpl, t;
 287       my_friendly_assert (TREE_CODE (ctx) == UNINSTANTIATED_P_TYPE, 266);
 288       tmpl = UPT_TEMPLATE (ctx);
 289       for (t = DECL_TEMPLATE_MEMBERS (tmpl); t; t = TREE_CHAIN (t))
 290         if (TREE_PURPOSE (t) == DECL_NAME (decl)
 291             && duplicate_decls (decl, TREE_VALUE (t)))
 292           goto already_there;
 293       DECL_TEMPLATE_MEMBERS (tmpl) =
 294         perm_tree_cons (DECL_NAME (decl), decl, DECL_TEMPLATE_MEMBERS (tmpl));
 295     already_there:
 296       poplevel (0, 0, 0);
 297       poplevel (0, 0, 0);
 298     }
 299   /* Otherwise, go back to top level first, and push the template decl
 300      again there.  */
 301   else
 302     {
 303       poplevel (0, 0, 0);
 304       poplevel (0, 0, 0);
 305       pushdecl (decl);
 306     }
 307  lose:
 308 #if 0 /* It happens sometimes, with syntactic or semantic errors.
 309
 310          One specific case:
 311          template <class A, int X, int Y> class Foo { ... };
 312          template <class A, int X, int y> Foo<X,Y>::method (Foo& x) { ... }
 313          Note the missing "A" in the class containing "method".  */
 314   my_friendly_assert (global_bindings_p (), 267);
 315 #else
 316   while (! global_bindings_p ())
 317     poplevel (0, 0, 0);
 318 #endif
 319   pop_obstacks ();
 320   processing_template_decl--;
 321   (void) get_pending_sizes ();
 322 }
 323
 324 tree tsubst             PROTO ((tree, tree*, int, tree));
 325
 326 /* Convert all template arguments to their appropriate types, and return
 327    a vector containing the resulting values.  If any error occurs, return
 328    error_mark_node.  */
 329 static tree
 330 coerce_template_parms (parms, arglist, in_decl)
 331      tree parms, arglist;
 332      tree in_decl;
 333 {
 334   int nparms, nargs, i, lost = 0;
 335   tree vec;
 336
 337   if (arglist == NULL_TREE)
 338     nargs = 0;
 339   else if (TREE_CODE (arglist) == TREE_VEC)
 340     nargs = TREE_VEC_LENGTH (arglist);
 341   else
 342     nargs = list_length (arglist);
 343
 344   nparms = TREE_VEC_LENGTH (parms);
 345
 346   if (nargs > nparms
 347       || (nargs < nparms
 348           && TREE_PURPOSE (TREE_VEC_ELT (parms, nargs)) == NULL_TREE))
 349     {
 350       error ("incorrect number of parameters (%d, should be %d)",
 351              nargs, nparms);
 352       if (in_decl)
 353         cp_error_at ("in template expansion for decl `%D'", in_decl);
 354       return error_mark_node;
 355     }
 356
 357   if (arglist && TREE_CODE (arglist) == TREE_VEC)
 358     vec = copy_node (arglist);
 359   else
 360     {
 361       vec = make_tree_vec (nparms);
 362       for (i = 0; i < nparms; i++)
 363         {
 364           tree arg;
 365
 366           if (arglist)
 367             {
 368               arg = arglist;
 369               arglist = TREE_CHAIN (arglist);
 370
 371               if (arg == error_mark_node)
 372                 lost++;
 373               else
 374                 arg = TREE_VALUE (arg);
 375             }
 376           else
 377             arg = TREE_PURPOSE (TREE_VEC_ELT (parms, i));
 378
 379           TREE_VEC_ELT (vec, i) = arg;
 380         }
 381     }
 382   for (i = 0; i < nparms; i++)
 383     {
 384       tree arg = TREE_VEC_ELT (vec, i);
 385       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 386       tree val = 0;
 387       int is_type, requires_type;
 388
 389       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
 390       requires_type = TREE_CODE (parm) == TYPE_DECL;
 391       if (is_type != requires_type)
 392         {
 393           if (in_decl)
 394             cp_error ("type/value mismatch in template parameter list for `%D'",
 395                       in_decl);
 396           lost++;
 397           TREE_VEC_ELT (vec, i) = error_mark_node;
 398           continue;
 399         }
 400       if (is_type)
 401         val = groktypename (arg);
 402       else
 403         {
 404           tree t = tsubst (TREE_TYPE (parm), &TREE_VEC_ELT (vec, 0),
 405                            TREE_VEC_LENGTH (vec), in_decl);
 406           val = digest_init (t, arg, (tree *) 0);
 407
 408           if (val == error_mark_node)
 409             ;
 410
 411           /* 14.2: Other template-arguments must be constant-expressions,
 412              addresses of objects or functions with external linkage, or of
 413              static class members.  */
 414           else if (!TREE_CONSTANT (val))
 415             {
 416               cp_error ("non-const `%E' cannot be used as template argument",
 417                         arg);
 418               val = error_mark_node;
 419             }
 420           else if (POINTER_TYPE_P (TREE_TYPE (val))
 421                    && ! integer_zerop (val)
 422                    && TREE_CODE (TREE_TYPE (TREE_TYPE (val))) != OFFSET_TYPE
 423                    && TREE_CODE (TREE_TYPE (TREE_TYPE (val))) != METHOD_TYPE)
 424             {
 425               t = val;
 426               STRIP_NOPS (t);
 427               if (TREE_CODE (t) == ADDR_EXPR)
 428                 {
 429                   tree a = TREE_OPERAND (t, 0);
 430                   STRIP_NOPS (a);
 431                   if (TREE_CODE (a) == STRING_CST)
 432                     {
 433                       cp_error ("string literal %E is not a valid template argument", a);
 434                       error ("because it is the address of an object with static linkage");
 435                       val = error_mark_node;
 436                     }
 437                   else if (TREE_CODE (a) != VAR_DECL
 438                            && TREE_CODE (a) != FUNCTION_DECL)
 439                     goto bad;
 440                   else if (! DECL_PUBLIC (a))
 441                     {
 442                       cp_error ("address of non-extern `%E' cannot be used as template argument", a);
 443                       val = error_mark_node;
 444                     }
 445                 }
 446               else
 447                 {
 448                 bad:
 449                   cp_error ("`%E' is not a valid template argument", t);
 450                   error ("it must be %s%s with external linkage",
 451                          TREE_CODE (TREE_TYPE (val)) == POINTER_TYPE
 452                          ? "a pointer to " : "",
 453                          TREE_CODE (TREE_TYPE (TREE_TYPE (val))) == FUNCTION_TYPE
 454                          ? "a function" : "an object");
 455                   val = error_mark_node;
 456                 }
 457             }
 458         }
 459
 460       if (val == error_mark_node)
 461         lost++;
 462
 463       TREE_VEC_ELT (vec, i) = val;
 464     }
 465   if (lost)
 466     return error_mark_node;
 467   return vec;
 468 }
 469
 470 /* Given class template name and parameter list, produce a user-friendly name
 471    for the instantiation.  */
 472 static char *
 473 mangle_class_name_for_template (name, parms, arglist)
 474      char *name;
 475      tree parms, arglist;
 476 {
 477   static struct obstack scratch_obstack;
 478   static char *scratch_firstobj;
 479   int i, nparms;
 480
 481   if (!scratch_firstobj)
 482     {
 483       gcc_obstack_init (&scratch_obstack);
 484       scratch_firstobj = obstack_alloc (&scratch_obstack, 1);
 485     }
 486   else
 487     obstack_free (&scratch_obstack, scratch_firstobj);
 488
 489 #if 0
 490 #define buflen  sizeof(buf)
 491 #define check   if (bufp >= buf+buflen-1) goto too_long
 492 #define ccat(c) *bufp++=(c); check
 493 #define advance bufp+=strlen(bufp); check
 494 #define cat(s)  strncpy(bufp, s, buf+buflen-bufp-1); advance
 495 #else
 496 #define check
 497 #define ccat(c) obstack_1grow (&scratch_obstack, (c));
 498 #define advance
 499 #define cat(s)  obstack_grow (&scratch_obstack, (s), strlen (s))
 500 #endif
 501
 502   cat (name);
 503   ccat ('<');
 504   nparms = TREE_VEC_LENGTH (parms);
 505   my_friendly_assert (nparms == TREE_VEC_LENGTH (arglist), 268);
 506   for (i = 0; i < nparms; i++)
 507     {
 508       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 509       tree arg = TREE_VEC_ELT (arglist, i);
 510
 511       if (i)
 512         ccat (',');
 513
 514       if (TREE_CODE (parm) == TYPE_DECL)
 515         {
 516           cat (type_as_string (arg, 0));
 517           continue;
 518         }
 519       else
 520         my_friendly_assert (TREE_CODE (parm) == PARM_DECL, 269);
 521
 522       if (TREE_CODE (arg) == TREE_LIST)
 523         {
 524           /* New list cell was built because old chain link was in
 525              use.  */
 526           my_friendly_assert (TREE_PURPOSE (arg) == NULL_TREE, 270);
 527           arg = TREE_VALUE (arg);
 528         }
 529       /* No need to check arglist against parmlist here; we did that
 530          in coerce_template_parms, called from lookup_template_class.  */
 531       cat (expr_as_string (arg, 0));
 532     }
 533   {
 534     char *bufp = obstack_next_free (&scratch_obstack);
 535     int offset = 0;
 536     while (bufp[offset - 1] == ' ')
 537       offset--;
 538     obstack_blank_fast (&scratch_obstack, offset);
 539
 540     /* B<C<char> >, not B<C<char>> */
 541     if (bufp[offset - 1] == '>')
 542       ccat (' ');
 543   }
 544   ccat ('>');
 545   ccat ('\0');
 546   return (char *) obstack_base (&scratch_obstack);
 547
 548 #if 0
 549  too_long:
 550 #endif
 551   fatal ("out of (preallocated) string space creating template instantiation name");
 552   /* NOTREACHED */
 553   return NULL;
 554 }
 555
 556 /* Given an IDENTIFIER_NODE (type TEMPLATE_DECL) and a chain of
 557    parameters, find the desired type.
 558
 559    D1 is the PTYPENAME terminal, and ARGLIST is the list of arguments.
 560    Since ARGLIST is build on the decl_obstack, we must copy it here
 561    to keep it from being reclaimed when the decl storage is reclaimed.
 562
 563    IN_DECL, if non-NULL, is the template declaration we are trying to
 564    instantiate.  */
 565 tree
 566 lookup_template_class (d1, arglist, in_decl)
 567      tree d1, arglist;
 568      tree in_decl;
 569 {
 570   tree template, parmlist;
 571   char *mangled_name;
 572   tree id;
 573
 574   my_friendly_assert (TREE_CODE (d1) == IDENTIFIER_NODE, 272);
 575   template = IDENTIFIER_GLOBAL_VALUE (d1); /* XXX */
 576   if (! template)
 577     template = IDENTIFIER_CLASS_VALUE (d1);
 578   /* With something like `template <class T> class X class X { ... };'
 579      we could end up with D1 having nothing but an IDENTIFIER_LOCAL_VALUE.
 580      We don't want to do that, but we have to deal with the situation, so
 581      let's give them some syntax errors to chew on instead of a crash.  */
 582   if (! template)
 583     return error_mark_node;
 584   if (TREE_CODE (template) != TEMPLATE_DECL)
 585     {
 586       cp_error ("non-template type `%T' used as a template", d1);
 587       if (in_decl)
 588         cp_error_at ("for template declaration `%D'", in_decl);
 589       return error_mark_node;
 590     }
 591   parmlist = DECL_TEMPLATE_PARMS (template);
 592
 593   arglist = coerce_template_parms (parmlist, arglist, template);
 594   if (arglist == error_mark_node)
 595     return error_mark_node;
 596   if (uses_template_parms (arglist))
 597     {
 598       tree t = make_lang_type (UNINSTANTIATED_P_TYPE);
 599       tree d;
 600       id = make_anon_name ();
 601       d = build_decl (TYPE_DECL, id, t);
 602       TYPE_NAME (t) = d;
 603       TYPE_VALUES (t) = build_tree_list (template, arglist);
 604       pushdecl_top_level (d);
 605     }
 606   else
 607     {
 608       mangled_name = mangle_class_name_for_template (IDENTIFIER_POINTER (d1),
 609                                                      parmlist, arglist);
 610       id = get_identifier (mangled_name);
 611     }
 612   if (!IDENTIFIER_TEMPLATE (id))
 613     {
 614       arglist = copy_to_permanent (arglist);
 615       IDENTIFIER_TEMPLATE (id) = perm_tree_cons (template, arglist, NULL_TREE);
 616     }
 617   return id;
 618 }
 619 \f
 620 void
 621 push_template_decls (parmlist, arglist, class_level)
 622      tree parmlist, arglist;
 623      int class_level;
 624 {
 625   int i, nparms;
 626
 627   /* Don't want to push values into global context.  */
 628   if (!class_level)
 629     {
 630       pushlevel (1);
 631       declare_pseudo_global_level ();
 632     }
 633
 634   nparms = TREE_VEC_LENGTH (parmlist);
 635
 636   for (i = 0; i < nparms; i++)
 637     {
 638       int requires_type, is_type;
 639       tree parm = TREE_VALUE (TREE_VEC_ELT (parmlist, i));
 640       tree arg = TREE_VEC_ELT (arglist, i);
 641       tree decl = 0;
 642
 643       requires_type = TREE_CODE (parm) == TYPE_DECL;
 644       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
 645       if (is_type)
 646         {
 647           /* add typename to namespace */
 648           if (!requires_type)
 649             {
 650               error ("template use error: type provided where value needed");
 651               continue;
 652             }
 653           decl = arg;
 654           my_friendly_assert (TREE_CODE_CLASS (TREE_CODE (decl)) == 't', 273);
 655           decl = build_decl (TYPE_DECL, DECL_NAME (parm), decl);
 656         }
 657       else
 658         {
 659           /* add const decl to namespace */
 660           tree val;
 661           tree parmtype;
 662           if (requires_type)
 663             {
 664               error ("template use error: value provided where type needed");
 665               continue;
 666             }
 667           parmtype = tsubst (TREE_TYPE (parm), &TREE_VEC_ELT (arglist, 0),
 668                              TREE_VEC_LENGTH (arglist), NULL_TREE);
 669           val = digest_init (parmtype, arg, (tree *) 0);
 670           if (val != error_mark_node)
 671             {
 672               decl = build_decl (CONST_DECL, DECL_NAME (parm),
 673                                  parmtype);
 674               DECL_INITIAL (decl) = val;
 675               TREE_READONLY (decl) = 1;
 676             }
 677         }
 678       if (decl != 0)
 679         {
 680           SET_DECL_ARTIFICIAL (decl);
 681           layout_decl (decl, 0);
 682           if (class_level)
 683             pushdecl_class_level (decl);
 684           else
 685             pushdecl (decl);
 686         }
 687     }
 688 }
 689
 690 void
 691 pop_template_decls (parmlist, arglist, class_level)
 692      tree parmlist, arglist;
 693      int class_level;
 694 {
 695   if (!class_level)
 696     poplevel (0, 0, 0);
 697 }
 698 \f
 699 /* Should be defined in parse.h.  */
 700 extern int yychar;
 701
 702 int
 703 uses_template_parms (t)
 704      tree t;
 705 {
 706   if (!t)
 707     return 0;
 708   switch (TREE_CODE (t))
 709     {
 710     case INDIRECT_REF:
 711     case COMPONENT_REF:
 712       /* We assume that the object must be instantiated in order to build
 713          the COMPONENT_REF, so we test only whether the type of the
 714          COMPONENT_REF uses template parms.  */
 715       return uses_template_parms (TREE_TYPE (t));
 716
 717     case IDENTIFIER_NODE:
 718       if (!IDENTIFIER_TEMPLATE (t))
 719         return 0;
 720       return uses_template_parms (TREE_VALUE (IDENTIFIER_TEMPLATE (t)));
 721
 722       /* aggregates of tree nodes */
 723     case TREE_VEC:
 724       {
 725         int i = TREE_VEC_LENGTH (t);
 726         while (i--)
 727           if (uses_template_parms (TREE_VEC_ELT (t, i)))
 728             return 1;
 729         return 0;
 730       }
 731     case TREE_LIST:
 732       if (uses_template_parms (TREE_PURPOSE (t))
 733           || uses_template_parms (TREE_VALUE (t)))
 734         return 1;
 735       return uses_template_parms (TREE_CHAIN (t));
 736
 737       /* constructed type nodes */
 738     case POINTER_TYPE:
 739     case REFERENCE_TYPE:
 740       return uses_template_parms (TREE_TYPE (t));
 741     case RECORD_TYPE:
 742       if (TYPE_PTRMEMFUNC_FLAG (t))
 743         return uses_template_parms (TYPE_PTRMEMFUNC_FN_TYPE (t));
 744     case UNION_TYPE:
 745       if (!TYPE_NAME (t))
 746         return 0;
 747       if (!TYPE_IDENTIFIER (t))
 748         return 0;
 749       return uses_template_parms (TYPE_IDENTIFIER (t));
 750     case FUNCTION_TYPE:
 751       if (uses_template_parms (TYPE_ARG_TYPES (t)))
 752         return 1;
 753       return uses_template_parms (TREE_TYPE (t));
 754     case ARRAY_TYPE:
 755       if (uses_template_parms (TYPE_DOMAIN (t)))
 756         return 1;
 757       return uses_template_parms (TREE_TYPE (t));
 758     case OFFSET_TYPE:
 759       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
 760         return 1;
 761       return uses_template_parms (TREE_TYPE (t));
 762     case METHOD_TYPE:
 763       if (uses_template_parms (TYPE_METHOD_BASETYPE (t)))
 764         return 1;
 765       if (uses_template_parms (TYPE_ARG_TYPES (t)))
 766         return 1;
 767       return uses_template_parms (TREE_TYPE (t));
 768
 769       /* decl nodes */
 770     case TYPE_DECL:
 771       return uses_template_parms (DECL_NAME (t));
 772     case FUNCTION_DECL:
 773       if (uses_template_parms (TREE_TYPE (t)))
 774         return 1;
 775       /* fall through */
 776     case VAR_DECL:
 777     case PARM_DECL:
 778       /* ??? What about FIELD_DECLs?  */
 779       /* The type of a decl can't use template parms if the name of the
 780          variable doesn't, because it's impossible to resolve them.  So
 781          ignore the type field for now.  */
 782       if (DECL_CONTEXT (t) && uses_template_parms (DECL_CONTEXT (t)))
 783         return 1;
 784       if (uses_template_parms (TREE_TYPE (t)))
 785         {
 786           error ("template parms used where they can't be resolved");
 787         }
 788       return 0;
 789
 790     case CALL_EXPR:
 791       return uses_template_parms (TREE_TYPE (t));
 792     case ADDR_EXPR:
 793       return uses_template_parms (TREE_OPERAND (t, 0));
 794
 795       /* template parm nodes */
 796     case TEMPLATE_TYPE_PARM:
 797     case TEMPLATE_CONST_PARM:
 798       return 1;
 799
 800       /* simple type nodes */
 801     case INTEGER_TYPE:
 802       if (uses_template_parms (TYPE_MIN_VALUE (t)))
 803         return 1;
 804       return uses_template_parms (TYPE_MAX_VALUE (t));
 805
 806     case REAL_TYPE:
 807     case VOID_TYPE:
 808     case ENUMERAL_TYPE:
 809     case BOOLEAN_TYPE:
 810       return 0;
 811
 812       /* constants */
 813     case INTEGER_CST:
 814     case REAL_CST:
 815     case STRING_CST:
 816       return 0;
 817
 818     case ERROR_MARK:
 819       /* Non-error_mark_node ERROR_MARKs are bad things.  */
 820       my_friendly_assert (t == error_mark_node, 274);
 821       /* NOTREACHED */
 822       return 0;
 823
 824     case UNINSTANTIATED_P_TYPE:
 825       return 1;
 826
 827     case CONSTRUCTOR:
 828       if (TREE_TYPE (t) && TYPE_PTRMEMFUNC_P (TREE_TYPE (t)))
 829         return uses_template_parms (TYPE_PTRMEMFUNC_FN_TYPE (TREE_TYPE (t)));
 830       /* else fall through */
 831
 832     default:
 833       switch (TREE_CODE_CLASS (TREE_CODE (t)))
 834         {
 835         case '1':
 836         case '2':
 837         case '3':
 838         case '<':
 839           {
 840             int i;
 841             for (i = tree_code_length[(int) TREE_CODE (t)]; --i >= 0;)
 842               if (uses_template_parms (TREE_OPERAND (t, i)))
 843                 return 1;
 844             return 0;
 845           }
 846         default:
 847           break;
 848         }
 849       sorry ("testing %s for template parms",
 850              tree_code_name [(int) TREE_CODE (t)]);
 851       my_friendly_abort (82);
 852       /* NOTREACHED */
 853       return 0;
 854     }
 855 }
 856
 857 void
 858 instantiate_member_templates (classname)
 859      tree classname;
 860 {
 861   tree t;
 862   tree id = classname;
 863   tree members = DECL_TEMPLATE_MEMBERS (TREE_PURPOSE (IDENTIFIER_TEMPLATE (id)));
 864
 865   for (t = members; t; t = TREE_CHAIN (t))
 866     {
 867       tree parmvec, type, classparms, tdecl, t2;
 868       int nparms, xxx = 0, i;
 869
 870       my_friendly_assert (TREE_VALUE (t) != NULL_TREE, 275);
 871       my_friendly_assert (TREE_CODE (TREE_VALUE (t)) == TEMPLATE_DECL, 276);
 872       /* @@ Should verify that class parm list is a list of
 873          distinct template parameters, and covers all the template
 874          parameters.  */
 875       tdecl = TREE_VALUE (t);
 876       type = DECL_CONTEXT (DECL_TEMPLATE_RESULT (tdecl));
 877       classparms = UPT_PARMS (type);
 878       nparms = TREE_VEC_LENGTH (classparms);
 879       parmvec = make_tree_vec (nparms);
 880       for (i = 0; i < nparms; i++)
 881         TREE_VEC_ELT (parmvec, i) = NULL_TREE;
 882       switch (unify (DECL_TEMPLATE_PARMS (tdecl),
 883                      &TREE_VEC_ELT (parmvec, 0), nparms,
 884                      type, IDENTIFIER_TYPE_VALUE (classname),
 885                      &xxx))
 886         {
 887         case 0:
 888           /* Success -- well, no inconsistency, at least.  */
 889           for (i = 0; i < nparms; i++)
 890             if (TREE_VEC_ELT (parmvec, i) == NULL_TREE)
 891               goto failure;
 892           t2 = instantiate_template (tdecl,
 893                                      &TREE_VEC_ELT (parmvec, 0));
 894           type = IDENTIFIER_TYPE_VALUE (id);
 895           my_friendly_assert (type != 0, 277);
 896           break;
 897         case 1:
 898           /* Failure.  */
 899         failure:
 900           cp_error_at ("type unification error instantiating `%D'", tdecl);
 901           cp_error ("while instantiating members of `%T'", classname);
 902
 903           continue /* loop of members */;
 904         default:
 905           /* Eek, a bug.  */
 906           my_friendly_abort (83);
 907         }
 908     }
 909 }
 910
 911 static struct tinst_level *current_tinst_level = 0;
 912 static struct tinst_level *free_tinst_level = 0;
 913 static int tinst_depth = 0;
 914 int max_tinst_depth = 17;
 915
 916 int
 917 push_tinst_level (name)
 918      tree name;
 919 {
 920   struct tinst_level *new;
 921   tree global = IDENTIFIER_GLOBAL_VALUE (name);
 922
 923   if (tinst_depth >= max_tinst_depth)
 924     {
 925       error ("template instantiation depth exceeds maximum of %d",
 926              max_tinst_depth);
 927       cp_error ("  instantiating `%D'", name);
 928       return 0;
 929     }
 930
 931   if (free_tinst_level)
 932     {
 933       new = free_tinst_level;
 934       free_tinst_level = new->next;
 935     }
 936   else
 937     new = (struct tinst_level *) xmalloc (sizeof (struct tinst_level));
 938
 939   new->classname = name;
 940   if (global)
 941     {
 942       new->line = DECL_SOURCE_LINE (global);
 943       new->file = DECL_SOURCE_FILE (global);
 944     }
 945   else
 946     {
 947       new->line = lineno;
 948       new->file = input_filename;
 949     }
 950   new->next = current_tinst_level;
 951   current_tinst_level = new;
 952   ++tinst_depth;
 953   return 1;
 954 }
 955
 956 void
 957 pop_tinst_level ()
 958 {
 959   struct tinst_level *old = current_tinst_level;
 960
 961   current_tinst_level = old->next;
 962   old->next = free_tinst_level;
 963   free_tinst_level = old;
 964   --tinst_depth;
 965 }
 966
 967 struct tinst_level *
 968 tinst_for_decl ()
 969 {
 970   struct tinst_level *p = current_tinst_level;
 971
 972   if (p)
 973     for (; p->next ; p = p->next )
 974       ;
 975   return p;
 976 }
 977
 978 tree
 979 instantiate_class_template (classname, setup_parse)
 980      tree classname;
 981      int setup_parse;
 982 {
 983   struct template_info *template_info;
 984   tree template, t1;
 985
 986   if (classname == error_mark_node)
 987     return error_mark_node;
 988
 989   my_friendly_assert (TREE_CODE (classname) == IDENTIFIER_NODE, 278);
 990   template = IDENTIFIER_TEMPLATE (classname);
 991
 992   if (IDENTIFIER_HAS_TYPE_VALUE (classname))
 993     {
 994       tree type = IDENTIFIER_TYPE_VALUE (classname);
 995       if (TREE_CODE (type) == UNINSTANTIATED_P_TYPE)
 996         return type;
 997       if (TYPE_BEING_DEFINED (type)
 998           || TYPE_SIZE (type)
 999           || CLASSTYPE_USE_TEMPLATE (type) != 0)
1000         return type;
1001     }
1002
1003   /* If IDENTIFIER_LOCAL_VALUE is already set on this template classname
1004      (it's something like `foo<int>'), that means we're already working on
1005      the instantiation for it.  Normally, a classname comes in with nothing
1006      but its IDENTIFIER_TEMPLATE slot set.  If we were to try to instantiate
1007      this again, we'd get a redeclaration error.  Since we're already working
1008      on it, we'll pass back this classname's TYPE_DECL (it's the value of
1009      the classname's IDENTIFIER_LOCAL_VALUE).  Only do this if we're setting
1010      things up for the parser, though---if we're just trying to instantiate
1011      it (e.g., via tsubst) we can trip up cuz it may not have an
1012      IDENTIFIER_TYPE_VALUE when it will need one.  */
1013   if (setup_parse && IDENTIFIER_LOCAL_VALUE (classname))
1014     return IDENTIFIER_LOCAL_VALUE (classname);
1015
1016   if (uses_template_parms (classname))
1017     {
1018       if (!TREE_TYPE (classname))
1019         {
1020           tree t = make_lang_type (RECORD_TYPE);
1021           tree d = build_decl (TYPE_DECL, classname, t);
1022           DECL_NAME (d) = classname;
1023           TYPE_NAME (t) = d;
1024           pushdecl (d);
1025         }
1026       return NULL_TREE;
1027     }
1028
1029   t1 = TREE_PURPOSE (template);
1030   my_friendly_assert (TREE_CODE (t1) == TEMPLATE_DECL, 279);
1031
1032   /* If a template is declared but not defined, accept it; don't crash.
1033      Later uses requiring the definition will be flagged as errors by
1034      other code.  Thanks to niklas@appli.se for this bug fix.  */
1035   if (DECL_TEMPLATE_INFO (t1)->text == 0)
1036     setup_parse = 0;
1037
1038   push_to_top_level ();
1039   template_info = DECL_TEMPLATE_INFO (t1);
1040   if (setup_parse && push_tinst_level (classname))
1041     {
1042       push_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (template)),
1043                            TREE_VALUE (template), 0);
1044       set_current_level_tags_transparency (1);
1045       feed_input (template_info->text, template_info->length, (struct obstack *)0);
1046       lineno = template_info->lineno;
1047       input_filename = template_info->filename;
1048       /* Get interface/implementation back in sync.  */
1049       extract_interface_info ();
1050       overload_template_name (classname, 0);
1051       /* Kludge so that we don't get screwed by our own base classes.  */
1052       TYPE_BEING_DEFINED (TREE_TYPE (classname)) = 1;
1053       yychar = PRE_PARSED_CLASS_DECL;
1054       yylval.ttype = classname;
1055       processing_template_defn++;
1056       if (!flag_external_templates)
1057         interface_unknown++;
1058       template_classes
1059         = perm_tree_cons (classname, NULL_TREE, template_classes);
1060     }
1061   else
1062     {
1063       tree t, decl, id, tmpl;
1064
1065       id = classname;
1066       tmpl = TREE_PURPOSE (IDENTIFIER_TEMPLATE (id));
1067       t = xref_tag (DECL_TEMPLATE_INFO (tmpl)->aggr, id, NULL_TREE, 0);
1068       my_friendly_assert (TREE_CODE (t) == RECORD_TYPE
1069                           || TREE_CODE (t) == UNION_TYPE, 280);
1070
1071       /* Now, put a copy of the decl in global scope, to avoid
1072        * recursive expansion.  */
1073       decl = IDENTIFIER_LOCAL_VALUE (id);
1074       if (!decl)
1075         decl = IDENTIFIER_CLASS_VALUE (id);
1076       if (decl)
1077         {
1078           my_friendly_assert (TREE_CODE (decl) == TYPE_DECL, 281);
1079           /* We'd better make sure we're on the permanent obstack or else
1080            * we'll get a "friendly" abort 124 in pushdecl.  Perhaps a
1081            * copy_to_permanent would be sufficient here, but then a
1082            * sharing problem might occur.  I don't know -- niklas@appli.se */
1083           push_obstacks (&permanent_obstack, &permanent_obstack);
1084           pushdecl_top_level (copy_node (decl));
1085           pop_obstacks ();
1086         }
1087       pop_from_top_level ();
1088     }
1089
1090   return NULL_TREE;
1091 }
1092
1093 static int
1094 list_eq (t1, t2)
1095      tree t1, t2;
1096 {
1097   if (t1 == NULL_TREE)
1098     return t2 == NULL_TREE;
1099   if (t2 == NULL_TREE)
1100     return 0;
1101   /* Don't care if one declares its arg const and the other doesn't -- the
1102      main variant of the arg type is all that matters.  */
1103   if (TYPE_MAIN_VARIANT (TREE_VALUE (t1))
1104       != TYPE_MAIN_VARIANT (TREE_VALUE (t2)))
1105     return 0;
1106   return list_eq (TREE_CHAIN (t1), TREE_CHAIN (t2));
1107 }
1108
1109 static tree
1110 lookup_nested_type_by_name (ctype, name)
1111         tree ctype, name;
1112 {
1113   tree t;
1114
1115   for (t = CLASSTYPE_TAGS (ctype); t; t = TREE_CHAIN (t))
1116     {
1117       if (name == TREE_PURPOSE (t))
1118         return TREE_VALUE (t);
1119     }
1120   return NULL_TREE;
1121 }
1122
1123 static tree
1124 search_nested_type_in_tmpl (tmpl, type)
1125         tree tmpl, type;
1126 {
1127   tree t;
1128
1129   if (tmpl == NULL || TYPE_CONTEXT(type) == NULL)
1130     return tmpl;
1131   t = search_nested_type_in_tmpl (tmpl, TYPE_CONTEXT(type));
1132   if (t == NULL) return t;
1133   t = lookup_nested_type_by_name(t, DECL_NAME(TYPE_NAME(type)));
1134   return t;
1135 }
1136
1137 tree
1138 tsubst (t, args, nargs, in_decl)
1139      tree t, *args;
1140      int nargs;
1141      tree in_decl;
1142 {
1143   tree type;
1144
1145   if (t == NULL_TREE || t == error_mark_node)
1146     return t;
1147
1148   type = TREE_TYPE (t);
1149   if (type
1150       /* Minor optimization.
1151          ?? Are these really the most frequent cases?  Is the savings
1152          significant?  */
1153       && type != integer_type_node
1154       && type != void_type_node
1155       && type != char_type_node)
1156     type = tsubst (type, args, nargs, in_decl);
1157
1158   switch (TREE_CODE (t))
1159     {
1160     case RECORD_TYPE:
1161       if (TYPE_PTRMEMFUNC_P (t))
1162         return build_ptrmemfunc_type
1163           (tsubst (TYPE_PTRMEMFUNC_FN_TYPE (t), args, nargs, in_decl));
1164
1165       /* else fall through */
1166
1167     case ERROR_MARK:
1168     case IDENTIFIER_NODE:
1169     case OP_IDENTIFIER:
1170     case VOID_TYPE:
1171     case REAL_TYPE:
1172     case ENUMERAL_TYPE:
1173     case BOOLEAN_TYPE:
1174     case INTEGER_CST:
1175     case REAL_CST:
1176     case STRING_CST:
1177     case UNION_TYPE:
1178       return t;
1179
1180     case INTEGER_TYPE:
1181       if (t == integer_type_node)
1182         return t;
1183
1184       if (TREE_CODE (TYPE_MIN_VALUE (t)) == INTEGER_CST
1185           && TREE_CODE (TYPE_MAX_VALUE (t)) == INTEGER_CST)
1186         return t;
1187       return build_index_2_type
1188         (tsubst (TYPE_MIN_VALUE (t), args, nargs, in_decl),
1189          tsubst (TYPE_MAX_VALUE (t), args, nargs, in_decl));
1190
1191     case TEMPLATE_TYPE_PARM:
1192       {
1193         tree arg = args[TEMPLATE_TYPE_IDX (t)];
1194         return cp_build_type_variant
1195           (arg, TYPE_READONLY (arg) || TYPE_READONLY (t),
1196            TYPE_VOLATILE (arg) || TYPE_VOLATILE (t));
1197       }
1198
1199     case TEMPLATE_CONST_PARM:
1200       return args[TEMPLATE_CONST_IDX (t)];
1201
1202     case FUNCTION_DECL:
1203       {
1204         tree r;
1205         tree fnargs, result;
1206
1207         if (type == TREE_TYPE (t)
1208             && (DECL_CONTEXT (t) == NULL_TREE
1209                 || TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) != 't'))
1210           return t;
1211         fnargs = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
1212         result = tsubst (DECL_RESULT (t), args, nargs, t);
1213         if (DECL_CONTEXT (t) != NULL_TREE
1214             && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't')
1215           {
1216             /* Look it up in that class, and return the decl node there,
1217                instead of creating a new one.  */
1218             tree ctx, methods, name, method;
1219             int n_methods;
1220             int i, found = 0;
1221
1222             name = DECL_NAME (t);
1223             ctx = tsubst (DECL_CONTEXT (t), args, nargs, t);
1224             methods = CLASSTYPE_METHOD_VEC (ctx);
1225             if (methods == NULL_TREE)
1226               /* No methods at all -- no way this one can match.  */
1227               goto no_match;
1228             n_methods = TREE_VEC_LENGTH (methods);
1229
1230             r = NULL_TREE;
1231
1232             if (!strncmp (OPERATOR_TYPENAME_FORMAT,
1233                           IDENTIFIER_POINTER (name),
1234                           sizeof (OPERATOR_TYPENAME_FORMAT) - 1))
1235               {
1236                 /* Type-conversion operator.  Reconstruct the name, in
1237                    case it's the name of one of the template's parameters.  */
1238                 name = build_typename_overload (TREE_TYPE (type));
1239               }
1240
1241             if (DECL_CONTEXT (t) != NULL_TREE
1242                 && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't'
1243                 && constructor_name (DECL_CONTEXT (t)) == DECL_NAME (t))
1244               name = constructor_name (ctx);
1245
1246             if (DECL_CONSTRUCTOR_P (t) && TYPE_USES_VIRTUAL_BASECLASSES (ctx))
1247               {
1248                 /* Since we didn't know that this class had virtual bases until after
1249                    we instantiated it, we have to recreate the arguments to this
1250                    constructor, as otherwise it would miss the __in_chrg parameter.  */
1251                 tree newtype, parm;
1252                 tree parms = TREE_CHAIN (TYPE_ARG_TYPES (type));
1253                 parms = hash_tree_chain (integer_type_node, parms);
1254                 newtype = build_cplus_method_type (ctx,
1255                                                    TREE_TYPE (type),
1256                                                    parms);
1257                 newtype = build_type_variant (newtype,
1258                                               TYPE_READONLY (type),
1259                                               TYPE_VOLATILE (type));
1260                 type = newtype;
1261
1262                 fnargs = copy_node (DECL_ARGUMENTS (t));
1263                 TREE_CHAIN (fnargs) = TREE_CHAIN (DECL_ARGUMENTS (t));
1264
1265                 /* In this case we need "in-charge" flag saying whether
1266                    this constructor is responsible for initialization
1267                    of virtual baseclasses or not.  */
1268                 parm = build_decl (PARM_DECL, in_charge_identifier, integer_type_node);
1269                 /* Mark the artificial `__in_chrg' parameter as "artificial".  */
1270                 SET_DECL_ARTIFICIAL (parm);
1271                 DECL_ARG_TYPE (parm) = integer_type_node;
1272                 DECL_REGISTER (parm) = 1;
1273                 TREE_CHAIN (parm) = TREE_CHAIN (fnargs);
1274                 TREE_CHAIN (fnargs) = parm;
1275
1276                 fnargs = tsubst (fnargs, args, nargs, t);
1277               }
1278 #if 0
1279             fprintf (stderr, "\nfor function %s in class %s:\n",
1280                      IDENTIFIER_POINTER (name),
1281                      IDENTIFIER_POINTER (TYPE_IDENTIFIER (ctx)));
1282 #endif
1283             for (i = 0; i < n_methods; i++)
1284               {
1285                 int pass;
1286
1287                 method = TREE_VEC_ELT (methods, i);
1288                 if (method == NULL_TREE || DECL_NAME (method) != name)
1289                   continue;
1290
1291                 pass = 0;
1292               maybe_error:
1293                 for (; method; method = DECL_CHAIN (method))
1294                   {
1295                     my_friendly_assert (TREE_CODE (method) == FUNCTION_DECL,
1296                                         282);
1297                     if (! comptypes (type, TREE_TYPE (method), 1))
1298                       {
1299                         tree mtype = TREE_TYPE (method);
1300                         tree t1, t2;
1301
1302                         /* Keep looking for a method that matches
1303                            perfectly.  This takes care of the problem
1304                            where destructors (which have implicit int args)
1305                            look like constructors which have an int arg.  */
1306                         if (pass == 0)
1307                           continue;
1308
1309                         t1 = TYPE_ARG_TYPES (mtype);
1310                         t2 = TYPE_ARG_TYPES (type);
1311                         if (TREE_CODE (mtype) == FUNCTION_TYPE)
1312                           t2 = TREE_CHAIN (t2);
1313
1314                         if (list_eq (t1, t2))
1315                           {
1316                             if (TREE_CODE (mtype) == FUNCTION_TYPE)
1317                               {
1318                                 tree newtype;
1319                                 newtype = build_function_type (TREE_TYPE (type),
1320                                                                TYPE_ARG_TYPES (type));
1321                                 newtype = build_type_variant (newtype,
1322                                                               TYPE_READONLY (type),
1323                                                               TYPE_VOLATILE (type));
1324                                 type = newtype;
1325                                 if (TREE_TYPE (type) != TREE_TYPE (mtype))
1326                                   goto maybe_bad_return_type;
1327                               }
1328                             else if (TYPE_METHOD_BASETYPE (mtype)
1329                                      == TYPE_METHOD_BASETYPE (type))
1330                               {
1331                                 /* Types didn't match, but arg types and
1332                                    `this' do match, so the return type is
1333                                    all that should be messing it up.  */
1334                               maybe_bad_return_type:
1335                                 if (TREE_TYPE (type) != TREE_TYPE (mtype))
1336                                   error ("inconsistent return types for method `%s' in class `%s'",
1337                                          IDENTIFIER_POINTER (name),
1338                                          IDENTIFIER_POINTER (TYPE_IDENTIFIER (ctx)));
1339                               }
1340                             r = method;
1341                             break;
1342                           }
1343                         found = 1;
1344                         continue;
1345                       }
1346 #if 0
1347                     fprintf (stderr, "\tfound %s\n\n",
1348                              IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (method)));
1349 #endif
1350                     if (DECL_ARTIFICIAL (method))
1351                       {
1352                         cp_error ("template for method `%D' which has default implementation in class `%T'", name, ctx);
1353                         if (in_decl)
1354                           cp_error_at ("in attempt to instantiate `%D' declared at this point in file", in_decl);
1355                         return error_mark_node;
1356                       }
1357
1358                     if (DECL_ARGUMENTS (method)
1359                         && ! TREE_PERMANENT (DECL_ARGUMENTS (method)))
1360                       /* @@ Is this early enough?  Might we want to do
1361                          this instead while processing the expansion?    */
1362                       DECL_ARGUMENTS (method)
1363                         = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
1364                     r = method;
1365                     break;
1366                   }
1367                 if (r == NULL_TREE && pass == 0)
1368                   {
1369                     pass = 1;
1370                     method = TREE_VEC_ELT (methods, i);
1371                     goto maybe_error;
1372                   }
1373               }
1374             if (r == NULL_TREE)
1375               {
1376               no_match:
1377                 cp_error
1378                   (found
1379                    ? "template for method `%D' doesn't match any in class `%T'"
1380                    : "method `%D' not found in class `%T'", name, ctx);
1381                 if (in_decl)
1382                   cp_error_at ("in attempt to instantiate `%D' declared at this point in file", in_decl);
1383                 return error_mark_node;
1384               }
1385           }
1386         else
1387           {
1388             r = DECL_NAME (t);
1389             {
1390               tree decls;
1391               int got_it = 0;
1392
1393               decls = lookup_name_nonclass (r);
1394               if (decls == NULL_TREE)
1395                 /* no match */;
1396               else if (TREE_CODE (decls) == TREE_LIST)
1397                 for (decls = TREE_VALUE (decls); decls ;
1398                      decls = DECL_CHAIN (decls))
1399                   {
1400                     if (TREE_CODE (decls) == FUNCTION_DECL
1401                         && TREE_TYPE (decls) == type)
1402                       {
1403                         got_it = 1;
1404                         r = decls;
1405                         break;
1406                       }
1407                   }
1408               else
1409                 {
1410                   tree val = decls;
1411                   decls = NULL_TREE;
1412                   if (TREE_CODE (val) == FUNCTION_DECL
1413                       && TREE_TYPE (val) == type)
1414                     {
1415                       got_it = 1;
1416                       r = val;
1417                     }
1418                 }
1419
1420               if (!got_it)
1421                 {
1422                   tree a = build_decl_overload (r, TYPE_VALUES (type),
1423                                                 DECL_CONTEXT (t) != NULL_TREE);
1424                   r = build_lang_decl (FUNCTION_DECL, r, type);
1425                   DECL_ASSEMBLER_NAME (r) = a;
1426                 }
1427               else if (TREE_STATIC (r))
1428                 {
1429                   /* This overrides the template version, use it. */
1430                   return r;
1431                 }
1432             }
1433           }
1434         TREE_PUBLIC (r) = 1;
1435         DECL_EXTERNAL (r) = 1;
1436         TREE_STATIC (r) = 0;
1437         DECL_INTERFACE_KNOWN (r) = 0;
1438         DECL_INLINE (r) = DECL_INLINE (t);
1439         DECL_THIS_INLINE (r) = DECL_THIS_INLINE (t);
1440         TREE_READONLY (r) = TREE_READONLY (t);
1441         TREE_THIS_VOLATILE (r) = TREE_THIS_VOLATILE (t);
1442         {
1443 #if 0                           /* Maybe later.  -jason  */
1444           struct tinst_level *til = tinst_for_decl();
1445
1446           /* should always be true under new approach */
1447           if (til)
1448             {
1449               DECL_SOURCE_FILE (r) = til->file;
1450               DECL_SOURCE_LINE (r) = til->line;
1451             }
1452           else
1453 #endif
1454             {
1455               DECL_SOURCE_FILE (r) = DECL_SOURCE_FILE (t);
1456               DECL_SOURCE_LINE (r) = DECL_SOURCE_LINE (t);
1457             }
1458         }
1459         DECL_CLASS_CONTEXT (r) = tsubst (DECL_CLASS_CONTEXT (t), args, nargs, t);
1460         make_decl_rtl (r, NULL_PTR, 1);
1461         DECL_ARGUMENTS (r) = fnargs;
1462         DECL_RESULT (r) = result;
1463 #if 0
1464         if (DECL_CONTEXT (t) == NULL_TREE
1465             || TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) != 't')
1466           push_overloaded_decl_top_level (r, 0);
1467 #endif
1468         return r;
1469       }
1470
1471     case PARM_DECL:
1472       {
1473         tree r;
1474         r = build_decl (PARM_DECL, DECL_NAME (t), type);
1475         DECL_INITIAL (r) = TREE_TYPE (r);
1476         DECL_ARTIFICIAL (r) = DECL_ARTIFICIAL (t);
1477 #ifdef PROMOTE_PROTOTYPES
1478         if ((TREE_CODE (type) == INTEGER_TYPE
1479              || TREE_CODE (type) == ENUMERAL_TYPE)
1480             && TYPE_PRECISION (type) < TYPE_PRECISION (integer_type_node))
1481           DECL_ARG_TYPE (r) = integer_type_node;
1482 #endif
1483         if (TREE_CHAIN (t))
1484           TREE_CHAIN (r) = tsubst (TREE_CHAIN (t), args, nargs, TREE_CHAIN (t));
1485         return r;
1486       }
1487
1488     case TREE_LIST:
1489       {
1490         tree purpose, value, chain, result;
1491         int via_public, via_virtual, via_protected;
1492
1493         if (t == void_list_node)
1494           return t;
1495
1496         via_public = TREE_VIA_PUBLIC (t);
1497         via_protected = TREE_VIA_PROTECTED (t);
1498         via_virtual = TREE_VIA_VIRTUAL (t);
1499
1500         purpose = TREE_PURPOSE (t);
1501         if (purpose)
1502           purpose = tsubst (purpose, args, nargs, in_decl);
1503         value = TREE_VALUE (t);
1504         if (value)
1505           value = tsubst (value, args, nargs, in_decl);
1506         chain = TREE_CHAIN (t);
1507         if (chain && chain != void_type_node)
1508           chain = tsubst (chain, args, nargs, in_decl);
1509         if (purpose == TREE_PURPOSE (t)
1510             && value == TREE_VALUE (t)
1511             && chain == TREE_CHAIN (t))
1512           return t;
1513         result = hash_tree_cons (via_public, via_virtual, via_protected,
1514                                  purpose, value, chain);
1515         TREE_PARMLIST (result) = TREE_PARMLIST (t);
1516         return result;
1517       }
1518     case TREE_VEC:
1519       {
1520         int len = TREE_VEC_LENGTH (t), need_new = 0, i;
1521         tree *elts = (tree *) alloca (len * sizeof (tree));
1522         bzero ((char *) elts, len * sizeof (tree));
1523
1524         for (i = 0; i < len; i++)
1525           {
1526             elts[i] = tsubst (TREE_VEC_ELT (t, i), args, nargs, in_decl);
1527             if (elts[i] != TREE_VEC_ELT (t, i))
1528               need_new = 1;
1529           }
1530
1531         if (!need_new)
1532           return t;
1533
1534         t = make_tree_vec (len);
1535         for (i = 0; i < len; i++)
1536           TREE_VEC_ELT (t, i) = elts[i];
1537         return t;
1538       }
1539     case POINTER_TYPE:
1540     case REFERENCE_TYPE:
1541       {
1542         tree r;
1543         enum tree_code code;
1544         if (type == TREE_TYPE (t))
1545           return t;
1546
1547         code = TREE_CODE (t);
1548         if (code == POINTER_TYPE)
1549           r = build_pointer_type (type);
1550         else
1551           r = build_reference_type (type);
1552         r = cp_build_type_variant (r, TYPE_READONLY (t), TYPE_VOLATILE (t));
1553         /* Will this ever be needed for TYPE_..._TO values?  */
1554         layout_type (r);
1555         return r;
1556       }
1557     case OFFSET_TYPE:
1558       return build_offset_type
1559         (tsubst (TYPE_OFFSET_BASETYPE (t), args, nargs, in_decl), type);
1560     case FUNCTION_TYPE:
1561     case METHOD_TYPE:
1562       {
1563         tree values = TYPE_ARG_TYPES (t);
1564         tree context = TYPE_CONTEXT (t);
1565         tree new_value;
1566
1567         /* Don't bother recursing if we know it won't change anything.  */
1568         if (values != void_list_node)
1569           values = tsubst (values, args, nargs, in_decl);
1570         if (context)
1571           context = tsubst (context, args, nargs, in_decl);
1572         /* Could also optimize cases where return value and
1573            values have common elements (e.g., T min(const &T, const T&).  */
1574
1575         /* If the above parameters haven't changed, just return the type.  */
1576         if (type == TREE_TYPE (t)
1577             && values == TYPE_VALUES (t)
1578             && context == TYPE_CONTEXT (t))
1579           return t;
1580
1581         /* Construct a new type node and return it.  */
1582         if (TREE_CODE (t) == FUNCTION_TYPE
1583             && context == NULL_TREE)
1584           {
1585             new_value = build_function_type (type, values);
1586           }
1587         else if (context == NULL_TREE)
1588           {
1589             tree base = tsubst (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (t))),
1590                                 args, nargs, in_decl);
1591             new_value = build_cplus_method_type (base, type,
1592                                                  TREE_CHAIN (values));
1593           }
1594         else
1595           {
1596             new_value = make_node (TREE_CODE (t));
1597             TREE_TYPE (new_value) = type;
1598             TYPE_CONTEXT (new_value) = context;
1599             TYPE_VALUES (new_value) = values;
1600             TYPE_SIZE (new_value) = TYPE_SIZE (t);
1601             TYPE_ALIGN (new_value) = TYPE_ALIGN (t);
1602             TYPE_MODE (new_value) = TYPE_MODE (t);
1603             if (TYPE_METHOD_BASETYPE (t))
1604               TYPE_METHOD_BASETYPE (new_value) = tsubst (TYPE_METHOD_BASETYPE (t),
1605                                                          args, nargs, in_decl);
1606             /* Need to generate hash value.  */
1607             my_friendly_abort (84);
1608           }
1609         new_value = build_type_variant (new_value,
1610                                         TYPE_READONLY (t),
1611                                         TYPE_VOLATILE (t));
1612         return new_value;
1613       }
1614     case ARRAY_TYPE:
1615       {
1616         tree domain = tsubst (TYPE_DOMAIN (t), args, nargs, in_decl);
1617         tree r;
1618         if (type == TREE_TYPE (t) && domain == TYPE_DOMAIN (t))
1619           return t;
1620         r = build_cplus_array_type (type, domain);
1621         return r;
1622       }
1623
1624     case UNINSTANTIATED_P_TYPE:
1625       {
1626         int nparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (UPT_TEMPLATE (t)));
1627         tree argvec = make_tree_vec (nparms);
1628         tree parmvec = UPT_PARMS (t);
1629         int i;
1630         tree id, rt;
1631         for (i = 0; i < nparms; i++)
1632           TREE_VEC_ELT (argvec, i) = tsubst (TREE_VEC_ELT (parmvec, i),
1633                                              args, nargs, in_decl);
1634         id = lookup_template_class (DECL_NAME (UPT_TEMPLATE (t)), argvec, NULL_TREE);
1635         if (! IDENTIFIER_HAS_TYPE_VALUE (id)) {
1636           instantiate_class_template(id, 0);
1637           /* set up pending_classes */
1638           add_pending_template (id);
1639
1640           TYPE_MAIN_VARIANT (IDENTIFIER_TYPE_VALUE (id)) =
1641             IDENTIFIER_TYPE_VALUE (id);
1642         }
1643         rt = IDENTIFIER_TYPE_VALUE (id);
1644
1645         /* kung: this part handles nested type in template definition */
1646
1647         if ( !ANON_AGGRNAME_P (DECL_NAME(TYPE_NAME(t))))
1648           {
1649             rt = search_nested_type_in_tmpl (rt, t);
1650           }
1651
1652         return build_type_variant (rt, TYPE_READONLY (t), TYPE_VOLATILE (t));
1653       }
1654
1655     case MINUS_EXPR:
1656     case PLUS_EXPR:
1657       return fold (build (TREE_CODE (t), TREE_TYPE (t),
1658                           tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1659                           tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl)));
1660
1661     case NEGATE_EXPR:
1662     case NOP_EXPR:
1663       return fold (build1 (TREE_CODE (t), TREE_TYPE (t),
1664                            tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl)));
1665
1666     default:
1667       sorry ("use of `%s' in function template",
1668              tree_code_name [(int) TREE_CODE (t)]);
1669       return error_mark_node;
1670     }
1671 }
1672
1673 tree
1674 instantiate_template (tmpl, targ_ptr)
1675      tree tmpl, *targ_ptr;
1676 {
1677   tree targs, fndecl;
1678   int i, len;
1679   struct pending_inline *p;
1680   struct template_info *t;
1681   struct obstack *old_fmp_obstack;
1682   extern struct obstack *function_maybepermanent_obstack;
1683
1684   push_obstacks (&permanent_obstack, &permanent_obstack);
1685   old_fmp_obstack = function_maybepermanent_obstack;
1686   function_maybepermanent_obstack = &permanent_obstack;
1687
1688   my_friendly_assert (TREE_CODE (tmpl) == TEMPLATE_DECL, 283);
1689   len = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (tmpl));
1690
1691   i = len;
1692   while (i--)
1693     targ_ptr[i] = copy_to_permanent (targ_ptr[i]);
1694
1695   for (fndecl = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1696        fndecl; fndecl = TREE_CHAIN (fndecl))
1697     {
1698       tree *t1 = &TREE_VEC_ELT (TREE_PURPOSE (fndecl), 0);
1699       for (i = len - 1; i >= 0; i--)
1700         if (simple_cst_equal (t1[i], targ_ptr[i]) <= 0)
1701           goto no_match;
1702
1703       /* Here, we have a match.  */
1704       fndecl = TREE_VALUE (fndecl);
1705       goto exit;
1706
1707     no_match:
1708       ;
1709     }
1710
1711   targs = make_tree_vec (len);
1712   i = len;
1713   while (i--)
1714     TREE_VEC_ELT (targs, i) = targ_ptr[i];
1715
1716   /* substitute template parameters */
1717   fndecl = tsubst (DECL_RESULT (tmpl), targ_ptr,
1718                    TREE_VEC_LENGTH (targs), tmpl);
1719
1720   if (fndecl == error_mark_node)
1721     goto exit;
1722
1723   assemble_external (fndecl);
1724
1725   /* If it's a static member fn in the template, we need to change it
1726      into a FUNCTION_TYPE and chop off its this pointer.  */
1727   if (TREE_CODE (TREE_TYPE (DECL_RESULT (tmpl))) == METHOD_TYPE
1728       && DECL_STATIC_FUNCTION_P (fndecl))
1729     {
1730       revert_static_member_fn (&DECL_RESULT (tmpl), NULL, NULL);
1731       /* Chop off the this pointer that grokclassfn so kindly added
1732          for us (it didn't know yet if the fn was static or not).  */
1733       DECL_ARGUMENTS (fndecl) = TREE_CHAIN (DECL_ARGUMENTS (fndecl));
1734     }
1735
1736   t = DECL_TEMPLATE_INFO (tmpl);
1737
1738   /* If we have a preexisting version of this function, don't expand
1739      the template version, use the other instead.  */
1740   if (TREE_STATIC (fndecl) || DECL_TEMPLATE_SPECIALIZATION (fndecl))
1741     {
1742       SET_DECL_TEMPLATE_SPECIALIZATION (fndecl);
1743       p = (struct pending_inline *)0;
1744     }
1745   else if (t->text)
1746     {
1747       SET_DECL_IMPLICIT_INSTANTIATION (fndecl);
1748       repo_template_used (fndecl);
1749       p = (struct pending_inline *) permalloc (sizeof (struct pending_inline));
1750       p->parm_vec = t->parm_vec;
1751       p->bindings = targs;
1752       p->can_free = 0;
1753       p->deja_vu = 0;
1754       p->buf = t->text;
1755       p->len = t->length;
1756       p->fndecl = fndecl;
1757       {
1758         int l = lineno;
1759         char * f = input_filename;
1760
1761         lineno = p->lineno = t->lineno;
1762         input_filename = p->filename = t->filename;
1763
1764         extract_interface_info ();
1765
1766         if (interface_unknown && flag_external_templates)
1767           {
1768             if (DECL_CLASS_CONTEXT (fndecl)
1769                 && CLASSTYPE_INTERFACE_KNOWN (DECL_CLASS_CONTEXT (fndecl)))
1770               {
1771                 interface_unknown = 0;
1772                 interface_only
1773                   = CLASSTYPE_INTERFACE_ONLY (DECL_CLASS_CONTEXT (fndecl));
1774               }
1775             else if (! DECL_IN_SYSTEM_HEADER (tmpl))
1776               warn_if_unknown_interface (tmpl);
1777           }
1778
1779         if (interface_unknown || ! flag_external_templates)
1780           p->interface = 1;             /* unknown */
1781         else
1782           p->interface = interface_only ? 0 : 2;
1783
1784         lineno = l;
1785         input_filename = f;
1786
1787         extract_interface_info ();
1788       }
1789     }
1790   else
1791     p = (struct pending_inline *)0;
1792
1793   DECL_TEMPLATE_INSTANTIATIONS (tmpl) =
1794     tree_cons (targs, fndecl, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1795
1796   if (p == (struct pending_inline *)0)
1797     {
1798       /* do nothing */
1799     }
1800   else if (DECL_INLINE (fndecl))
1801     {
1802       DECL_PENDING_INLINE_INFO (fndecl) = p;
1803       p->next = pending_inlines;
1804       pending_inlines = p;
1805     }
1806   else
1807     {
1808       p->next = pending_template_expansions;
1809       pending_template_expansions = p;
1810     }
1811  exit:
1812   function_maybepermanent_obstack = old_fmp_obstack;
1813   pop_obstacks ();
1814
1815   return fndecl;
1816 }
1817
1818 /* classlevel should now never be true.  jason 4/12/94 */
1819 void
1820 undo_template_name_overload (id, classlevel)
1821      tree id;
1822      int classlevel;
1823 {
1824   tree template;
1825
1826   template = IDENTIFIER_TEMPLATE (id);
1827   if (!template)
1828     return;
1829
1830 #if 0 /* not yet, should get fixed properly later */
1831   poplevel (0, 0, 0);
1832 #endif
1833 #if 1 /* XXX */
1834   /* This was a botch... See `overload_template_name' just below.  */
1835   if (!classlevel)
1836     poplevel (0, 0, 0);
1837 #endif
1838 }
1839
1840 /* classlevel should now never be true.  jason 4/12/94 */
1841 void
1842 overload_template_name (id, classlevel)
1843      tree id;
1844      int classlevel;
1845 {
1846   tree template, t, decl;
1847   struct template_info *tinfo;
1848
1849   my_friendly_assert (TREE_CODE (id) == IDENTIFIER_NODE, 284);
1850   template = IDENTIFIER_TEMPLATE (id);
1851   if (!template)
1852     return;
1853
1854   template = TREE_PURPOSE (template);
1855   tinfo = DECL_TEMPLATE_INFO (template);
1856   template = DECL_NAME (template);
1857   my_friendly_assert (template != NULL_TREE, 285);
1858
1859 #if 1 /* XXX */
1860   /* This was a botch... names of templates do not get their own private
1861      scopes.  Rather, they should go into the binding level already created
1862      by push_template_decls.  Except that there isn't one of those for
1863      specializations.  */
1864   if (!classlevel)
1865     {
1866       pushlevel (1);
1867       declare_pseudo_global_level ();
1868     }
1869 #endif
1870
1871   t = xref_tag (tinfo->aggr, id, NULL_TREE, 1);
1872   my_friendly_assert (TREE_CODE (t) == RECORD_TYPE
1873                       || TREE_CODE (t) == UNION_TYPE
1874                       || TREE_CODE (t) == UNINSTANTIATED_P_TYPE, 286);
1875
1876   decl = build_decl (TYPE_DECL, template, t);
1877   SET_DECL_ARTIFICIAL (decl);
1878
1879 #if 0 /* fix this later */
1880   /* We don't want to call here if the work has already been done.  */
1881   t = (classlevel
1882        ? IDENTIFIER_CLASS_VALUE (template)
1883        : IDENTIFIER_LOCAL_VALUE (template));
1884   if (t
1885       && TREE_CODE (t) == TYPE_DECL
1886       && TREE_TYPE (t) == t)
1887     my_friendly_abort (85);
1888 #endif
1889
1890   if (classlevel)
1891     pushdecl_class_level (decl);
1892   else
1893     pushdecl (decl);
1894
1895 #if 0 /* This seems bogus to me; if it isn't, explain why.  (jason) */
1896   /* Fake this for now, just to make dwarfout.c happy.  It will have to
1897      be done in a proper way later on.  */
1898   DECL_CONTEXT (decl) = t;
1899 #endif
1900 }
1901
1902 extern struct pending_input *to_be_restored;
1903
1904 /* NAME is the IDENTIFIER value of a PRE_PARSED_CLASS_DECL. */
1905 void
1906 end_template_instantiation (name)
1907      tree name;
1908 {
1909   tree t, decl;
1910
1911   processing_template_defn--;
1912   if (!flag_external_templates)
1913     interface_unknown--;
1914
1915   /* Restore the old parser input state.  */
1916   if (yychar == YYEMPTY)
1917     yychar = yylex ();
1918   if (yychar != END_OF_SAVED_INPUT)
1919     error ("parse error at end of class template");
1920   else
1921     {
1922       restore_pending_input (to_be_restored);
1923       to_be_restored = 0;
1924     }
1925
1926   /* Our declarations didn't get stored in the global slot, since
1927      there was a (supposedly tags-transparent) scope in between.  */
1928   t = IDENTIFIER_TYPE_VALUE (name);
1929   my_friendly_assert (t != NULL_TREE
1930                       && TREE_CODE_CLASS (TREE_CODE (t)) == 't',
1931                       287);
1932   SET_CLASSTYPE_IMPLICIT_INSTANTIATION (t);
1933   /* Make methods of template classes static, unless
1934      -fexternal-templates is given.  */
1935   if (!flag_external_templates)
1936     SET_CLASSTYPE_INTERFACE_UNKNOWN (t);
1937   decl = IDENTIFIER_GLOBAL_VALUE (name);
1938   my_friendly_assert (TREE_CODE (decl) == TYPE_DECL, 288);
1939
1940   undo_template_name_overload (name, 0);
1941   t = IDENTIFIER_TEMPLATE (name);
1942   pop_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (t)), TREE_VALUE (t),
1943                       0);
1944   /* This will fix up the type-value field.  */
1945   pushdecl (decl);
1946   pop_from_top_level ();
1947
1948 #ifdef DWARF_DEBUGGING_INFO
1949   if (write_symbols == DWARF_DEBUG && TREE_CODE (decl) == TYPE_DECL)
1950     {
1951       /* We just completed the definition of a new file-scope type,
1952          so we can go ahead and output debug-info for it now.  */
1953       TYPE_STUB_DECL (TREE_TYPE (decl)) = decl;
1954       rest_of_type_compilation (TREE_TYPE (decl), 1);
1955     }
1956 #endif /* DWARF_DEBUGGING_INFO */
1957
1958   /* Restore interface/implementation settings.  */
1959   extract_interface_info ();
1960 }
1961 \f
1962 /* Store away the text of an template.  */
1963
1964 void
1965 reinit_parse_for_template (yychar, d1, d2)
1966      int yychar;
1967      tree d1, d2;
1968 {
1969   struct template_info *template_info;
1970   extern struct obstack inline_text_obstack; /* see comment in lex.c */
1971
1972   if (d2 == NULL_TREE || d2 == error_mark_node)
1973     {
1974     lose:
1975       /* @@ Should use temp obstack, and discard results.  */
1976       reinit_parse_for_block (yychar, &inline_text_obstack, 1);
1977       return;
1978     }
1979
1980   if (TREE_CODE (d2) == IDENTIFIER_NODE)
1981     d2 = IDENTIFIER_GLOBAL_VALUE (d2);
1982   if (!d2)
1983     goto lose;
1984   template_info = DECL_TEMPLATE_INFO (d2);
1985   if (!template_info)
1986     {
1987       template_info = (struct template_info *) permalloc (sizeof (struct template_info));
1988       bzero ((char *) template_info, sizeof (struct template_info));
1989       DECL_TEMPLATE_INFO (d2) = template_info;
1990     }
1991   template_info->filename = input_filename;
1992   template_info->lineno = lineno;
1993   reinit_parse_for_block (yychar, &inline_text_obstack, 1);
1994   template_info->text = obstack_base (&inline_text_obstack);
1995   template_info->length = obstack_object_size (&inline_text_obstack);
1996   obstack_finish (&inline_text_obstack);
1997   template_info->parm_vec = d1;
1998 }
1999
2000 /* Type unification.
2001
2002    We have a function template signature with one or more references to
2003    template parameters, and a parameter list we wish to fit to this
2004    template.  If possible, produce a list of parameters for the template
2005    which will cause it to fit the supplied parameter list.
2006
2007    Return zero for success, 2 for an incomplete match that doesn't resolve
2008    all the types, and 1 for complete failure.  An error message will be
2009    printed only for an incomplete match.
2010
2011    TPARMS[NTPARMS] is an array of template parameter types;
2012    TARGS[NTPARMS] is the array of template parameter values.  PARMS is
2013    the function template's signature (using TEMPLATE_PARM_IDX nodes),
2014    and ARGS is the argument list we're trying to match against it.
2015
2016    If SUBR is 1, we're being called recursively (to unify the arguments of
2017    a function or method parameter of a function template), so don't zero
2018    out targs and don't fail on an incomplete match. */
2019
2020 int
2021 type_unification (tparms, targs, parms, args, nsubsts, subr)
2022      tree tparms, *targs, parms, args;
2023      int *nsubsts, subr;
2024 {
2025   tree parm, arg;
2026   int i;
2027   int ntparms = TREE_VEC_LENGTH (tparms);
2028
2029   my_friendly_assert (TREE_CODE (tparms) == TREE_VEC, 289);
2030   my_friendly_assert (TREE_CODE (parms) == TREE_LIST, 290);
2031   /* ARGS could be NULL (via a call from parse.y to
2032      build_x_function_call).  */
2033   if (args)
2034     my_friendly_assert (TREE_CODE (args) == TREE_LIST, 291);
2035   my_friendly_assert (ntparms > 0, 292);
2036
2037   if (!subr)
2038     bzero ((char *) targs, sizeof (tree) * ntparms);
2039
2040   while (parms
2041          && parms != void_list_node
2042          && args
2043          && args != void_list_node)
2044     {
2045       parm = TREE_VALUE (parms);
2046       parms = TREE_CHAIN (parms);
2047       arg = TREE_VALUE (args);
2048       args = TREE_CHAIN (args);
2049
2050       if (arg == error_mark_node)
2051         return 1;
2052       if (arg == unknown_type_node)
2053         return 1;
2054
2055       if (! uses_template_parms (parm)
2056           && TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
2057         {
2058           if (can_convert_arg (parm, TREE_TYPE (arg), arg))
2059             continue;
2060           return 1;
2061         }
2062
2063 #if 0
2064       if (TREE_CODE (arg) == VAR_DECL)
2065         arg = TREE_TYPE (arg);
2066       else if (TREE_CODE_CLASS (TREE_CODE (arg)) == 'e')
2067         arg = TREE_TYPE (arg);
2068 #else
2069       if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
2070         {
2071           my_friendly_assert (TREE_TYPE (arg) != NULL_TREE, 293);
2072           if (TREE_CODE (arg) == TREE_LIST
2073               && TREE_TYPE (arg) == unknown_type_node
2074               && TREE_CODE (TREE_VALUE (arg)) == TEMPLATE_DECL)
2075             {
2076               int nsubsts, ntparms;
2077               tree *targs;
2078
2079               /* Have to back unify here */
2080               arg = TREE_VALUE (arg);
2081               nsubsts = 0;
2082               ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (arg));
2083               targs = (tree *) alloca (sizeof (tree) * ntparms);
2084               parm = tree_cons (NULL_TREE, parm, NULL_TREE);
2085               return type_unification (DECL_TEMPLATE_PARMS (arg), targs,
2086                                        TYPE_ARG_TYPES (TREE_TYPE (arg)),
2087                                        parm, &nsubsts, 0);
2088             }
2089           arg = TREE_TYPE (arg);
2090         }
2091 #endif
2092       if (TREE_CODE (arg) == REFERENCE_TYPE)
2093         arg = TREE_TYPE (arg);
2094
2095       if (TREE_CODE (parm) != REFERENCE_TYPE)
2096         {
2097           if (TREE_CODE (arg) == FUNCTION_TYPE
2098               || TREE_CODE (arg) == METHOD_TYPE)
2099             arg = build_pointer_type (arg);
2100           else if (TREE_CODE (arg) == ARRAY_TYPE)
2101             arg = build_pointer_type (TREE_TYPE (arg));
2102           else
2103             arg = TYPE_MAIN_VARIANT (arg);
2104         }
2105
2106       switch (unify (tparms, targs, ntparms, parm, arg, nsubsts))
2107         {
2108         case 0:
2109           break;
2110         case 1:
2111           return 1;
2112         }
2113     }
2114   /* Fail if we've reached the end of the parm list, and more args
2115      are present, and the parm list isn't variadic.  */
2116   if (args && args != void_list_node && parms == void_list_node)
2117     return 1;
2118   /* Fail if parms are left and they don't have default values.  */
2119   if (parms
2120       && parms != void_list_node
2121       && TREE_PURPOSE (parms) == NULL_TREE)
2122     return 1;
2123   if (!subr)
2124     for (i = 0; i < ntparms; i++)
2125       if (!targs[i])
2126         {
2127           error ("incomplete type unification");
2128           return 2;
2129         }
2130   return 0;
2131 }
2132
2133 /* Tail recursion is your friend.  */
2134 static int
2135 unify (tparms, targs, ntparms, parm, arg, nsubsts)
2136      tree tparms, *targs, parm, arg;
2137      int *nsubsts, ntparms;
2138 {
2139   int idx;
2140
2141   /* I don't think this will do the right thing with respect to types.
2142      But the only case I've seen it in so far has been array bounds, where
2143      signedness is the only information lost, and I think that will be
2144      okay.  */
2145   while (TREE_CODE (parm) == NOP_EXPR)
2146     parm = TREE_OPERAND (parm, 0);
2147
2148   if (arg == error_mark_node)
2149     return 1;
2150   if (arg == unknown_type_node)
2151     return 1;
2152   if (arg == parm)
2153     return 0;
2154
2155   switch (TREE_CODE (parm))
2156     {
2157     case TEMPLATE_TYPE_PARM:
2158       (*nsubsts)++;
2159       if (TEMPLATE_TYPE_TPARMLIST (parm) != tparms)
2160         {
2161           error ("mixed template headers?!");
2162           my_friendly_abort (86);
2163           return 1;
2164         }
2165       idx = TEMPLATE_TYPE_IDX (parm);
2166 #if 0
2167       /* Template type parameters cannot contain cv-quals; i.e.
2168          template <class T> void f (T& a, T& b) will not generate
2169          void f (const int& a, const int& b).  */
2170       if (TYPE_READONLY (arg) > TYPE_READONLY (parm)
2171           || TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm))
2172         return 1;
2173       arg = TYPE_MAIN_VARIANT (arg);
2174 #else
2175       {
2176         int constp = TYPE_READONLY (arg) > TYPE_READONLY (parm);
2177         int volatilep = TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm);
2178         arg = cp_build_type_variant (arg, constp, volatilep);
2179       }
2180 #endif
2181       /* Simple cases: Value already set, does match or doesn't.  */
2182       if (targs[idx] == arg)
2183         return 0;
2184       else if (targs[idx])
2185         return 1;
2186       /* Check for mixed types and values.  */
2187       if (TREE_CODE (TREE_VALUE (TREE_VEC_ELT (tparms, idx))) != TYPE_DECL)
2188         return 1;
2189       targs[idx] = arg;
2190       return 0;
2191     case TEMPLATE_CONST_PARM:
2192       (*nsubsts)++;
2193       idx = TEMPLATE_CONST_IDX (parm);
2194       if (targs[idx] == arg)
2195         return 0;
2196       else if (targs[idx])
2197         {
2198           tree t = targs[idx];
2199           if (TREE_CODE (t) == TREE_CODE (arg))
2200             switch (TREE_CODE (arg))
2201               {
2202               case INTEGER_CST:
2203                 if (tree_int_cst_equal (t, arg))
2204                   return 0;
2205                 break;
2206               case REAL_CST:
2207                 if (REAL_VALUES_EQUAL (TREE_REAL_CST (t), TREE_REAL_CST (arg)))
2208                   return 0;
2209                 break;
2210               /* STRING_CST values are not valid template const parms.  */
2211               default:
2212                 ;
2213               }
2214           my_friendly_abort (87);
2215           return 1;
2216         }
2217 /*      else if (typeof arg != tparms[idx])
2218         return 1;*/
2219
2220       targs[idx] = copy_to_permanent (arg);
2221       return 0;
2222
2223     case POINTER_TYPE:
2224       if (TREE_CODE (arg) != POINTER_TYPE)
2225         return 1;
2226       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2227                     nsubsts);
2228
2229     case REFERENCE_TYPE:
2230       if (TREE_CODE (arg) == REFERENCE_TYPE)
2231         arg = TREE_TYPE (arg);
2232       return unify (tparms, targs, ntparms, TREE_TYPE (parm), arg, nsubsts);
2233
2234     case ARRAY_TYPE:
2235       if (TREE_CODE (arg) != ARRAY_TYPE)
2236         return 1;
2237       if (unify (tparms, targs, ntparms, TYPE_DOMAIN (parm), TYPE_DOMAIN (arg),
2238                  nsubsts) != 0)
2239         return 1;
2240       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2241                     nsubsts);
2242
2243     case REAL_TYPE:
2244     case INTEGER_TYPE:
2245       if (TREE_CODE (arg) != TREE_CODE (parm))
2246         return 1;
2247
2248       if (TREE_CODE (parm) == INTEGER_TYPE)
2249         {
2250           if (TYPE_MIN_VALUE (parm) && TYPE_MIN_VALUE (arg)
2251               && unify (tparms, targs, ntparms,
2252                         TYPE_MIN_VALUE (parm), TYPE_MIN_VALUE (arg), nsubsts))
2253             return 1;
2254           if (TYPE_MAX_VALUE (parm) && TYPE_MAX_VALUE (arg)
2255               && unify (tparms, targs, ntparms,
2256                         TYPE_MAX_VALUE (parm), TYPE_MAX_VALUE (arg), nsubsts))
2257             return 1;
2258         }
2259       /* As far as unification is concerned, this wins.  Later checks
2260          will invalidate it if necessary.  */
2261       return 0;
2262
2263       /* Types INTEGER_CST and MINUS_EXPR can come from array bounds.  */
2264     case INTEGER_CST:
2265       if (TREE_CODE (arg) != INTEGER_CST)
2266         return 1;
2267       return !tree_int_cst_equal (parm, arg);
2268
2269     case MINUS_EXPR:
2270       {
2271         tree t1, t2;
2272         t1 = TREE_OPERAND (parm, 0);
2273         t2 = TREE_OPERAND (parm, 1);
2274         return unify (tparms, targs, ntparms, t1,
2275                       fold (build (PLUS_EXPR, integer_type_node, arg, t2)),
2276                       nsubsts);
2277       }
2278
2279     case TREE_VEC:
2280       {
2281         int i;
2282         if (TREE_CODE (arg) != TREE_VEC)
2283           return 1;
2284         if (TREE_VEC_LENGTH (parm) != TREE_VEC_LENGTH (arg))
2285           return 1;
2286         for (i = TREE_VEC_LENGTH (parm) - 1; i >= 0; i--)
2287           if (unify (tparms, targs, ntparms,
2288                      TREE_VEC_ELT (parm, i), TREE_VEC_ELT (arg, i),
2289                      nsubsts))
2290             return 1;
2291         return 0;
2292       }
2293
2294     case UNINSTANTIATED_P_TYPE:
2295       {
2296         tree a;
2297         /* Unification of something that is not a class fails.  */
2298         if (! IS_AGGR_TYPE (arg))
2299           return 1;
2300         a = IDENTIFIER_TEMPLATE (TYPE_IDENTIFIER (arg));
2301         if (a && UPT_TEMPLATE (parm) == TREE_PURPOSE (a))
2302           return unify (tparms, targs, ntparms, UPT_PARMS (parm),
2303                         TREE_VALUE (a), nsubsts);
2304         /* FIXME: Should check base conversions here.  */
2305         return 1;
2306       }
2307
2308     case RECORD_TYPE:
2309       if (TYPE_PTRMEMFUNC_FLAG (parm))
2310         return unify (tparms, targs, ntparms, TYPE_PTRMEMFUNC_FN_TYPE (parm),
2311                       arg, nsubsts);
2312
2313       /* Allow trivial conversions.  */
2314       if (TYPE_MAIN_VARIANT (parm) != TYPE_MAIN_VARIANT (arg)
2315           || TYPE_READONLY (parm) < TYPE_READONLY (arg)
2316           || TYPE_VOLATILE (parm) < TYPE_VOLATILE (arg))
2317         return 1;
2318       return 0;
2319
2320     case METHOD_TYPE:
2321       if (TREE_CODE (arg) != METHOD_TYPE)
2322         return 1;
2323       goto check_args;
2324
2325     case FUNCTION_TYPE:
2326       if (TREE_CODE (arg) != FUNCTION_TYPE)
2327         return 1;
2328      check_args:
2329       if (unify (tparms, targs, ntparms, TREE_TYPE (parm),
2330                  TREE_TYPE (arg), nsubsts))
2331         return 1;
2332       return type_unification (tparms, targs, TYPE_ARG_TYPES (parm),
2333                                TYPE_ARG_TYPES (arg), nsubsts, 1);
2334
2335     case OFFSET_TYPE:
2336       if (TREE_CODE (arg) != OFFSET_TYPE)
2337         return 1;
2338       if (unify (tparms, targs, ntparms, TYPE_OFFSET_BASETYPE (parm),
2339                  TYPE_OFFSET_BASETYPE (arg), nsubsts))
2340         return 1;
2341       return unify (tparms, targs, ntparms, TREE_TYPE (parm),
2342                     TREE_TYPE (arg), nsubsts);
2343
2344     default:
2345       sorry ("use of `%s' in template type unification",
2346              tree_code_name [(int) TREE_CODE (parm)]);
2347       return 1;
2348     }
2349 }
2350
2351 \f
2352 #undef DEBUG
2353
2354 int
2355 do_pending_expansions ()
2356 {
2357   struct pending_inline *i, *new_list = 0;
2358
2359   {
2360     tree t;
2361     for (t = template_classes; t; t = TREE_CHAIN (t))
2362       instantiate_member_templates (TREE_PURPOSE (t));
2363   }
2364
2365   if (!pending_template_expansions)
2366     return 0;
2367
2368 #ifdef DEBUG
2369   fprintf (stderr, "\n\n\t\t IN DO_PENDING_EXPANSIONS\n\n");
2370 #endif
2371
2372   i = pending_template_expansions;
2373   while (i)
2374     {
2375       tree context;
2376
2377       struct pending_inline *next = i->next;
2378       tree t = i->fndecl;
2379
2380       int decision = 0;
2381 #define DECIDE(N) do {decision=(N); goto decided;} while(0)
2382
2383       my_friendly_assert (TREE_CODE (t) == FUNCTION_DECL
2384                           || TREE_CODE (t) == VAR_DECL, 294);
2385       if (TREE_ASM_WRITTEN (t))
2386         DECIDE (0);
2387
2388       if (DECL_EXPLICIT_INSTANTIATION (t))
2389         DECIDE (DECL_NOT_REALLY_EXTERN (t));
2390       else if (! flag_implicit_templates)
2391         DECIDE (0);
2392
2393       if (i->interface == 1)
2394         /* OK, it was an implicit instantiation.  */
2395         {
2396           if (flag_weak)
2397             DECL_WEAK (t) = 1;
2398           else
2399             TREE_PUBLIC (t) = 0;
2400         }
2401
2402       /* If it's a method, let the class type decide it.
2403          @@ What if the method template is in a separate file?
2404          Maybe both file contexts should be taken into account?
2405          Maybe only do this if i->interface == 1 (unknown)?  */
2406       context = DECL_CONTEXT (t);
2407       if (context != NULL_TREE
2408           && TREE_CODE_CLASS (TREE_CODE (context)) == 't')
2409         {
2410           /* I'm interested in the context of this version of the function,
2411              not the original virtual declaration.  */
2412           context = DECL_CLASS_CONTEXT (t);
2413
2414           /* If `unknown', we might want a static copy.
2415              If `implementation', we want a global one.
2416              If `interface', ext ref.  */
2417           if (CLASSTYPE_INTERFACE_KNOWN (context))
2418             DECIDE (!CLASSTYPE_INTERFACE_ONLY (context));
2419 #if 1 /* This doesn't get us stuff needed only by the file initializer.  */
2420           DECIDE (TREE_USED (t));
2421 #else /* This compiles too much stuff, but that's probably better in
2422          most cases than never compiling the stuff we need.  */
2423           DECIDE (1);
2424 #endif
2425         }
2426
2427       if (i->interface == 1)
2428         DECIDE (TREE_USED (t));
2429       else
2430         DECIDE (i->interface);
2431
2432     decided:
2433 #ifdef DEBUG
2434       print_node_brief (stderr, decision ? "yes: " : "no: ", t, 0);
2435       fprintf (stderr, "\t%s\n",
2436                (DECL_ASSEMBLER_NAME (t)
2437                 ? IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (t))
2438                 : ""));
2439 #endif
2440       if (decision)
2441         {
2442           i->next = pending_inlines;
2443           pending_inlines = i;
2444         }
2445       else
2446         {
2447           i->next = new_list;
2448           new_list = i;
2449         }
2450       i = next;
2451     }
2452   pending_template_expansions = new_list;
2453   if (!pending_inlines)
2454     return 0;
2455   do_pending_inlines ();
2456   return 1;
2457 }
2458
2459 \f
2460 struct pending_template {
2461   struct pending_template *next;
2462   tree id;
2463 };
2464
2465 static struct pending_template* pending_templates;
2466
2467 void
2468 do_pending_templates ()
2469 {
2470   struct pending_template* t;
2471
2472   for ( t = pending_templates; t; t = t->next)
2473     {
2474       instantiate_class_template (t->id, 1);
2475     }
2476
2477   for ( t = pending_templates; t; t = pending_templates)
2478     {
2479       pending_templates = t->next;
2480       free(t);
2481     }
2482 }
2483
2484 static void
2485 add_pending_template (pt)
2486      tree pt;
2487 {
2488   struct pending_template *p;
2489
2490   p = (struct pending_template *) malloc (sizeof (struct pending_template));
2491   p->next = pending_templates;
2492   pending_templates = p;
2493   p->id = pt;
2494 }
2495
2496 void
2497 mark_function_instantiated (result, extern_p)
2498      tree result;
2499      int extern_p;
2500 {
2501   if (DECL_TEMPLATE_INSTANTIATION (result))
2502     SET_DECL_EXPLICIT_INSTANTIATION (result);
2503   TREE_PUBLIC (result) = 1;
2504
2505   if (! extern_p)
2506     {
2507       DECL_INTERFACE_KNOWN (result) = 1;
2508       DECL_NOT_REALLY_EXTERN (result) = 1;
2509     }
2510 }
2511
2512 /* called from the parser.  */
2513 void
2514 do_function_instantiation (declspecs, declarator, storage)
2515      tree declspecs, declarator, storage;
2516 {
2517   tree decl = grokdeclarator (declarator, declspecs, NORMAL, 0,
2518                               NULL_TREE, NULL_TREE);
2519   tree name;
2520   tree fn;
2521   tree result = NULL_TREE;
2522   int extern_p = 0;
2523
2524   /* If we've already seen this template instance, use it.  */
2525   if (name = DECL_ASSEMBLER_NAME (decl),
2526       fn = IDENTIFIER_GLOBAL_VALUE (name),
2527       fn && DECL_TEMPLATE_INSTANTIATION (fn))
2528     result = fn;
2529   else if (fn && DECL_CONTEXT (fn))
2530     ;
2531   else if (name = DECL_NAME (decl), fn = IDENTIFIER_GLOBAL_VALUE (name), fn)
2532     {
2533       for (fn = get_first_fn (fn); fn; fn = DECL_CHAIN (fn))
2534         if (decls_match (fn, decl)
2535             && DECL_DEFER_OUTPUT (fn))
2536           {
2537             result = fn;
2538             break;
2539           }
2540         else if (TREE_CODE (fn) == TEMPLATE_DECL)
2541           {
2542             int ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (fn));
2543             tree *targs = (tree *) malloc (sizeof (tree) * ntparms);
2544             int i, dummy = 0;
2545             i = type_unification (DECL_TEMPLATE_PARMS (fn), targs,
2546                                   TYPE_ARG_TYPES (TREE_TYPE (fn)),
2547                                   TYPE_ARG_TYPES (TREE_TYPE (decl)),
2548                                   &dummy, 0);
2549             if (i == 0)
2550               {
2551                 if (result)
2552                   cp_error ("ambiguous template instantiation for `%D' requested", decl);
2553                 else
2554                   result = instantiate_template (fn, targs);
2555               }
2556             free (targs);
2557           }
2558     }
2559   if (! result)
2560     {
2561       cp_error ("no matching template for `%D' found", decl);
2562       return;
2563     }
2564
2565   if (flag_external_templates)
2566     return;
2567
2568   if (storage == NULL_TREE)
2569     ;
2570   else if (storage == ridpointers[(int) RID_EXTERN])
2571     extern_p = 1;
2572   else
2573     cp_error ("storage class `%D' applied to template instantiation",
2574               storage);
2575   mark_function_instantiated (result, extern_p);
2576   repo_template_instantiated (result, extern_p);
2577 }
2578
2579 void
2580 mark_class_instantiated (t, extern_p)
2581      tree t;
2582      int extern_p;
2583 {
2584   SET_CLASSTYPE_EXPLICIT_INSTANTIATION (t);
2585   SET_CLASSTYPE_INTERFACE_KNOWN (t);
2586   CLASSTYPE_INTERFACE_ONLY (t) = extern_p;
2587   CLASSTYPE_VTABLE_NEEDS_WRITING (t) = ! extern_p;
2588   TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = extern_p;
2589   if (! extern_p)
2590     {
2591       CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2592       rest_of_type_compilation (t, 1);
2593     }
2594 }
2595
2596 void
2597 do_type_instantiation (name, storage)
2598      tree name, storage;
2599 {
2600   tree t = TREE_TYPE (name);
2601   int extern_p = 0;
2602   int nomem_p = 0;
2603
2604   /* With -fexternal-templates, explicit instantiations are treated the same
2605      as implicit ones.  */
2606   if (flag_external_templates)
2607     return;
2608
2609   if (TYPE_SIZE (t) == NULL_TREE)
2610     {
2611       cp_error ("explicit instantiation of `%#T' before definition of template",
2612                 t);
2613       return;
2614     }
2615
2616   if (storage == NULL_TREE)
2617     /* OK */;
2618   else if (storage == ridpointers[(int) RID_INLINE])
2619     nomem_p = 1;
2620   else if (storage == ridpointers[(int) RID_EXTERN])
2621     extern_p = 1;
2622   else
2623     {
2624       cp_error ("storage class `%D' applied to template instantiation",
2625                 storage);
2626       extern_p = 0;
2627     }
2628
2629   /* We've already instantiated this.  */
2630   if (CLASSTYPE_EXPLICIT_INSTANTIATION (t) && ! CLASSTYPE_INTERFACE_ONLY (t)
2631       && extern_p)
2632     return;
2633
2634   if (! CLASSTYPE_TEMPLATE_SPECIALIZATION (t))
2635     {
2636       mark_class_instantiated (t, extern_p);
2637       repo_template_instantiated (t, extern_p);
2638     }
2639
2640   if (nomem_p)
2641     return;
2642
2643   {
2644     tree tmp;
2645     /* Classes nested in template classes currently don't have an
2646        IDENTIFIER_TEMPLATE--their out-of-line members are handled
2647        by the enclosing template class.  Note that there are name
2648        conflict bugs with this approach. */
2649     tmp = TYPE_IDENTIFIER (t);
2650     if (IDENTIFIER_TEMPLATE (tmp))
2651       instantiate_member_templates (tmp);
2652
2653     /* this should really be done by instantiate_member_templates */
2654     tmp = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (t), 0);
2655     for (; tmp; tmp = TREE_CHAIN (tmp))
2656       if (DECL_TEMPLATE_INSTANTIATION (tmp))
2657         {
2658           mark_function_instantiated (tmp, extern_p);
2659           repo_template_instantiated (tmp, extern_p);
2660         }
2661
2662 #if 0
2663     for (tmp = TYPE_FIELDS (t); tmp; tmp = TREE_CHAIN (tmp))
2664       {
2665         if (TREE_CODE (tmp) == VAR_DECL)
2666           /* eventually do something */;
2667       }
2668 #endif
2669
2670     for (tmp = CLASSTYPE_TAGS (t); tmp; tmp = TREE_CHAIN (tmp))
2671       if (IS_AGGR_TYPE (TREE_VALUE (tmp)))
2672         do_type_instantiation (TYPE_MAIN_DECL (TREE_VALUE (tmp)), storage);
2673   }
2674 }
2675
2676 tree
2677 create_nested_upt (scope, name)
2678      tree scope, name;
2679 {
2680   tree t = make_lang_type (UNINSTANTIATED_P_TYPE);
2681   tree d = build_decl (TYPE_DECL, name, t);
2682
2683   TYPE_NAME (t) = d;
2684   TYPE_VALUES (t) = TYPE_VALUES (scope);
2685   TYPE_CONTEXT (t) = scope;
2686
2687   pushdecl (d);
2688   return d;
2689 }