gcc/cp/pt.c

   1 /* Handle parameterized types (templates) for GNU C++.
   2    Copyright (C) 1992, 1993 Free Software Foundation, Inc.
   3    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 /* Known bugs or deficiencies include:
  22    * templates for class static data don't work (methods only)
  23    * duplicated method templates can crash the compiler
  24    * interface/impl data is taken from file defining the template
  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    * method templates must be seen before the expansion of the
  28      class template is done
  29  */
  30
  31 #include "config.h"
  32 #include <stdio.h>
  33 #include "obstack.h"
  34
  35 #include "tree.h"
  36 #include "flags.h"
  37 #include "cp-tree.h"
  38 #include "decl.h"
  39 #include "parse.h"
  40 #include "lex.h"
  41
  42 extern struct obstack permanent_obstack;
  43 extern tree grokdeclarator ();
  44
  45 extern int lineno;
  46 extern char *input_filename;
  47 struct pending_inline *pending_template_expansions;
  48
  49 int processing_template_decl;
  50 int processing_template_defn;
  51
  52 #define obstack_chunk_alloc xmalloc
  53 #define obstack_chunk_free free
  54
  55 static int unify ();
  56 static void add_pending_template ();
  57
  58 void overload_template_name (), pop_template_decls ();
  59
  60 /* We've got a template header coming up; set obstacks up to save the
  61    nodes created permanently.  (There might be cases with nested templates
  62    where we don't have to do this, but they aren't implemented, and it
  63    probably wouldn't be worth the effort.)  */
  64 void
  65 begin_template_parm_list ()
  66 {
  67   pushlevel (0);
  68   push_obstacks (&permanent_obstack, &permanent_obstack);
  69   pushlevel (0);
  70 }
  71
  72 /* Process information from new template parameter NEXT and append it to the
  73    LIST being built.  The rules for use of a template parameter type name
  74    by later parameters are not well-defined for us just yet.  However, the
  75    only way to avoid having to parse expressions of unknown complexity (and
  76    with tokens of unknown types) is to disallow it completely.  So for now,
  77    that is what is assumed.  */
  78 tree
  79 process_template_parm (list, next)
  80      tree list, next;
  81 {
  82   tree parm;
  83   tree decl = 0;
  84   int is_type;
  85   parm = next;
  86   my_friendly_assert (TREE_CODE (parm) == TREE_LIST, 259);
  87   is_type = TREE_CODE (TREE_PURPOSE (parm)) == IDENTIFIER_NODE;
  88   if (!is_type)
  89     {
  90       tree tinfo = 0;
  91       parm = TREE_PURPOSE (parm);
  92       my_friendly_assert (TREE_CODE (parm) == TREE_LIST, 260);
  93       parm = TREE_VALUE (parm);
  94       /* is a const-param */
  95       parm = grokdeclarator (TREE_VALUE (next), TREE_PURPOSE (next),
  96                              PARM, 0, NULL_TREE);
  97       /* A template parameter is not modifiable.  */
  98       TREE_READONLY (parm) = 1;
  99       if (TREE_CODE (TREE_TYPE (parm)) == RECORD_TYPE
 100           || TREE_CODE (TREE_TYPE (parm)) == UNION_TYPE)
 101         {
 102           sorry ("aggregate template parameter types");
 103           TREE_TYPE (parm) = void_type_node;
 104         }
 105       tinfo = make_node (TEMPLATE_CONST_PARM);
 106       my_friendly_assert (TREE_PERMANENT (tinfo), 260.5);
 107       if (TREE_PERMANENT (parm) == 0)
 108         {
 109           parm = copy_node (parm);
 110           TREE_PERMANENT (parm) = 1;
 111         }
 112       TREE_TYPE (tinfo) = TREE_TYPE (parm);
 113       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
 114       DECL_INITIAL (decl) = tinfo;
 115       DECL_INITIAL (parm) = tinfo;
 116     }
 117   else
 118     {
 119       tree t = make_node (TEMPLATE_TYPE_PARM);
 120       decl = build_decl (TYPE_DECL, TREE_PURPOSE (parm), t);
 121       TYPE_NAME (t) = decl;
 122       TREE_VALUE (parm) = t;
 123     }
 124   pushdecl (decl);
 125   return chainon (list, parm);
 126 }
 127
 128 /* The end of a template parameter list has been reached.  Process the
 129    tree list into a parameter vector, converting each parameter into a more
 130    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
 131    as PARM_DECLs.  */
 132
 133 tree
 134 end_template_parm_list (parms)
 135      tree parms;
 136 {
 137   int nparms = 0;
 138   tree saved_parmlist;
 139   tree parm;
 140   for (parm = parms; parm; parm = TREE_CHAIN (parm))
 141     nparms++;
 142   saved_parmlist = make_tree_vec (nparms);
 143
 144   for (parm = parms, nparms = 0; parm; parm = TREE_CHAIN (parm), nparms++)
 145     {
 146       tree p = parm;
 147       if (TREE_CODE (p) == TREE_LIST)
 148         {
 149           tree t = TREE_VALUE (p);
 150           TREE_VALUE (p) = NULL_TREE;
 151           p = TREE_PURPOSE (p);
 152           my_friendly_assert (TREE_CODE (p) == IDENTIFIER_NODE, 261);
 153           TEMPLATE_TYPE_SET_INFO (t, saved_parmlist, nparms);
 154         }
 155       else
 156         {
 157           tree tinfo = DECL_INITIAL (p);
 158           DECL_INITIAL (p) = NULL_TREE;
 159           TEMPLATE_CONST_SET_INFO (tinfo, saved_parmlist, nparms);
 160         }
 161       TREE_VEC_ELT (saved_parmlist, nparms) = p;
 162     }
 163   set_current_level_tags_transparency (1);
 164   processing_template_decl++;
 165   return saved_parmlist;
 166 }
 167
 168 /* end_template_decl is called after a template declaration is seen.
 169    D1 is template header; D2 is class_head_sans_basetype or a
 170    TEMPLATE_DECL with its DECL_RESULT field set.  */
 171 void
 172 end_template_decl (d1, d2, is_class, defn)
 173      tree d1, d2, is_class;
 174      int defn;
 175 {
 176   tree decl;
 177   struct template_info *tmpl;
 178
 179   tmpl = (struct template_info *) obstack_alloc (&permanent_obstack,
 180                                             sizeof (struct template_info));
 181   tmpl->text = 0;
 182   tmpl->length = 0;
 183   tmpl->aggr = is_class;
 184
 185   /* cloned from reinit_parse_for_template */
 186   tmpl->filename = input_filename;
 187   tmpl->lineno = lineno;
 188   tmpl->parm_vec = d1;          /* [eichin:19911015.2306EST] */
 189
 190   if (d2 == NULL_TREE || d2 == error_mark_node)
 191     {
 192       decl = 0;
 193       goto lose;
 194     }
 195
 196   if (is_class)
 197     {
 198       decl = build_lang_decl (TEMPLATE_DECL, d2, NULL_TREE);
 199       GNU_xref_decl (current_function_decl, decl);
 200     }
 201   else
 202     {
 203       if (TREE_CODE (d2) == TEMPLATE_DECL)
 204         decl = d2;
 205       else
 206         {
 207           /* Class destructor templates and operator templates are
 208              slipping past as non-template nodes.  Process them here, since
 209              I haven't figured out where to catch them earlier.  I could
 210              go do that, but it's a choice between getting that done and
 211              staying only N months behind schedule.  Sorry....  */
 212           enum tree_code code;
 213           my_friendly_assert (TREE_CODE (d2) == CALL_EXPR, 263);
 214           code = TREE_CODE (TREE_OPERAND (d2, 0));
 215           my_friendly_assert (code == BIT_NOT_EXPR
 216                   || code == OP_IDENTIFIER
 217                   || code == SCOPE_REF, 264);
 218           d2 = grokdeclarator (d2, NULL_TREE, MEMFUNCDEF, 0, NULL_TREE);
 219           decl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (d2),
 220                                   TREE_TYPE (d2));
 221           DECL_TEMPLATE_RESULT (decl) = d2;
 222           DECL_CONTEXT (decl) = DECL_CONTEXT (d2);
 223           DECL_CLASS_CONTEXT (decl) = DECL_CLASS_CONTEXT (d2);
 224           DECL_NAME (decl) = DECL_NAME (d2);
 225           TREE_TYPE (decl) = TREE_TYPE (d2);
 226           if (interface_unknown && flag_external_templates && ! DECL_IN_SYSTEM_HEADER (decl))
 227             warn_if_unknown_interface ();
 228           TREE_PUBLIC (decl) = TREE_PUBLIC (d2) = flag_external_templates && !interface_unknown;
 229           DECL_EXTERNAL (decl) = (DECL_EXTERNAL (d2)
 230                                   && !(DECL_CLASS_CONTEXT (d2)
 231                                        && !DECL_THIS_EXTERN (d2)));
 232         }
 233
 234       /* All routines creating TEMPLATE_DECL nodes should now be using
 235          build_lang_decl, which will have set this up already.  */
 236       my_friendly_assert (DECL_LANG_SPECIFIC (decl) != 0, 265);
 237
 238       /* @@ Somewhere, permanent allocation isn't being used.  */
 239       if (! DECL_TEMPLATE_IS_CLASS (decl)
 240           && TREE_CODE (DECL_TEMPLATE_RESULT (decl)) == FUNCTION_DECL)
 241         {
 242           tree result = DECL_TEMPLATE_RESULT (decl);
 243           /* Will do nothing if allocation was already permanent.  */
 244           DECL_ARGUMENTS (result) = copy_to_permanent (DECL_ARGUMENTS (result));
 245         }
 246
 247       /* If this is for a method, there's an extra binding level here.  */
 248       if (DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl)) != NULL_TREE)
 249         {
 250           /* @@ Find out where this should be getting set!  */
 251           tree r = DECL_TEMPLATE_RESULT (decl);
 252           if (DECL_LANG_SPECIFIC (r) && DECL_CLASS_CONTEXT (r) == NULL_TREE)
 253             DECL_CLASS_CONTEXT (r) = DECL_CONTEXT (r);
 254         }
 255     }
 256   DECL_TEMPLATE_INFO (decl) = tmpl;
 257   DECL_TEMPLATE_PARMS (decl) = d1;
 258
 259   /* So that duplicate_decls can do the right thing.  */
 260   if (defn)
 261     DECL_INITIAL (decl) = error_mark_node;
 262
 263   /* If context of decl is non-null (i.e., method template), add it
 264      to the appropriate class template, and pop the binding levels.  */
 265   if (! is_class && DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl)) != NULL_TREE)
 266     {
 267       tree ctx = DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl));
 268       tree tmpl, t;
 269       my_friendly_assert (TREE_CODE (ctx) == UNINSTANTIATED_P_TYPE, 266);
 270       tmpl = UPT_TEMPLATE (ctx);
 271       for (t = DECL_TEMPLATE_MEMBERS (tmpl); t; t = TREE_CHAIN (t))
 272         if (TREE_PURPOSE (t) == DECL_NAME (decl)
 273             && duplicate_decls (decl, TREE_VALUE (t)))
 274           goto already_there;
 275       DECL_TEMPLATE_MEMBERS (tmpl) =
 276         perm_tree_cons (DECL_NAME (decl), decl, DECL_TEMPLATE_MEMBERS (tmpl));
 277     already_there:
 278       poplevel (0, 0, 0);
 279       poplevel (0, 0, 0);
 280     }
 281   /* Otherwise, go back to top level first, and push the template decl
 282      again there.  */
 283   else
 284     {
 285       poplevel (0, 0, 0);
 286       poplevel (0, 0, 0);
 287       pushdecl (decl);
 288     }
 289  lose:
 290 #if 0 /* It happens sometimes, with syntactic or semantic errors.
 291
 292          One specific case:
 293          template <class A, int X, int Y> class Foo { ... };
 294          template <class A, int X, int y> Foo<X,Y>::method (Foo& x) { ... }
 295          Note the missing "A" in the class containing "method".  */
 296   my_friendly_assert (global_bindings_p (), 267);
 297 #else
 298   while (! global_bindings_p ())
 299     poplevel (0, 0, 0);
 300 #endif
 301   pop_obstacks ();
 302   processing_template_decl--;
 303   (void) get_pending_sizes ();
 304 }
 305
 306 /* If TYPE contains a template parm type, then substitute that type
 307    with its actual type that is found in TVEC. */
 308 static void
 309 grok_template_type (tvec, type)
 310      tree tvec;
 311      tree* type;
 312 {
 313   switch (TREE_CODE (*type))
 314     {
 315     case TEMPLATE_TYPE_PARM:
 316       if (*type != TYPE_MAIN_VARIANT (*type))
 317         {
 318           /* we are here for cases like const T* etc. */
 319           grok_template_type (tvec, &TYPE_MAIN_VARIANT (*type));
 320           *type = build_type_variant (TYPE_MAIN_VARIANT (*type),
 321                                       TYPE_READONLY (*type),
 322                                       TYPE_VOLATILE (*type));
 323         }
 324       else
 325           *type = TREE_VEC_ELT (tvec, TEMPLATE_TYPE_IDX (*type));
 326       return;
 327     case POINTER_TYPE:
 328     case REFERENCE_TYPE:
 329       grok_template_type (tvec, &TREE_TYPE (*type));
 330       return;
 331     case FUNCTION_TYPE:
 332       {
 333         tree p;
 334
 335         /* take care of function's return type first */
 336         grok_template_type (tvec, &TREE_TYPE (*type));
 337
 338         /* take care of function's arguments */
 339         for (p = TYPE_ARG_TYPES (*type); p; p = TREE_CHAIN (p))
 340           grok_template_type (tvec, &TREE_VALUE (p));
 341         return;
 342       }
 343     default:
 344       break;
 345     }
 346   return;
 347 }
 348
 349 /* Convert all template arguments to their appropriate types, and return
 350    a vector containing the resulting values.  If any error occurs, return
 351    error_mark_node.  */
 352 static tree
 353 coerce_template_parms (parms, arglist, in_decl)
 354      tree parms, arglist;
 355      tree in_decl;
 356 {
 357   int nparms, i, lost = 0;
 358   tree vec;
 359
 360   if (TREE_CODE (arglist) == TREE_VEC)
 361     nparms = TREE_VEC_LENGTH (arglist);
 362   else
 363     nparms = list_length (arglist);
 364   if (nparms != TREE_VEC_LENGTH (parms))
 365     {
 366       error ("incorrect number of parameters (%d, should be %d)",
 367              nparms, TREE_VEC_LENGTH (parms));
 368       if (in_decl)
 369         cp_error_at ("in template expansion for decl `%D'", in_decl);
 370       return error_mark_node;
 371     }
 372
 373   if (TREE_CODE (arglist) == TREE_VEC)
 374     vec = copy_node (arglist);
 375   else
 376     {
 377       vec = make_tree_vec (nparms);
 378       for (i = 0; i < nparms; i++)
 379         {
 380           tree arg = arglist;
 381           arglist = TREE_CHAIN (arglist);
 382           if (arg == error_mark_node)
 383             lost++;
 384           else
 385             arg = TREE_VALUE (arg);
 386           TREE_VEC_ELT (vec, i) = arg;
 387         }
 388     }
 389   for (i = 0; i < nparms; i++)
 390     {
 391       tree arg = TREE_VEC_ELT (vec, i);
 392       tree parm = TREE_VEC_ELT (parms, i);
 393       tree val = 0;
 394       int is_type, requires_type;
 395
 396       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
 397       requires_type = TREE_CODE (parm) == IDENTIFIER_NODE;
 398       if (is_type != requires_type)
 399         {
 400           if (in_decl)
 401             cp_error_at ("type/value mismatch in template parameter list for `%D'", in_decl);
 402           lost++;
 403           TREE_VEC_ELT (vec, i) = error_mark_node;
 404           continue;
 405         }
 406       if (is_type)
 407         val = groktypename (arg);
 408       else if (TREE_CODE (arg) == STRING_CST)
 409         {
 410           cp_error ("string literal %E is not a valid template argument", arg);
 411           error ("because it is the address of an object with static linkage");
 412           val = error_mark_node;
 413         }
 414       else
 415         {
 416           grok_template_type (vec, &TREE_TYPE (parm));
 417           val = digest_init (TREE_TYPE (parm), arg, (tree *) 0);
 418
 419           if (val == error_mark_node)
 420             ;
 421
 422           /* 14.2: Other template-arguments must be constant-expressions,
 423              addresses of objects or functions with external linkage, or of
 424              static class members.  */
 425           else if (!TREE_CONSTANT (val))
 426             {
 427               cp_error ("non-const `%E' cannot be used as template argument",
 428                         arg);
 429               val = error_mark_node;
 430             }
 431           else if (TREE_CODE (val) == ADDR_EXPR)
 432             {
 433               tree a = TREE_OPERAND (val, 0);
 434               if ((TREE_CODE (a) == VAR_DECL
 435                    || TREE_CODE (a) == FUNCTION_DECL)
 436                   && !TREE_PUBLIC (a))
 437                 {
 438                   cp_error ("address of non-extern `%E' cannot be used as template argument", a);
 439                   val = error_mark_node;
 440                 }
 441             }
 442         }
 443
 444       if (val == error_mark_node)
 445         lost++;
 446
 447       TREE_VEC_ELT (vec, i) = val;
 448     }
 449   if (lost)
 450     return error_mark_node;
 451   return vec;
 452 }
 453
 454 /* Given class template name and parameter list, produce a user-friendly name
 455    for the instantiation.  */
 456 static char *
 457 mangle_class_name_for_template (name, parms, arglist)
 458      char *name;
 459      tree parms, arglist;
 460 {
 461   static struct obstack scratch_obstack;
 462   static char *scratch_firstobj;
 463   int i, nparms;
 464
 465   if (!scratch_firstobj)
 466     {
 467       gcc_obstack_init (&scratch_obstack);
 468       scratch_firstobj = obstack_alloc (&scratch_obstack, 1);
 469     }
 470   else
 471     obstack_free (&scratch_obstack, scratch_firstobj);
 472
 473 #if 0
 474 #define buflen  sizeof(buf)
 475 #define check   if (bufp >= buf+buflen-1) goto too_long
 476 #define ccat(c) *bufp++=(c); check
 477 #define advance bufp+=strlen(bufp); check
 478 #define cat(s)  strncpy(bufp, s, buf+buflen-bufp-1); advance
 479 #else
 480 #define check
 481 #define ccat(c) obstack_1grow (&scratch_obstack, (c));
 482 #define advance
 483 #define cat(s)  obstack_grow (&scratch_obstack, (s), strlen (s))
 484 #endif
 485
 486   cat (name);
 487   ccat ('<');
 488   nparms = TREE_VEC_LENGTH (parms);
 489   my_friendly_assert (nparms == TREE_VEC_LENGTH (arglist), 268);
 490   for (i = 0; i < nparms; i++)
 491     {
 492       tree parm = TREE_VEC_ELT (parms, i), arg = TREE_VEC_ELT (arglist, i);
 493
 494       if (i)
 495         ccat (',');
 496
 497       if (TREE_CODE (parm) == IDENTIFIER_NODE)
 498         {
 499           cat (type_as_string (arg, 0));
 500           continue;
 501         }
 502       else
 503         my_friendly_assert (TREE_CODE (parm) == PARM_DECL, 269);
 504
 505       if (TREE_CODE (arg) == TREE_LIST)
 506         {
 507           /* New list cell was built because old chain link was in
 508              use.  */
 509           my_friendly_assert (TREE_PURPOSE (arg) == NULL_TREE, 270);
 510           arg = TREE_VALUE (arg);
 511         }
 512       /* No need to check arglist against parmlist here; we did that
 513          in coerce_template_parms, called from lookup_template_class.  */
 514       cat (expr_as_string (arg, 0));
 515     }
 516   {
 517     char *bufp = obstack_next_free (&scratch_obstack);
 518     int offset = 0;
 519     while (bufp[offset - 1] == ' ')
 520       offset--;
 521     obstack_blank_fast (&scratch_obstack, offset);
 522
 523     /* B<C<char> >, not B<C<char>> */
 524     if (bufp[offset - 1] == '>')
 525       ccat (' ');
 526   }
 527   ccat ('>');
 528   ccat ('\0');
 529   return (char *) obstack_base (&scratch_obstack);
 530
 531 #if 0
 532  too_long:
 533 #endif
 534   fatal ("out of (preallocated) string space creating template instantiation name");
 535   /* NOTREACHED */
 536   return NULL;
 537 }
 538
 539 /* Given an IDENTIFIER_NODE (type TEMPLATE_DECL) and a chain of
 540    parameters, find the desired type.
 541
 542    D1 is the PTYPENAME terminal, and ARGLIST is the list of arguments.
 543    Since ARGLIST is build on the decl_obstack, we must copy it here
 544    to keep it from being reclaimed when the decl storage is reclaimed.
 545
 546    IN_DECL, if non-NULL, is the template declaration we are trying to
 547    instantiate.  */
 548 tree
 549 lookup_template_class (d1, arglist, in_decl)
 550      tree d1, arglist;
 551      tree in_decl;
 552 {
 553   tree template, parmlist;
 554   char *mangled_name;
 555   tree id;
 556
 557   my_friendly_assert (TREE_CODE (d1) == IDENTIFIER_NODE, 272);
 558   template = IDENTIFIER_GLOBAL_VALUE (d1); /* XXX */
 559   if (! template)
 560     template = IDENTIFIER_CLASS_VALUE (d1);
 561   /* With something like `template <class T> class X class X { ... };'
 562      we could end up with D1 having nothing but an IDENTIFIER_LOCAL_VALUE.
 563      We don't want to do that, but we have to deal with the situation, so
 564      let's give them some syntax errors to chew on instead of a crash.  */
 565   if (! template)
 566     return error_mark_node;
 567   if (TREE_CODE (template) != TEMPLATE_DECL)
 568     {
 569       cp_error ("non-template type `%T' used as a template", d1);
 570       if (in_decl)
 571         cp_error_at ("for template declaration `%D'", in_decl);
 572       return error_mark_node;
 573     }
 574   parmlist = DECL_TEMPLATE_PARMS (template);
 575
 576   arglist = coerce_template_parms (parmlist, arglist, in_decl);
 577   if (arglist == error_mark_node)
 578     return error_mark_node;
 579   if (uses_template_parms (arglist))
 580     {
 581       tree t = make_lang_type (UNINSTANTIATED_P_TYPE);
 582       tree d;
 583       id = make_anon_name ();
 584       d = build_decl (TYPE_DECL, id, t);
 585       TYPE_NAME (t) = d;
 586       TYPE_VALUES (t) = build_tree_list (template, arglist);
 587       pushdecl_top_level (d);
 588     }
 589   else
 590     {
 591       mangled_name = mangle_class_name_for_template (IDENTIFIER_POINTER (d1),
 592                                                      parmlist, arglist);
 593       id = get_identifier (mangled_name);
 594     }
 595   if (!IDENTIFIER_TEMPLATE (id))
 596     {
 597       arglist = copy_to_permanent (arglist);
 598       IDENTIFIER_TEMPLATE (id) = perm_tree_cons (template, arglist, NULL_TREE);
 599     }
 600   return id;
 601 }
 602 \f
 603 void
 604 push_template_decls (parmlist, arglist, class_level)
 605      tree parmlist, arglist;
 606      int class_level;
 607 {
 608   int i, nparms;
 609
 610   /* Don't want to push values into global context.  */
 611   if (!class_level)
 612     {
 613       pushlevel (1);
 614       declare_pseudo_global_level ();
 615     }
 616
 617   nparms = TREE_VEC_LENGTH (parmlist);
 618
 619   for (i = 0; i < nparms; i++)
 620     {
 621       int requires_type, is_type;
 622       tree parm = TREE_VEC_ELT (parmlist, i);
 623       tree arg = TREE_VEC_ELT (arglist, i);
 624       tree decl = 0;
 625
 626       requires_type = TREE_CODE (parm) == IDENTIFIER_NODE;
 627       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
 628       if (is_type)
 629         {
 630           /* add typename to namespace */
 631           if (!requires_type)
 632             {
 633               error ("template use error: type provided where value needed");
 634               continue;
 635             }
 636           decl = arg;
 637           my_friendly_assert (TREE_CODE_CLASS (TREE_CODE (decl)) == 't', 273);
 638           decl = build_decl (TYPE_DECL, parm, decl);
 639         }
 640       else
 641         {
 642           /* add const decl to namespace */
 643           tree val;
 644           if (requires_type)
 645             {
 646               error ("template use error: value provided where type needed");
 647               continue;
 648             }
 649           val = digest_init (TREE_TYPE (parm), arg, (tree *) 0);
 650           if (val != error_mark_node)
 651             {
 652               decl = build_decl (VAR_DECL, DECL_NAME (parm), TREE_TYPE (parm));
 653               DECL_INITIAL (decl) = val;
 654               TREE_READONLY (decl) = 1;
 655             }
 656         }
 657       if (decl != 0)
 658         {
 659           layout_decl (decl, 0);
 660           if (class_level)
 661             pushdecl_class_level (decl);
 662           else
 663             pushdecl (decl);
 664         }
 665     }
 666 }
 667
 668 void
 669 pop_template_decls (parmlist, arglist, class_level)
 670      tree parmlist, arglist;
 671      int class_level;
 672 {
 673   if (!class_level)
 674     poplevel (0, 0, 0);
 675 }
 676 \f
 677 /* Should be defined in parse.h.  */
 678 extern int yychar;
 679
 680 int
 681 uses_template_parms (t)
 682      tree t;
 683 {
 684   if (!t)
 685     return 0;
 686   switch (TREE_CODE (t))
 687     {
 688     case INDIRECT_REF:
 689     case COMPONENT_REF:
 690       /* We assume that the object must be instantiated in order to build
 691          the COMPONENT_REF, so we test only whether the type of the
 692          COMPONENT_REF uses template parms.  */
 693       return uses_template_parms (TREE_TYPE (t));
 694
 695     case IDENTIFIER_NODE:
 696       if (!IDENTIFIER_TEMPLATE (t))
 697         return 0;
 698       return uses_template_parms (TREE_VALUE (IDENTIFIER_TEMPLATE (t)));
 699
 700       /* aggregates of tree nodes */
 701     case TREE_VEC:
 702       {
 703         int i = TREE_VEC_LENGTH (t);
 704         while (i--)
 705           if (uses_template_parms (TREE_VEC_ELT (t, i)))
 706             return 1;
 707         return 0;
 708       }
 709     case TREE_LIST:
 710       if (uses_template_parms (TREE_PURPOSE (t))
 711           || uses_template_parms (TREE_VALUE (t)))
 712         return 1;
 713       return uses_template_parms (TREE_CHAIN (t));
 714
 715       /* constructed type nodes */
 716     case POINTER_TYPE:
 717     case REFERENCE_TYPE:
 718       return uses_template_parms (TREE_TYPE (t));
 719     case RECORD_TYPE:
 720     case UNION_TYPE:
 721       if (!TYPE_NAME (t))
 722         return 0;
 723       if (!TYPE_IDENTIFIER (t))
 724         return 0;
 725       return uses_template_parms (TYPE_IDENTIFIER (t));
 726     case FUNCTION_TYPE:
 727       if (uses_template_parms (TYPE_ARG_TYPES (t)))
 728         return 1;
 729       return uses_template_parms (TREE_TYPE (t));
 730     case ARRAY_TYPE:
 731       if (uses_template_parms (TYPE_DOMAIN (t)))
 732         return 1;
 733       return uses_template_parms (TREE_TYPE (t));
 734     case OFFSET_TYPE:
 735       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
 736         return 1;
 737       return uses_template_parms (TREE_TYPE (t));
 738     case METHOD_TYPE:
 739       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
 740         return 1;
 741       if (uses_template_parms (TYPE_ARG_TYPES (t)))
 742         return 1;
 743       return uses_template_parms (TREE_TYPE (t));
 744
 745       /* decl nodes */
 746     case TYPE_DECL:
 747       return uses_template_parms (DECL_NAME (t));
 748     case FUNCTION_DECL:
 749       if (uses_template_parms (TREE_TYPE (t)))
 750         return 1;
 751       /* fall through */
 752     case VAR_DECL:
 753     case PARM_DECL:
 754       /* ??? What about FIELD_DECLs?  */
 755       /* The type of a decl can't use template parms if the name of the
 756          variable doesn't, because it's impossible to resolve them.  So
 757          ignore the type field for now.  */
 758       if (DECL_CONTEXT (t) && uses_template_parms (DECL_CONTEXT (t)))
 759         return 1;
 760       if (uses_template_parms (TREE_TYPE (t)))
 761         {
 762           error ("template parms used where they can't be resolved");
 763         }
 764       return 0;
 765
 766     case CALL_EXPR:
 767       return uses_template_parms (TREE_TYPE (t));
 768     case ADDR_EXPR:
 769       return uses_template_parms (TREE_OPERAND (t, 0));
 770
 771       /* template parm nodes */
 772     case TEMPLATE_TYPE_PARM:
 773     case TEMPLATE_CONST_PARM:
 774       return 1;
 775
 776       /* simple type nodes */
 777     case INTEGER_TYPE:
 778       if (uses_template_parms (TYPE_MIN_VALUE (t)))
 779         return 1;
 780       return uses_template_parms (TYPE_MAX_VALUE (t));
 781
 782     case REAL_TYPE:
 783     case VOID_TYPE:
 784     case ENUMERAL_TYPE:
 785     case BOOLEAN_TYPE:
 786       return 0;
 787
 788       /* constants */
 789     case INTEGER_CST:
 790     case REAL_CST:
 791     case STRING_CST:
 792       return 0;
 793
 794     case ERROR_MARK:
 795       /* Non-error_mark_node ERROR_MARKs are bad things.  */
 796       my_friendly_assert (t == error_mark_node, 274);
 797       /* NOTREACHED */
 798       return 0;
 799
 800     case UNINSTANTIATED_P_TYPE:
 801       return 1;
 802
 803     default:
 804       switch (TREE_CODE_CLASS (TREE_CODE (t)))
 805         {
 806         case '1':
 807         case '2':
 808         case '3':
 809         case '<':
 810           {
 811             int i;
 812             for (i = tree_code_length[(int) TREE_CODE (t)]; --i >= 0;)
 813               if (uses_template_parms (TREE_OPERAND (t, i)))
 814                 return 1;
 815             return 0;
 816           }
 817         default:
 818           break;
 819         }
 820       sorry ("testing %s for template parms",
 821              tree_code_name [(int) TREE_CODE (t)]);
 822       my_friendly_abort (82);
 823       /* NOTREACHED */
 824       return 0;
 825     }
 826 }
 827
 828 void
 829 instantiate_member_templates (classname)
 830      tree classname;
 831 {
 832   tree t;
 833   tree id = classname;
 834   tree members = DECL_TEMPLATE_MEMBERS (TREE_PURPOSE (IDENTIFIER_TEMPLATE (id)));
 835
 836   for (t = members; t; t = TREE_CHAIN (t))
 837     {
 838       tree parmvec, type, classparms, tdecl, t2;
 839       int nparms, xxx = 0, i;
 840
 841       my_friendly_assert (TREE_VALUE (t) != NULL_TREE, 275);
 842       my_friendly_assert (TREE_CODE (TREE_VALUE (t)) == TEMPLATE_DECL, 276);
 843       /* @@ Should verify that class parm list is a list of
 844          distinct template parameters, and covers all the template
 845          parameters.  */
 846       tdecl = TREE_VALUE (t);
 847       type = DECL_CONTEXT (DECL_TEMPLATE_RESULT (tdecl));
 848       classparms = UPT_PARMS (type);
 849       nparms = TREE_VEC_LENGTH (classparms);
 850       parmvec = make_tree_vec (nparms);
 851       for (i = 0; i < nparms; i++)
 852         TREE_VEC_ELT (parmvec, i) = NULL_TREE;
 853       switch (unify (DECL_TEMPLATE_PARMS (tdecl),
 854                      &TREE_VEC_ELT (parmvec, 0), nparms,
 855                      type, IDENTIFIER_TYPE_VALUE (classname),
 856                      &xxx))
 857         {
 858         case 0:
 859           /* Success -- well, no inconsistency, at least.  */
 860           for (i = 0; i < nparms; i++)
 861             if (TREE_VEC_ELT (parmvec, i) == NULL_TREE)
 862               goto failure;
 863           t2 = instantiate_template (tdecl,
 864                                      &TREE_VEC_ELT (parmvec, 0));
 865           type = IDENTIFIER_TYPE_VALUE (id);
 866           my_friendly_assert (type != 0, 277);
 867           if (CLASSTYPE_INTERFACE_UNKNOWN (type))
 868             {
 869               DECL_EXTERNAL (t2) = 0;
 870               TREE_PUBLIC (t2) = 0;
 871             }
 872           else
 873             {
 874               DECL_EXTERNAL (t2) = CLASSTYPE_INTERFACE_ONLY (type);
 875               TREE_PUBLIC (t2) = 1;
 876             }
 877           break;
 878         case 1:
 879           /* Failure.  */
 880         failure:
 881           cp_error ("type unification error instantiating %T::%D",
 882                       classname, tdecl);
 883           cp_error_at ("for template declaration `%D'", tdecl);
 884
 885           continue /* loop of members */;
 886         default:
 887           /* Eek, a bug.  */
 888           my_friendly_abort (83);
 889         }
 890     }
 891 }
 892
 893 struct tinst_level *current_tinst_level = 0;
 894 struct tinst_level *free_tinst_level = 0;
 895
 896 void
 897 push_tinst_level (name)
 898      tree name;
 899 {
 900   struct tinst_level *new;
 901   tree global = IDENTIFIER_GLOBAL_VALUE (name);
 902
 903   if (free_tinst_level)
 904     {
 905       new = free_tinst_level;
 906       free_tinst_level = new->next;
 907     }
 908   else
 909     new = (struct tinst_level *) xmalloc (sizeof (struct tinst_level));
 910
 911   new->classname = name;
 912   if (global)
 913     {
 914       new->line = DECL_SOURCE_LINE (global);
 915       new->file = DECL_SOURCE_FILE (global);
 916     }
 917   else
 918     {
 919       new->line = lineno;
 920       new->file = input_filename;
 921     }
 922   new->next = current_tinst_level;
 923   current_tinst_level = new;
 924 }
 925
 926 void
 927 pop_tinst_level ()
 928 {
 929   struct tinst_level *old = current_tinst_level;
 930
 931   current_tinst_level = old->next;
 932   old->next = free_tinst_level;
 933   free_tinst_level = old;
 934 }
 935
 936 struct tinst_level *
 937 tinst_for_decl ()
 938 {
 939   struct tinst_level *p = current_tinst_level;
 940
 941   if (p)
 942     for (; p->next ; p = p->next )
 943       ;
 944   return p;
 945 }
 946
 947 tree
 948 instantiate_class_template (classname, setup_parse)
 949      tree classname;
 950      int setup_parse;
 951 {
 952   struct template_info *template_info;
 953   tree template, t1;
 954
 955   if (classname == error_mark_node)
 956     return error_mark_node;
 957
 958   my_friendly_assert (TREE_CODE (classname) == IDENTIFIER_NODE, 278);
 959   template = IDENTIFIER_TEMPLATE (classname);
 960
 961   if (IDENTIFIER_HAS_TYPE_VALUE (classname))
 962     {
 963       tree type = IDENTIFIER_TYPE_VALUE (classname);
 964       if (TREE_CODE (type) == UNINSTANTIATED_P_TYPE)
 965         return type;
 966       if (TYPE_BEING_DEFINED (type)
 967           || TYPE_SIZE (type)
 968           || CLASSTYPE_USE_TEMPLATE (type) != 0)
 969         return type;
 970     }
 971
 972   /* If IDENTIFIER_LOCAL_VALUE is already set on this template classname
 973      (it's something like `foo<int>'), that means we're already working on
 974      the instantiation for it.  Normally, a classname comes in with nothing
 975      but its IDENTIFIER_TEMPLATE slot set.  If we were to try to instantiate
 976      this again, we'd get a redeclaration error.  Since we're already working
 977      on it, we'll pass back this classname's TYPE_DECL (it's the value of
 978      the classname's IDENTIFIER_LOCAL_VALUE).  Only do this if we're setting
 979      things up for the parser, though---if we're just trying to instantiate
 980      it (e.g., via tsubst) we can trip up cuz it may not have an
 981      IDENTIFIER_TYPE_VALUE when it will need one.  */
 982   if (setup_parse && IDENTIFIER_LOCAL_VALUE (classname))
 983     return IDENTIFIER_LOCAL_VALUE (classname);
 984
 985   if (uses_template_parms (classname))
 986     {
 987       if (!TREE_TYPE (classname))
 988         {
 989           tree t = make_lang_type (RECORD_TYPE);
 990           tree d = build_decl (TYPE_DECL, classname, t);
 991           DECL_NAME (d) = classname;
 992           TYPE_NAME (t) = d;
 993           pushdecl (d);
 994         }
 995       return NULL_TREE;
 996     }
 997
 998   t1 = TREE_PURPOSE (template);
 999   my_friendly_assert (TREE_CODE (t1) == TEMPLATE_DECL, 279);
1000
1001   /* If a template is declared but not defined, accept it; don't crash.
1002      Later uses requiring the definition will be flagged as errors by
1003      other code.  Thanks to niklas@appli.se for this bug fix.  */
1004   if (DECL_TEMPLATE_INFO (t1)->text == 0)
1005     setup_parse = 0;
1006
1007   push_to_top_level ();
1008   template_info = DECL_TEMPLATE_INFO (t1);
1009   if (setup_parse)
1010     {
1011       push_tinst_level (classname);
1012       push_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (template)),
1013                            TREE_VALUE (template), 0);
1014       set_current_level_tags_transparency (1);
1015       feed_input (template_info->text, template_info->length, (struct obstack *)0);
1016       lineno = template_info->lineno;
1017       input_filename = template_info->filename;
1018       /* Get interface/implementation back in sync.  */
1019       extract_interface_info ();
1020       overload_template_name (classname, 0);
1021       /* Kludge so that we don't get screwed by our own base classes.  */
1022       TYPE_BEING_DEFINED (TREE_TYPE (classname)) = 1;
1023       yychar = PRE_PARSED_CLASS_DECL;
1024       yylval.ttype = classname;
1025       processing_template_defn++;
1026       if (!flag_external_templates)
1027         interface_unknown++;
1028     }
1029   else
1030     {
1031       tree t, decl, id, tmpl;
1032
1033       id = classname;
1034       tmpl = TREE_PURPOSE (IDENTIFIER_TEMPLATE (id));
1035       t = xref_tag (DECL_TEMPLATE_INFO (tmpl)->aggr, id, NULL_TREE, 0);
1036       my_friendly_assert (TREE_CODE (t) == RECORD_TYPE
1037                           || TREE_CODE (t) == UNION_TYPE, 280);
1038
1039       /* Now, put a copy of the decl in global scope, to avoid
1040        * recursive expansion.  */
1041       decl = IDENTIFIER_LOCAL_VALUE (id);
1042       if (!decl)
1043         decl = IDENTIFIER_CLASS_VALUE (id);
1044       if (decl)
1045         {
1046           my_friendly_assert (TREE_CODE (decl) == TYPE_DECL, 281);
1047           /* We'd better make sure we're on the permanent obstack or else
1048            * we'll get a "friendly" abort 124 in pushdecl.  Perhaps a
1049            * copy_to_permanent would be sufficient here, but then a
1050            * sharing problem might occur.  I don't know -- niklas@appli.se */
1051           push_obstacks (&permanent_obstack, &permanent_obstack);
1052           pushdecl_top_level (copy_node (decl));
1053           pop_obstacks ();
1054         }
1055       pop_from_top_level ();
1056     }
1057
1058   return NULL_TREE;
1059 }
1060
1061 static int
1062 list_eq (t1, t2)
1063      tree t1, t2;
1064 {
1065   if (t1 == NULL_TREE)
1066     return t2 == NULL_TREE;
1067   if (t2 == NULL_TREE)
1068     return 0;
1069   /* Don't care if one declares its arg const and the other doesn't -- the
1070      main variant of the arg type is all that matters.  */
1071   if (TYPE_MAIN_VARIANT (TREE_VALUE (t1))
1072       != TYPE_MAIN_VARIANT (TREE_VALUE (t2)))
1073     return 0;
1074   return list_eq (TREE_CHAIN (t1), TREE_CHAIN (t2));
1075 }
1076
1077 static tree
1078 lookup_nested_type_by_name (ctype, name)
1079         tree ctype, name;
1080 {
1081   tree t;
1082
1083   t = TREE_VALUE(CLASSTYPE_TAGS(ctype));
1084   while (t)
1085   {
1086     if (strcmp(IDENTIFIER_POINTER(name), IDENTIFIER_POINTER(TYPE_IDENTIFIER(t)))
1087  == 0)
1088       return t;
1089     else
1090       t = TREE_CHAIN(t);
1091   }
1092   return NULL_TREE;
1093 }
1094
1095 static tree
1096 search_nested_type_in_tmpl (tmpl, type)
1097         tree tmpl, type;
1098 {
1099   tree t;
1100
1101   if (tmpl == NULL || TYPE_CONTEXT(type) == NULL)
1102     return tmpl;
1103   t = search_nested_type_in_tmpl (tmpl, TYPE_CONTEXT(type));
1104   if (t == NULL) return t;
1105   t = lookup_nested_type_by_name(t, DECL_NAME(TYPE_NAME(type)));
1106   return t;
1107 }
1108
1109 static tree
1110 tsubst (t, args, nargs, in_decl)
1111      tree t, *args;
1112      int nargs;
1113      tree in_decl;
1114 {
1115   tree type;
1116
1117   if (t == NULL_TREE || t == error_mark_node)
1118     return t;
1119
1120   type = TREE_TYPE (t);
1121   if (type
1122       /* Minor optimization.
1123          ?? Are these really the most frequent cases?  Is the savings
1124          significant?  */
1125       && type != integer_type_node
1126       && type != void_type_node
1127       && type != char_type_node)
1128     type = build_type_variant (tsubst (type, args, nargs, in_decl),
1129                                TYPE_READONLY (type),
1130                                TYPE_VOLATILE (type));
1131   switch (TREE_CODE (t))
1132     {
1133     case RECORD_TYPE:
1134       if (TYPE_PTRMEMFUNC_P (t))
1135         return build_ptrmemfunc_type
1136           (tsubst (TYPE_PTRMEMFUNC_FN_TYPE (t), args, nargs, in_decl));
1137
1138       /* else fall through */
1139
1140     case ERROR_MARK:
1141     case IDENTIFIER_NODE:
1142     case OP_IDENTIFIER:
1143     case VOID_TYPE:
1144     case REAL_TYPE:
1145     case ENUMERAL_TYPE:
1146     case BOOLEAN_TYPE:
1147     case INTEGER_CST:
1148     case REAL_CST:
1149     case STRING_CST:
1150     case UNION_TYPE:
1151       return t;
1152
1153     case INTEGER_TYPE:
1154       if (t == integer_type_node)
1155         return t;
1156
1157       if (TREE_CODE (TYPE_MIN_VALUE (t)) == INTEGER_CST
1158           && TREE_CODE (TYPE_MAX_VALUE (t)) == INTEGER_CST)
1159         return t;
1160       return build_index_2_type
1161         (tsubst (TYPE_MIN_VALUE (t), args, nargs, in_decl),
1162          tsubst (TYPE_MAX_VALUE (t), args, nargs, in_decl));
1163
1164     case TEMPLATE_TYPE_PARM:
1165       return build_type_variant (args[TEMPLATE_TYPE_IDX (t)],
1166                                  TYPE_READONLY (t),
1167                                  TYPE_VOLATILE (t));
1168
1169     case TEMPLATE_CONST_PARM:
1170       return args[TEMPLATE_CONST_IDX (t)];
1171
1172     case FUNCTION_DECL:
1173       {
1174         tree r;
1175         tree fnargs, result;
1176
1177         if (type == TREE_TYPE (t)
1178             && (DECL_CONTEXT (t) == NULL_TREE
1179                 || TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) != 't'))
1180           return t;
1181         fnargs = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
1182         result = tsubst (DECL_RESULT (t), args, nargs, t);
1183         if (DECL_CONTEXT (t) != NULL_TREE
1184             && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't')
1185           {
1186             /* Look it up in that class, and return the decl node there,
1187                instead of creating a new one.  */
1188             tree ctx, methods, name, method;
1189             int n_methods;
1190             int i, found = 0;
1191
1192             name = DECL_NAME (t);
1193             ctx = tsubst (DECL_CONTEXT (t), args, nargs, t);
1194             methods = CLASSTYPE_METHOD_VEC (ctx);
1195             if (methods == NULL_TREE)
1196               /* No methods at all -- no way this one can match.  */
1197               goto no_match;
1198             n_methods = TREE_VEC_LENGTH (methods);
1199
1200             r = NULL_TREE;
1201
1202             if (!strncmp (OPERATOR_TYPENAME_FORMAT,
1203                           IDENTIFIER_POINTER (name),
1204                           sizeof (OPERATOR_TYPENAME_FORMAT) - 1))
1205               {
1206                 /* Type-conversion operator.  Reconstruct the name, in
1207                    case it's the name of one of the template's parameters.  */
1208                 name = build_typename_overload (TREE_TYPE (type));
1209               }
1210
1211             if (DECL_CONTEXT (t) != NULL_TREE
1212                 && TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) == 't'
1213                 && constructor_name (DECL_CONTEXT (t)) == DECL_NAME (t))
1214               name = constructor_name (ctx);
1215 #if 0
1216             fprintf (stderr, "\nfor function %s in class %s:\n",
1217                      IDENTIFIER_POINTER (name),
1218                      IDENTIFIER_POINTER (TYPE_IDENTIFIER (ctx)));
1219 #endif
1220             for (i = 0; i < n_methods; i++)
1221               {
1222                 int pass;
1223
1224                 method = TREE_VEC_ELT (methods, i);
1225                 if (method == NULL_TREE || DECL_NAME (method) != name)
1226                   continue;
1227
1228                 pass = 0;
1229               maybe_error:
1230                 for (; method; method = DECL_CHAIN (method))
1231                   {
1232                     my_friendly_assert (TREE_CODE (method) == FUNCTION_DECL,
1233                                         282);
1234                     if (! comptypes (type, TREE_TYPE (method), 1))
1235                       {
1236                         tree mtype = TREE_TYPE (method);
1237                         tree t1, t2;
1238
1239                         /* Keep looking for a method that matches
1240                            perfectly.  This takes care of the problem
1241                            where destructors (which have implicit int args)
1242                            look like constructors which have an int arg.  */
1243                         if (pass == 0)
1244                           continue;
1245
1246                         t1 = TYPE_ARG_TYPES (mtype);
1247                         t2 = TYPE_ARG_TYPES (type);
1248                         if (TREE_CODE (mtype) == FUNCTION_TYPE)
1249                           t2 = TREE_CHAIN (t2);
1250
1251                         if (list_eq (t1, t2))
1252                           {
1253                             if (TREE_CODE (mtype) == FUNCTION_TYPE)
1254                               {
1255                                 tree newtype;
1256                                 newtype = build_function_type (TREE_TYPE (type),
1257                                                                TYPE_ARG_TYPES (type));
1258                                 newtype = build_type_variant (newtype,
1259                                                               TYPE_READONLY (type),
1260                                                               TYPE_VOLATILE (type));
1261                                 type = newtype;
1262                                 if (TREE_TYPE (type) != TREE_TYPE (mtype))
1263                                   goto maybe_bad_return_type;
1264                               }
1265                             else if (TYPE_METHOD_BASETYPE (mtype)
1266                                      == TYPE_METHOD_BASETYPE (type))
1267                               {
1268                                 /* Types didn't match, but arg types and
1269                                    `this' do match, so the return type is
1270                                    all that should be messing it up.  */
1271                               maybe_bad_return_type:
1272                                 if (TREE_TYPE (type) != TREE_TYPE (mtype))
1273                                   error ("inconsistent return types for method `%s' in class `%s'",
1274                                          IDENTIFIER_POINTER (name),
1275                                          IDENTIFIER_POINTER (TYPE_IDENTIFIER (ctx)));
1276                               }
1277                             r = method;
1278                             break;
1279                           }
1280                         found = 1;
1281                         continue;
1282                       }
1283 #if 0
1284                     fprintf (stderr, "\tfound %s\n\n",
1285                              IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (method)));
1286 #endif
1287                     if (DECL_ARTIFICIAL (method))
1288                       {
1289                         cp_error ("template for method `%D' which has default implementation in class `%T'", name, ctx);
1290                         if (in_decl)
1291                           cp_error_at ("in attempt to instantiate `%D' declared at this point in file", in_decl);
1292                         return error_mark_node;
1293                       }
1294
1295                     if (DECL_ARGUMENTS (method)
1296                         && ! TREE_PERMANENT (DECL_ARGUMENTS (method)))
1297                       /* @@ Is this early enough?  Might we want to do
1298                          this instead while processing the expansion?    */
1299                       DECL_ARGUMENTS (method)
1300                         = tsubst (DECL_ARGUMENTS (t), args, nargs, t);
1301                     r = method;
1302                     break;
1303                   }
1304                 if (r == NULL_TREE && pass == 0)
1305                   {
1306                     pass = 1;
1307                     method = TREE_VEC_ELT (methods, i);
1308                     goto maybe_error;
1309                   }
1310               }
1311             if (r == NULL_TREE)
1312               {
1313               no_match:
1314                 cp_error
1315                   (found
1316                    ? "template for method `%D' doesn't match any in class `%T'"
1317                    : "method `%D' not found in class `%T'", name, ctx);
1318                 if (in_decl)
1319                   cp_error_at ("in attempt to instantiate `%D' declared at this point in file", in_decl);
1320                 return error_mark_node;
1321               }
1322           }
1323         else
1324           {
1325             r = DECL_NAME (t);
1326             {
1327               tree decls;
1328               int got_it = 0;
1329
1330               decls = lookup_name_nonclass (r);
1331               if (decls == NULL_TREE)
1332                 /* no match */;
1333               else if (TREE_CODE (decls) == TREE_LIST)
1334                 for (decls = TREE_VALUE (decls); decls ;
1335                      decls = DECL_CHAIN (decls))
1336                   {
1337                     if (TREE_CODE (decls) == FUNCTION_DECL
1338                         && TREE_TYPE (decls) == type)
1339                       {
1340                         got_it = 1;
1341                         r = decls;
1342                         break;
1343                       }
1344                   }
1345               else
1346                 {
1347                   tree val = decls;
1348                   decls = NULL_TREE;
1349                   if (TREE_CODE (val) == FUNCTION_DECL
1350                       && TREE_TYPE (val) == type)
1351                     {
1352                       got_it = 1;
1353                       r = val;
1354                     }
1355                 }
1356
1357               if (!got_it)
1358                 {
1359                   r = build_decl_overload (r, TYPE_VALUES (type),
1360                                            DECL_CONTEXT (t) != NULL_TREE);
1361                   r = build_lang_decl (FUNCTION_DECL, r, type);
1362                 }
1363               else if (DECL_INLINE (r) && DECL_SAVED_INSNS (r))
1364                 {
1365                   /* This overrides the template version, use it. */
1366                   return r;
1367                 }
1368             }
1369           }
1370         TREE_PUBLIC (r) = TREE_PUBLIC (t);
1371         DECL_EXTERNAL (r) = DECL_EXTERNAL (t);
1372         TREE_STATIC (r) = TREE_STATIC (t);
1373         DECL_INLINE (r) = DECL_INLINE (t);
1374         {
1375 #if 0                           /* Maybe later.  -jason  */
1376           struct tinst_level *til = tinst_for_decl();
1377
1378           /* should always be true under new approach */
1379           if (til)
1380             {
1381               DECL_SOURCE_FILE (r) = til->file;
1382               DECL_SOURCE_LINE (r) = til->line;
1383             }
1384           else
1385 #endif
1386             {
1387               DECL_SOURCE_FILE (r) = DECL_SOURCE_FILE (t);
1388               DECL_SOURCE_LINE (r) = DECL_SOURCE_LINE (t);
1389             }
1390         }
1391         DECL_CLASS_CONTEXT (r) = tsubst (DECL_CLASS_CONTEXT (t), args, nargs, t);
1392         make_decl_rtl (r, NULL_PTR, 1);
1393         DECL_ARGUMENTS (r) = fnargs;
1394         DECL_RESULT (r) = result;
1395         if (DECL_CONTEXT (t) == NULL_TREE
1396             || TREE_CODE_CLASS (TREE_CODE (DECL_CONTEXT (t))) != 't')
1397           push_overloaded_decl_top_level (r, 0);
1398         return r;
1399       }
1400
1401     case PARM_DECL:
1402       {
1403         tree r;
1404         r = build_decl (PARM_DECL, DECL_NAME (t), type);
1405         DECL_INITIAL (r) = TREE_TYPE (r);
1406         if (TREE_CHAIN (t))
1407           TREE_CHAIN (r) = tsubst (TREE_CHAIN (t), args, nargs, TREE_CHAIN (t));
1408         return r;
1409       }
1410
1411     case TREE_LIST:
1412       {
1413         tree purpose, value, chain, result;
1414         int via_public, via_virtual, via_protected;
1415
1416         if (t == void_list_node)
1417           return t;
1418
1419         via_public = TREE_VIA_PUBLIC (t);
1420         via_protected = TREE_VIA_PROTECTED (t);
1421         via_virtual = TREE_VIA_VIRTUAL (t);
1422
1423         purpose = TREE_PURPOSE (t);
1424         if (purpose)
1425           purpose = tsubst (purpose, args, nargs, in_decl);
1426         value = TREE_VALUE (t);
1427         if (value)
1428           value = tsubst (value, args, nargs, in_decl);
1429         chain = TREE_CHAIN (t);
1430         if (chain && chain != void_type_node)
1431           chain = tsubst (chain, args, nargs, in_decl);
1432         if (purpose == TREE_PURPOSE (t)
1433             && value == TREE_VALUE (t)
1434             && chain == TREE_CHAIN (t))
1435           return t;
1436         result = hash_tree_cons (via_public, via_virtual, via_protected,
1437                                  purpose, value, chain);
1438         TREE_PARMLIST (result) = TREE_PARMLIST (t);
1439         return result;
1440       }
1441     case TREE_VEC:
1442       {
1443         int len = TREE_VEC_LENGTH (t), need_new = 0, i;
1444         tree *elts = (tree *) alloca (len * sizeof (tree));
1445         bzero (elts, len * sizeof (tree));
1446
1447         for (i = 0; i < len; i++)
1448           {
1449             elts[i] = tsubst (TREE_VEC_ELT (t, i), args, nargs, in_decl);
1450             if (elts[i] != TREE_VEC_ELT (t, i))
1451               need_new = 1;
1452           }
1453
1454         if (!need_new)
1455           return t;
1456
1457         t = make_tree_vec (len);
1458         for (i = 0; i < len; i++)
1459           TREE_VEC_ELT (t, i) = elts[i];
1460         return t;
1461       }
1462     case POINTER_TYPE:
1463     case REFERENCE_TYPE:
1464       {
1465         tree r;
1466         enum tree_code code;
1467         if (type == TREE_TYPE (t))
1468           return t;
1469
1470         code = TREE_CODE (t);
1471         if (code == POINTER_TYPE)
1472           r = build_pointer_type (type);
1473         else
1474           r = build_reference_type (type);
1475         r = build_type_variant (r, TYPE_READONLY (t), TYPE_VOLATILE (t));
1476         /* Will this ever be needed for TYPE_..._TO values?  */
1477         layout_type (r);
1478         return r;
1479       }
1480     case OFFSET_TYPE:
1481       return build_offset_type
1482         (tsubst (TYPE_OFFSET_BASETYPE (t), args, nargs, in_decl), type);
1483     case FUNCTION_TYPE:
1484     case METHOD_TYPE:
1485       {
1486         tree values = TYPE_VALUES (t); /* same as TYPE_ARG_TYPES */
1487         tree context = TYPE_CONTEXT (t);
1488         tree new_value;
1489
1490         /* Don't bother recursing if we know it won't change anything.  */
1491         if (values != void_list_node)
1492           values = tsubst (values, args, nargs, in_decl);
1493         if (context)
1494           context = tsubst (context, args, nargs, in_decl);
1495         /* Could also optimize cases where return value and
1496            values have common elements (e.g., T min(const &T, const T&).  */
1497
1498         /* If the above parameters haven't changed, just return the type.  */
1499         if (type == TREE_TYPE (t)
1500             && values == TYPE_VALUES (t)
1501             && context == TYPE_CONTEXT (t))
1502           return t;
1503
1504         /* Construct a new type node and return it.  */
1505         if (TREE_CODE (t) == FUNCTION_TYPE
1506             && context == NULL_TREE)
1507           {
1508             new_value = build_function_type (type, values);
1509           }
1510         else if (context == NULL_TREE)
1511           {
1512             tree base = tsubst (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (t))),
1513                                 args, nargs, in_decl);
1514             new_value = build_cplus_method_type (base, type,
1515                                                  TREE_CHAIN (values));
1516           }
1517         else
1518           {
1519             new_value = make_node (TREE_CODE (t));
1520             TREE_TYPE (new_value) = type;
1521             TYPE_CONTEXT (new_value) = context;
1522             TYPE_VALUES (new_value) = values;
1523             TYPE_SIZE (new_value) = TYPE_SIZE (t);
1524             TYPE_ALIGN (new_value) = TYPE_ALIGN (t);
1525             TYPE_MODE (new_value) = TYPE_MODE (t);
1526             if (TYPE_METHOD_BASETYPE (t))
1527               TYPE_METHOD_BASETYPE (new_value) = tsubst (TYPE_METHOD_BASETYPE (t),
1528                                                          args, nargs, in_decl);
1529             /* Need to generate hash value.  */
1530             my_friendly_abort (84);
1531           }
1532         new_value = build_type_variant (new_value,
1533                                         TYPE_READONLY (t),
1534                                         TYPE_VOLATILE (t));
1535         return new_value;
1536       }
1537     case ARRAY_TYPE:
1538       {
1539         tree domain = tsubst (TYPE_DOMAIN (t), args, nargs, in_decl);
1540         tree r;
1541         if (type == TREE_TYPE (t) && domain == TYPE_DOMAIN (t))
1542           return t;
1543         r = build_cplus_array_type (type, domain);
1544         return r;
1545       }
1546
1547     case UNINSTANTIATED_P_TYPE:
1548       {
1549         int nparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (UPT_TEMPLATE (t)));
1550         tree argvec = make_tree_vec (nparms);
1551         tree parmvec = UPT_PARMS (t);
1552         int i;
1553         tree id, rt;
1554         for (i = 0; i < nparms; i++)
1555           TREE_VEC_ELT (argvec, i) = tsubst (TREE_VEC_ELT (parmvec, i),
1556                                              args, nargs, in_decl);
1557         id = lookup_template_class (DECL_NAME (UPT_TEMPLATE (t)), argvec, NULL_TREE);
1558         if (! IDENTIFIER_HAS_TYPE_VALUE (id)) {
1559           instantiate_class_template(id, 0);
1560           /* set up pending_classes */
1561           add_pending_template (id);
1562
1563           TYPE_MAIN_VARIANT (IDENTIFIER_TYPE_VALUE (id)) =
1564             IDENTIFIER_TYPE_VALUE (id);
1565         }
1566         rt = IDENTIFIER_TYPE_VALUE (id);
1567
1568         /* kung: this part handles nested type in template definition */
1569
1570         if ( !ANON_AGGRNAME_P (DECL_NAME(TYPE_NAME(t))))
1571           {
1572             rt = search_nested_type_in_tmpl (rt, t);
1573           }
1574
1575         return build_type_variant (rt, TYPE_READONLY (t), TYPE_VOLATILE (t));
1576       }
1577
1578     case MINUS_EXPR:
1579     case PLUS_EXPR:
1580       return fold (build (TREE_CODE (t), TREE_TYPE (t),
1581                           tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl),
1582                           tsubst (TREE_OPERAND (t, 1), args, nargs, in_decl)));
1583
1584     case NEGATE_EXPR:
1585     case NOP_EXPR:
1586       return fold (build1 (TREE_CODE (t), TREE_TYPE (t),
1587                            tsubst (TREE_OPERAND (t, 0), args, nargs, in_decl)));
1588
1589     default:
1590       sorry ("use of `%s' in function template",
1591              tree_code_name [(int) TREE_CODE (t)]);
1592       return error_mark_node;
1593     }
1594 }
1595
1596 tree
1597 instantiate_template (tmpl, targ_ptr)
1598      tree tmpl, *targ_ptr;
1599 {
1600   tree targs, fndecl;
1601   int i, len;
1602   struct pending_inline *p;
1603   struct template_info *t;
1604   struct obstack *old_fmp_obstack;
1605   extern struct obstack *function_maybepermanent_obstack;
1606
1607   push_obstacks (&permanent_obstack, &permanent_obstack);
1608   old_fmp_obstack = function_maybepermanent_obstack;
1609   function_maybepermanent_obstack = &permanent_obstack;
1610
1611   my_friendly_assert (TREE_CODE (tmpl) == TEMPLATE_DECL, 283);
1612   len = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (tmpl));
1613
1614   for (fndecl = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
1615        fndecl; fndecl = TREE_CHAIN (fndecl))
1616     {
1617       tree *t1 = &TREE_VEC_ELT (TREE_PURPOSE (fndecl), 0);
1618       for (i = len - 1; i >= 0; i--)
1619         if (t1[i] != targ_ptr[i])
1620           goto no_match;
1621
1622       /* Here, we have a match.  */
1623       fndecl = TREE_VALUE (fndecl);
1624       goto exit;
1625
1626     no_match:
1627       ;
1628     }
1629
1630   targs = make_tree_vec (len);
1631   i = len;
1632   while (i--)
1633     TREE_VEC_ELT (targs, i) = targ_ptr[i];
1634
1635   /* substitute template parameters */
1636   fndecl = tsubst (DECL_RESULT (tmpl), targ_ptr,
1637                    TREE_VEC_LENGTH (targs), tmpl);
1638
1639   if (fndecl == error_mark_node)
1640     goto exit;
1641
1642   /* If it's a static member fn in the template, we need to change it
1643      into a FUNCTION_TYPE and chop off its this pointer.  */
1644   if (TREE_CODE (TREE_TYPE (DECL_RESULT (tmpl))) == METHOD_TYPE
1645       && DECL_STATIC_FUNCTION_P (fndecl))
1646     {
1647       tree olddecl = DECL_RESULT (tmpl);
1648       revert_static_member_fn (&DECL_RESULT (tmpl), NULL, NULL);
1649       /* Chop off the this pointer that grokclassfn so kindly added
1650          for us (it didn't know yet if the fn was static or not).  */
1651       DECL_ARGUMENTS (olddecl) = TREE_CHAIN (DECL_ARGUMENTS (olddecl));
1652       DECL_ARGUMENTS (fndecl) = TREE_CHAIN (DECL_ARGUMENTS (fndecl));
1653     }
1654
1655   t = DECL_TEMPLATE_INFO (tmpl);
1656
1657   /* If we have a preexisting version of this function, don't expand
1658      the template version, use the other instead.  */
1659   if (DECL_INLINE (fndecl) && DECL_SAVED_INSNS (fndecl))
1660     {
1661       SET_DECL_TEMPLATE_SPECIALIZATION (fndecl);
1662       p = (struct pending_inline *)0;
1663     }
1664   else if (t->text)
1665     {
1666       SET_DECL_IMPLICIT_INSTANTIATION (fndecl);
1667       p = (struct pending_inline *) permalloc (sizeof (struct pending_inline));
1668       p->parm_vec = t->parm_vec;
1669       p->bindings = targs;
1670       p->can_free = 0;
1671       p->deja_vu = 0;
1672       p->buf = t->text;
1673       p->len = t->length;
1674       p->fndecl = fndecl;
1675       {
1676         int l = lineno;
1677         char * f = input_filename;
1678
1679         lineno = p->lineno = t->lineno;
1680         input_filename = p->filename = t->filename;
1681
1682         extract_interface_info ();
1683
1684         if (interface_unknown && flag_external_templates && ! DECL_IN_SYSTEM_HEADER (tmpl))
1685           warn_if_unknown_interface ();
1686         if (interface_unknown || !flag_external_templates)
1687           p->interface = 1;             /* unknown */
1688         else
1689           p->interface = interface_only ? 0 : 2;
1690
1691         lineno = l;
1692         input_filename = f;
1693
1694         extract_interface_info ();
1695       }
1696     }
1697   else
1698     p = (struct pending_inline *)0;
1699
1700   DECL_TEMPLATE_INSTANTIATIONS (tmpl) =
1701     tree_cons (targs, fndecl, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1702
1703   if (p == (struct pending_inline *)0)
1704     {
1705       /* do nothing */
1706     }
1707   else if (DECL_INLINE (fndecl))
1708     {
1709       DECL_PENDING_INLINE_INFO (fndecl) = p;
1710       p->next = pending_inlines;
1711       pending_inlines = p;
1712     }
1713   else
1714     {
1715       p->next = pending_template_expansions;
1716       pending_template_expansions = p;
1717     }
1718  exit:
1719   function_maybepermanent_obstack = old_fmp_obstack;
1720   pop_obstacks ();
1721
1722   return fndecl;
1723 }
1724
1725 /* classlevel should now never be true.  jason 4/12/94 */
1726 void
1727 undo_template_name_overload (id, classlevel)
1728      tree id;
1729      int classlevel;
1730 {
1731   tree template;
1732
1733   template = IDENTIFIER_TEMPLATE (id);
1734   if (!template)
1735     return;
1736
1737 #if 0 /* not yet, should get fixed properly later */
1738   poplevel (0, 0, 0);
1739 #endif
1740 #if 1 /* XXX */
1741   /* This was a botch... See `overload_template_name' just below.  */
1742   if (!classlevel)
1743     poplevel (0, 0, 0);
1744 #endif
1745 }
1746
1747 /* classlevel should now never be true.  jason 4/12/94 */
1748 void
1749 overload_template_name (id, classlevel)
1750      tree id;
1751      int classlevel;
1752 {
1753   tree template, t, decl;
1754   struct template_info *tinfo;
1755
1756   my_friendly_assert (TREE_CODE (id) == IDENTIFIER_NODE, 284);
1757   template = IDENTIFIER_TEMPLATE (id);
1758   if (!template)
1759     return;
1760
1761   template = TREE_PURPOSE (template);
1762   tinfo = DECL_TEMPLATE_INFO (template);
1763   template = DECL_NAME (template);
1764   my_friendly_assert (template != NULL_TREE, 285);
1765
1766 #if 1 /* XXX */
1767   /* This was a botch... names of templates do not get their own private
1768      scopes.  Rather, they should go into the binding level already created
1769      by push_template_decls.  Except that there isn't one of those for
1770      specializations.  */
1771   if (!classlevel)
1772     {
1773       pushlevel (1);
1774       declare_pseudo_global_level ();
1775     }
1776 #endif
1777
1778   t = xref_tag (tinfo->aggr, id, NULL_TREE, 0);
1779   my_friendly_assert (TREE_CODE (t) == RECORD_TYPE
1780                       || TREE_CODE (t) == UNION_TYPE
1781                       || TREE_CODE (t) == UNINSTANTIATED_P_TYPE, 286);
1782
1783   decl = build_decl (TYPE_DECL, template, t);
1784
1785 #if 0 /* fix this later */
1786   /* We don't want to call here if the work has already been done.  */
1787   t = (classlevel
1788        ? IDENTIFIER_CLASS_VALUE (template)
1789        : IDENTIFIER_LOCAL_VALUE (template));
1790   if (t
1791       && TREE_CODE (t) == TYPE_DECL
1792       && TREE_TYPE (t) == t)
1793     my_friendly_abort (85);
1794 #endif
1795
1796   if (classlevel)
1797     pushdecl_class_level (decl);
1798   else
1799     pushdecl (decl);
1800
1801 #if 0 /* This seems bogus to me; if it isn't, explain why.  (jason) */
1802   /* Fake this for now, just to make dwarfout.c happy.  It will have to
1803      be done in a proper way later on.  */
1804   DECL_CONTEXT (decl) = t;
1805 #endif
1806 }
1807
1808 /* NAME is the IDENTIFIER value of a PRE_PARSED_CLASS_DECL. */
1809 void
1810 end_template_instantiation (name)
1811      tree name;
1812 {
1813   extern struct pending_input *to_be_restored;
1814   tree t, decl;
1815
1816   processing_template_defn--;
1817   if (!flag_external_templates)
1818     interface_unknown--;
1819
1820   /* Restore the old parser input state.  */
1821   if (yychar == YYEMPTY)
1822     yychar = yylex ();
1823   if (yychar != END_OF_SAVED_INPUT)
1824     error ("parse error at end of class template");
1825   else
1826     {
1827       restore_pending_input (to_be_restored);
1828       to_be_restored = 0;
1829     }
1830
1831   /* Our declarations didn't get stored in the global slot, since
1832      there was a (supposedly tags-transparent) scope in between.  */
1833   t = IDENTIFIER_TYPE_VALUE (name);
1834   my_friendly_assert (t != NULL_TREE
1835                       && TREE_CODE_CLASS (TREE_CODE (t)) == 't',
1836                       287);
1837   SET_CLASSTYPE_IMPLICIT_INSTANTIATION (t);
1838   /* Make methods of template classes static, unless
1839      -fexternal-templates is given.  */
1840   if (!flag_external_templates)
1841     SET_CLASSTYPE_INTERFACE_UNKNOWN (t);
1842   decl = IDENTIFIER_GLOBAL_VALUE (name);
1843   my_friendly_assert (TREE_CODE (decl) == TYPE_DECL, 288);
1844
1845   undo_template_name_overload (name, 0);
1846   t = IDENTIFIER_TEMPLATE (name);
1847   pop_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (t)), TREE_VALUE (t),
1848                       0);
1849   /* This will fix up the type-value field.  */
1850   pushdecl (decl);
1851   pop_from_top_level ();
1852
1853 #ifdef DWARF_DEBUGGING_INFO
1854   if (write_symbols == DWARF_DEBUG && TREE_CODE (decl) == TYPE_DECL)
1855     {
1856       /* We just completed the definition of a new file-scope type,
1857          so we can go ahead and output debug-info for it now.  */
1858       TYPE_STUB_DECL (TREE_TYPE (decl)) = decl;
1859       rest_of_type_compilation (TREE_TYPE (decl), 1);
1860     }
1861 #endif /* DWARF_DEBUGGING_INFO */
1862
1863   /* Restore interface/implementation settings.  */
1864   extract_interface_info ();
1865 }
1866 \f
1867 /* Store away the text of an template.  */
1868
1869 void
1870 reinit_parse_for_template (yychar, d1, d2)
1871      int yychar;
1872      tree d1, d2;
1873 {
1874   struct template_info *template_info;
1875   extern struct obstack inline_text_obstack; /* see comment in lex.c */
1876
1877   if (d2 == NULL_TREE || d2 == error_mark_node)
1878     {
1879     lose:
1880       /* @@ Should use temp obstack, and discard results.  */
1881       reinit_parse_for_block (yychar, &inline_text_obstack, 1);
1882       return;
1883     }
1884
1885   if (TREE_CODE (d2) == IDENTIFIER_NODE)
1886     d2 = IDENTIFIER_GLOBAL_VALUE (d2);
1887   if (!d2)
1888     goto lose;
1889   template_info = DECL_TEMPLATE_INFO (d2);
1890   if (!template_info)
1891     {
1892       template_info = (struct template_info *) permalloc (sizeof (struct template_info));
1893       bzero (template_info, sizeof (struct template_info));
1894       DECL_TEMPLATE_INFO (d2) = template_info;
1895     }
1896   template_info->filename = input_filename;
1897   template_info->lineno = lineno;
1898   reinit_parse_for_block (yychar, &inline_text_obstack, 1);
1899   template_info->text = obstack_base (&inline_text_obstack);
1900   template_info->length = obstack_object_size (&inline_text_obstack);
1901   obstack_finish (&inline_text_obstack);
1902   template_info->parm_vec = d1;
1903 }
1904
1905 /* Type unification.
1906
1907    We have a function template signature with one or more references to
1908    template parameters, and a parameter list we wish to fit to this
1909    template.  If possible, produce a list of parameters for the template
1910    which will cause it to fit the supplied parameter list.
1911
1912    Return zero for success, 2 for an incomplete match that doesn't resolve
1913    all the types, and 1 for complete failure.  An error message will be
1914    printed only for an incomplete match.
1915
1916    TPARMS[NTPARMS] is an array of template parameter types;
1917    TARGS[NTPARMS] is the array of template parameter values.  PARMS is
1918    the function template's signature (using TEMPLATE_PARM_IDX nodes),
1919    and ARGS is the argument list we're trying to match against it.
1920
1921    If SUBR is 1, we're being called recursively (to unify the arguments of
1922    a function or method parameter of a function template), so don't zero
1923    out targs and don't fail on an incomplete match. */
1924
1925 int
1926 type_unification (tparms, targs, parms, args, nsubsts, subr)
1927      tree tparms, *targs, parms, args;
1928      int *nsubsts, subr;
1929 {
1930   tree parm, arg;
1931   int i;
1932   int ntparms = TREE_VEC_LENGTH (tparms);
1933
1934   my_friendly_assert (TREE_CODE (tparms) == TREE_VEC, 289);
1935   my_friendly_assert (TREE_CODE (parms) == TREE_LIST, 290);
1936   /* ARGS could be NULL (via a call from parse.y to
1937      build_x_function_call).  */
1938   if (args)
1939     my_friendly_assert (TREE_CODE (args) == TREE_LIST, 291);
1940   my_friendly_assert (ntparms > 0, 292);
1941
1942   if (!subr)
1943     bzero (targs, sizeof (tree) * ntparms);
1944
1945   while (parms
1946          && parms != void_list_node
1947          && args
1948          && args != void_list_node)
1949     {
1950       parm = TREE_VALUE (parms);
1951       parms = TREE_CHAIN (parms);
1952       arg = TREE_VALUE (args);
1953       args = TREE_CHAIN (args);
1954
1955       if (arg == error_mark_node)
1956         return 1;
1957       if (arg == unknown_type_node)
1958         return 1;
1959 #if 0
1960       if (TREE_CODE (arg) == VAR_DECL)
1961         arg = TREE_TYPE (arg);
1962       else if (TREE_CODE_CLASS (TREE_CODE (arg)) == 'e')
1963         arg = TREE_TYPE (arg);
1964 #else
1965       if (TREE_CODE_CLASS (TREE_CODE (arg)) != 't')
1966         {
1967           my_friendly_assert (TREE_TYPE (arg) != NULL_TREE, 293);
1968           arg = TREE_TYPE (arg);
1969         }
1970 #endif
1971       if (TREE_CODE (arg) == FUNCTION_TYPE
1972           || TREE_CODE (arg) == METHOD_TYPE)
1973         arg = build_pointer_type (arg);
1974
1975       switch (unify (tparms, targs, ntparms, parm, arg, nsubsts))
1976         {
1977         case 0:
1978           break;
1979         case 1:
1980           return 1;
1981         }
1982     }
1983   /* Fail if we've reached the end of the parm list, and more args
1984      are present, and the parm list isn't variadic.  */
1985   if (args && args != void_list_node && parms == void_list_node)
1986     return 1;
1987   /* Fail if parms are left and they don't have default values.  */
1988   if (parms
1989       && parms != void_list_node
1990       && TREE_PURPOSE (parms) == NULL_TREE)
1991     return 1;
1992   if (!subr)
1993     for (i = 0; i < ntparms; i++)
1994       if (!targs[i])
1995         {
1996           error ("incomplete type unification");
1997           return 2;
1998         }
1999   return 0;
2000 }
2001
2002 /* Tail recursion is your friend.  */
2003 static int
2004 unify (tparms, targs, ntparms, parm, arg, nsubsts)
2005      tree tparms, *targs, parm, arg;
2006      int *nsubsts, ntparms;
2007 {
2008   int idx;
2009
2010   /* I don't think this will do the right thing with respect to types.
2011      But the only case I've seen it in so far has been array bounds, where
2012      signedness is the only information lost, and I think that will be
2013      okay.  */
2014   while (TREE_CODE (parm) == NOP_EXPR)
2015     parm = TREE_OPERAND (parm, 0);
2016
2017   if (arg == error_mark_node)
2018     return 1;
2019   if (arg == unknown_type_node)
2020     return 1;
2021   if (arg == parm)
2022     return 0;
2023
2024   if (TREE_CODE (arg) == REFERENCE_TYPE)
2025     arg = TREE_TYPE (arg);
2026
2027   switch (TREE_CODE (parm))
2028     {
2029     case TEMPLATE_TYPE_PARM:
2030       (*nsubsts)++;
2031       if (TEMPLATE_TYPE_TPARMLIST (parm) != tparms)
2032         {
2033           error ("mixed template headers?!");
2034           my_friendly_abort (86);
2035           return 1;
2036         }
2037       idx = TEMPLATE_TYPE_IDX (parm);
2038       /* Simple cases: Value already set, does match or doesn't.  */
2039       if (targs[idx] == arg)
2040         return 0;
2041       else if (targs[idx])
2042         {
2043           if (TYPE_MAIN_VARIANT (targs[idx]) == TYPE_MAIN_VARIANT (arg))
2044             /* allow different parms to have different cv-qualifiers */;
2045           else
2046             return 1;
2047         }
2048       /* Check for mixed types and values.  */
2049       if (TREE_CODE (TREE_VEC_ELT (tparms, idx)) != IDENTIFIER_NODE)
2050         return 1;
2051       /* Allow trivial conversions.  */
2052       if (TYPE_READONLY (parm) < TYPE_READONLY (arg)
2053           || TYPE_VOLATILE (parm) < TYPE_VOLATILE (arg))
2054         return 1;
2055       targs[idx] = arg;
2056       return 0;
2057     case TEMPLATE_CONST_PARM:
2058       (*nsubsts)++;
2059       idx = TEMPLATE_CONST_IDX (parm);
2060       if (targs[idx] == arg)
2061         return 0;
2062       else if (targs[idx])
2063         {
2064           tree t = targs[idx];
2065           if (TREE_CODE (t) == TREE_CODE (arg))
2066             switch (TREE_CODE (arg))
2067               {
2068               case INTEGER_CST:
2069                 if (tree_int_cst_equal (t, arg))
2070                   return 0;
2071                 break;
2072               case REAL_CST:
2073                 if (REAL_VALUES_EQUAL (TREE_REAL_CST (t), TREE_REAL_CST (arg)))
2074                   return 0;
2075                 break;
2076               /* STRING_CST values are not valid template const parms.  */
2077               default:
2078                 ;
2079               }
2080           my_friendly_abort (87);
2081           return 1;
2082         }
2083 /*      else if (typeof arg != tparms[idx])
2084         return 1;*/
2085
2086       targs[idx] = copy_to_permanent (arg);
2087       return 0;
2088
2089     case POINTER_TYPE:
2090       if (TREE_CODE (arg) != POINTER_TYPE)
2091         return 1;
2092       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2093                     nsubsts);
2094
2095     case REFERENCE_TYPE:
2096       return unify (tparms, targs, ntparms, TREE_TYPE (parm), arg, nsubsts);
2097
2098     case ARRAY_TYPE:
2099       if (TREE_CODE (arg) != ARRAY_TYPE)
2100         return 1;
2101       if (unify (tparms, targs, ntparms, TYPE_DOMAIN (parm), TYPE_DOMAIN (arg),
2102                  nsubsts) != 0)
2103         return 1;
2104       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
2105                     nsubsts);
2106
2107     case REAL_TYPE:
2108     case INTEGER_TYPE:
2109       if (TREE_CODE (parm) == INTEGER_TYPE && TREE_CODE (arg) == INTEGER_TYPE)
2110         {
2111           if (TYPE_MIN_VALUE (parm) && TYPE_MIN_VALUE (arg)
2112               && unify (tparms, targs, ntparms,
2113                         TYPE_MIN_VALUE (parm), TYPE_MIN_VALUE (arg), nsubsts))
2114             return 1;
2115           if (TYPE_MAX_VALUE (parm) && TYPE_MAX_VALUE (arg)
2116               && unify (tparms, targs, ntparms,
2117                         TYPE_MAX_VALUE (parm), TYPE_MAX_VALUE (arg), nsubsts))
2118             return 1;
2119         }
2120       /* As far as unification is concerned, this wins.  Later checks
2121          will invalidate it if necessary.  */
2122       return 0;
2123
2124       /* Types INTEGER_CST and MINUS_EXPR can come from array bounds.  */
2125     case INTEGER_CST:
2126       if (TREE_CODE (arg) != INTEGER_CST)
2127         return 1;
2128       return !tree_int_cst_equal (parm, arg);
2129
2130     case MINUS_EXPR:
2131       {
2132         tree t1, t2;
2133         t1 = TREE_OPERAND (parm, 0);
2134         t2 = TREE_OPERAND (parm, 1);
2135         if (TREE_CODE (t1) != TEMPLATE_CONST_PARM)
2136           return 1;
2137         return unify (tparms, targs, ntparms, t1,
2138                       fold (build (PLUS_EXPR, integer_type_node, arg, t2)),
2139                       nsubsts);
2140       }
2141
2142     case TREE_VEC:
2143       {
2144         int i;
2145         if (TREE_CODE (arg) != TREE_VEC)
2146           return 1;
2147         if (TREE_VEC_LENGTH (parm) != TREE_VEC_LENGTH (arg))
2148           return 1;
2149         for (i = TREE_VEC_LENGTH (parm) - 1; i >= 0; i--)
2150           if (unify (tparms, targs, ntparms,
2151                      TREE_VEC_ELT (parm, i), TREE_VEC_ELT (arg, i),
2152                      nsubsts))
2153             return 1;
2154         return 0;
2155       }
2156
2157     case UNINSTANTIATED_P_TYPE:
2158       {
2159         tree a;
2160         /* Unification of something that is not a template fails. (mrs) */
2161         if (TYPE_NAME (arg) == 0)
2162           return 1;
2163         a = IDENTIFIER_TEMPLATE (TYPE_IDENTIFIER (arg));
2164         /* Unification of something that is not a template fails. (mrs) */
2165         if (a == 0)
2166           return 1;
2167         if (UPT_TEMPLATE (parm) != TREE_PURPOSE (a))
2168           /* different templates */
2169           return 1;
2170         return unify (tparms, targs, ntparms, UPT_PARMS (parm), TREE_VALUE (a),
2171                       nsubsts);
2172       }
2173
2174     case RECORD_TYPE:
2175       if (TYPE_PTRMEMFUNC_P (parm))
2176         return unify (tparms, targs, ntparms, TYPE_PTRMEMFUNC_FN_TYPE (parm),
2177                       arg, nsubsts);
2178
2179       /* Allow trivial conversions.  */
2180       if (TYPE_MAIN_VARIANT (parm) != TYPE_MAIN_VARIANT (arg)
2181           || TYPE_READONLY (parm) < TYPE_READONLY (arg)
2182           || TYPE_VOLATILE (parm) < TYPE_VOLATILE (arg))
2183         return 1;
2184       return 0;
2185
2186     case METHOD_TYPE:
2187       if (TREE_CODE (arg) != METHOD_TYPE)
2188         return 1;
2189       goto check_args;
2190
2191     case FUNCTION_TYPE:
2192       if (TREE_CODE (arg) != FUNCTION_TYPE)
2193         return 1;
2194      check_args:
2195       return type_unification (tparms, targs, TYPE_ARG_TYPES (parm),
2196                                TYPE_ARG_TYPES (arg), nsubsts, 1);
2197
2198     case OFFSET_TYPE:
2199       if (TREE_CODE (arg) != OFFSET_TYPE)
2200         return 1;
2201       if (unify (tparms, targs, ntparms, TYPE_OFFSET_BASETYPE (parm),
2202                  TYPE_OFFSET_BASETYPE (arg), nsubsts))
2203         return 1;
2204       return unify (tparms, targs, ntparms, TREE_TYPE (parm),
2205                     TREE_TYPE (arg), nsubsts);
2206
2207     default:
2208       sorry ("use of `%s' in template type unification",
2209              tree_code_name [(int) TREE_CODE (parm)]);
2210       return 1;
2211     }
2212 }
2213
2214 \f
2215 #undef DEBUG
2216
2217 int
2218 do_pending_expansions ()
2219 {
2220   struct pending_inline *i, *new_list = 0;
2221
2222   if (!pending_template_expansions)
2223     return 0;
2224
2225 #ifdef DEBUG
2226   fprintf (stderr, "\n\n\t\t IN DO_PENDING_EXPANSIONS\n\n");
2227 #endif
2228
2229   i = pending_template_expansions;
2230   while (i)
2231     {
2232       tree context;
2233
2234       struct pending_inline *next = i->next;
2235       tree t = i->fndecl;
2236
2237       int decision = 0;
2238 #define DECIDE(N) do {decision=(N); goto decided;} while(0)
2239
2240       my_friendly_assert (TREE_CODE (t) == FUNCTION_DECL
2241                           || TREE_CODE (t) == VAR_DECL, 294);
2242       if (TREE_ASM_WRITTEN (t))
2243         DECIDE (0);
2244
2245       if (DECL_EXPLICIT_INSTANTIATION (t))
2246         DECIDE (! DECL_EXTERNAL (t));
2247       else if (! flag_implicit_templates)
2248         DECIDE (0);
2249
2250       /* If it's a method, let the class type decide it.
2251          @@ What if the method template is in a separate file?
2252          Maybe both file contexts should be taken into account?
2253          Maybe only do this if i->interface == 1 (unknown)?  */
2254       context = DECL_CONTEXT (t);
2255       if (context != NULL_TREE
2256           && TREE_CODE_CLASS (TREE_CODE (context)) == 't')
2257         {
2258           /* I'm interested in the context of this version of the function,
2259              not the original virtual declaration.  */
2260           context = DECL_CLASS_CONTEXT (t);
2261
2262           /* If `unknown', we might want a static copy.
2263              If `implementation', we want a global one.
2264              If `interface', ext ref.  */
2265           if (CLASSTYPE_INTERFACE_KNOWN (context))
2266             DECIDE (!CLASSTYPE_INTERFACE_ONLY (context));
2267 #if 0 /* This doesn't get us stuff needed only by the file initializer.  */
2268           DECIDE (TREE_USED (t));
2269 #else /* This compiles too much stuff, but that's probably better in
2270          most cases than never compiling the stuff we need.  */
2271           DECIDE (1);
2272 #endif
2273         }
2274
2275       if (i->interface == 1)
2276         DECIDE (TREE_USED (t));
2277       else
2278         DECIDE (i->interface);
2279
2280     decided:
2281 #ifdef DEBUG
2282       print_node_brief (stderr, decision ? "yes: " : "no: ", t, 0);
2283       fprintf (stderr, "\t%s\n",
2284                (DECL_ASSEMBLER_NAME (t)
2285                 ? IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (t))
2286                 : ""));
2287 #endif
2288       if (decision)
2289         {
2290           i->next = pending_inlines;
2291           pending_inlines = i;
2292         }
2293       else
2294         {
2295           i->next = new_list;
2296           new_list = i;
2297         }
2298       i = next;
2299     }
2300   pending_template_expansions = new_list;
2301   if (!pending_inlines)
2302     return 0;
2303   do_pending_inlines ();
2304   return 1;
2305 }
2306
2307 \f
2308 struct pending_template {
2309   struct pending_template *next;
2310   tree id;
2311 };
2312
2313 static struct pending_template* pending_templates;
2314
2315 void
2316 do_pending_templates ()
2317 {
2318   struct pending_template* t;
2319
2320   for ( t = pending_templates; t; t = t->next)
2321     {
2322       instantiate_class_template (t->id, 1);
2323     }
2324
2325   for ( t = pending_templates; t; t = pending_templates)
2326     {
2327       pending_templates = t->next;
2328       free(t);
2329     }
2330 }
2331
2332 static void
2333 add_pending_template (pt)
2334      tree pt;
2335 {
2336   struct pending_template *p;
2337
2338   p = (struct pending_template *) malloc (sizeof (struct pending_template));
2339   p->next = pending_templates;
2340   pending_templates = p;
2341   p->id = pt;
2342 }
2343
2344 /* called from the parser.  */
2345 void
2346 do_function_instantiation (declspecs, declarator, storage)
2347      tree declspecs, declarator, storage;
2348 {
2349   tree decl = grokdeclarator (declarator, declspecs, NORMAL, 0, 0);
2350   tree name = DECL_NAME (decl);
2351   tree fn = IDENTIFIER_GLOBAL_VALUE (name);
2352   tree result = NULL_TREE;
2353   if (fn)
2354     {
2355       for (fn = get_first_fn (fn); fn; fn = DECL_CHAIN (fn))
2356         if (TREE_CODE (fn) == TEMPLATE_DECL)
2357           {
2358             int ntparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (fn));
2359             tree *targs = (tree *) malloc (sizeof (tree) * ntparms);
2360             int i, dummy;
2361             i = type_unification (DECL_TEMPLATE_PARMS (fn), targs,
2362                                   TYPE_ARG_TYPES (TREE_TYPE (fn)),
2363                                   TYPE_ARG_TYPES (TREE_TYPE (decl)),
2364                                   &dummy, 0);
2365             if (i == 0)
2366               {
2367                 if (result)
2368                   cp_error ("ambiguous template instantiation for `%D' requested", decl);
2369                 else
2370                   result = instantiate_template (fn, targs);
2371               }
2372           }
2373     }
2374   if (! result)
2375     cp_error ("no matching template for `%D' found", decl);
2376
2377   if (flag_external_templates)
2378     return;
2379
2380   SET_DECL_EXPLICIT_INSTANTIATION (result);
2381   TREE_PUBLIC (result) = 1;
2382
2383   if (storage == NULL_TREE)
2384     DECL_EXTERNAL (result) = DECL_INLINE (result) && ! flag_implement_inlines;
2385   else if (storage == ridpointers[(int) RID_EXTERN])
2386     DECL_EXTERNAL (result) = 1;
2387   else
2388     cp_error ("storage class `%D' applied to template instantiation",
2389               storage);
2390 }
2391
2392 void
2393 do_type_instantiation (name, storage)
2394      tree name, storage;
2395 {
2396   tree t = TREE_TYPE (name);
2397   int extern_p;
2398
2399   if (flag_external_templates)
2400     return;
2401
2402   if (TYPE_SIZE (t) == NULL_TREE)
2403     {
2404       cp_error ("explicit instantiation of `%#T' before definition of template",
2405                 t);
2406       return;
2407     }
2408
2409   if (storage == NULL_TREE)
2410     extern_p = 0;
2411   else if (storage == ridpointers[(int) RID_EXTERN])
2412     extern_p = 1;
2413   else
2414     {
2415       cp_error ("storage class `%D' applied to template instantiation",
2416                 storage);
2417       extern_p = 0;
2418     }
2419
2420   SET_CLASSTYPE_EXPLICIT_INSTANTIATION (t);
2421   CLASSTYPE_VTABLE_NEEDS_WRITING (t) = ! extern_p;
2422   SET_CLASSTYPE_INTERFACE_KNOWN (t);
2423   CLASSTYPE_INTERFACE_ONLY (t) = extern_p;
2424   if (! extern_p)
2425     {
2426       CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2427       TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (t)) = 0;
2428       rest_of_type_compilation (t, 1);
2429     }
2430
2431   /* this should really be done by instantiate_member_templates */
2432   {
2433     tree method = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (t), 0);
2434     for (; method; method = TREE_CHAIN (method))
2435       {
2436         SET_DECL_EXPLICIT_INSTANTIATION (method);
2437         TREE_PUBLIC (method) = 1;
2438         DECL_EXTERNAL (method)
2439           = (extern_p || (DECL_INLINE (method) && ! flag_implement_inlines));
2440       }
2441   }
2442
2443   /* and data member templates, too */
2444 }
2445
2446 tree
2447 create_nested_upt (scope, name)
2448      tree scope, name;
2449 {
2450   tree t = make_lang_type (UNINSTANTIATED_P_TYPE);
2451   tree d = build_decl (TYPE_DECL, name, t);
2452
2453   TYPE_NAME (t) = d;
2454   TYPE_VALUES (t) = TYPE_VALUES (scope);
2455   TYPE_CONTEXT (t) = scope;
2456
2457   pushdecl (d);
2458   return d;
2459 }