gcc/cp/pt.c

   1 /* Handle parameterized types (templates) for GNU C++.
   2    Copyright (C) 1992, 93, 94, 95, 96, 1997 Free Software Foundation, Inc.
   3    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
   4    Rewritten by Jason Merrill (jason@cygnus.com).
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 /* Known bugs or deficiencies include:
  24
  25      all methods must be provided in header files; can't use a source
  26      file that contains only the method templates and "just win".  */
  27
  28 #include "config.h"
  29 #include <stdio.h>
  30 #include "obstack.h"
  31
  32 #include "tree.h"
  33 #include "flags.h"
  34 #include "cp-tree.h"
  35 #include "decl.h"
  36 #include "parse.h"
  37 #include "lex.h"
  38 #include "output.h"
  39 #include "defaults.h"
  40 #include "except.h"
  41
  42 #ifdef HAVE_STDLIB_H
  43 #include <stdlib.h>
  44 #endif
  45
  46 extern struct obstack permanent_obstack;
  47
  48 extern int lineno;
  49 extern char *input_filename;
  50 struct pending_inline *pending_template_expansions;
  51
  52 tree current_template_parms;
  53 HOST_WIDE_INT processing_template_decl;
  54
  55 tree pending_templates;
  56 static tree *template_tail = &pending_templates;
  57
  58 tree maybe_templates;
  59 static tree *maybe_template_tail = &maybe_templates;
  60
  61 int minimal_parse_mode;
  62
  63 int processing_specialization;
  64 static int template_header_count;
  65
  66 #define obstack_chunk_alloc xmalloc
  67 #define obstack_chunk_free free
  68
  69 static int unify PROTO((tree, tree *, int, tree, tree, int *, int));
  70 static void add_pending_template PROTO((tree));
  71 static int push_tinst_level PROTO((tree));
  72 static tree classtype_mangled_name PROTO((tree));
  73 static char *mangle_class_name_for_template PROTO((char *, tree, tree));
  74 static tree tsubst_expr_values PROTO((tree, tree));
  75 static int comp_template_args PROTO((tree, tree));
  76 static int list_eq PROTO((tree, tree));
  77 static tree get_class_bindings PROTO((tree, tree, tree));
  78 static tree coerce_template_parms PROTO((tree, tree, tree));
  79 static tree tsubst_enum PROTO((tree, tree, int, tree *));
  80 static tree add_to_template_args PROTO((tree, tree));
  81 static int  type_unification_real PROTO((tree, tree *, tree, tree, int*,
  82                                          int, int, int));
  83 static int processing_explicit_specialization PROTO((int));
  84 static void note_template_header PROTO((int));
  85
  86 /* Restore the template parameter context. */
  87
  88 void
  89 begin_member_template_processing (decl)
  90      tree decl;
  91 {
  92   tree parms;
  93   int i;
  94
  95   parms = DECL_INNERMOST_TEMPLATE_PARMS (DECL_TI_TEMPLATE (decl));
  96
  97   ++processing_template_decl;
  98   current_template_parms
  99     = tree_cons (build_int_2 (0, processing_template_decl),
 100                  parms, current_template_parms);
 101   pushlevel (0);
 102   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
 103     {
 104       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 105       my_friendly_assert (TREE_CODE_CLASS (TREE_CODE (parm)) == 'd', 0);
 106
 107       switch (TREE_CODE (parm))
 108         {
 109         case TYPE_DECL:
 110           pushdecl (parm);
 111           break;
 112
 113         case PARM_DECL:
 114           {
 115             /* Make a CONST_DECL as is done in process_template_parm. */
 116             tree decl = build_decl (CONST_DECL, DECL_NAME (parm),
 117                                     TREE_TYPE (parm));
 118             DECL_INITIAL (decl) = DECL_INITIAL (parm);
 119             pushdecl (decl);
 120           }
 121         break;
 122
 123         default:
 124           my_friendly_abort (0);
 125         }
 126     }
 127 }
 128
 129 /* Undo the effects of begin_member_template_processing. */
 130
 131 void
 132 end_member_template_processing ()
 133 {
 134   if (! processing_template_decl)
 135     return;
 136
 137   --processing_template_decl;
 138   current_template_parms = TREE_CHAIN (current_template_parms);
 139   poplevel (0, 0, 0);
 140 }
 141
 142 /* Returns non-zero iff T is a member template function.  Works if T
 143    is either a FUNCTION_DECL or a TEMPLATE_DECL.  */
 144
 145 int
 146 is_member_template (t)
 147      tree t;
 148 {
 149   int r = 0;
 150
 151   if (TREE_CODE (t) != FUNCTION_DECL
 152       && !DECL_FUNCTION_TEMPLATE_P (t))
 153     /* Anything that isn't a template or a template function is
 154        certainly not a member template.  */
 155     return 0;
 156
 157   if ((DECL_FUNCTION_MEMBER_P (t)
 158        && !DECL_TEMPLATE_SPECIALIZATION (t))
 159       || (TREE_CODE (t) == TEMPLATE_DECL &&
 160           DECL_FUNCTION_MEMBER_P (DECL_TEMPLATE_RESULT (t))))
 161     {
 162       tree tmpl = NULL_TREE;
 163
 164       if (DECL_FUNCTION_TEMPLATE_P (t))
 165         tmpl = t;
 166       else if (DECL_TEMPLATE_INFO (t)
 167                && DECL_FUNCTION_TEMPLATE_P (DECL_TI_TEMPLATE (t)))
 168         tmpl = DECL_TI_TEMPLATE (t);
 169
 170       if (tmpl)
 171         {
 172           tree parms = DECL_TEMPLATE_PARMS (tmpl);
 173           int parm_levels = list_length (parms);
 174           int template_class_levels = 0;
 175           tree ctx = DECL_CLASS_CONTEXT (t);
 176
 177           if (CLASSTYPE_TEMPLATE_INFO (ctx))
 178             {
 179               tree args;
 180
 181               /* Here, we should really count the number of levels
 182                  deep ctx is, making sure not to count any levels that
 183                  are just specializations.  Since there are no member
 184                  template classes yet, we don't have to do all that.  */
 185
 186               if (!CLASSTYPE_TEMPLATE_SPECIALIZATION (ctx))
 187                 template_class_levels = 1;
 188               else
 189                 {
 190                   int i;
 191
 192                   args = CLASSTYPE_TI_ARGS (ctx);
 193
 194                   if (args == NULL_TREE)
 195                     template_class_levels = 1;
 196                   else
 197                     for (i = 0; i < TREE_VEC_LENGTH (args); ++i)
 198                       if (uses_template_parms (TREE_VEC_ELT (args, i)))
 199                         {
 200                           template_class_levels++;
 201                           break;
 202                         }
 203                 }
 204             }
 205
 206           if (parm_levels > template_class_levels)
 207             r = 1;
 208         }
 209     }
 210
 211   return r;
 212 }
 213
 214 /* Return a new template argument vector which contains all of ARGS,
 215    but has as its innermost set of arguments the EXTRA_ARGS.  */
 216
 217 static tree
 218 add_to_template_args (args, extra_args)
 219      tree args;
 220      tree extra_args;
 221 {
 222   tree new_args;
 223
 224   if (TREE_CODE (TREE_VEC_ELT (args, 0)) != TREE_VEC)
 225     {
 226       new_args = make_tree_vec (2);
 227       TREE_VEC_ELT (new_args, 0) = args;
 228     }
 229   else
 230     {
 231       int i;
 232
 233       new_args = make_tree_vec (TREE_VEC_LENGTH (args) - 1);
 234
 235       for (i = 0; i < TREE_VEC_LENGTH (args); ++i)
 236         TREE_VEC_ELT (new_args, i) = TREE_VEC_ELT (args, i);
 237     }
 238
 239   TREE_VEC_ELT (new_args,
 240                 TREE_VEC_LENGTH (new_args) - 1) = extra_args;
 241
 242   return new_args;
 243 }
 244
 245 /* We've got a template header coming up; push to a new level for storing
 246    the parms.  */
 247
 248 void
 249 begin_template_parm_list ()
 250 {
 251   pushlevel (0);
 252   declare_pseudo_global_level ();
 253   ++processing_template_decl;
 254   note_template_header (0);
 255 }
 256
 257
 258 /* We've just seen template <>. */
 259
 260 void
 261 begin_specialization ()
 262 {
 263   note_template_header (1);
 264 }
 265
 266
 267 /* Called at then end of processing a declaration preceeded by
 268    template<>.  */
 269
 270 void
 271 end_specialization ()
 272 {
 273   reset_specialization ();
 274 }
 275
 276
 277 /* Any template <>'s that we have seen thus far are not referring to a
 278    function specialization. */
 279
 280 void
 281 reset_specialization ()
 282 {
 283   processing_specialization = 0;
 284   template_header_count = 0;
 285 }
 286
 287
 288 /* We've just seen a template header.  If SPECIALIZATION is non-zero,
 289    it was of the form template <>.  */
 290
 291 static void
 292 note_template_header (specialization)
 293      int specialization;
 294 {
 295   processing_specialization = specialization;
 296   template_header_count++;
 297 }
 298
 299
 300 /* Returns non-zero iff a declarator, in which the number of template
 301    types that appeared was TEMPLATE_COUNT, is an explicit
 302    specialization.  */
 303
 304 static int
 305 processing_explicit_specialization (template_count)
 306      int template_count;
 307 {
 308   /* A function declaration is an explicit specialization of a member
 309      template if all of the following conditions hold:
 310
 311      o There was a template <...> preceeding the declaration.
 312      o The last template <...> was in fact template <>.
 313      o The number of template <...>'s preceeding the declaration, less
 314        the number of template classes with arguments specified used to
 315        qualify the function name, is 1.
 316
 317      For example:
 318
 319      template <> void S<int>::foo();
 320      template <class T> template <> void S<T>::foo();
 321      template <> struct S<int> { ... template <> void foo(); }
 322
 323      The first of these is not a specialization of S<int>::foo() (it
 324      is instead a specialization of S<T>::foo), while the next two are
 325      specializations of member template functions.  */
 326
 327   return processing_specialization
 328     && template_header_count > template_count;
 329 }
 330
 331 /* Returns the template function specialized by TEMPLATE_ID, or
 332    NULL_TREE if there is none.
 333
 334    The TEMPLATE_ID is a TEMPLATE_ID_EXPR.  The TYPE is
 335    the type it has been declared to have.  Return the TEMPLATE_DECL
 336    that is being specialized, and put the specialization arguments in
 337    *TARGS.  If no appropriate specialization can be found, NULL_TREE is
 338    returned, and *TARGS is assigned NULL_TREE.  If complain is
 339    non-zero, error messages are printed where appropriate.  */
 340
 341 tree
 342 determine_explicit_specialization (template_id, type, targs_out,
 343                                    need_member_template,
 344                                    complain)
 345      tree template_id;
 346      tree type;
 347      tree* targs_out;
 348      int need_member_template;
 349      int complain;
 350 {
 351   int i;
 352   int overloaded;
 353   tree fns;
 354   tree matching_fns = NULL_TREE;
 355   tree result;
 356   tree fn;
 357
 358   my_friendly_assert (TREE_CODE (template_id) == TEMPLATE_ID_EXPR
 359                       && TREE_OPERAND (template_id, 0), 0);
 360
 361   fns = TREE_OPERAND (template_id, 0);
 362
 363   if (is_overloaded_fn (fns))
 364     fn = get_first_fn (fns);
 365   else
 366     fn = NULL_TREE;
 367
 368   overloaded = really_overloaded_fn (fns);
 369
 370   for (; fn != NULL_TREE;
 371        fn = overloaded ? DECL_CHAIN (fn) : NULL_TREE)
 372     {
 373       int dummy = 0;
 374       tree targs;
 375
 376       if (TREE_CODE (fn) != TEMPLATE_DECL
 377           || (need_member_template && !is_member_template (fn)))
 378         continue;
 379
 380       if (list_length (TREE_OPERAND (template_id, 1)) > DECL_NTPARMS (fn))
 381         continue;
 382
 383       targs = make_scratch_vec (DECL_NTPARMS (fn));
 384
 385       /* We allow incomplete unification here, because we are going to
 386          check all the functions. */
 387       i = type_unification (DECL_INNERMOST_TEMPLATE_PARMS (fn),
 388                             &TREE_VEC_ELT (targs, 0),
 389                             type
 390                             ? TYPE_ARG_TYPES (TREE_TYPE (fn)) : NULL_TREE,
 391                             type ? TYPE_ARG_TYPES (type) : NULL_TREE,
 392                             TREE_OPERAND (template_id, 1),
 393                             &dummy, 1, 1);
 394
 395       if (i == 0)
 396         {
 397           /* Unification was successful.  See if the return types
 398              match. */
 399           if (type != NULL_TREE)
 400             {
 401               tree tmpl_return_type = tsubst (TREE_TYPE (TREE_TYPE (fn)),
 402                                               targs,
 403                                               DECL_NTPARMS (fn),
 404                                               NULL_TREE);
 405
 406               if (tmpl_return_type != TREE_TYPE (type))
 407                 {
 408                   /* Always complain about this.  With ambiguity, some
 409                      other context, might resolve things.  But, a
 410                      non-matching return type will always be a
 411                      problem.  */
 412                   cp_error ("Return type of explicit specialization of");
 413                   cp_error ("`%D' is `%T', but should be `%T'.",
 414                             fn, TREE_TYPE (type), tmpl_return_type);
 415                   *targs_out = NULL_TREE;
 416                   return NULL_TREE;
 417                 }
 418             }
 419
 420           matching_fns = scratch_tree_cons (fn, targs, matching_fns);
 421         }
 422     }
 423
 424   if (matching_fns == NULL_TREE)
 425     {
 426       if (complain)
 427         cp_error ("`%D' does not match any template declaration.",
 428                   template_id);
 429
 430       *targs_out = NULL_TREE;
 431       return NULL_TREE;
 432     }
 433
 434   if (TREE_CHAIN (matching_fns) != NULL_TREE)
 435     {
 436       if (complain)
 437         {
 438           tree fn;
 439
 440           cp_error ("Ambiguous explicit specialization.  Candidates are:");
 441           for (fn = matching_fns; fn != NULL_TREE; fn = TREE_CHAIN (fn))
 442             cp_error ("    %D", TREE_PURPOSE (fn));
 443         }
 444
 445       *targs_out = NULL_TREE;
 446       return NULL_TREE;
 447     }
 448
 449   /* We have one, and exactly one, match. */
 450   *targs_out = TREE_VALUE (matching_fns);
 451   return TREE_PURPOSE (matching_fns);
 452 }
 453
 454
 455 /* Check to see if the function just declared, as indicated in
 456    DECLARATOR, and in DECL, is a specialization.  Check that the
 457    specialization is OK.  If FLAGS == 1, we are being called by
 458    finish_struct_methods.  If FLAGS == 2, we are being called by
 459    grokfndecl, and the function has a definition, or is a friend.  If
 460    FLAGS == 3, this is a friend declaration.
 461    Returns 0 if the decl is not an explicit specialization or
 462    instantiation, 1 if it is an explicit specialization, and 2 if it
 463    is an explicit instantiation.  */
 464
 465 int
 466 check_explicit_specialization (declarator, decl, template_count, flags)
 467      tree declarator;
 468      tree decl;
 469      int template_count;
 470      int flags;
 471 {
 472   int finish_member = flags == 1;
 473   int have_def = flags == 2;
 474   int is_friend = flags == 3;
 475
 476   if (processing_explicit_specialization (template_count)
 477       || finish_member
 478       || TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
 479     {
 480       tree tmpl = NULL_TREE;
 481       tree dname = DECL_NAME (decl);
 482       tree ctype = DECL_CLASS_CONTEXT (decl);
 483       tree targs;
 484
 485       /* We've come across a declarator that looks like: U f<T1,
 486          T2, ...>(A1, A2, ..).  This is an explicit template
 487          specialization.  Check that:
 488
 489          o The explicitly specified parameters together with those
 490          that can be deduced by template argument deduction
 491          uniquely determine a particular specialization.
 492
 493          See [temp.expl.spec].  */
 494
 495       if (!finish_member
 496           && TREE_CODE (declarator) == TEMPLATE_ID_EXPR
 497           && !processing_explicit_specialization (template_count)
 498           && !is_friend)
 499         {
 500           if (! have_def && ! template_header_count && ! ctype)
 501             /* This is not an explict specialization.  It must be
 502                an explicit instantiation.  */
 503             return 2;
 504           else if (template_header_count > template_count
 505                    && !processing_specialization)
 506             {
 507               cp_error ("template-id `%D' in declaration of primary template",
 508                         declarator);
 509               return 0;
 510             }
 511           else if (pedantic || uses_template_parms (decl))
 512             pedwarn ("explicit specialization not preceded by `template <>'");
 513         }
 514
 515       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
 516         {
 517           tree fns;
 518
 519           my_friendly_assert (TREE_CODE (declarator) == IDENTIFIER_NODE,
 520                               0);
 521           if (!ctype)
 522             fns = IDENTIFIER_GLOBAL_VALUE (dname);
 523           else
 524             fns = dname;
 525
 526           declarator = lookup_template_function (fns, NULL_TREE);
 527         }
 528
 529       if (TREE_CODE (TREE_OPERAND (declarator, 0)) == LOOKUP_EXPR)
 530         {
 531           /* A friend declaration.  We can't do much, because we don't
 532            know what this resolves to, yet.  */
 533           my_friendly_assert (is_friend != 0, 0);
 534           SET_DECL_IMPLICIT_INSTANTIATION (decl);
 535           return 1;
 536         }
 537
 538       if (ctype
 539           && TREE_CODE (TREE_OPERAND (declarator, 0)) == IDENTIFIER_NODE)
 540         {
 541           tree fns;
 542
 543           if (TYPE_BEING_DEFINED (ctype) && !finish_member)
 544             {
 545               /* Since finish_struct_1 has not been called yet, we
 546                  can't call lookup_fnfields.  We note that this
 547                  template is a specialization, and proceed, letting
 548                  finish_struct_methods fix this up later.  */
 549               SET_DECL_TEMPLATE_SPECIALIZATION (decl);
 550               DECL_TEMPLATE_INFO (decl)
 551                 = perm_tree_cons (NULL_TREE,
 552                                   TREE_OPERAND (declarator, 1),
 553                                   NULL_TREE);
 554               return 1;
 555             }
 556
 557           fns = lookup_fnfields (TYPE_BINFO (ctype),
 558                                  TREE_OPERAND (declarator, 0),
 559                                  1);
 560
 561           if (fns == NULL_TREE)
 562             {
 563               cp_error ("No member template `%s' declared in `%T'",
 564                         IDENTIFIER_POINTER (TREE_OPERAND (declarator,
 565                                                           0)),
 566                         ctype);
 567               return 1;
 568             }
 569           else
 570             TREE_OPERAND (declarator, 0) = fns;
 571         }
 572
 573       tmpl =
 574         determine_explicit_specialization
 575         (declarator, TREE_TYPE (decl), &targs,
 576          TREE_CODE (decl) == TEMPLATE_DECL, 1);
 577
 578       if (tmpl)
 579         {
 580           /* Mangle the function name appropriately.  */
 581           if (name_mangling_version >= 1)
 582             {
 583               tree arg_types = TYPE_ARG_TYPES (TREE_TYPE (tmpl));
 584
 585               if (ctype
 586                   && TREE_CODE (TREE_TYPE (tmpl)) == FUNCTION_TYPE)
 587                 arg_types =
 588                   hash_tree_chain (build_pointer_type (ctype),
 589                                    arg_types);
 590
 591               DECL_ASSEMBLER_NAME (decl)
 592                 = build_template_decl_overload
 593                 (DECL_NAME (decl),
 594                  arg_types,
 595                  TREE_TYPE (TREE_TYPE (tmpl)),
 596                  DECL_INNERMOST_TEMPLATE_PARMS (tmpl),
 597                  targs, ctype != NULL_TREE);
 598             }
 599
 600           if (is_friend && !have_def)
 601             {
 602               /* This is not really a declaration of a specialization.
 603                  It's just the name of an instantiation.  But, it's not
 604                  a request for an instantiation, either.  */
 605               SET_DECL_IMPLICIT_INSTANTIATION (decl);
 606               DECL_TEMPLATE_INFO (decl)
 607                 = perm_tree_cons (tmpl, targs, NULL_TREE);
 608               return 1;
 609             }
 610
 611           /* This function declaration is a template specialization.
 612              Record that fact.  */
 613           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
 614           DECL_TEMPLATE_SPECIALIZATIONS (tmpl)
 615             = perm_tree_cons (targs, decl,
 616                               DECL_TEMPLATE_SPECIALIZATIONS
 617                               (tmpl));
 618           /* If DECL_TI_TEMPLATE (decl), the decl is an
 619              instantiation of a specialization of a member template.
 620              (In other words, there was a member template, in a
 621              class template.  That member template was specialized.
 622              We then instantiated the class, so there is now an
 623              instance of that specialization.)
 624
 625              According to the CD2,
 626
 627              14.7.3.13 [tmpl.expl.spec]
 628
 629              A specialization  of  a member function template or
 630              member class template of a non-specialized class
 631              template is itself a template.
 632
 633              So, we just leave the template info alone in this case.  */
 634           if (!(DECL_TEMPLATE_INFO (decl) && DECL_TI_TEMPLATE (decl)))
 635             DECL_TEMPLATE_INFO (decl)
 636               = perm_tree_cons (tmpl, targs, NULL_TREE);
 637           return 1;
 638         }
 639     }
 640
 641   return 0;
 642 }
 643
 644 /* Process information from new template parameter NEXT and append it to the
 645    LIST being built.  */
 646
 647 tree
 648 process_template_parm (list, next)
 649      tree list, next;
 650 {
 651   tree parm;
 652   tree decl = 0;
 653   tree defval;
 654   int is_type, idx;
 655   parm = next;
 656   my_friendly_assert (TREE_CODE (parm) == TREE_LIST, 259);
 657   defval = TREE_PURPOSE (parm);
 658   parm = TREE_VALUE (parm);
 659   is_type = TREE_PURPOSE (parm) == class_type_node;
 660
 661   if (list)
 662     {
 663       tree p = TREE_VALUE (tree_last (list));
 664
 665       if (TREE_CODE (p) == TYPE_DECL)
 666         idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
 667       else
 668         idx = TEMPLATE_CONST_IDX (DECL_INITIAL (p));
 669       ++idx;
 670     }
 671   else
 672     idx = 0;
 673
 674   if (!is_type)
 675     {
 676       tree tinfo = 0;
 677       my_friendly_assert (TREE_CODE (TREE_PURPOSE (parm)) == TREE_LIST, 260);
 678       /* is a const-param */
 679       parm = grokdeclarator (TREE_VALUE (parm), TREE_PURPOSE (parm),
 680                              PARM, 0, NULL_TREE);
 681       /* A template parameter is not modifiable.  */
 682       TREE_READONLY (parm) = 1;
 683       if (IS_AGGR_TYPE (TREE_TYPE (parm))
 684           && TREE_CODE (TREE_TYPE (parm)) != TEMPLATE_TYPE_PARM)
 685         {
 686           cp_error ("`%#T' is not a valid type for a template constant parameter",
 687                     TREE_TYPE (parm));
 688           if (DECL_NAME (parm) == NULL_TREE)
 689             error ("  a template type parameter must begin with `class' or `typename'");
 690           TREE_TYPE (parm) = void_type_node;
 691         }
 692       else if (pedantic
 693                && (TREE_CODE (TREE_TYPE (parm)) == REAL_TYPE
 694                    || TREE_CODE (TREE_TYPE (parm)) == COMPLEX_TYPE))
 695         cp_pedwarn ("`%T' is not a valid type for a template constant parameter",
 696                     TREE_TYPE (parm));
 697       tinfo = make_node (TEMPLATE_CONST_PARM);
 698       my_friendly_assert (TREE_PERMANENT (tinfo), 260.5);
 699       if (TREE_PERMANENT (parm) == 0)
 700         {
 701           parm = copy_node (parm);
 702           TREE_PERMANENT (parm) = 1;
 703         }
 704       TREE_TYPE (tinfo) = TREE_TYPE (parm);
 705       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
 706       DECL_INITIAL (decl) = tinfo;
 707       DECL_INITIAL (parm) = tinfo;
 708       TEMPLATE_CONST_SET_INFO (tinfo, idx, processing_template_decl);
 709     }
 710   else
 711     {
 712       tree t = make_lang_type (TEMPLATE_TYPE_PARM);
 713       CLASSTYPE_GOT_SEMICOLON (t) = 1;
 714       decl = build_decl (TYPE_DECL, TREE_VALUE (parm), t);
 715       TYPE_NAME (t) = decl;
 716       TYPE_STUB_DECL (t) = decl;
 717       parm = decl;
 718       TEMPLATE_TYPE_SET_INFO (t, idx, processing_template_decl);
 719     }
 720   SET_DECL_ARTIFICIAL (decl);
 721   pushdecl (decl);
 722   parm = build_tree_list (defval, parm);
 723   return chainon (list, parm);
 724 }
 725
 726 /* The end of a template parameter list has been reached.  Process the
 727    tree list into a parameter vector, converting each parameter into a more
 728    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
 729    as PARM_DECLs.  */
 730
 731 tree
 732 end_template_parm_list (parms)
 733      tree parms;
 734 {
 735   int nparms;
 736   tree parm;
 737   tree saved_parmlist = make_tree_vec (list_length (parms));
 738
 739   current_template_parms
 740     = tree_cons (build_int_2 (0, processing_template_decl),
 741                  saved_parmlist, current_template_parms);
 742
 743   for (parm = parms, nparms = 0; parm; parm = TREE_CHAIN (parm), nparms++)
 744     TREE_VEC_ELT (saved_parmlist, nparms) = parm;
 745
 746   return saved_parmlist;
 747 }
 748
 749 /* end_template_decl is called after a template declaration is seen.  */
 750
 751 void
 752 end_template_decl ()
 753 {
 754   reset_specialization ();
 755
 756   if (! processing_template_decl)
 757     return;
 758
 759   /* This matches the pushlevel in begin_template_parm_list.  */
 760   poplevel (0, 0, 0);
 761
 762   --processing_template_decl;
 763   current_template_parms = TREE_CHAIN (current_template_parms);
 764   (void) get_pending_sizes ();  /* Why? */
 765 }
 766
 767 /* Generate a valid set of template args from current_template_parms.  */
 768
 769 tree
 770 current_template_args ()
 771 {
 772   tree header = current_template_parms;
 773   int length = list_length (header);
 774   tree args = make_tree_vec (length);
 775   int l = length;
 776
 777   while (header)
 778     {
 779       tree a = copy_node (TREE_VALUE (header));
 780       int i = TREE_VEC_LENGTH (a);
 781       TREE_TYPE (a) = NULL_TREE;
 782       while (i--)
 783         {
 784           tree t = TREE_VEC_ELT (a, i);
 785
 786           /* t will be a list if we are called from within a
 787              begin/end_template_parm_list pair, but a vector directly
 788              if within a begin/end_member_template_processing pair.  */
 789           if (TREE_CODE (t) == TREE_LIST)
 790             {
 791               t = TREE_VALUE (t);
 792
 793               if (TREE_CODE (t) == TYPE_DECL)
 794                 t = TREE_TYPE (t);
 795               else
 796                 t = DECL_INITIAL (t);
 797             }
 798
 799           TREE_VEC_ELT (a, i) = t;
 800         }
 801       TREE_VEC_ELT (args, --l) = a;
 802       header = TREE_CHAIN (header);
 803     }
 804
 805   return args;
 806 }
 807
 808 void
 809 push_template_decl (decl)
 810      tree decl;
 811 {
 812   tree tmpl;
 813   tree args = NULL_TREE;
 814   tree info;
 815   tree ctx = DECL_CONTEXT (decl) ? DECL_CONTEXT (decl) : current_class_type;
 816   int primary = 0;
 817
 818   /* Kludge! */
 819   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_FRIEND_P (decl)
 820       && DECL_CLASS_CONTEXT (decl))
 821     ;
 822   /* Note that this template is a "primary template" */
 823   else if (! ctx || ! CLASSTYPE_TEMPLATE_INFO (ctx)
 824       /* || (processing_template_decl > CLASSTYPE_TEMPLATE_LEVEL (ctx)) */)
 825     primary = 1;
 826
 827   /* Partial specialization.  */
 828   if (TREE_CODE (decl) == TYPE_DECL && DECL_ARTIFICIAL (decl)
 829       && CLASSTYPE_TEMPLATE_SPECIALIZATION (TREE_TYPE (decl)))
 830     {
 831       tree type = TREE_TYPE (decl);
 832       tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
 833       tree mainargs = CLASSTYPE_TI_ARGS (type);
 834       tree spec = DECL_TEMPLATE_SPECIALIZATIONS (maintmpl);
 835
 836       for (; spec; spec = TREE_CHAIN (spec))
 837         {
 838           /* purpose: args to main template
 839              value: spec template */
 840           if (comp_template_args (TREE_PURPOSE (spec), mainargs))
 841             return;
 842         }
 843
 844       DECL_TEMPLATE_SPECIALIZATIONS (maintmpl) = CLASSTYPE_TI_SPEC_INFO (type)
 845         = perm_tree_cons (mainargs, TREE_VALUE (current_template_parms),
 846                           DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
 847       TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
 848       return;
 849     }
 850
 851   args = current_template_args ();
 852
 853   if (! ctx || TYPE_BEING_DEFINED (ctx))
 854     {
 855       tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
 856       DECL_TEMPLATE_PARMS (tmpl) = current_template_parms;
 857       DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
 858       if (DECL_LANG_SPECIFIC (decl))
 859         {
 860           DECL_CLASS_CONTEXT (tmpl) = DECL_CLASS_CONTEXT (decl);
 861           DECL_STATIC_FUNCTION_P (tmpl) =
 862             DECL_STATIC_FUNCTION_P (decl);
 863
 864           if (DECL_TEMPLATE_SPECIALIZATION (decl))
 865             {
 866               /* A specialization of a member template of a template
 867                  class. */
 868               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
 869               DECL_TEMPLATE_INFO (tmpl) = DECL_TEMPLATE_INFO (decl);
 870               DECL_TEMPLATE_INFO (decl) = NULL_TREE;
 871             }
 872         }
 873     }
 874   else
 875     {
 876       tree t;
 877       tree a;
 878
 879       if (CLASSTYPE_TEMPLATE_INSTANTIATION (ctx))
 880         cp_error ("must specialize `%#T' before defining member `%#D'",
 881                   ctx, decl);
 882       if (TREE_CODE (decl) == TYPE_DECL && DECL_ARTIFICIAL (decl))
 883         tmpl = CLASSTYPE_TI_TEMPLATE (TREE_TYPE (decl));
 884       else if (! DECL_TEMPLATE_INFO (decl))
 885         {
 886           cp_error ("template definition of non-template `%#D'", decl);
 887           return;
 888         }
 889       else
 890         tmpl = DECL_TI_TEMPLATE (decl);
 891
 892       if (is_member_template (tmpl))
 893         {
 894           a = TREE_VEC_ELT (args, TREE_VEC_LENGTH (args) - 1);
 895           t = DECL_INNERMOST_TEMPLATE_PARMS (DECL_TI_TEMPLATE (decl));
 896           if (TREE_VEC_LENGTH (t)
 897               != TREE_VEC_LENGTH (a))
 898             {
 899               cp_error ("got %d template parameters for `%#D'",
 900                         TREE_VEC_LENGTH (a), decl);
 901               cp_error ("  but %d required", TREE_VEC_LENGTH (t));
 902             }
 903           if (TREE_VEC_LENGTH (args) > 1)
 904             /* Get the template parameters for the enclosing template
 905                class.  */
 906             a = TREE_VEC_ELT (args, TREE_VEC_LENGTH (args) - 2);
 907           else
 908             a = NULL_TREE;
 909         }
 910       else
 911         a = TREE_VEC_ELT (args, TREE_VEC_LENGTH (args) - 1);
 912
 913       t = NULL_TREE;
 914
 915       if (CLASSTYPE_TEMPLATE_SPECIALIZATION (ctx))
 916         {
 917           /* When processing an inline member template of a
 918              specialized class, there is no CLASSTYPE_TI_SPEC_INFO.  */
 919           if (CLASSTYPE_TI_SPEC_INFO (ctx))
 920             t = TREE_VALUE (CLASSTYPE_TI_SPEC_INFO (ctx));
 921         }
 922       else if (CLASSTYPE_TEMPLATE_INFO (ctx))
 923         t = DECL_INNERMOST_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (ctx));
 924
 925       /* There should be template arguments if and only if there is a
 926          template class.  */
 927       my_friendly_assert((a != NULL_TREE) == (t != NULL_TREE), 0);
 928
 929       if (t != NULL_TREE
 930           && TREE_VEC_LENGTH (t) != TREE_VEC_LENGTH (a))
 931         {
 932           cp_error ("got %d template parameters for `%#D'",
 933                     TREE_VEC_LENGTH (a), decl);
 934           cp_error ("  but `%#T' has %d", ctx, TREE_VEC_LENGTH (t));
 935         }
 936     }
 937   /* Get the innermost set of template arguments. */
 938   args = TREE_VEC_ELT (args, TREE_VEC_LENGTH (args) - 1);
 939
 940   DECL_TEMPLATE_RESULT (tmpl) = decl;
 941   TREE_TYPE (tmpl) = TREE_TYPE (decl);
 942
 943   if (! ctx)
 944     tmpl = pushdecl_top_level (tmpl);
 945
 946   if (primary)
 947     TREE_TYPE (DECL_INNERMOST_TEMPLATE_PARMS (tmpl)) = tmpl;
 948
 949   info = perm_tree_cons (tmpl, args, NULL_TREE);
 950
 951   if (TREE_CODE (decl) == TYPE_DECL && DECL_ARTIFICIAL (decl))
 952     {
 953       CLASSTYPE_TEMPLATE_INFO (TREE_TYPE (tmpl)) = info;
 954       DECL_NAME (decl) = classtype_mangled_name (TREE_TYPE (decl));
 955     }
 956   else if (! DECL_LANG_SPECIFIC (decl))
 957     cp_error ("template declaration of `%#D'", decl);
 958   else
 959     DECL_TEMPLATE_INFO (decl) = info;
 960 }
 961
 962 /* Convert all template arguments to their appropriate types, and return
 963    a vector containing the resulting values.  If any error occurs, return
 964    error_mark_node.  */
 965
 966 static tree
 967 coerce_template_parms (parms, arglist, in_decl)
 968      tree parms, arglist;
 969      tree in_decl;
 970 {
 971   int nparms, nargs, i, lost = 0;
 972   tree vec;
 973
 974   if (arglist == NULL_TREE)
 975     nargs = 0;
 976   else if (TREE_CODE (arglist) == TREE_VEC)
 977     nargs = TREE_VEC_LENGTH (arglist);
 978   else
 979     nargs = list_length (arglist);
 980
 981   nparms = TREE_VEC_LENGTH (parms);
 982
 983   if (nargs > nparms
 984       || (nargs < nparms
 985           && TREE_PURPOSE (TREE_VEC_ELT (parms, nargs)) == NULL_TREE))
 986     {
 987       error ("incorrect number of parameters (%d, should be %d)",
 988              nargs, nparms);
 989       if (in_decl)
 990         cp_error_at ("in template expansion for decl `%D'", in_decl);
 991       return error_mark_node;
 992     }
 993
 994   if (arglist && TREE_CODE (arglist) == TREE_VEC)
 995     vec = copy_node (arglist);
 996   else
 997     {
 998       vec = make_tree_vec (nparms);
 999       for (i = 0; i < nparms; i++)
1000         {
1001           tree arg;
1002
1003           if (arglist)
1004             {
1005               arg = arglist;
1006               arglist = TREE_CHAIN (arglist);
1007
1008               if (arg == error_mark_node)
1009                 lost++;
1010               else
1011                 arg = TREE_VALUE (arg);
1012             }
1013           else if (TREE_CODE (TREE_VALUE (TREE_VEC_ELT (parms, i)))
1014                    == TYPE_DECL)
1015             arg = tsubst (TREE_PURPOSE (TREE_VEC_ELT (parms, i)),
1016                           vec, i, in_decl);
1017           else
1018             arg = tsubst_expr (TREE_PURPOSE (TREE_VEC_ELT (parms, i)),
1019                                vec, i, in_decl);
1020
1021           TREE_VEC_ELT (vec, i) = arg;
1022         }
1023     }
1024   for (i = 0; i < nparms; i++)
1025     {
1026       tree arg = TREE_VEC_ELT (vec, i);
1027       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
1028       tree val = 0;
1029       int is_type, requires_type;
1030
1031       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
1032       requires_type = TREE_CODE (parm) == TYPE_DECL;
1033
1034       if (requires_type && ! is_type && TREE_CODE (arg) == SCOPE_REF
1035           && TREE_CODE (TREE_OPERAND (arg, 0)) == TEMPLATE_TYPE_PARM)
1036         {
1037           cp_pedwarn ("to refer to a type member of a template parameter,");
1038           cp_pedwarn ("  use `typename %E'", arg);
1039           arg = make_typename_type (TREE_OPERAND (arg, 0),
1040                                     TREE_OPERAND (arg, 1));
1041           is_type = 1;
1042         }
1043       if (is_type != requires_type)
1044         {
1045           if (in_decl)
1046             {
1047               cp_error ("type/value mismatch at argument %d in template parameter list for `%D'",
1048                         i, in_decl);
1049               if (is_type)
1050                 cp_error ("  expected a constant of type `%T', got `%T'",
1051                           TREE_TYPE (parm), arg);
1052               else
1053                 cp_error ("  expected a type, got `%E'", arg);
1054             }
1055           lost++;
1056           TREE_VEC_ELT (vec, i) = error_mark_node;
1057           continue;
1058         }
1059       if (is_type)
1060         {
1061           val = groktypename (arg);
1062           if (! processing_template_decl)
1063             {
1064               tree t = target_type (val);
1065               if (TREE_CODE (t) != TYPENAME_TYPE
1066                   && IS_AGGR_TYPE (t)
1067                   && decl_function_context (TYPE_MAIN_DECL (t)))
1068                 {
1069                   cp_error ("type `%T' composed from a local class is not a valid template-argument", val);
1070                   return error_mark_node;
1071                 }
1072             }
1073         }
1074       else
1075         {
1076           tree t = tsubst (TREE_TYPE (parm), vec,
1077                            TREE_VEC_LENGTH (vec), in_decl);
1078           if (processing_template_decl)
1079             val = arg;
1080           else
1081             val = digest_init (t, arg, (tree *) 0);
1082
1083           if (val == error_mark_node || processing_template_decl)
1084             ;
1085
1086           /* 14.2: Other template-arguments must be constant-expressions,
1087              addresses of objects or functions with external linkage, or of
1088              static class members.  */
1089           else if (IS_AGGR_TYPE (TREE_TYPE (val)))
1090             {
1091               cp_error ("object `%E' cannot be used as template argument", arg);
1092               val = error_mark_node;
1093             }
1094           else if (!TREE_CONSTANT (val))
1095             {
1096               cp_error ("non-constant `%E' cannot be used as template argument",
1097                         arg);
1098               val = error_mark_node;
1099             }
1100           else if (POINTER_TYPE_P (TREE_TYPE (val))
1101                    && ! integer_zerop (val)
1102                    && TREE_CODE (TREE_TYPE (TREE_TYPE (val))) != OFFSET_TYPE
1103                    && TREE_CODE (TREE_TYPE (TREE_TYPE (val))) != METHOD_TYPE)
1104             {
1105               t = val;
1106               STRIP_NOPS (t);
1107               if (TREE_CODE (t) == ADDR_EXPR)
1108                 {
1109                   tree a = TREE_OPERAND (t, 0);
1110                   STRIP_NOPS (a);
1111                   if (TREE_CODE (a) == STRING_CST)
1112                     {
1113                       cp_error ("string literal %E is not a valid template argument", a);
1114                       error ("because it is the address of an object with static linkage");
1115                       val = error_mark_node;
1116                     }
1117                   else if (TREE_CODE (a) != VAR_DECL
1118                            && TREE_CODE (a) != FUNCTION_DECL)
1119                     goto bad;
1120                   else if (! TREE_PUBLIC (a))
1121                     {
1122                       cp_error ("address of non-extern `%E' cannot be used as template argument", a);
1123                       val = error_mark_node;
1124                     }
1125                 }
1126               else
1127                 {
1128                 bad:
1129                   cp_error ("`%E' is not a valid template argument", t);
1130                   error ("it must be %s%s with external linkage",
1131                          TREE_CODE (TREE_TYPE (val)) == POINTER_TYPE
1132                          ? "a pointer to " : "",
1133                          TREE_CODE (TREE_TYPE (TREE_TYPE (val))) == FUNCTION_TYPE
1134                          ? "a function" : "an object");
1135                   val = error_mark_node;
1136                 }
1137             }
1138         }
1139
1140       if (val == error_mark_node)
1141         lost++;
1142
1143       TREE_VEC_ELT (vec, i) = val;
1144     }
1145   if (lost)
1146     return error_mark_node;
1147   return vec;
1148 }
1149
1150 static int
1151 comp_template_args (oldargs, newargs)
1152      tree oldargs, newargs;
1153 {
1154   int i;
1155
1156   if (TREE_VEC_LENGTH (oldargs) != TREE_VEC_LENGTH (newargs))
1157     return 0;
1158
1159   for (i = 0; i < TREE_VEC_LENGTH (oldargs); ++i)
1160     {
1161       tree nt = TREE_VEC_ELT (newargs, i);
1162       tree ot = TREE_VEC_ELT (oldargs, i);
1163
1164       if (nt == ot)
1165         continue;
1166       if (TREE_CODE (nt) != TREE_CODE (ot))
1167         return 0;
1168       if (TREE_CODE (nt) == TREE_VEC)
1169         {
1170           /* For member templates */
1171           if (comp_template_args (nt, ot))
1172             continue;
1173         }
1174       else if (TREE_CODE_CLASS (TREE_CODE (ot)) == 't')
1175         {
1176           if (comptypes (ot, nt, 1))
1177             continue;
1178         }
1179       else if (cp_tree_equal (ot, nt) > 0)
1180         continue;
1181       return 0;
1182     }
1183   return 1;
1184 }
1185
1186 /* Given class template name and parameter list, produce a user-friendly name
1187    for the instantiation.  */
1188
1189 static char *
1190 mangle_class_name_for_template (name, parms, arglist)
1191      char *name;
1192      tree parms, arglist;
1193 {
1194   static struct obstack scratch_obstack;
1195   static char *scratch_firstobj;
1196   int i, nparms;
1197
1198   if (!scratch_firstobj)
1199     gcc_obstack_init (&scratch_obstack);
1200   else
1201     obstack_free (&scratch_obstack, scratch_firstobj);
1202   scratch_firstobj = obstack_alloc (&scratch_obstack, 1);
1203
1204 #if 0
1205 #define buflen  sizeof(buf)
1206 #define check   if (bufp >= buf+buflen-1) goto too_long
1207 #define ccat(c) *bufp++=(c); check
1208 #define advance bufp+=strlen(bufp); check
1209 #define cat(s)  strncpy(bufp, s, buf+buflen-bufp-1); advance
1210 #else
1211 #define check
1212 #define ccat(c) obstack_1grow (&scratch_obstack, (c));
1213 #define advance
1214 #define cat(s)  obstack_grow (&scratch_obstack, (s), strlen (s))
1215 #endif
1216
1217   cat (name);
1218   ccat ('<');
1219   nparms = TREE_VEC_LENGTH (parms);
1220   my_friendly_assert (nparms == TREE_VEC_LENGTH (arglist), 268);
1221   for (i = 0; i < nparms; i++)
1222     {
1223       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
1224       tree arg = TREE_VEC_ELT (arglist, i);
1225
1226       if (i)
1227         ccat (',');
1228
1229       if (TREE_CODE (parm) == TYPE_DECL)
1230         {
1231           cat (type_as_string (arg, 0));
1232           continue;
1233         }
1234       else
1235         my_friendly_assert (TREE_CODE (parm) == PARM_DECL, 269);
1236
1237       if (TREE_CODE (arg) == TREE_LIST)
1238         {
1239           /* New list cell was built because old chain link was in
1240              use.  */
1241           my_friendly_assert (TREE_PURPOSE (arg) == NULL_TREE, 270);
1242           arg = TREE_VALUE (arg);
1243         }
1244       /* No need to check arglist against parmlist here; we did that
1245          in coerce_template_parms, called from lookup_template_class.  */
1246       cat (expr_as_string (arg, 0));
1247     }
1248   {
1249     char *bufp = obstack_next_free (&scratch_obstack);
1250     int offset = 0;
1251     while (bufp[offset - 1] == ' ')
1252       offset--;
1253     obstack_blank_fast (&scratch_obstack, offset);
1254
1255     /* B<C<char> >, not B<C<char>> */
1256     if (bufp[offset - 1] == '>')
1257       ccat (' ');
1258   }
1259   ccat ('>');
1260   ccat ('\0');
1261   return (char *) obstack_base (&scratch_obstack);
1262
1263 #if 0
1264  too_long:
1265 #endif
1266   fatal ("out of (preallocated) string space creating template instantiation name");
1267   /* NOTREACHED */
1268   return NULL;
1269 }
1270
1271 static tree
1272 classtype_mangled_name (t)
1273      tree t;
1274 {
1275   if (CLASSTYPE_TEMPLATE_INFO (t)
1276       && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t)))
1277     {
1278       tree name = DECL_NAME (CLASSTYPE_TI_TEMPLATE (t));
1279       char *mangled_name = mangle_class_name_for_template
1280         (IDENTIFIER_POINTER (name),
1281          DECL_INNERMOST_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (t)),
1282          CLASSTYPE_TI_ARGS (t));
1283       tree id = get_identifier (mangled_name);
1284       IDENTIFIER_TEMPLATE (id) = name;
1285       return id;
1286     }
1287   else
1288     return TYPE_IDENTIFIER (t);
1289 }
1290
1291 static void
1292 add_pending_template (d)
1293      tree d;
1294 {
1295   tree ti;
1296
1297   if (TREE_CODE_CLASS (TREE_CODE (d)) == 't')
1298     ti = CLASSTYPE_TEMPLATE_INFO (d);
1299   else
1300     ti = DECL_TEMPLATE_INFO (d);
1301
1302   if (TI_PENDING_TEMPLATE_FLAG (ti))
1303     return;
1304
1305   *template_tail = perm_tree_cons
1306     (current_function_decl, d, NULL_TREE);
1307   template_tail = &TREE_CHAIN (*template_tail);
1308   TI_PENDING_TEMPLATE_FLAG (ti) = 1;
1309 }
1310
1311
1312 /* Return a TEMPLATE_ID_EXPR corresponding to the indicated FNS (which
1313    may be either a _DECL or an overloaded function or an
1314    IDENTIFIER_NODE), and ARGLIST.  */
1315
1316 tree
1317 lookup_template_function (fns, arglist)
1318      tree fns, arglist;
1319 {
1320   if (fns == NULL_TREE)
1321     {
1322       cp_error ("non-template used as template");
1323       return error_mark_node;
1324     }
1325
1326   if (arglist != NULL_TREE && !TREE_PERMANENT (arglist))
1327     {
1328       push_obstacks (&permanent_obstack, &permanent_obstack);
1329       arglist = copy_list (arglist);
1330       pop_obstacks ();
1331     }
1332
1333   return build_min (TEMPLATE_ID_EXPR,
1334                     TREE_TYPE (fns)
1335                     ? TREE_TYPE (fns) : unknown_type_node,
1336                     fns, arglist);
1337 }
1338
1339
1340 /* Given an IDENTIFIER_NODE (type TEMPLATE_DECL) and a chain of
1341    parameters, find the desired type.
1342
1343    D1 is the PTYPENAME terminal, and ARGLIST is the list of arguments.
1344    Since ARGLIST is build on the decl_obstack, we must copy it here
1345    to keep it from being reclaimed when the decl storage is reclaimed.
1346
1347    IN_DECL, if non-NULL, is the template declaration we are trying to
1348    instantiate.  */
1349
1350 tree
1351 lookup_template_class (d1, arglist, in_decl)
1352      tree d1, arglist;
1353      tree in_decl;
1354 {
1355   tree template, parmlist;
1356   char *mangled_name;
1357   tree id, t;
1358
1359   if (TREE_CODE (d1) == IDENTIFIER_NODE)
1360     {
1361       template = IDENTIFIER_GLOBAL_VALUE (d1); /* XXX */
1362       if (! template)
1363         template = IDENTIFIER_CLASS_VALUE (d1);
1364     }
1365   else if (TREE_CODE (d1) == TYPE_DECL && IS_AGGR_TYPE (TREE_TYPE (d1)))
1366     {
1367       template = CLASSTYPE_TI_TEMPLATE (TREE_TYPE (d1));
1368       d1 = DECL_NAME (template);
1369     }
1370   else if (TREE_CODE_CLASS (TREE_CODE (d1)) == 't' && IS_AGGR_TYPE (d1))
1371     {
1372       template = CLASSTYPE_TI_TEMPLATE (d1);
1373       d1 = DECL_NAME (template);
1374     }
1375   else
1376     my_friendly_abort (272);
1377
1378   /* With something like `template <class T> class X class X { ... };'
1379      we could end up with D1 having nothing but an IDENTIFIER_LOCAL_VALUE.
1380      We don't want to do that, but we have to deal with the situation, so
1381      let's give them some syntax errors to chew on instead of a crash.  */
1382   if (! template)
1383     return error_mark_node;
1384   if (TREE_CODE (template) != TEMPLATE_DECL)
1385     {
1386       cp_error ("non-template type `%T' used as a template", d1);
1387       if (in_decl)
1388         cp_error_at ("for template declaration `%D'", in_decl);
1389       return error_mark_node;
1390     }
1391
1392   if (PRIMARY_TEMPLATE_P (template))
1393     {
1394       parmlist = DECL_INNERMOST_TEMPLATE_PARMS (template);
1395
1396       arglist = coerce_template_parms (parmlist, arglist, template);
1397       if (arglist == error_mark_node)
1398         return error_mark_node;
1399       if (uses_template_parms (arglist))
1400         {
1401           tree found;
1402           if (comp_template_args
1403               (CLASSTYPE_TI_ARGS (TREE_TYPE (template)), arglist))
1404             found = TREE_TYPE (template);
1405           else
1406             {
1407               for (found = DECL_TEMPLATE_INSTANTIATIONS (template);
1408                    found; found = TREE_CHAIN (found))
1409                 {
1410                   if (TI_USES_TEMPLATE_PARMS (found)
1411                       && comp_template_args (TREE_PURPOSE (found), arglist))
1412                     break;
1413                 }
1414               if (found)
1415                 found = TREE_VALUE (found);
1416             }
1417
1418           if (found)
1419             {
1420               if (can_free (&permanent_obstack, arglist))
1421                 obstack_free (&permanent_obstack, arglist);
1422               return found;
1423             }
1424         }
1425
1426       mangled_name = mangle_class_name_for_template (IDENTIFIER_POINTER (d1),
1427                                                      parmlist, arglist);
1428       id = get_identifier (mangled_name);
1429       IDENTIFIER_TEMPLATE (id) = d1;
1430
1431       maybe_push_to_top_level (uses_template_parms (arglist));
1432       t = xref_tag_from_type (TREE_TYPE (template), id, 1);
1433       pop_from_top_level ();
1434     }
1435   else
1436     {
1437       tree ctx = lookup_template_class (TYPE_CONTEXT (TREE_TYPE (template)),
1438                                         arglist, in_decl);
1439       id = d1;
1440       arglist = CLASSTYPE_TI_ARGS (ctx);
1441
1442       if (TYPE_BEING_DEFINED (ctx) && ctx == current_class_type)
1443         {
1444           int save_temp = processing_template_decl;
1445           processing_template_decl = 0;
1446           t = xref_tag_from_type (TREE_TYPE (template), id, 0);
1447           processing_template_decl = save_temp;
1448         }
1449       else
1450         {
1451           t = lookup_nested_type_by_name (ctx, id);
1452           my_friendly_assert (t != NULL_TREE, 42);
1453         }
1454     }
1455
1456   /* Seems to be wanted.  */
1457   CLASSTYPE_GOT_SEMICOLON (t) = 1;
1458
1459   if (! CLASSTYPE_TEMPLATE_INFO (t))
1460     {
1461       arglist = copy_to_permanent (arglist);
1462       CLASSTYPE_TEMPLATE_INFO (t)
1463         = perm_tree_cons (template, arglist, NULL_TREE);
1464       DECL_TEMPLATE_INSTANTIATIONS (template) = perm_tree_cons
1465         (arglist, t, DECL_TEMPLATE_INSTANTIATIONS (template));
1466       TI_USES_TEMPLATE_PARMS (DECL_TEMPLATE_INSTANTIATIONS (template))
1467         = uses_template_parms (arglist);
1468
1469       SET_CLASSTYPE_IMPLICIT_INSTANTIATION (t);
1470
1471       /* We need to set this again after CLASSTYPE_TEMPLATE_INFO is set up.  */
1472       DECL_ASSEMBLER_NAME (TYPE_MAIN_DECL (t)) = id;
1473       /* if (! uses_template_parms (arglist)) */
1474         DECL_ASSEMBLER_NAME (TYPE_MAIN_DECL (t))
1475           = get_identifier (build_overload_name (t, 1, 1));
1476
1477       if (flag_external_templates && ! uses_template_parms (arglist)
1478           && CLASSTYPE_INTERFACE_KNOWN (TREE_TYPE (template))
1479           && ! CLASSTYPE_INTERFACE_ONLY (TREE_TYPE (template)))
1480         add_pending_template (t);
1481     }
1482
1483   return t;
1484 }
1485 \f
1486 /* Should be defined in parse.h.  */
1487 extern int yychar;
1488
1489 int
1490 uses_template_parms (t)
1491      tree t;
1492 {
1493   if (!t)
1494     return 0;
1495   switch (TREE_CODE (t))
1496     {
1497     case INDIRECT_REF:
1498     case COMPONENT_REF:
1499       /* We assume that the object must be instantiated in order to build
1500          the COMPONENT_REF, so we test only whether the type of the
1501          COMPONENT_REF uses template parms.  */
1502       return uses_template_parms (TREE_TYPE (t));
1503
1504     case IDENTIFIER_NODE:
1505       if (!IDENTIFIER_TEMPLATE (t))
1506         return 0;
1507       my_friendly_abort (42);
1508
1509       /* aggregates of tree nodes */
1510     case TREE_VEC:
1511       {
1512         int i = TREE_VEC_LENGTH (t);
1513         while (i--)
1514           if (uses_template_parms (TREE_VEC_ELT (t, i)))
1515             return 1;
1516         return 0;
1517       }
1518     case TREE_LIST:
1519       if (uses_template_parms (TREE_PURPOSE (t))
1520           || uses_template_parms (TREE_VALUE (t)))
1521         return 1;
1522       return uses_template_parms (TREE_CHAIN (t));
1523
1524       /* constructed type nodes */
1525     case POINTER_TYPE:
1526     case REFERENCE_TYPE:
1527       return uses_template_parms (TREE_TYPE (t));
1528     case RECORD_TYPE:
1529       if (TYPE_PTRMEMFUNC_FLAG (t))
1530         return uses_template_parms (TYPE_PTRMEMFUNC_FN_TYPE (t));
1531     case UNION_TYPE:
1532       if (! CLASSTYPE_TEMPLATE_INFO (t))
1533         return 0;
1534       return uses_template_parms (TREE_VALUE (CLASSTYPE_TEMPLATE_INFO (t)));
1535     case FUNCTION_TYPE:
1536       if (uses_template_parms (TYPE_ARG_TYPES (t)))
1537         return 1;
1538       return uses_template_parms (TREE_TYPE (t));
1539     case ARRAY_TYPE:
1540       if (uses_template_parms (TYPE_DOMAIN (t)))
1541         return 1;
1542       return uses_template_parms (TREE_TYPE (t));
1543     case OFFSET_TYPE:
1544       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
1545         return 1;
1546       return uses_template_parms (TREE_TYPE (t));
1547     case METHOD_TYPE:
1548       if (uses_template_parms (TYPE_METHOD_BASETYPE (t)))
1549         return 1;
1550       if (uses_template_parms (TYPE_ARG_TYPES (t)))
1551         return 1;
1552       return uses_template_parms (TREE_TYPE (t));
1553
1554       /* decl nodes */
1555     case TYPE_DECL:
1556       return uses_template_parms (TREE_TYPE (t));
1557
1558     case FUNCTION_DECL:
1559     case VAR_DECL:
1560       /* ??? What about FIELD_DECLs?  */
1561       if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t)
1562           && uses_template_parms (DECL_TI_ARGS (t)))
1563         return 1;
1564       /* fall through */
1565     case CONST_DECL:
1566     case PARM_DECL:
1567       if (uses_template_parms (TREE_TYPE (t)))
1568         return 1;
1569       if (DECL_CONTEXT (t) && uses_template_parms (DECL_CONTEXT (t)))
1570         return 1;
1571       return 0;
1572
1573     case CALL_EXPR:
1574       return uses_template_parms (TREE_TYPE (t));
1575     case ADDR_EXPR:
1576       return uses_template_parms (TREE_OPERAND (t, 0));
1577
1578       /* template parm nodes */
1579     case TEMPLATE_TYPE_PARM:
1580     case TEMPLATE_CONST_PARM:
1581       return 1;
1582
1583       /* simple type nodes */
1584     case INTEGER_TYPE:
1585       if (uses_template_parms (TYPE_MIN_VALUE (t)))
1586         return 1;
1587       return uses_template_parms (TYPE_MAX_VALUE (t));
1588
1589     case REAL_TYPE:
1590     case COMPLEX_TYPE:
1591     case VOID_TYPE:
1592     case BOOLEAN_TYPE:
1593       return 0;
1594
1595     case ENUMERAL_TYPE:
1596       {
1597         tree v;
1598
1599         for (v = TYPE_VALUES (t); v != NULL_TREE; v = TREE_CHAIN (v))
1600           if (uses_template_parms (TREE_VALUE (v)))
1601             return 1;
1602       }
1603       return 0;
1604
1605       /* constants */
1606     case INTEGER_CST:
1607     case REAL_CST:
1608     case STRING_CST:
1609       return 0;
1610
1611     case ERROR_MARK:
1612       /* Non-error_mark_node ERROR_MARKs are bad things.  */
1613       my_friendly_assert (t == error_mark_node, 274);
1614       /* NOTREACHED */
1615       return 0;
1616
1617     case LOOKUP_EXPR:
1618     case TYPENAME_TYPE:
1619       return 1;
1620
1621     case SCOPE_REF:
1622       return uses_template_parms (TREE_OPERAND (t, 0));
1623
1624     case CONSTRUCTOR:
1625       if (TREE_TYPE (t) && TYPE_PTRMEMFUNC_P (TREE_TYPE (t)))
1626         return uses_template_parms (TYPE_PTRMEMFUNC_FN_TYPE (TREE_TYPE (t)));
1627       return uses_template_parms (TREE_OPERAND (t, 1));
1628
1629     case MODOP_EXPR:
1630     case CAST_EXPR:
1631     case REINTERPRET_CAST_EXPR:
1632     case CONST_CAST_EXPR:
1633     case STATIC_CAST_EXPR:
1634     case DYNAMIC_CAST_EXPR:
1635     case SIZEOF_EXPR:
1636     case ARROW_EXPR:
1637     case DOTSTAR_EXPR:
1638     case TYPEID_EXPR:
1639       return 1;
1640
1641     default:
1642       switch (TREE_CODE_CLASS (TREE_CODE (t)))
1643         {
1644         case '1':
1645         case '2':
1646         case 'e':
1647         case '<':
1648           {
1649             int i;
1650             for (i = tree_code_length[(int) TREE_CODE (t)]; --i >= 0;)
1651               if (uses_template_parms (TREE_OPERAND (t, i)))
1652                 return 1;
1653             return 0;
1654           }
1655         default:
1656           break;
1657         }
1658       sorry ("testing %s for template parms",
1659              tree_code_name [(int) TREE_CODE (t)]);
1660       my_friendly_abort (82);
1661       /* NOTREACHED */
1662       return 0;
1663     }
1664 }
1665
1666 static struct tinst_level *current_tinst_level = 0;
1667 static struct tinst_level *free_tinst_level = 0;
1668 static int tinst_depth = 0;
1669 extern int max_tinst_depth;
1670 #ifdef GATHER_STATISTICS
1671 int depth_reached = 0;
1672 #endif
1673
1674 static int
1675 push_tinst_level (d)
1676      tree d;
1677 {
1678   struct tinst_level *new;
1679
1680   if (tinst_depth >= max_tinst_depth)
1681     {
1682       struct tinst_level *p = current_tinst_level;
1683       int line = lineno;
1684       char *file = input_filename;
1685
1686       error ("template instantiation depth exceeds maximum of %d",
1687              max_tinst_depth);
1688       error (" (use -ftemplate-depth-NN to increase the maximum)");
1689       cp_error ("  instantiating `%D'", d);
1690
1691       for (; p; p = p->next)
1692         {
1693           cp_error ("  instantiated from `%D'", p->decl);
1694           lineno = p->line;
1695           input_filename = p->file;
1696         }
1697       error ("  instantiated from here");
1698
1699       lineno = line;
1700       input_filename = file;
1701
1702       return 0;
1703     }
1704
1705   if (free_tinst_level)
1706     {
1707       new = free_tinst_level;
1708       free_tinst_level = new->next;
1709     }
1710   else
1711     new = (struct tinst_level *) xmalloc (sizeof (struct tinst_level));
1712
1713   new->decl = d;
1714   new->line = lineno;
1715   new->file = input_filename;
1716   new->next = current_tinst_level;
1717   current_tinst_level = new;
1718
1719   ++tinst_depth;
1720 #ifdef GATHER_STATISTICS
1721   if (tinst_depth > depth_reached)
1722     depth_reached = tinst_depth;
1723 #endif
1724
1725   return 1;
1726 }
1727
1728 void
1729 pop_tinst_level ()
1730 {
1731   struct tinst_level *old = current_tinst_level;
1732
1733   current_tinst_level = old->next;
1734   old->next = free_tinst_level;
1735   free_tinst_level = old;
1736   --tinst_depth;
1737 }
1738
1739 struct tinst_level *
1740 tinst_for_decl ()
1741 {
1742   struct tinst_level *p = current_tinst_level;
1743
1744   if (p)
1745     for (; p->next ; p = p->next )
1746       ;
1747   return p;
1748 }
1749
1750 tree
1751 instantiate_class_template (type)
1752      tree type;
1753 {
1754   tree template, template_info, args, pattern, t, *field_chain;
1755
1756   if (type == error_mark_node)
1757     return error_mark_node;
1758
1759   template_info = CLASSTYPE_TEMPLATE_INFO (type);
1760
1761   if (TYPE_BEING_DEFINED (type) || TYPE_SIZE (type))
1762     return type;
1763
1764   template = TI_TEMPLATE (template_info);
1765   my_friendly_assert (TREE_CODE (template) == TEMPLATE_DECL, 279);
1766   args = TI_ARGS (template_info);
1767
1768   t = most_specialized_class
1769     (DECL_TEMPLATE_SPECIALIZATIONS (template), args);
1770
1771   if (t == error_mark_node)
1772     {
1773       char *str = "candidates are:";
1774       cp_error ("ambiguous class template instantiation for `%#T'", type);
1775       for (t = DECL_TEMPLATE_SPECIALIZATIONS (template); t; t = TREE_CHAIN (t))
1776         {
1777           if (get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), args))
1778             {
1779               cp_error_at ("%s %+#T", str, TREE_TYPE (t));
1780               str = "               ";
1781             }
1782         }
1783       TYPE_BEING_DEFINED (type) = 1;
1784       return error_mark_node;
1785     }
1786   else if (t)
1787     pattern = TREE_TYPE (t);
1788   else
1789     pattern = TREE_TYPE (template);
1790
1791   if (TYPE_SIZE (pattern) == NULL_TREE)
1792     return type;
1793
1794   if (t)
1795     args = get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), args);
1796
1797   TYPE_BEING_DEFINED (type) = 1;
1798
1799   if (! push_tinst_level (type))
1800     return type;
1801
1802   maybe_push_to_top_level (uses_template_parms (type));
1803   pushclass (type, 0);
1804
1805   if (flag_external_templates)
1806     {
1807       if (flag_alt_external_templates)
1808         {
1809           CLASSTYPE_INTERFACE_ONLY (type) = interface_only;
1810           SET_CLASSTYPE_INTERFACE_UNKNOWN_X (type, interface_unknown);
1811           CLASSTYPE_VTABLE_NEEDS_WRITING (type)
1812             = ! CLASSTYPE_INTERFACE_ONLY (type)
1813               && CLASSTYPE_INTERFACE_KNOWN (type);
1814         }
1815       else
1816         {
1817           CLASSTYPE_INTERFACE_ONLY (type) = CLASSTYPE_INTERFACE_ONLY (pattern);
1818           SET_CLASSTYPE_INTERFACE_UNKNOWN_X
1819             (type, CLASSTYPE_INTERFACE_UNKNOWN (pattern));
1820           CLASSTYPE_VTABLE_NEEDS_WRITING (type)
1821             = ! CLASSTYPE_INTERFACE_ONLY (type)
1822               && CLASSTYPE_INTERFACE_KNOWN (type);
1823         }
1824     }
1825   else
1826     {
1827       SET_CLASSTYPE_INTERFACE_UNKNOWN (type);
1828       CLASSTYPE_VTABLE_NEEDS_WRITING (type) = 1;
1829     }
1830
1831   TYPE_HAS_CONSTRUCTOR (type) = TYPE_HAS_CONSTRUCTOR (pattern);
1832   TYPE_HAS_DESTRUCTOR (type) = TYPE_HAS_DESTRUCTOR (pattern);
1833   TYPE_HAS_ASSIGNMENT (type) = TYPE_HAS_ASSIGNMENT (pattern);
1834   TYPE_OVERLOADS_CALL_EXPR (type) = TYPE_OVERLOADS_CALL_EXPR (pattern);
1835   TYPE_OVERLOADS_ARRAY_REF (type) = TYPE_OVERLOADS_ARRAY_REF (pattern);
1836   TYPE_OVERLOADS_ARROW (type) = TYPE_OVERLOADS_ARROW (pattern);
1837   TYPE_GETS_NEW (type) = TYPE_GETS_NEW (pattern);
1838   TYPE_GETS_DELETE (type) = TYPE_GETS_DELETE (pattern);
1839   TYPE_VEC_DELETE_TAKES_SIZE (type) = TYPE_VEC_DELETE_TAKES_SIZE (pattern);
1840   TYPE_HAS_ASSIGN_REF (type) = TYPE_HAS_ASSIGN_REF (pattern);
1841   TYPE_HAS_CONST_ASSIGN_REF (type) = TYPE_HAS_CONST_ASSIGN_REF (pattern);
1842   TYPE_HAS_ABSTRACT_ASSIGN_REF (type) = TYPE_HAS_ABSTRACT_ASSIGN_REF (pattern);
1843   TYPE_HAS_INIT_REF (type) = TYPE_HAS_INIT_REF (pattern);
1844   TYPE_HAS_CONST_INIT_REF (type) = TYPE_HAS_CONST_INIT_REF (pattern);
1845   TYPE_GETS_INIT_AGGR (type) = TYPE_GETS_INIT_AGGR (pattern);
1846   TYPE_HAS_DEFAULT_CONSTRUCTOR (type) = TYPE_HAS_DEFAULT_CONSTRUCTOR (pattern);
1847   TYPE_HAS_CONVERSION (type) = TYPE_HAS_CONVERSION (pattern);
1848   TYPE_USES_COMPLEX_INHERITANCE (type)
1849     = TYPE_USES_COMPLEX_INHERITANCE (pattern);
1850   TYPE_USES_MULTIPLE_INHERITANCE (type)
1851     = TYPE_USES_MULTIPLE_INHERITANCE (pattern);
1852   TYPE_USES_VIRTUAL_BASECLASSES (type)
1853     = TYPE_USES_VIRTUAL_BASECLASSES (pattern);
1854   TYPE_PACKED (type) = TYPE_PACKED (pattern);
1855   TYPE_ALIGN (type) = TYPE_ALIGN (pattern);
1856
1857   {
1858     tree binfo = TYPE_BINFO (type);
1859     tree pbases = TYPE_BINFO_BASETYPES (pattern);
1860
1861     if (pbases)
1862       {
1863         tree bases;
1864         int i;
1865         int len = TREE_VEC_LENGTH (pbases);
1866         bases = make_tree_vec (len);
1867         for (i = 0; i < len; ++i)
1868           {
1869             tree elt;
1870
1871             TREE_VEC_ELT (bases, i) = elt
1872               = tsubst (TREE_VEC_ELT (pbases, i), args,
1873                         TREE_VEC_LENGTH (args), NULL_TREE);
1874             BINFO_INHERITANCE_CHAIN (elt) = binfo;
1875
1876             if (! IS_AGGR_TYPE (TREE_TYPE (elt)))
1877               cp_error
1878                 ("base type `%T' of `%T' fails to be a struct or class type",
1879                  TREE_TYPE (elt), type);
1880             else if (! uses_template_parms (type)
1881                      && (TYPE_SIZE (complete_type (TREE_TYPE (elt)))
1882                          == NULL_TREE))
1883               cp_error ("base class `%T' of `%T' has incomplete type",
1884                         TREE_TYPE (elt), type);
1885           }
1886         /* Don't initialize this until the vector is filled out, or
1887            lookups will crash.  */
1888         BINFO_BASETYPES (binfo) = bases;
1889       }
1890   }
1891
1892   CLASSTYPE_LOCAL_TYPEDECLS (type) = CLASSTYPE_LOCAL_TYPEDECLS (pattern);
1893
1894   field_chain = &TYPE_FIELDS (type);
1895
1896   for (t = CLASSTYPE_TAGS (pattern); t; t = TREE_CHAIN (t))
1897     {
1898       tree name = TREE_PURPOSE (t);
1899       tree tag = TREE_VALUE (t);
1900
1901       /* These will add themselves to CLASSTYPE_TAGS for the new type.  */
1902       if (TREE_CODE (tag) == ENUMERAL_TYPE)
1903         {
1904           tree e, newtag = tsubst_enum (tag, args,
1905                                         TREE_VEC_LENGTH (args), field_chain);
1906
1907           while (*field_chain)
1908             {
1909               DECL_FIELD_CONTEXT (*field_chain) = type;
1910               field_chain = &TREE_CHAIN (*field_chain);
1911             }
1912         }
1913       else
1914         tsubst (tag, args,
1915                 TREE_VEC_LENGTH (args), NULL_TREE);
1916     }
1917
1918   /* Don't replace enum constants here.  */
1919   for (t = TYPE_FIELDS (pattern); t; t = TREE_CHAIN (t))
1920     if (TREE_CODE (t) != CONST_DECL)
1921       {
1922         tree r = tsubst (t, args,
1923                          TREE_VEC_LENGTH (args), NULL_TREE);
1924         if (TREE_CODE (r) == VAR_DECL)
1925           {
1926             if (! uses_template_parms (r))
1927               pending_statics = perm_tree_cons (NULL_TREE, r, pending_statics);
1928             /* Perhaps I should do more of grokfield here.  */
1929             start_decl_1 (r);
1930             DECL_IN_AGGR_P (r) = 1;
1931             DECL_EXTERNAL (r) = 1;
1932             cp_finish_decl (r, DECL_INITIAL (r), NULL_TREE, 0, 0);
1933           }
1934
1935         *field_chain = r;
1936         field_chain = &TREE_CHAIN (r);
1937       }
1938
1939   TYPE_METHODS (type) = tsubst_chain (TYPE_METHODS (pattern), args);
1940   for (t = TYPE_METHODS (type); t; t = TREE_CHAIN (t))
1941     {
1942       if (DECL_CONSTRUCTOR_P (t))
1943         grok_ctor_properties (type, t);
1944       else if (IDENTIFIER_OPNAME_P (DECL_NAME (t)))
1945         grok_op_properties (t, DECL_VIRTUAL_P (t), 0);
1946     }
1947
1948   DECL_FRIENDLIST (TYPE_MAIN_DECL (type))
1949     = tsubst (DECL_FRIENDLIST (TYPE_MAIN_DECL (pattern)),
1950               args, TREE_VEC_LENGTH (args), NULL_TREE);
1951
1952   {
1953     tree d = CLASSTYPE_FRIEND_CLASSES (type)
1954       = tsubst (CLASSTYPE_FRIEND_CLASSES (pattern), args,
1955                 TREE_VEC_LENGTH (args), NULL_TREE);
1956
1957     /* This does injection for friend classes.  */
1958     for (; d; d = TREE_CHAIN (d))
1959       TREE_VALUE (d) = xref_tag_from_type (TREE_VALUE (d), NULL_TREE, 1);
1960
1961     d = tsubst (DECL_TEMPLATE_INJECT (template), args,
1962                 TREE_VEC_LENGTH (args), NULL_TREE);
1963
1964     for (; d; d = TREE_CHAIN (d))
1965       {
1966         tree t = TREE_VALUE (d);
1967
1968         if (TREE_CODE (t) == TYPE_DECL)
1969           /* Already injected.  */;
1970         else
1971           pushdecl (t);
1972       }
1973   }
1974
1975   if (! uses_template_parms (type))
1976     {
1977       tree tmp;
1978       for (tmp = TYPE_FIELDS (type); tmp; tmp = TREE_CHAIN (tmp))
1979         if (TREE_CODE (tmp) == FIELD_DECL)
1980           {
1981             TREE_TYPE (tmp) = complete_type (TREE_TYPE (tmp));
1982             require_complete_type (tmp);
1983           }
1984
1985       type = finish_struct_1 (type, 0);
1986       CLASSTYPE_GOT_SEMICOLON (type) = 1;
1987
1988       repo_template_used (type);
1989       if (at_eof && TYPE_BINFO_VTABLE (type) != NULL_TREE)
1990         finish_prevtable_vardecl (NULL, TYPE_BINFO_VTABLE (type));
1991     }
1992   else
1993     {
1994       TYPE_SIZE (type) = integer_zero_node;
1995       CLASSTYPE_METHOD_VEC (type)
1996         = finish_struct_methods (type, TYPE_METHODS (type), 1);
1997     }
1998
1999   TYPE_BEING_DEFINED (type) = 0;
2000   popclass (0);
2001
2002   pop_from_top_level ();
2003   pop_tinst_level ();
2004
2005   return type;
2006 }
2007
2008 static int
2009 list_eq (t1, t2)
2010      tree t1, t2;
2011 {
2012   if (t1 == NULL_TREE)
2013     return t2 == NULL_TREE;
2014   if (t2 == NULL_TREE)
2015     return 0;
2016   /* Don't care if one declares its arg const and the other doesn't -- the
2017      main variant of the arg type is all that matters.  */
2018   if (TYPE_MAIN_VARIANT (TREE_VALUE (t1))
2019       != TYPE_MAIN_VARIANT (TREE_VALUE (t2)))
2020     return 0;
2021   return list_eq (TREE_CHAIN (t1), TREE_CHAIN (t2));
2022 }
2023
2024 tree
2025 lookup_nested_type_by_name (ctype, name)
2026         tree ctype, name;
2027 {
2028   tree t;
2029
2030   complete_type (ctype);
2031
2032   for (t = CLASSTYPE_TAGS (ctype); t; t = TREE_CHAIN (t))
2033     {
2034       if (name == TREE_PURPOSE (t)
2035           /* this catches typedef enum { foo } bar; */
2036           || name == TYPE_IDENTIFIER (TREE_VALUE (t)))
2037         return TREE_VALUE (t);
2038     }
2039   return NULL_TREE;
2040 }
2041
2042 /* If arg is a non-type template parameter that does not depend on template
2043    arguments, fold it like we weren't in the body of a template.  */
2044
2045 static tree
2046 maybe_fold_nontype_arg (arg)
2047      tree arg;
2048 {
2049   if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't'
2050       && !uses_template_parms (arg))
2051     {
2052       /* Sometimes, one of the args was an expression involving a
2053          template constant parameter, like N - 1.  Now that we've
2054          tsubst'd, we might have something like 2 - 1.  This will
2055          confuse lookup_template_class, so we do constant folding
2056          here.  We have to unset processing_template_decl, to
2057          fool build_expr_from_tree() into building an actual
2058          tree.  */
2059
2060       int saved_processing_template_decl = processing_template_decl;
2061       processing_template_decl = 0;
2062       arg = fold (build_expr_from_tree (arg));
2063       processing_template_decl = saved_processing_template_decl;
2064     }
2065   return arg;
2066 }
2067
2068 /* Take the tree structure T and replace template parameters used therein
2069    with the argument vector ARGS.  NARGS is the number of args; should
2070    be removed.  IN_DECL is an associated decl for diagnostics.
2071
2072    tsubst is used for dealing with types, decls and the like; for
2073    expressions, use tsubst_expr or tsubst_copy.  */
2074
2075 tree
2076 tsubst (t, args, nargs, in_decl)
2077      tree t, args;
2078      int nargs;
2079      tree in_decl;
2080 {
2081   tree type;
2082
2083   if (t == NULL_TREE || t == error_mark_node
2084       || t == integer_type_node
2085       || t == void_type_node
2086       || t == char_type_node)
2087     return t;
2088
2089   type = TREE_TYPE (t);
2090   if (type == unknown_type_node)
2091     my_friendly_abort (42);
2092   if (type && TREE_CODE (t) != FUNCTION_DECL
2093       && TREE_CODE (t) != TYPENAME_TYPE)
2094     type = tsubst (type, args, nargs, in_decl);
2095
2096   switch (TREE_CODE (t))
2097     {
2098     case RECORD_TYPE:
2099       if (TYPE_PTRMEMFUNC_P (t))
2100         {
2101           tree r = build_ptrmemfunc_type
2102             (tsubst (TYPE_PTRMEMFUNC_FN_TYPE (t), args, nargs, in_decl));
2103           return cp_build_type_variant (r, TYPE_READONLY (t),
2104                                         TYPE_VOLATILE (t));
2105         }
2106
2107       /* else fall through */
2108     case UNION_TYPE:
2109       if (uses_template_parms (t))
2110         {
2111           tree argvec = tsubst (CLASSTYPE_TI_ARGS (t), args, nargs, in_decl);
2112           tree r = lookup_template_class (t, argvec, in_decl);
2113           return cp_build_type_variant (r, TYPE_READONLY (t),
2114                                         TYPE_VOLATILE (t));
2115         }
2116
2117       /* else fall through */
2118     case ERROR_MARK:
2119     case IDENTIFIER_NODE:
2120     case OP_IDENTIFIER:
2121     case VOID_TYPE:
2122     case REAL_TYPE:
2123     case COMPLEX_TYPE:
2124     case BOOLEAN_TYPE:
2125     case INTEGER_CST:
2126     case REAL_CST:
2127     case STRING_CST:
2128       return t;
2129
2130     case ENUMERAL_TYPE:
2131       {
2132         tree ctx = tsubst (TYPE_CONTEXT (t), args, nargs, in_decl);
2133         if (ctx == NULL_TREE)
2134           return t;
2135         else if (ctx == current_function_decl)
2136           return lookup_name (TYPE_IDENTIFIER (t), 1);
2137         else
2138           return lookup_nested_type_by_name (ctx, TYPE_IDENTIFIER (t));
2139       }
2140
2141     case INTEGER_TYPE:
2142       if (t == integer_type_node)
2143         return t;
2144
2145       if (TREE_CODE (TYPE_MIN_VALUE (t)) == INTEGER_CST
2146           && TREE_CODE (TYPE_MAX_VALUE (t)) == INTEGER_CST)
2147         return t;
2148
2149       {
2150         tree max = TREE_OPERAND (TYPE_MAX_VALUE (t), 0);
2151         max = tsubst_expr (max, args, nargs, in_decl);
2152         if (processing_template_decl)
2153           {
2154             tree itype = make_node (INTEGER_TYPE);
2155             TYPE_MIN_VALUE (itype) = size_zero_node;
2156             TYPE_MAX_VALUE (itype) = build_min (MINUS_EXPR, sizetype, max,
2157                                                 integer_one_node);
2158             return itype;
2159           }
2160
2161         max = fold (build_binary_op (MINUS_EXPR, max, integer_one_node, 1));
2162         return build_index_2_type (size_zero_node, max);
2163       }
2164
2165     case TEMPLATE_TYPE_PARM:
2166     case TEMPLATE_CONST_PARM:
2167       {
2168         int idx;
2169         int level;
2170
2171         if (TREE_CODE (t) == TEMPLATE_TYPE_PARM)
2172           {
2173             idx = TEMPLATE_TYPE_IDX (t);
2174             level = TEMPLATE_TYPE_LEVEL (t);
2175           }
2176         else
2177           {
2178             idx = TEMPLATE_CONST_IDX (t);
2179             level = TEMPLATE_CONST_LEVEL (t);
2180           }
2181
2182         if (TREE_VEC_LENGTH (args) > 0)
2183           {
2184             tree arg = NULL_TREE;
2185
2186             if (TREE_CODE (TREE_VEC_ELT (args, 0)) == TREE_VEC)
2187               {
2188                 if (TREE_VEC_LENGTH (args) >= level - 1)
2189                   arg = TREE_VEC_ELT
2190                     (TREE_VEC_ELT (args, level - 1), idx);
2191               }
2192             else if (level == 1)
2193               arg = TREE_VEC_ELT (args, idx);
2194
2195             if (arg != NULL_TREE)
2196               {
2197                 if (TREE_CODE (t) == TEMPLATE_TYPE_PARM)
2198                   return cp_build_type_variant
2199                     (arg, TYPE_READONLY (arg) || TYPE_READONLY (t),
2200                      TYPE_VOLATILE (arg) || TYPE_VOLATILE (t));
2201                 else
2202                   return arg;
2203               }
2204           }
2205
2206         /* If we get here, we must have been looking at a parm for a
2207            more deeply nested template.  */
2208         my_friendly_assert((TREE_CODE (t) == TEMPLATE_CONST_PARM
2209                             && TEMPLATE_CONST_LEVEL (t) > 1)
2210                            || (TREE_CODE (t) == TEMPLATE_TYPE_PARM
2211                                && TEMPLATE_TYPE_LEVEL (t) > 1),
2212                            0);
2213         return t;
2214       }
2215
2216     case TEMPLATE_DECL:
2217       {
2218         /* We can get here when processing a member template function
2219            of a template class.  */
2220         tree tmpl;
2221         tree decl = DECL_TEMPLATE_RESULT (t);
2222         tree new_decl;
2223         tree parms;
2224         tree spec;
2225         int i;
2226
2227         /* We might already have an instance of this template. */
2228         tree instances = DECL_TEMPLATE_INSTANTIATIONS (t);
2229         tree ctx = tsubst (DECL_CLASS_CONTEXT (t), args, nargs, in_decl);
2230
2231         for (; instances; instances = TREE_CHAIN (instances))
2232           if (DECL_CLASS_CONTEXT (TREE_VALUE (instances)) == ctx)
2233             return TREE_VALUE (instances);
2234
2235         /* Make a new template decl.  It will be similar to the
2236            original, but will record the current template arguments.
2237            We also create a new function declaration, which is just
2238            like the old one, but points to this new template, rather
2239            than the old one.  */
2240         tmpl = copy_node (t);
2241         copy_lang_decl (tmpl);
2242         my_friendly_assert (DECL_LANG_SPECIFIC (tmpl) != 0, 0);
2243         DECL_CHAIN (tmpl) = NULL_TREE;
2244         TREE_CHAIN (tmpl) = NULL_TREE;
2245         DECL_TEMPLATE_INFO (tmpl) = build_tree_list (t, args);
2246         new_decl = tsubst (decl, args, nargs, in_decl);
2247         DECL_RESULT (tmpl) = new_decl;
2248         DECL_TI_TEMPLATE (new_decl) = tmpl;
2249         TREE_TYPE (tmpl) = TREE_TYPE (new_decl);
2250         DECL_TEMPLATE_INSTANTIATIONS (tmpl) = NULL_TREE;
2251         SET_DECL_IMPLICIT_INSTANTIATION (tmpl);
2252
2253         /* The template parameters for this new template are all the
2254            template parameters for the old template, except the
2255            outermost level of parameters. */
2256         DECL_TEMPLATE_PARMS (tmpl)
2257           = copy_node (DECL_TEMPLATE_PARMS (tmpl));
2258         for (parms = DECL_TEMPLATE_PARMS (tmpl);
2259              TREE_CHAIN (parms) != NULL_TREE;
2260              parms = TREE_CHAIN (parms))
2261           TREE_CHAIN (parms) = copy_node (TREE_CHAIN (parms));
2262
2263         /* Record this partial instantiation. */
2264         DECL_TEMPLATE_INSTANTIATIONS (t)
2265           = perm_tree_cons (NULL_TREE, tmpl,
2266                             DECL_TEMPLATE_INSTANTIATIONS (t));
2267
2268         DECL_TEMPLATE_SPECIALIZATIONS (tmpl) = NULL_TREE;
2269         return tmpl;
2270       }
2271
2272     case FUNCTION_DECL:
2273       {
2274         tree r = NULL_TREE;
2275         tree ctx;
2276
2277         int member;
2278
2279         if (DECL_CONTEXT (t) != NULL_TREE
2280             && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't')
2281           {
2282             if (DECL_NAME (t) == constructor_name (DECL_CONTEXT (t)))
2283               member = 2;
2284             else
2285               member = 1;
2286             ctx = tsubst (DECL_CLASS_CONTEXT (t), args, nargs, t);
2287             type = tsubst (type, args, nargs, in_decl);
2288           }
2289         else
2290           {
2291             member = 0;
2292             ctx = NULL_TREE;
2293             type = tsubst (type, args, nargs, in_decl);
2294           }
2295
2296         /* Do we already have this instantiation?  */
2297         if (DECL_TEMPLATE_INFO (t) != NULL_TREE)
2298           {
2299             tree tmpl = DECL_TI_TEMPLATE (t);
2300             tree decls = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
2301
2302             for (; decls; decls = TREE_CHAIN (decls))
2303               if (TREE_TYPE (TREE_VALUE (decls)) == type
2304                   && DECL_CLASS_CONTEXT (TREE_VALUE (decls)) == ctx
2305                   && comp_template_args (TREE_PURPOSE (decls), args))
2306                 return TREE_VALUE (decls);
2307           }
2308
2309         /* We do NOT check for matching decls pushed separately at this
2310            point, as they may not represent instantiations of this
2311            template, and in any case are considered separate under the
2312            discrete model.  Instead, see add_maybe_template.  */
2313
2314         r = copy_node (t);
2315         copy_lang_decl (r);
2316         TREE_TYPE (r) = type;
2317
2318         DECL_CONTEXT (r)
2319           = tsubst (DECL_CONTEXT (t), args, nargs, t);
2320         DECL_CLASS_CONTEXT (r) = ctx;
2321
2322         if (member && !strncmp (OPERATOR_TYPENAME_FORMAT,
2323                                 IDENTIFIER_POINTER (DECL_NAME (r)),
2324                                 sizeof (OPERATOR_TYPENAME_FORMAT) - 1))
2325           {
2326             /* Type-conversion operator.  Reconstruct the name, in
2327                case it's the name of one of the template's parameters.  */
2328             DECL_NAME (r) = build_typename_overload (TREE_TYPE (type));
2329           }
2330
2331         if (DESTRUCTOR_NAME_P (DECL_ASSEMBLER_NAME (t)))
2332           {
2333             char *buf, *dbuf = build_overload_name (ctx, 1, 1);
2334             int len = sizeof (DESTRUCTOR_DECL_PREFIX) - 1;
2335             buf = (char *) alloca (strlen (dbuf)
2336                                    + sizeof (DESTRUCTOR_DECL_PREFIX));
2337             bcopy (DESTRUCTOR_DECL_PREFIX, buf, len);
2338             buf[len] = '\0';
2339             strcat (buf, dbuf);
2340             DECL_ASSEMBLER_NAME (r) = get_identifier (buf);
2341           }
2342         else
2343           {
2344             /* Instantiations of template functions must be mangled
2345                specially, in order to conform to 14.5.5.1
2346                [temp.over.link].  We use in_decl below rather than
2347                DECL_TI_TEMPLATE (r) because the latter is set to
2348                NULL_TREE in instantiate_decl.  */
2349             tree tmpl;
2350             tree arg_types;
2351
2352             if (DECL_TEMPLATE_INFO (r))
2353               tmpl = DECL_TI_TEMPLATE (r);
2354             else
2355               tmpl = in_decl;
2356
2357             /* tmpl will be NULL if this is a specialization of a
2358                member template of a template class.  */
2359             if (name_mangling_version < 1
2360                 || tmpl == NULL_TREE
2361                 || (member && !is_member_template (tmpl)
2362                     && !DECL_TEMPLATE_INFO (tmpl)))
2363               {
2364                 arg_types = TYPE_ARG_TYPES (type);
2365                 if (member && TREE_CODE (type) == FUNCTION_TYPE)
2366                   arg_types = hash_tree_chain
2367                     (build_pointer_type (DECL_CONTEXT (r)),
2368                      arg_types);
2369
2370                 DECL_ASSEMBLER_NAME (r)
2371                   = build_decl_overload (DECL_NAME (r), arg_types,
2372                                          member);
2373               }
2374             else
2375               {
2376                 /* We pass the outermost template parameters to
2377                    build_template_decl_overload since the innermost
2378                    template parameters are still just template
2379                    parameters; there are no corresponding subsitution
2380                    arguments.  */
2381                 /* FIXME The messed up thing here is that we get here with
2382                    full args and only one level of parms.  This is necessary
2383                    because when we partially instantiate a member template,
2384                    even though there's really only one level of parms left
2385                    we re-use the parms from the original template, which
2386                    have level 2.  When this is fixed we can remove the
2387                    add_to_template_args from instantiate_template.  */
2388                 tree tparms = DECL_TEMPLATE_PARMS (tmpl);
2389
2390                 while (tparms && TREE_CHAIN (tparms) != NULL_TREE)
2391                   tparms = TREE_CHAIN (tparms);
2392
2393                 my_friendly_assert (tparms != NULL_TREE
2394                                     && TREE_CODE (tparms) == TREE_LIST,
2395                                     0);
2396                 tparms = TREE_VALUE (tparms);
2397
2398                 arg_types = TYPE_ARG_TYPES (TREE_TYPE (tmpl));
2399                 if (member && TREE_CODE (type) == FUNCTION_TYPE)
2400                   arg_types = hash_tree_chain
2401                     (build_pointer_type (DECL_CONTEXT (r)),
2402                      arg_types);
2403
2404                 DECL_ASSEMBLER_NAME (r)
2405                   = build_template_decl_overload
2406                   (DECL_NAME (r), arg_types,
2407                    TREE_TYPE (TREE_TYPE (tmpl)),
2408                    tparms,
2409                    TREE_CODE (TREE_VEC_ELT (args, 0)) == TREE_VEC
2410                    ? TREE_VEC_ELT (args, TREE_VEC_LENGTH (args) - 1) :
2411                    args,
2412                    member);
2413               }
2414           }
2415         DECL_RTL (r) = 0;
2416         make_decl_rtl (r, NULL_PTR, 1);
2417
2418         DECL_ARGUMENTS (r) = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
2419         DECL_MAIN_VARIANT (r) = r;
2420         DECL_RESULT (r) = NULL_TREE;
2421         DECL_INITIAL (r) = NULL_TREE;
2422
2423         TREE_STATIC (r) = 0;
2424         TREE_PUBLIC (r) = 1;
2425         DECL_EXTERNAL (r) = 1;
2426         DECL_INTERFACE_KNOWN (r) = 0;
2427         DECL_DEFER_OUTPUT (r) = 0;
2428         TREE_CHAIN (r) = NULL_TREE;
2429         DECL_CHAIN (r) = NULL_TREE;
2430
2431         if (IDENTIFIER_OPNAME_P (DECL_NAME (r)))
2432           grok_op_properties (r, DECL_VIRTUAL_P (r), DECL_FRIEND_P (r));
2433
2434         /* Look for matching decls for the moment.  */
2435         if (! member && ! flag_ansi_overloading)
2436           {
2437             tree decls = lookup_name_nonclass (DECL_NAME (t));
2438             tree d = NULL_TREE;
2439
2440             if (decls == NULL_TREE)
2441               /* no match */;
2442             else if (is_overloaded_fn (decls))
2443               for (decls = get_first_fn (decls); decls;
2444                    decls = DECL_CHAIN (decls))
2445                 {
2446                   if (TREE_CODE (decls) == FUNCTION_DECL
2447                       && TREE_TYPE (decls) == type)
2448                     {
2449                       d = decls;
2450                       break;
2451                     }
2452                 }
2453
2454             if (d)
2455               {
2456                 int dcl_only = ! DECL_INITIAL (d);
2457                 if (dcl_only)
2458                   DECL_INITIAL (r) = error_mark_node;
2459                 duplicate_decls (r, d);
2460                 r = d;
2461                 if (dcl_only)
2462                   DECL_INITIAL (r) = 0;
2463               }
2464           }
2465
2466         if (DECL_TEMPLATE_INFO (t) != NULL_TREE)
2467           {
2468             tree tmpl = DECL_TI_TEMPLATE (t);
2469             tree *declsp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
2470             tree argvec = tsubst (DECL_TI_ARGS (t), args, nargs, in_decl);
2471
2472             if (DECL_TEMPLATE_INFO (tmpl) && DECL_TI_ARGS (tmpl))
2473               argvec = add_to_template_args (DECL_TI_ARGS (tmpl), argvec);
2474
2475             DECL_TEMPLATE_INFO (r) = perm_tree_cons (tmpl, argvec, NULL_TREE);
2476             *declsp = perm_tree_cons (argvec, r, *declsp);
2477
2478             /* If we have a preexisting version of this function, don't expand
2479                the template version, use the other instead.  */
2480             if (TREE_STATIC (r) || DECL_TEMPLATE_SPECIALIZATION (r))
2481               SET_DECL_TEMPLATE_SPECIALIZATION (r);
2482             else
2483               SET_DECL_IMPLICIT_INSTANTIATION (r);
2484
2485           }
2486
2487         /* Like grokfndecl.  If we don't do this, pushdecl will mess up our
2488            TREE_CHAIN because it doesn't find a previous decl.  Sigh.  */
2489         if (member
2490             && IDENTIFIER_GLOBAL_VALUE (DECL_ASSEMBLER_NAME (r)) == NULL_TREE)
2491           IDENTIFIER_GLOBAL_VALUE (DECL_ASSEMBLER_NAME (r)) = r;
2492
2493         return r;
2494       }
2495
2496     case PARM_DECL:
2497       {
2498         tree r = copy_node (t);
2499         TREE_TYPE (r) = type;
2500         DECL_INITIAL (r) = TREE_TYPE (r);
2501         DECL_CONTEXT (r) = NULL_TREE;
2502 #ifdef PROMOTE_PROTOTYPES
2503         if ((TREE_CODE (type) == INTEGER_TYPE
2504              || TREE_CODE (type) == ENUMERAL_TYPE)
2505             && TYPE_PRECISION (type) < TYPE_PRECISION (integer_type_node))
2506           DECL_ARG_TYPE (r) = integer_type_node;
2507 #endif
2508         if (TREE_CHAIN (t))
2509           TREE_CHAIN (r) = tsubst (TREE_CHAIN (t), args, nargs, TREE_CHAIN (t));
2510         return r;
2511       }
2512
2513     case FIELD_DECL:
2514       {
2515         tree r = copy_node (t);
2516         TREE_TYPE (r) = type;
2517         copy_lang_decl (r);
2518 #if 0
2519         DECL_FIELD_CONTEXT (r) = tsubst (DECL_FIELD_CONTEXT (t), args, nargs, in_decl);
2520 #endif
2521         DECL_INITIAL (r) = tsubst_expr (DECL_INITIAL (t), args, nargs, in_decl);
2522         TREE_CHAIN (r) = NULL_TREE;
2523         return r;
2524       }
2525
2526     case USING_DECL:
2527       {
2528         tree r = copy_node (t);
2529         DECL_INITIAL (r)
2530           = tsubst_copy (DECL_INITIAL (t), args, nargs, in_decl);
2531         TREE_CHAIN (r) = NULL_TREE;
2532         return r;
2533       }
2534
2535     case VAR_DECL:
2536       {
2537         tree r;
2538         tree ctx = tsubst_copy (DECL_CONTEXT (t), args, nargs, in_decl);
2539
2540         /* Do we already have this instantiation?  */
2541         if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
2542           {
2543             tree tmpl = DECL_TI_TEMPLATE (t);
2544             tree decls = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
2545
2546             for (; decls; decls = TREE_CHAIN (decls))
2547               if (DECL_CONTEXT (TREE_VALUE (decls)) == ctx)
2548                 return TREE_VALUE (decls);
2549           }
2550
2551         r = copy_node (t);
2552         TREE_TYPE (r) = type;
2553         DECL_CONTEXT (r) = ctx;
2554         if (TREE_STATIC (r))
2555           DECL_ASSEMBLER_NAME (r)
2556             = build_static_name (DECL_CONTEXT (r), DECL_NAME (r));
2557
2558         /* Don't try to expand the initializer until someone tries to use
2559            this variable; otherwise we run into circular dependencies.  */
2560         DECL_INITIAL (r) = NULL_TREE;
2561
2562         DECL_RTL (r) = 0;
2563         DECL_SIZE (r) = 0;
2564
2565         if (DECL_LANG_SPECIFIC (r))
2566           {
2567             copy_lang_decl (r);
2568             DECL_CLASS_CONTEXT (r) = DECL_CONTEXT (r);
2569           }
2570
2571         if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
2572           {
2573             tree tmpl = DECL_TI_TEMPLATE (t);
2574             tree *declsp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
2575             tree argvec = tsubst (DECL_TI_ARGS (t), args, nargs, in_decl);
2576
2577             DECL_TEMPLATE_INFO (r) = perm_tree_cons (tmpl, argvec, NULL_TREE);
2578             *declsp = perm_tree_cons (argvec, r, *declsp);
2579             SET_DECL_IMPLICIT_INSTANTIATION (r);
2580           }
2581         TREE_CHAIN (r) = NULL_TREE;
2582         return r;
2583       }
2584
2585     case TYPE_DECL:
2586       if (t == TYPE_NAME (TREE_TYPE (t)))
2587         return TYPE_NAME (type);
2588
2589       {
2590         tree r = copy_node (t);
2591         TREE_TYPE (r) = type;
2592         DECL_CONTEXT (r) = current_class_type;
2593         TREE_CHAIN (r) = NULL_TREE;
2594         return r;
2595       }
2596
2597     case TREE_LIST:
2598       {
2599         tree purpose, value, chain, result;
2600         int via_public, via_virtual, via_protected;
2601
2602         if (t == void_list_node)
2603           return t;
2604
2605         via_public = TREE_VIA_PUBLIC (t);
2606         via_protected = TREE_VIA_PROTECTED (t);
2607         via_virtual = TREE_VIA_VIRTUAL (t);
2608
2609         purpose = TREE_PURPOSE (t);
2610         if (purpose)
2611           purpose = tsubst (purpose, args, nargs, in_decl);
2612         value = TREE_VALUE (t);
2613         if (value)
2614           value = tsubst (value, args, nargs, in_decl);
2615         chain = TREE_CHAIN (t);
2616         if (chain && chain != void_type_node)
2617           chain = tsubst (chain, args, nargs, in_decl);
2618         if (purpose == TREE_PURPOSE (t)
2619             && value == TREE_VALUE (t)
2620             && chain == TREE_CHAIN (t))
2621           return t;
2622         result = hash_tree_cons (via_public, via_virtual, via_protected,
2623                                  purpose, value, chain);
2624         TREE_PARMLIST (result) = TREE_PARMLIST (t);
2625         return result;
2626       }
2627     case TREE_VEC:
2628       if (type != NULL_TREE)
2629         {
2630           /* A binfo node.  */
2631
2632           t = copy_node (t);
2633
2634           if (type == TREE_TYPE (t))
2635             return t;
2636
2637           TREE_TYPE (t) = complete_type (type);
2638           if (IS_AGGR_TYPE (type))
2639             {
2640               BINFO_VTABLE (t) = TYPE_BINFO_VTABLE (type);
2641               BINFO_VIRTUALS (t) = TYPE_BINFO_VIRTUALS (type);
2642               if (TYPE_BINFO_BASETYPES (type) != NULL_TREE)
2643                 BINFO_BASETYPES (t) = copy_node (TYPE_BINFO_BASETYPES (type));
2644             }
2645           return t;
2646         }
2647
2648       /* Otherwise, a vector of template arguments.  */
2649       {
2650         int len = TREE_VEC_LENGTH (t), need_new = 0, i;
2651         tree *elts = (tree *) alloca (len * sizeof (tree));
2652
2653         bzero ((char *) elts, len * sizeof (tree));
2654
2655         for (i = 0; i < len; i++)
2656           {
2657             elts[i] = maybe_fold_nontype_arg
2658               (tsubst_expr (TREE_VEC_ELT (t, i), args, nargs, in_decl));
2659
2660             if (elts[i] != TREE_VEC_ELT (t, i))
2661               need_new = 1;
2662           }
2663
2664         if (!need_new)
2665           return t;
2666
2667         t = make_tree_vec (len);
2668         for (i = 0; i < len; i++)
2669           TREE_VEC_ELT (t, i) = elts[i];
2670
2671         return t;
2672       }
2673     case POINTER_TYPE:
2674     case REFERENCE_TYPE:
2675       {
2676         tree r;
2677         enum tree_code code;
2678         if (type == TREE_TYPE (t))
2679           return t;
2680
2681         code = TREE_CODE (t);
2682         if (code == POINTER_TYPE)
2683           r = build_pointer_type (type);
2684         else
2685           r = build_reference_type (type);
2686         r = cp_build_type_variant (r, TYPE_READONLY (t), TYPE_VOLATILE (t));
2687         /* Will this ever be needed for TYPE_..._TO values?  */
2688         layout_type (r);
2689         return r;
2690       }
2691     case OFFSET_TYPE:
2692       return build_offset_type
2693         (tsubst (TYPE_OFFSET_BASETYPE (t), args, nargs, in_decl), type);
2694     case FUNCTION_TYPE:
2695     case METHOD_TYPE:
2696       {
2697         tree values = TYPE_ARG_TYPES (t);
2698         tree context = TYPE_CONTEXT (t);
2699         tree raises = TYPE_RAISES_EXCEPTIONS (t);
2700         tree fntype;
2701
2702         /* Don't bother recursing if we know it won't change anything.  */
2703         if (values != void_list_node)
2704           {
2705             /* This should probably be rewritten to use hash_tree_cons for
2706                the memory savings.  */
2707             tree first = NULL_TREE;
2708             tree last;
2709
2710             for (; values && values != void_list_node;
2711                  values = TREE_CHAIN (values))
2712               {
2713                 tree value = TYPE_MAIN_VARIANT (type_decays_to
2714                   (tsubst (TREE_VALUE (values), args, nargs, in_decl)));
2715                 /* Don't instantiate default args unless they are used.
2716                    Handle it in build_over_call instead.  */
2717                 tree purpose = TREE_PURPOSE (values);
2718                 tree x = build_tree_list (purpose, value);
2719
2720                 if (first)
2721                   TREE_CHAIN (last) = x;
2722                 else
2723                   first = x;
2724                 last = x;
2725               }
2726
2727             if (values == void_list_node)
2728               TREE_CHAIN (last) = void_list_node;
2729
2730             values = first;
2731           }
2732         if (context)
2733           context = tsubst (context, args, nargs, in_decl);
2734         /* Could also optimize cases where return value and
2735            values have common elements (e.g., T min(const &T, const T&).  */
2736
2737         /* If the above parameters haven't changed, just return the type.  */
2738         if (type == TREE_TYPE (t)
2739             && values == TYPE_VALUES (t)
2740             && context == TYPE_CONTEXT (t))
2741           return t;
2742
2743         /* Construct a new type node and return it.  */
2744         if (TREE_CODE (t) == FUNCTION_TYPE
2745             && context == NULL_TREE)
2746           {
2747             fntype = build_function_type (type, values);
2748           }
2749         else if (context == NULL_TREE)
2750           {
2751             tree base = tsubst (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (t))),
2752                                 args, nargs, in_decl);
2753             fntype = build_cplus_method_type (base, type,
2754                                               TREE_CHAIN (values));
2755           }
2756         else
2757           {
2758             fntype = make_node (TREE_CODE (t));
2759             TREE_TYPE (fntype) = type;
2760             TYPE_CONTEXT (fntype) = context;
2761             TYPE_VALUES (fntype) = values;
2762             TYPE_SIZE (fntype) = TYPE_SIZE (t);
2763             TYPE_ALIGN (fntype) = TYPE_ALIGN (t);
2764             TYPE_MODE (fntype) = TYPE_MODE (t);
2765             if (TYPE_METHOD_BASETYPE (t))
2766               TYPE_METHOD_BASETYPE (fntype) = tsubst (TYPE_METHOD_BASETYPE (t),
2767                                                       args, nargs, in_decl);
2768             /* Need to generate hash value.  */
2769             my_friendly_abort (84);
2770           }
2771         fntype = build_type_variant (fntype,
2772                                      TYPE_READONLY (t),
2773                                      TYPE_VOLATILE (t));
2774         if (raises)
2775           {
2776             raises = tsubst (raises, args, nargs, in_decl);
2777             fntype = build_exception_variant (fntype, raises);
2778           }
2779         return fntype;
2780       }
2781     case ARRAY_TYPE:
2782       {
2783         tree domain = tsubst (TYPE_DOMAIN (t), args, nargs, in_decl);
2784         tree r;
2785         if (type == TREE_TYPE (t) && domain == TYPE_DOMAIN (t))
2786           return t;
2787         r = build_cplus_array_type (type, domain);
2788         return r;
2789       }
2790
2791     case PLUS_EXPR:
2792     case MINUS_EXPR:
2793       return fold (build (TREE_CODE (t), TREE_TYPE (t),
2794                           tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
2795                           tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl)));
2796
2797     case NEGATE_EXPR:
2798     case NOP_EXPR:
2799       return fold (build1 (TREE_CODE (t), TREE_TYPE (t),
2800                            tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl)));
2801
2802     case TYPENAME_TYPE:
2803       {
2804         tree ctx = tsubst (TYPE_CONTEXT (t), args, nargs, in_decl);
2805         tree f = make_typename_type (ctx, TYPE_IDENTIFIER (t));
2806         return cp_build_type_variant
2807           (f, TYPE_READONLY (f) || TYPE_READONLY (t),
2808            TYPE_VOLATILE (f) || TYPE_VOLATILE (t));
2809       }
2810
2811     case INDIRECT_REF:
2812       return make_pointer_declarator
2813         (type, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl));
2814
2815     case ADDR_EXPR:
2816       return make_reference_declarator
2817         (type, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl));
2818
2819     case ARRAY_REF:
2820       return build_parse_node
2821         (ARRAY_REF, tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
2822          tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl));
2823
2824     case CALL_EXPR:
2825       return make_call_declarator
2826         (tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
2827          tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl),
2828          TREE_OPERAND (t, 2),
2829          tsubst (TREE_TYPE (t), args, nargs, in_decl));
2830
2831     case SCOPE_REF:
2832       return build_parse_node
2833         (TREE_CODE (t), tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
2834          tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl));
2835
2836     default:
2837       sorry ("use of `%s' in template",
2838              tree_code_name [(int) TREE_CODE (t)]);
2839       return error_mark_node;
2840     }
2841 }
2842
2843 void
2844 do_pushlevel ()
2845 {
2846   emit_line_note (input_filename, lineno);
2847   pushlevel (0);
2848   clear_last_expr ();
2849   push_momentary ();
2850   expand_start_bindings (0);
2851 }
2852
2853 tree
2854 do_poplevel ()
2855 {
2856   tree t;
2857   int saved_warn_unused;
2858
2859   if (processing_template_decl)
2860     {
2861       saved_warn_unused = warn_unused;
2862       warn_unused = 0;
2863     }
2864   expand_end_bindings (getdecls (), kept_level_p (), 0);
2865   if (processing_template_decl)
2866     warn_unused = saved_warn_unused;
2867   t = poplevel (kept_level_p (), 1, 0);
2868   pop_momentary ();
2869   return t;
2870 }
2871
2872 /* Like tsubst, but deals with expressions.  This function just replaces
2873    template parms; to finish processing the resultant expression, use
2874    tsubst_expr.  */
2875
2876 tree
2877 tsubst_copy (t, args, nargs, in_decl)
2878      tree t, args;
2879      int nargs;
2880      tree in_decl;
2881 {
2882   enum tree_code code;
2883
2884   if (t == NULL_TREE || t == error_mark_node)
2885     return t;
2886
2887   code = TREE_CODE (t);
2888
2889   switch (code)
2890     {
2891     case PARM_DECL:
2892       return do_identifier (DECL_NAME (t), 0);
2893
2894     case CONST_DECL:
2895     case FIELD_DECL:
2896       if (DECL_CONTEXT (t))
2897         {
2898           tree ctx = tsubst (DECL_CONTEXT (t), args, nargs, in_decl);
2899           if (ctx == current_function_decl)
2900             return lookup_name (DECL_NAME (t), 0);
2901           else if (ctx != DECL_CONTEXT (t))
2902             return lookup_field (ctx, DECL_NAME (t), 0, 0);
2903         }
2904       return t;
2905
2906     case VAR_DECL:
2907     case FUNCTION_DECL:
2908       if (DECL_LANG_SPECIFIC (t) && DECL_TEMPLATE_INFO (t))
2909         t = tsubst (t, args, nargs, in_decl);
2910       mark_used (t);
2911       return t;
2912
2913     case TEMPLATE_DECL:
2914       if (is_member_template (t))
2915         return tsubst (t, args, nargs, in_decl);
2916       else
2917         return t;
2918
2919 #if 0
2920     case IDENTIFIER_NODE:
2921       return do_identifier (t, 0);
2922 #endif
2923
2924     case CAST_EXPR:
2925     case REINTERPRET_CAST_EXPR:
2926     case CONST_CAST_EXPR:
2927     case STATIC_CAST_EXPR:
2928     case DYNAMIC_CAST_EXPR:
2929       return build1
2930         (code, tsubst (TREE_TYPE (t), args, nargs, in_decl),
2931          tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl));
2932
2933     case INDIRECT_REF:
2934     case PREDECREMENT_EXPR:
2935     case PREINCREMENT_EXPR:
2936     case POSTDECREMENT_EXPR:
2937     case POSTINCREMENT_EXPR:
2938     case NEGATE_EXPR:
2939     case TRUTH_NOT_EXPR:
2940     case BIT_NOT_EXPR:
2941     case ADDR_EXPR:
2942     case CONVERT_EXPR:      /* Unary + */
2943     case SIZEOF_EXPR:
2944     case ARROW_EXPR:
2945     case THROW_EXPR:
2946     case TYPEID_EXPR:
2947       return build1
2948         (code, NULL_TREE,
2949          tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl));
2950
2951     case PLUS_EXPR:
2952     case MINUS_EXPR:
2953     case MULT_EXPR:
2954     case TRUNC_DIV_EXPR:
2955     case CEIL_DIV_EXPR:
2956     case FLOOR_DIV_EXPR:
2957     case ROUND_DIV_EXPR:
2958     case EXACT_DIV_EXPR:
2959     case BIT_AND_EXPR:
2960     case BIT_ANDTC_EXPR:
2961     case BIT_IOR_EXPR:
2962     case BIT_XOR_EXPR:
2963     case TRUNC_MOD_EXPR:
2964     case FLOOR_MOD_EXPR:
2965     case TRUTH_ANDIF_EXPR:
2966     case TRUTH_ORIF_EXPR:
2967     case TRUTH_AND_EXPR:
2968     case TRUTH_OR_EXPR:
2969     case RSHIFT_EXPR:
2970     case LSHIFT_EXPR:
2971     case RROTATE_EXPR:
2972     case LROTATE_EXPR:
2973     case EQ_EXPR:
2974     case NE_EXPR:
2975     case MAX_EXPR:
2976     case MIN_EXPR:
2977     case LE_EXPR:
2978     case GE_EXPR:
2979     case LT_EXPR:
2980     case GT_EXPR:
2981     case COMPONENT_REF:
2982     case ARRAY_REF:
2983     case COMPOUND_EXPR:
2984     case SCOPE_REF:
2985     case DOTSTAR_EXPR:
2986     case MEMBER_REF:
2987       return build_nt
2988         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
2989          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl));
2990
2991     case CALL_EXPR:
2992       {
2993         tree fn = TREE_OPERAND (t, 0);
2994         if (really_overloaded_fn (fn))
2995           fn = tsubst_copy (get_first_fn (fn), args, nargs, in_decl);
2996         else
2997           fn = tsubst_copy (fn, args, nargs, in_decl);
2998         return build_nt
2999           (code, fn, tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
3000            NULL_TREE);
3001       }
3002
3003     case METHOD_CALL_EXPR:
3004       {
3005         tree name = TREE_OPERAND (t, 0);
3006         if (TREE_CODE (name) == BIT_NOT_EXPR)
3007           {
3008             name = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
3009             name = build1 (BIT_NOT_EXPR, NULL_TREE, TYPE_MAIN_VARIANT (name));
3010           }
3011         else if (TREE_CODE (name) == SCOPE_REF
3012                  && TREE_CODE (TREE_OPERAND (name, 1)) == BIT_NOT_EXPR)
3013           {
3014             tree base = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
3015             name = TREE_OPERAND (name, 1);
3016             name = tsubst_copy (TREE_OPERAND (name, 0), args, nargs, in_decl);
3017             name = build1 (BIT_NOT_EXPR, NULL_TREE, TYPE_MAIN_VARIANT (name));
3018             name = build_nt (SCOPE_REF, base, name);
3019           }
3020         else
3021           name = tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl);
3022         return build_nt
3023           (code, name, tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
3024            tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl),
3025            NULL_TREE);
3026       }
3027
3028     case COND_EXPR:
3029     case MODOP_EXPR:
3030       return build_nt
3031         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
3032          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
3033          tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl));
3034
3035     case NEW_EXPR:
3036       {
3037         tree r = build_nt
3038         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
3039          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl),
3040          tsubst_copy (TREE_OPERAND (t, 2), args, nargs, in_decl));
3041         NEW_EXPR_USE_GLOBAL (r) = NEW_EXPR_USE_GLOBAL (t);
3042         return r;
3043       }
3044
3045     case DELETE_EXPR:
3046       {
3047         tree r = build_nt
3048         (code, tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl),
3049          tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl));
3050         DELETE_EXPR_USE_GLOBAL (r) = DELETE_EXPR_USE_GLOBAL (t);
3051         DELETE_EXPR_USE_VEC (r) = DELETE_EXPR_USE_VEC (t);
3052         return r;
3053       }
3054
3055     case TEMPLATE_ID_EXPR:
3056       {
3057         /* Substituted template arguments */
3058         tree targs = tsubst_copy (TREE_OPERAND (t, 1), args, nargs, in_decl);
3059         tree chain;
3060         for (chain = targs; chain; chain = TREE_CHAIN (chain))
3061           TREE_VALUE (chain) = maybe_fold_nontype_arg (TREE_VALUE (chain));
3062
3063         return lookup_template_function
3064           (tsubst_copy (TREE_OPERAND (t, 0), args, nargs, in_decl), targs);
3065       }
3066
3067     case TREE_LIST:
3068       {
3069         tree purpose, value, chain;
3070
3071         if (t == void_list_node)
3072           return t;
3073
3074         purpose = TREE_PURPOSE (t);
3075         if (purpose)
3076           purpose = tsubst_copy (purpose, args, nargs, in_decl);
3077         value = TREE_VALUE (t);
3078         if (value)
3079           value = tsubst_copy (value, args, nargs, in_decl);
3080         chain = TREE_CHAIN (t);
3081         if (chain && chain != void_type_node)
3082           chain = tsubst_copy (chain, args, nargs, in_decl);
3083         if (purpose == TREE_PURPOSE (t)
3084             && value == TREE_VALUE (t)
3085             && chain == TREE_CHAIN (t))
3086           return t;
3087         return tree_cons (purpose, value, chain);
3088       }
3089
3090     case RECORD_TYPE:
3091     case UNION_TYPE:
3092     case ENUMERAL_TYPE:
3093     case INTEGER_TYPE:
3094     case TEMPLATE_TYPE_PARM:
3095     case TEMPLATE_CONST_PARM:
3096     case POINTER_TYPE:
3097     case REFERENCE_TYPE:
3098     case OFFSET_TYPE:
3099     case FUNCTION_TYPE:
3100     case METHOD_TYPE:
3101     case ARRAY_TYPE:
3102     case TYPENAME_TYPE:
3103       return tsubst (t, args, nargs, in_decl);
3104
3105     case IDENTIFIER_NODE:
3106       if (IDENTIFIER_TYPENAME_P (t))
3107         return build_typename_overload
3108           (tsubst (TREE_TYPE (t), args, nargs, in_decl));
3109       else
3110         return t;
3111
3112     case CONSTRUCTOR:
3113       return build
3114         (CONSTRUCTOR, tsubst (TREE_TYPE (t), args, nargs, in_decl), NULL_TREE,
3115          tsubst_copy (CONSTRUCTOR_ELTS (t), args, nargs, in_decl));
3116
3117     default:
3118       return t;
3119     }
3120 }
3121
3122 /* Like tsubst_copy, but also does semantic processing and RTL expansion.  */
3123
3124 tree
3125 tsubst_expr (t, args, nargs, in_decl)
3126      tree t, args;
3127      int nargs;
3128      tree in_decl;
3129 {
3130   if (t == NULL_TREE || t == error_mark_node)
3131     return t;
3132
3133   if (processing_template_decl)
3134     return tsubst_copy (t, args, nargs, in_decl);
3135
3136   switch (TREE_CODE (t))
3137     {
3138     case RETURN_STMT:
3139       lineno = TREE_COMPLEXITY (t);
3140       emit_line_note (input_filename, lineno);
3141       c_expand_return
3142         (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl));
3143       finish_stmt ();
3144       break;
3145
3146     case EXPR_STMT:
3147       lineno = TREE_COMPLEXITY (t);
3148       emit_line_note (input_filename, lineno);
3149       t = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
3150       /* Do default conversion if safe and possibly important,
3151          in case within ({...}).  */
3152       if ((TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE && lvalue_p (t))
3153           || TREE_CODE (TREE_TYPE (t)) == FUNCTION_TYPE)
3154         t = default_conversion (t);
3155       cplus_expand_expr_stmt (t);
3156       clear_momentary ();
3157       finish_stmt ();
3158       break;
3159
3160     case DECL_STMT:
3161       {
3162         int i = suspend_momentary ();
3163         tree dcl, init;
3164
3165         lineno = TREE_COMPLEXITY (t);
3166         emit_line_note (input_filename, lineno);
3167         dcl = start_decl
3168           (tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
3169            tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl),
3170            TREE_OPERAND (t, 2) != 0);
3171         init = tsubst_expr (TREE_OPERAND (t, 2), args, nargs, in_decl);
3172         cp_finish_decl
3173           (dcl, init, NULL_TREE, 1, /*init ? LOOKUP_ONLYCONVERTING :*/ 0);
3174         resume_momentary (i);
3175         return dcl;
3176       }
3177
3178     case FOR_STMT:
3179       {
3180         tree tmp;
3181         int init_scope = (flag_new_for_scope > 0 && TREE_OPERAND (t, 0)
3182                           && TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
3183         int cond_scope = (TREE_OPERAND (t, 1)
3184                           && TREE_CODE (TREE_OPERAND (t, 1)) == DECL_STMT);
3185
3186         lineno = TREE_COMPLEXITY (t);
3187         emit_line_note (input_filename, lineno);
3188         if (init_scope)
3189           do_pushlevel ();
3190         for (tmp = TREE_OPERAND (t, 0); tmp; tmp = TREE_CHAIN (tmp))
3191           tsubst_expr (tmp, args, nargs, in_decl);
3192         emit_nop ();
3193         emit_line_note (input_filename, lineno);
3194         expand_start_loop_continue_elsewhere (1);
3195
3196         if (cond_scope)
3197           do_pushlevel ();
3198         tmp = tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
3199         emit_line_note (input_filename, lineno);
3200         if (tmp)
3201           expand_exit_loop_if_false (0, condition_conversion (tmp));
3202
3203         if (! cond_scope)
3204           do_pushlevel ();
3205         tsubst_expr (TREE_OPERAND (t, 3), args, nargs, in_decl);
3206         do_poplevel ();
3207
3208         emit_line_note (input_filename, lineno);
3209         expand_loop_continue_here ();
3210         tmp = tsubst_expr (TREE_OPERAND (t, 2), args, nargs, in_decl);
3211         if (tmp)
3212           cplus_expand_expr_stmt (tmp);
3213
3214         expand_end_loop ();
3215         if (init_scope)
3216           do_poplevel ();
3217         finish_stmt ();
3218       }
3219       break;
3220
3221     case WHILE_STMT:
3222       {
3223         tree cond;
3224
3225         lineno = TREE_COMPLEXITY (t);
3226         emit_nop ();
3227         emit_line_note (input_filename, lineno);
3228         expand_start_loop (1);
3229
3230         cond = TREE_OPERAND (t, 0);
3231         if (TREE_CODE (cond) == DECL_STMT)
3232           do_pushlevel ();
3233         cond = tsubst_expr (cond, args, nargs, in_decl);
3234         emit_line_note (input_filename, lineno);
3235         expand_exit_loop_if_false (0, condition_conversion (cond));
3236
3237         if (TREE_CODE (TREE_OPERAND (t, 0)) != DECL_STMT)
3238           do_pushlevel ();
3239         tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
3240         do_poplevel ();
3241
3242         expand_end_loop ();
3243         finish_stmt ();
3244       }
3245       break;
3246
3247     case DO_STMT:
3248       {
3249         tree cond;
3250
3251         lineno = TREE_COMPLEXITY (t);
3252         emit_nop ();
3253         emit_line_note (input_filename, lineno);
3254         expand_start_loop_continue_elsewhere (1);
3255
3256         tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
3257         expand_loop_continue_here ();
3258
3259         cond = tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
3260         emit_line_note (input_filename, lineno);
3261         expand_exit_loop_if_false (0, condition_conversion (cond));
3262         expand_end_loop ();
3263
3264         clear_momentary ();
3265         finish_stmt ();
3266       }
3267       break;
3268
3269     case IF_STMT:
3270       {
3271         tree tmp;
3272         int cond_scope = (TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
3273
3274         lineno = TREE_COMPLEXITY (t);
3275         if (cond_scope)
3276           do_pushlevel ();
3277         tmp = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
3278         emit_line_note (input_filename, lineno);
3279         expand_start_cond (condition_conversion (tmp), 0);
3280
3281         if (tmp = TREE_OPERAND (t, 1), tmp)
3282           tsubst_expr (tmp, args, nargs, in_decl);
3283
3284         if (tmp = TREE_OPERAND (t, 2), tmp)
3285           {
3286             expand_start_else ();
3287             tsubst_expr (tmp, args, nargs, in_decl);
3288           }
3289
3290         expand_end_cond ();
3291
3292         if (cond_scope)
3293           do_poplevel ();
3294
3295         finish_stmt ();
3296       }
3297       break;
3298
3299     case COMPOUND_STMT:
3300       {
3301         tree substmt = TREE_OPERAND (t, 0);
3302
3303         lineno = TREE_COMPLEXITY (t);
3304
3305         if (COMPOUND_STMT_NO_SCOPE (t) == 0)
3306           do_pushlevel ();
3307
3308         for (; substmt; substmt = TREE_CHAIN (substmt))
3309           tsubst_expr (substmt, args, nargs, in_decl);
3310
3311         if (COMPOUND_STMT_NO_SCOPE (t) == 0)
3312           do_poplevel ();
3313       }
3314       break;
3315
3316     case BREAK_STMT:
3317       lineno = TREE_COMPLEXITY (t);
3318       emit_line_note (input_filename, lineno);
3319       if (! expand_exit_something ())
3320         error ("break statement not within loop or switch");
3321       break;
3322
3323     case CONTINUE_STMT:
3324       lineno = TREE_COMPLEXITY (t);
3325       emit_line_note (input_filename, lineno);
3326       if (! expand_continue_loop (0))
3327         error ("continue statement not within a loop");
3328       break;
3329
3330     case SWITCH_STMT:
3331       {
3332         tree val, tmp;
3333         int cond_scope = (TREE_CODE (TREE_OPERAND (t, 0)) == DECL_STMT);
3334
3335         lineno = TREE_COMPLEXITY (t);
3336         if (cond_scope)
3337           do_pushlevel ();
3338         val = tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
3339         emit_line_note (input_filename, lineno);
3340         c_expand_start_case (val);
3341         push_switch ();
3342
3343         if (tmp = TREE_OPERAND (t, 1), tmp)
3344           tsubst_expr (tmp, args, nargs, in_decl);
3345
3346         expand_end_case (val);
3347         pop_switch ();
3348
3349         if (cond_scope)
3350           do_poplevel ();
3351
3352         finish_stmt ();
3353       }
3354       break;
3355
3356     case CASE_LABEL:
3357       do_case (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl),
3358                tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl));
3359       break;
3360
3361     case LABEL_DECL:
3362       t = define_label (DECL_SOURCE_FILE (t), DECL_SOURCE_LINE (t),
3363                         DECL_NAME (t));
3364       if (t)
3365         expand_label (t);
3366       break;
3367
3368     case GOTO_STMT:
3369       lineno = TREE_COMPLEXITY (t);
3370       emit_line_note (input_filename, lineno);
3371       if (TREE_CODE (TREE_OPERAND (t, 0)) == IDENTIFIER_NODE)
3372         {
3373           tree decl = lookup_label (TREE_OPERAND (t, 0));
3374           TREE_USED (decl) = 1;
3375           expand_goto (decl);
3376         }
3377       else
3378         expand_computed_goto
3379           (tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl));
3380       break;
3381
3382     case TRY_BLOCK:
3383       lineno = TREE_COMPLEXITY (t);
3384       emit_line_note (input_filename, lineno);
3385       expand_start_try_stmts ();
3386       tsubst_expr (TREE_OPERAND (t, 0), args, nargs, in_decl);
3387       expand_start_all_catch ();
3388       {
3389         tree handler = TREE_OPERAND (t, 1);
3390         for (; handler; handler = TREE_CHAIN (handler))
3391           tsubst_expr (handler, args, nargs, in_decl);
3392       }
3393       expand_end_all_catch ();
3394       break;
3395
3396     case HANDLER:
3397       lineno = TREE_COMPLEXITY (t);
3398       do_pushlevel ();
3399       if (TREE_OPERAND (t, 0))
3400         {
3401           tree d = TREE_OPERAND (t, 0);
3402           expand_start_catch_block
3403             (tsubst (TREE_OPERAND (d, 1), args, nargs, in_decl),
3404              tsubst (TREE_OPERAND (d, 0), args, nargs, in_decl));
3405         }
3406       else
3407         expand_start_catch_block (NULL_TREE, NULL_TREE);
3408       tsubst_expr (TREE_OPERAND (t, 1), args, nargs, in_decl);
3409       expand_end_catch_block ();
3410       do_poplevel ();
3411       break;
3412
3413     case TAG_DEFN:
3414       lineno = TREE_COMPLEXITY (t);
3415       t = TREE_TYPE (t);
3416       if (TREE_CODE (t) == ENUMERAL_TYPE)
3417         tsubst_enum (t, args, nargs, NULL);
3418       break;
3419
3420     default:
3421       return build_expr_from_tree (tsubst_copy (t, args, nargs, in_decl));
3422     }
3423   return NULL_TREE;
3424 }
3425
3426 tree
3427 instantiate_template (tmpl, targ_ptr)
3428      tree tmpl, targ_ptr;
3429 {
3430   tree fndecl;
3431   int i, len;
3432   struct obstack *old_fmp_obstack;
3433   extern struct obstack *function_maybepermanent_obstack;
3434
3435   my_friendly_assert (TREE_CODE (tmpl) == TEMPLATE_DECL, 283);
3436
3437   if (DECL_FUNCTION_TEMPLATE_P (tmpl))
3438     {
3439       tree specs;
3440
3441       /* Check to see if there is a matching specialization. */
3442       for (specs = DECL_TEMPLATE_SPECIALIZATIONS (tmpl);
3443            specs != NULL_TREE;
3444            specs = TREE_CHAIN (specs))
3445         if (comp_template_args (TREE_PURPOSE (specs), targ_ptr))
3446           return TREE_VALUE (specs);
3447     }
3448
3449   push_obstacks (&permanent_obstack, &permanent_obstack);
3450   old_fmp_obstack = function_maybepermanent_obstack;
3451   function_maybepermanent_obstack = &permanent_obstack;
3452
3453   len = DECL_NTPARMS (tmpl);
3454
3455   i = len;
3456   while (i--)
3457     {
3458       tree t = TREE_VEC_ELT (targ_ptr, i);
3459       if (TREE_CODE_CLASS (TREE_CODE (t)) == 't')
3460         {
3461           tree nt = target_type (t);
3462           if (IS_AGGR_TYPE (nt) && decl_function_context (TYPE_MAIN_DECL (nt)))
3463             {
3464               cp_error ("type `%T' composed from a local class is not a valid template-argument", t);
3465               cp_error ("  trying to instantiate `%D'", tmpl);
3466               fndecl = error_mark_node;
3467               goto out;
3468             }
3469         }
3470       TREE_VEC_ELT (targ_ptr, i) = copy_to_permanent (t);
3471     }
3472   targ_ptr = copy_to_permanent (targ_ptr);
3473
3474   if (DECL_TEMPLATE_INFO (tmpl) && DECL_TI_ARGS (tmpl))
3475     targ_ptr = add_to_template_args (DECL_TI_ARGS (tmpl), targ_ptr);
3476
3477   /* substitute template parameters */
3478   fndecl = tsubst (DECL_RESULT (tmpl), targ_ptr, len, tmpl);
3479
3480   if (flag_external_templates)
3481     add_pending_template (fndecl);
3482
3483  out:
3484   function_maybepermanent_obstack = old_fmp_obstack;
3485   pop_obstacks ();
3486
3487   return fndecl;
3488 }
3489
3490 /* Push the name of the class template into the scope of the instantiation.  */
3491
3492 void
3493 overload_template_name (type)
3494      tree type;
3495 {
3496   tree id = DECL_NAME (CLASSTYPE_TI_TEMPLATE (type));
3497   tree decl;
3498
3499   if (IDENTIFIER_CLASS_VALUE (id)
3500       && TREE_TYPE (IDENTIFIER_CLASS_VALUE (id)) == type)
3501     return;
3502
3503   decl = build_decl (TYPE_DECL, id, type);
3504   SET_DECL_ARTIFICIAL (decl);
3505   pushdecl_class_level (decl);
3506 }
3507
3508 /* Like type_unification but designed specially to handle conversion
3509    operators.  */
3510
3511 int
3512 fn_type_unification (fn, explicit_targs, targs, args, return_type, strict)
3513      tree fn, explicit_targs, targs, args, return_type;
3514      int strict;
3515 {
3516   int i, dummy = 0;
3517   tree fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
3518   tree decl_arg_types = args;
3519
3520   my_friendly_assert (TREE_CODE (fn) == TEMPLATE_DECL, 0);
3521
3522   if (IDENTIFIER_TYPENAME_P (DECL_NAME (fn)))
3523     {
3524       /* This is a template conversion operator.  Use the return types
3525          as well as the argument types.  */
3526       fn_arg_types = scratch_tree_cons (NULL_TREE,
3527                                 TREE_TYPE (TREE_TYPE (fn)),
3528                                 fn_arg_types);
3529       decl_arg_types = scratch_tree_cons (NULL_TREE,
3530                                   return_type,
3531                                   decl_arg_types);
3532     }
3533
3534   i = type_unification (DECL_INNERMOST_TEMPLATE_PARMS (fn),
3535                         &TREE_VEC_ELT (targs, 0),
3536                         fn_arg_types,
3537                         decl_arg_types,
3538                         explicit_targs,
3539                         &dummy, strict, 0);
3540
3541   return i;
3542 }
3543
3544
3545 /* Type unification.
3546
3547    We have a function template signature with one or more references to
3548    template parameters, and a parameter list we wish to fit to this
3549    template.  If possible, produce a list of parameters for the template
3550    which will cause it to fit the supplied parameter list.
3551
3552    Return zero for success, 2 for an incomplete match that doesn't resolve
3553    all the types, and 1 for complete failure.  An error message will be
3554    printed only for an incomplete match.
3555
3556    TPARMS[NTPARMS] is an array of template parameter types;
3557    TARGS[NTPARMS] is the array of template parameter values.  PARMS is
3558    the function template's signature (using TEMPLATE_PARM_IDX nodes),
3559    and ARGS is the argument list we're trying to match against it.
3560
3561    If SUBR is 1, we're being called recursively (to unify the arguments of
3562    a function or method parameter of a function template), so don't zero
3563    out targs and don't fail on an incomplete match.
3564
3565    If STRICT is 1, the match must be exact (for casts of overloaded
3566    addresses, explicit instantiation, and more_specialized).  */
3567
3568 int
3569 type_unification (tparms, targs, parms, args, targs_in, nsubsts,
3570                   strict, allow_incomplete)
3571      tree tparms, *targs, parms, args, targs_in;
3572      int *nsubsts, strict, allow_incomplete;
3573 {
3574   int ntparms = TREE_VEC_LENGTH (tparms);
3575   tree t;
3576   int i;
3577   int r;
3578
3579   bzero ((char *) targs, sizeof (tree) * ntparms);
3580
3581   /* Insert any explicit template arguments.  They are encoded as the
3582      operands of NOP_EXPRs so that unify can tell that they are
3583      explicit arguments.  */
3584   for (i = 0, t = targs_in; t != NULL_TREE; t = TREE_CHAIN (t), ++i)
3585     targs[i] = build1 (NOP_EXPR, NULL_TREE, TREE_VALUE (t));
3586
3587   r = type_unification_real (tparms, targs, parms, args, nsubsts, 0,
3588                              strict, allow_incomplete);
3589
3590   for (i = 0, t = targs_in; t != NULL_TREE; t = TREE_CHAIN (t), ++i)
3591     if (TREE_CODE (targs[i]) == NOP_EXPR)
3592       targs[i] = TREE_OPERAND (targs[i], 0);
3593
3594   return r;
3595 }
3596
3597
3598 static int
3599 type_unification_real (tparms, targs, parms, args, nsubsts, subr,
3600                        strict, allow_incomplete)
3601      tree tparms, *targs, parms, args;
3602      int *nsubsts, subr, strict, allow_incomplete;
3603 {
3604   tree parm, arg;
3605   int i;
3606   int ntparms = TREE_VEC_LENGTH (tparms);
3607
3608   my_friendly_assert (TREE_CODE (tparms) == TREE_VEC, 289);
3609   my_friendly_assert (parms == NULL_TREE
3610                       || TREE_CODE (parms) == TREE_LIST, 290);
3611   /* ARGS could be NULL (via a call from parse.y to
3612      build_x_function_call).  */
3613   if (args)
3614     my_friendly_assert (TREE_CODE (args) == TREE_LIST, 291);
3615   my_friendly_assert (ntparms > 0, 292);
3616
3617   while (parms
3618          && parms != void_list_node
3619          && args
3620          && args != void_list_node)
3621     {
3622       parm = TREE_VALUE (parms);
3623       parms = TREE_CHAIN (parms);
3624       arg = TREE_VALUE (args);
3625       args = TREE_CHAIN (args);
3626
3627       if (arg == error_mark_node)
3628         return 1;
3629       if (arg == unknown_type_node)
3630         return 1;
3631
3632       /* Conversions will be performed on a function argument that
3633          corresponds with a function parameter that contains only
3634          non-deducible template parameters and explicitly specified
3635          template parameters.  */
3636       if (! uses_template_parms (parm))
3637         {
3638           tree type;
3639
3640           if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
3641             type = TREE_TYPE (arg);
3642           else
3643             {
3644               type = arg;
3645               arg = NULL_TREE;
3646             }
3647
3648           if (strict)
3649             {
3650               if (comptypes (parm, type, 1))
3651                 continue;
3652             }
3653           else if (arg)
3654             {
3655               if (can_convert_arg (parm, type, arg))
3656                 continue;
3657             }
3658           else
3659             {
3660               if (can_convert (parm, type))
3661                 continue;
3662             }
3663
3664           return 1;
3665         }
3666
3667 #if 0
3668       if (TREE_CODE (arg) == VAR_DECL)
3669         arg = TREE_TYPE (arg);
3670       else if (TREE_CODE_CLASS (TREE_CODE (arg)) == 'e')
3671         arg = TREE_TYPE (arg);
3672 #else
3673       if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
3674         {
3675           my_friendly_assert (TREE_TYPE (arg) != NULL_TREE, 293);
3676           if (TREE_CODE (arg) == TREE_LIST
3677               && TREE_TYPE (arg) == unknown_type_node
3678               && TREE_CODE (TREE_VALUE (arg)) == TEMPLATE_DECL)
3679             {
3680               int nsubsts, ntparms;
3681               tree *targs;
3682
3683               /* Have to back unify here */
3684               arg = TREE_VALUE (arg);
3685               nsubsts = 0;
3686               ntparms = DECL_NTPARMS (arg);
3687               targs = (tree *) alloca (sizeof (tree) * ntparms);
3688               parm = expr_tree_cons (NULL_TREE, parm, NULL_TREE);
3689               return
3690                 type_unification (DECL_INNERMOST_TEMPLATE_PARMS (arg),
3691                                   targs,
3692                                   TYPE_ARG_TYPES (TREE_TYPE (arg)),
3693                                   parm, NULL_TREE, &nsubsts, strict,
3694                                   allow_incomplete);
3695             }
3696           arg = TREE_TYPE (arg);
3697         }
3698 #endif
3699       if (! subr && TREE_CODE (arg) == REFERENCE_TYPE)
3700         arg = TREE_TYPE (arg);
3701
3702       if (! subr && TREE_CODE (parm) != REFERENCE_TYPE)
3703         {
3704           if (TREE_CODE (arg) == FUNCTION_TYPE
3705               || TREE_CODE (arg) == METHOD_TYPE)
3706             arg = build_pointer_type (arg);
3707           else if (TREE_CODE (arg) == ARRAY_TYPE)
3708             arg = build_pointer_type (TREE_TYPE (arg));
3709           else
3710             arg = TYPE_MAIN_VARIANT (arg);
3711         }
3712
3713       switch (unify (tparms, targs, ntparms, parm, arg, nsubsts, strict))
3714         {
3715         case 0:
3716           break;
3717         case 1:
3718           return 1;
3719         }
3720     }
3721   /* Fail if we've reached the end of the parm list, and more args
3722      are present, and the parm list isn't variadic.  */
3723   if (args && args != void_list_node && parms == void_list_node)
3724     return 1;
3725   /* Fail if parms are left and they don't have default values.  */
3726   if (parms
3727       && parms != void_list_node
3728       && TREE_PURPOSE (parms) == NULL_TREE)
3729     return 1;
3730   if (!subr)
3731     for (i = 0; i < ntparms; i++)
3732       if (!targs[i])
3733         {
3734           if (!allow_incomplete)
3735             error ("incomplete type unification");
3736           return 2;
3737         }
3738   return 0;
3739 }
3740
3741 /* Tail recursion is your friend.  */
3742
3743 static int
3744 unify (tparms, targs, ntparms, parm, arg, nsubsts, strict)
3745      tree tparms, *targs, parm, arg;
3746      int *nsubsts, ntparms, strict;
3747 {
3748   int idx;
3749
3750   /* I don't think this will do the right thing with respect to types.
3751      But the only case I've seen it in so far has been array bounds, where
3752      signedness is the only information lost, and I think that will be
3753      okay.  */
3754   while (TREE_CODE (parm) == NOP_EXPR)
3755     parm = TREE_OPERAND (parm, 0);
3756
3757   if (arg == error_mark_node)
3758     return 1;
3759   if (arg == unknown_type_node)
3760     return 1;
3761   if (arg == parm)
3762     return 0;
3763
3764   switch (TREE_CODE (parm))
3765     {
3766     case TYPENAME_TYPE:
3767       /* In a type which contains a nested-name-specifier, template
3768          argument values cannot be deduced for template parameters used
3769          within the nested-name-specifier.  */
3770       return 0;
3771
3772     case TEMPLATE_TYPE_PARM:
3773       (*nsubsts)++;
3774       idx = TEMPLATE_TYPE_IDX (parm);
3775       /* Check for mixed types and values.  */
3776       if (TREE_CODE (TREE_VALUE (TREE_VEC_ELT (tparms, idx))) != TYPE_DECL)
3777         return 1;
3778
3779       if (!strict && targs[idx] != NULL_TREE &&
3780           TREE_CODE (targs[idx]) == NOP_EXPR)
3781         /* An explicit template argument.  Don't even try to match
3782            here; the overload resolution code will manage check to
3783            see whether the call is legal.  */
3784         return 0;
3785
3786       if (strict && (TYPE_READONLY (arg) < TYPE_READONLY (parm)
3787                      || TYPE_VOLATILE (arg) < TYPE_VOLATILE (parm)))
3788         return 1;
3789 #if 0
3790       /* Template type parameters cannot contain cv-quals; i.e.
3791          template <class T> void f (T& a, T& b) will not generate
3792          void f (const int& a, const int& b).  */
3793       if (TYPE_READONLY (arg) > TYPE_READONLY (parm)
3794           || TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm))
3795         return 1;
3796       arg = TYPE_MAIN_VARIANT (arg);
3797 #else
3798       {
3799         int constp = TYPE_READONLY (arg) > TYPE_READONLY (parm);
3800         int volatilep = TYPE_VOLATILE (arg) > TYPE_VOLATILE (parm);
3801         arg = cp_build_type_variant (arg, constp, volatilep);
3802       }
3803 #endif
3804       /* Simple cases: Value already set, does match or doesn't.  */
3805       if (targs[idx] == arg
3806           || (targs[idx]
3807               && TREE_CODE (targs[idx]) == NOP_EXPR
3808               && TREE_OPERAND (targs[idx], 0) == arg))
3809         return 0;
3810       else if (targs[idx])
3811         return 1;
3812       targs[idx] = arg;
3813       return 0;
3814     case TEMPLATE_CONST_PARM:
3815       (*nsubsts)++;
3816       idx = TEMPLATE_CONST_IDX (parm);
3817       if (targs[idx])
3818         {
3819           int i = cp_tree_equal (targs[idx], arg);
3820           if (i == 1)
3821             return 0;
3822           else if (i == 0)
3823             return 1;
3824           else
3825             my_friendly_abort (42);
3826         }
3827
3828       targs[idx] = copy_to_permanent (arg);
3829       return 0;
3830
3831     case POINTER_TYPE:
3832       if (TREE_CODE (arg) == RECORD_TYPE && TYPE_PTRMEMFUNC_FLAG (arg))
3833         return unify (tparms, targs, ntparms, parm,
3834                       TYPE_PTRMEMFUNC_FN_TYPE (arg), nsubsts, strict);
3835
3836       if (TREE_CODE (arg) != POINTER_TYPE)
3837         return 1;
3838       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
3839                     nsubsts, strict);
3840
3841     case REFERENCE_TYPE:
3842       if (TREE_CODE (arg) == REFERENCE_TYPE)
3843         arg = TREE_TYPE (arg);
3844       return unify (tparms, targs, ntparms, TREE_TYPE (parm), arg,
3845                     nsubsts, strict);
3846
3847     case ARRAY_TYPE:
3848       if (TREE_CODE (arg) != ARRAY_TYPE)
3849         return 1;
3850       if (unify (tparms, targs, ntparms, TYPE_DOMAIN (parm), TYPE_DOMAIN (arg),
3851                  nsubsts, strict) != 0)
3852         return 1;
3853       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
3854                     nsubsts, strict);
3855
3856     case REAL_TYPE:
3857     case COMPLEX_TYPE:
3858     case INTEGER_TYPE:
3859     case BOOLEAN_TYPE:
3860     case VOID_TYPE:
3861       if (TREE_CODE (arg) != TREE_CODE (parm))
3862         return 1;
3863
3864       if (TREE_CODE (parm) == INTEGER_TYPE)
3865         {
3866           if (TYPE_MIN_VALUE (parm) && TYPE_MIN_VALUE (arg)
3867               && unify (tparms, targs, ntparms, TYPE_MIN_VALUE (parm),
3868                         TYPE_MIN_VALUE (arg), nsubsts, strict))
3869             return 1;
3870           if (TYPE_MAX_VALUE (parm) && TYPE_MAX_VALUE (arg)
3871               && unify (tparms, targs, ntparms, TYPE_MAX_VALUE (parm),
3872                         TYPE_MAX_VALUE (arg), nsubsts, strict))
3873             return 1;
3874         }
3875       else if (TREE_CODE (parm) == REAL_TYPE
3876                && TYPE_MAIN_VARIANT (arg) != TYPE_MAIN_VARIANT (parm))
3877         return 1;
3878
3879       /* As far as unification is concerned, this wins.  Later checks
3880          will invalidate it if necessary.  */
3881       return 0;
3882
3883       /* Types INTEGER_CST and MINUS_EXPR can come from array bounds.  */
3884       /* Type INTEGER_CST can come from ordinary constant template args.  */
3885     case INTEGER_CST:
3886       while (TREE_CODE (arg) == NOP_EXPR)
3887         arg = TREE_OPERAND (arg, 0);
3888
3889       if (TREE_CODE (arg) != INTEGER_CST)
3890         return 1;
3891       return !tree_int_cst_equal (parm, arg);
3892
3893     case MINUS_EXPR:
3894       {
3895         tree t1, t2;
3896         t1 = TREE_OPERAND (parm, 0);
3897         t2 = TREE_OPERAND (parm, 1);
3898         return unify (tparms, targs, ntparms, t1,
3899                       fold (build (PLUS_EXPR, integer_type_node, arg, t2)),
3900                       nsubsts, strict);
3901       }
3902
3903     case TREE_VEC:
3904       {
3905         int i;
3906         if (TREE_CODE (arg) != TREE_VEC)
3907           return 1;
3908         if (TREE_VEC_LENGTH (parm) != TREE_VEC_LENGTH (arg))
3909           return 1;
3910         for (i = TREE_VEC_LENGTH (parm) - 1; i >= 0; i--)
3911           if (unify (tparms, targs, ntparms,
3912                      TREE_VEC_ELT (parm, i), TREE_VEC_ELT (arg, i),
3913                      nsubsts, strict))
3914             return 1;
3915         return 0;
3916       }
3917
3918     case RECORD_TYPE:
3919       if (TYPE_PTRMEMFUNC_FLAG (parm))
3920         return unify (tparms, targs, ntparms, TYPE_PTRMEMFUNC_FN_TYPE (parm),
3921                       arg, nsubsts, strict);
3922
3923       /* Allow trivial conversions.  */
3924       if (TREE_CODE (arg) != RECORD_TYPE
3925           || TYPE_READONLY (parm) < TYPE_READONLY (arg)
3926           || TYPE_VOLATILE (parm) < TYPE_VOLATILE (arg))
3927         return 1;
3928
3929       if (CLASSTYPE_TEMPLATE_INFO (parm) && uses_template_parms (parm))
3930         {
3931           tree t = NULL_TREE;
3932           if (flag_ansi_overloading && ! strict)
3933             t = get_template_base (CLASSTYPE_TI_TEMPLATE (parm), arg);
3934           else if
3935             (CLASSTYPE_TEMPLATE_INFO (arg)
3936              && CLASSTYPE_TI_TEMPLATE (parm) == CLASSTYPE_TI_TEMPLATE (arg))
3937             t = arg;
3938           if (! t || t == error_mark_node)
3939             return 1;
3940
3941           return unify (tparms, targs, ntparms, CLASSTYPE_TI_ARGS (parm),
3942                         CLASSTYPE_TI_ARGS (t), nsubsts, strict);
3943         }
3944       else if (TYPE_MAIN_VARIANT (parm) != TYPE_MAIN_VARIANT (arg))
3945         return 1;
3946       return 0;
3947
3948     case METHOD_TYPE:
3949       if (TREE_CODE (arg) != METHOD_TYPE)
3950         return 1;
3951       goto check_args;
3952
3953     case FUNCTION_TYPE:
3954       if (TREE_CODE (arg) != FUNCTION_TYPE)
3955         return 1;
3956      check_args:
3957       if (unify (tparms, targs, ntparms, TREE_TYPE (parm),
3958                  TREE_TYPE (arg), nsubsts, strict))
3959         return 1;
3960       return type_unification_real (tparms, targs, TYPE_ARG_TYPES (parm),
3961                                     TYPE_ARG_TYPES (arg), nsubsts, 1,
3962                                     strict, 0);
3963
3964     case OFFSET_TYPE:
3965       if (TREE_CODE (arg) != OFFSET_TYPE)
3966         return 1;
3967       if (unify (tparms, targs, ntparms, TYPE_OFFSET_BASETYPE (parm),
3968                  TYPE_OFFSET_BASETYPE (arg), nsubsts, strict))
3969         return 1;
3970       return unify (tparms, targs, ntparms, TREE_TYPE (parm),
3971                     TREE_TYPE (arg), nsubsts, strict);
3972
3973     case CONST_DECL:
3974       if (arg != decl_constant_value (parm))
3975         return 1;
3976       return 0;
3977
3978     default:
3979       sorry ("use of `%s' in template type unification",
3980              tree_code_name [(int) TREE_CODE (parm)]);
3981       return 1;
3982     }
3983 }
3984 \f
3985 void
3986 mark_decl_instantiated (result, extern_p)
3987      tree result;
3988      int extern_p;
3989 {
3990   if (DECL_TEMPLATE_INSTANTIATION (result))
3991     SET_DECL_EXPLICIT_INSTANTIATION (result);
3992   TREE_PUBLIC (result) = 1;
3993
3994   if (! extern_p)
3995     {
3996       DECL_INTERFACE_KNOWN (result) = 1;
3997       DECL_NOT_REALLY_EXTERN (result) = 1;
3998
3999       /* For WIN32 we also want to put explicit instantiations in
4000          linkonce sections.  */
4001       if (supports_one_only () && ! SUPPORTS_WEAK)
4002         comdat_linkage (result);
4003     }
4004   else if (TREE_CODE (result) == FUNCTION_DECL)
4005     mark_inline_for_output (result);
4006 }
4007
4008 /* Given two function templates PAT1 and PAT2, return:
4009
4010    1 if PAT1 is more specialized than PAT2 as described in [temp.func.order].
4011    -1 if PAT2 is more specialized than PAT1.
4012    0 if neither is more specialized.  */
4013
4014 int
4015 more_specialized (pat1, pat2)
4016      tree pat1, pat2;
4017 {
4018   tree targs;
4019   int winner = 0;
4020
4021   targs = get_bindings (pat1, pat2);
4022   if (targs)
4023     {
4024       --winner;
4025     }
4026
4027   targs = get_bindings (pat2, pat1);
4028   if (targs)
4029     {
4030       ++winner;
4031     }
4032
4033   return winner;
4034 }
4035
4036 /* Given two class template specialization list nodes PAT1 and PAT2, return:
4037
4038    1 if PAT1 is more specialized than PAT2 as described in [temp.class.order].
4039    -1 if PAT2 is more specialized than PAT1.
4040    0 if neither is more specialized.  */
4041
4042 int
4043 more_specialized_class (pat1, pat2)
4044      tree pat1, pat2;
4045 {
4046   tree targs;
4047   int winner = 0;
4048
4049   targs = get_class_bindings
4050     (TREE_VALUE (pat1), TREE_PURPOSE (pat1), TREE_PURPOSE (pat2));
4051   if (targs)
4052     --winner;
4053
4054   targs = get_class_bindings
4055     (TREE_VALUE (pat2), TREE_PURPOSE (pat2), TREE_PURPOSE (pat1));
4056   if (targs)
4057     ++winner;
4058
4059   return winner;
4060 }
4061
4062 /* Return the template arguments that will produce the function signature
4063    DECL from the function template FN.  */
4064
4065 tree
4066 get_bindings (fn, decl)
4067      tree fn, decl;
4068 {
4069   int ntparms = DECL_NTPARMS (fn);
4070   tree targs = make_scratch_vec (ntparms);
4071   int i;
4072
4073   i = fn_type_unification (fn, NULL_TREE, targs,
4074                            TYPE_ARG_TYPES (TREE_TYPE (decl)),
4075                            TREE_TYPE (TREE_TYPE (decl)),
4076                            1);
4077
4078   if (i == 0)
4079     return targs;
4080   return 0;
4081 }
4082
4083 static tree
4084 get_class_bindings (tparms, parms, args)
4085      tree tparms, parms, args;
4086 {
4087   int i, dummy, ntparms = TREE_VEC_LENGTH (tparms);
4088   tree vec = make_temp_vec (ntparms);
4089
4090   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
4091     {
4092       switch (unify (tparms, &TREE_VEC_ELT (vec, 0), ntparms,
4093                      TREE_VEC_ELT (parms, i), TREE_VEC_ELT (args, i),
4094                      &dummy, 1))
4095         {
4096         case 0:
4097           break;
4098         case 1:
4099           return NULL_TREE;
4100         }
4101     }
4102
4103   for (i =  0; i < ntparms; ++i)
4104     if (! TREE_VEC_ELT (vec, i))
4105       return NULL_TREE;
4106
4107   return vec;
4108 }
4109
4110 /* Return the most specialized of the list of templates in FNS that can
4111    produce an instantiation matching DECL.  */
4112
4113 tree
4114 most_specialized (fns, decl)
4115      tree fns, decl;
4116 {
4117   tree fn, champ, args, *p;
4118   int fate;
4119
4120   for (p = &fns; *p; )
4121     {
4122       args = get_bindings (TREE_VALUE (*p), decl);
4123       if (args)
4124         {
4125           p = &TREE_CHAIN (*p);
4126         }
4127       else
4128         *p = TREE_CHAIN (*p);
4129     }
4130
4131   if (! fns)
4132     return NULL_TREE;
4133
4134   fn = fns;
4135   champ = TREE_VALUE (fn);
4136   fn = TREE_CHAIN (fn);
4137   for (; fn; fn = TREE_CHAIN (fn))
4138     {
4139       fate = more_specialized (champ, TREE_VALUE (fn));
4140       if (fate == 1)
4141         ;
4142       else
4143         {
4144           if (fate == 0)
4145             {
4146               fn = TREE_CHAIN (fn);
4147               if (! fn)
4148                 return error_mark_node;
4149             }
4150           champ = TREE_VALUE (fn);
4151         }
4152     }
4153
4154   for (fn = fns; fn && TREE_VALUE (fn) != champ; fn = TREE_CHAIN (fn))
4155     {
4156       fate = more_specialized (champ, TREE_VALUE (fn));
4157       if (fate != 1)
4158         return error_mark_node;
4159     }
4160
4161   return champ;
4162 }
4163
4164 /* Return the most specialized of the class template specializations in
4165    SPECS that can produce an instantiation matching ARGS.  */
4166
4167 tree
4168 most_specialized_class (specs, mainargs)
4169      tree specs, mainargs;
4170 {
4171   tree list = NULL_TREE, t, args, champ;
4172   int fate;
4173
4174   for (t = specs; t; t = TREE_CHAIN (t))
4175     {
4176       args = get_class_bindings (TREE_VALUE (t), TREE_PURPOSE (t), mainargs);
4177       if (args)
4178         {
4179           list = decl_tree_cons (TREE_PURPOSE (t), TREE_VALUE (t), list);
4180           TREE_TYPE (list) = TREE_TYPE (t);
4181         }
4182     }
4183
4184   if (! list)
4185     return NULL_TREE;
4186
4187   t = list;
4188   champ = t;
4189   t = TREE_CHAIN (t);
4190   for (; t; t = TREE_CHAIN (t))
4191     {
4192       fate = more_specialized_class (champ, t);
4193       if (fate == 1)
4194         ;
4195       else
4196         {
4197           if (fate == 0)
4198             {
4199               t = TREE_CHAIN (t);
4200               if (! t)
4201                 return error_mark_node;
4202             }
4203           champ = t;
4204         }
4205     }
4206
4207   for (t = list; t && t != champ; t = TREE_CHAIN (t))
4208     {
4209       fate = more_specialized_class (champ, t);
4210       if (fate != 1)
4211         return error_mark_node;
4212     }
4213
4214   return champ;
4215 }
4216
4217 /* called from the parser.  */
4218
4219 void
4220 do_decl_instantiation (declspecs, declarator, storage)
4221      tree declspecs, declarator, storage;
4222 {
4223   tree decl = grokdeclarator (declarator, declspecs, NORMAL, 0, NULL_TREE);
4224   tree name;
4225   tree fn;
4226   tree result = NULL_TREE;
4227   int extern_p = 0;
4228   tree templates = NULL_TREE;
4229
4230   if (! DECL_LANG_SPECIFIC (decl))
4231     {
4232       cp_error ("explicit instantiation of non-template `%#D'", decl);
4233       return;
4234     }
4235
4236   /* If we've already seen this template instance, use it.  */
4237   if (TREE_CODE (decl) == VAR_DECL)
4238     {
4239       result = lookup_field (DECL_CONTEXT (decl), DECL_NAME (decl), 0, 0);
4240       if (result && TREE_CODE (result) != VAR_DECL)
4241         result = NULL_TREE;
4242     }
4243   else if (TREE_CODE (decl) != FUNCTION_DECL)
4244     {
4245       cp_error ("explicit instantiation of `%#D'", decl);
4246       return;
4247     }
4248   else if (DECL_FUNCTION_MEMBER_P (decl))
4249     {
4250       if (DECL_TEMPLATE_INSTANTIATION (decl))
4251         result = decl;
4252       else if (name = DECL_ASSEMBLER_NAME (decl),
4253                fn = IDENTIFIER_GLOBAL_VALUE (name),
4254                fn && DECL_TEMPLATE_INSTANTIATION (fn))
4255         result = fn;
4256       else
4257         {
4258           /* Maybe this is an instantiation of a member template
4259              function.  */
4260           tree ctype = DECL_CONTEXT (decl);
4261
4262           name = DECL_NAME (decl);
4263           fn = lookup_fnfields (TYPE_BINFO (ctype), name, 1);
4264           if (fn)
4265             fn = TREE_VALUE (fn);
4266
4267           for (; fn; fn = DECL_CHAIN (fn))
4268             if (TREE_CODE (fn) == TEMPLATE_DECL)
4269               templates = decl_tree_cons (NULL_TREE, fn, templates);
4270         }
4271     }
4272   else if (name = DECL_NAME (decl), fn = IDENTIFIER_GLOBAL_VALUE (name), fn)
4273     {
4274       for (fn = get_first_fn (fn); fn; fn = DECL_CHAIN (fn))
4275         if (TREE_CODE (fn) == TEMPLATE_DECL)
4276           templates = decl_tree_cons (NULL_TREE, fn, templates);
4277     }
4278
4279   if (templates && !result)
4280     {
4281       tree args;
4282       result = most_specialized (templates, decl);
4283       if (result == error_mark_node)
4284         {
4285           char *str = "candidates are:";
4286           cp_error ("ambiguous template instantiation for `%D' requested", decl);
4287           for (fn = templates; fn; fn = TREE_CHAIN (fn))
4288             {
4289               cp_error_at ("%s %+#D", str, TREE_VALUE (fn));
4290               str = "               ";
4291             }
4292           return;
4293         }
4294       else if (result)
4295         {
4296           args = get_bindings (result, decl);
4297           result = instantiate_template (result, args);
4298         }
4299     }
4300
4301   if (! result)
4302     {
4303       cp_error ("no matching template for `%D' found", decl);
4304       return;
4305     }
4306
4307   if (! DECL_TEMPLATE_INFO (result))
4308     {
4309       cp_pedwarn ("explicit instantiation of non-template `%#D'", result);
4310       return;
4311     }
4312
4313   if (flag_external_templates)
4314     return;
4315
4316   if (storage == NULL_TREE)
4317     ;
4318   else if (storage == ridpointers[(int) RID_EXTERN])
4319     extern_p = 1;
4320   else
4321     cp_error ("storage class `%D' applied to template instantiation",
4322               storage);
4323
4324   mark_decl_instantiated (result, extern_p);
4325   repo_template_instantiated (result, extern_p);
4326   if (! extern_p)
4327     instantiate_decl (result);
4328 }
4329
4330 void
4331 mark_class_instantiated (t, extern_p)
4332      tree t;
4333      int extern_p;
4334 {
4335   SET_CLASSTYPE_EXPLICIT_INSTANTIATION (t);
4336   SET_CLASSTYPE_INTERFACE_KNOWN (t);
4337   CLASSTYPE_INTERFACE_ONLY (t) = extern_p;
4338   CLASSTYPE_VTABLE_NEEDS_WRITING (t) = ! extern_p;
4339   TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = extern_p;
4340   if (! extern_p)
4341     {
4342       CLASSTYPE_DEBUG_REQUESTED (t) = 1;
4343       rest_of_type_compilation (t, 1);
4344     }
4345 }
4346
4347 void
4348 do_type_instantiation (t, storage)
4349      tree t, storage;
4350 {
4351   int extern_p = 0;
4352   int nomem_p = 0;
4353   int static_p = 0;
4354
4355   if (TREE_CODE (t) == TYPE_DECL)
4356     t = TREE_TYPE (t);
4357
4358   if (! IS_AGGR_TYPE (t) || ! CLASSTYPE_TEMPLATE_INFO (t))
4359     {
4360       cp_error ("explicit instantiation of non-template type `%T'", t);
4361       return;
4362     }
4363
4364   complete_type (t);
4365
4366   /* With -fexternal-templates, explicit instantiations are treated the same
4367      as implicit ones.  */
4368   if (flag_external_templates)
4369     return;
4370
4371   if (TYPE_SIZE (t) == NULL_TREE)
4372     {
4373       cp_error ("explicit instantiation of `%#T' before definition of template",
4374                 t);
4375       return;
4376     }
4377
4378   if (storage == NULL_TREE)
4379     /* OK */;
4380   else if (storage == ridpointers[(int) RID_INLINE])
4381     nomem_p = 1;
4382   else if (storage == ridpointers[(int) RID_EXTERN])
4383     extern_p = 1;
4384   else if (storage == ridpointers[(int) RID_STATIC])
4385     static_p = 1;
4386   else
4387     {
4388       cp_error ("storage class `%D' applied to template instantiation",
4389                 storage);
4390       extern_p = 0;
4391     }
4392
4393   /* We've already instantiated this.  */
4394   if (CLASSTYPE_EXPLICIT_INSTANTIATION (t) && ! CLASSTYPE_INTERFACE_ONLY (t)
4395       && extern_p)
4396     return;
4397
4398   if (! CLASSTYPE_TEMPLATE_SPECIALIZATION (t))
4399     {
4400       mark_class_instantiated (t, extern_p);
4401       repo_template_instantiated (t, extern_p);
4402     }
4403
4404   if (nomem_p)
4405     return;
4406
4407   {
4408     tree tmp;
4409
4410     if (! static_p)
4411       for (tmp = TYPE_METHODS (t); tmp; tmp = TREE_CHAIN (tmp))
4412         if (TREE_CODE (tmp) == FUNCTION_DECL
4413             && DECL_TEMPLATE_INSTANTIATION (tmp))
4414           {
4415             mark_decl_instantiated (tmp, extern_p);
4416             repo_template_instantiated (tmp, extern_p);
4417             if (! extern_p)
4418               instantiate_decl (tmp);
4419           }
4420
4421     for (tmp = TYPE_FIELDS (t); tmp; tmp = TREE_CHAIN (tmp))
4422       if (TREE_CODE (tmp) == VAR_DECL && DECL_TEMPLATE_INSTANTIATION (tmp))
4423         {
4424           mark_decl_instantiated (tmp, extern_p);
4425           repo_template_instantiated (tmp, extern_p);
4426           if (! extern_p)
4427             instantiate_decl (tmp);
4428         }
4429
4430     for (tmp = CLASSTYPE_TAGS (t); tmp; tmp = TREE_CHAIN (tmp))
4431       if (IS_AGGR_TYPE (TREE_VALUE (tmp)))
4432         do_type_instantiation (TYPE_MAIN_DECL (TREE_VALUE (tmp)), storage);
4433   }
4434 }
4435
4436 tree
4437 instantiate_decl (d)
4438      tree d;
4439 {
4440   tree ti = DECL_TEMPLATE_INFO (d);
4441   tree tmpl = TI_TEMPLATE (ti);
4442   tree args = TI_ARGS (ti);
4443   tree td;
4444   tree decl_pattern, code_pattern;
4445   tree save_ti;
4446   int nested = in_function_p ();
4447   int d_defined;
4448   int pattern_defined;
4449   int line = lineno;
4450   char *file = input_filename;
4451
4452   for (td = tmpl; DECL_TEMPLATE_INSTANTIATION (td); )
4453     td = DECL_TI_TEMPLATE (td);
4454
4455   /* In the case of a member template, decl_pattern is the partially
4456      instantiated declaration (in the instantiated class), and code_pattern
4457      is the original template definition.  */
4458   decl_pattern = DECL_TEMPLATE_RESULT (tmpl);
4459   code_pattern = DECL_TEMPLATE_RESULT (td);
4460
4461   if (TREE_CODE (d) == FUNCTION_DECL)
4462     {
4463       d_defined = (DECL_INITIAL (d) != NULL_TREE);
4464       pattern_defined = (DECL_INITIAL (code_pattern) != NULL_TREE);
4465     }
4466   else
4467     {
4468       d_defined = ! DECL_IN_AGGR_P (d);
4469       pattern_defined = ! DECL_IN_AGGR_P (code_pattern);
4470     }
4471
4472   if (d_defined)
4473     return d;
4474
4475   if (TREE_CODE (d) == FUNCTION_DECL)
4476     {
4477       tree specs;
4478
4479       /* Check to see if there is a matching specialization. */
4480       for (specs = DECL_TEMPLATE_SPECIALIZATIONS (tmpl);
4481            specs != NULL_TREE;
4482            specs = TREE_CHAIN (specs))
4483         if (comp_template_args (TREE_PURPOSE (specs), args))
4484           return TREE_VALUE (specs);
4485     }
4486
4487   /* This needs to happen before any tsubsting.  */
4488   if (! push_tinst_level (d))
4489     return d;
4490
4491   push_to_top_level ();
4492   lineno = DECL_SOURCE_LINE (d);
4493   input_filename = DECL_SOURCE_FILE (d);
4494
4495   /* We need to set up DECL_INITIAL regardless of pattern_defined if the
4496      variable is a static const initialized in the class body.  */
4497   if (TREE_CODE (d) == VAR_DECL
4498       && ! DECL_INITIAL (d) && DECL_INITIAL (code_pattern))
4499     {
4500       pushclass (DECL_CONTEXT (d), 2);
4501       DECL_INITIAL (d) = tsubst_expr (DECL_INITIAL (code_pattern), args,
4502                                       TREE_VEC_LENGTH (args), tmpl);
4503       popclass (1);
4504     }
4505
4506   if (pattern_defined)
4507     {
4508       repo_template_used (d);
4509
4510       if (flag_external_templates && ! DECL_INTERFACE_KNOWN (d))
4511         {
4512           if (flag_alt_external_templates)
4513             {
4514               if (interface_unknown)
4515                 warn_if_unknown_interface (d);
4516             }
4517           else if (DECL_INTERFACE_KNOWN (code_pattern))
4518             {
4519               DECL_INTERFACE_KNOWN (d) = 1;
4520               DECL_NOT_REALLY_EXTERN (d) = ! DECL_EXTERNAL (code_pattern);
4521             }
4522           else
4523             warn_if_unknown_interface (code_pattern);
4524         }
4525
4526       if (at_eof)
4527         import_export_decl (d);
4528     }
4529
4530   if (! pattern_defined
4531       || (TREE_CODE (d) == FUNCTION_DECL && ! DECL_INLINE (d)
4532           && (! DECL_INTERFACE_KNOWN (d)
4533               || ! DECL_NOT_REALLY_EXTERN (d)))
4534       /* Kludge: if we compile a constructor in the middle of processing a
4535          toplevel declaration, we blow away the declspecs in
4536          temp_decl_obstack when we call permanent_allocation in
4537          finish_function.  So don't compile it yet.  */
4538       || (TREE_CODE (d) == FUNCTION_DECL && ! nested && ! at_eof))
4539     {
4540       add_pending_template (d);
4541       goto out;
4542     }
4543
4544   lineno = DECL_SOURCE_LINE (d);
4545   input_filename = DECL_SOURCE_FILE (d);
4546
4547   /* Trick tsubst into giving us a new decl in case the template changed.  */
4548   save_ti = DECL_TEMPLATE_INFO (decl_pattern);
4549   DECL_TEMPLATE_INFO (decl_pattern) = NULL_TREE;
4550   td = tsubst (decl_pattern, args, TREE_VEC_LENGTH (args), tmpl);
4551   SET_DECL_IMPLICIT_INSTANTIATION (td);
4552   DECL_TEMPLATE_INFO (decl_pattern) = save_ti;
4553
4554   /* And set up DECL_INITIAL, since tsubst doesn't.  */
4555   if (TREE_CODE (td) == VAR_DECL)
4556     {
4557       pushclass (DECL_CONTEXT (d), 2);
4558       DECL_INITIAL (td) = tsubst_expr (DECL_INITIAL (code_pattern), args,
4559                                        TREE_VEC_LENGTH (args), tmpl);
4560       popclass (1);
4561     }
4562
4563   if (TREE_CODE (d) == FUNCTION_DECL)
4564     {
4565       /* Convince duplicate_decls to use the DECL_ARGUMENTS from the
4566          new decl.  */
4567       DECL_INITIAL (td) = error_mark_node;
4568
4569       if (DECL_TEMPLATE_SPECIALIZATION (td) && !DECL_TEMPLATE_INFO (td))
4570         /* Set up the information about what is being specialized. */
4571         DECL_TEMPLATE_INFO (td) = DECL_TEMPLATE_INFO (d);
4572     }
4573   duplicate_decls (td, d);
4574   if (TREE_CODE (d) == FUNCTION_DECL)
4575     DECL_INITIAL (td) = 0;
4576
4577   if (TREE_CODE (d) == VAR_DECL)
4578     {
4579       DECL_IN_AGGR_P (d) = 0;
4580       if (DECL_INTERFACE_KNOWN (d))
4581         DECL_EXTERNAL (d) = ! DECL_NOT_REALLY_EXTERN (d);
4582       else
4583         {
4584           DECL_EXTERNAL (d) = 1;
4585           DECL_NOT_REALLY_EXTERN (d) = 1;
4586         }
4587       cp_finish_decl (d, DECL_INITIAL (d), NULL_TREE, 0, 0);
4588     }
4589   else if (TREE_CODE (d) == FUNCTION_DECL)
4590     {
4591       tree t = DECL_SAVED_TREE (code_pattern);
4592
4593       start_function (NULL_TREE, d, NULL_TREE, 1);
4594       store_parm_decls ();
4595
4596       if (t && TREE_CODE (t) == RETURN_INIT)
4597         {
4598           store_return_init
4599             (TREE_OPERAND (t, 0),
4600              tsubst_expr (TREE_OPERAND (t, 1), args,
4601                           TREE_VEC_LENGTH (args), tmpl));
4602           t = TREE_CHAIN (t);
4603         }
4604
4605       if (t && TREE_CODE (t) == CTOR_INITIALIZER)
4606         {
4607           current_member_init_list
4608             = tsubst_expr_values (TREE_OPERAND (t, 0), args);
4609           current_base_init_list
4610             = tsubst_expr_values (TREE_OPERAND (t, 1), args);
4611           t = TREE_CHAIN (t);
4612         }
4613
4614       setup_vtbl_ptr ();
4615       /* Always keep the BLOCK node associated with the outermost
4616          pair of curly braces of a function.  These are needed
4617          for correct operation of dwarfout.c.  */
4618       keep_next_level ();
4619
4620       my_friendly_assert (TREE_CODE (t) == COMPOUND_STMT, 42);
4621       tsubst_expr (t, args, TREE_VEC_LENGTH (args), tmpl);
4622
4623       finish_function (lineno, 0, nested);
4624     }
4625
4626 out:
4627   lineno = line;
4628   input_filename = file;
4629
4630   pop_from_top_level ();
4631   pop_tinst_level ();
4632
4633   return d;
4634 }
4635
4636 tree
4637 tsubst_chain (t, argvec)
4638      tree t, argvec;
4639 {
4640   if (t)
4641     {
4642       tree first = tsubst (t, argvec,
4643                            TREE_VEC_LENGTH (argvec), NULL_TREE);
4644       tree last = first;
4645
4646       for (t = TREE_CHAIN (t); t; t = TREE_CHAIN (t))
4647         {
4648           tree x = tsubst (t, argvec, TREE_VEC_LENGTH (argvec), NULL_TREE);
4649           TREE_CHAIN (last) = x;
4650           last = x;
4651         }
4652
4653       return first;
4654     }
4655   return NULL_TREE;
4656 }
4657
4658 static tree
4659 tsubst_expr_values (t, argvec)
4660      tree t, argvec;
4661 {
4662   tree first = NULL_TREE;
4663   tree *p = &first;
4664
4665   for (; t; t = TREE_CHAIN (t))
4666     {
4667       tree pur = tsubst_copy (TREE_PURPOSE (t), argvec,
4668                               TREE_VEC_LENGTH (argvec), NULL_TREE);
4669       tree val = tsubst_expr (TREE_VALUE (t), argvec,
4670                               TREE_VEC_LENGTH (argvec), NULL_TREE);
4671       *p = build_tree_list (pur, val);
4672       p = &TREE_CHAIN (*p);
4673     }
4674   return first;
4675 }
4676
4677 tree last_tree;
4678
4679 void
4680 add_tree (t)
4681      tree t;
4682 {
4683   last_tree = TREE_CHAIN (last_tree) = t;
4684 }
4685
4686 /* D is an undefined function declaration in the presence of templates with
4687    the same name, listed in FNS.  If one of them can produce D as an
4688    instantiation, remember this so we can instantiate it at EOF if D has
4689    not been defined by that time.  */
4690
4691 void
4692 add_maybe_template (d, fns)
4693      tree d, fns;
4694 {
4695   tree t;
4696
4697   if (DECL_MAYBE_TEMPLATE (d))
4698     return;
4699
4700   t = most_specialized (fns, d);
4701   if (! t)
4702     return;
4703   if (t == error_mark_node)
4704     {
4705       cp_error ("ambiguous template instantiation for `%D'", d);
4706       return;
4707     }
4708
4709   *maybe_template_tail = perm_tree_cons (t, d, NULL_TREE);
4710   maybe_template_tail = &TREE_CHAIN (*maybe_template_tail);
4711   DECL_MAYBE_TEMPLATE (d) = 1;
4712 }
4713
4714 /* Instantiate an enumerated type.  Used by instantiate_class_template and
4715    tsubst_expr.  */
4716
4717 static tree
4718 tsubst_enum (tag, args, nargs, field_chain)
4719      tree tag, args;
4720      int nargs;
4721      tree * field_chain;
4722 {
4723   extern tree current_local_enum;
4724   tree prev_local_enum = current_local_enum;
4725
4726   tree newtag = start_enum (TYPE_IDENTIFIER (tag));
4727   tree e, values = NULL_TREE;
4728
4729   for (e = TYPE_VALUES (tag); e; e = TREE_CHAIN (e))
4730     {
4731       tree elt = build_enumerator (TREE_PURPOSE (e),
4732                                    tsubst_expr (TREE_VALUE (e), args,
4733                                                 nargs, NULL_TREE));
4734       TREE_CHAIN (elt) = values;
4735       values = elt;
4736     }
4737
4738   finish_enum (newtag, values);
4739
4740   if (NULL != field_chain)
4741     *field_chain = grok_enum_decls (newtag, NULL_TREE);
4742
4743   current_local_enum = prev_local_enum;
4744
4745   return newtag;
4746 }