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