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   TYPE_HAS_CONSTRUCTOR (type) = TYPE_HAS_CONSTRUCTOR (pattern);
1129   TYPE_HAS_DESTRUCTOR (type) = TYPE_HAS_DESTRUCTOR (pattern);
1130   TYPE_HAS_ASSIGNMENT (type) = TYPE_HAS_ASSIGNMENT (pattern);
1131   TYPE_OVERLOADS_CALL_EXPR (type) = TYPE_OVERLOADS_CALL_EXPR (pattern);
1132   TYPE_OVERLOADS_ARRAY_REF (type) = TYPE_OVERLOADS_ARRAY_REF (pattern);
1133   TYPE_OVERLOADS_ARROW (type) = TYPE_OVERLOADS_ARROW (pattern);
1134   TYPE_GETS_NEW (type) = TYPE_GETS_NEW (pattern);
1135   TYPE_GETS_DELETE (type) = TYPE_GETS_DELETE (pattern);
1136   TYPE_VEC_DELETE_TAKES_SIZE (type) = TYPE_VEC_DELETE_TAKES_SIZE (pattern);
1137   TYPE_HAS_ASSIGN_REF (type) = TYPE_HAS_ASSIGN_REF (pattern);
1138   TYPE_HAS_CONST_ASSIGN_REF (type) = TYPE_HAS_CONST_ASSIGN_REF (pattern);
1139   TYPE_HAS_ABSTRACT_ASSIGN_REF (type) = TYPE_HAS_ABSTRACT_ASSIGN_REF (pattern);
1140   TYPE_HAS_INIT_REF (type) = TYPE_HAS_INIT_REF (pattern);
1141   TYPE_HAS_CONST_INIT_REF (type) = TYPE_HAS_CONST_INIT_REF (pattern);
1142   TYPE_GETS_INIT_AGGR (type) = TYPE_GETS_INIT_AGGR (pattern);
1143   TYPE_HAS_DEFAULT_CONSTRUCTOR (type) = TYPE_HAS_DEFAULT_CONSTRUCTOR (pattern);
1144   TYPE_HAS_CONVERSION (type) = TYPE_HAS_CONVERSION (pattern);
1145   TYPE_USES_COMPLEX_INHERITANCE (type)
1146     = TYPE_USES_COMPLEX_INHERITANCE (pattern);
1147   TYPE_USES_MULTIPLE_INHERITANCE (type)
1148     = TYPE_USES_MULTIPLE_INHERITANCE (pattern);
1149   TYPE_USES_VIRTUAL_BASECLASSES (type)
1150     = TYPE_USES_VIRTUAL_BASECLASSES (pattern);
1151   TYPE_PACKED (type) = TYPE_PACKED (pattern);
1152   TYPE_ALIGN (type) = TYPE_ALIGN (pattern);
1153
1154   {
1155     tree binfo = TYPE_BINFO (type);
1156     tree pbases = TYPE_BINFO_BASETYPES (pattern);
1157
1158     if (pbases)
1159       {
1160         tree bases;
1161         int i;
1162         int len = TREE_VEC_LENGTH (pbases);
1163         BINFO_BASETYPES (binfo) = bases = make_tree_vec (len);
1164         for (i = 0; i < len; ++i)
1165           {
1166             tree elt;
1167
1168             TREE_VEC_ELT (bases, i) = elt
1169               = tsubst (TREE_VEC_ELT (pbases, i), &TREE_VEC_ELT (args, 0),
1170                         TREE_VEC_LENGTH (args), NULL_TREE);
1171             BINFO_INHERITANCE_CHAIN (elt) = binfo;
1172
1173             if (! uses_template_parms (type) &&
1174                 TYPE_SIZE (complete_type (TREE_TYPE (elt))) == NULL_TREE)
1175               cp_error ("base class `%T' of `%T' has incomplete type",
1176                         TREE_TYPE (elt), type);
1177           }
1178       }
1179   }
1180
1181   CLASSTYPE_LOCAL_TYPEDECLS (type) = CLASSTYPE_LOCAL_TYPEDECLS (pattern);
1182
1183   field_chain = &TYPE_FIELDS (type);
1184
1185   for (t = CLASSTYPE_TAGS (pattern); t; t = TREE_CHAIN (t))
1186     {
1187       tree name = TREE_PURPOSE (t);
1188       tree tag = TREE_VALUE (t);
1189       tree newtag;
1190
1191       /* These will add themselves to CLASSTYPE_TAGS for the new type.  */
1192       if (TREE_CODE (tag) == ENUMERAL_TYPE)
1193         newtag = start_enum (name);
1194       else
1195         newtag = tsubst (tag, &TREE_VEC_ELT (args, 0),
1196                          TREE_VEC_LENGTH (args), NULL_TREE);
1197
1198       if (TREE_CODE (tag) == ENUMERAL_TYPE)
1199         {
1200           tree e, values = NULL_TREE, *last = &values;
1201
1202           for (e = TYPE_VALUES (tag); e; e = TREE_CHAIN (e))
1203             {
1204               tree elt = build_enumerator
1205                 (TREE_PURPOSE (e),
1206                  tsubst_expr (TREE_VALUE (e), &TREE_VEC_ELT (args, 0),
1207                               TREE_VEC_LENGTH (args), NULL_TREE));
1208               DECL_FIELD_CONTEXT (TREE_VALUE (elt)) = type;
1209               *last = elt;
1210               last = &TREE_CHAIN (elt);
1211             }
1212
1213           finish_enum (newtag, values);
1214
1215           *field_chain = grok_enum_decls (newtag, NULL_TREE);
1216           while (*field_chain)
1217             field_chain = &TREE_CHAIN (*field_chain);
1218         }
1219     }
1220
1221   /* Don't replace enum constants here.  */
1222   for (t = TYPE_FIELDS (pattern); t; t = TREE_CHAIN (t))
1223     if (TREE_CODE (t) != CONST_DECL)
1224       {
1225         tree r = tsubst (t, &TREE_VEC_ELT (args, 0),
1226                          TREE_VEC_LENGTH (args), NULL_TREE);
1227         if (TREE_CODE (r) == VAR_DECL)
1228           {
1229             if (! uses_template_parms (r))
1230               pending_statics = perm_tree_cons (NULL_TREE, r, pending_statics);
1231             /* Perhaps I should do more of grokfield here.  */
1232             start_decl_1 (r);
1233             DECL_IN_AGGR_P (r) = 1;
1234             DECL_EXTERNAL (r) = 1;
1235             cp_finish_decl (r, DECL_INITIAL (r), NULL_TREE, 0, 0);
1236           }
1237
1238         *field_chain = r;
1239         field_chain = &TREE_CHAIN (r);
1240       }
1241
1242   TYPE_METHODS (type) = tsubst_chain (TYPE_METHODS (pattern), args);
1243   for (t = TYPE_METHODS (type); t; t = TREE_CHAIN (t))
1244     {
1245       if (DECL_CONSTRUCTOR_P (t))
1246         grok_ctor_properties (type, t);
1247       else if (IDENTIFIER_OPNAME_P (DECL_NAME (t)))
1248         grok_op_properties (t, DECL_VIRTUAL_P (t), 0);
1249     }
1250
1251   DECL_FRIENDLIST (TYPE_MAIN_DECL (type))
1252     = tsubst (DECL_FRIENDLIST (TYPE_MAIN_DECL (pattern)),
1253               &TREE_VEC_ELT (args, 0), TREE_VEC_LENGTH (args), NULL_TREE);
1254
1255   {
1256     tree d = CLASSTYPE_FRIEND_CLASSES (type) =
1257       tsubst (CLASSTYPE_FRIEND_CLASSES (pattern), &TREE_VEC_ELT (args, 0),
1258               TREE_VEC_LENGTH (args), NULL_TREE);
1259
1260     /* This does injection for friend classes.  */
1261     for (; d; d = TREE_CHAIN (d))
1262       TREE_VALUE (d) = xref_tag_from_type (TREE_VALUE (d), NULL_TREE, 1);
1263
1264     d = tsubst (DECL_TEMPLATE_INJECT (template), &TREE_VEC_ELT (args, 0),
1265                      TREE_VEC_LENGTH (args), NULL_TREE);
1266
1267     for (; d; d = TREE_CHAIN (d))
1268       {
1269         tree t = TREE_VALUE (d);
1270
1271         if (TREE_CODE (t) == TYPE_DECL)
1272           /* Already injected.  */;
1273         else
1274           pushdecl (t);
1275       }
1276   }
1277
1278   if (! uses_template_parms (type))
1279     {
1280       tree tmp;
1281       for (tmp = TYPE_FIELDS (type); tmp; tmp = TREE_CHAIN (tmp))
1282         if (TREE_CODE (tmp) == FIELD_DECL)
1283           {
1284             TREE_TYPE (tmp) = complete_type (TREE_TYPE (tmp));
1285             require_complete_type (tmp);
1286           }
1287
1288       type = finish_struct_1 (type, 0);
1289       CLASSTYPE_GOT_SEMICOLON (type) = 1;
1290       if (at_eof && TYPE_BINFO_VTABLE (type) != NULL_TREE)
1291         finish_prevtable_vardecl (NULL, TYPE_BINFO_VTABLE (type));
1292
1293       repo_template_used (type);
1294     }
1295   else
1296     {
1297       TYPE_SIZE (type) = integer_zero_node;
1298       CLASSTYPE_METHOD_VEC (type)
1299         = finish_struct_methods (type, TYPE_METHODS (type), 1);
1300     }
1301
1302   TYPE_BEING_DEFINED (type) = 0;
1303   popclass (0);
1304
1305   pop_from_top_level ();
1306   pop_tinst_level ();
1307
1308   return type;
1309 }
1310
1311 static int
1312 list_eq (t1, t2)
1313      tree t1, t2;
1314 {
1315   if (t1 == NULL_TREE)
1316     return t2 == NULL_TREE;
1317   if (t2 == NULL_TREE)
1318     return 0;
1319   /* Don't care if one declares its arg const and the other doesn't -- the
1320      main variant of the arg type is all that matters.  */
1321   if (TYPE_MAIN_VARIANT (TREE_VALUE (t1))
1322       != TYPE_MAIN_VARIANT (TREE_VALUE (t2)))
1323     return 0;
1324   return list_eq (TREE_CHAIN (t1), TREE_CHAIN (t2));
1325 }
1326
1327 tree
1328 lookup_nested_type_by_name (ctype, name)
1329         tree ctype, name;
1330 {
1331   tree t;
1332
1333   complete_type (ctype);
1334
1335   for (t = CLASSTYPE_TAGS (ctype); t; t = TREE_CHAIN (t))
1336     {
1337       if (name == TREE_PURPOSE (t))
1338         return TREE_VALUE (t);
1339     }
1340   return NULL_TREE;
1341 }
1342
1343 tree
1344 tsubst (t, args, nargs, in_decl)
1345      tree t, *args;
1346      int nargs;
1347      tree in_decl;
1348 {
1349   tree type;
1350
1351   if (t == NULL_TREE || t == error_mark_node
1352       || t == integer_type_node
1353       || t == void_type_node
1354       || t == char_type_node)
1355     return t;
1356
1357   type = TREE_TYPE (t);
1358   if (type == unknown_type_node)
1359     my_friendly_abort (42);
1360   if (type && TREE_CODE (t) != FUNCTION_DECL)
1361     type = tsubst (type, args, nargs, in_decl);
1362
1363   switch (TREE_CODE (t))
1364     {
1365     case RECORD_TYPE:
1366       if (TYPE_PTRMEMFUNC_P (t))
1367         {
1368           tree r = build_ptrmemfunc_type
1369             (tsubst (TYPE_PTRMEMFUNC_FN_TYPE (t), args, nargs, in_decl));
1370           return cp_build_type_variant (r, TYPE_READONLY (t),
1371                                         TYPE_VOLATILE (t));
1372         }
1373
1374       /* else fall through */
1375     case UNION_TYPE:
1376       if (uses_template_parms (t))
1377         {
1378           tree argvec = tsubst (CLASSTYPE_TI_ARGS (t), args, nargs, in_decl);
1379           tree r = lookup_template_class (t, argvec, in_decl);
1380           return cp_build_type_variant (r, TYPE_READONLY (t),
1381                                         TYPE_VOLATILE (t));
1382         }
1383
1384       /* else fall through */
1385     case ERROR_MARK:
1386     case IDENTIFIER_NODE:
1387     case OP_IDENTIFIER:
1388     case VOID_TYPE:
1389     case REAL_TYPE:
1390     case BOOLEAN_TYPE:
1391     case INTEGER_CST:
1392     case REAL_CST:
1393     case STRING_CST:
1394       return t;
1395
1396     case ENUMERAL_TYPE:
1397       {
1398         tree ctx = tsubst (TYPE_CONTEXT (t), args, nargs, in_decl);
1399         if (ctx == NULL_TREE)
1400           return t;
1401         else
1402           return lookup_nested_type_by_name (ctx, TYPE_IDENTIFIER (t));
1403       }
1404
1405     case INTEGER_TYPE:
1406       if (t == integer_type_node)
1407         return t;
1408
1409       if (TREE_CODE (TYPE_MIN_VALUE (t)) == INTEGER_CST
1410           && TREE_CODE (TYPE_MAX_VALUE (t)) == INTEGER_CST)
1411         return t;
1412
1413       {
1414         tree max = tsubst_expr (TYPE_MAX_VALUE (t), args, nargs, in_decl);
1415         if (processing_template_decl)
1416           {
1417             tree itype = make_node (INTEGER_TYPE);
1418             TYPE_MIN_VALUE (itype) = size_zero_node;
1419             TYPE_MAX_VALUE (itype) = max;
1420             return itype;
1421           }
1422         return build_index_2_type (size_zero_node, max);
1423       }
1424
1425     case TEMPLATE_TYPE_PARM:
1426       {
1427         tree arg = args[TEMPLATE_TYPE_IDX (t)];
1428         return cp_build_type_variant
1429           (arg, TYPE_READONLY (arg) || TYPE_READONLY (t),
1430            TYPE_VOLATILE (arg) || TYPE_VOLATILE (t));
1431       }
1432
1433     case TEMPLATE_CONST_PARM:
1434       return args[TEMPLATE_CONST_IDX (t)];
1435
1436     case FUNCTION_DECL:
1437       {
1438         tree r = NULL_TREE;
1439         tree arg_types, ctx;
1440
1441         int member;
1442
1443         if (DECL_CONTEXT (t) != NULL_TREE
1444             && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't')
1445           {
1446             if (DECL_NAME (t) == constructor_name (DECL_CONTEXT (t)))
1447               member = 2;
1448             else
1449               member = 1;
1450             ctx = tsubst (DECL_CLASS_CONTEXT (t), args, nargs, t);
1451             type = tsubst (type, args, nargs, in_decl);
1452           }
1453         else
1454           {
1455             member = 0;
1456             ctx = NULL_TREE;
1457             type = tsubst (type, args, nargs, in_decl);
1458           }
1459
1460         if (type == TREE_TYPE (t)
1461             && (! member || ctx == DECL_CLASS_CONTEXT (t)))
1462           {
1463             t = copy_node (t);
1464             copy_lang_decl (t);
1465             return t;
1466           }
1467
1468         /* Do we already have this instantiation?  */
1469         if (DECL_TEMPLATE_INFO (t) != NULL_TREE)
1470           {
1471             tree tmpl = TREE_PURPOSE (DECL_TEMPLATE_INFO (t));
1472             tree decls = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1473
1474             for (; decls; decls = TREE_CHAIN (decls))
1475               if (TREE_TYPE (TREE_VALUE (decls)) == type
1476                   && DECL_CLASS_CONTEXT (TREE_VALUE (decls)) == ctx)
1477                 return TREE_VALUE (decls);
1478           }
1479
1480         /* We do NOT check for matching decls pushed separately at this
1481            point, as they may not represent instantiations of this
1482            template, and in any case are considered separate under the
1483            discrete model.  */
1484
1485         r = copy_node (t);
1486         copy_lang_decl (r);
1487         TREE_TYPE (r) = type;
1488
1489         DECL_CONTEXT (r)
1490           = tsubst (DECL_CONTEXT (t), args, nargs, t);
1491         DECL_CLASS_CONTEXT (r) = ctx;
1492
1493         if (member && !strncmp (OPERATOR_TYPENAME_FORMAT,
1494                                 IDENTIFIER_POINTER (DECL_NAME (r)),
1495                                 sizeof (OPERATOR_TYPENAME_FORMAT) - 1))
1496           {
1497             /* Type-conversion operator.  Reconstruct the name, in
1498                case it's the name of one of the template's parameters.  */
1499             DECL_NAME (r) = build_typename_overload (TREE_TYPE (type));
1500           }
1501
1502         arg_types = TYPE_VALUES (type);
1503
1504         if (member && TREE_CODE (type) == FUNCTION_TYPE)
1505           arg_types = hash_tree_chain
1506             (build_pointer_type (DECL_CONTEXT (r)), arg_types);
1507
1508         if (DESTRUCTOR_NAME_P (DECL_ASSEMBLER_NAME (t)))
1509           {
1510             char *buf, *dbuf = build_overload_name (ctx, 1, 1);
1511             int len = sizeof (DESTRUCTOR_DECL_PREFIX) - 1;
1512             buf = (char *) alloca (strlen (dbuf)
1513                                    + sizeof (DESTRUCTOR_DECL_PREFIX));
1514             bcopy (DESTRUCTOR_DECL_PREFIX, buf, len);
1515             buf[len] = '\0';
1516             strcat (buf, dbuf);
1517             DECL_ASSEMBLER_NAME (r) = get_identifier (buf);
1518           }
1519         else
1520           DECL_ASSEMBLER_NAME (r)
1521             = build_decl_overload (DECL_NAME (r), arg_types, member);
1522         DECL_RTL (r) = 0;
1523         make_decl_rtl (r, NULL_PTR, 1);
1524
1525         DECL_ARGUMENTS (r) = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
1526         DECL_MAIN_VARIANT (r) = r;
1527         DECL_RESULT (r) = NULL_TREE;
1528         DECL_INITIAL (r) = NULL_TREE;
1529
1530         TREE_STATIC (r) = 0;
1531         TREE_PUBLIC (r) = 1;
1532         DECL_EXTERNAL (r) = 1;
1533         DECL_INTERFACE_KNOWN (r) = 0;
1534         DECL_DEFER_OUTPUT (r) = 0;
1535         TREE_CHAIN (r) = NULL_TREE;
1536         DECL_CHAIN (r) = NULL_TREE;
1537
1538         if (IDENTIFIER_OPNAME_P (DECL_NAME (r)))
1539           grok_op_properties (r, DECL_VIRTUAL_P (r), DECL_FRIEND_P (r));
1540
1541         /* Look for matching decls for the moment.  */
1542         if (! member)
1543           {
1544             tree decls = lookup_name_nonclass (DECL_NAME (t));
1545             tree d = NULL_TREE;
1546
1547             if (decls == NULL_TREE)
1548               /* no match */;
1549             else if (is_overloaded_fn (decls))
1550               for (decls = get_first_fn (decls); decls;
1551                    decls = DECL_CHAIN (decls))
1552                 {
1553                   if (TREE_CODE (decls) == FUNCTION_DECL
1554                       && TREE_TYPE (decls) == type)
1555                     {
1556                       d = decls;
1557                       break;
1558                     }
1559                 }
1560
1561             if (d)
1562               {
1563                 int dcl_only = ! DECL_INITIAL (d);
1564                 if (dcl_only)
1565                   DECL_INITIAL (r) = error_mark_node;
1566                 duplicate_decls (r, d);
1567                 r = d;
1568                 if (dcl_only)
1569                   DECL_INITIAL (r) = 0;
1570               }
1571           }
1572
1573         if (DECL_TEMPLATE_INFO (t) != NULL_TREE)
1574           {
1575             tree tmpl = DECL_TI_TEMPLATE (t);
1576             tree *declsp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1577             tree argvec = tsubst (TREE_VALUE (DECL_TEMPLATE_INFO (t)),
1578                                   args, nargs, in_decl);
1579
1580             DECL_TEMPLATE_INFO (r) = perm_tree_cons (tmpl, argvec, NULL_TREE);
1581             *declsp = perm_tree_cons (argvec, r, *declsp);
1582
1583             /* If we have a preexisting version of this function, don't expand
1584                the template version, use the other instead.  */
1585             if (TREE_STATIC (r) || DECL_TEMPLATE_SPECIALIZATION (r))
1586               SET_DECL_TEMPLATE_SPECIALIZATION (r);
1587             else
1588               SET_DECL_IMPLICIT_INSTANTIATION (r);
1589
1590             DECL_TEMPLATE_INSTANTIATIONS (tmpl) =
1591               tree_cons (argvec, r, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1592           }
1593
1594         /* Like grokfndecl.  If we don't do this, pushdecl will mess up our
1595            TREE_CHAIN because it doesn't find a previous decl.  Sigh.  */
1596         if (member
1597             && IDENTIFIER_GLOBAL_VALUE (DECL_ASSEMBLER_NAME (r)) == NULL_TREE)
1598           IDENTIFIER_GLOBAL_VALUE (DECL_ASSEMBLER_NAME (r)) = r;
1599
1600         return r;
1601       }
1602
1603     case PARM_DECL:
1604       {
1605         tree r = copy_node (t);
1606         TREE_TYPE (r) = type;
1607         DECL_INITIAL (r) = TREE_TYPE (r);
1608         DECL_CONTEXT (r) = NULL_TREE;
1609 #ifdef PROMOTE_PROTOTYPES
1610         if ((TREE_CODE (type) == INTEGER_TYPE
1611              || TREE_CODE (type) == ENUMERAL_TYPE)
1612             && TYPE_PRECISION (type) < TYPE_PRECISION (integer_type_node))
1613           DECL_ARG_TYPE (r) = integer_type_node;
1614 #endif
1615         if (TREE_CHAIN (t))
1616           TREE_CHAIN (r) = tsubst (TREE_CHAIN (t), args, nargs, TREE_CHAIN (t));
1617         return r;
1618       }
1619
1620     case FIELD_DECL:
1621       {
1622         tree r = copy_node (t);
1623         TREE_TYPE (r) = type;
1624         copy_lang_decl (r);
1625 #if 0
1626         DECL_FIELD_CONTEXT (r) = tsubst (DECL_FIELD_CONTEXT (t), args, nargs, in_decl);
1627 #endif
1628         DECL_INITIAL (r) = tsubst_expr (DECL_INITIAL (t), args, nargs, in_decl);
1629         TREE_CHAIN (r) = NULL_TREE;
1630         return r;
1631       }
1632
1633     case USING_DECL:
1634       {
1635         tree r = copy_node (t);
1636         DECL_INITIAL (r)
1637           = tsubst_copy (DECL_INITIAL (t), args, nargs, in_decl);
1638         TREE_CHAIN (r) = NULL_TREE;
1639         return r;
1640       }
1641
1642     case VAR_DECL:
1643       {
1644         tree r;
1645         tree ctx = tsubst_copy (DECL_CONTEXT (t), args, nargs, in_decl);
1646
1647         /* Do we already have this instantiation?  */
1648         if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
1649           {
1650             tree tmpl = DECL_TI_TEMPLATE (t);
1651             tree decls = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1652
1653             for (; decls; decls = TREE_CHAIN (decls))
1654               if (DECL_CONTEXT (TREE_VALUE (decls)) == ctx)
1655                 return TREE_VALUE (decls);
1656           }
1657
1658         r = copy_node (t);
1659         TREE_TYPE (r) = type;
1660         DECL_CONTEXT (r) = ctx;
1661         if (TREE_STATIC (r))
1662           DECL_ASSEMBLER_NAME (r)
1663             = build_static_name (DECL_CONTEXT (r), DECL_NAME (r));
1664
1665         /* Don't try to expand the initializer until someone tries to use
1666            this variable; otherwise we run into circular dependencies.  */
1667         DECL_INITIAL (r) = NULL_TREE;
1668
1669         DECL_RTL (r) = 0;
1670         DECL_SIZE (r) = 0;
1671
1672         if (DECL_LANG_SPECIFIC (r))
1673           {
1674             copy_lang_decl (r);
1675             DECL_CLASS_CONTEXT (r) = DECL_CONTEXT (r);
1676           }
1677
1678         if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
1679           {
1680             tree tmpl = DECL_TI_TEMPLATE (t);
1681             tree *declsp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1682             tree argvec = tsubst (TREE_VALUE (DECL_TEMPLATE_INFO (t)),
1683                                   args, nargs, in_decl);
1684
1685             DECL_TEMPLATE_INFO (r) = perm_tree_cons (tmpl, argvec, NULL_TREE);
1686             *declsp = perm_tree_cons (argvec, r, *declsp);
1687             SET_DECL_IMPLICIT_INSTANTIATION (r);
1688           }
1689         TREE_CHAIN (r) = NULL_TREE;
1690         return r;
1691       }
1692
1693     case TYPE_DECL:
1694       if (t == TYPE_NAME (TREE_TYPE (t)))
1695         return TYPE_NAME (type);
1696
1697       {
1698         tree r = copy_node (t);
1699         TREE_TYPE (r) = type;
1700         DECL_CONTEXT (r) = current_class_type;
1701         TREE_CHAIN (r) = NULL_TREE;
1702         return r;
1703       }
1704
1705     case TREE_LIST:
1706       {
1707         tree purpose, value, chain, result;
1708         int via_public, via_virtual, via_protected;
1709
1710         if (t == void_list_node)
1711           return t;
1712
1713         via_public = TREE_VIA_PUBLIC (t);
1714         via_protected = TREE_VIA_PROTECTED (t);
1715         via_virtual = TREE_VIA_VIRTUAL (t);
1716
1717         purpose = TREE_PURPOSE (t);
1718         if (purpose)
1719           purpose = tsubst (purpose, args, nargs, in_decl);
1720         value = TREE_VALUE (t);
1721         if (value)
1722           value = tsubst (value, args, nargs, in_decl);
1723         chain = TREE_CHAIN (t);
1724         if (chain && chain != void_type_node)
1725           chain = tsubst (chain, args, nargs, in_decl);
1726         if (purpose == TREE_PURPOSE (t)
1727             && value == TREE_VALUE (t)
1728             && chain == TREE_CHAIN (t))
1729           return t;
1730         result = hash_tree_cons (via_public, via_virtual, via_protected,
1731                                  purpose, value, chain);
1732         TREE_PARMLIST (result) = TREE_PARMLIST (t);
1733         return result;
1734       }
1735     case TREE_VEC:
1736       if (type != NULL_TREE)
1737         {
1738           t = copy_node (t);
1739
1740           if (type == TREE_TYPE (t))
1741             return t;
1742
1743           TREE_TYPE (t) = complete_type (type);
1744           BINFO_VTABLE (t) = TYPE_BINFO_VTABLE (type);
1745           BINFO_VIRTUALS (t) = TYPE_BINFO_VIRTUALS (type);
1746           if (TYPE_BINFO_BASETYPES (type) != NULL_TREE)
1747             BINFO_BASETYPES (t) = copy_node (TYPE_BINFO_BASETYPES (type));
1748
1749           return t;
1750         }
1751       {
1752         int len = TREE_VEC_LENGTH (t), need_new = 0, i;
1753         tree *elts = (tree *) alloca (len * sizeof (tree));
1754
1755         bzero ((char *) elts, len * sizeof (tree));
1756
1757         for (i = 0; i < len; i++)
1758           {
1759             elts[i] = tsubst_expr (TREE_VEC_ELT (t, i), args, nargs, in_decl);
1760             if (elts[i] != TREE_VEC_ELT (t, i))
1761               need_new = 1;
1762           }
1763
1764         if (!need_new)
1765           return t;
1766
1767         t = make_tree_vec (len);
1768         for (i = 0; i < len; i++)
1769           TREE_VEC_ELT (t, i) = elts[i];
1770
1771         return t;
1772       }
1773     case POINTER_TYPE:
1774     case REFERENCE_TYPE:
1775       {
1776         tree r;
1777         enum tree_code code;
1778         if (type == TREE_TYPE (t))
1779           return t;
1780
1781         code = TREE_CODE (t);
1782         if (code == POINTER_TYPE)
1783           r = build_pointer_type (type);
1784         else
1785           r = build_reference_type (type);
1786         r = cp_build_type_variant (r, TYPE_READONLY (t), TYPE_VOLATILE (t));
1787         /* Will this ever be needed for TYPE_..._TO values?  */
1788         layout_type (r);
1789         return r;
1790       }
1791     case OFFSET_TYPE:
1792       return build_offset_type
1793         (tsubst (TYPE_OFFSET_BASETYPE (t), args, nargs, in_decl), type);
1794     case FUNCTION_TYPE:
1795     case METHOD_TYPE:
1796       {
1797         tree values = TYPE_ARG_TYPES (t);
1798         tree context = TYPE_CONTEXT (t);
1799         tree raises = TYPE_RAISES_EXCEPTIONS (t);
1800         tree fntype;
1801
1802         /* Don't bother recursing if we know it won't change anything.  */
1803         if (values != void_list_node)
1804           {
1805             /* This should probably be rewritten to use hash_tree_cons for
1806                the memory savings.  */
1807             tree first = NULL_TREE;
1808             tree last;
1809
1810             for (; values && values != void_list_node;
1811                  values = TREE_CHAIN (values))
1812               {
1813                 tree value = TYPE_MAIN_VARIANT (type_decays_to
1814                   (tsubst (TREE_VALUE (values), args, nargs, in_decl)));
1815                 tree purpose = tsubst_expr (TREE_PURPOSE (values),
1816                                             args, nargs, in_decl);
1817                 tree x = build_tree_list (purpose, value);
1818
1819                 if (first)
1820                   TREE_CHAIN (last) = x;
1821                 else
1822                   first = x;
1823                 last = x;
1824               }
1825
1826             if (values == void_list_node)
1827               TREE_CHAIN (last) = void_list_node;
1828
1829             values = first;
1830           }
1831         if (context)
1832           context = tsubst (context, args, nargs, in_decl);
1833         /* Could also optimize cases where return value and
1834            values have common elements (e.g., T min(const &T, const T&).  */
1835
1836         /* If the above parameters haven't changed, just return the type.  */
1837         if (type == TREE_TYPE (t)
1838             && values == TYPE_VALUES (t)
1839             && context == TYPE_CONTEXT (t))
1840           return t;
1841
1842         /* Construct a new type node and return it.  */
1843         if (TREE_CODE (t) == FUNCTION_TYPE
1844             && context == NULL_TREE)
1845           {
1846             fntype = build_function_type (type, values);
1847           }
1848         else if (context == NULL_TREE)
1849           {
1850             tree base = tsubst (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (t))),
1851                                 args, nargs, in_decl);
1852             fntype = build_cplus_method_type (base, type,
1853                                               TREE_CHAIN (values));
1854           }
1855         else
1856           {
1857             fntype = make_node (TREE_CODE (t));
1858             TREE_TYPE (fntype) = type;
1859             TYPE_CONTEXT (fntype) = context;
1860             TYPE_VALUES (fntype) = values;
1861             TYPE_SIZE (fntype) = TYPE_SIZE (t);
1862             TYPE_ALIGN (fntype) = TYPE_ALIGN (t);
1863             TYPE_MODE (fntype) = TYPE_MODE (t);
1864             if (TYPE_METHOD_BASETYPE (t))
1865               TYPE_METHOD_BASETYPE (fntype) = tsubst (TYPE_METHOD_BASETYPE (t),
1866                                                       args, nargs, in_decl);
1867             /* Need to generate hash value.  */
1868             my_friendly_abort (84);
1869           }
1870         fntype = build_type_variant (fntype,
1871                                      TYPE_READONLY (t),
1872                                      TYPE_VOLATILE (t));
1873         if (raises)
1874           {
1875             raises = tsubst (raises, args, nargs, in_decl);
1876             fntype = build_exception_variant (fntype, raises);
1877           }
1878         return fntype;
1879       }
1880     case ARRAY_TYPE:
1881       {
1882         tree domain = tsubst (TYPE_DOMAIN (t), args, nargs, in_decl);
1883         tree r;
1884         if (type == TREE_TYPE (t) && domain == TYPE_DOMAIN (t))
1885           return t;
1886         r = build_cplus_array_type (type, domain);
1887         return r;
1888       }
1889
1890     case PLUS_EXPR:
1891     case MINUS_EXPR:
1892       return fold (build (TREE_CODE (t), TREE_TYPE (t),
1893                           tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1894                           tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl)));
1895
1896     case NEGATE_EXPR:
1897     case NOP_EXPR:
1898       return fold (build1 (TREE_CODE (t), TREE_TYPE (t),
1899                            tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl)));
1900
1901     case TYPENAME_TYPE:
1902       {
1903         tree ctx = tsubst (TYPE_CONTEXT (t), args, nargs, in_decl);
1904         tree f = make_typename_type (ctx, TYPE_IDENTIFIER (t));
1905         return cp_build_type_variant
1906           (f, TYPE_READONLY (f) || TYPE_READONLY (t),
1907            TYPE_VOLATILE (f) || TYPE_VOLATILE (t));
1908       }
1909
1910     case INDIRECT_REF:
1911       return make_pointer_declarator
1912         (type, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl));
1913
1914     case ADDR_EXPR:
1915       return make_reference_declarator
1916         (type, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl));
1917
1918     case ARRAY_REF:
1919       return build_parse_node
1920         (ARRAY_REF, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1921          tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl));
1922
1923     case CALL_EXPR:
1924       return make_call_declarator
1925         (tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1926          tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl),
1927          TREE_OPERAND (t, 2),
1928          tsubst (TREE_TYPE (t), args, nargs, in_decl));
1929
1930     case SCOPE_REF:
1931       return build_parse_node
1932         (TREE_CODE (t), tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1933          tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl));
1934
1935     default:
1936       sorry ("use of `%s' in template",
1937              tree_code_name [(int) TREE_CODE (t)]);
1938       return error_mark_node;
1939     }
1940 }
1941
1942 void
1943 do_pushlevel ()
1944 {
1945   emit_line_note (input_filename, lineno);
1946   pushlevel (0);
1947   clear_last_expr ();
1948   push_momentary ();
1949   expand_start_bindings (0);
1950 }
1951
1952 tree
1953 do_poplevel ()
1954 {
1955   tree t;
1956
1957   expand_end_bindings (getdecls (), kept_level_p (), 1);
1958   t = poplevel (kept_level_p (), 1, 0);
1959   pop_momentary ();
1960   return t;
1961 }
1962
1963 tree
1964 tsubst_copy (t, args, nargs, in_decl)
1965      tree t, *args;
1966      int nargs;
1967      tree in_decl;
1968 {
1969   enum tree_code code;
1970
1971   if (t == NULL_TREE || t == error_mark_node)
1972     return t;
1973
1974   code = TREE_CODE (t);
1975
1976   switch (code)
1977     {
1978     case PARM_DECL:
1979       return do_identifier (DECL_NAME (t), 0);
1980
1981     case CONST_DECL:
1982     case FIELD_DECL:
1983       if (DECL_CONTEXT (t))
1984         {
1985           tree ctx = tsubst (DECL_CONTEXT (t), args, nargs, in_decl);
1986           if (ctx != DECL_CONTEXT (t))
1987             return lookup_field (ctx, DECL_NAME (t), 0, 0);
1988         }
1989       return t;
1990
1991     case VAR_DECL:
1992     case FUNCTION_DECL:
1993       if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
1994         t = tsubst (t, args, nargs, in_decl);
1995       mark_used (t);
1996       return t;
1997
1998 #if 0
1999     case IDENTIFIER_NODE:
2000       return do_identifier (t, 0);
2001 #endif
2002
2003     case CAST_EXPR:
2004     case REINTERPRET_CAST_EXPR:
2005     case CONST_CAST_EXPR:
2006     case STATIC_CAST_EXPR:
2007     case DYNAMIC_CAST_EXPR:
2008       return build1
2009         (code, tsubst (TREE_TYPE (t), args, nargs, in_decl),
2010          tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl));
2011
2012     case INDIRECT_REF:
2013     case PREDECREMENT_EXPR:
2014     case PREINCREMENT_EXPR:
2015     case POSTDECREMENT_EXPR:
2016     case POSTINCREMENT_EXPR:
2017     case NEGATE_EXPR:
2018     case TRUTH_NOT_EXPR:
2019     case ADDR_EXPR:
2020     case CONVERT_EXPR:      /* Unary + */
2021     case SIZEOF_EXPR:
2022     case ARROW_EXPR:
2023     case THROW_EXPR:
2024     case TYPEID_EXPR:
2025       return build1
2026         (code, NULL_TREE,
2027          tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl));
2028
2029     case PLUS_EXPR:
2030     case MINUS_EXPR:
2031     case MULT_EXPR:
2032     case TRUNC_DIV_EXPR:
2033     case CEIL_DIV_EXPR:
2034     case FLOOR_DIV_EXPR:
2035     case ROUND_DIV_EXPR:
2036     case EXACT_DIV_EXPR:
2037     case BIT_AND_EXPR:
2038     case BIT_ANDTC_EXPR:
2039     case BIT_IOR_EXPR:
2040     case BIT_XOR_EXPR:
2041     case TRUNC_MOD_EXPR:
2042     case FLOOR_MOD_EXPR:
2043     case TRUTH_ANDIF_EXPR:
2044     case TRUTH_ORIF_EXPR:
2045     case TRUTH_AND_EXPR:
2046     case TRUTH_OR_EXPR:
2047     case RSHIFT_EXPR:
2048     case LSHIFT_EXPR:
2049     case RROTATE_EXPR:
2050     case LROTATE_EXPR:
2051     case EQ_EXPR:
2052     case NE_EXPR:
2053     case MAX_EXPR:
2054     case MIN_EXPR:
2055     case LE_EXPR:
2056     case GE_EXPR:
2057     case LT_EXPR:
2058     case GT_EXPR:
2059     case COMPONENT_REF:
2060     case ARRAY_REF:
2061     case COMPOUND_EXPR:
2062     case SCOPE_REF:
2063     case DOTSTAR_EXPR:
2064     case MEMBER_REF:
2065       return build_nt
2066         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2067          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl));
2068
2069     case CALL_EXPR:
2070       {
2071         tree fn = TREE_OPERAND (t, 0);
2072         if (really_overloaded_fn (fn))
2073           fn = tsubst_copy (TREE_VALUE (fn), args, nargs, in_decl);
2074         else
2075           fn = tsubst_copy (fn, args, nargs, in_decl);
2076         return build_nt
2077           (code, fn, tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2078            NULL_TREE);
2079       }
2080
2081     case METHOD_CALL_EXPR:
2082       {
2083         tree name = TREE_OPERAND (t, 0);
2084         if (TREE_CODE (name) == BIT_NOT_EXPR)
2085           {
2086             name = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
2087             name = build1 (BIT_NOT_EXPR, NULL_TREE, TYPE_MAIN_VARIANT (name));
2088           }
2089         else if (TREE_CODE (name) == SCOPE_REF
2090                  && TREE_CODE (TREE_OPERAND (name, 1)) == BIT_NOT_EXPR)
2091           {
2092             tree base = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
2093             name = TREE_OPERAND (name, 1);
2094             name = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
2095             name = build1 (BIT_NOT_EXPR, NULL_TREE, TYPE_MAIN_VARIANT (name));
2096             name = build_nt (SCOPE_REF, base, name);
2097           }
2098         else
2099           name = tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl);
2100         return build_nt
2101           (code, name, tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2102            tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl),
2103            NULL_TREE);
2104       }
2105
2106     case COND_EXPR:
2107     case MODOP_EXPR:
2108       return 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
2113     case NEW_EXPR:
2114       {
2115         tree r = build_nt
2116         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2117          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
2118          tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl));
2119         NEW_EXPR_USE_GLOBAL (r) = NEW_EXPR_USE_GLOBAL (t);
2120         return r;
2121       }
2122
2123     case DELETE_EXPR:
2124       {
2125         tree r = build_nt
2126         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2127          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl));
2128         DELETE_EXPR_USE_GLOBAL (r) = DELETE_EXPR_USE_GLOBAL (t);
2129         DELETE_EXPR_USE_VEC (r) = DELETE_EXPR_USE_VEC (t);
2130         return r;
2131       }
2132
2133     case TREE_LIST:
2134       {
2135         tree purpose, value, chain;
2136
2137         if (t == void_list_node)
2138           return t;
2139
2140         purpose = TREE_PURPOSE (t);
2141         if (purpose)
2142           purpose = tsubst_copy (purpose, args, nargs, in_decl);
2143         value = TREE_VALUE (t);
2144         if (value)
2145           value = tsubst_copy (value, args, nargs, in_decl);
2146         chain = TREE_CHAIN (t);
2147         if (chain && chain != void_type_node)
2148           chain = tsubst_copy (chain, args, nargs, in_decl);
2149         if (purpose == TREE_PURPOSE (t)
2150             && value == TREE_VALUE (t)
2151             && chain == TREE_CHAIN (t))
2152           return t;
2153         return tree_cons (purpose, value, chain);
2154       }
2155
2156     case RECORD_TYPE:
2157     case UNION_TYPE:
2158     case ENUMERAL_TYPE:
2159     case INTEGER_TYPE:
2160     case TEMPLATE_TYPE_PARM:
2161     case TEMPLATE_CONST_PARM:
2162     case POINTER_TYPE:
2163     case REFERENCE_TYPE:
2164     case OFFSET_TYPE:
2165     case FUNCTION_TYPE:
2166     case METHOD_TYPE:
2167     case ARRAY_TYPE:
2168     case TYPENAME_TYPE:
2169       return tsubst (t, args, nargs, in_decl);
2170
2171     case IDENTIFIER_NODE:
2172       if (IDENTIFIER_TYPENAME_P (t))
2173         return build_typename_overload
2174           (tsubst (TREE_TYPE (t), args, nargs, in_decl));
2175       else
2176         return t;
2177
2178     case CONSTRUCTOR:
2179       return build
2180         (CONSTRUCTOR, tsubst (TREE_TYPE (t), args, nargs, in_decl), NULL_TREE,
2181          tsubst_copy (CONSTRUCTOR_ELTS (t), args, nargs, in_decl));
2182
2183     default:
2184       return t;
2185     }
2186 }
2187
2188 tree
2189 tsubst_expr (t, args, nargs, in_decl)
2190      tree t, *args;
2191      int nargs;
2192      tree in_decl;
2193 {
2194   if (t == NULL_TREE || t == error_mark_node)
2195     return t;
2196
2197   if (processing_template_decl)
2198     return tsubst_copy (t, args, nargs, in_decl);
2199
2200   switch (TREE_CODE (t))
2201     {
2202     case RETURN_STMT:
2203       lineno = TREE_COMPLEXITY (t);
2204       emit_line_note (input_filename, lineno);
2205       c_expand_return
2206         (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl));
2207       finish_stmt ();
2208       break;
2209
2210     case EXPR_STMT:
2211       lineno = TREE_COMPLEXITY (t);
2212       emit_line_note (input_filename, lineno);
2213       t = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2214       /* Do default conversion if safe and possibly important,
2215          in case within ({...}).  */
2216       if ((TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE && lvalue_p (t))
2217           || TREE_CODE (TREE_TYPE (t)) == FUNCTION_TYPE)
2218         t = default_conversion (t);
2219       cplus_expand_expr_stmt (t);
2220       clear_momentary ();
2221       finish_stmt ();
2222       break;
2223
2224     case DECL_STMT:
2225       {
2226         int i = suspend_momentary ();
2227         tree dcl, init;
2228
2229         lineno = TREE_COMPLEXITY (t);
2230         emit_line_note (input_filename, lineno);
2231         dcl = start_decl
2232           (tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
2233            tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl),
2234            TREE_OPERAND (t, 2) != 0);
2235         init = tsubst_expr (TREE_OPERAND (t, 2), args, nargs, in_decl);
2236         cp_finish_decl
2237           (dcl, init, NULL_TREE, 1, /*init ? LOOKUP_ONLYCONVERTING :*/ 0);
2238         resume_momentary (i);
2239         return dcl;
2240       }
2241
2242     case FOR_STMT:
2243       {
2244         tree tmp;
2245         int init_scope = (flag_new_for_scope > 0 && TREE_OPERAND (t, 0)
2246                           && TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
2247         int cond_scope = (TREE_OPERAND (t, 1)
2248                           && TREE_CODE (TREE_OPERAND (t, 1)) == DECL_STMT);
2249
2250         lineno = TREE_COMPLEXITY (t);
2251         emit_line_note (input_filename, lineno);
2252         if (init_scope)
2253           do_pushlevel ();
2254         for (tmp = TREE_OPERAND (t, 0); tmp; tmp = TREE_CHAIN (tmp))
2255           tsubst_expr (tmp, args, nargs, in_decl);
2256         emit_nop ();
2257         emit_line_note (input_filename, lineno);
2258         expand_start_loop_continue_elsewhere (1);
2259
2260         if (cond_scope)
2261           do_pushlevel ();
2262         tmp = tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2263         emit_line_note (input_filename, lineno);
2264         if (tmp)
2265           expand_exit_loop_if_false (0, condition_conversion (tmp));
2266
2267         if (! cond_scope)
2268           do_pushlevel ();
2269         tsubst_expr (TREE_OPERAND (t, 3), args, nargs, in_decl);
2270         do_poplevel ();
2271
2272         emit_line_note (input_filename, lineno);
2273         expand_loop_continue_here ();
2274         tmp = tsubst_expr (TREE_OPERAND (t, 2), args, nargs, in_decl);
2275         if (tmp)
2276           cplus_expand_expr_stmt (tmp);
2277
2278         expand_end_loop ();
2279         if (init_scope)
2280           do_poplevel ();
2281         finish_stmt ();
2282       }
2283       break;
2284
2285     case WHILE_STMT:
2286       {
2287         tree cond;
2288
2289         lineno = TREE_COMPLEXITY (t);
2290         emit_nop ();
2291         emit_line_note (input_filename, lineno);
2292         expand_start_loop (1);
2293
2294         cond = TREE_OPERAND (t, 0);
2295         if (TREE_CODE (cond) == DECL_STMT)
2296           do_pushlevel ();
2297         cond = tsubst_expr (cond, args, nargs, in_decl);
2298         emit_line_note (input_filename, lineno);
2299         expand_exit_loop_if_false (0, condition_conversion (cond));
2300
2301         if (TREE_CODE (TREE_OPERAND (t, 0)) != DECL_STMT)
2302           do_pushlevel ();
2303         tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2304         do_poplevel ();
2305
2306         expand_end_loop ();
2307         finish_stmt ();
2308       }
2309       break;
2310
2311     case DO_STMT:
2312       {
2313         tree cond;
2314
2315         lineno = TREE_COMPLEXITY (t);
2316         emit_nop ();
2317         emit_line_note (input_filename, lineno);
2318         expand_start_loop_continue_elsewhere (1);
2319
2320         tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2321         expand_loop_continue_here ();
2322
2323         cond = tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2324         emit_line_note (input_filename, lineno);
2325         expand_exit_loop_if_false (0, condition_conversion (cond));
2326         expand_end_loop ();
2327
2328         clear_momentary ();
2329         finish_stmt ();
2330       }
2331       break;
2332
2333     case IF_STMT:
2334       {
2335         tree tmp;
2336         int cond_scope = (TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
2337
2338         lineno = TREE_COMPLEXITY (t);
2339         if (cond_scope)
2340           do_pushlevel ();
2341         tmp = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2342         emit_line_note (input_filename, lineno);
2343         expand_start_cond (condition_conversion (tmp), 0);
2344
2345         if (tmp = TREE_OPERAND (t, 1), tmp)
2346           tsubst_expr (tmp, args, nargs, in_decl);
2347
2348         if (tmp = TREE_OPERAND (t, 2), tmp)
2349           {
2350             expand_start_else ();
2351             tsubst_expr (tmp, args, nargs, in_decl);
2352           }
2353
2354         expand_end_cond ();
2355
2356         if (cond_scope)
2357           do_poplevel ();
2358
2359         finish_stmt ();
2360       }
2361       break;
2362
2363     case COMPOUND_STMT:
2364       {
2365         tree substmt = TREE_OPERAND (t, 0);
2366
2367         lineno = TREE_COMPLEXITY (t);
2368
2369         if (COMPOUND_STMT_NO_SCOPE (t) == 0)
2370           do_pushlevel ();
2371
2372         for (; substmt; substmt = TREE_CHAIN (substmt))
2373           tsubst_expr (substmt, args, nargs, in_decl);
2374
2375         if (COMPOUND_STMT_NO_SCOPE (t) == 0)
2376           do_poplevel ();
2377       }
2378       break;
2379
2380     case BREAK_STMT:
2381       lineno = TREE_COMPLEXITY (t);
2382       emit_line_note (input_filename, lineno);
2383       if (! expand_exit_something ())
2384         error ("break statement not within loop or switch");
2385       break;
2386
2387     case CONTINUE_STMT:
2388       lineno = TREE_COMPLEXITY (t);
2389       emit_line_note (input_filename, lineno);
2390       if (! expand_continue_loop (0))
2391         error ("continue statement not within a loop");
2392       break;
2393
2394     case SWITCH_STMT:
2395       {
2396         tree val, tmp;
2397         int cond_scope = (TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
2398
2399         lineno = TREE_COMPLEXITY (t);
2400         if (cond_scope)
2401           do_pushlevel ();
2402         val = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2403         emit_line_note (input_filename, lineno);
2404         c_expand_start_case (val);
2405         push_switch ();
2406
2407         if (tmp = TREE_OPERAND (t, 1), tmp)
2408           tsubst_expr (tmp, args, nargs, in_decl);
2409
2410         expand_end_case (val);
2411         pop_switch ();
2412
2413         if (cond_scope)
2414           do_poplevel ();
2415
2416         finish_stmt ();
2417       }
2418       break;
2419
2420     case CASE_LABEL:
2421       do_case (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl),
2422                tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl));
2423       break;
2424
2425     case LABEL_DECL:
2426       t = define_label (DECL_SOURCE_FILE (t), DECL_SOURCE_LINE (t),
2427                         DECL_NAME (t));
2428       if (t)
2429         expand_label (t);
2430       break;
2431
2432     case GOTO_STMT:
2433       lineno = TREE_COMPLEXITY (t);
2434       emit_line_note (input_filename, lineno);
2435       if (TREE_CODE (TREE_OPERAND (t, 0)) == IDENTIFIER_NODE)
2436         {
2437           tree decl = lookup_label (TREE_OPERAND (t, 0));
2438           TREE_USED (decl) = 1;
2439           expand_goto (decl);
2440         }
2441       else
2442         expand_computed_goto
2443           (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl));
2444       break;
2445
2446     case TRY_BLOCK:
2447       lineno = TREE_COMPLEXITY (t);
2448       emit_line_note (input_filename, lineno);
2449       expand_start_try_stmts ();
2450       tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
2451       expand_start_all_catch ();
2452       {
2453         tree handler = TREE_OPERAND (t, 1);
2454         for (; handler; handler = TREE_CHAIN (handler))
2455           tsubst_expr (handler, args, nargs, in_decl);
2456       }
2457       expand_end_all_catch ();
2458       break;
2459
2460     case HANDLER:
2461       lineno = TREE_COMPLEXITY (t);
2462       do_pushlevel ();
2463       if (TREE_OPERAND (t, 0))
2464         {
2465           tree d = TREE_OPERAND (t, 0);
2466           expand_start_catch_block
2467             (tsubst (TREE_OPERAND (d, 1), args, nargs, in_decl),
2468              tsubst (TREE_OPERAND (d, 0), args, nargs, in_decl));
2469         }
2470       else
2471         expand_start_catch_block (NULL_TREE, NULL_TREE);
2472       tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
2473       expand_end_catch_block ();
2474       do_poplevel ();
2475       break;
2476
2477     default:
2478       return build_expr_from_tree (tsubst_copy (t, args, nargs, in_decl));
2479     }
2480   return NULL_TREE;
2481 }
2482
2483 tree
2484 instantiate_template (tmpl, targ_ptr)
2485      tree tmpl, *targ_ptr;
2486 {
2487   tree fndecl;
2488   int i, len;
2489   struct obstack *old_fmp_obstack;
2490   extern struct obstack *function_maybepermanent_obstack;
2491
2492   push_obstacks (&permanent_obstack, &permanent_obstack);
2493   old_fmp_obstack = function_maybepermanent_obstack;
2494   function_maybepermanent_obstack = &permanent_obstack;
2495
2496   my_friendly_assert (TREE_CODE (tmpl) == TEMPLATE_DECL, 283);
2497   len = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (tmpl));
2498
2499   i = len;
2500   while (i--)
2501     {
2502       tree t = targ_ptr [i];
2503       if (TREE_CODE_CLASS (TREE_CODE (t)) == 't')
2504         {
2505           tree nt = target_type (t);
2506           if (IS_AGGR_TYPE (nt) && decl_function_context (TYPE_MAIN_DECL (nt)))
2507             {
2508               cp_error ("type `%T' composed from a local class is not a valid template-argument", t);
2509               cp_error ("  trying to instantiate `%D'", tmpl);
2510               fndecl = error_mark_node;
2511               goto out;
2512             }
2513         }
2514       targ_ptr[i] = copy_to_permanent (t);
2515     }
2516
2517   /* substitute template parameters */
2518   fndecl = tsubst (DECL_RESULT (tmpl), targ_ptr, len, tmpl);
2519
2520  out:
2521   function_maybepermanent_obstack = old_fmp_obstack;
2522   pop_obstacks ();
2523
2524   return fndecl;
2525 }
2526
2527 /* Push the name of the class template into the scope of the instantiation.  */
2528
2529 void
2530 overload_template_name (type)
2531      tree type;
2532 {
2533   tree id = DECL_NAME (CLASSTYPE_TI_TEMPLATE (type));
2534   tree decl;
2535
2536   if (IDENTIFIER_CLASS_VALUE (id)
2537       && TREE_TYPE (IDENTIFIER_CLASS_VALUE (id)) == type)
2538     return;
2539
2540   decl = build_decl (TYPE_DECL, id, type);
2541   SET_DECL_ARTIFICIAL (decl);
2542   pushdecl_class_level (decl);
2543 }
2544
2545 /* Type unification.
2546
2547    We have a function template signature with one or more references to
2548    template parameters, and a parameter list we wish to fit to this
2549    template.  If possible, produce a list of parameters for the template
2550    which will cause it to fit the supplied parameter list.
2551
2552    Return zero for success, 2 for an incomplete match that doesn't resolve
2553    all the types, and 1 for complete failure.  An error message will be
2554    printed only for an incomplete match.
2555
2556    TPARMS[NTPARMS] is an array of template parameter types;
2557    TARGS[NTPARMS] is the array of template parameter values.  PARMS is
2558    the function template's signature (using TEMPLATE_PARM_IDX nodes),
2559    and ARGS is the argument list we're trying to match against it.
2560
2561    If SUBR is 1, we're being called recursively (to unify the arguments of
2562    a function or method parameter of a function template), so don't zero
2563    out targs and don't fail on an incomplete match.
2564
2565    If STRICT is 1, the match must be exact (for casts of overloaded
2566    addresses, explicit instantiation, and more_specialized).  */
2567
2568 int
2569 type_unification (tparms, targs, parms, args, nsubsts, subr, strict)
2570      tree tparms, *targs, parms, args;
2571      int *nsubsts, subr, strict;
2572 {
2573   tree parm, arg;
2574   int i;
2575   int ntparms = TREE_VEC_LENGTH (tparms);
2576
2577   my_friendly_assert (TREE_CODE (tparms) == TREE_VEC, 289);
2578   my_friendly_assert (TREE_CODE (parms) == TREE_LIST, 290);
2579   /* ARGS could be NULL (via a call from parse.y to
2580      build_x_function_call).  */
2581   if (args)
2582     my_friendly_assert (TREE_CODE (args) == TREE_LIST, 291);
2583   my_friendly_assert (ntparms > 0, 292);
2584
2585   if (!subr)
2586     bzero ((char *) targs, sizeof (tree) * ntparms);
2587
2588   while (parms
2589          && parms != void_list_node
2590          && args
2591          && args != void_list_node)
2592     {
2593       parm = TREE_VALUE (parms);
2594       parms = TREE_CHAIN (parms);
2595       arg = TREE_VALUE (args);
2596       args = TREE_CHAIN (args);
2597
2598       if (arg == error_mark_node)
2599         return 1;
2600       if (arg == unknown_type_node)
2601         return 1;
2602
2603       if (! uses_template_parms (parm)
2604           && TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
2605         {
2606           if (can_convert_arg (parm, TREE_TYPE (arg), arg))
2607             continue;
2608           return 1;
2609         }
2610
2611 #if 0
2612       if (TREE_CODE (arg) == VAR_DECL)
2613         arg = TREE_TYPE (arg);
2614       else if (TREE_CODE_CLASS (TREE_CODE (arg)) == 'e')
2615         arg = TREE_TYPE (arg);
2616 #else
2617       if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
2618         {
2619           my_friendly_assert (TREE_TYPE (arg) != NULL_TREE, 293);
2620           if (TREE_CODE (arg) == TREE_LIST
2621               && TREE_TYPE (arg) == unknown_type_node
2622               && TREE_CODE (TREE_VALUE (arg)) == TEMPLATE_DECL)
2623             {
2624               int nsubsts, ntparms;
2625               tree *targs;
2626
2627               /* Have to back unify here */
2628               arg = TREE_VALUE (arg);
2629               nsubsts = 0;
2630               ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (arg));
2631               targs = (tree *) alloca (sizeof (tree) * ntparms);
2632               parm = tree_cons (NULL_TREE, parm, NULL_TREE);
2633               return type_unification (DECL_TEMPLATE_PARMS (arg), targs,
2634                                        TYPE_ARG_TYPES (TREE_TYPE (arg)),
2635                                        parm, &nsubsts, 0, strict);
2636             }
2637           arg = TREE_TYPE (arg);
2638         }
2639 #endif
2640       if (TREE_CODE (arg) == REFERENCE_TYPE)
2641         arg = TREE_TYPE (arg);
2642
2643       if (TREE_CODE (parm) != REFERENCE_TYPE)
2644         {
2645           if (TREE_CODE (arg) == FUNCTION_TYPE
2646               || TREE_CODE (arg) == METHOD_TYPE)
2647             arg = build_pointer_type (arg);
2648           else if (TREE_CODE (arg) == ARRAY_TYPE)
2649             arg = build_pointer_type (TREE_TYPE (arg));
2650           else
2651             arg = TYPE_MAIN_VARIANT (arg);
2652         }
2653
2654       switch (unify (tparms, targs, ntparms, parm, arg, nsubsts, strict))
2655         {
2656         case 0:
2657           break;
2658         case 1:
2659           return 1;
2660         }
2661     }
2662   /* Fail if we've reached the end of the parm list, and more args
2663      are present, and the parm list isn't variadic.  */
2664   if (args && args != void_list_node && parms == void_list_node)
2665     return 1;
2666   /* Fail if parms are left and they don't have default values.  */
2667   if (parms
2668       && parms != void_list_node
2669       && TREE_PURPOSE (parms) == NULL_TREE)
2670     return 1;
2671   if (!subr)
2672     for (i = 0; i < ntparms; i++)
2673       if (!targs[i])
2674         {
2675           error ("incomplete type unification");
2676           return 2;
2677         }
2678   return 0;
2679 }
2680
2681 /* Tail recursion is your friend.  */
2682
2683 static int
2684 unify (tparms, targs, ntparms, parm, arg, nsubsts, strict)
2685      tree tparms, *targs, parm, arg;
2686      int *nsubsts, ntparms, strict;
2687 {
2688   int idx;
2689
2690   /* I don't think this will do the right thing with respect to types.
2691      But the only case I've seen it in so far has been array bounds, where
2692      signedness is the only information lost, and I think that will be
2693      okay.  */
2694   while (TREE_CODE (parm) == NOP_EXPR)
2695     parm = TREE_OPERAND (parm, 0);
2696
2697   if (arg == error_mark_node)
2698     return 1;
2699   if (arg == unknown_type_node)
2700     return 1;
2701   if (arg == parm)
2702     return 0;
2703
2704   switch (TREE_CODE (parm))
2705     {
2706     case TEMPLATE_TYPE_PARM:
2707       (*nsubsts)++;
2708       idx = TEMPLATE_TYPE_IDX (parm);
2709       if (strict && (TYPE_READONLY (arg) < TYPE_READONLY (parm)
2710                      || TYPE_VOLATILE (arg) < TYPE_VOLATILE (parm)))
2711         return 1;
2712 #if 0
2713       /* Template type parameters cannot contain cv-quals; i.e.
2714          template <class T> void f (T& a, T& b) will not generate
2715          void f (const int& a, const int& b).  */
2716       if (TYPE_READONLY (arg) > TYPE_READONLY (parm)
2717           || TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm))
2718         return 1;
2719       arg = TYPE_MAIN_VARIANT (arg);
2720 #else
2721       {
2722         int constp = TYPE_READONLY (arg) > TYPE_READONLY (parm);
2723         int volatilep = TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm);
2724         arg = cp_build_type_variant (arg, constp, volatilep);
2725       }
2726 #endif
2727       /* Simple cases: Value already set, does match or doesn't.  */
2728       if (targs[idx] == arg)
2729         return 0;
2730       else if (targs[idx])
2731         return 1;
2732       /* Check for mixed types and values.  */
2733       if (TREE_CODE (TREE_VALUE (TREE_VEC_ELT (tparms, idx))) != TYPE_DECL)
2734         return 1;
2735       targs[idx] = arg;
2736       return 0;
2737     case TEMPLATE_CONST_PARM:
2738       (*nsubsts)++;
2739       idx = TEMPLATE_CONST_IDX (parm);
2740       if (targs[idx] == arg)
2741         return 0;
2742       else if (targs[idx])
2743         {
2744           tree t = targs[idx];
2745           if (TREE_CODE (t) == TREE_CODE (arg))
2746             switch (TREE_CODE (arg))
2747               {
2748               case INTEGER_CST:
2749                 if (tree_int_cst_equal (t, arg))
2750                   return 0;
2751                 break;
2752               case REAL_CST:
2753                 if (REAL_VALUES_EQUAL (TREE_REAL_CST (t), TREE_REAL_CST (arg)))
2754                   return 0;
2755                 break;
2756               /* STRING_CST values are not valid template const parms.  */
2757               default:
2758                 ;
2759               }
2760           my_friendly_abort (87);
2761           return 1;
2762         }
2763 /*      else if (typeof arg != tparms[idx])
2764         return 1;*/
2765
2766       targs[idx] = copy_to_permanent (arg);
2767       return 0;
2768
2769     case POINTER_TYPE:
2770       if (TREE_CODE (arg) == RECORD_TYPE && TYPE_PTRMEMFUNC_FLAG (arg))
2771         return unify (tparms, targs, ntparms, parm,
2772                       TYPE_PTRMEMFUNC_FN_TYPE (arg), nsubsts, strict);
2773
2774       if (TREE_CODE (arg) != POINTER_TYPE)
2775         return 1;
2776       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2777                     nsubsts, strict);
2778
2779     case REFERENCE_TYPE:
2780       if (TREE_CODE (arg) == REFERENCE_TYPE)
2781         arg = TREE_TYPE (arg);
2782       return unify (tparms, targs, ntparms, TREE_TYPE (parm), arg,
2783                     nsubsts, strict);
2784
2785     case ARRAY_TYPE:
2786       if (TREE_CODE (arg) != ARRAY_TYPE)
2787         return 1;
2788       if (unify (tparms, targs, ntparms, TYPE_DOMAIN (parm), TYPE_DOMAIN (arg),
2789                  nsubsts, strict) != 0)
2790         return 1;
2791       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2792                     nsubsts, strict);
2793
2794     case REAL_TYPE:
2795     case INTEGER_TYPE:
2796       if (TREE_CODE (arg) != TREE_CODE (parm))
2797         return 1;
2798
2799       if (TREE_CODE (parm) == INTEGER_TYPE)
2800         {
2801           if (TYPE_MIN_VALUE (parm) && TYPE_MIN_VALUE (arg)
2802               && unify (tparms, targs, ntparms, TYPE_MIN_VALUE (parm),
2803                         TYPE_MIN_VALUE (arg), nsubsts, strict))
2804             return 1;
2805           if (TYPE_MAX_VALUE (parm) && TYPE_MAX_VALUE (arg)
2806               && unify (tparms, targs, ntparms, TYPE_MAX_VALUE (parm),
2807                         TYPE_MAX_VALUE (arg), nsubsts, strict))
2808             return 1;
2809         }
2810       /* As far as unification is concerned, this wins.  Later checks
2811          will invalidate it if necessary.  */
2812       return 0;
2813
2814       /* Types INTEGER_CST and MINUS_EXPR can come from array bounds.  */
2815     case INTEGER_CST:
2816       if (TREE_CODE (arg) != INTEGER_CST)
2817         return 1;
2818       return !tree_int_cst_equal (parm, arg);
2819
2820     case MINUS_EXPR:
2821       {
2822         tree t1, t2;
2823         t1 = TREE_OPERAND (parm, 0);
2824         t2 = TREE_OPERAND (parm, 1);
2825         return unify (tparms, targs, ntparms, t1,
2826                       fold (build (PLUS_EXPR, integer_type_node, arg, t2)),
2827                       nsubsts, strict);
2828       }
2829
2830     case TREE_VEC:
2831       {
2832         int i;
2833         if (TREE_CODE (arg) != TREE_VEC)
2834           return 1;
2835         if (TREE_VEC_LENGTH (parm) != TREE_VEC_LENGTH (arg))
2836           return 1;
2837         for (i = TREE_VEC_LENGTH (parm) - 1; i >= 0; i--)
2838           if (unify (tparms, targs, ntparms,
2839                      TREE_VEC_ELT (parm, i), TREE_VEC_ELT (arg, i),
2840                      nsubsts, strict))
2841             return 1;
2842         return 0;
2843       }
2844
2845     case RECORD_TYPE:
2846       if (TYPE_PTRMEMFUNC_FLAG (parm))
2847         return unify (tparms, targs, ntparms, TYPE_PTRMEMFUNC_FN_TYPE (parm),
2848                       arg, nsubsts, strict);
2849
2850       /* Allow trivial conversions.  */
2851       if (TREE_CODE (arg) != RECORD_TYPE
2852           || TYPE_READONLY (parm) < TYPE_READONLY (arg)
2853           || TYPE_VOLATILE (parm) < TYPE_VOLATILE (arg))
2854         return 1;
2855
2856       if (CLASSTYPE_TEMPLATE_INFO (parm) && uses_template_parms (parm))
2857         {
2858           tree t = NULL_TREE;
2859           if (flag_ansi_overloading && ! strict)
2860             t = get_template_base (CLASSTYPE_TI_TEMPLATE (parm), arg);
2861           else if
2862             (CLASSTYPE_TEMPLATE_INFO (arg)
2863              && CLASSTYPE_TI_TEMPLATE (parm) == CLASSTYPE_TI_TEMPLATE (arg))
2864             t = arg;
2865           if (! t || t == error_mark_node)
2866             return 1;
2867
2868           return unify (tparms, targs, ntparms, CLASSTYPE_TI_ARGS (parm),
2869                         CLASSTYPE_TI_ARGS (t), nsubsts, strict);
2870         }
2871       else if (TYPE_MAIN_VARIANT (parm) != TYPE_MAIN_VARIANT (arg))
2872         return 1;
2873       return 0;
2874
2875     case METHOD_TYPE:
2876       if (TREE_CODE (arg) != METHOD_TYPE)
2877         return 1;
2878       goto check_args;
2879
2880     case FUNCTION_TYPE:
2881       if (TREE_CODE (arg) != FUNCTION_TYPE)
2882         return 1;
2883      check_args:
2884       if (unify (tparms, targs, ntparms, TREE_TYPE (parm),
2885                  TREE_TYPE (arg), nsubsts, strict))
2886         return 1;
2887       return type_unification (tparms, targs, TYPE_ARG_TYPES (parm),
2888                                TYPE_ARG_TYPES (arg), nsubsts, 1, strict);
2889
2890     case OFFSET_TYPE:
2891       if (TREE_CODE (arg) != OFFSET_TYPE)
2892         return 1;
2893       if (unify (tparms, targs, ntparms, TYPE_OFFSET_BASETYPE (parm),
2894                  TYPE_OFFSET_BASETYPE (arg), nsubsts, strict))
2895         return 1;
2896       return unify (tparms, targs, ntparms, TREE_TYPE (parm),
2897                     TREE_TYPE (arg), nsubsts, strict);
2898
2899     default:
2900       sorry ("use of `%s' in template type unification",
2901              tree_code_name [(int) TREE_CODE (parm)]);
2902       return 1;
2903     }
2904 }
2905 \f
2906 void
2907 mark_decl_instantiated (result, extern_p)
2908      tree result;
2909      int extern_p;
2910 {
2911   if (DECL_TEMPLATE_INSTANTIATION (result))
2912     SET_DECL_EXPLICIT_INSTANTIATION (result);
2913   TREE_PUBLIC (result) = 1;
2914
2915   if (! extern_p)
2916     {
2917       DECL_INTERFACE_KNOWN (result) = 1;
2918       DECL_NOT_REALLY_EXTERN (result) = 1;
2919     }
2920   else if (TREE_CODE (result) == FUNCTION_DECL)
2921     mark_inline_for_output (result);
2922 }
2923
2924 /* Given two function templates PAT1 and PAT2, return:
2925
2926    1 if PAT1 is more specialized than PAT2 as described in [temp.func.order].
2927    -1 if PAT2 is more specialized than PAT1.
2928    0 if neither is more specialized.  */
2929
2930 int
2931 more_specialized (pat1, pat2)
2932      tree pat1, pat2;
2933 {
2934   tree *targs;
2935   int winner = 0;
2936
2937   targs = get_bindings (pat1, pat2);
2938   if (targs)
2939     {
2940       free (targs);
2941       --winner;
2942     }
2943
2944   targs = get_bindings (pat2, pat1);
2945   if (targs)
2946     {
2947       free (targs);
2948       ++winner;
2949     }
2950
2951   return winner;
2952 }
2953
2954 /* Given two class template specialization list nodes PAT1 and PAT2, return:
2955
2956    1 if PAT1 is more specialized than PAT2 as described in [temp.class.order].
2957    -1 if PAT2 is more specialized than PAT1.
2958    0 if neither is more specialized.  */
2959
2960 int
2961 more_specialized_class (pat1, pat2)
2962      tree pat1, pat2;
2963 {
2964   tree targs;
2965   int winner = 0;
2966
2967   targs = get_class_bindings
2968     (TREE_VALUE (pat1), TREE_PURPOSE (pat1), TREE_PURPOSE (pat2));
2969   if (targs)
2970     --winner;
2971
2972   targs = get_class_bindings
2973     (TREE_VALUE (pat2), TREE_PURPOSE (pat2), TREE_PURPOSE (pat1));
2974   if (targs)
2975     ++winner;
2976
2977   return winner;
2978 }
2979
2980 /* Return the template arguments that will produce the function signature
2981    DECL from the function template FN.  */
2982
2983 tree *
2984 get_bindings (fn, decl)
2985      tree fn, decl;
2986 {
2987   int ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (fn));
2988   tree *targs = (tree *) malloc (sizeof (tree) * ntparms);
2989   int i, dummy = 0;
2990   i = type_unification (DECL_TEMPLATE_PARMS (fn), targs,
2991                         TYPE_ARG_TYPES (TREE_TYPE (fn)),
2992                         TYPE_ARG_TYPES (TREE_TYPE (decl)),
2993                         &dummy, 0, 1);
2994   if (i == 0)
2995     return targs;
2996   free (targs);
2997   return 0;
2998 }
2999
3000 tree
3001 get_class_bindings (tparms, parms, args)
3002      tree tparms, parms, args;
3003 {
3004   int i, dummy, ntparms = TREE_VEC_LENGTH (tparms);
3005   tree vec = make_temp_vec (ntparms);
3006
3007   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
3008     {
3009       switch (unify (tparms, &TREE_VEC_ELT (vec, 0), ntparms,
3010                      TREE_VEC_ELT (parms, i), TREE_VEC_ELT (args, i),
3011                      &dummy, 1))
3012         {
3013         case 0:
3014           break;
3015         case 1:
3016           return NULL_TREE;
3017         }
3018     }
3019
3020   for (i =  0; i < ntparms; ++i)
3021     if (! TREE_VEC_ELT (vec, i))
3022       return NULL_TREE;
3023
3024   return vec;
3025 }
3026
3027 /* Return the most specialized of the list of templates in FNS that can
3028    produce an instantiation matching DECL.  */
3029
3030 tree
3031 most_specialized (fns, decl)
3032      tree fns, decl;
3033 {
3034   tree fn, champ, *args, *p;
3035   int fate;
3036
3037   for (p = &fns; *p; )
3038     {
3039       args = get_bindings (TREE_VALUE (*p), decl);
3040       if (args)
3041         {
3042           free (args);
3043           p = &TREE_CHAIN (*p);
3044         }
3045       else
3046         *p = TREE_CHAIN (*p);
3047     }
3048
3049   if (! fns)
3050     return NULL_TREE;
3051
3052   fn = fns;
3053   champ = TREE_VALUE (fn);
3054   fn = TREE_CHAIN (fn);
3055   for (; fn; fn = TREE_CHAIN (fn))
3056     {
3057       fate = more_specialized (champ, TREE_VALUE (fn));
3058       if (fate == 1)
3059         ;
3060       else
3061         {
3062           if (fate == 0)
3063             {
3064               fn = TREE_CHAIN (fn);
3065               if (! fn)
3066                 return error_mark_node;
3067             }
3068           champ = TREE_VALUE (fn);
3069         }
3070     }
3071
3072   for (fn = fns; fn && TREE_VALUE (fn) != champ; fn = TREE_CHAIN (fn))
3073     {
3074       fate = more_specialized (champ, TREE_VALUE (fn));
3075       if (fate != 1)
3076         return error_mark_node;
3077     }
3078
3079   return champ;
3080 }
3081
3082 /* Return the most specialized of the class template specializations in
3083    SPECS that can produce an instantiation matching ARGS.  */
3084
3085 tree
3086 most_specialized_class (specs, mainargs)
3087      tree specs, mainargs;
3088 {
3089   tree list = NULL_TREE, t, args, champ;
3090   int fate;
3091
3092   for (t = specs; t; t = TREE_CHAIN (t))
3093     {
3094       args = get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), mainargs);
3095       if (args)
3096         {
3097           list = decl_tree_cons (TREE_PURPOSE (t), TREE_VALUE (t), list);
3098           TREE_TYPE (list) = TREE_TYPE (t);
3099         }
3100     }
3101
3102   if (! list)
3103     return NULL_TREE;
3104
3105   t = list;
3106   champ = t;
3107   t = TREE_CHAIN (t);
3108   for (; t; t = TREE_CHAIN (t))
3109     {
3110       fate = more_specialized_class (champ, t);
3111       if (fate == 1)
3112         ;
3113       else
3114         {
3115           if (fate == 0)
3116             {
3117               t = TREE_CHAIN (t);
3118               if (! t)
3119                 return error_mark_node;
3120             }
3121           champ = t;
3122         }
3123     }
3124
3125   for (t = list; t && t != champ; t = TREE_CHAIN (t))
3126     {
3127       fate = more_specialized (champ, t);
3128       if (fate != 1)
3129         return error_mark_node;
3130     }
3131
3132   return champ;
3133 }
3134
3135 /* called from the parser.  */
3136
3137 void
3138 do_function_instantiation (declspecs, declarator, storage)
3139      tree declspecs, declarator, storage;
3140 {
3141   tree decl = grokdeclarator (declarator, declspecs, NORMAL, 0, NULL_TREE);
3142   tree name;
3143   tree fn;
3144   tree result = NULL_TREE;
3145   int extern_p = 0;
3146
3147   if (! DECL_LANG_SPECIFIC (decl))
3148     {
3149       cp_error ("explicit instantiation of non-template `%#D'", decl);
3150       return;
3151     }
3152
3153   /* If we've already seen this template instance, use it.  */
3154   if (DECL_FUNCTION_MEMBER_P (decl))
3155     {
3156       if (DECL_TEMPLATE_INSTANTIATION (decl))
3157         result = decl;
3158       else if (name = DECL_ASSEMBLER_NAME (decl),
3159                fn = IDENTIFIER_GLOBAL_VALUE (name),
3160                fn && DECL_TEMPLATE_INSTANTIATION (fn))
3161         result = fn;
3162     }
3163   else if (name = DECL_NAME (decl), fn = IDENTIFIER_GLOBAL_VALUE (name), fn)
3164     {
3165       tree templates = NULL_TREE;
3166       for (fn = get_first_fn (fn); fn; fn = DECL_CHAIN (fn))
3167         if (decls_match (fn, decl)
3168             && DECL_DEFER_OUTPUT (fn))
3169           {
3170             result = fn;
3171             break;
3172           }
3173         else if (TREE_CODE (fn) == TEMPLATE_DECL)
3174           templates = decl_tree_cons (NULL_TREE, fn, templates);
3175
3176       if (! result)
3177         {
3178           tree *args;
3179           result = most_specialized (templates, decl);
3180           if (result == error_mark_node)
3181             {
3182               char *str = "candidates are:";
3183               cp_error ("ambiguous template instantiation for `%D' requested", decl);
3184               for (fn = templates; fn; fn = TREE_CHAIN (fn))
3185                 {
3186                   cp_error_at ("%s %+#D", str, TREE_VALUE (fn));
3187                   str = "               ";
3188                 }
3189               return;
3190             }
3191           else if (result)
3192             {
3193               args = get_bindings (result, decl);
3194               result = instantiate_template (result, args);
3195               free (args);
3196             }
3197         }
3198     }
3199   if (! result)
3200     {
3201       cp_error ("no matching template for `%D' found", decl);
3202       return;
3203     }
3204
3205   if (flag_external_templates)
3206     return;
3207
3208   if (storage == NULL_TREE)
3209     ;
3210   else if (storage == ridpointers[(int) RID_EXTERN])
3211     extern_p = 1;
3212   else
3213     cp_error ("storage class `%D' applied to template instantiation",
3214               storage);
3215
3216   mark_decl_instantiated (result, extern_p);
3217   repo_template_instantiated (result, extern_p);
3218   if (! extern_p)
3219     instantiate_decl (result);
3220 }
3221
3222 void
3223 mark_class_instantiated (t, extern_p)
3224      tree t;
3225      int extern_p;
3226 {
3227   SET_CLASSTYPE_EXPLICIT_INSTANTIATION (t);
3228   SET_CLASSTYPE_INTERFACE_KNOWN (t);
3229   CLASSTYPE_INTERFACE_ONLY (t) = extern_p;
3230   CLASSTYPE_VTABLE_NEEDS_WRITING (t) = ! extern_p;
3231   TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = extern_p;
3232   if (! extern_p)
3233     {
3234       CLASSTYPE_DEBUG_REQUESTED (t) = 1;
3235       rest_of_type_compilation (t, 1);
3236     }
3237 }
3238
3239 void
3240 do_type_instantiation (name, storage)
3241      tree name, storage;
3242 {
3243   tree t = TREE_TYPE (name);
3244   int extern_p = 0;
3245   int nomem_p = 0;
3246   int static_p = 0;
3247
3248   complete_type (t);
3249
3250   /* With -fexternal-templates, explicit instantiations are treated the same
3251      as implicit ones.  */
3252   if (flag_external_templates)
3253     return;
3254
3255   if (TYPE_SIZE (t) == NULL_TREE)
3256     {
3257       cp_error ("explicit instantiation of `%#T' before definition of template",
3258                 t);
3259       return;
3260     }
3261
3262   if (storage == NULL_TREE)
3263     /* OK */;
3264   else if (storage == ridpointers[(int) RID_INLINE])
3265     nomem_p = 1;
3266   else if (storage == ridpointers[(int) RID_EXTERN])
3267     extern_p = 1;
3268   else if (storage == ridpointers[(int) RID_STATIC])
3269     static_p = 1;
3270   else
3271     {
3272       cp_error ("storage class `%D' applied to template instantiation",
3273                 storage);
3274       extern_p = 0;
3275     }
3276
3277   /* We've already instantiated this.  */
3278   if (CLASSTYPE_EXPLICIT_INSTANTIATION (t) && ! CLASSTYPE_INTERFACE_ONLY (t)
3279       && extern_p)
3280     return;
3281
3282   if (! CLASSTYPE_TEMPLATE_SPECIALIZATION (t))
3283     {
3284       mark_class_instantiated (t, extern_p);
3285       repo_template_instantiated (t, extern_p);
3286     }
3287
3288   if (nomem_p)
3289     return;
3290
3291   {
3292     tree tmp;
3293
3294     if (! static_p)
3295       for (tmp = TYPE_METHODS (t); tmp; tmp = TREE_CHAIN (tmp))
3296         if (DECL_TEMPLATE_INSTANTIATION (tmp))
3297           {
3298             mark_decl_instantiated (tmp, extern_p);
3299             repo_template_instantiated (tmp, extern_p);
3300             if (! extern_p)
3301               instantiate_decl (tmp);
3302           }
3303
3304     for (tmp = TYPE_FIELDS (t); tmp; tmp = TREE_CHAIN (tmp))
3305       if (TREE_CODE (tmp) == VAR_DECL && DECL_TEMPLATE_INSTANTIATION (tmp))
3306         {
3307           mark_decl_instantiated (tmp, extern_p);
3308           repo_template_instantiated (tmp, extern_p);
3309           if (! extern_p)
3310             instantiate_decl (tmp);
3311         }
3312
3313     for (tmp = CLASSTYPE_TAGS (t); tmp; tmp = TREE_CHAIN (tmp))
3314       if (IS_AGGR_TYPE (TREE_VALUE (tmp)))
3315         do_type_instantiation (TYPE_MAIN_DECL (TREE_VALUE (tmp)), storage);
3316   }
3317 }
3318
3319 tree
3320 instantiate_decl (d)
3321      tree d;
3322 {
3323   tree ti = DECL_TEMPLATE_INFO (d);
3324   tree tmpl = TI_TEMPLATE (ti);
3325   tree args = TI_ARGS (ti);
3326   tree td;
3327   tree pattern = DECL_TEMPLATE_RESULT (tmpl);
3328   tree save_ti;
3329   int nested = in_function_p ();
3330   int d_defined;
3331   int pattern_defined;
3332   int line = lineno;
3333   char *file = input_filename;
3334
3335   if (TREE_CODE (d) == FUNCTION_DECL)
3336     {
3337       d_defined = (DECL_INITIAL (d) != NULL_TREE);
3338       pattern_defined = (DECL_INITIAL (pattern) != NULL_TREE);
3339     }
3340   else
3341     {
3342       d_defined = ! DECL_IN_AGGR_P (d);
3343       pattern_defined = ! DECL_IN_AGGR_P (pattern);
3344     }
3345
3346   if (d_defined)
3347     return d;
3348   else if (pattern_defined)
3349     {
3350       repo_template_used (d);
3351
3352       if (flag_external_templates && ! DECL_INTERFACE_KNOWN (d))
3353         {
3354           if (flag_alt_external_templates)
3355             {
3356               if (interface_unknown)
3357                 warn_if_unknown_interface (d);
3358             }
3359           else if (DECL_INTERFACE_KNOWN (pattern))
3360             {
3361               DECL_INTERFACE_KNOWN (d) = 1;
3362               DECL_NOT_REALLY_EXTERN (d) = ! DECL_EXTERNAL (pattern);
3363             }
3364           else
3365             warn_if_unknown_interface (pattern);
3366         }
3367
3368       if (at_eof)
3369         import_export_decl (d);
3370     }
3371
3372   /* We need to set up DECL_INITIAL regardless of pattern_defined if the
3373      variable is a static const initialized in the class body.  */
3374   if (TREE_CODE (d) == VAR_DECL
3375       && ! DECL_INITIAL (d) && DECL_INITIAL (pattern))
3376     {
3377       lineno = DECL_SOURCE_LINE (d);
3378       input_filename = DECL_SOURCE_FILE (d);
3379
3380       pushclass (DECL_CONTEXT (d), 2);
3381       DECL_INITIAL (d) = tsubst_expr
3382         (DECL_INITIAL (pattern), &TREE_VEC_ELT (args, 0),
3383          TREE_VEC_LENGTH (args), tmpl);
3384       popclass (1);
3385
3386       lineno = line;
3387       input_filename = file;
3388     }
3389
3390   if (! pattern_defined
3391       || (TREE_CODE (d) == FUNCTION_DECL && ! DECL_INLINE (d)
3392           && (! DECL_INTERFACE_KNOWN (d)
3393               || ! DECL_NOT_REALLY_EXTERN (d)))
3394       /* Kludge: if we compile a constructor in the middle of processing a
3395          toplevel declaration, we blow away the declspecs in
3396          temp_decl_obstack when we call permanent_allocation in
3397          finish_function.  So don't compile it yet.  */
3398       || (TREE_CODE (d) == FUNCTION_DECL && ! nested && ! at_eof))
3399     {
3400       add_pending_template (d);
3401       return d;
3402     }
3403
3404   if (! push_tinst_level (d))
3405     return d;
3406
3407   push_to_top_level ();
3408
3409   lineno = DECL_SOURCE_LINE (d);
3410   input_filename = DECL_SOURCE_FILE (d);
3411
3412   /* Trick tsubst into giving us a new decl in case the template changed.  */
3413   save_ti = DECL_TEMPLATE_INFO (pattern);
3414   DECL_TEMPLATE_INFO (pattern) = NULL_TREE;
3415   td = tsubst (pattern, &TREE_VEC_ELT (args, 0), TREE_VEC_LENGTH (args), tmpl);
3416   DECL_TEMPLATE_INFO (pattern) = save_ti;
3417
3418   /* And set up DECL_INITIAL, since tsubst doesn't.  */
3419   if (TREE_CODE (td) == VAR_DECL)
3420     {
3421       pushclass (DECL_CONTEXT (d), 2);
3422       DECL_INITIAL (td) = tsubst_expr
3423         (DECL_INITIAL (pattern), &TREE_VEC_ELT (args, 0),
3424          TREE_VEC_LENGTH (args), tmpl);
3425       popclass (1);
3426     }
3427
3428   /* Convince duplicate_decls to use the DECL_ARGUMENTS from the new decl.  */
3429   if (TREE_CODE (d) == FUNCTION_DECL)
3430     DECL_INITIAL (td) = error_mark_node;
3431   duplicate_decls (td, d);
3432   if (TREE_CODE (d) == FUNCTION_DECL)
3433     DECL_INITIAL (td) = 0;
3434
3435   if (TREE_CODE (d) == VAR_DECL)
3436     {
3437       DECL_IN_AGGR_P (d) = 0;
3438       if (DECL_INTERFACE_KNOWN (d))
3439         DECL_EXTERNAL (d) = ! DECL_NOT_REALLY_EXTERN (d);
3440       else
3441         {
3442           DECL_EXTERNAL (d) = 1;
3443           DECL_NOT_REALLY_EXTERN (d) = 1;
3444         }
3445       cp_finish_decl (d, DECL_INITIAL (d), NULL_TREE, 0, 0);
3446     }
3447   else if (TREE_CODE (d) == FUNCTION_DECL)
3448     {
3449       tree t = DECL_SAVED_TREE (pattern);
3450
3451       start_function (NULL_TREE, d, NULL_TREE, 1);
3452       store_parm_decls ();
3453
3454       if (t && TREE_CODE (t) == RETURN_INIT)
3455         {
3456           store_return_init
3457             (TREE_OPERAND (t, 0),
3458              tsubst_expr (TREE_OPERAND (t, 1), &TREE_VEC_ELT (args, 0),
3459                           TREE_VEC_LENGTH (args), tmpl));
3460           t = TREE_CHAIN (t);
3461         }
3462
3463       if (t && TREE_CODE (t) == CTOR_INITIALIZER)
3464         {
3465           current_member_init_list
3466             = tsubst_expr_values (TREE_OPERAND (t, 0), args);
3467           current_base_init_list
3468             = tsubst_expr_values (TREE_OPERAND (t, 1), args);
3469           t = TREE_CHAIN (t);
3470         }
3471
3472       setup_vtbl_ptr ();
3473       /* Always keep the BLOCK node associated with the outermost
3474          pair of curley braces of a function.  These are needed
3475          for correct operation of dwarfout.c.  */
3476       keep_next_level ();
3477
3478       my_friendly_assert (TREE_CODE (t) == COMPOUND_STMT, 42);
3479       tsubst_expr (t, &TREE_VEC_ELT (args, 0),
3480                    TREE_VEC_LENGTH (args), tmpl);
3481
3482       finish_function (lineno, 0, nested);
3483     }
3484
3485   lineno = line;
3486   input_filename = file;
3487
3488   pop_from_top_level ();
3489   pop_tinst_level ();
3490
3491   return d;
3492 }
3493
3494 tree
3495 tsubst_chain (t, argvec)
3496      tree t, argvec;
3497 {
3498   if (t)
3499     {
3500       tree first = tsubst (t, &TREE_VEC_ELT (argvec, 0),
3501                            TREE_VEC_LENGTH (argvec), NULL_TREE);
3502       tree last = first;
3503
3504       for (t = TREE_CHAIN (t); t; t = TREE_CHAIN (t))
3505         {
3506           tree x = tsubst (t, &TREE_VEC_ELT (argvec, 0),
3507                            TREE_VEC_LENGTH (argvec), NULL_TREE);
3508           TREE_CHAIN (last) = x;
3509           last = x;
3510         }
3511
3512       return first;
3513     }
3514   return NULL_TREE;
3515 }
3516
3517 tree
3518 tsubst_expr_values (t, argvec)
3519      tree t, argvec;
3520 {
3521   tree first = NULL_TREE;
3522   tree *p = &first;
3523
3524   for (; t; t = TREE_CHAIN (t))
3525     {
3526       tree pur = tsubst_copy (TREE_PURPOSE (t), &TREE_VEC_ELT (argvec, 0),
3527                               TREE_VEC_LENGTH (argvec), NULL_TREE);
3528       tree val = tsubst_expr (TREE_VALUE (t), &TREE_VEC_ELT (argvec, 0),
3529                               TREE_VEC_LENGTH (argvec), NULL_TREE);
3530       *p = build_tree_list (pur, val);
3531       p = &TREE_CHAIN (*p);
3532     }
3533   return first;
3534 }
3535
3536 tree last_tree;
3537
3538 void
3539 add_tree (t)
3540      tree t;
3541 {
3542   last_tree = TREE_CHAIN (last_tree) = t;
3543 }
3544
3545 /* D is an undefined function declaration in the presence of templates with
3546    the same name, listed in FNS.  If one of them can produce D as an
3547    instantiation, remember this so we can instantiate it at EOF if D has
3548    not been defined by that time.  */
3549
3550 void
3551 add_maybe_template (d, fns)
3552      tree d, fns;
3553 {
3554   tree t;
3555
3556   if (DECL_MAYBE_TEMPLATE (d))
3557     return;
3558
3559   t = most_specialized (fns, d);
3560   if (! t)
3561     return;
3562   if (t == error_mark_node)
3563     {
3564       cp_error ("ambiguous template instantiation for `%D'", d);
3565       return;
3566     }
3567
3568   *maybe_template_tail = perm_tree_cons (t, d, NULL_TREE);
3569   maybe_template_tail = &TREE_CHAIN (*maybe_template_tail);
3570   DECL_MAYBE_TEMPLATE (d) = 1;
3571 }