gcc/cp/pt.c

   1 /* Handle parameterized types (templates) for GNU C++.
   2    Copyright (C) 1992, 93, 94, 95, 1996 Free Software Foundation, Inc.
   3    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
   4    Rewritten by Jason Merrill (jason@cygnus.com).
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 /* Known bugs or deficiencies include:
  24
  25      templates for class static data don't work (methods only),
  26      duplicated method templates can crash the compiler,
  27      interface/impl data is taken from file defining the template,
  28      all methods must be provided in header files; can't use a source
  29      file that contains only the method templates and "just win".  */
  30
  31 #include "config.h"
  32 #include <stdio.h>
  33 #include "obstack.h"
  34
  35 #include "tree.h"
  36 #include "flags.h"
  37 #include "cp-tree.h"
  38 #include "decl.h"
  39 #include "parse.h"
  40 #include "lex.h"
  41 #include "output.h"
  42 #include "defaults.h"
  43
  44 extern struct obstack permanent_obstack;
  45
  46 extern int lineno;
  47 extern char *input_filename;
  48 struct pending_inline *pending_template_expansions;
  49
  50 tree current_template_parms;
  51 HOST_WIDE_INT processing_template_decl;
  52
  53 tree pending_templates;
  54 static tree *template_tail = &pending_templates;
  55
  56 tree maybe_templates;
  57 static tree *maybe_template_tail = &maybe_templates;
  58
  59 int minimal_parse_mode;
  60
  61 #define obstack_chunk_alloc xmalloc
  62 #define obstack_chunk_free free
  63
  64 static int unify ();
  65
  66 void pop_template_decls ();
  67
  68 tree classtype_mangled_name ();
  69 static char * mangle_class_name_for_template ();
  70 tree tsubst_expr_values ();
  71 tree most_specialized_class PROTO((tree, tree));
  72 tree get_class_bindings PROTO((tree, tree, tree));
  73 tree make_temp_vec PROTO((int));
  74
  75 /* We've got a template header coming up; push to a new level for storing
  76    the parms.  */
  77
  78 void
  79 begin_template_parm_list ()
  80 {
  81   pushlevel (0);
  82   declare_pseudo_global_level ();
  83   ++processing_template_decl;
  84 }
  85
  86 /* Process information from new template parameter NEXT and append it to the
  87    LIST being built.  */
  88
  89 tree
  90 process_template_parm (list, next)
  91      tree list, next;
  92 {
  93   tree parm;
  94   tree decl = 0;
  95   tree defval;
  96   int is_type, idx;
  97   parm = next;
  98   my_friendly_assert (TREE_CODE (parm) == TREE_LIST, 259);
  99   defval = TREE_PURPOSE (parm);
 100   parm = TREE_VALUE (parm);
 101   is_type = TREE_PURPOSE (parm) == class_type_node;
 102
 103   if (list)
 104     {
 105       tree p = TREE_VALUE (tree_last (list));
 106
 107       if (TREE_CODE (p) == TYPE_DECL)
 108         idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
 109       else
 110         idx = TEMPLATE_CONST_IDX (DECL_INITIAL (p));
 111       ++idx;
 112     }
 113   else
 114     idx = 0;
 115
 116   if (!is_type)
 117     {
 118       tree tinfo = 0;
 119       my_friendly_assert (TREE_CODE (TREE_PURPOSE (parm)) == TREE_LIST, 260);
 120       /* is a const-param */
 121       parm = grokdeclarator (TREE_VALUE (parm), TREE_PURPOSE (parm),
 122                              PARM, 0, NULL_TREE);
 123       /* A template parameter is not modifiable.  */
 124       TREE_READONLY (parm) = 1;
 125       if (IS_AGGR_TYPE (TREE_TYPE (parm))
 126           && TREE_CODE (TREE_TYPE (parm)) != TEMPLATE_TYPE_PARM)
 127         {
 128           cp_error ("`%#T' is not a valid type for a template constant parameter",
 129                     TREE_TYPE (parm));
 130           if (DECL_NAME (parm) == NULL_TREE)
 131             error ("  a template type parameter must begin with `class' or `typename'");
 132           TREE_TYPE (parm) = void_type_node;
 133         }
 134       tinfo = make_node (TEMPLATE_CONST_PARM);
 135       my_friendly_assert (TREE_PERMANENT (tinfo), 260.5);
 136       if (TREE_PERMANENT (parm) == 0)
 137         {
 138           parm = copy_node (parm);
 139           TREE_PERMANENT (parm) = 1;
 140         }
 141       TREE_TYPE (tinfo) = TREE_TYPE (parm);
 142       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
 143       DECL_INITIAL (decl) = tinfo;
 144       DECL_INITIAL (parm) = tinfo;
 145       TEMPLATE_CONST_SET_INFO (tinfo, idx, processing_template_decl);
 146     }
 147   else
 148     {
 149       tree t = make_lang_type (TEMPLATE_TYPE_PARM);
 150       CLASSTYPE_GOT_SEMICOLON (t) = 1;
 151       decl = build_decl (TYPE_DECL, TREE_VALUE (parm), t);
 152       TYPE_NAME (t) = decl;
 153       TYPE_STUB_DECL (t) = decl;
 154       parm = decl;
 155       TEMPLATE_TYPE_SET_INFO (t, idx, processing_template_decl);
 156     }
 157   SET_DECL_ARTIFICIAL (decl);
 158   pushdecl (decl);
 159   parm = build_tree_list (defval, parm);
 160   return chainon (list, parm);
 161 }
 162
 163 /* The end of a template parameter list has been reached.  Process the
 164    tree list into a parameter vector, converting each parameter into a more
 165    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
 166    as PARM_DECLs.  */
 167
 168 tree
 169 end_template_parm_list (parms)
 170      tree parms;
 171 {
 172   int nparms;
 173   tree parm;
 174   tree saved_parmlist = make_tree_vec (list_length (parms));
 175
 176   current_template_parms
 177     = tree_cons (build_int_2 (0, processing_template_decl),
 178                  saved_parmlist, current_template_parms);
 179
 180   for (parm = parms, nparms = 0; parm; parm = TREE_CHAIN (parm), nparms++)
 181     TREE_VEC_ELT (saved_parmlist, nparms) = parm;
 182
 183   return saved_parmlist;
 184 }
 185
 186 /* end_template_decl is called after a template declaration is seen.  */
 187
 188 void
 189 end_template_decl ()
 190 {
 191   if (! processing_template_decl)
 192     return;
 193
 194   /* This matches the pushlevel in begin_template_parm_list.  */
 195   poplevel (0, 0, 0);
 196
 197   --processing_template_decl;
 198   current_template_parms = TREE_CHAIN (current_template_parms);
 199   (void) get_pending_sizes ();  /* Why? */
 200 }
 201
 202 /* Generate a valid set of template args from current_template_parms.  */
 203
 204 tree
 205 current_template_args ()
 206 {
 207   tree header = current_template_parms;
 208   tree args = NULL_TREE;
 209   while (header)
 210     {
 211       tree a = copy_node (TREE_VALUE (header));
 212       int i = TREE_VEC_LENGTH (a);
 213       TREE_TYPE (a) = NULL_TREE;
 214       while (i--)
 215         {
 216           tree t = TREE_VALUE (TREE_VEC_ELT (a, i));
 217           if (TREE_CODE (t) == TYPE_DECL)
 218             t = TREE_TYPE (t);
 219           else
 220             t = DECL_INITIAL (t);
 221           TREE_VEC_ELT (a, i) = t;
 222         }
 223       args = tree_cons (TREE_PURPOSE (header), a, args);
 224       header = TREE_CHAIN (header);
 225     }
 226   args = nreverse (args);
 227
 228   /* FIXME Remove this when we support member templates.  */
 229   args = TREE_VALUE (args);
 230
 231   return args;
 232 }
 233
 234 void
 235 push_template_decl (decl)
 236      tree decl;
 237 {
 238   tree tmpl;
 239   tree args = NULL_TREE;
 240   tree info;
 241   tree ctx = DECL_CONTEXT (decl) ? DECL_CONTEXT (decl) : current_class_type;
 242   int primary = 0;
 243
 244   /* Kludge! */
 245   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_FRIEND_P (decl)
 246       && DECL_CLASS_CONTEXT (decl))
 247     ;
 248   /* Note that this template is a "primary template" */
 249   else if (! ctx || ! CLASSTYPE_TEMPLATE_INFO (ctx)
 250       /* || (processing_template_decl > CLASSTYPE_TEMPLATE_LEVEL (ctx)) */)
 251     primary = 1;
 252
 253   /* Partial specialization.  */
 254   if (TREE_CODE (decl) == TYPE_DECL
 255       && CLASSTYPE_TEMPLATE_SPECIALIZATION (TREE_TYPE (decl)))
 256     {
 257       tree type = TREE_TYPE (decl);
 258       tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
 259       tree mainargs = CLASSTYPE_TI_ARGS (type);
 260       tree spec = DECL_TEMPLATE_SPECIALIZATIONS (maintmpl);
 261
 262       for (; spec; spec = TREE_CHAIN (spec))
 263         {
 264           /* purpose: args to main template
 265              value: spec template */
 266           if (comp_template_args (TREE_PURPOSE (spec), mainargs))
 267             return;
 268         }
 269
 270       DECL_TEMPLATE_SPECIALIZATIONS (maintmpl) = perm_tree_cons
 271         (mainargs, TREE_VALUE (current_template_parms),
 272          DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
 273       TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
 274       return;
 275     }
 276
 277   args = current_template_args ();
 278
 279   if (! ctx || TYPE_BEING_DEFINED (ctx))
 280     {
 281       tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
 282       DECL_TEMPLATE_PARMS (tmpl) = TREE_VALUE (current_template_parms);
 283       DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
 284     }
 285   else
 286     {
 287       if (CLASSTYPE_TEMPLATE_INSTANTIATION (ctx))
 288         cp_error ("must specialize `%#T' before defining member `%#D'",
 289                   ctx, decl);
 290       if (TREE_CODE (decl) == TYPE_DECL)
 291         tmpl = CLASSTYPE_TI_TEMPLATE (TREE_TYPE (decl));
 292       else if (! DECL_TEMPLATE_INFO (decl))
 293         {
 294           cp_error ("template definition of non-template `%#D'", decl);
 295           return;
 296         }
 297       else
 298         tmpl = DECL_TI_TEMPLATE (decl);
 299     }
 300
 301   DECL_TEMPLATE_RESULT (tmpl) = decl;
 302   TREE_TYPE (tmpl) = TREE_TYPE (decl);
 303
 304   if (! ctx)
 305     tmpl = pushdecl_top_level (tmpl);
 306
 307   if (primary)
 308     TREE_TYPE (DECL_TEMPLATE_PARMS (tmpl)) = tmpl;
 309
 310   info = perm_tree_cons (tmpl, args, NULL_TREE);
 311
 312   if (TREE_CODE (decl) == TYPE_DECL)
 313     {
 314       CLASSTYPE_TEMPLATE_INFO (TREE_TYPE (tmpl)) = info;
 315       DECL_NAME (decl) = classtype_mangled_name (TREE_TYPE (decl));
 316     }
 317   else if (! DECL_LANG_SPECIFIC (decl))
 318     cp_error ("template declaration of `%#D'", decl);
 319   else
 320     DECL_TEMPLATE_INFO (decl) = info;
 321 }
 322
 323 tree tsubst             PROTO ((tree, tree*, int, tree));
 324
 325 /* Convert all template arguments to their appropriate types, and return
 326    a vector containing the resulting values.  If any error occurs, return
 327    error_mark_node.  */
 328
 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 if (TREE_CODE (TREE_VALUE (TREE_VEC_ELT (parms, i)))
 377                    == TYPE_DECL)
 378             arg = tsubst (TREE_PURPOSE (TREE_VEC_ELT (parms, i)),
 379                           &TREE_VEC_ELT (vec, 0), i, in_decl);
 380           else
 381             arg = tsubst_expr (TREE_PURPOSE (TREE_VEC_ELT (parms, i)),
 382                                &TREE_VEC_ELT (vec, 0), i, in_decl);
 383
 384           TREE_VEC_ELT (vec, i) = arg;
 385         }
 386     }
 387   for (i = 0; i < nparms; i++)
 388     {
 389       tree arg = TREE_VEC_ELT (vec, i);
 390       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 391       tree val = 0;
 392       int is_type, requires_type;
 393
 394       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
 395       requires_type = TREE_CODE (parm) == TYPE_DECL;
 396
 397       if (requires_type && ! is_type && TREE_CODE (arg) == SCOPE_REF
 398           && TREE_CODE (TREE_OPERAND (arg, 0)) == TEMPLATE_TYPE_PARM)
 399         {
 400           cp_pedwarn ("to refer to a type member of a template parameter,");
 401           cp_pedwarn ("  use `typename %E'", arg);
 402           arg = make_typename_type (TREE_OPERAND (arg, 0),
 403                                     TREE_OPERAND (arg, 1));
 404           is_type = 1;
 405         }
 406       if (is_type != requires_type)
 407         {
 408           if (in_decl)
 409             {
 410               cp_error ("type/value mismatch at argument %d in template parameter list for `%D'",
 411                         i, in_decl);
 412               if (is_type)
 413                 cp_error ("  expected a constant of type `%T', got `%T'",
 414                           TREE_TYPE (parm), arg);
 415               else
 416                 cp_error ("  expected a type, got `%E'", arg);
 417             }
 418           lost++;
 419           TREE_VEC_ELT (vec, i) = error_mark_node;
 420           continue;
 421         }
 422       if (is_type)
 423         {
 424           val = groktypename (arg);
 425           if (! processing_template_decl)
 426             {
 427               tree t = target_type (val);
 428               if (IS_AGGR_TYPE (t)
 429                   && decl_function_context (TYPE_MAIN_DECL (t)))
 430                 {
 431                   cp_error ("type `%T' composed from a local class is not a valid template-argument", val);
 432                   return error_mark_node;
 433                 }
 434             }
 435         }
 436       else
 437         {
 438           tree t = tsubst (TREE_TYPE (parm), &TREE_VEC_ELT (vec, 0),
 439                            TREE_VEC_LENGTH (vec), in_decl);
 440           if (processing_template_decl)
 441             val = arg;
 442           else
 443             val = digest_init (t, arg, (tree *) 0);
 444
 445           if (val == error_mark_node || processing_template_decl)
 446             ;
 447
 448           /* 14.2: Other template-arguments must be constant-expressions,
 449              addresses of objects or functions with external linkage, or of
 450              static class members.  */
 451           else if (!TREE_CONSTANT (val))
 452             {
 453               cp_error ("non-const `%E' cannot be used as template argument",
 454                         arg);
 455               val = error_mark_node;
 456             }
 457           else if (POINTER_TYPE_P (TREE_TYPE (val))
 458                    && ! integer_zerop (val)
 459                    && TREE_CODE (TREE_TYPE (TREE_TYPE (val))) != OFFSET_TYPE
 460                    && TREE_CODE (TREE_TYPE (TREE_TYPE (val))) != METHOD_TYPE)
 461             {
 462               t = val;
 463               STRIP_NOPS (t);
 464               if (TREE_CODE (t) == ADDR_EXPR)
 465                 {
 466                   tree a = TREE_OPERAND (t, 0);
 467                   STRIP_NOPS (a);
 468                   if (TREE_CODE (a) == STRING_CST)
 469                     {
 470                       cp_error ("string literal %E is not a valid template argument", a);
 471                       error ("because it is the address of an object with static linkage");
 472                       val = error_mark_node;
 473                     }
 474                   else if (TREE_CODE (a) != VAR_DECL
 475                            && TREE_CODE (a) != FUNCTION_DECL)
 476                     goto bad;
 477                   else if (! DECL_PUBLIC (a))
 478                     {
 479                       cp_error ("address of non-extern `%E' cannot be used as template argument", a);
 480                       val = error_mark_node;
 481                     }
 482                 }
 483               else
 484                 {
 485                 bad:
 486                   cp_error ("`%E' is not a valid template argument", t);
 487                   error ("it must be %s%s with external linkage",
 488                          TREE_CODE (TREE_TYPE (val)) == POINTER_TYPE
 489                          ? "a pointer to " : "",
 490                          TREE_CODE (TREE_TYPE (TREE_TYPE (val))) == FUNCTION_TYPE
 491                          ? "a function" : "an object");
 492                   val = error_mark_node;
 493                 }
 494             }
 495         }
 496
 497       if (val == error_mark_node)
 498         lost++;
 499
 500       TREE_VEC_ELT (vec, i) = val;
 501     }
 502   if (lost)
 503     return error_mark_node;
 504   return vec;
 505 }
 506
 507 int
 508 comp_template_args (oldargs, newargs)
 509      tree oldargs, newargs;
 510 {
 511   int i;
 512
 513   for (i = 0; i < TREE_VEC_LENGTH (oldargs); ++i)
 514     {
 515       tree nt = TREE_VEC_ELT (newargs, i);
 516       tree ot = TREE_VEC_ELT (oldargs, i);
 517
 518       if (nt == ot)
 519         continue;
 520       if (TREE_CODE (nt) != TREE_CODE (ot))
 521         return 0;
 522       if (TREE_CODE_CLASS (TREE_CODE (ot)) == 't')
 523         {
 524           if (comptypes (ot, nt, 1))
 525             continue;
 526         }
 527       else if (cp_tree_equal (ot, nt) > 0)
 528         continue;
 529       return 0;
 530     }
 531   return 1;
 532 }
 533
 534 /* Given class template name and parameter list, produce a user-friendly name
 535    for the instantiation.  */
 536
 537 static char *
 538 mangle_class_name_for_template (name, parms, arglist)
 539      char *name;
 540      tree parms, arglist;
 541 {
 542   static struct obstack scratch_obstack;
 543   static char *scratch_firstobj;
 544   int i, nparms;
 545
 546   if (!scratch_firstobj)
 547     gcc_obstack_init (&scratch_obstack);
 548   else
 549     obstack_free (&scratch_obstack, scratch_firstobj);
 550   scratch_firstobj = obstack_alloc (&scratch_obstack, 1);
 551
 552 #if 0
 553 #define buflen  sizeof(buf)
 554 #define check   if (bufp >= buf+buflen-1) goto too_long
 555 #define ccat(c) *bufp++=(c); check
 556 #define advance bufp+=strlen(bufp); check
 557 #define cat(s)  strncpy(bufp, s, buf+buflen-bufp-1); advance
 558 #else
 559 #define check
 560 #define ccat(c) obstack_1grow (&scratch_obstack, (c));
 561 #define advance
 562 #define cat(s)  obstack_grow (&scratch_obstack, (s), strlen (s))
 563 #endif
 564
 565   cat (name);
 566   ccat ('<');
 567   nparms = TREE_VEC_LENGTH (parms);
 568   my_friendly_assert (nparms == TREE_VEC_LENGTH (arglist), 268);
 569   for (i = 0; i < nparms; i++)
 570     {
 571       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 572       tree arg = TREE_VEC_ELT (arglist, i);
 573
 574       if (i)
 575         ccat (',');
 576
 577       if (TREE_CODE (parm) == TYPE_DECL)
 578         {
 579           cat (type_as_string (arg, 0));
 580           continue;
 581         }
 582       else
 583         my_friendly_assert (TREE_CODE (parm) == PARM_DECL, 269);
 584
 585       if (TREE_CODE (arg) == TREE_LIST)
 586         {
 587           /* New list cell was built because old chain link was in
 588              use.  */
 589           my_friendly_assert (TREE_PURPOSE (arg) == NULL_TREE, 270);
 590           arg = TREE_VALUE (arg);
 591         }
 592       /* No need to check arglist against parmlist here; we did that
 593          in coerce_template_parms, called from lookup_template_class.  */
 594       cat (expr_as_string (arg, 0));
 595     }
 596   {
 597     char *bufp = obstack_next_free (&scratch_obstack);
 598     int offset = 0;
 599     while (bufp[offset - 1] == ' ')
 600       offset--;
 601     obstack_blank_fast (&scratch_obstack, offset);
 602
 603     /* B<C<char> >, not B<C<char>> */
 604     if (bufp[offset - 1] == '>')
 605       ccat (' ');
 606   }
 607   ccat ('>');
 608   ccat ('\0');
 609   return (char *) obstack_base (&scratch_obstack);
 610
 611 #if 0
 612  too_long:
 613 #endif
 614   fatal ("out of (preallocated) string space creating template instantiation name");
 615   /* NOTREACHED */
 616   return NULL;
 617 }
 618
 619 tree
 620 classtype_mangled_name (t)
 621      tree t;
 622 {
 623   if (CLASSTYPE_TEMPLATE_INFO (t)
 624       && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t)))
 625     {
 626       tree name = DECL_NAME (CLASSTYPE_TI_TEMPLATE (t));
 627       char *mangled_name = mangle_class_name_for_template
 628         (IDENTIFIER_POINTER (name),
 629          DECL_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (t)),
 630          CLASSTYPE_TI_ARGS (t));
 631       tree id = get_identifier (mangled_name);
 632       IDENTIFIER_TEMPLATE (id) = name;
 633       return id;
 634     }
 635   else
 636     return TYPE_IDENTIFIER (t);
 637 }
 638
 639 static void
 640 add_pending_template (d)
 641      tree d;
 642 {
 643   tree ti;
 644
 645   if (TREE_CODE_CLASS (TREE_CODE (d)) == 't')
 646     ti = CLASSTYPE_TEMPLATE_INFO (d);
 647   else
 648     ti = DECL_TEMPLATE_INFO (d);
 649
 650   if (TREE_LANG_FLAG_0 (ti))
 651     return;
 652
 653   *template_tail = perm_tree_cons
 654     (current_function_decl, d, NULL_TREE);
 655   template_tail = &TREE_CHAIN (*template_tail);
 656   TREE_LANG_FLAG_0 (ti) = 1;
 657 }
 658
 659 /* Given an IDENTIFIER_NODE (type TEMPLATE_DECL) and a chain of
 660    parameters, find the desired type.
 661
 662    D1 is the PTYPENAME terminal, and ARGLIST is the list of arguments.
 663    Since ARGLIST is build on the decl_obstack, we must copy it here
 664    to keep it from being reclaimed when the decl storage is reclaimed.
 665
 666    IN_DECL, if non-NULL, is the template declaration we are trying to
 667    instantiate.  */
 668
 669 tree
 670 lookup_template_class (d1, arglist, in_decl)
 671      tree d1, arglist;
 672      tree in_decl;
 673 {
 674   tree template, parmlist;
 675   char *mangled_name;
 676   tree id, t;
 677   tree code_type_node;
 678
 679   if (TREE_CODE (d1) == IDENTIFIER_NODE)
 680     {
 681       template = IDENTIFIER_GLOBAL_VALUE (d1); /* XXX */
 682       if (! template)
 683         template = IDENTIFIER_CLASS_VALUE (d1);
 684     }
 685   else if (TREE_CODE (d1) == TYPE_DECL && IS_AGGR_TYPE (TREE_TYPE (d1)))
 686     {
 687       template = CLASSTYPE_TI_TEMPLATE (TREE_TYPE (d1));
 688       d1 = DECL_NAME (template);
 689     }
 690   else if (TREE_CODE_CLASS (TREE_CODE (d1)) == 't' && IS_AGGR_TYPE (d1))
 691     {
 692       template = CLASSTYPE_TI_TEMPLATE (d1);
 693       d1 = DECL_NAME (template);
 694     }
 695   else
 696     my_friendly_abort (272);
 697
 698   /* With something like `template <class T> class X class X { ... };'
 699      we could end up with D1 having nothing but an IDENTIFIER_LOCAL_VALUE.
 700      We don't want to do that, but we have to deal with the situation, so
 701      let's give them some syntax errors to chew on instead of a crash.  */
 702   if (! template)
 703     return error_mark_node;
 704   if (TREE_CODE (template) != TEMPLATE_DECL)
 705     {
 706       cp_error ("non-template type `%T' used as a template", d1);
 707       if (in_decl)
 708         cp_error_at ("for template declaration `%D'", in_decl);
 709       return error_mark_node;
 710     }
 711
 712   if (PRIMARY_TEMPLATE_P (template))
 713     {
 714       parmlist = DECL_TEMPLATE_PARMS (template);
 715
 716       arglist = coerce_template_parms (parmlist, arglist, template);
 717       if (arglist == error_mark_node)
 718         return error_mark_node;
 719       if (uses_template_parms (arglist))
 720         {
 721           tree found;
 722           if (comp_template_args
 723               (CLASSTYPE_TI_ARGS (TREE_TYPE (template)), arglist))
 724             found = TREE_TYPE (template);
 725           else
 726             {
 727               for (found = DECL_TEMPLATE_INSTANTIATIONS (template);
 728                    found; found = TREE_CHAIN (found))
 729                 {
 730                   if (TI_USES_TEMPLATE_PARMS (found)
 731                       && comp_template_args (TREE_PURPOSE (found), arglist))
 732                     break;
 733                 }
 734               if (found)
 735                 found = TREE_VALUE (found);
 736             }
 737
 738           if (found)
 739             {
 740               if (can_free (&permanent_obstack, arglist))
 741                 obstack_free (&permanent_obstack, arglist);
 742               return found;
 743             }
 744         }
 745
 746       mangled_name = mangle_class_name_for_template (IDENTIFIER_POINTER (d1),
 747                                                      parmlist, arglist);
 748       id = get_identifier (mangled_name);
 749       IDENTIFIER_TEMPLATE (id) = d1;
 750
 751       maybe_push_to_top_level (uses_template_parms (arglist));
 752       t = xref_tag_from_type (TREE_TYPE (template), id, 1);
 753       pop_from_top_level ();
 754     }
 755   else
 756     {
 757       tree ctx = lookup_template_class (TYPE_CONTEXT (TREE_TYPE (template)),
 758                                         arglist, in_decl);
 759       id = d1;
 760       arglist = CLASSTYPE_TI_ARGS (ctx);
 761
 762       if (TYPE_BEING_DEFINED (ctx) && ctx == current_class_type)
 763         {
 764           int save_temp = processing_template_decl;
 765           processing_template_decl = 0;
 766           t = xref_tag_from_type (TREE_TYPE (template), id, 0);
 767           processing_template_decl = save_temp;
 768         }
 769       else
 770         {
 771           t = lookup_nested_type_by_name (ctx, id);
 772           my_friendly_assert (t != NULL_TREE, 42);
 773         }
 774     }
 775
 776   /* Seems to be wanted.  */
 777   CLASSTYPE_GOT_SEMICOLON (t) = 1;
 778
 779   if (! CLASSTYPE_TEMPLATE_INFO (t))
 780     {
 781       arglist = copy_to_permanent (arglist);
 782       CLASSTYPE_TEMPLATE_INFO (t)
 783         = perm_tree_cons (template, arglist, NULL_TREE);
 784       DECL_TEMPLATE_INSTANTIATIONS (template) = perm_tree_cons
 785         (arglist, t, DECL_TEMPLATE_INSTANTIATIONS (template));
 786       TI_USES_TEMPLATE_PARMS (DECL_TEMPLATE_INSTANTIATIONS (template))
 787         = uses_template_parms (arglist);
 788
 789       SET_CLASSTYPE_IMPLICIT_INSTANTIATION (t);
 790
 791       /* We need to set this again after CLASSTYPE_TEMPLATE_INFO is set up.  */
 792       DECL_ASSEMBLER_NAME (TYPE_MAIN_DECL (t)) = id;
 793       if (! uses_template_parms (arglist))
 794         DECL_ASSEMBLER_NAME (TYPE_MAIN_DECL (t))
 795           = get_identifier (build_overload_name (t, 1, 1));
 796
 797       if (flag_external_templates && ! uses_template_parms (arglist)
 798           && CLASSTYPE_INTERFACE_KNOWN (TREE_TYPE (template))
 799           && ! CLASSTYPE_INTERFACE_ONLY (TREE_TYPE (template)))
 800         add_pending_template (t);
 801     }
 802
 803   return t;
 804 }
 805 \f
 806 /* Should be defined in parse.h.  */
 807 extern int yychar;
 808
 809 int
 810 uses_template_parms (t)
 811      tree t;
 812 {
 813   if (!t)
 814     return 0;
 815   switch (TREE_CODE (t))
 816     {
 817     case INDIRECT_REF:
 818     case COMPONENT_REF:
 819       /* We assume that the object must be instantiated in order to build
 820          the COMPONENT_REF, so we test only whether the type of the
 821          COMPONENT_REF uses template parms.  */
 822       return uses_template_parms (TREE_TYPE (t));
 823
 824     case IDENTIFIER_NODE:
 825       if (!IDENTIFIER_TEMPLATE (t))
 826         return 0;
 827       my_friendly_abort (42);
 828
 829       /* aggregates of tree nodes */
 830     case TREE_VEC:
 831       {
 832         int i = TREE_VEC_LENGTH (t);
 833         while (i--)
 834           if (uses_template_parms (TREE_VEC_ELT (t, i)))
 835             return 1;
 836         return 0;
 837       }
 838     case TREE_LIST:
 839       if (uses_template_parms (TREE_PURPOSE (t))
 840           || uses_template_parms (TREE_VALUE (t)))
 841         return 1;
 842       return uses_template_parms (TREE_CHAIN (t));
 843
 844       /* constructed type nodes */
 845     case POINTER_TYPE:
 846     case REFERENCE_TYPE:
 847       return uses_template_parms (TREE_TYPE (t));
 848     case RECORD_TYPE:
 849       if (TYPE_PTRMEMFUNC_FLAG (t))
 850         return uses_template_parms (TYPE_PTRMEMFUNC_FN_TYPE (t));
 851     case UNION_TYPE:
 852       if (! CLASSTYPE_TEMPLATE_INFO (t))
 853         return 0;
 854       return uses_template_parms (TREE_VALUE (CLASSTYPE_TEMPLATE_INFO (t)));
 855     case FUNCTION_TYPE:
 856       if (uses_template_parms (TYPE_ARG_TYPES (t)))
 857         return 1;
 858       return uses_template_parms (TREE_TYPE (t));
 859     case ARRAY_TYPE:
 860       if (uses_template_parms (TYPE_DOMAIN (t)))
 861         return 1;
 862       return uses_template_parms (TREE_TYPE (t));
 863     case OFFSET_TYPE:
 864       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
 865         return 1;
 866       return uses_template_parms (TREE_TYPE (t));
 867     case METHOD_TYPE:
 868       if (uses_template_parms (TYPE_METHOD_BASETYPE (t)))
 869         return 1;
 870       if (uses_template_parms (TYPE_ARG_TYPES (t)))
 871         return 1;
 872       return uses_template_parms (TREE_TYPE (t));
 873
 874       /* decl nodes */
 875     case TYPE_DECL:
 876       return uses_template_parms (TREE_TYPE (t));
 877
 878     case FUNCTION_DECL:
 879     case VAR_DECL:
 880       /* ??? What about FIELD_DECLs?  */
 881       if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t)
 882           && uses_template_parms (DECL_TI_ARGS (t)))
 883         return 1;
 884       /* fall through */
 885     case CONST_DECL:
 886     case PARM_DECL:
 887       if (uses_template_parms (TREE_TYPE (t)))
 888         return 1;
 889       if (DECL_CONTEXT (t) && uses_template_parms (DECL_CONTEXT (t)))
 890         return 1;
 891       return 0;
 892
 893     case CALL_EXPR:
 894       return uses_template_parms (TREE_TYPE (t));
 895     case ADDR_EXPR:
 896       return uses_template_parms (TREE_OPERAND (t, 0));
 897
 898       /* template parm nodes */
 899     case TEMPLATE_TYPE_PARM:
 900     case TEMPLATE_CONST_PARM:
 901       return 1;
 902
 903       /* simple type nodes */
 904     case INTEGER_TYPE:
 905       if (uses_template_parms (TYPE_MIN_VALUE (t)))
 906         return 1;
 907       return uses_template_parms (TYPE_MAX_VALUE (t));
 908
 909     case REAL_TYPE:
 910     case VOID_TYPE:
 911     case ENUMERAL_TYPE:
 912     case BOOLEAN_TYPE:
 913       return 0;
 914
 915       /* constants */
 916     case INTEGER_CST:
 917     case REAL_CST:
 918     case STRING_CST:
 919       return 0;
 920
 921     case ERROR_MARK:
 922       /* Non-error_mark_node ERROR_MARKs are bad things.  */
 923       my_friendly_assert (t == error_mark_node, 274);
 924       /* NOTREACHED */
 925       return 0;
 926
 927     case LOOKUP_EXPR:
 928     case TYPENAME_TYPE:
 929       return 1;
 930
 931     case SCOPE_REF:
 932       return uses_template_parms (TREE_OPERAND (t, 0));
 933
 934     case CONSTRUCTOR:
 935       if (TREE_TYPE (t) && TYPE_PTRMEMFUNC_P (TREE_TYPE (t)))
 936         return uses_template_parms (TYPE_PTRMEMFUNC_FN_TYPE (TREE_TYPE (t)));
 937       return uses_template_parms (TREE_OPERAND (t, 1));
 938
 939     default:
 940       switch (TREE_CODE_CLASS (TREE_CODE (t)))
 941         {
 942         case '1':
 943         case '2':
 944         case 'e':
 945         case '<':
 946           {
 947             int i;
 948             for (i = tree_code_length[(int) TREE_CODE (t)]; --i >= 0;)
 949               if (uses_template_parms (TREE_OPERAND (t, i)))
 950                 return 1;
 951             return 0;
 952           }
 953         default:
 954           break;
 955         }
 956       sorry ("testing %s for template parms",
 957              tree_code_name [(int) TREE_CODE (t)]);
 958       my_friendly_abort (82);
 959       /* NOTREACHED */
 960       return 0;
 961     }
 962 }
 963
 964 static struct tinst_level *current_tinst_level = 0;
 965 static struct tinst_level *free_tinst_level = 0;
 966 static int tinst_depth = 0;
 967 int max_tinst_depth = 17;
 968 #ifdef GATHER_STATISTICS
 969 int depth_reached = 0;
 970 #endif
 971
 972 int
 973 push_tinst_level (d)
 974      tree d;
 975 {
 976   struct tinst_level *new;
 977
 978   if (tinst_depth >= max_tinst_depth)
 979     {
 980       struct tinst_level *p = current_tinst_level;
 981       int line = lineno;
 982       char *file = input_filename;
 983
 984       error ("template instantiation depth exceeds maximum of %d",
 985              max_tinst_depth);
 986       cp_error ("  instantiating `%D'", d);
 987
 988       for (; p; p = p->next)
 989         {
 990           cp_error ("  instantiated from `%D'", p->decl);
 991           lineno = p->line;
 992           input_filename = p->file;
 993         }
 994       error ("  instantiated from here");
 995
 996       lineno = line;
 997       input_filename = file;
 998
 999       return 0;
1000     }
1001
1002   if (free_tinst_level)
1003     {
1004       new = free_tinst_level;
1005       free_tinst_level = new->next;
1006     }
1007   else
1008     new = (struct tinst_level *) xmalloc (sizeof (struct tinst_level));
1009
1010   new->decl = d;
1011   new->line = lineno;
1012   new->file = input_filename;
1013   new->next = current_tinst_level;
1014   current_tinst_level = new;
1015
1016   ++tinst_depth;
1017 #ifdef GATHER_STATISTICS
1018   if (tinst_depth > depth_reached)
1019     depth_reached = tinst_depth;
1020 #endif
1021
1022   return 1;
1023 }
1024
1025 void
1026 pop_tinst_level ()
1027 {
1028   struct tinst_level *old = current_tinst_level;
1029
1030   current_tinst_level = old->next;
1031   old->next = free_tinst_level;
1032   free_tinst_level = old;
1033   --tinst_depth;
1034 }
1035
1036 struct tinst_level *
1037 tinst_for_decl ()
1038 {
1039   struct tinst_level *p = current_tinst_level;
1040
1041   if (p)
1042     for (; p->next ; p = p->next )
1043       ;
1044   return p;
1045 }
1046
1047 tree
1048 instantiate_class_template (type)
1049      tree type;
1050 {
1051   tree template, template_info, args, pattern, t, *field_chain;
1052
1053   if (type == error_mark_node)
1054     return error_mark_node;
1055
1056   template_info = CLASSTYPE_TEMPLATE_INFO (type);
1057
1058   if (TYPE_BEING_DEFINED (type) || TYPE_SIZE (type))
1059     return type;
1060
1061   template = TI_TEMPLATE (template_info);
1062   my_friendly_assert (TREE_CODE (template) == TEMPLATE_DECL, 279);
1063   args = TI_ARGS (template_info);
1064
1065   t = most_specialized_class
1066     (DECL_TEMPLATE_SPECIALIZATIONS (template), args);
1067
1068   if (t == error_mark_node)
1069     {
1070       char *str = "candidates are:";
1071       cp_error ("ambiguous class template instantiation for `%#T'", type);
1072       for (t = DECL_TEMPLATE_SPECIALIZATIONS (template); t; t = TREE_CHAIN (t))
1073         {
1074           if (get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), args))
1075             {
1076               cp_error_at ("%s %+#T", str, TREE_TYPE (t));
1077               str = "               ";
1078             }
1079         }
1080       TYPE_BEING_DEFINED (type) = 1;
1081       return;
1082     }
1083   else if (t)
1084     pattern = TREE_TYPE (t);
1085   else
1086     pattern = TREE_TYPE (template);
1087
1088   if (TYPE_SIZE (pattern) == NULL_TREE)
1089     return type;
1090
1091   if (t)
1092     args = get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), args);
1093
1094   TYPE_BEING_DEFINED (type) = 1;
1095
1096   if (! push_tinst_level (type))
1097     return type;
1098
1099   maybe_push_to_top_level (uses_template_parms (type));
1100   pushclass (type, 0);
1101
1102   if (flag_external_templates)
1103     {
1104       if (flag_alt_external_templates)
1105         {
1106           CLASSTYPE_INTERFACE_ONLY (type) = interface_only;
1107           SET_CLASSTYPE_INTERFACE_UNKNOWN_X (type, interface_unknown);
1108           CLASSTYPE_VTABLE_NEEDS_WRITING (type)
1109             = ! CLASSTYPE_INTERFACE_ONLY (type)
1110               && CLASSTYPE_INTERFACE_KNOWN (type);
1111         }
1112       else
1113         {
1114           CLASSTYPE_INTERFACE_ONLY (type) = CLASSTYPE_INTERFACE_ONLY (pattern);
1115           SET_CLASSTYPE_INTERFACE_UNKNOWN_X
1116             (type, CLASSTYPE_INTERFACE_UNKNOWN (pattern));
1117           CLASSTYPE_VTABLE_NEEDS_WRITING (type)
1118             = ! CLASSTYPE_INTERFACE_ONLY (type)
1119               && CLASSTYPE_INTERFACE_KNOWN (type);
1120         }
1121     }
1122   else
1123     {
1124       SET_CLASSTYPE_INTERFACE_UNKNOWN (type);
1125       CLASSTYPE_VTABLE_NEEDS_WRITING (type) = 1;
1126     }
1127
1128   {
1129     tree binfo = TYPE_BINFO (type);
1130     tree pbases = TYPE_BINFO_BASETYPES (pattern);
1131
1132     if (pbases)
1133       {
1134         tree bases;
1135         int i;
1136         int len = TREE_VEC_LENGTH (pbases);
1137         BINFO_BASETYPES (binfo) = bases = make_tree_vec (len);
1138         for (i = 0; i < len; ++i)
1139           {
1140             tree elt;
1141
1142             TREE_VEC_ELT (bases, i) = elt
1143               = tsubst (TREE_VEC_ELT (pbases, i), &TREE_VEC_ELT (args, 0),
1144                         TREE_VEC_LENGTH (args), NULL_TREE);
1145             BINFO_INHERITANCE_CHAIN (elt) = binfo;
1146
1147             if (! uses_template_parms (type) &&
1148                 TYPE_SIZE (complete_type (TREE_TYPE (elt))) == NULL_TREE)
1149               cp_error ("base class `%T' of `%T' has incomplete type",
1150                         TREE_TYPE (elt), type);
1151           }
1152       }
1153   }
1154
1155   CLASSTYPE_LOCAL_TYPEDECLS (type) = CLASSTYPE_LOCAL_TYPEDECLS (pattern);
1156
1157   field_chain = &TYPE_FIELDS (type);
1158
1159   for (t = CLASSTYPE_TAGS (pattern); t; t = TREE_CHAIN (t))
1160     {
1161       tree name = TREE_PURPOSE (t);
1162       tree tag = TREE_VALUE (t);
1163       tree newtag;
1164
1165       /* These will add themselves to CLASSTYPE_TAGS for the new type.  */
1166       if (TREE_CODE (tag) == ENUMERAL_TYPE)
1167         newtag = start_enum (name);
1168       else
1169         newtag = tsubst (tag, &TREE_VEC_ELT (args, 0),
1170                          TREE_VEC_LENGTH (args), NULL_TREE);
1171
1172       if (TREE_CODE (tag) == ENUMERAL_TYPE)
1173         {
1174           tree e, values = NULL_TREE, *last = &values;
1175
1176           for (e = TYPE_VALUES (tag); e; e = TREE_CHAIN (e))
1177             {
1178               tree elt = build_enumerator
1179                 (TREE_PURPOSE (e),
1180                  tsubst_expr (TREE_VALUE (e), &TREE_VEC_ELT (args, 0),
1181                               TREE_VEC_LENGTH (args), NULL_TREE));
1182               DECL_FIELD_CONTEXT (TREE_VALUE (elt)) = type;
1183               *last = elt;
1184               last = &TREE_CHAIN (elt);
1185             }
1186
1187           finish_enum (newtag, values);
1188
1189           *field_chain = grok_enum_decls (newtag, NULL_TREE);
1190           while (*field_chain)
1191             field_chain = &TREE_CHAIN (*field_chain);
1192         }
1193     }
1194
1195   /* Don't replace enum constants here.  */
1196   for (t = TYPE_FIELDS (pattern); t; t = TREE_CHAIN (t))
1197     if (TREE_CODE (t) != CONST_DECL)
1198       {
1199         tree r = tsubst (t, &TREE_VEC_ELT (args, 0),
1200                          TREE_VEC_LENGTH (args), NULL_TREE);
1201         if (TREE_CODE (r) == VAR_DECL)
1202           {
1203             if (! uses_template_parms (r))
1204               pending_statics = perm_tree_cons (NULL_TREE, r, pending_statics);
1205             /* Perhaps I should do more of grokfield here.  */
1206             start_decl_1 (r);
1207             DECL_IN_AGGR_P (r) = 1;
1208             DECL_EXTERNAL (r) = 1;
1209             cp_finish_decl (r, DECL_INITIAL (r), NULL_TREE, 0, 0);
1210           }
1211
1212         *field_chain = r;
1213         field_chain = &TREE_CHAIN (r);
1214       }
1215
1216   TYPE_METHODS (type) = tsubst_chain (TYPE_METHODS (pattern), args);
1217
1218   DECL_FRIENDLIST (TYPE_MAIN_DECL (type))
1219     = tsubst (DECL_FRIENDLIST (TYPE_MAIN_DECL (pattern)),
1220               &TREE_VEC_ELT (args, 0), TREE_VEC_LENGTH (args), NULL_TREE);
1221
1222   {
1223     tree d = CLASSTYPE_FRIEND_CLASSES (type) =
1224       tsubst (CLASSTYPE_FRIEND_CLASSES (pattern), &TREE_VEC_ELT (args, 0),
1225               TREE_VEC_LENGTH (args), NULL_TREE);
1226
1227     /* This does injection for friend classes.  */
1228     for (; d; d = TREE_CHAIN (d))
1229       TREE_VALUE (d) = xref_tag_from_type (TREE_VALUE (d), NULL_TREE, 1);
1230
1231     d = tsubst (DECL_TEMPLATE_INJECT (template), &TREE_VEC_ELT (args, 0),
1232                      TREE_VEC_LENGTH (args), NULL_TREE);
1233
1234     for (; d; d = TREE_CHAIN (d))
1235       {
1236         tree t = TREE_VALUE (d);
1237
1238         if (TREE_CODE (t) == TYPE_DECL)
1239           /* Already injected.  */;
1240         else
1241           pushdecl (t);
1242       }
1243   }
1244
1245   TYPE_HAS_CONSTRUCTOR (type) = TYPE_HAS_CONSTRUCTOR (pattern);
1246   TYPE_HAS_DESTRUCTOR (type) = TYPE_HAS_DESTRUCTOR (pattern);
1247   TYPE_HAS_ASSIGNMENT (type) = TYPE_HAS_ASSIGNMENT (pattern);
1248   TYPE_OVERLOADS_CALL_EXPR (type) = TYPE_OVERLOADS_CALL_EXPR (pattern);
1249   TYPE_OVERLOADS_ARRAY_REF (type) = TYPE_OVERLOADS_ARRAY_REF (pattern);
1250   TYPE_OVERLOADS_ARROW (type) = TYPE_OVERLOADS_ARROW (pattern);
1251   TYPE_GETS_NEW (type) = TYPE_GETS_NEW (pattern);
1252   TYPE_GETS_DELETE (type) = TYPE_GETS_DELETE (pattern);
1253   TYPE_VEC_DELETE_TAKES_SIZE (type) = TYPE_VEC_DELETE_TAKES_SIZE (pattern);
1254   TYPE_HAS_ASSIGN_REF (type) = TYPE_HAS_ASSIGN_REF (pattern);
1255   TYPE_HAS_CONST_ASSIGN_REF (type) = TYPE_HAS_CONST_ASSIGN_REF (pattern);
1256   TYPE_HAS_ABSTRACT_ASSIGN_REF (type) = TYPE_HAS_ABSTRACT_ASSIGN_REF (pattern);
1257   TYPE_HAS_INIT_REF (type) = TYPE_HAS_INIT_REF (pattern);
1258   TYPE_HAS_CONST_INIT_REF (type) = TYPE_HAS_CONST_INIT_REF (pattern);
1259   TYPE_GETS_INIT_AGGR (type) = TYPE_GETS_INIT_AGGR (pattern);
1260   TYPE_HAS_DEFAULT_CONSTRUCTOR (type) = TYPE_HAS_DEFAULT_CONSTRUCTOR (pattern);
1261   TYPE_HAS_CONVERSION (type) = TYPE_HAS_CONVERSION (pattern);
1262   TYPE_USES_COMPLEX_INHERITANCE (type)
1263     = TYPE_USES_COMPLEX_INHERITANCE (pattern);
1264   TYPE_USES_MULTIPLE_INHERITANCE (type)
1265     = TYPE_USES_MULTIPLE_INHERITANCE (pattern);
1266   TYPE_USES_VIRTUAL_BASECLASSES (type)
1267     = TYPE_USES_VIRTUAL_BASECLASSES (pattern);
1268   TYPE_PACKED (type) = TYPE_PACKED (pattern);
1269   TYPE_ALIGN (type) = TYPE_ALIGN (pattern);
1270
1271   if (! uses_template_parms (type))
1272     {
1273       tree tmp;
1274       for (tmp = TYPE_FIELDS (type); tmp; tmp = TREE_CHAIN (tmp))
1275         if (TREE_CODE (tmp) == FIELD_DECL)
1276           {
1277             TREE_TYPE (tmp) = complete_type (TREE_TYPE (tmp));
1278             require_complete_type (tmp);
1279           }
1280
1281       type = finish_struct_1 (type, 0);
1282       CLASSTYPE_GOT_SEMICOLON (type) = 1;
1283       if (at_eof && TYPE_BINFO_VTABLE (type) != NULL_TREE)
1284         finish_prevtable_vardecl (NULL, TYPE_BINFO_VTABLE (type));
1285
1286       repo_template_used (type);
1287     }
1288   else
1289     {
1290       TYPE_SIZE (type) = integer_zero_node;
1291       CLASSTYPE_METHOD_VEC (type)
1292         = finish_struct_methods (type, TYPE_METHODS (type), 1);
1293     }
1294
1295   TYPE_BEING_DEFINED (type) = 0;
1296   popclass (0);
1297
1298   pop_from_top_level ();
1299   pop_tinst_level ();
1300
1301   return type;
1302 }
1303
1304 static int
1305 list_eq (t1, t2)
1306      tree t1, t2;
1307 {
1308   if (t1 == NULL_TREE)
1309     return t2 == NULL_TREE;
1310   if (t2 == NULL_TREE)
1311     return 0;
1312   /* Don't care if one declares its arg const and the other doesn't -- the
1313      main variant of the arg type is all that matters.  */
1314   if (TYPE_MAIN_VARIANT (TREE_VALUE (t1))
1315       != TYPE_MAIN_VARIANT (TREE_VALUE (t2)))
1316     return 0;
1317   return list_eq (TREE_CHAIN (t1), TREE_CHAIN (t2));
1318 }
1319
1320 tree
1321 lookup_nested_type_by_name (ctype, name)
1322         tree ctype, name;
1323 {
1324   tree t;
1325
1326   complete_type (ctype);
1327
1328   for (t = CLASSTYPE_TAGS (ctype); t; t = TREE_CHAIN (t))
1329     {
1330       if (name == TREE_PURPOSE (t))
1331         return TREE_VALUE (t);
1332     }
1333   return NULL_TREE;
1334 }
1335
1336 tree
1337 tsubst (t, args, nargs, in_decl)
1338      tree t, *args;
1339      int nargs;
1340      tree in_decl;
1341 {
1342   tree type;
1343
1344   if (t == NULL_TREE || t == error_mark_node
1345       || t == integer_type_node
1346       || t == void_type_node
1347       || t == char_type_node)
1348     return t;
1349
1350   type = TREE_TYPE (t);
1351   if (type == unknown_type_node)
1352     my_friendly_abort (42);
1353   if (type && TREE_CODE (t) != FUNCTION_DECL)
1354     type = tsubst (type, args, nargs, in_decl);
1355
1356   switch (TREE_CODE (t))
1357     {
1358     case RECORD_TYPE:
1359       if (TYPE_PTRMEMFUNC_P (t))
1360         {
1361           tree r = build_ptrmemfunc_type
1362             (tsubst (TYPE_PTRMEMFUNC_FN_TYPE (t), args, nargs, in_decl));
1363           return cp_build_type_variant (r, TYPE_READONLY (t),
1364                                         TYPE_VOLATILE (t));
1365         }
1366
1367       /* else fall through */
1368     case UNION_TYPE:
1369       if (uses_template_parms (t))
1370         {
1371           tree argvec = tsubst (CLASSTYPE_TI_ARGS (t), args, nargs, in_decl);
1372           tree r = lookup_template_class (t, argvec, in_decl);
1373           return cp_build_type_variant (r, TYPE_READONLY (t),
1374                                         TYPE_VOLATILE (t));
1375         }
1376
1377       /* else fall through */
1378     case ERROR_MARK:
1379     case IDENTIFIER_NODE:
1380     case OP_IDENTIFIER:
1381     case VOID_TYPE:
1382     case REAL_TYPE:
1383     case BOOLEAN_TYPE:
1384     case INTEGER_CST:
1385     case REAL_CST:
1386     case STRING_CST:
1387       return t;
1388
1389     case ENUMERAL_TYPE:
1390       {
1391         tree ctx = tsubst (TYPE_CONTEXT (t), args, nargs, in_decl);
1392         if (ctx == NULL_TREE)
1393           return t;
1394         else
1395           return lookup_nested_type_by_name (ctx, TYPE_IDENTIFIER (t));
1396       }
1397
1398     case INTEGER_TYPE:
1399       if (t == integer_type_node)
1400         return t;
1401
1402       if (TREE_CODE (TYPE_MIN_VALUE (t)) == INTEGER_CST
1403           && TREE_CODE (TYPE_MAX_VALUE (t)) == INTEGER_CST)
1404         return t;
1405
1406       {
1407         tree max = tsubst_expr (TYPE_MAX_VALUE (t), args, nargs, in_decl);
1408         if (processing_template_decl)
1409           {
1410             tree itype = make_node (INTEGER_TYPE);
1411             TYPE_MIN_VALUE (itype) = size_zero_node;
1412             TYPE_MAX_VALUE (itype) = max;
1413             return itype;
1414           }
1415         return build_index_2_type (size_zero_node, max);
1416       }
1417
1418     case TEMPLATE_TYPE_PARM:
1419       {
1420         tree arg = args[TEMPLATE_TYPE_IDX (t)];
1421         return cp_build_type_variant
1422           (arg, TYPE_READONLY (arg) || TYPE_READONLY (t),
1423            TYPE_VOLATILE (arg) || TYPE_VOLATILE (t));
1424       }
1425
1426     case TEMPLATE_CONST_PARM:
1427       return args[TEMPLATE_CONST_IDX (t)];
1428
1429     case FUNCTION_DECL:
1430       {
1431         tree r = NULL_TREE;
1432         tree arg_types, ctx;
1433
1434         int member;
1435
1436         if (DECL_CONTEXT (t) != NULL_TREE
1437             && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't')
1438           {
1439             if (DECL_NAME (t) == constructor_name (DECL_CONTEXT (t)))
1440               member = 2;
1441             else
1442               member = 1;
1443             ctx = tsubst (DECL_CLASS_CONTEXT (t), args, nargs, t);
1444             type = tsubst (type, args, nargs, in_decl);
1445           }
1446         else
1447           {
1448             member = 0;
1449             ctx = NULL_TREE;
1450             type = tsubst (type, args, nargs, in_decl);
1451           }
1452
1453         if (type == TREE_TYPE (t)
1454             && (! member || ctx == DECL_CLASS_CONTEXT (t)))
1455           {
1456             t = copy_node (t);
1457             copy_lang_decl (t);
1458             return t;
1459           }
1460
1461         /* Do we already have this instantiation?  */
1462         if (DECL_TEMPLATE_INFO (t) != NULL_TREE)
1463           {
1464             tree tmpl = TREE_PURPOSE (DECL_TEMPLATE_INFO (t));
1465             tree decls = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1466
1467             for (; decls; decls = TREE_CHAIN (decls))
1468               if (TREE_TYPE (TREE_VALUE (decls)) == type
1469                   && DECL_CLASS_CONTEXT (TREE_VALUE (decls)) == ctx)
1470                 return TREE_VALUE (decls);
1471           }
1472
1473         /* We do NOT check for matching decls pushed separately at this
1474            point, as they may not represent instantiations of this
1475            template, and in any case are considered separate under the
1476            discrete model.  */
1477
1478         r = copy_node (t);
1479         copy_lang_decl (r);
1480         TREE_TYPE (r) = type;
1481
1482         DECL_CONTEXT (r)
1483           = tsubst (DECL_CONTEXT (t), args, nargs, t);
1484         DECL_CLASS_CONTEXT (r) = ctx;
1485
1486         if (member && !strncmp (OPERATOR_TYPENAME_FORMAT,
1487                                 IDENTIFIER_POINTER (DECL_NAME (r)),
1488                                 sizeof (OPERATOR_TYPENAME_FORMAT) - 1))
1489           {
1490             /* Type-conversion operator.  Reconstruct the name, in
1491                case it's the name of one of the template's parameters.  */
1492             DECL_NAME (r) = build_typename_overload (TREE_TYPE (type));
1493           }
1494
1495         arg_types = TYPE_VALUES (type);
1496
1497         if (member && TREE_CODE (type) == FUNCTION_TYPE)
1498           arg_types = hash_tree_chain
1499             (build_pointer_type (DECL_CONTEXT (r)), arg_types);
1500
1501         if (DESTRUCTOR_NAME_P (DECL_ASSEMBLER_NAME (t)))
1502           {
1503             char *buf, *dbuf = build_overload_name (ctx, 1, 1);
1504             int len = sizeof (DESTRUCTOR_DECL_PREFIX) - 1;
1505             buf = (char *) alloca (strlen (dbuf)
1506                                    + sizeof (DESTRUCTOR_DECL_PREFIX));
1507             bcopy (DESTRUCTOR_DECL_PREFIX, buf, len);
1508             buf[len] = '\0';
1509             strcat (buf, dbuf);
1510             DECL_ASSEMBLER_NAME (r) = get_identifier (buf);
1511           }
1512         else
1513           DECL_ASSEMBLER_NAME (r)
1514             = build_decl_overload (DECL_NAME (r), arg_types, member);
1515         DECL_RTL (r) = 0;
1516         make_decl_rtl (r, NULL_PTR, 1);
1517
1518         DECL_ARGUMENTS (r) = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
1519         DECL_MAIN_VARIANT (r) = r;
1520         DECL_RESULT (r) = NULL_TREE;
1521         DECL_INITIAL (r) = NULL_TREE;
1522
1523         TREE_STATIC (r) = 0;
1524         TREE_PUBLIC (r) = 1;
1525         DECL_EXTERNAL (r) = 1;
1526         DECL_INTERFACE_KNOWN (r) = 0;
1527         DECL_DEFER_OUTPUT (r) = 0;
1528         TREE_CHAIN (r) = NULL_TREE;
1529         DECL_CHAIN (r) = NULL_TREE;
1530
1531         if (IDENTIFIER_OPNAME_P (DECL_NAME (r)))
1532           grok_op_properties (r, DECL_VIRTUAL_P (r), DECL_FRIEND_P (r));
1533
1534         /* Look for matching decls for the moment.  */
1535         if (! member)
1536           {
1537             tree decls = lookup_name_nonclass (DECL_NAME (t));
1538             tree d = NULL_TREE;
1539
1540             if (decls == NULL_TREE)
1541               /* no match */;
1542             else if (is_overloaded_fn (decls))
1543               for (decls = get_first_fn (decls); decls;
1544                    decls = DECL_CHAIN (decls))
1545                 {
1546                   if (TREE_CODE (decls) == FUNCTION_DECL
1547                       && TREE_TYPE (decls) == type)
1548                     {
1549                       d = decls;
1550                       break;
1551                     }
1552                 }
1553
1554             if (d)
1555               {
1556                 int dcl_only = ! DECL_INITIAL (d);
1557                 if (dcl_only)
1558                   DECL_INITIAL (r) = error_mark_node;
1559                 duplicate_decls (r, d);
1560                 r = d;
1561                 if (dcl_only)
1562                   DECL_INITIAL (r) = 0;
1563               }
1564           }
1565
1566         if (DECL_TEMPLATE_INFO (t) != NULL_TREE)
1567           {
1568             tree tmpl = DECL_TI_TEMPLATE (t);
1569             tree *declsp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1570             tree argvec = tsubst (TREE_VALUE (DECL_TEMPLATE_INFO (t)),
1571                                   args, nargs, in_decl);
1572
1573             DECL_TEMPLATE_INFO (r) = perm_tree_cons (tmpl, argvec, NULL_TREE);
1574             *declsp = perm_tree_cons (argvec, r, *declsp);
1575
1576             /* If we have a preexisting version of this function, don't expand
1577                the template version, use the other instead.  */
1578             if (TREE_STATIC (r) || DECL_TEMPLATE_SPECIALIZATION (r))
1579               SET_DECL_TEMPLATE_SPECIALIZATION (r);
1580             else
1581               SET_DECL_IMPLICIT_INSTANTIATION (r);
1582
1583             DECL_TEMPLATE_INSTANTIATIONS (tmpl) =
1584               tree_cons (argvec, r, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1585           }
1586
1587         /* Like grokfndecl.  If we don't do this, pushdecl will mess up our
1588            TREE_CHAIN because it doesn't find a previous decl.  Sigh.  */
1589         if (member
1590             && IDENTIFIER_GLOBAL_VALUE (DECL_ASSEMBLER_NAME (r)) == NULL_TREE)
1591           IDENTIFIER_GLOBAL_VALUE (DECL_ASSEMBLER_NAME (r)) = r;
1592
1593         return r;
1594       }
1595
1596     case PARM_DECL:
1597       {
1598         tree r = copy_node (t);
1599         TREE_TYPE (r) = type;
1600         DECL_INITIAL (r) = TREE_TYPE (r);
1601         DECL_CONTEXT (r) = NULL_TREE;
1602 #ifdef PROMOTE_PROTOTYPES
1603         if ((TREE_CODE (type) == INTEGER_TYPE
1604              || TREE_CODE (type) == ENUMERAL_TYPE)
1605             && TYPE_PRECISION (type) < TYPE_PRECISION (integer_type_node))
1606           DECL_ARG_TYPE (r) = integer_type_node;
1607 #endif
1608         if (TREE_CHAIN (t))
1609           TREE_CHAIN (r) = tsubst (TREE_CHAIN (t), args, nargs, TREE_CHAIN (t));
1610         return r;
1611       }
1612
1613     case FIELD_DECL:
1614       {
1615         tree r = copy_node (t);
1616         TREE_TYPE (r) = type;
1617         copy_lang_decl (r);
1618 #if 0
1619         DECL_FIELD_CONTEXT (r) = tsubst (DECL_FIELD_CONTEXT (t), args, nargs, in_decl);
1620 #endif
1621         DECL_INITIAL (r) = tsubst_expr (DECL_INITIAL (t), args, nargs, in_decl);
1622         TREE_CHAIN (r) = NULL_TREE;
1623         return r;
1624       }
1625
1626     case USING_DECL:
1627       {
1628         tree r = copy_node (t);
1629         DECL_INITIAL (r)
1630           = tsubst_copy (DECL_INITIAL (t), args, nargs, in_decl);
1631         TREE_CHAIN (r) = NULL_TREE;
1632         return r;
1633       }
1634
1635     case VAR_DECL:
1636       {
1637         tree r;
1638         tree ctx = tsubst_copy (DECL_CONTEXT (t), args, nargs, in_decl);
1639
1640         /* Do we already have this instantiation?  */
1641         if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
1642           {
1643             tree tmpl = DECL_TI_TEMPLATE (t);
1644             tree decls = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1645
1646             for (; decls; decls = TREE_CHAIN (decls))
1647               if (DECL_CONTEXT (TREE_VALUE (decls)) == ctx)
1648                 return TREE_VALUE (decls);
1649           }
1650
1651         r = copy_node (t);
1652         TREE_TYPE (r) = type;
1653         DECL_CONTEXT (r) = ctx;
1654         if (TREE_STATIC (r))
1655           DECL_ASSEMBLER_NAME (r)
1656             = build_static_name (DECL_CONTEXT (r), DECL_NAME (r));
1657
1658         /* Don't try to expand the initializer until someone tries to use
1659            this variable; otherwise we run into circular dependencies.  */
1660         DECL_INITIAL (r) = NULL_TREE;
1661
1662         DECL_RTL (r) = 0;
1663         DECL_SIZE (r) = 0;
1664
1665         if (DECL_LANG_SPECIFIC (r))
1666           {
1667             copy_lang_decl (r);
1668             DECL_CLASS_CONTEXT (r) = DECL_CONTEXT (r);
1669           }
1670
1671         if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
1672           {
1673             tree tmpl = DECL_TI_TEMPLATE (t);
1674             tree *declsp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1675             tree argvec = tsubst (TREE_VALUE (DECL_TEMPLATE_INFO (t)),
1676                                   args, nargs, in_decl);
1677
1678             DECL_TEMPLATE_INFO (r) = perm_tree_cons (tmpl, argvec, NULL_TREE);
1679             *declsp = perm_tree_cons (argvec, r, *declsp);
1680             SET_DECL_IMPLICIT_INSTANTIATION (r);
1681           }
1682         TREE_CHAIN (r) = NULL_TREE;
1683         return r;
1684       }
1685
1686     case TYPE_DECL:
1687       if (t == TYPE_NAME (TREE_TYPE (t)))
1688         return TYPE_NAME (type);
1689
1690       {
1691         tree r = copy_node (t);
1692         TREE_TYPE (r) = type;
1693         DECL_CONTEXT (r) = current_class_type;
1694         TREE_CHAIN (r) = NULL_TREE;
1695         return r;
1696       }
1697
1698     case TREE_LIST:
1699       {
1700         tree purpose, value, chain, result;
1701         int via_public, via_virtual, via_protected;
1702
1703         if (t == void_list_node)
1704           return t;
1705
1706         via_public = TREE_VIA_PUBLIC (t);
1707         via_protected = TREE_VIA_PROTECTED (t);
1708         via_virtual = TREE_VIA_VIRTUAL (t);
1709
1710         purpose = TREE_PURPOSE (t);
1711         if (purpose)
1712           purpose = tsubst (purpose, args, nargs, in_decl);
1713         value = TREE_VALUE (t);
1714         if (value)
1715           value = tsubst (value, args, nargs, in_decl);
1716         chain = TREE_CHAIN (t);
1717         if (chain && chain != void_type_node)
1718           chain = tsubst (chain, args, nargs, in_decl);
1719         if (purpose == TREE_PURPOSE (t)
1720             && value == TREE_VALUE (t)
1721             && chain == TREE_CHAIN (t))
1722           return t;
1723         result = hash_tree_cons (via_public, via_virtual, via_protected,
1724                                  purpose, value, chain);
1725         TREE_PARMLIST (result) = TREE_PARMLIST (t);
1726         return result;
1727       }
1728     case TREE_VEC:
1729       if (type != NULL_TREE)
1730         {
1731           t = copy_node (t);
1732
1733           if (type == TREE_TYPE (t))
1734             return t;
1735
1736           TREE_TYPE (t) = complete_type (type);
1737           BINFO_VTABLE (t) = TYPE_BINFO_VTABLE (type);
1738           BINFO_VIRTUALS (t) = TYPE_BINFO_VIRTUALS (type);
1739           if (TYPE_BINFO_BASETYPES (type) != NULL_TREE)
1740             BINFO_BASETYPES (t) = copy_node (TYPE_BINFO_BASETYPES (type));
1741
1742           return t;
1743         }
1744       {
1745         int len = TREE_VEC_LENGTH (t), need_new = 0, i;
1746         tree *elts = (tree *) alloca (len * sizeof (tree));
1747
1748         bzero ((char *) elts, len * sizeof (tree));
1749
1750         for (i = 0; i < len; i++)
1751           {
1752             elts[i] = tsubst_expr (TREE_VEC_ELT (t, i), args, nargs, in_decl);
1753             if (elts[i] != TREE_VEC_ELT (t, i))
1754               need_new = 1;
1755           }
1756
1757         if (!need_new)
1758           return t;
1759
1760         t = make_tree_vec (len);
1761         for (i = 0; i < len; i++)
1762           TREE_VEC_ELT (t, i) = elts[i];
1763
1764         return t;
1765       }
1766     case POINTER_TYPE:
1767     case REFERENCE_TYPE:
1768       {
1769         tree r;
1770         enum tree_code code;
1771         if (type == TREE_TYPE (t))
1772           return t;
1773
1774         code = TREE_CODE (t);
1775         if (code == POINTER_TYPE)
1776           r = build_pointer_type (type);
1777         else
1778           r = build_reference_type (type);
1779         r = cp_build_type_variant (r, TYPE_READONLY (t), TYPE_VOLATILE (t));
1780         /* Will this ever be needed for TYPE_..._TO values?  */
1781         layout_type (r);
1782         return r;
1783       }
1784     case OFFSET_TYPE:
1785       return build_offset_type
1786         (tsubst (TYPE_OFFSET_BASETYPE (t), args, nargs, in_decl), type);
1787     case FUNCTION_TYPE:
1788     case METHOD_TYPE:
1789       {
1790         tree values = TYPE_ARG_TYPES (t);
1791         tree context = TYPE_CONTEXT (t);
1792         tree raises = TYPE_RAISES_EXCEPTIONS (t);
1793         tree fntype;
1794
1795         /* Don't bother recursing if we know it won't change anything.  */
1796         if (values != void_list_node)
1797           {
1798             /* This should probably be rewritten to use hash_tree_cons for
1799                the memory savings.  */
1800             tree first = NULL_TREE;
1801             tree last;
1802
1803             for (; values && values != void_list_node;
1804                  values = TREE_CHAIN (values))
1805               {
1806                 tree value
1807                   = tsubst (TREE_VALUE (values), args, nargs, in_decl);
1808                 tree purpose = tsubst_expr (TREE_PURPOSE (values),
1809                                             args, nargs, in_decl);
1810                 tree x = build_tree_list (purpose, value);
1811
1812                 if (first)
1813                   TREE_CHAIN (last) = x;
1814                 else
1815                   first = x;
1816                 last = x;
1817               }
1818
1819             if (values == void_list_node)
1820               TREE_CHAIN (last) = void_list_node;
1821
1822             values = first;
1823           }
1824         if (context)
1825           context = tsubst (context, args, nargs, in_decl);
1826         /* Could also optimize cases where return value and
1827            values have common elements (e.g., T min(const &T, const T&).  */
1828
1829         /* If the above parameters haven't changed, just return the type.  */
1830         if (type == TREE_TYPE (t)
1831             && values == TYPE_VALUES (t)
1832             && context == TYPE_CONTEXT (t))
1833           return t;
1834
1835         /* Construct a new type node and return it.  */
1836         if (TREE_CODE (t) == FUNCTION_TYPE
1837             && context == NULL_TREE)
1838           {
1839             fntype = build_function_type (type, values);
1840           }
1841         else if (context == NULL_TREE)
1842           {
1843             tree base = tsubst (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (t))),
1844                                 args, nargs, in_decl);
1845             fntype = build_cplus_method_type (base, type,
1846                                               TREE_CHAIN (values));
1847           }
1848         else
1849           {
1850             fntype = make_node (TREE_CODE (t));
1851             TREE_TYPE (fntype) = type;
1852             TYPE_CONTEXT (fntype) = context;
1853             TYPE_VALUES (fntype) = values;
1854             TYPE_SIZE (fntype) = TYPE_SIZE (t);
1855             TYPE_ALIGN (fntype) = TYPE_ALIGN (t);
1856             TYPE_MODE (fntype) = TYPE_MODE (t);
1857             if (TYPE_METHOD_BASETYPE (t))
1858               TYPE_METHOD_BASETYPE (fntype) = tsubst (TYPE_METHOD_BASETYPE (t),
1859                                                       args, nargs, in_decl);
1860             /* Need to generate hash value.  */
1861             my_friendly_abort (84);
1862           }
1863         fntype = build_type_variant (fntype,
1864                                      TYPE_READONLY (t),
1865                                      TYPE_VOLATILE (t));
1866         if (raises)
1867           {
1868             raises = tsubst (raises, args, nargs, in_decl);
1869             fntype = build_exception_variant (fntype, raises);
1870           }
1871         return fntype;
1872       }
1873     case ARRAY_TYPE:
1874       {
1875         tree domain = tsubst (TYPE_DOMAIN (t), args, nargs, in_decl);
1876         tree r;
1877         if (type == TREE_TYPE (t) && domain == TYPE_DOMAIN (t))
1878           return t;
1879         r = build_cplus_array_type (type, domain);
1880         return r;
1881       }
1882
1883     case PLUS_EXPR:
1884     case MINUS_EXPR:
1885       return fold (build (TREE_CODE (t), TREE_TYPE (t),
1886                           tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1887                           tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl)));
1888
1889     case NEGATE_EXPR:
1890     case NOP_EXPR:
1891       return fold (build1 (TREE_CODE (t), TREE_TYPE (t),
1892                            tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl)));
1893
1894     case TYPENAME_TYPE:
1895       {
1896         tree ctx = tsubst (TYPE_CONTEXT (t), args, nargs, in_decl);
1897         tree f = make_typename_type (ctx, TYPE_IDENTIFIER (t));
1898         return cp_build_type_variant
1899           (f, TYPE_READONLY (f) || TYPE_READONLY (t),
1900            TYPE_VOLATILE (f) || TYPE_VOLATILE (t));
1901       }
1902
1903     case INDIRECT_REF:
1904       return make_pointer_declarator
1905         (type, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl));
1906
1907     case ADDR_EXPR:
1908       return make_reference_declarator
1909         (type, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl));
1910
1911     case ARRAY_REF:
1912       return build_parse_node
1913         (ARRAY_REF, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1914          tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl));
1915
1916     case CALL_EXPR:
1917       return make_call_declarator
1918         (tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1919          tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl),
1920          TREE_OPERAND (t, 2),
1921          tsubst (TREE_TYPE (t), args, nargs, in_decl));
1922
1923     case SCOPE_REF:
1924       return build_parse_node
1925         (TREE_CODE (t), tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1926          tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl));
1927
1928     default:
1929       sorry ("use of `%s' in template",
1930              tree_code_name [(int) TREE_CODE (t)]);
1931       return error_mark_node;
1932     }
1933 }
1934
1935 void
1936 do_pushlevel ()
1937 {
1938   emit_line_note (input_filename, lineno);
1939   pushlevel (0);
1940   clear_last_expr ();
1941   push_momentary ();
1942   expand_start_bindings (0);
1943 }
1944
1945 tree
1946 do_poplevel ()
1947 {
1948   tree t;
1949
1950   expand_end_bindings (getdecls (), kept_level_p (), 1);
1951   t = poplevel (kept_level_p (), 1, 0);
1952   pop_momentary ();
1953   return t;
1954 }
1955
1956 tree
1957 tsubst_copy (t, args, nargs, in_decl)
1958      tree t, *args;
1959      int nargs;
1960      tree in_decl;
1961 {
1962   enum tree_code code;
1963
1964   if (t == NULL_TREE || t == error_mark_node)
1965     return t;
1966
1967   code = TREE_CODE (t);
1968
1969   switch (code)
1970     {
1971     case PARM_DECL:
1972       return do_identifier (DECL_NAME (t), 0);
1973
1974     case CONST_DECL:
1975     case FIELD_DECL:
1976       if (DECL_CONTEXT (t))
1977         {
1978           tree ctx = tsubst (DECL_CONTEXT (t), args, nargs, in_decl);
1979           if (ctx != DECL_CONTEXT (t))
1980             return lookup_field (ctx, DECL_NAME (t), 0, 0);
1981         }
1982       return t;
1983
1984     case VAR_DECL:
1985     case FUNCTION_DECL:
1986       if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
1987         t = tsubst (t, args, nargs, in_decl);
1988       mark_used (t);
1989       return t;
1990
1991 #if 0
1992     case IDENTIFIER_NODE:
1993       return do_identifier (t, 0);
1994 #endif
1995
1996     case CAST_EXPR:
1997     case REINTERPRET_CAST_EXPR:
1998     case CONST_CAST_EXPR:
1999     case STATIC_CAST_EXPR:
2000     case DYNAMIC_CAST_EXPR:
2001       return build1
2002         (code, tsubst (TREE_TYPE (t), args, nargs, in_decl),
2003          tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl));
2004
2005     case INDIRECT_REF:
2006     case PREDECREMENT_EXPR:
2007     case PREINCREMENT_EXPR:
2008     case POSTDECREMENT_EXPR:
2009     case POSTINCREMENT_EXPR:
2010     case NEGATE_EXPR:
2011     case TRUTH_NOT_EXPR:
2012     case ADDR_EXPR:
2013     case CONVERT_EXPR:      /* Unary + */
2014     case SIZEOF_EXPR:
2015     case ARROW_EXPR:
2016     case THROW_EXPR:
2017     case TYPEID_EXPR:
2018       return build1
2019         (code, NULL_TREE,
2020          tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl));
2021
2022     case PLUS_EXPR:
2023     case MINUS_EXPR:
2024     case MULT_EXPR:
2025     case TRUNC_DIV_EXPR:
2026     case CEIL_DIV_EXPR:
2027     case FLOOR_DIV_EXPR:
2028     case ROUND_DIV_EXPR:
2029     case EXACT_DIV_EXPR:
2030     case BIT_AND_EXPR:
2031     case BIT_ANDTC_EXPR:
2032     case BIT_IOR_EXPR:
2033     case BIT_XOR_EXPR:
2034     case TRUNC_MOD_EXPR:
2035     case FLOOR_MOD_EXPR:
2036     case TRUTH_ANDIF_EXPR:
2037     case TRUTH_ORIF_EXPR:
2038     case TRUTH_AND_EXPR:
2039     case TRUTH_OR_EXPR:
2040     case RSHIFT_EXPR:
2041     case LSHIFT_EXPR:
2042     case RROTATE_EXPR:
2043     case LROTATE_EXPR:
2044     case EQ_EXPR:
2045     case NE_EXPR:
2046     case MAX_EXPR:
2047     case MIN_EXPR:
2048     case LE_EXPR:
2049     case GE_EXPR:
2050     case LT_EXPR:
2051     case GT_EXPR:
2052     case COMPONENT_REF:
2053     case ARRAY_REF:
2054     case COMPOUND_EXPR:
2055     case SCOPE_REF:
2056     case DOTSTAR_EXPR:
2057     case MEMBER_REF:
2058       return build_nt
2059         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2060          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl));
2061
2062     case CALL_EXPR:
2063       {
2064         tree fn = TREE_OPERAND (t, 0);
2065         if (really_overloaded_fn (fn))
2066           fn = tsubst_copy (TREE_VALUE (fn), args, nargs, in_decl);
2067         else
2068           fn = tsubst_copy (fn, args, nargs, in_decl);
2069         return build_nt
2070           (code, fn, tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2071            NULL_TREE);
2072       }
2073
2074     case METHOD_CALL_EXPR:
2075       {
2076         tree name = TREE_OPERAND (t, 0);
2077         if (TREE_CODE (name) == BIT_NOT_EXPR)
2078           {
2079             name = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
2080             name = build1 (BIT_NOT_EXPR, NULL_TREE, TYPE_MAIN_VARIANT (name));
2081           }
2082         else if (TREE_CODE (name) == SCOPE_REF
2083                  && TREE_CODE (TREE_OPERAND (name, 1)) == BIT_NOT_EXPR)
2084           {
2085             tree base = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
2086             name = TREE_OPERAND (name, 1);
2087             name = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
2088             name = build1 (BIT_NOT_EXPR, NULL_TREE, TYPE_MAIN_VARIANT (name));
2089             name = build_nt (SCOPE_REF, base, name);
2090           }
2091         else
2092           name = tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl);
2093         return build_nt
2094           (code, name, tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2095            tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl),
2096            NULL_TREE);
2097       }
2098
2099     case COND_EXPR:
2100     case MODOP_EXPR:
2101       return build_nt
2102         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2103          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2104          tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl));
2105
2106     case NEW_EXPR:
2107       {
2108         tree r = build_nt
2109         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2110          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2111          tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl));
2112         NEW_EXPR_USE_GLOBAL (r) = NEW_EXPR_USE_GLOBAL (t);
2113         return r;
2114       }
2115
2116     case DELETE_EXPR:
2117       {
2118         tree r = build_nt
2119         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2120          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl));
2121         DELETE_EXPR_USE_GLOBAL (r) = DELETE_EXPR_USE_GLOBAL (t);
2122         DELETE_EXPR_USE_VEC (r) = DELETE_EXPR_USE_VEC (t);
2123         return r;
2124       }
2125
2126     case TREE_LIST:
2127       {
2128         tree purpose, value, chain;
2129
2130         if (t == void_list_node)
2131           return t;
2132
2133         purpose = TREE_PURPOSE (t);
2134         if (purpose)
2135           purpose = tsubst_copy (purpose, args, nargs, in_decl);
2136         value = TREE_VALUE (t);
2137         if (value)
2138           value = tsubst_copy (value, args, nargs, in_decl);
2139         chain = TREE_CHAIN (t);
2140         if (chain && chain != void_type_node)
2141           chain = tsubst_copy (chain, args, nargs, in_decl);
2142         if (purpose == TREE_PURPOSE (t)
2143             && value == TREE_VALUE (t)
2144             && chain == TREE_CHAIN (t))
2145           return t;
2146         return tree_cons (purpose, value, chain);
2147       }
2148
2149     case RECORD_TYPE:
2150     case UNION_TYPE:
2151     case ENUMERAL_TYPE:
2152     case INTEGER_TYPE:
2153     case TEMPLATE_TYPE_PARM:
2154     case TEMPLATE_CONST_PARM:
2155     case POINTER_TYPE:
2156     case REFERENCE_TYPE:
2157     case OFFSET_TYPE:
2158     case FUNCTION_TYPE:
2159     case METHOD_TYPE:
2160     case ARRAY_TYPE:
2161     case TYPENAME_TYPE:
2162       return tsubst (t, args, nargs, in_decl);
2163
2164     case IDENTIFIER_NODE:
2165       if (IDENTIFIER_TYPENAME_P (t))
2166         return build_typename_overload
2167           (tsubst (TREE_TYPE (t), args, nargs, in_decl));
2168       else
2169         return t;
2170
2171     case CONSTRUCTOR:
2172       return build
2173         (CONSTRUCTOR, tsubst (TREE_TYPE (t), args, nargs, in_decl), NULL_TREE,
2174          tsubst_copy (CONSTRUCTOR_ELTS (t), args, nargs, in_decl));
2175
2176     default:
2177       return t;
2178     }
2179 }
2180
2181 tree
2182 tsubst_expr (t, args, nargs, in_decl)
2183      tree t, *args;
2184      int nargs;
2185      tree in_decl;
2186 {
2187   if (t == NULL_TREE || t == error_mark_node)
2188     return t;
2189
2190   if (processing_template_decl)
2191     return tsubst_copy (t, args, nargs, in_decl);
2192
2193   switch (TREE_CODE (t))
2194     {
2195     case RETURN_STMT:
2196       lineno = TREE_COMPLEXITY (t);
2197       emit_line_note (input_filename, lineno);
2198       c_expand_return
2199         (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl));
2200       finish_stmt ();
2201       break;
2202
2203     case EXPR_STMT:
2204       lineno = TREE_COMPLEXITY (t);
2205       emit_line_note (input_filename, lineno);
2206       t = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2207       /* Do default conversion if safe and possibly important,
2208          in case within ({...}).  */
2209       if ((TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE && lvalue_p (t))
2210           || TREE_CODE (TREE_TYPE (t)) == FUNCTION_TYPE)
2211         t = default_conversion (t);
2212       cplus_expand_expr_stmt (t);
2213       clear_momentary ();
2214       finish_stmt ();
2215       break;
2216
2217     case DECL_STMT:
2218       {
2219         int i = suspend_momentary ();
2220         tree dcl, init;
2221
2222         lineno = TREE_COMPLEXITY (t);
2223         emit_line_note (input_filename, lineno);
2224         dcl = start_decl
2225           (tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
2226            tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl),
2227            TREE_OPERAND (t, 2) != 0);
2228         init = tsubst_expr (TREE_OPERAND (t, 2), args, nargs, in_decl);
2229         cp_finish_decl
2230           (dcl, init, NULL_TREE, 1, /*init ? LOOKUP_ONLYCONVERTING :*/ 0);
2231         resume_momentary (i);
2232         return dcl;
2233       }
2234
2235     case FOR_STMT:
2236       {
2237         tree tmp;
2238         int init_scope = (flag_new_for_scope > 0 && TREE_OPERAND (t, 0)
2239                           && TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
2240         int cond_scope = (TREE_OPERAND (t, 1)
2241                           && TREE_CODE (TREE_OPERAND (t, 1)) == DECL_STMT);
2242
2243         lineno = TREE_COMPLEXITY (t);
2244         emit_line_note (input_filename, lineno);
2245         if (init_scope)
2246           do_pushlevel ();
2247         for (tmp = TREE_OPERAND (t, 0); tmp; tmp = TREE_CHAIN (tmp))
2248           tsubst_expr (tmp, args, nargs, in_decl);
2249         emit_nop ();
2250         emit_line_note (input_filename, lineno);
2251         expand_start_loop_continue_elsewhere (1);
2252
2253         if (cond_scope)
2254           do_pushlevel ();
2255         tmp = tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2256         emit_line_note (input_filename, lineno);
2257         if (tmp)
2258           expand_exit_loop_if_false (0, condition_conversion (tmp));
2259
2260         if (! cond_scope)
2261           do_pushlevel ();
2262         tsubst_expr (TREE_OPERAND (t, 3), args, nargs, in_decl);
2263         do_poplevel ();
2264
2265         emit_line_note (input_filename, lineno);
2266         expand_loop_continue_here ();
2267         tmp = tsubst_expr (TREE_OPERAND (t, 2), args, nargs, in_decl);
2268         if (tmp)
2269           cplus_expand_expr_stmt (tmp);
2270
2271         expand_end_loop ();
2272         if (init_scope)
2273           do_poplevel ();
2274         finish_stmt ();
2275       }
2276       break;
2277
2278     case WHILE_STMT:
2279       {
2280         tree cond;
2281
2282         lineno = TREE_COMPLEXITY (t);
2283         emit_nop ();
2284         emit_line_note (input_filename, lineno);
2285         expand_start_loop (1);
2286
2287         cond = TREE_OPERAND (t, 0);
2288         if (TREE_CODE (cond) == DECL_STMT)
2289           do_pushlevel ();
2290         cond = tsubst_expr (cond, args, nargs, in_decl);
2291         emit_line_note (input_filename, lineno);
2292         expand_exit_loop_if_false (0, condition_conversion (cond));
2293
2294         if (TREE_CODE (TREE_OPERAND (t, 0)) != DECL_STMT)
2295           do_pushlevel ();
2296         tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2297         do_poplevel ();
2298
2299         expand_end_loop ();
2300         finish_stmt ();
2301       }
2302       break;
2303
2304     case DO_STMT:
2305       {
2306         tree cond;
2307
2308         lineno = TREE_COMPLEXITY (t);
2309         emit_nop ();
2310         emit_line_note (input_filename, lineno);
2311         expand_start_loop_continue_elsewhere (1);
2312
2313         tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2314         expand_loop_continue_here ();
2315
2316         cond = tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2317         emit_line_note (input_filename, lineno);
2318         expand_exit_loop_if_false (0, condition_conversion (cond));
2319         expand_end_loop ();
2320
2321         clear_momentary ();
2322         finish_stmt ();
2323       }
2324       break;
2325
2326     case IF_STMT:
2327       {
2328         tree tmp;
2329         int cond_scope = (TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
2330
2331         lineno = TREE_COMPLEXITY (t);
2332         if (cond_scope)
2333           do_pushlevel ();
2334         tmp = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2335         emit_line_note (input_filename, lineno);
2336         expand_start_cond (condition_conversion (tmp), 0);
2337
2338         if (tmp = TREE_OPERAND (t, 1), tmp)
2339           tsubst_expr (tmp, args, nargs, in_decl);
2340
2341         if (tmp = TREE_OPERAND (t, 2), tmp)
2342           {
2343             expand_start_else ();
2344             tsubst_expr (tmp, args, nargs, in_decl);
2345           }
2346
2347         expand_end_cond ();
2348
2349         if (cond_scope)
2350           do_poplevel ();
2351
2352         finish_stmt ();
2353       }
2354       break;
2355
2356     case COMPOUND_STMT:
2357       {
2358         tree substmt = TREE_OPERAND (t, 0);
2359
2360         lineno = TREE_COMPLEXITY (t);
2361
2362         if (COMPOUND_STMT_NO_SCOPE (t) == 0)
2363           do_pushlevel ();
2364
2365         for (; substmt; substmt = TREE_CHAIN (substmt))
2366           tsubst_expr (substmt, args, nargs, in_decl);
2367
2368         if (COMPOUND_STMT_NO_SCOPE (t) == 0)
2369           do_poplevel ();
2370       }
2371       break;
2372
2373     case BREAK_STMT:
2374       lineno = TREE_COMPLEXITY (t);
2375       emit_line_note (input_filename, lineno);
2376       if (! expand_exit_something ())
2377         error ("break statement not within loop or switch");
2378       break;
2379
2380     case CONTINUE_STMT:
2381       lineno = TREE_COMPLEXITY (t);
2382       emit_line_note (input_filename, lineno);
2383       if (! expand_continue_loop (0))
2384         error ("continue statement not within a loop");
2385       break;
2386
2387     case SWITCH_STMT:
2388       {
2389         tree val, tmp;
2390         int cond_scope = (TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
2391
2392         lineno = TREE_COMPLEXITY (t);
2393         if (cond_scope)
2394           do_pushlevel ();
2395         val = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2396         emit_line_note (input_filename, lineno);
2397         c_expand_start_case (val);
2398         push_switch ();
2399
2400         if (tmp = TREE_OPERAND (t, 1), tmp)
2401           tsubst_expr (tmp, args, nargs, in_decl);
2402
2403         expand_end_case (val);
2404         pop_switch ();
2405
2406         if (cond_scope)
2407           do_poplevel ();
2408
2409         finish_stmt ();
2410       }
2411       break;
2412
2413     case CASE_LABEL:
2414       do_case (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl),
2415                tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl));
2416       break;
2417
2418     case LABEL_DECL:
2419       t = define_label (DECL_SOURCE_FILE (t), DECL_SOURCE_LINE (t),
2420                         DECL_NAME (t));
2421       if (t)
2422         expand_label (t);
2423       break;
2424
2425     case GOTO_STMT:
2426       lineno = TREE_COMPLEXITY (t);
2427       emit_line_note (input_filename, lineno);
2428       if (TREE_CODE (TREE_OPERAND (t, 0)) == IDENTIFIER_NODE)
2429         {
2430           tree decl = lookup_label (TREE_OPERAND (t, 0));
2431           TREE_USED (decl) = 1;
2432           expand_goto (decl);
2433         }
2434       else
2435         expand_computed_goto
2436           (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl));
2437       break;
2438
2439     case TRY_BLOCK:
2440       lineno = TREE_COMPLEXITY (t);
2441       emit_line_note (input_filename, lineno);
2442       expand_start_try_stmts ();
2443       tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2444       expand_start_all_catch ();
2445       {
2446         tree handler = TREE_OPERAND (t, 1);
2447         for (; handler; handler = TREE_CHAIN (handler))
2448           tsubst_expr (handler, args, nargs, in_decl);
2449       }
2450       expand_end_all_catch ();
2451       break;
2452
2453     case HANDLER:
2454       lineno = TREE_COMPLEXITY (t);
2455       do_pushlevel ();
2456       if (TREE_OPERAND (t, 0))
2457         {
2458           tree d = TREE_OPERAND (t, 0);
2459           expand_start_catch_block
2460             (tsubst (TREE_OPERAND (d, 1), args, nargs, in_decl),
2461              tsubst (TREE_OPERAND (d, 0), args, nargs, in_decl));
2462         }
2463       else
2464         expand_start_catch_block (NULL_TREE, NULL_TREE);
2465       tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2466       expand_end_catch_block ();
2467       do_poplevel ();
2468       break;
2469
2470     default:
2471       return build_expr_from_tree (tsubst_copy (t, args, nargs, in_decl));
2472     }
2473   return NULL_TREE;
2474 }
2475
2476 tree
2477 instantiate_template (tmpl, targ_ptr)
2478      tree tmpl, *targ_ptr;
2479 {
2480   tree fndecl;
2481   int i, len;
2482   struct obstack *old_fmp_obstack;
2483   extern struct obstack *function_maybepermanent_obstack;
2484
2485   push_obstacks (&permanent_obstack, &permanent_obstack);
2486   old_fmp_obstack = function_maybepermanent_obstack;
2487   function_maybepermanent_obstack = &permanent_obstack;
2488
2489   my_friendly_assert (TREE_CODE (tmpl) == TEMPLATE_DECL, 283);
2490   len = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (tmpl));
2491
2492   i = len;
2493   while (i--)
2494     {
2495       tree t = targ_ptr [i];
2496       if (TREE_CODE_CLASS (TREE_CODE (t)) == 't')
2497         {
2498           tree nt = target_type (t);
2499           if (IS_AGGR_TYPE (nt) && decl_function_context (TYPE_MAIN_DECL (nt)))
2500             {
2501               cp_error ("type `%T' composed from a local class is not a valid template-argument", t);
2502               cp_error ("  trying to instantiate `%D'", tmpl);
2503               fndecl = error_mark_node;
2504               goto out;
2505             }
2506         }
2507       targ_ptr[i] = copy_to_permanent (t);
2508     }
2509
2510   /* substitute template parameters */
2511   fndecl = tsubst (DECL_RESULT (tmpl), targ_ptr, len, tmpl);
2512
2513  out:
2514   function_maybepermanent_obstack = old_fmp_obstack;
2515   pop_obstacks ();
2516
2517   return fndecl;
2518 }
2519
2520 /* Push the name of the class template into the scope of the instantiation.  */
2521
2522 void
2523 overload_template_name (type)
2524      tree type;
2525 {
2526   tree id = DECL_NAME (CLASSTYPE_TI_TEMPLATE (type));
2527   tree decl;
2528
2529   if (IDENTIFIER_CLASS_VALUE (id)
2530       && TREE_TYPE (IDENTIFIER_CLASS_VALUE (id)) == type)
2531     return;
2532
2533   decl = build_decl (TYPE_DECL, id, type);
2534   SET_DECL_ARTIFICIAL (decl);
2535   pushdecl_class_level (decl);
2536 }
2537
2538 /* Type unification.
2539
2540    We have a function template signature with one or more references to
2541    template parameters, and a parameter list we wish to fit to this
2542    template.  If possible, produce a list of parameters for the template
2543    which will cause it to fit the supplied parameter list.
2544
2545    Return zero for success, 2 for an incomplete match that doesn't resolve
2546    all the types, and 1 for complete failure.  An error message will be
2547    printed only for an incomplete match.
2548
2549    TPARMS[NTPARMS] is an array of template parameter types;
2550    TARGS[NTPARMS] is the array of template parameter values.  PARMS is
2551    the function template's signature (using TEMPLATE_PARM_IDX nodes),
2552    and ARGS is the argument list we're trying to match against it.
2553
2554    If SUBR is 1, we're being called recursively (to unify the arguments of
2555    a function or method parameter of a function template), so don't zero
2556    out targs and don't fail on an incomplete match.
2557
2558    If STRICT is 1, the match must be exact (for casts of overloaded
2559    addresses, explicit instantiation, and more_specialized).  */
2560
2561 int
2562 type_unification (tparms, targs, parms, args, nsubsts, subr, strict)
2563      tree tparms, *targs, parms, args;
2564      int *nsubsts, subr, strict;
2565 {
2566   tree parm, arg;
2567   int i;
2568   int ntparms = TREE_VEC_LENGTH (tparms);
2569
2570   my_friendly_assert (TREE_CODE (tparms) == TREE_VEC, 289);
2571   my_friendly_assert (TREE_CODE (parms) == TREE_LIST, 290);
2572   /* ARGS could be NULL (via a call from parse.y to
2573      build_x_function_call).  */
2574   if (args)
2575     my_friendly_assert (TREE_CODE (args) == TREE_LIST, 291);
2576   my_friendly_assert (ntparms > 0, 292);
2577
2578   if (!subr)
2579     bzero ((char *) targs, sizeof (tree) * ntparms);
2580
2581   while (parms
2582          && parms != void_list_node
2583          && args
2584          && args != void_list_node)
2585     {
2586       parm = TREE_VALUE (parms);
2587       parms = TREE_CHAIN (parms);
2588       arg = TREE_VALUE (args);
2589       args = TREE_CHAIN (args);
2590
2591       if (arg == error_mark_node)
2592         return 1;
2593       if (arg == unknown_type_node)
2594         return 1;
2595
2596       if (! uses_template_parms (parm)
2597           && TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
2598         {
2599           if (can_convert_arg (parm, TREE_TYPE (arg), arg))
2600             continue;
2601           return 1;
2602         }
2603
2604 #if 0
2605       if (TREE_CODE (arg) == VAR_DECL)
2606         arg = TREE_TYPE (arg);
2607       else if (TREE_CODE_CLASS (TREE_CODE (arg)) == 'e')
2608         arg = TREE_TYPE (arg);
2609 #else
2610       if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
2611         {
2612           my_friendly_assert (TREE_TYPE (arg) != NULL_TREE, 293);
2613           if (TREE_CODE (arg) == TREE_LIST
2614               && TREE_TYPE (arg) == unknown_type_node
2615               && TREE_CODE (TREE_VALUE (arg)) == TEMPLATE_DECL)
2616             {
2617               int nsubsts, ntparms;
2618               tree *targs;
2619
2620               /* Have to back unify here */
2621               arg = TREE_VALUE (arg);
2622               nsubsts = 0;
2623               ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (arg));
2624               targs = (tree *) alloca (sizeof (tree) * ntparms);
2625               parm = tree_cons (NULL_TREE, parm, NULL_TREE);
2626               return type_unification (DECL_TEMPLATE_PARMS (arg), targs,
2627                                        TYPE_ARG_TYPES (TREE_TYPE (arg)),
2628                                        parm, &nsubsts, 0, strict);
2629             }
2630           arg = TREE_TYPE (arg);
2631         }
2632 #endif
2633       if (TREE_CODE (arg) == REFERENCE_TYPE)
2634         arg = TREE_TYPE (arg);
2635
2636       if (TREE_CODE (parm) != REFERENCE_TYPE)
2637         {
2638           if (TREE_CODE (arg) == FUNCTION_TYPE
2639               || TREE_CODE (arg) == METHOD_TYPE)
2640             arg = build_pointer_type (arg);
2641           else if (TREE_CODE (arg) == ARRAY_TYPE)
2642             arg = build_pointer_type (TREE_TYPE (arg));
2643           else
2644             arg = TYPE_MAIN_VARIANT (arg);
2645         }
2646
2647       switch (unify (tparms, targs, ntparms, parm, arg, nsubsts, strict))
2648         {
2649         case 0:
2650           break;
2651         case 1:
2652           return 1;
2653         }
2654     }
2655   /* Fail if we've reached the end of the parm list, and more args
2656      are present, and the parm list isn't variadic.  */
2657   if (args && args != void_list_node && parms == void_list_node)
2658     return 1;
2659   /* Fail if parms are left and they don't have default values.  */
2660   if (parms
2661       && parms != void_list_node
2662       && TREE_PURPOSE (parms) == NULL_TREE)
2663     return 1;
2664   if (!subr)
2665     for (i = 0; i < ntparms; i++)
2666       if (!targs[i])
2667         {
2668           error ("incomplete type unification");
2669           return 2;
2670         }
2671   return 0;
2672 }
2673
2674 /* Tail recursion is your friend.  */
2675
2676 static int
2677 unify (tparms, targs, ntparms, parm, arg, nsubsts, strict)
2678      tree tparms, *targs, parm, arg;
2679      int *nsubsts, ntparms, strict;
2680 {
2681   int idx;
2682
2683   /* I don't think this will do the right thing with respect to types.
2684      But the only case I've seen it in so far has been array bounds, where
2685      signedness is the only information lost, and I think that will be
2686      okay.  */
2687   while (TREE_CODE (parm) == NOP_EXPR)
2688     parm = TREE_OPERAND (parm, 0);
2689
2690   if (arg == error_mark_node)
2691     return 1;
2692   if (arg == unknown_type_node)
2693     return 1;
2694   if (arg == parm)
2695     return 0;
2696
2697   switch (TREE_CODE (parm))
2698     {
2699     case TEMPLATE_TYPE_PARM:
2700       (*nsubsts)++;
2701       idx = TEMPLATE_TYPE_IDX (parm);
2702       if (strict && (TYPE_READONLY (arg) < TYPE_READONLY (parm)
2703                      || TYPE_VOLATILE (arg) < TYPE_VOLATILE (parm)))
2704         return 1;
2705 #if 0
2706       /* Template type parameters cannot contain cv-quals; i.e.
2707          template <class T> void f (T& a, T& b) will not generate
2708          void f (const int& a, const int& b).  */
2709       if (TYPE_READONLY (arg) > TYPE_READONLY (parm)
2710           || TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm))
2711         return 1;
2712       arg = TYPE_MAIN_VARIANT (arg);
2713 #else
2714       {
2715         int constp = TYPE_READONLY (arg) > TYPE_READONLY (parm);
2716         int volatilep = TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm);
2717         arg = cp_build_type_variant (arg, constp, volatilep);
2718       }
2719 #endif
2720       /* Simple cases: Value already set, does match or doesn't.  */
2721       if (targs[idx] == arg)
2722         return 0;
2723       else if (targs[idx])
2724         return 1;
2725       /* Check for mixed types and values.  */
2726       if (TREE_CODE (TREE_VALUE (TREE_VEC_ELT (tparms, idx))) != TYPE_DECL)
2727         return 1;
2728       targs[idx] = arg;
2729       return 0;
2730     case TEMPLATE_CONST_PARM:
2731       (*nsubsts)++;
2732       idx = TEMPLATE_CONST_IDX (parm);
2733       if (targs[idx] == arg)
2734         return 0;
2735       else if (targs[idx])
2736         {
2737           tree t = targs[idx];
2738           if (TREE_CODE (t) == TREE_CODE (arg))
2739             switch (TREE_CODE (arg))
2740               {
2741               case INTEGER_CST:
2742                 if (tree_int_cst_equal (t, arg))
2743                   return 0;
2744                 break;
2745               case REAL_CST:
2746                 if (REAL_VALUES_EQUAL (TREE_REAL_CST (t), TREE_REAL_CST (arg)))
2747                   return 0;
2748                 break;
2749               /* STRING_CST values are not valid template const parms.  */
2750               default:
2751                 ;
2752               }
2753           my_friendly_abort (87);
2754           return 1;
2755         }
2756 /*      else if (typeof arg != tparms[idx])
2757         return 1;*/
2758
2759       targs[idx] = copy_to_permanent (arg);
2760       return 0;
2761
2762     case POINTER_TYPE:
2763       if (TREE_CODE (arg) == RECORD_TYPE && TYPE_PTRMEMFUNC_FLAG (arg))
2764         return unify (tparms, targs, ntparms, parm,
2765                       TYPE_PTRMEMFUNC_FN_TYPE (arg), nsubsts, strict);
2766
2767       if (TREE_CODE (arg) != POINTER_TYPE)
2768         return 1;
2769       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2770                     nsubsts, strict);
2771
2772     case REFERENCE_TYPE:
2773       if (TREE_CODE (arg) == REFERENCE_TYPE)
2774         arg = TREE_TYPE (arg);
2775       return unify (tparms, targs, ntparms, TREE_TYPE (parm), arg,
2776                     nsubsts, strict);
2777
2778     case ARRAY_TYPE:
2779       if (TREE_CODE (arg) != ARRAY_TYPE)
2780         return 1;
2781       if (unify (tparms, targs, ntparms, TYPE_DOMAIN (parm), TYPE_DOMAIN (arg),
2782                  nsubsts, strict) != 0)
2783         return 1;
2784       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2785                     nsubsts, strict);
2786
2787     case REAL_TYPE:
2788     case INTEGER_TYPE:
2789       if (TREE_CODE (arg) != TREE_CODE (parm))
2790         return 1;
2791
2792       if (TREE_CODE (parm) == INTEGER_TYPE)
2793         {
2794           if (TYPE_MIN_VALUE (parm) && TYPE_MIN_VALUE (arg)
2795               && unify (tparms, targs, ntparms, TYPE_MIN_VALUE (parm),
2796                         TYPE_MIN_VALUE (arg), nsubsts, strict))
2797             return 1;
2798           if (TYPE_MAX_VALUE (parm) && TYPE_MAX_VALUE (arg)
2799               && unify (tparms, targs, ntparms, TYPE_MAX_VALUE (parm),
2800                         TYPE_MAX_VALUE (arg), nsubsts, strict))
2801             return 1;
2802         }
2803       /* As far as unification is concerned, this wins.  Later checks
2804          will invalidate it if necessary.  */
2805       return 0;
2806
2807       /* Types INTEGER_CST and MINUS_EXPR can come from array bounds.  */
2808     case INTEGER_CST:
2809       if (TREE_CODE (arg) != INTEGER_CST)
2810         return 1;
2811       return !tree_int_cst_equal (parm, arg);
2812
2813     case MINUS_EXPR:
2814       {
2815         tree t1, t2;
2816         t1 = TREE_OPERAND (parm, 0);
2817         t2 = TREE_OPERAND (parm, 1);
2818         return unify (tparms, targs, ntparms, t1,
2819                       fold (build (PLUS_EXPR, integer_type_node, arg, t2)),
2820                       nsubsts, strict);
2821       }
2822
2823     case TREE_VEC:
2824       {
2825         int i;
2826         if (TREE_CODE (arg) != TREE_VEC)
2827           return 1;
2828         if (TREE_VEC_LENGTH (parm) != TREE_VEC_LENGTH (arg))
2829           return 1;
2830         for (i = TREE_VEC_LENGTH (parm) - 1; i >= 0; i--)
2831           if (unify (tparms, targs, ntparms,
2832                      TREE_VEC_ELT (parm, i), TREE_VEC_ELT (arg, i),
2833                      nsubsts, strict))
2834             return 1;
2835         return 0;
2836       }
2837
2838     case RECORD_TYPE:
2839       if (TYPE_PTRMEMFUNC_FLAG (parm))
2840         return unify (tparms, targs, ntparms, TYPE_PTRMEMFUNC_FN_TYPE (parm),
2841                       arg, nsubsts, strict);
2842
2843       /* Allow trivial conversions.  */
2844       if (TREE_CODE (arg) != RECORD_TYPE
2845           || TYPE_READONLY (parm) < TYPE_READONLY (arg)
2846           || TYPE_VOLATILE (parm) < TYPE_VOLATILE (arg))
2847         return 1;
2848
2849       if (CLASSTYPE_TEMPLATE_INFO (parm) && uses_template_parms (parm))
2850         {
2851           tree t = NULL_TREE;
2852           if (flag_ansi_overloading && ! strict)
2853             t = get_template_base (CLASSTYPE_TI_TEMPLATE (parm), arg);
2854           else if
2855             (CLASSTYPE_TEMPLATE_INFO (arg)
2856              && CLASSTYPE_TI_TEMPLATE (parm) == CLASSTYPE_TI_TEMPLATE (arg))
2857             t = arg;
2858           if (! t || t == error_mark_node)
2859             return 1;
2860
2861           return unify (tparms, targs, ntparms, CLASSTYPE_TI_ARGS (parm),
2862                         CLASSTYPE_TI_ARGS (t), nsubsts, strict);
2863         }
2864       else if (TYPE_MAIN_VARIANT (parm) != TYPE_MAIN_VARIANT (arg))
2865         return 1;
2866       return 0;
2867
2868     case METHOD_TYPE:
2869       if (TREE_CODE (arg) != METHOD_TYPE)
2870         return 1;
2871       goto check_args;
2872
2873     case FUNCTION_TYPE:
2874       if (TREE_CODE (arg) != FUNCTION_TYPE)
2875         return 1;
2876      check_args:
2877       if (unify (tparms, targs, ntparms, TREE_TYPE (parm),
2878                  TREE_TYPE (arg), nsubsts, strict))
2879         return 1;
2880       return type_unification (tparms, targs, TYPE_ARG_TYPES (parm),
2881                                TYPE_ARG_TYPES (arg), nsubsts, 1, strict);
2882
2883     case OFFSET_TYPE:
2884       if (TREE_CODE (arg) != OFFSET_TYPE)
2885         return 1;
2886       if (unify (tparms, targs, ntparms, TYPE_OFFSET_BASETYPE (parm),
2887                  TYPE_OFFSET_BASETYPE (arg), nsubsts, strict))
2888         return 1;
2889       return unify (tparms, targs, ntparms, TREE_TYPE (parm),
2890                     TREE_TYPE (arg), nsubsts, strict);
2891
2892     default:
2893       sorry ("use of `%s' in template type unification",
2894              tree_code_name [(int) TREE_CODE (parm)]);
2895       return 1;
2896     }
2897 }
2898 \f
2899 void
2900 mark_decl_instantiated (result, extern_p)
2901      tree result;
2902      int extern_p;
2903 {
2904   if (DECL_TEMPLATE_INSTANTIATION (result))
2905     SET_DECL_EXPLICIT_INSTANTIATION (result);
2906   TREE_PUBLIC (result) = 1;
2907
2908   if (! extern_p)
2909     {
2910       DECL_INTERFACE_KNOWN (result) = 1;
2911       DECL_NOT_REALLY_EXTERN (result) = 1;
2912     }
2913   else if (TREE_CODE (result) == FUNCTION_DECL)
2914     mark_inline_for_output (result);
2915 }
2916
2917 /* Given two function templates PAT1 and PAT2, return:
2918
2919    1 if PAT1 is more specialized than PAT2 as described in [temp.func.order].
2920    -1 if PAT2 is more specialized than PAT1.
2921    0 if neither is more specialized.  */
2922
2923 int
2924 more_specialized (pat1, pat2)
2925      tree pat1, pat2;
2926 {
2927   tree *targs;
2928   int winner = 0;
2929
2930   targs = get_bindings (pat1, pat2);
2931   if (targs)
2932     {
2933       free (targs);
2934       --winner;
2935     }
2936
2937   targs = get_bindings (pat2, pat1);
2938   if (targs)
2939     {
2940       free (targs);
2941       ++winner;
2942     }
2943
2944   return winner;
2945 }
2946
2947 /* Given two class template specialization list nodes PAT1 and PAT2, return:
2948
2949    1 if PAT1 is more specialized than PAT2 as described in [temp.class.order].
2950    -1 if PAT2 is more specialized than PAT1.
2951    0 if neither is more specialized.  */
2952
2953 int
2954 more_specialized_class (pat1, pat2)
2955      tree pat1, pat2;
2956 {
2957   tree targs;
2958   int winner = 0;
2959
2960   targs = get_class_bindings
2961     (TREE_VALUE (pat1), TREE_PURPOSE (pat1), TREE_PURPOSE (pat2));
2962   if (targs)
2963     --winner;
2964
2965   targs = get_class_bindings
2966     (TREE_VALUE (pat2), TREE_PURPOSE (pat2), TREE_PURPOSE (pat1));
2967   if (targs)
2968     ++winner;
2969
2970   return winner;
2971 }
2972
2973 /* Return the template arguments that will produce the function signature
2974    DECL from the function template FN.  */
2975
2976 tree *
2977 get_bindings (fn, decl)
2978      tree fn, decl;
2979 {
2980   int ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (fn));
2981   tree *targs = (tree *) malloc (sizeof (tree) * ntparms);
2982   int i, dummy = 0;
2983   i = type_unification (DECL_TEMPLATE_PARMS (fn), targs,
2984                         TYPE_ARG_TYPES (TREE_TYPE (fn)),
2985                         TYPE_ARG_TYPES (TREE_TYPE (decl)),
2986                         &dummy, 0, 1);
2987   if (i == 0)
2988     return targs;
2989   free (targs);
2990   return 0;
2991 }
2992
2993 tree
2994 get_class_bindings (tparms, parms, args)
2995      tree tparms, parms, args;
2996 {
2997   int i, dummy, ntparms = TREE_VEC_LENGTH (tparms);
2998   tree vec = make_temp_vec (ntparms);
2999
3000   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
3001     {
3002       switch (unify (tparms, &TREE_VEC_ELT (vec, 0), ntparms,
3003                      TREE_VEC_ELT (parms, i), TREE_VEC_ELT (args, i),
3004                      &dummy, 1))
3005         {
3006         case 0:
3007           break;
3008         case 1:
3009           return NULL_TREE;
3010         }
3011     }
3012
3013   for (i =  0; i < ntparms; ++i)
3014     if (! TREE_VEC_ELT (vec, i))
3015       return NULL_TREE;
3016
3017   return vec;
3018 }
3019
3020 /* Return the most specialized of the list of templates in FNS that can
3021    produce an instantiation matching DECL.  */
3022
3023 tree
3024 most_specialized (fns, decl)
3025      tree fns, decl;
3026 {
3027   tree fn, champ, *args, *p;
3028   int fate;
3029
3030   for (p = &fns; *p; )
3031     {
3032       args = get_bindings (TREE_VALUE (*p), decl);
3033       if (args)
3034         {
3035           free (args);
3036           p = &TREE_CHAIN (*p);
3037         }
3038       else
3039         *p = TREE_CHAIN (*p);
3040     }
3041
3042   if (! fns)
3043     return NULL_TREE;
3044
3045   fn = fns;
3046   champ = TREE_VALUE (fn);
3047   fn = TREE_CHAIN (fn);
3048   for (; fn; fn = TREE_CHAIN (fn))
3049     {
3050       fate = more_specialized (champ, TREE_VALUE (fn));
3051       if (fate == 1)
3052         ;
3053       else
3054         {
3055           if (fate == 0)
3056             {
3057               fn = TREE_CHAIN (fn);
3058               if (! fn)
3059                 return error_mark_node;
3060             }
3061           champ = TREE_VALUE (fn);
3062         }
3063     }
3064
3065   for (fn = fns; fn && TREE_VALUE (fn) != champ; fn = TREE_CHAIN (fn))
3066     {
3067       fate = more_specialized (champ, TREE_VALUE (fn));
3068       if (fate != 1)
3069         return error_mark_node;
3070     }
3071
3072   return champ;
3073 }
3074
3075 /* Return the most specialized of the class template specializations in
3076    SPECS that can produce an instantiation matching ARGS.  */
3077
3078 tree
3079 most_specialized_class (specs, mainargs)
3080      tree specs, mainargs;
3081 {
3082   tree list = NULL_TREE, t, args, champ;
3083   int fate;
3084
3085   for (t = specs; t; t = TREE_CHAIN (t))
3086     {
3087       args = get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), mainargs);
3088       if (args)
3089         {
3090           list = decl_tree_cons (TREE_PURPOSE (t), TREE_VALUE (t), list);
3091           TREE_TYPE (list) = TREE_TYPE (t);
3092         }
3093     }
3094
3095   if (! list)
3096     return NULL_TREE;
3097
3098   t = list;
3099   champ = t;
3100   t = TREE_CHAIN (t);
3101   for (; t; t = TREE_CHAIN (t))
3102     {
3103       fate = more_specialized_class (champ, t);
3104       if (fate == 1)
3105         ;
3106       else
3107         {
3108           if (fate == 0)
3109             {
3110               t = TREE_CHAIN (t);
3111               if (! t)
3112                 return error_mark_node;
3113             }
3114           champ = t;
3115         }
3116     }
3117
3118   for (t = list; t && t != champ; t = TREE_CHAIN (t))
3119     {
3120       fate = more_specialized (champ, t);
3121       if (fate != 1)
3122         return error_mark_node;
3123     }
3124
3125   return champ;
3126 }
3127
3128 /* called from the parser.  */
3129
3130 void
3131 do_function_instantiation (declspecs, declarator, storage)
3132      tree declspecs, declarator, storage;
3133 {
3134   tree decl = grokdeclarator (declarator, declspecs, NORMAL, 0, NULL_TREE);
3135   tree name;
3136   tree fn;
3137   tree result = NULL_TREE;
3138   int extern_p = 0;
3139
3140   if (! DECL_LANG_SPECIFIC (decl))
3141     {
3142       cp_error ("explicit instantiation of non-template `%#D'", decl);
3143       return;
3144     }
3145
3146   /* If we've already seen this template instance, use it.  */
3147   if (DECL_FUNCTION_MEMBER_P (decl))
3148     {
3149       if (DECL_TEMPLATE_INSTANTIATION (decl))
3150         result = decl;
3151       else if (name = DECL_ASSEMBLER_NAME (decl),
3152                fn = IDENTIFIER_GLOBAL_VALUE (name),
3153                fn && DECL_TEMPLATE_INSTANTIATION (fn))
3154         result = fn;
3155     }
3156   else if (name = DECL_NAME (decl), fn = IDENTIFIER_GLOBAL_VALUE (name), fn)
3157     {
3158       tree templates = NULL_TREE;
3159       for (fn = get_first_fn (fn); fn; fn = DECL_CHAIN (fn))
3160         if (decls_match (fn, decl)
3161             && DECL_DEFER_OUTPUT (fn))
3162           {
3163             result = fn;
3164             break;
3165           }
3166         else if (TREE_CODE (fn) == TEMPLATE_DECL)
3167           templates = decl_tree_cons (NULL_TREE, fn, templates);
3168
3169       if (! result)
3170         {
3171           tree *args;
3172           result = most_specialized (templates, decl);
3173           if (result == error_mark_node)
3174             {
3175               char *str = "candidates are:";
3176               cp_error ("ambiguous template instantiation for `%D' requested", decl);
3177               for (fn = templates; fn; fn = TREE_CHAIN (fn))
3178                 {
3179                   cp_error_at ("%s %+#D", str, TREE_VALUE (fn));
3180                   str = "               ";
3181                 }
3182               return;
3183             }
3184           else if (result)
3185             {
3186               args = get_bindings (result, decl);
3187               result = instantiate_template (result, args);
3188               free (args);
3189             }
3190         }
3191     }
3192   if (! result)
3193     {
3194       cp_error ("no matching template for `%D' found", decl);
3195       return;
3196     }
3197
3198   if (flag_external_templates)
3199     return;
3200
3201   if (storage == NULL_TREE)
3202     ;
3203   else if (storage == ridpointers[(int) RID_EXTERN])
3204     extern_p = 1;
3205   else
3206     cp_error ("storage class `%D' applied to template instantiation",
3207               storage);
3208
3209   mark_decl_instantiated (result, extern_p);
3210   repo_template_instantiated (result, extern_p);
3211   if (! extern_p)
3212     instantiate_decl (result);
3213 }
3214
3215 void
3216 mark_class_instantiated (t, extern_p)
3217      tree t;
3218      int extern_p;
3219 {
3220   SET_CLASSTYPE_EXPLICIT_INSTANTIATION (t);
3221   SET_CLASSTYPE_INTERFACE_KNOWN (t);
3222   CLASSTYPE_INTERFACE_ONLY (t) = extern_p;
3223   CLASSTYPE_VTABLE_NEEDS_WRITING (t) = ! extern_p;
3224   TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = extern_p;
3225   if (! extern_p)
3226     {
3227       CLASSTYPE_DEBUG_REQUESTED (t) = 1;
3228       rest_of_type_compilation (t, 1);
3229     }
3230 }
3231
3232 void
3233 do_type_instantiation (name, storage)
3234      tree name, storage;
3235 {
3236   tree t = TREE_TYPE (name);
3237   int extern_p = 0;
3238   int nomem_p = 0;
3239   int static_p = 0;
3240
3241   complete_type (t);
3242
3243   /* With -fexternal-templates, explicit instantiations are treated the same
3244      as implicit ones.  */
3245   if (flag_external_templates)
3246     return;
3247
3248   if (TYPE_SIZE (t) == NULL_TREE)
3249     {
3250       cp_error ("explicit instantiation of `%#T' before definition of template",
3251                 t);
3252       return;
3253     }
3254
3255   if (storage == NULL_TREE)
3256     /* OK */;
3257   else if (storage == ridpointers[(int) RID_INLINE])
3258     nomem_p = 1;
3259   else if (storage == ridpointers[(int) RID_EXTERN])
3260     extern_p = 1;
3261   else if (storage == ridpointers[(int) RID_STATIC])
3262     static_p = 1;
3263   else
3264     {
3265       cp_error ("storage class `%D' applied to template instantiation",
3266                 storage);
3267       extern_p = 0;
3268     }
3269
3270   /* We've already instantiated this.  */
3271   if (CLASSTYPE_EXPLICIT_INSTANTIATION (t) && ! CLASSTYPE_INTERFACE_ONLY (t)
3272       && extern_p)
3273     return;
3274
3275   if (! CLASSTYPE_TEMPLATE_SPECIALIZATION (t))
3276     {
3277       mark_class_instantiated (t, extern_p);
3278       repo_template_instantiated (t, extern_p);
3279     }
3280
3281   if (nomem_p)
3282     return;
3283
3284   {
3285     tree tmp;
3286
3287     if (! static_p)
3288       for (tmp = TYPE_METHODS (t); tmp; tmp = TREE_CHAIN (tmp))
3289         if (DECL_TEMPLATE_INSTANTIATION (tmp))
3290           {
3291             mark_decl_instantiated (tmp, extern_p);
3292             repo_template_instantiated (tmp, extern_p);
3293             if (! extern_p)
3294               instantiate_decl (tmp);
3295           }
3296
3297     for (tmp = TYPE_FIELDS (t); tmp; tmp = TREE_CHAIN (tmp))
3298       if (TREE_CODE (tmp) == VAR_DECL && DECL_TEMPLATE_INSTANTIATION (tmp))
3299         {
3300           mark_decl_instantiated (tmp, extern_p);
3301           repo_template_instantiated (tmp, extern_p);
3302           if (! extern_p)
3303             instantiate_decl (tmp);
3304         }
3305
3306     for (tmp = CLASSTYPE_TAGS (t); tmp; tmp = TREE_CHAIN (tmp))
3307       if (IS_AGGR_TYPE (TREE_VALUE (tmp)))
3308         do_type_instantiation (TYPE_MAIN_DECL (TREE_VALUE (tmp)), storage);
3309   }
3310 }
3311
3312 tree
3313 instantiate_decl (d)
3314      tree d;
3315 {
3316   tree ti = DECL_TEMPLATE_INFO (d);
3317   tree tmpl = TI_TEMPLATE (ti);
3318   tree args = TI_ARGS (ti);
3319   tree td;
3320   tree pattern = DECL_TEMPLATE_RESULT (tmpl);
3321   tree save_ti;
3322   int nested = in_function_p ();
3323   int d_defined;
3324   int pattern_defined;
3325   int line = lineno;
3326   char *file = input_filename;
3327
3328   if (TREE_CODE (d) == FUNCTION_DECL)
3329     {
3330       d_defined = (DECL_INITIAL (d) != NULL_TREE);
3331       pattern_defined = (DECL_INITIAL (pattern) != NULL_TREE);
3332     }
3333   else
3334     {
3335       d_defined = ! DECL_IN_AGGR_P (d);
3336       pattern_defined = ! DECL_IN_AGGR_P (pattern);
3337     }
3338
3339   if (d_defined)
3340     return d;
3341   else if (pattern_defined)
3342     {
3343       repo_template_used (d);
3344
3345       if (flag_external_templates && ! DECL_INTERFACE_KNOWN (d))
3346         {
3347           if (flag_alt_external_templates)
3348             {
3349               if (interface_unknown)
3350                 warn_if_unknown_interface (d);
3351             }
3352           else if (DECL_INTERFACE_KNOWN (pattern))
3353             {
3354               DECL_INTERFACE_KNOWN (d) = 1;
3355               DECL_NOT_REALLY_EXTERN (d) = ! DECL_EXTERNAL (pattern);
3356             }
3357           else
3358             warn_if_unknown_interface (pattern);
3359         }
3360
3361       if (at_eof)
3362         import_export_decl (d);
3363     }
3364
3365   /* We need to set up DECL_INITIAL regardless of pattern_defined if the
3366      variable is a static const initialized in the class body.  */
3367   if (TREE_CODE (d) == VAR_DECL
3368       && ! DECL_INITIAL (d) && DECL_INITIAL (pattern))
3369     {
3370       lineno = DECL_SOURCE_LINE (d);
3371       input_filename = DECL_SOURCE_FILE (d);
3372
3373       pushclass (DECL_CONTEXT (d), 2);
3374       DECL_INITIAL (d) = tsubst_expr
3375         (DECL_INITIAL (pattern), &TREE_VEC_ELT (args, 0),
3376          TREE_VEC_LENGTH (args), tmpl);
3377       popclass (1);
3378
3379       lineno = line;
3380       input_filename = file;
3381     }
3382
3383   if (! pattern_defined
3384       || (TREE_CODE (d) == FUNCTION_DECL && ! DECL_INLINE (d)
3385           && (! DECL_INTERFACE_KNOWN (d)
3386               || ! DECL_NOT_REALLY_EXTERN (d)))
3387       /* Kludge: if we compile a constructor in the middle of processing a
3388          toplevel declaration, we blow away the declspecs in
3389          temp_decl_obstack when we call permanent_allocation in
3390          finish_function.  So don't compile it yet.  */
3391       || (TREE_CODE (d) == FUNCTION_DECL && ! nested && ! at_eof))
3392     {
3393       add_pending_template (d);
3394       return d;
3395     }
3396
3397   if (! push_tinst_level (d))
3398     return d;
3399
3400   push_to_top_level ();
3401
3402   lineno = DECL_SOURCE_LINE (d);
3403   input_filename = DECL_SOURCE_FILE (d);
3404
3405   /* Trick tsubst into giving us a new decl in case the template changed.  */
3406   save_ti = DECL_TEMPLATE_INFO (pattern);
3407   DECL_TEMPLATE_INFO (pattern) = NULL_TREE;
3408   td = tsubst (pattern, &TREE_VEC_ELT (args, 0), TREE_VEC_LENGTH (args), tmpl);
3409   DECL_TEMPLATE_INFO (pattern) = save_ti;
3410
3411   /* And set up DECL_INITIAL, since tsubst doesn't.  */
3412   if (TREE_CODE (td) == VAR_DECL)
3413     {
3414       pushclass (DECL_CONTEXT (d), 2);
3415       DECL_INITIAL (td) = tsubst_expr
3416         (DECL_INITIAL (pattern), &TREE_VEC_ELT (args, 0),
3417          TREE_VEC_LENGTH (args), tmpl);
3418       popclass (1);
3419     }
3420
3421   /* Convince duplicate_decls to use the DECL_ARGUMENTS from the new decl.  */
3422   if (TREE_CODE (d) == FUNCTION_DECL)
3423     DECL_INITIAL (td) = error_mark_node;
3424   duplicate_decls (td, d);
3425   if (TREE_CODE (d) == FUNCTION_DECL)
3426     DECL_INITIAL (td) = 0;
3427
3428   if (TREE_CODE (d) == VAR_DECL)
3429     {
3430       DECL_IN_AGGR_P (d) = 0;
3431       if (DECL_INTERFACE_KNOWN (d))
3432         DECL_EXTERNAL (d) = ! DECL_NOT_REALLY_EXTERN (d);
3433       else
3434         {
3435           DECL_EXTERNAL (d) = 1;
3436           DECL_NOT_REALLY_EXTERN (d) = 1;
3437         }
3438       cp_finish_decl (d, DECL_INITIAL (d), NULL_TREE, 0, 0);
3439     }
3440   else if (TREE_CODE (d) == FUNCTION_DECL)
3441     {
3442       tree t = DECL_SAVED_TREE (pattern);
3443
3444       start_function (NULL_TREE, d, NULL_TREE, 1);
3445       store_parm_decls ();
3446
3447       if (t && TREE_CODE (t) == RETURN_INIT)
3448         {
3449           store_return_init
3450             (TREE_OPERAND (t, 0),
3451              tsubst_expr (TREE_OPERAND (t, 1), &TREE_VEC_ELT (args, 0),
3452                           TREE_VEC_LENGTH (args), tmpl));
3453           t = TREE_CHAIN (t);
3454         }
3455
3456       if (t && TREE_CODE (t) == CTOR_INITIALIZER)
3457         {
3458           current_member_init_list
3459             = tsubst_expr_values (TREE_OPERAND (t, 0), args);
3460           current_base_init_list
3461             = tsubst_expr_values (TREE_OPERAND (t, 1), args);
3462           t = TREE_CHAIN (t);
3463         }
3464
3465       setup_vtbl_ptr ();
3466       /* Always keep the BLOCK node associated with the outermost
3467          pair of curley braces of a function.  These are needed
3468          for correct operation of dwarfout.c.  */
3469       keep_next_level ();
3470
3471       my_friendly_assert (TREE_CODE (t) == COMPOUND_STMT, 42);
3472       tsubst_expr (t, &TREE_VEC_ELT (args, 0),
3473                    TREE_VEC_LENGTH (args), tmpl);
3474
3475       finish_function (lineno, 0, nested);
3476     }
3477
3478   lineno = line;
3479   input_filename = file;
3480
3481   pop_from_top_level ();
3482   pop_tinst_level ();
3483
3484   return d;
3485 }
3486
3487 tree
3488 tsubst_chain (t, argvec)
3489      tree t, argvec;
3490 {
3491   if (t)
3492     {
3493       tree first = tsubst (t, &TREE_VEC_ELT (argvec, 0),
3494                            TREE_VEC_LENGTH (argvec), NULL_TREE);
3495       tree last = first;
3496
3497       for (t = TREE_CHAIN (t); t; t = TREE_CHAIN (t))
3498         {
3499           tree x = tsubst (t, &TREE_VEC_ELT (argvec, 0),
3500                            TREE_VEC_LENGTH (argvec), NULL_TREE);
3501           TREE_CHAIN (last) = x;
3502           last = x;
3503         }
3504
3505       return first;
3506     }
3507   return NULL_TREE;
3508 }
3509
3510 tree
3511 tsubst_expr_values (t, argvec)
3512      tree t, argvec;
3513 {
3514   tree first = NULL_TREE;
3515   tree *p = &first;
3516
3517   for (; t; t = TREE_CHAIN (t))
3518     {
3519       tree pur = tsubst_copy (TREE_PURPOSE (t), &TREE_VEC_ELT (argvec, 0),
3520                               TREE_VEC_LENGTH (argvec), NULL_TREE);
3521       tree val = tsubst_expr (TREE_VALUE (t), &TREE_VEC_ELT (argvec, 0),
3522                               TREE_VEC_LENGTH (argvec), NULL_TREE);
3523       *p = build_tree_list (pur, val);
3524       p = &TREE_CHAIN (*p);
3525     }
3526   return first;
3527 }
3528
3529 tree last_tree;
3530
3531 void
3532 add_tree (t)
3533      tree t;
3534 {
3535   last_tree = TREE_CHAIN (last_tree) = t;
3536 }
3537
3538 /* D is an undefined function declaration in the presence of templates with
3539    the same name, listed in FNS.  If one of them can produce D as an
3540    instantiation, remember this so we can instantiate it at EOF if D has
3541    not been defined by that time.  */
3542
3543 void
3544 add_maybe_template (d, fns)
3545      tree d, fns;
3546 {
3547   tree t;
3548
3549   if (DECL_MAYBE_TEMPLATE (d))
3550     return;
3551
3552   t = most_specialized (fns, d);
3553   if (! t)
3554     return;
3555   if (t == error_mark_node)
3556     {
3557       cp_error ("ambiguous template instantiation for `%D'", d);
3558       return;
3559     }
3560
3561   *maybe_template_tail = perm_tree_cons (t, d, NULL_TREE);
3562   maybe_template_tail = &TREE_CHAIN (*maybe_template_tail);
3563   DECL_MAYBE_TEMPLATE (d) = 1;
3564 }