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