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