Return to cp-pt.c CVS log

Up to [GCC 2.x] / gcc

Annotation of gcc/cp-pt.c, revision 1.1

1.1     ! root        1: /* Handle parameterized types (templates) for GNU C++.
        !             2:    Written by Ken Raeburn of Watchmaker Computing.
        !             3:    Copyright (C) 1992 Free Software Foundation, Inc.
        !             4: 
        !             5: This file is part of GNU CC.
        !             6: 
        !             7: GNU CC is free software; you can redistribute it and/or modify
        !             8: it under the terms of the GNU General Public License as published by
        !             9: the Free Software Foundation; either version 2, or (at your option)
        !            10: any later version.
        !            11: 
        !            12: GNU CC is distributed in the hope that it will be useful,
        !            13: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            15: GNU General Public License for more details.
        !            16: 
        !            17: You should have received a copy of the GNU General Public License
        !            18: along with GNU CC; see the file COPYING.  If not, write to
        !            19: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            20: 
        !            21: /* Known bugs or deficiencies include:
        !            22:    * templates for class static data don't work (methods only)
        !            23:    * duplicated method templates can crash the compiler
        !            24:    * interface/impl data is taken from file defining the template
        !            25:    * all methods must be provided in header files; can't use a source
        !            26:      file that contains only the method templates and "just win"
        !            27:    * method templates must be seen before the expansion of the
        !            28:      class template is done
        !            29:  */
        !            30: 
        !            31: #include "config.h"
        !            32: #include <stdio.h>
        !            33: #include <assert.h>
        !            34: #include "obstack.h"
        !            35: 
        !            36: #include "tree.h"
        !            37: #include "cp-tree.h"
        !            38: #include "cp-decl.h"
        !            39: #include "cp-parse.h"
        !            40: 
        !            41: extern struct obstack permanent_obstack;
        !            42: extern tree grokdeclarator ();
        !            43: 
        !            44: extern int lineno;
        !            45: extern char *input_filename;
        !            46: struct pending_inline *pending_template_expansions;
        !            47: 
        !            48: int processing_template_decl;
        !            49: int processing_template_defn;
        !            50: 
        !            51: #define obstack_chunk_alloc xmalloc
        !            52: #define obstack_chunk_free free
        !            53: 
        !            54: extern int xmalloc ();
        !            55: extern void free ();
        !            56: 
        !            57: static int unify ();
        !            58: 
        !            59: void overload_template_name (), pop_template_decls ();
        !            60: 
        !            61: /* We've got a template header coming up; set obstacks up to save the
        !            62:    nodes created permanently.  (There might be cases with nested templates
        !            63:    where we don't have to do this, but they aren't implemented, and it
        !            64:    probably wouldn't be worth the effort.)  */
        !            65: void
        !            66: begin_template_parm_list ()
        !            67: {
        !            68:   pushlevel (0);
        !            69:   push_obstacks (&permanent_obstack, &permanent_obstack);
        !            70: }
        !            71: 
        !            72: /* Process information from new template parameter NEXT and append it to the
        !            73:    LIST being built.  The rules for use of a template parameter type name
        !            74:    by later parameters are not well-defined for us just yet.  However, the
        !            75:    only way to avoid having to parse expressions of unknown complexity (and
        !            76:    with tokens of unknown types) is to disallow it completely. So for now,
        !            77:    that is what is assumed.  */
        !            78: tree
        !            79: process_template_parm (list, next)
        !            80:      tree list, next;
        !            81: {
        !            82:   tree parm;
        !            83:   int is_type;
        !            84:   parm = next;
        !            85:   assert (TREE_CODE (parm) == TREE_LIST);
        !            86:   is_type = TREE_CODE (TREE_PURPOSE (parm)) == IDENTIFIER_NODE;
        !            87:   if (!is_type)
        !            88:     {
        !            89:       parm = TREE_PURPOSE (parm);
        !            90:       assert (TREE_CODE (parm) == TREE_LIST);
        !            91:       parm = TREE_VALUE (parm);
        !            92:       /* is a const-param */
        !            93:       parm = grokdeclarator (TREE_VALUE (next), TREE_PURPOSE (next),
        !            94:                             NORMAL, 0, NULL_TREE);
        !            95:       /* A template parameter is not modifiable.  */
        !            96:       TREE_READONLY (parm) = 1;
        !            97:       if (TREE_CODE (TREE_TYPE (parm)) == RECORD_TYPE
        !            98:          || TREE_CODE (TREE_TYPE (parm)) == UNION_TYPE)
        !            99:        {
        !           100:          sorry ("aggregate template parameter types");
        !           101:          TREE_TYPE (parm) = void_type_node;
        !           102:        }
        !           103:     }
        !           104:   return chainon (list, parm);
        !           105: }
        !           106: 
        !           107: /* The end of a template parameter list has been reached.  Process the
        !           108:    tree list into a parameter vector, converting each parameter into a more
        !           109:    useful form.         Type parameters are saved as IDENTIFIER_NODEs, and others
        !           110:    as PARM_DECLs.  */
        !           111: 
        !           112: tree
        !           113: end_template_parm_list (parms)
        !           114:      tree parms;
        !           115: {
        !           116:   int nparms = 0;
        !           117:   tree saved_parmlist;
        !           118:   tree parm;
        !           119:   for (parm = parms; parm; parm = TREE_CHAIN (parm))
        !           120:     nparms++;
        !           121:   saved_parmlist = make_tree_vec (nparms);
        !           122: 
        !           123:   pushlevel (0);
        !           124: 
        !           125:   for (parm = parms, nparms = 0; parm; parm = TREE_CHAIN (parm), nparms++)
        !           126:     {
        !           127:       tree p = parm, decl;
        !           128:       if (TREE_CODE (p) == TREE_LIST)
        !           129:        {
        !           130:          tree t;
        !           131:          p = TREE_PURPOSE (p);
        !           132:          assert (TREE_CODE (p) == IDENTIFIER_NODE);
        !           133:          t = make_node (TEMPLATE_TYPE_PARM);
        !           134:          TEMPLATE_TYPE_SET_INFO (t, saved_parmlist, nparms);
        !           135:          decl = build_lang_decl (TYPE_DECL, p, t);
        !           136:          TYPE_NAME (t) = decl;
        !           137:        }
        !           138:       else
        !           139:        {
        !           140:          tree tinfo = make_node (TEMPLATE_CONST_PARM);
        !           141:          assert (TREE_PERMANENT (tinfo));
        !           142:          if (!TREE_PERMANENT (p))
        !           143:            {
        !           144:              tree old_p = p;
        !           145:              TREE_PERMANENT (old_p) = 1;
        !           146:              p = copy_node (p);
        !           147:              TREE_PERMANENT (old_p) = 0;
        !           148:            }
        !           149:          TEMPLATE_CONST_SET_INFO (tinfo, saved_parmlist, nparms);
        !           150:          TREE_TYPE (tinfo) = TREE_TYPE (p);
        !           151:          decl = build_decl (CONST_DECL, DECL_NAME (p), TREE_TYPE (p));
        !           152:          DECL_INITIAL (decl) = tinfo;
        !           153:        }
        !           154:       TREE_VEC_ELT (saved_parmlist, nparms) = p;
        !           155:       pushdecl (decl);
        !           156:     }
        !           157:   set_current_level_tags_transparency (1);
        !           158:   processing_template_decl++;
        !           159:   return saved_parmlist;
        !           160: }
        !           161: 
        !           162: /* end_template_decl is called after a template declaration is seen.
        !           163:    D1 is template header; D2 is class_head_sans_basetype or a
        !           164:    TEMPLATE_DECL with its DECL_RESULT field set.  */
        !           165: void
        !           166: end_template_decl (d1, d2, is_class)
        !           167:      tree d1, d2, is_class;
        !           168: {
        !           169:   tree decl;
        !           170:   struct template_info *tmpl;
        !           171: 
        !           172:   tmpl = (struct template_info *) obstack_alloc (&permanent_obstack,
        !           173:                                            sizeof (struct template_info));
        !           174:   tmpl->text = 0;
        !           175:   tmpl->length = 0;
        !           176:   tmpl->aggr = is_class;
        !           177: 
        !           178:   /* cloned from reinit_parse_for_template */
        !           179:   tmpl->filename = input_filename;
        !           180:   tmpl->lineno = lineno;
        !           181:   tmpl->parm_vec = d1;          /* [eichin:19911015.2306EST] */
        !           182: 
        !           183: #ifdef DEBUG_CP_BINDING_LEVELS
        !           184:   indent_to (stderr, debug_bindings_indentation);
        !           185:   fprintf (stderr, "end_template_decl");
        !           186:   debug_bindings_indentation += 4;
        !           187: #endif
        !           188: 
        !           189:   if (d2 == NULL_TREE || d2 == error_mark_node)
        !           190:     {
        !           191:       decl = 0;
        !           192:       goto lose;
        !           193:     }
        !           194: 
        !           195:   if (is_class)
        !           196:     {
        !           197:       decl = build_lang_decl (TEMPLATE_DECL, d2, NULL_TREE);
        !           198:     }
        !           199:   else
        !           200:     {
        !           201:       if (TREE_CODE (d2) == TEMPLATE_DECL)
        !           202:        decl = d2;
        !           203:       else
        !           204:        {
        !           205:          /* Class destructor templates and operator templates are
        !           206:             slipping past as non-template nodes.  Process them here, since
        !           207:             I haven't figured out where to catch them earlier.  I could
        !           208:             go do that, but it's a choice between getting that done and
        !           209:             staying only N months behind schedule.  Sorry....  */
        !           210:          enum tree_code code;
        !           211:          assert (TREE_CODE (d2) == CALL_EXPR);
        !           212:          code = TREE_CODE (TREE_OPERAND (d2, 0));
        !           213:          assert (code == BIT_NOT_EXPR
        !           214:                  || code == OP_IDENTIFIER
        !           215:                  || code == SCOPE_REF);
        !           216:          d2 = grokdeclarator (d2, NULL_TREE, MEMFUNCDEF, 0, NULL_TREE);
        !           217:          decl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (d2),
        !           218:                                  TREE_TYPE (d2));
        !           219:          DECL_TEMPLATE_RESULT (decl) = d2;
        !           220:          DECL_CONTEXT (decl) = DECL_CONTEXT (d2);
        !           221:          DECL_CLASS_CONTEXT (decl) = DECL_CLASS_CONTEXT (d2);
        !           222:          DECL_NAME (decl) = DECL_NAME (d2);
        !           223:          TREE_TYPE (decl) = TREE_TYPE (d2);
        !           224:          TREE_PUBLIC (decl) = TREE_PUBLIC (d2) = 0;
        !           225:          TREE_EXTERNAL (decl) = (TREE_EXTERNAL (d2)
        !           226:                                  && !(DECL_CLASS_CONTEXT (d2)
        !           227:                                       && !DECL_EXTERNAL (d2)));
        !           228:        }
        !           229: 
        !           230:       /* All routines creating TEMPLATE_DECL nodes should now be using
        !           231:         build_lang_decl, which will have set this up already.  */
        !           232:       assert (DECL_LANG_SPECIFIC (decl) != 0);
        !           233: 
        !           234:       /* @@ Somewhere, permanent allocation isn't being used.  */
        !           235:       if (! DECL_TEMPLATE_IS_CLASS (decl)
        !           236:          && TREE_CODE (DECL_TEMPLATE_RESULT (decl)) == FUNCTION_DECL)
        !           237:        {
        !           238:          tree result = DECL_TEMPLATE_RESULT (decl);
        !           239:          /* Will do nothing if allocation was already permanent.  */
        !           240:          DECL_ARGUMENTS (result) = copy_to_permanent (DECL_ARGUMENTS (result));
        !           241:        }
        !           242: 
        !           243:       /* If this is for a method, there's an extra binding level here. */
        !           244:       if (! DECL_TEMPLATE_IS_CLASS (decl)
        !           245:          && DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl)) != NULL_TREE)
        !           246:        {
        !           247:          /* @@ Find out where this should be getting set!  */
        !           248:          tree r = DECL_TEMPLATE_RESULT (decl);
        !           249:          if (DECL_CLASS_CONTEXT (r) == NULL_TREE)
        !           250:            DECL_CLASS_CONTEXT (r) = DECL_CONTEXT (r);
        !           251:        }
        !           252:     }
        !           253:   DECL_TEMPLATE_INFO (decl) = tmpl;
        !           254:   DECL_TEMPLATE_PARMS (decl) = d1;
        !           255: lose:
        !           256:   if (decl)
        !           257:     {
        !           258:       /* If context of decl is non-null (i.e., method template), add it
        !           259:         to the appropriate class template, and pop the binding levels.  */
        !           260:       if (! DECL_TEMPLATE_IS_CLASS (decl)
        !           261:          && DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl)) != NULL_TREE)
        !           262:        {
        !           263:          tree ctx = DECL_CONTEXT (DECL_TEMPLATE_RESULT (decl));
        !           264:          tree tmpl;
        !           265:          assert (TREE_CODE (ctx) == UNINSTANTIATED_P_TYPE);
        !           266:          tmpl = UPT_TEMPLATE (ctx);
        !           267:          DECL_TEMPLATE_MEMBERS (tmpl) =
        !           268:            perm_tree_cons (DECL_NAME (decl), decl,
        !           269:                            DECL_TEMPLATE_MEMBERS (tmpl));
        !           270:          poplevel (0, 0, 0);
        !           271:          poplevel (0, 0, 0);
        !           272:        }
        !           273:       /* Otherwise, go back to top level first, and push the template decl
        !           274:         again there.  */
        !           275:       else
        !           276:        {
        !           277:          poplevel (0, 0, 0);
        !           278:          poplevel (0, 0, 0);
        !           279:          if (TREE_TYPE (decl)
        !           280:              && IDENTIFIER_GLOBAL_VALUE (DECL_NAME (decl)) != NULL_TREE)
        !           281:            push_overloaded_decl (decl, 0);
        !           282:          else
        !           283:            pushdecl (decl);
        !           284:        }
        !           285:     }
        !           286: #if 0 /* It happens sometimes, with syntactic or semantic errors.
        !           287: 
        !           288:         One specific case:
        !           289:         template <class A, int X, int Y> class Foo { ... };
        !           290:         template <class A, int X, int y> Foo<X,Y>::method (Foo& x) { ... }
        !           291:         Note the missing "A" in the class containing "method".  */
        !           292:   assert (global_bindings_p ());
        !           293: #else
        !           294:   while (! global_bindings_p ())
        !           295:     poplevel (0, 0, 0);
        !           296: #endif
        !           297:   pop_obstacks ();
        !           298:   processing_template_decl--;
        !           299:   (void) get_pending_sizes ();
        !           300: #ifdef DEBUG_CP_BINDING_LEVELS
        !           301:   debug_bindings_indentation -= 4;
        !           302: #endif
        !           303: }
        !           304: 
        !           305: 
        !           306: /* Convert all template arguments to their appropriate types, and return
        !           307:    a vector containing the resulting values.  If any error occurs, return
        !           308:    error_mark_node.  */
        !           309: static tree
        !           310: coerce_template_parms (parms, arglist)
        !           311:      tree parms, arglist;
        !           312: {
        !           313:   int nparms, i, lost = 0;
        !           314:   tree vec;
        !           315: 
        !           316:   if (TREE_CODE (arglist) == TREE_VEC)
        !           317:     nparms = TREE_VEC_LENGTH (arglist);
        !           318:   else
        !           319:     nparms = list_length (arglist);
        !           320:   if (nparms != TREE_VEC_LENGTH (parms))
        !           321:     {
        !           322:       error ("incorrect number of parameters (%d, should be %d) in template expansion",
        !           323:             nparms, TREE_VEC_LENGTH (parms));
        !           324:       return error_mark_node;
        !           325:     }
        !           326: 
        !           327:   if (TREE_CODE (arglist) == TREE_VEC)
        !           328:     vec = copy_node (arglist);
        !           329:   else
        !           330:     {
        !           331:       vec = make_tree_vec (nparms);
        !           332:       for (i = 0; i < nparms; i++)
        !           333:        {
        !           334:          tree arg = arglist;
        !           335:          arglist = TREE_CHAIN (arglist);
        !           336:          if (arg == error_mark_node)
        !           337:            lost++;
        !           338:          else
        !           339:            arg = TREE_VALUE (arg);
        !           340:          TREE_VEC_ELT (vec, i) = arg;
        !           341:        }
        !           342:     }
        !           343:   for (i = 0; i < nparms; i++)
        !           344:     {
        !           345:       tree arg = TREE_VEC_ELT (vec, i);
        !           346:       tree parm = TREE_VEC_ELT (parms, i);
        !           347:       tree val;
        !           348:       int is_type, requires_type;
        !           349: 
        !           350:       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
        !           351:       requires_type = TREE_CODE (parm) == IDENTIFIER_NODE;
        !           352:       if (is_type != requires_type)
        !           353:        {
        !           354:          error ("type/value mismatch in template parameter list");
        !           355:          lost++;
        !           356:          TREE_VEC_ELT (vec, i) = error_mark_node;
        !           357:          continue;
        !           358:        }
        !           359:       if (is_type)
        !           360:        {
        !           361:          val = groktypename (arg);
        !           362:        }
        !           363:       else
        !           364:        {
        !           365:          val = digest_init (TREE_TYPE (parm), arg, (tree *) 0);
        !           366:        }
        !           367:       if (val == error_mark_node)
        !           368:        lost++;
        !           369:       TREE_VEC_ELT (vec, i) = val;
        !           370:     }
        !           371:   if (lost)
        !           372:     return error_mark_node;
        !           373:   return vec;
        !           374: }
        !           375: 
        !           376: /* Given class template name and parameter list, produce a user-friendly name
        !           377:    for the instantiation.  Note that this name isn't necessarily valid as
        !           378:    input to the compiler, because ">" characters may be adjacent.  */
        !           379: static char *
        !           380: mangle_class_name_for_template (name, parms, arglist)
        !           381:      char *name;
        !           382:      tree parms, arglist;
        !           383: {
        !           384:   static struct obstack scratch_obstack;
        !           385:   static char *scratch_firstobj;
        !           386:   int i, nparms;
        !           387:   char ibuf[100];
        !           388: 
        !           389:   if (!scratch_firstobj)
        !           390:     {
        !           391:       gcc_obstack_init (&scratch_obstack);
        !           392:       scratch_firstobj = obstack_alloc (&scratch_obstack, 1);
        !           393:     }
        !           394:   else
        !           395:     obstack_free (&scratch_obstack, scratch_firstobj);
        !           396: 
        !           397: #if 0
        !           398: #define buflen sizeof(buf)
        !           399: #define check  if (bufp >= buf+buflen-1) goto too_long
        !           400: #define ccat(c) *bufp++=(c); check
        !           401: #define advance        bufp+=strlen(bufp); check
        !           402: #define cat(s) strncpy(bufp, s, buf+buflen-bufp-1); advance
        !           403: #else
        !           404: #define check
        !           405: #define ccat(c)        obstack_1grow (&scratch_obstack, (c));
        !           406: #define advance
        !           407: #define cat(s) obstack_grow (&scratch_obstack, (s), strlen (s))
        !           408: #endif
        !           409: #define icat(n)        sprintf(ibuf,"%d",(n)); cat(ibuf)
        !           410: #define xcat(n)        sprintf(ibuf,"%ux",n); cat(ibuf)
        !           411: 
        !           412:   cat (name);
        !           413:   ccat ('<');
        !           414:   nparms = TREE_VEC_LENGTH (parms);
        !           415:   assert (nparms == TREE_VEC_LENGTH (arglist));
        !           416:   for (i = 0; i < nparms; i++)
        !           417:     {
        !           418:       tree parm = TREE_VEC_ELT (parms, i), arg = TREE_VEC_ELT (arglist, i);
        !           419:       tree type, id;
        !           420: 
        !           421:       if (i)
        !           422:        ccat (',');
        !           423: 
        !           424:       if (TREE_CODE (parm) == IDENTIFIER_NODE)
        !           425:        {
        !           426:          /* parm is a type */
        !           427:          extern char * type_as_string ();
        !           428:          char *typename;
        !           429: 
        !           430:          if (TYPE_NAME (arg)
        !           431:              && (TREE_CODE (arg) == RECORD_TYPE
        !           432:                  || TREE_CODE (arg) == UNION_TYPE
        !           433:                  || TREE_CODE (arg) == ENUMERAL_TYPE)
        !           434:              && DECL_NAME (TYPE_NAME (arg))
        !           435:              && IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (arg))))
        !           436:            typename = IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (arg)));
        !           437:          else
        !           438:            typename = type_as_string ((char *) 0, arg);
        !           439:          cat (typename);
        !           440:          continue;
        !           441:        }
        !           442:       else
        !           443:        assert (TREE_CODE (parm) == PARM_DECL);
        !           444: 
        !           445:       /* Should do conversions as for "const" initializers.  */
        !           446:       type = TREE_TYPE (parm);
        !           447:       id = DECL_NAME (parm);
        !           448:        
        !           449:       if (TREE_CODE (arg) == TREE_LIST)
        !           450:        {
        !           451:          /* New list cell was built because old chain link was in
        !           452:             use.  */
        !           453:          assert (TREE_PURPOSE (arg) == NULL_TREE);
        !           454:          arg = TREE_VALUE (arg);
        !           455:        }
        !           456:       
        !           457:       switch (TREE_CODE (type))
        !           458:        {
        !           459:        case INTEGER_TYPE:
        !           460:        case ENUMERAL_TYPE:
        !           461:          if (TREE_CODE (arg) == INTEGER_CST)
        !           462:            {
        !           463:              if (TREE_INT_CST_HIGH (arg) != (((int)TREE_INT_CST_LOW (arg)) >> (HOST_BITS_PER_INT - 1)))
        !           464:                {
        !           465:                  tree val = arg;
        !           466:                  if (TREE_INT_CST_HIGH (val) < 0)
        !           467:                    {
        !           468:                      ccat ('-');
        !           469:                      val = build_int_2 (~TREE_INT_CST_LOW (val),
        !           470:                                         -TREE_INT_CST_HIGH (val));
        !           471:                    }
        !           472:                  /* Would "%x%0*x" or "%x%*0x" get zero-padding on all
        !           473:                     systems?  */
        !           474:                  {
        !           475:                    static char format[10]; /* "%x%09999x\0" */
        !           476:                    if (!format[0])
        !           477:                      sprintf (format, "%%x%%0%dx", HOST_BITS_PER_INT / 4);
        !           478:                    sprintf (ibuf, format, TREE_INT_CST_HIGH (val),
        !           479:                             TREE_INT_CST_LOW (val));
        !           480:                    cat (ibuf);
        !           481:                  }
        !           482:                }
        !           483:              else
        !           484:                icat (TREE_INT_CST_LOW (arg));
        !           485:            }
        !           486:          else
        !           487:            {
        !           488:              error ("invalid integer constant for template parameter");
        !           489:              cat ("*error*");
        !           490:            }
        !           491:          break;
        !           492: #ifndef REAL_IS_NOT_DOUBLE
        !           493:        case REAL_TYPE:
        !           494:          sprintf (ibuf, "%e", TREE_REAL_CST (arg));
        !           495:          cat (ibuf);
        !           496:          break;
        !           497: #endif
        !           498:        case POINTER_TYPE:
        !           499:          if (TREE_CODE (arg) != ADDR_EXPR)
        !           500:            {
        !           501:              error ("invalid pointer constant for template parameter");
        !           502:              cat ("*error*");
        !           503:              break;
        !           504:            }
        !           505:          ccat ('&');
        !           506:          arg = TREE_OPERAND (arg, 0);
        !           507:          if (TREE_CODE (arg) == FUNCTION_DECL)
        !           508:            cat (fndecl_as_string (0, arg, 0));
        !           509:          else
        !           510:            {
        !           511:              assert (TREE_CODE_CLASS (TREE_CODE (arg)) == 'd');
        !           512:              cat (IDENTIFIER_POINTER (DECL_NAME (arg)));
        !           513:            }
        !           514:          break;
        !           515:        default:
        !           516:          sorry ("encoding %s as template parm",
        !           517:                 tree_code_name [(int) TREE_CODE (type)]);
        !           518:          abort ();
        !           519:        }
        !           520:     }
        !           521:   {
        !           522:     char *bufp = obstack_next_free (&scratch_obstack);
        !           523:     int offset = 0;
        !           524:     while (bufp[offset - 1] == ' ')
        !           525:       offset--;
        !           526:     obstack_blank_fast (&scratch_obstack, offset);
        !           527:   }
        !           528:   ccat ('>');
        !           529:   ccat ('\0');
        !           530:   return (char *) obstack_base (&scratch_obstack);
        !           531: 
        !           532:  too_long:
        !           533:   fatal ("out of (preallocated) string space creating template instantiation name");
        !           534:   /* NOTREACHED */
        !           535:   return NULL;
        !           536: }
        !           537: 
        !           538: /* Given an IDENTIFIER_NODE (type TEMPLATE_DECL) and a chain of
        !           539:    parameters, find the desired type.
        !           540: 
        !           541:    D1 is the PTYPENAME terminal, and ARGLIST is the list of arguments.
        !           542:    Since ARGLIST is build on the decl_obstack, we must copy it here
        !           543:    to keep it from being reclaimed when the decl storage is reclaimed. */
        !           544: tree
        !           545: lookup_template_class (d1, arglist)
        !           546:      tree d1, arglist;
        !           547: {
        !           548:   tree template, parmlist;
        !           549:   char *mangled_name;
        !           550:   tree id;
        !           551: 
        !           552:   assert (TREE_CODE (d1) == IDENTIFIER_NODE);
        !           553:   template = IDENTIFIER_GLOBAL_VALUE (d1); /* XXX */
        !           554:   assert (TREE_CODE (template) == TEMPLATE_DECL);
        !           555:   parmlist = DECL_TEMPLATE_PARMS (template);
        !           556: 
        !           557:   arglist = coerce_template_parms (parmlist, arglist);
        !           558:   if (arglist == error_mark_node)
        !           559:     return error_mark_node;
        !           560:   if (uses_template_parms (arglist))
        !           561:     {
        !           562:       tree t = make_lang_type (UNINSTANTIATED_P_TYPE);
        !           563:       tree d;
        !           564:       id = make_anon_name ();
        !           565:       d = build_lang_decl (TYPE_DECL, id, t);
        !           566:       TYPE_NAME (t) = d;
        !           567:       TYPE_VALUES (t) = build_tree_list (template, arglist);
        !           568:       pushdecl_top_level (d);
        !           569:     }
        !           570:   else
        !           571:     {
        !           572:       mangled_name = mangle_class_name_for_template (IDENTIFIER_POINTER (d1),
        !           573:                                                     parmlist, arglist);
        !           574:       id = get_identifier (mangled_name);
        !           575:     }
        !           576:   if (!IDENTIFIER_TEMPLATE (id))
        !           577:     {
        !           578:       arglist = copy_to_permanent (arglist);
        !           579:       IDENTIFIER_TEMPLATE (id) = perm_tree_cons (template, arglist, NULL_TREE);
        !           580:     }
        !           581:   return id;
        !           582: }
        !           583: 
        !           584: void
        !           585: push_template_decls (parmlist, arglist, class_level)
        !           586:      tree parmlist, arglist;
        !           587:      int class_level;
        !           588: {
        !           589:   int i, nparms;
        !           590: 
        !           591: #ifdef DEBUG_CP_BINDING_LEVELS
        !           592:   indent_to (stderr, debug_bindings_indentation);
        !           593:   fprintf (stderr, "push_template_decls");
        !           594:   debug_bindings_indentation += 4;
        !           595: #endif
        !           596: 
        !           597:   /* Don't want to push values into global context.  */
        !           598:   if (!class_level)
        !           599:     pushlevel (0);
        !           600:   nparms = TREE_VEC_LENGTH (parmlist);
        !           601: 
        !           602:   for (i = 0; i < nparms; i++)
        !           603:     {
        !           604:       int requires_type, is_type;
        !           605:       tree parm = TREE_VEC_ELT (parmlist, i);
        !           606:       tree arg = TREE_VEC_ELT (arglist, i);
        !           607:       tree decl = 0;
        !           608: 
        !           609:       requires_type = TREE_CODE (parm) == IDENTIFIER_NODE;
        !           610:       is_type = TREE_CODE_CLASS (TREE_CODE (arg)) == 't';
        !           611:       if (is_type)
        !           612:        {
        !           613:          /* add typename to namespace */
        !           614:          if (!requires_type)
        !           615:            {
        !           616:              error ("template use error: type provided where value needed");
        !           617:              continue;
        !           618:            }
        !           619:          decl = arg;
        !           620:          assert (TREE_CODE_CLASS (TREE_CODE (decl)) == 't');
        !           621:          decl = build_lang_decl (TYPE_DECL, parm, decl);
        !           622:        }
        !           623:       else
        !           624:        {
        !           625:          /* add const decl to namespace */
        !           626:          tree val;
        !           627:          if (requires_type)
        !           628:            {
        !           629:              error ("template use error: value provided where type needed");
        !           630:              continue;
        !           631:            }
        !           632:          val = digest_init (TREE_TYPE (parm), arg, (tree *) 0);
        !           633:          if (val != error_mark_node)
        !           634:            {
        !           635:              decl = build_decl (VAR_DECL, DECL_NAME (parm), TREE_TYPE (parm));
        !           636:              DECL_INITIAL (decl) = val;
        !           637:              TREE_READONLY (decl) = 1;
        !           638:            }
        !           639:        }
        !           640:       if (decl != 0)
        !           641:        {
        !           642:          layout_decl (decl, 0);
        !           643:          if (class_level)
        !           644:            pushdecl_class_level (decl);
        !           645:          else
        !           646:            pushdecl (decl);
        !           647:        }
        !           648:     }
        !           649:   if (!class_level)
        !           650:     set_current_level_tags_transparency (1);
        !           651: #ifdef DEBUG_CP_BINDING_LEVELS
        !           652:   debug_bindings_indentation -= 4;
        !           653: #endif
        !           654: }
        !           655: 
        !           656: void
        !           657: pop_template_decls (parmlist, arglist, class_level)
        !           658:      tree parmlist, arglist;
        !           659:      int class_level;
        !           660: {
        !           661: #ifdef DEBUG_CP_BINDING_LEVELS
        !           662:   indent_to (stderr, debug_bindings_indentation);
        !           663:   fprintf (stderr, "pop_template_decls");
        !           664:   debug_bindings_indentation += 4;
        !           665: #endif
        !           666: 
        !           667:   if (!class_level)
        !           668:     poplevel (0, 0, 0);
        !           669: 
        !           670: #ifdef DEBUG_CP_BINDING_LEVELS
        !           671:   debug_bindings_indentation -= 4;
        !           672: #endif
        !           673: }
        !           674: 
        !           675: /* Should be defined in cp-parse.h.  */
        !           676: extern int yychar;
        !           677: 
        !           678: int
        !           679: uses_template_parms (t)
        !           680:      tree t;
        !           681: {
        !           682:   if (!t)
        !           683:     return 0;
        !           684:   switch (TREE_CODE (t))
        !           685:     {
        !           686:     case INDIRECT_REF:
        !           687:     case COMPONENT_REF:
        !           688:       /* We assume that the object must be instantiated in order to build
        !           689:         the COMPONENT_REF, so we test only whether the type of the
        !           690:         COMPONENT_REF uses template parms.  */
        !           691:       return uses_template_parms (TREE_TYPE (t));
        !           692: 
        !           693:     case IDENTIFIER_NODE:
        !           694:       if (!IDENTIFIER_TEMPLATE (t))
        !           695:        return 0;
        !           696:       return uses_template_parms (TREE_VALUE (IDENTIFIER_TEMPLATE (t)));
        !           697: 
        !           698:       /* aggregates of tree nodes */
        !           699:     case TREE_VEC:
        !           700:       {
        !           701:        int i = TREE_VEC_LENGTH (t);
        !           702:        while (i--)
        !           703:          if (uses_template_parms (TREE_VEC_ELT (t, i)))
        !           704:            return 1;
        !           705:        return 0;
        !           706:       }
        !           707:     case TREE_LIST:
        !           708:       if (uses_template_parms (TREE_PURPOSE (t))
        !           709:          || uses_template_parms (TREE_VALUE (t)))
        !           710:        return 1;
        !           711:       return uses_template_parms (TREE_CHAIN (t));
        !           712: 
        !           713:       /* constructed type nodes */
        !           714:     case POINTER_TYPE:
        !           715:     case REFERENCE_TYPE:
        !           716:       return uses_template_parms (TREE_TYPE (t));
        !           717:     case RECORD_TYPE:
        !           718:     case UNION_TYPE:
        !           719:       if (!TYPE_NAME (t))
        !           720:        return 0;
        !           721:       if (!DECL_NAME (TYPE_NAME (t)))
        !           722:        return 0;
        !           723:       return uses_template_parms (DECL_NAME (TYPE_NAME (t)));
        !           724:     case FUNCTION_TYPE:
        !           725:       if (uses_template_parms (TYPE_ARG_TYPES (t)))
        !           726:        return 1;
        !           727:       return uses_template_parms (TREE_TYPE (t));
        !           728:     case ARRAY_TYPE:
        !           729:       if (uses_template_parms (TYPE_DOMAIN (t)))
        !           730:        return 1;
        !           731:       return uses_template_parms (TREE_TYPE (t));
        !           732:     case OFFSET_TYPE:
        !           733:       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
        !           734:        return 1;
        !           735:       return uses_template_parms (TREE_TYPE (t));
        !           736:     case METHOD_TYPE:
        !           737:       if (uses_template_parms (TYPE_OFFSET_BASETYPE (t)))
        !           738:        return 1;
        !           739:       if (uses_template_parms (TYPE_ARG_TYPES (t)))
        !           740:        return 1;
        !           741:       return uses_template_parms (TREE_TYPE (t));
        !           742: 
        !           743:       /* decl nodes */
        !           744:     case TYPE_DECL:
        !           745:       return uses_template_parms (DECL_NAME (t));
        !           746:     case FUNCTION_DECL:
        !           747:       if (uses_template_parms (TREE_TYPE (t)))
        !           748:        return 1;
        !           749:       /* fall through */
        !           750:     case VAR_DECL:
        !           751:     case PARM_DECL:
        !           752:       /* ??? What about FIELD_DECLs?  */
        !           753:       /* The type of a decl can't use template parms if the name of the
        !           754:         variable doesn't, because it's impossible to resolve them.  So
        !           755:         ignore the type field for now.  */
        !           756:       if (DECL_CONTEXT (t) && uses_template_parms (DECL_CONTEXT (t)))
        !           757:        return 1;
        !           758:       if (uses_template_parms (TREE_TYPE (t)))
        !           759:        {
        !           760:          error ("template parms used where they can't be resolved");
        !           761:        }
        !           762:       return 0;
        !           763: 
        !           764:     case CALL_EXPR:
        !           765:       return uses_template_parms (TREE_TYPE (t));
        !           766:     case ADDR_EXPR:
        !           767:       return uses_template_parms (TREE_OPERAND (t, 0));
        !           768: 
        !           769:       /* template parm nodes */
        !           770:     case TEMPLATE_TYPE_PARM:
        !           771:     case TEMPLATE_CONST_PARM:
        !           772:       return 1;
        !           773: 
        !           774:       /* simple type nodes */
        !           775:     case INTEGER_TYPE:
        !           776:       if (uses_template_parms (TYPE_MIN_VALUE (t)))
        !           777:        return 1;
        !           778:       return uses_template_parms (TYPE_MAX_VALUE (t));
        !           779: 
        !           780:     case REAL_TYPE:
        !           781:     case VOID_TYPE:
        !           782:     case ENUMERAL_TYPE:
        !           783:       return 0;
        !           784: 
        !           785:       /* constants */
        !           786:     case INTEGER_CST:
        !           787:     case REAL_CST:
        !           788:     case STRING_CST:
        !           789:       return 0;
        !           790: 
        !           791:     case ERROR_MARK:
        !           792:       /* Non-error_mark_node ERROR_MARKs are bad things.  */
        !           793:       assert (t == error_mark_node);
        !           794:       /* NOTREACHED */
        !           795:       return 0;
        !           796: 
        !           797:     case UNINSTANTIATED_P_TYPE:
        !           798:       return 1;
        !           799: 
        !           800:     default:
        !           801:       switch (TREE_CODE_CLASS (TREE_CODE (t)))
        !           802:        {
        !           803:        case '1':
        !           804:        case '2':
        !           805:        case '3':
        !           806:        case '<':
        !           807:          {
        !           808:            int i;
        !           809:            for (i = tree_code_length[(int) TREE_CODE (t)]; --i >= 0;)
        !           810:              if (uses_template_parms (TREE_OPERAND (t, i)))
        !           811:                return 1;
        !           812:            return 0;
        !           813:          }
        !           814:        default:
        !           815:          break;
        !           816:        }
        !           817:       sorry ("testing %s for template parms",
        !           818:             tree_code_name [(int) TREE_CODE (t)]);
        !           819:       abort ();
        !           820:       /* NOTREACHED */
        !           821:       return 0;
        !           822:     }
        !           823: }
        !           824: 
        !           825: void
        !           826: instantiate_member_templates (arg)
        !           827:      tree arg;
        !           828: {
        !           829:   tree t;
        !           830:   tree classname = TREE_VALUE (arg);
        !           831:   tree id = classname;
        !           832:   tree members = DECL_TEMPLATE_MEMBERS (TREE_PURPOSE (IDENTIFIER_TEMPLATE (id)));
        !           833: 
        !           834:   for (t = members; t; t = TREE_CHAIN (t))
        !           835:     {
        !           836:       tree parmvec, type, classparms, tdecl, t2;
        !           837:       int nparms, xxx, i;
        !           838: 
        !           839:       assert (TREE_VALUE (t) != NULL_TREE);
        !           840:       assert (TREE_CODE (TREE_VALUE (t)) == TEMPLATE_DECL);
        !           841:       /* @@ Should verify that class parm list is a list of
        !           842:         distinct template parameters, and covers all the template
        !           843:         parameters.  */
        !           844:       tdecl = TREE_VALUE (t);
        !           845:       type = DECL_CONTEXT (DECL_TEMPLATE_RESULT (tdecl));
        !           846:       classparms = UPT_PARMS (type);
        !           847:       nparms = TREE_VEC_LENGTH (classparms);
        !           848:       parmvec = make_tree_vec (nparms);
        !           849:       for (i = 0; i < nparms; i++)
        !           850:        TREE_VEC_ELT (parmvec, i) = NULL_TREE;
        !           851:       switch (unify (DECL_TEMPLATE_PARMS (tdecl),
        !           852:                     &TREE_VEC_ELT (parmvec, 0), nparms,
        !           853:                     type, IDENTIFIER_TYPE_VALUE (classname),
        !           854:                     &xxx))
        !           855:        {
        !           856:        case 0:
        !           857:          /* Success -- well, no inconsistency, at least.  */
        !           858:          for (i = 0; i < nparms; i++)
        !           859:            if (TREE_VEC_ELT (parmvec, i) == NULL_TREE)
        !           860:              goto failure;
        !           861:          t2 = instantiate_template (tdecl,
        !           862:                                     &TREE_VEC_ELT (parmvec, 0));
        !           863:          type = IDENTIFIER_TYPE_VALUE (id);
        !           864: #if 0
        !           865:          print_node_brief (stderr, "producing ", t2, 0);
        !           866:          print_node_brief (stderr, "\n\tfrom template ", tdecl, 0);
        !           867:          fprintf (stderr, "\n");
        !           868: #endif
        !           869:          assert (type != 0);
        !           870:          if (CLASSTYPE_INTERFACE_UNKNOWN (type))
        !           871:            {
        !           872:              TREE_EXTERNAL (t2) = 0;
        !           873:              TREE_PUBLIC (t2) = 0;
        !           874:            }
        !           875:          else
        !           876:            {
        !           877:              TREE_EXTERNAL (t2) = CLASSTYPE_INTERFACE_ONLY (type);
        !           878:              TREE_PUBLIC (t2) = ! CLASSTYPE_INTERFACE_ONLY (type);
        !           879:            }
        !           880:          break;
        !           881:        case 1:
        !           882:          /* Failure.  */
        !           883:        failure:
        !           884:          error ("type unification error instantiating %s::%s",
        !           885:                 IDENTIFIER_POINTER (classname),
        !           886:                 IDENTIFIER_POINTER (DECL_NAME (tdecl)));
        !           887:          continue /* loop of members */;
        !           888:        default:
        !           889:          /* Eek, a bug.  */
        !           890:          abort ();
        !           891:        }
        !           892:     }
        !           893: }
        !           894: 
        !           895: tree
        !           896: instantiate_class_template (classname, setup_parse)
        !           897:      tree classname;
        !           898:      int setup_parse;
        !           899: {
        !           900:   struct template_info *template_info;
        !           901:   tree template, t1;
        !           902: 
        !           903:   if (classname == error_mark_node)
        !           904:     return error_mark_node;
        !           905: 
        !           906:   assert (TREE_CODE (classname) == IDENTIFIER_NODE);
        !           907:   template = IDENTIFIER_TEMPLATE (classname);
        !           908: 
        !           909:   if (IDENTIFIER_HAS_TYPE_VALUE (classname))
        !           910:     {
        !           911:       tree type = IDENTIFIER_TYPE_VALUE (classname);
        !           912:       if (TREE_CODE (type) == UNINSTANTIATED_P_TYPE)
        !           913:        return type;
        !           914:       if (TYPE_BEING_DEFINED (type)
        !           915:          || TYPE_SIZE (type)
        !           916:          || CLASSTYPE_USE_TEMPLATE (type) != 0)
        !           917:        return type;
        !           918:     }
        !           919:   if (uses_template_parms (classname))
        !           920:     {
        !           921:       if (!TREE_TYPE (classname))
        !           922:        {
        !           923:          tree t = make_lang_type (RECORD_TYPE);
        !           924:          tree d = build_lang_decl (TYPE_DECL, classname, t);
        !           925:          DECL_NAME (d) = classname;
        !           926:          TYPE_NAME (t) = d;
        !           927:          pushdecl (d);
        !           928:        }
        !           929:       return NULL_TREE;
        !           930:     }
        !           931: 
        !           932:   t1 = TREE_PURPOSE (template);
        !           933:   assert (TREE_CODE (t1) == TEMPLATE_DECL);
        !           934: 
        !           935:   if (DECL_TEMPLATE_INFO (t1)->text == 0)
        !           936:     {
        !           937:       error ("template `%s' declared but not defined",
        !           938:             IDENTIFIER_POINTER (DECL_NAME (t1)));
        !           939:       return error_mark_node;
        !           940:     }
        !           941: 
        !           942: #ifdef DEBUG_CP_BINDING_LEVELS
        !           943:   indent_to (stderr, debug_bindings_indentation);
        !           944:   fprintf (stderr, "instantiate_class_template");
        !           945:   debug_bindings_indentation += 4;
        !           946: #endif
        !           947: 
        !           948:   if (setup_parse)
        !           949:     {
        !           950:       push_to_top_level ();
        !           951:       push_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (template)),
        !           952:                           TREE_VALUE (template), 0);
        !           953:       set_current_level_tags_transparency (1);
        !           954:       template_info = DECL_TEMPLATE_INFO (t1);
        !           955:       feed_input (template_info->text, template_info->length, (struct obstack *)0);
        !           956:       lineno = template_info->lineno;
        !           957:       input_filename = template_info->filename;
        !           958:       /* Get interface/implementation back in sync.  */
        !           959:       extract_interface_info ();
        !           960:       overload_template_name (classname, 0);
        !           961:       yychar = PRE_PARSED_CLASS_DECL;
        !           962:       yylval.ttype = build_tree_list (class_type_node, classname);
        !           963:       processing_template_defn++;
        !           964:     }
        !           965:   else
        !           966:     {
        !           967:       tree t, decl, id, tmpl;
        !           968: 
        !           969:       push_to_top_level ();
        !           970:       push_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (template)),
        !           971:                           TREE_VALUE (template), 0);
        !           972:       set_current_level_tags_transparency (1);
        !           973:       template_info = DECL_TEMPLATE_INFO (t1);
        !           974:       id = classname;
        !           975:       tmpl = TREE_PURPOSE (IDENTIFIER_TEMPLATE (id));
        !           976:       t = xref_tag (DECL_TEMPLATE_INFO (tmpl)->aggr, id, NULL_TREE);
        !           977:       assert (TREE_CODE (t) == RECORD_TYPE);
        !           978: #if 1
        !           979:       lineno = template_info->lineno;
        !           980:       input_filename = template_info->filename;
        !           981:       /* Get interface/implementation back in sync.  */
        !           982:       extract_interface_info ();
        !           983: #endif
        !           984: 
        !           985:       /* Now, put a copy of the decl in global scope, to avoid
        !           986:        * recursive expansion.  */
        !           987:       decl = IDENTIFIER_LOCAL_VALUE (id);
        !           988:       if (!decl)
        !           989:        decl = IDENTIFIER_CLASS_VALUE (id);
        !           990:       if (decl)
        !           991:        {
        !           992:          assert (TREE_CODE (decl) == TYPE_DECL);
        !           993:          pushdecl_top_level (copy_node (decl));
        !           994:        }
        !           995:       pop_from_top_level ();
        !           996:     }
        !           997: 
        !           998: #ifdef DEBUG_CP_BINDING_LEVELS
        !           999:   debug_bindings_indentation -= 4;
        !          1000: #endif
        !          1001: 
        !          1002:   return NULL_TREE;
        !          1003: }
        !          1004: 
        !          1005: static tree
        !          1006: tsubst (t, args, nargs)
        !          1007:      tree t, *args;
        !          1008: {
        !          1009:   tree type;
        !          1010:   if (t == NULL_TREE)
        !          1011:     return t;
        !          1012:   type = TREE_TYPE (t);
        !          1013:   if (type
        !          1014:       && type != integer_type_node
        !          1015:       && type != void_type_node
        !          1016:       && type != char_type_node)
        !          1017:     type = build_type_variant (tsubst (type, args, nargs),
        !          1018:                               TYPE_READONLY (type),
        !          1019:                               TYPE_VOLATILE (type));
        !          1020:   if (type != TREE_TYPE (t))
        !          1021:     layout_type (t);
        !          1022:   switch (TREE_CODE (t))
        !          1023:     {
        !          1024:     case ERROR_MARK:
        !          1025:     case IDENTIFIER_NODE:
        !          1026:     case OP_IDENTIFIER:
        !          1027:     case VOID_TYPE:
        !          1028:     case REAL_TYPE:
        !          1029:     case ENUMERAL_TYPE:
        !          1030:     case INTEGER_CST:
        !          1031:     case REAL_CST:
        !          1032:     case STRING_CST:
        !          1033:     case RECORD_TYPE:
        !          1034:     case UNION_TYPE:
        !          1035:       return t;
        !          1036: 
        !          1037:     case INTEGER_TYPE:
        !          1038:       if (t == integer_type_node)
        !          1039:        return t;
        !          1040: 
        !          1041:       if (TREE_CODE (TYPE_MIN_VALUE (t)) == INTEGER_CST
        !          1042:          && TREE_CODE (TYPE_MAX_VALUE (t)) == INTEGER_CST)
        !          1043:        return t;
        !          1044:       return build_index_2_type (tsubst (TYPE_MIN_VALUE (t), args, nargs),
        !          1045:                                 tsubst (TYPE_MAX_VALUE (t), args, nargs));
        !          1046: 
        !          1047:     case TEMPLATE_TYPE_PARM:
        !          1048:       return build_type_variant (args[TEMPLATE_TYPE_IDX (t)],
        !          1049:                                 TYPE_READONLY (t),
        !          1050:                                 TYPE_VOLATILE (t));
        !          1051: 
        !          1052:     case TEMPLATE_CONST_PARM:
        !          1053:       return args[TEMPLATE_CONST_IDX (t)];
        !          1054: 
        !          1055:     case FUNCTION_DECL:
        !          1056:       {
        !          1057:        tree r;
        !          1058:        tree fnargs, result;
        !          1059:        
        !          1060:        if (type == TREE_TYPE (t)
        !          1061:            && DECL_CONTEXT (t) == NULL_TREE)
        !          1062:          return t;
        !          1063:        fnargs = tsubst (DECL_ARGUMENTS (t), args, nargs);
        !          1064:        result = tsubst (DECL_RESULT (t), args, nargs);
        !          1065:        if (DECL_CONTEXT (t))
        !          1066:          {
        !          1067:            /* Look it up in that class, and return the decl node there,
        !          1068:               instead of creating a new one.  */
        !          1069:            tree ctx = tsubst (DECL_CONTEXT (t), args, nargs);
        !          1070:            tree methods = CLASSTYPE_METHOD_VEC (ctx);
        !          1071:            tree name = DECL_NAME (t);
        !          1072:            tree method;
        !          1073:            int n_methods = TREE_VEC_LENGTH (methods);
        !          1074:            int i, found = 0;
        !          1075: 
        !          1076:            r = NULL_TREE;
        !          1077: 
        !          1078:            if (DECL_CONTEXT (t)
        !          1079:                && constructor_name (DECL_CONTEXT (t)) == DECL_NAME (t))
        !          1080:              name = constructor_name (ctx);
        !          1081: #if 0
        !          1082:            fprintf (stderr, "\nfor function %s in class %s:\n",
        !          1083:                     IDENTIFIER_POINTER (name),
        !          1084:                     IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (ctx))));
        !          1085: #endif
        !          1086:            for (i = 0; i < n_methods; i++)
        !          1087:              {
        !          1088:                method = TREE_VEC_ELT (methods, i);
        !          1089:                if (method == NULL_TREE || DECL_NAME (method) != name)
        !          1090:                  continue;
        !          1091:                for (; method; method = TREE_CHAIN (method))
        !          1092:                  {
        !          1093:                    assert (TREE_CODE (method) == FUNCTION_DECL);
        !          1094:                    if (TREE_TYPE (method) != type)
        !          1095:                      {
        !          1096:                        found = 1;
        !          1097:                        continue;
        !          1098:                      }
        !          1099: #if 0
        !          1100:                    fprintf (stderr, "\tfound %s\n\n",
        !          1101:                             IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (method)));
        !          1102: #endif
        !          1103: 
        !          1104:                    if (! TREE_PERMANENT (DECL_ARGUMENTS (method)))
        !          1105:                      /* @@ Is this early enough?  Might we want to do
        !          1106:                         this instead while processing the expansion?    */
        !          1107:                      DECL_ARGUMENTS (method)
        !          1108:                        = tsubst (DECL_ARGUMENTS (t), args, nargs);
        !          1109:                    r = method;
        !          1110:                    break;
        !          1111:                  }
        !          1112:              }
        !          1113:            if (r == NULL_TREE)
        !          1114:              {
        !          1115:                error (found
        !          1116:                       ? "template for method `%s' doesn't match any in class `%s'"
        !          1117:                       : "method `%s' not found in class `%s'",
        !          1118:                       IDENTIFIER_POINTER (name),
        !          1119:                       IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (ctx))));
        !          1120:                return error_mark_node;
        !          1121:              }
        !          1122:          }
        !          1123:        else
        !          1124:          {
        !          1125:            r = DECL_NAME (t);
        !          1126:            r = build_decl_overload (IDENTIFIER_POINTER (r),
        !          1127:                                     TYPE_VALUES (type),
        !          1128:                                     DECL_CONTEXT (t) != NULL_TREE);
        !          1129:            r = build_lang_decl (FUNCTION_DECL, r, type);
        !          1130:          }
        !          1131:        TREE_PUBLIC (r) = TREE_PUBLIC (t);
        !          1132:        TREE_EXTERNAL (r) = TREE_EXTERNAL (t);
        !          1133:        TREE_STATIC (r) = TREE_STATIC (t);
        !          1134:        TREE_INLINE (r) = TREE_INLINE (t);
        !          1135:        DECL_SOURCE_FILE (r) = DECL_SOURCE_FILE (t);
        !          1136:        DECL_SOURCE_LINE (r) = DECL_SOURCE_LINE (t);
        !          1137:        DECL_CLASS_CONTEXT (r) = tsubst (DECL_CLASS_CONTEXT (t), args, nargs);
        !          1138:        make_decl_rtl (r, 0, 1);
        !          1139:        DECL_ARGUMENTS (r) = fnargs;
        !          1140:        DECL_RESULT (r) = result;
        !          1141:        if (DECL_CONTEXT (t) == NULL_TREE)
        !          1142:          push_overloaded_decl_top_level (r, 0);
        !          1143:        return r;
        !          1144:       }
        !          1145: 
        !          1146:     case PARM_DECL:
        !          1147:       {
        !          1148:        tree r;
        !          1149:        r = build_decl (PARM_DECL, DECL_NAME (t), type);
        !          1150:        DECL_INITIAL (r) = TREE_TYPE (r);
        !          1151:        if (TREE_CHAIN (t))
        !          1152:          TREE_CHAIN (r) = tsubst (TREE_CHAIN (t), args, nargs);
        !          1153:        return r;
        !          1154:       }
        !          1155: 
        !          1156:     case TREE_LIST:
        !          1157:       {
        !          1158:        tree purpose, value, chain, result;
        !          1159:        int via_public, via_virtual;
        !          1160: 
        !          1161:        if (t == void_list_node)
        !          1162:          return t;
        !          1163: 
        !          1164:        via_public = TREE_VIA_PUBLIC (t);
        !          1165:        via_virtual = TREE_VIA_VIRTUAL (t);
        !          1166: 
        !          1167:        purpose = TREE_PURPOSE (t);
        !          1168:        if (purpose)
        !          1169:          purpose = tsubst (purpose, args, nargs);
        !          1170:        value = TREE_VALUE (t);
        !          1171:        if (value)
        !          1172:          value = tsubst (value, args, nargs);
        !          1173:        chain = TREE_CHAIN (t);
        !          1174:        if (chain
        !          1175:            && chain != void_type_node)
        !          1176:          chain = tsubst (chain, args, nargs);
        !          1177:        if (purpose == TREE_PURPOSE (t)
        !          1178:            && value == TREE_VALUE (t)
        !          1179:            && chain == TREE_CHAIN (t))
        !          1180:          return t;
        !          1181:        result = hash_tree_cons (via_public, via_virtual,
        !          1182:                                 purpose, value, chain);
        !          1183:        TREE_PARMLIST (result) = TREE_PARMLIST (t);
        !          1184:        return result;
        !          1185:       }
        !          1186:     case TREE_VEC:
        !          1187:       {
        !          1188:        int len = TREE_VEC_LENGTH (t), need_new = 0, i;
        !          1189:        tree *elts = (tree *) alloca (len * sizeof (tree));
        !          1190:        bzero (elts, len * sizeof (tree));
        !          1191: 
        !          1192:        for (i = 0; i < len; i++)
        !          1193:          {
        !          1194:            elts[i] = tsubst (TREE_VEC_ELT (t, i), args, nargs);
        !          1195:            if (elts[i] != TREE_VEC_ELT (t, i))
        !          1196:              need_new = 1;
        !          1197:          }
        !          1198: 
        !          1199:        if (!need_new)
        !          1200:          return t;
        !          1201: 
        !          1202:        t = make_tree_vec (len);
        !          1203:        for (i = 0; i < len; i++)
        !          1204:          TREE_VEC_ELT (t, i) = elts[i];
        !          1205:        return t;
        !          1206:       }
        !          1207:     case POINTER_TYPE:
        !          1208:     case REFERENCE_TYPE:
        !          1209:       {
        !          1210:        tree r;
        !          1211:        enum tree_code code;
        !          1212:        if (type == TREE_TYPE (t))
        !          1213:          return t;
        !          1214: 
        !          1215:        code = TREE_CODE (t);
        !          1216:        if (code == POINTER_TYPE)
        !          1217:          r = build_pointer_type (type);
        !          1218:        else
        !          1219:          r = build_reference_type (type);
        !          1220:        r = build_type_variant (r, TYPE_READONLY (t), TYPE_VOLATILE (t));
        !          1221:        /* Will this ever be needed for TYPE_..._TO values?  */
        !          1222:        layout_type (r);
        !          1223:        return r;
        !          1224:       }
        !          1225:     case FUNCTION_TYPE:
        !          1226:     case METHOD_TYPE:
        !          1227:       {
        !          1228:        tree values = TYPE_VALUES (t); /* same as TYPE_ARG_TYPES */
        !          1229:        tree context = TYPE_CONTEXT (t);
        !          1230:        tree new_value;
        !          1231: 
        !          1232:        /* Don't bother recursing if we know it won't change anything.  */
        !          1233:        if (! (values == void_type_node
        !          1234:               || values == integer_type_node))
        !          1235:          values = tsubst (values, args, nargs);
        !          1236:        if (context)
        !          1237:          context = tsubst (context, args, nargs);
        !          1238:        /* Could also optimize cases where return value and
        !          1239:           values have common elements (e.g., T min(const &T, const T&).  */
        !          1240: 
        !          1241:        /* If the above parameters haven't changed, just return the type.  */
        !          1242:        if (type == TREE_TYPE (t)
        !          1243:            && values == TYPE_VALUES (t)
        !          1244:            && context == TYPE_CONTEXT (t))
        !          1245:          return t;
        !          1246: 
        !          1247:        /* Construct a new type node and return it.  */
        !          1248:        if (TREE_CODE (t) == FUNCTION_TYPE
        !          1249:            && context == NULL_TREE)
        !          1250:          {
        !          1251:            new_value = build_function_type (type, values);
        !          1252:          }
        !          1253:        else if (context == NULL_TREE)
        !          1254:          {
        !          1255:            tree base = tsubst (TYPE_METHOD_BASETYPE (t), args, nargs);
        !          1256:            new_value = build_cplus_method_type (base, type,
        !          1257:                                                 TREE_CHAIN (values));
        !          1258:          }
        !          1259:        else
        !          1260:          {
        !          1261:            new_value = make_node (TREE_CODE (t));
        !          1262:            TREE_TYPE (new_value) = type;
        !          1263:            TYPE_CONTEXT (new_value) = context;
        !          1264:            TYPE_VALUES (new_value) = values;
        !          1265:            TYPE_SIZE (new_value) = TYPE_SIZE (t);
        !          1266:            TYPE_ALIGN (new_value) = TYPE_ALIGN (t);
        !          1267:            TYPE_MODE (new_value) = TYPE_MODE (t);
        !          1268:            if (TYPE_METHOD_BASETYPE (t))
        !          1269:              TYPE_METHOD_BASETYPE (new_value) = tsubst (TYPE_METHOD_BASETYPE (t),
        !          1270:                                                         args, nargs);
        !          1271:            /* Need to generate hash value.  */
        !          1272:            abort ();
        !          1273:          }
        !          1274:        new_value = build_type_variant (new_value,
        !          1275:                                        TYPE_READONLY (new_value),
        !          1276:                                        TYPE_VOLATILE (new_value));
        !          1277:        return new_value;
        !          1278:       }
        !          1279:     case ARRAY_TYPE:
        !          1280:       {
        !          1281:        tree domain = tsubst (TYPE_DOMAIN (t), args, nargs);
        !          1282:        tree r;
        !          1283:        if (type == TREE_TYPE (t) && domain == TYPE_DOMAIN (t))
        !          1284:          return t;
        !          1285:        r = build_cplus_array_type (type, domain);
        !          1286:        return r;
        !          1287:       }
        !          1288: 
        !          1289:     case UNINSTANTIATED_P_TYPE:
        !          1290:       {
        !          1291:        int nparms = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (UPT_TEMPLATE (t)));
        !          1292:        tree argvec = make_tree_vec (nparms);
        !          1293:        tree parmvec = UPT_PARMS (t);
        !          1294:        int i;
        !          1295:        tree id;
        !          1296:        for (i = 0; i < nparms; i++)
        !          1297:          TREE_VEC_ELT (argvec, i) = tsubst (TREE_VEC_ELT (parmvec, i),
        !          1298:                                             args, nargs);
        !          1299:        id = lookup_template_class (DECL_NAME (UPT_TEMPLATE (t)), argvec);
        !          1300:        if (! IDENTIFIER_HAS_TYPE_VALUE (id)) {
        !          1301:          instantiate_class_template(id, 0);
        !          1302:          /* set up pending_classes */
        !          1303:          add_pending_template (id);
        !          1304: 
        !          1305:          TYPE_MAIN_VARIANT (IDENTIFIER_TYPE_VALUE (id)) =
        !          1306:            IDENTIFIER_TYPE_VALUE (id);
        !          1307:        }
        !          1308:        return IDENTIFIER_TYPE_VALUE (id);
        !          1309:       }
        !          1310: 
        !          1311:     case MINUS_EXPR:
        !          1312:     case PLUS_EXPR:
        !          1313:       return fold (build (TREE_CODE (t), TREE_TYPE (t),
        !          1314:                          tsubst (TREE_OPERAND (t, 0), args, nargs),
        !          1315:                          tsubst (TREE_OPERAND (t, 1), args, nargs)));
        !          1316: 
        !          1317:     case NEGATE_EXPR:
        !          1318:     case NOP_EXPR:
        !          1319:       return fold (build1 (TREE_CODE (t), TREE_TYPE (t),
        !          1320:                           tsubst (TREE_OPERAND (t, 0), args, nargs)));
        !          1321: 
        !          1322:     default:
        !          1323:       sorry ("use of `%s' in function template",
        !          1324:             tree_code_name [(int) TREE_CODE (t)]);
        !          1325:       return error_mark_node;
        !          1326:     }
        !          1327: }
        !          1328: 
        !          1329: tree
        !          1330: instantiate_template (tmpl, targ_ptr)
        !          1331:      tree tmpl, *targ_ptr;
        !          1332: {
        !          1333:   tree targs, fndecl;
        !          1334:   int i, len;
        !          1335:   struct pending_inline *p;
        !          1336:   struct template_info *t;
        !          1337:   struct obstack *old_fmp_obstack;
        !          1338:   extern struct obstack *function_maybepermanent_obstack;
        !          1339: 
        !          1340:   push_obstacks (&permanent_obstack, &permanent_obstack);
        !          1341:   old_fmp_obstack = function_maybepermanent_obstack;
        !          1342:   function_maybepermanent_obstack = &permanent_obstack;
        !          1343: 
        !          1344:   assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
        !          1345:   len = TREE_VEC_LENGTH (DECL_TEMPLATE_PARMS (tmpl));
        !          1346: 
        !          1347:   for (fndecl = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
        !          1348:        fndecl; fndecl = TREE_CHAIN (fndecl))
        !          1349:     {
        !          1350:       tree *t1 = &TREE_VEC_ELT (TREE_PURPOSE (fndecl), 0);
        !          1351:       for (i = len - 1; i >= 0; i--)
        !          1352:        if (t1[i] != targ_ptr[i])
        !          1353:          goto no_match;
        !          1354: 
        !          1355:       /* Here, we have a match.  */
        !          1356:       fndecl = TREE_VALUE (fndecl);
        !          1357:       function_maybepermanent_obstack = old_fmp_obstack;
        !          1358:       pop_obstacks ();
        !          1359:       return fndecl;
        !          1360: 
        !          1361:     no_match:
        !          1362:       ;
        !          1363:     }
        !          1364: 
        !          1365:   targs = make_tree_vec (len);
        !          1366:   i = len;
        !          1367:   while (i--)
        !          1368:     TREE_VEC_ELT (targs, i) = targ_ptr[i];
        !          1369: 
        !          1370:   /* substitute template parameters */
        !          1371:   fndecl = tsubst (DECL_RESULT (tmpl), targ_ptr,
        !          1372:                   TREE_VEC_LENGTH (targs));
        !          1373:   p = (struct pending_inline *) permalloc (sizeof (struct pending_inline));
        !          1374:   t = DECL_TEMPLATE_INFO (tmpl);
        !          1375:   p->parm_vec = t->parm_vec;
        !          1376:   p->bindings = targs;
        !          1377:   p->can_free = 0;
        !          1378:   p->deja_vu = 0;
        !          1379:   p->lineno = t->lineno;
        !          1380:   p->filename = t->filename;
        !          1381:   p->buf = t->text;
        !          1382:   p->len = t->length;
        !          1383:   p->fndecl = fndecl;
        !          1384: 
        !          1385:   DECL_TEMPLATE_INSTANTIATIONS (tmpl) =
        !          1386:     tree_cons (targs, fndecl, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
        !          1387: 
        !          1388:   function_maybepermanent_obstack = old_fmp_obstack;
        !          1389:   pop_obstacks ();
        !          1390: 
        !          1391:   if (fndecl == error_mark_node)
        !          1392:     {
        !          1393:       /* do nothing */
        !          1394:     }
        !          1395:   else if (TREE_INLINE (fndecl))
        !          1396:     {
        !          1397:       DECL_PENDING_INLINE_INFO (fndecl) = p;
        !          1398:       p->next = pending_inlines;
        !          1399:       pending_inlines = p;
        !          1400:     }
        !          1401:   else
        !          1402:     {
        !          1403:       p->next = pending_template_expansions;
        !          1404:       pending_template_expansions = p;
        !          1405:     }
        !          1406:   return fndecl;
        !          1407: }
        !          1408: 
        !          1409: void
        !          1410: undo_template_name_overload (id, classlevel)
        !          1411:      tree id;
        !          1412:      int classlevel;
        !          1413: {
        !          1414:   tree template;
        !          1415: 
        !          1416:   template = IDENTIFIER_TEMPLATE (id);
        !          1417:   if (!template)
        !          1418:     return;
        !          1419: 
        !          1420: #ifdef DEBUG_CP_BINDING_LEVELS
        !          1421:   indent_to (stderr, debug_bindings_indentation);
        !          1422:   fprintf (stderr, "undo_template_name_overload");
        !          1423:   debug_bindings_indentation += 4;
        !          1424: #endif
        !          1425: 
        !          1426:   poplevel (0,0,0);
        !          1427:   if (!classlevel)
        !          1428:     poplevel (0, 0, 0);
        !          1429: #ifdef DEBUG_CP_BINDING_LEVELS
        !          1430:   debug_bindings_indentation -= 4;
        !          1431: #endif
        !          1432: }
        !          1433: 
        !          1434: void
        !          1435: overload_template_name (id, classlevel)
        !          1436:      tree id;
        !          1437:      int classlevel;
        !          1438: {
        !          1439:   tree template, t, decl;
        !          1440:   struct template_info *tinfo;
        !          1441: 
        !          1442:   assert (TREE_CODE (id) == IDENTIFIER_NODE);
        !          1443:   template = IDENTIFIER_TEMPLATE (id);
        !          1444:   if (!template)
        !          1445:     return;
        !          1446: 
        !          1447: #ifdef DEBUG_CP_BINDING_LEVELS
        !          1448:   indent_to (stderr, debug_bindings_indentation);
        !          1449:   fprintf (stderr, "overload_template_name(%d)", classlevel);
        !          1450:   debug_bindings_indentation += 4;
        !          1451: #endif
        !          1452:   template = TREE_PURPOSE (template);
        !          1453:   tinfo = DECL_TEMPLATE_INFO (template);
        !          1454:   template = DECL_NAME (template);
        !          1455:   assert (template != NULL_TREE);
        !          1456: 
        !          1457:   if (!classlevel)
        !          1458:     pushlevel (1);
        !          1459: 
        !          1460:   t = xref_tag (tinfo->aggr, id, NULL_TREE);
        !          1461:   assert (TREE_CODE (t) == RECORD_TYPE
        !          1462:          || TREE_CODE (t) == UNINSTANTIATED_P_TYPE);
        !          1463: 
        !          1464:   decl = build_decl (TYPE_DECL, template, t);
        !          1465: 
        !          1466: #if 0 /* fix this later */
        !          1467:   /* We don't want to call here if the work has already been done.  */
        !          1468:   t = (classlevel
        !          1469:        ? IDENTIFIER_CLASS_VALUE (template)
        !          1470:        : IDENTIFIER_LOCAL_VALUE (template));
        !          1471:   if (t
        !          1472:       && TREE_CODE (t) == TYPE_DECL
        !          1473:       && TREE_TYPE (t) == t)
        !          1474:     abort ();
        !          1475: #endif
        !          1476: 
        !          1477:   if (classlevel)
        !          1478:     pushdecl_class_level (decl);
        !          1479:   else
        !          1480:     {
        !          1481:       pushdecl (decl);
        !          1482:       /* @@ Is this necessary now?  */
        !          1483:       IDENTIFIER_LOCAL_VALUE (template) = decl;
        !          1484:     }
        !          1485:   pushlevel(1);
        !          1486: 
        !          1487: #ifdef DEBUG_CP_BINDING_LEVELS
        !          1488:   debug_bindings_indentation -= 4;
        !          1489: #endif
        !          1490: }
        !          1491: 
        !          1492: /* T1 is PRE_PARSED_CLASS_DECL; T3 is result of XREF_TAG lookup.  */
        !          1493: void
        !          1494: end_template_instantiation (t1, t3)
        !          1495:      tree t1, t3;
        !          1496: {
        !          1497:   extern struct pending_input *to_be_restored;
        !          1498:   tree t, decl;
        !          1499: 
        !          1500: #ifdef DEBUG_CP_BINDING_LEVELS
        !          1501:   indent_to (stderr, debug_bindings_indentation);
        !          1502:   fprintf (stderr, "end_template_instantiation");
        !          1503:   debug_bindings_indentation += 4;
        !          1504: #endif
        !          1505: 
        !          1506:   processing_template_defn--;
        !          1507: 
        !          1508:   /* Restore the old parser input state.  */
        !          1509:   if (yychar == -2 /* YYEMPTY */)
        !          1510:     yychar = yylex ();
        !          1511:   if (yychar != END_OF_SAVED_INPUT)
        !          1512:     error ("parse error at end of class template");
        !          1513:   else
        !          1514:     {
        !          1515:       restore_pending_input (to_be_restored);
        !          1516:       to_be_restored = 0;
        !          1517:     }
        !          1518: 
        !          1519:   /* Our declarations didn't get stored in the global slot, since
        !          1520:      there was a (supposedly tags-transparent) scope in between.  */
        !          1521:   t = IDENTIFIER_TYPE_VALUE (TREE_VALUE (t1));
        !          1522:   assert (t != NULL_TREE && TREE_CODE_CLASS (TREE_CODE (t)) == 't');
        !          1523:   CLASSTYPE_USE_TEMPLATE (t) = 2;
        !          1524:   decl = IDENTIFIER_GLOBAL_VALUE (TREE_VALUE (t1));
        !          1525:   assert (TREE_CODE (decl) == TYPE_DECL);
        !          1526: 
        !          1527:   undo_template_name_overload (TREE_VALUE (t1), 0);
        !          1528:   t = IDENTIFIER_TEMPLATE (TREE_VALUE (t1));
        !          1529:   pop_template_decls (DECL_TEMPLATE_PARMS (TREE_PURPOSE (t)), TREE_VALUE (t),
        !          1530:                      0);
        !          1531:   pop_from_top_level ();
        !          1532: 
        !          1533:   /* This will fix up the type-value field.  */
        !          1534:   pushdecl_top_level (decl);
        !          1535: 
        !          1536:   /* Restore interface/implementation settings.         */
        !          1537:   extract_interface_info ();
        !          1538: 
        !          1539: #ifdef DEBUG_CP_BINDING_LEVELS
        !          1540:   debug_bindings_indentation -= 4;
        !          1541: #endif
        !          1542: }
        !          1543: 
        !          1544: /* Store away the text of an inline template function. No rtl is
        !          1545:    generated for this function until it is actually needed.  */
        !          1546: 
        !          1547: void
        !          1548: reinit_parse_for_template (yychar, d1, d2)
        !          1549:      int yychar;
        !          1550:      tree d1, d2;
        !          1551: {
        !          1552:   struct template_info *template_info;
        !          1553: 
        !          1554:   if (d2 == NULL_TREE || d2 == error_mark_node)
        !          1555:     {
        !          1556:     lose:
        !          1557:       /* @@ Should use temp obstack, and discard results.  */
        !          1558:       reinit_parse_for_block (yychar, &permanent_obstack, 1);
        !          1559:       return;
        !          1560:     }
        !          1561: 
        !          1562:   if (TREE_CODE (d2) == IDENTIFIER_NODE)
        !          1563:     d2 = IDENTIFIER_GLOBAL_VALUE (d2);
        !          1564:   if (!d2)
        !          1565:     goto lose;
        !          1566:   template_info = DECL_TEMPLATE_INFO (d2);
        !          1567:   if (!template_info)
        !          1568:     {
        !          1569:       template_info = (struct template_info *) permalloc (sizeof (struct template_info));
        !          1570:       bzero (template_info, sizeof (struct template_info));
        !          1571:       DECL_TEMPLATE_INFO (d2) = template_info;
        !          1572:     }
        !          1573:   template_info->filename = input_filename;
        !          1574:   template_info->lineno = lineno;
        !          1575:   reinit_parse_for_block (yychar, &permanent_obstack, 1);
        !          1576:   template_info->text = obstack_base (&permanent_obstack);
        !          1577:   template_info->length = obstack_object_size (&permanent_obstack);
        !          1578:   obstack_finish (&permanent_obstack);
        !          1579:   template_info->parm_vec = d1;
        !          1580: }
        !          1581: 
        !          1582: /* Type unification.
        !          1583: 
        !          1584:    We have a function template signature with one or more references to
        !          1585:    template parameters, and a parameter list we wish to fit to this
        !          1586:    template.  If possible, produce a list of parameters for the template
        !          1587:    which will cause it to fit the supplied parameter list.
        !          1588: 
        !          1589:    Return zero for success, 2 for an incomplete match that doesn't resolve
        !          1590:    all the types, and 1 for complete failure.  An error message will be
        !          1591:    printed only for an incomplete match.
        !          1592: 
        !          1593:    TPARMS[NTPARMS] is an array of template parameter types;
        !          1594:    TARGS[NTPARMS] is the array of template parameter values.  PARMS is
        !          1595:    the function template's signature (using TEMPLATE_PARM_IDX nodes),
        !          1596:    and ARGS is the argument list we're trying to match against it.  */
        !          1597: 
        !          1598: int
        !          1599: type_unification (tparms, targs, parms, args, nsubsts)
        !          1600:      tree tparms, *targs, parms, args;
        !          1601:      int *nsubsts;
        !          1602: {
        !          1603:   tree parm, arg;
        !          1604:   int i;
        !          1605:   int ntparms = TREE_VEC_LENGTH (tparms);
        !          1606: 
        !          1607:   assert (TREE_CODE (tparms) == TREE_VEC);
        !          1608:   assert (TREE_CODE (parms) == TREE_LIST);
        !          1609:   assert (TREE_CODE (args) == TREE_LIST);
        !          1610:   assert (ntparms > 0);
        !          1611: 
        !          1612:   bzero (targs, sizeof (tree) * ntparms);
        !          1613: 
        !          1614:   while (parms
        !          1615:         && parms != void_list_node
        !          1616:         && args)
        !          1617:     {
        !          1618:       parm = TREE_VALUE (parms);
        !          1619:       parms = TREE_CHAIN (parms);
        !          1620:       arg = TREE_VALUE (args);
        !          1621:       args = TREE_CHAIN (args);
        !          1622: 
        !          1623:       if (arg == error_mark_node)
        !          1624:        return 1;
        !          1625: #if 0
        !          1626:       if (TREE_CODE (arg) == VAR_DECL)
        !          1627:        arg = TREE_TYPE (arg);
        !          1628:       else if (TREE_CODE_CLASS (TREE_CODE (arg)) == 'e')
        !          1629:        arg = TREE_TYPE (arg);
        !          1630: #else
        !          1631:       assert (TREE_TYPE (arg) != NULL_TREE);
        !          1632:       arg = TREE_TYPE (arg);
        !          1633: #endif
        !          1634: 
        !          1635:       switch (unify (tparms, targs, ntparms, parm, arg, nsubsts))
        !          1636:        {
        !          1637:        case 0:
        !          1638:          break;
        !          1639:        case 1:
        !          1640:          return 1;
        !          1641:        }
        !          1642:     }
        !          1643:   /* Fail if we've reached the end of the parm list, and more args
        !          1644:      are present, and the parm list isn't variadic.  */
        !          1645:   if (args && parms == void_list_node)
        !          1646:     return 1;
        !          1647:   /* Fail if parms are left and they don't have default values.         */
        !          1648:   if (parms
        !          1649:       && parms != void_list_node
        !          1650:       && TREE_PURPOSE (parms) == NULL_TREE)
        !          1651:     return 1;
        !          1652:   for (i = 0; i < ntparms; i++)
        !          1653:     if (!targs[i])
        !          1654:       {
        !          1655:        error ("incomplete type unification");
        !          1656:        return 2;
        !          1657:       }
        !          1658:   return 0;
        !          1659: }
        !          1660: 
        !          1661: /* Tail recursion is your friend.  */
        !          1662: static int
        !          1663: unify (tparms, targs, ntparms, parm, arg, nsubsts)
        !          1664:      tree tparms, *targs, parm, arg;
        !          1665:      int *nsubsts;
        !          1666: {
        !          1667:   int idx;
        !          1668: 
        !          1669:   /* I don't think this will do the right thing with respect to types.
        !          1670:      But the only case I've seen it in so far has been array bounds, where
        !          1671:      signedness is the only information lost, and I think that will be
        !          1672:      okay.  */
        !          1673:   while (TREE_CODE (parm) == NOP_EXPR)
        !          1674:     parm = TREE_OPERAND (parm, 0);
        !          1675: 
        !          1676:   if (arg == error_mark_node)
        !          1677:     return 1;
        !          1678:   if (arg == parm)
        !          1679:     return 0;
        !          1680: 
        !          1681:   switch (TREE_CODE (parm))
        !          1682:     {
        !          1683:     case TEMPLATE_TYPE_PARM:
        !          1684:       (*nsubsts)++;
        !          1685:       if (TEMPLATE_TYPE_TPARMLIST (parm) != tparms)
        !          1686:        {
        !          1687:          error ("mixed template headers?!");
        !          1688:          abort ();
        !          1689:          return 1;
        !          1690:        }
        !          1691:       idx = TEMPLATE_TYPE_IDX (parm);
        !          1692:       /* Simple cases: Value already set, does match or doesn't.  */
        !          1693:       if (targs[idx] == arg)
        !          1694:        return 0;
        !          1695:       else if (targs[idx])
        !          1696:        return 1;
        !          1697:       /* Check for mixed types and values.  */
        !          1698:       if (TREE_CODE (TREE_VEC_ELT (tparms, idx)) != IDENTIFIER_NODE)
        !          1699:        return 1;
        !          1700:       targs[idx] = arg;
        !          1701:       return 0;
        !          1702:     case TEMPLATE_CONST_PARM:
        !          1703:       (*nsubsts)++;
        !          1704:       idx = TEMPLATE_CONST_IDX (parm);
        !          1705:       if (targs[idx] == arg)
        !          1706:        return 0;
        !          1707:       else if (targs[idx])
        !          1708:        {
        !          1709:          abort();
        !          1710:          return 1;
        !          1711:        }
        !          1712: /*     else if (typeof arg != tparms[idx])
        !          1713:        return 1;*/
        !          1714: 
        !          1715:       targs[idx] = copy_to_permanent (arg);
        !          1716:       return 0;
        !          1717: 
        !          1718:     case POINTER_TYPE:
        !          1719:       if (TREE_CODE (arg) != POINTER_TYPE)
        !          1720:        return 1;
        !          1721:       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
        !          1722:                    nsubsts);
        !          1723: 
        !          1724:     case REFERENCE_TYPE:
        !          1725:       return unify (tparms, targs, ntparms, TREE_TYPE (parm), arg, nsubsts);
        !          1726: 
        !          1727:     case ARRAY_TYPE:
        !          1728:       if (TREE_CODE (arg) != ARRAY_TYPE)
        !          1729:        return 1;
        !          1730:       if (unify (tparms, targs, ntparms, TYPE_DOMAIN (parm), TYPE_DOMAIN (arg),
        !          1731:                 nsubsts) != 0)
        !          1732:        return 1;
        !          1733:       return unify (tparms, targs, ntparms, TREE_TYPE (parm), TREE_TYPE (arg),
        !          1734:                    nsubsts);
        !          1735: 
        !          1736:     case REAL_TYPE:
        !          1737:     case INTEGER_TYPE:
        !          1738:       if (TREE_CODE (parm) == INTEGER_TYPE && TREE_CODE (arg) == INTEGER_TYPE)
        !          1739:        {
        !          1740:          if (TYPE_MIN_VALUE (parm) && TYPE_MIN_VALUE (arg)
        !          1741:              && unify (tparms, targs, ntparms,
        !          1742:                        TYPE_MIN_VALUE (parm), TYPE_MIN_VALUE (arg), nsubsts))
        !          1743:            return 1;
        !          1744:          if (TYPE_MAX_VALUE (parm) && TYPE_MAX_VALUE (arg)
        !          1745:              && unify (tparms, targs, ntparms,
        !          1746:                        TYPE_MAX_VALUE (parm), TYPE_MAX_VALUE (arg), nsubsts))
        !          1747:            return 1;
        !          1748:        }
        !          1749:       /* As far as unification is concerned, this wins.         Later checks
        !          1750:         will invalidate it if necessary.  */
        !          1751:       return 0;
        !          1752: 
        !          1753:       /* Types INTEGER_CST and MINUS_EXPR can come from array bounds.  */
        !          1754:     case INTEGER_CST:
        !          1755:       if (TREE_CODE (arg) != INTEGER_CST)
        !          1756:        return 1;
        !          1757:       return !tree_int_cst_equal (parm, arg);
        !          1758: 
        !          1759:     case MINUS_EXPR:
        !          1760:       {
        !          1761:        tree t1, t2;
        !          1762:        t1 = TREE_OPERAND (parm, 0);
        !          1763:        t2 = TREE_OPERAND (parm, 1);
        !          1764:        if (TREE_CODE (t1) != TEMPLATE_CONST_PARM)
        !          1765:          return 1;
        !          1766:        return unify (tparms, targs, ntparms, t1,
        !          1767:                      fold (build (PLUS_EXPR, integer_type_node, arg, t2)),
        !          1768:                      nsubsts);
        !          1769:       }
        !          1770: 
        !          1771:     case TREE_VEC:
        !          1772:       {
        !          1773:        int i;
        !          1774:        if (TREE_CODE (arg) != TREE_VEC)
        !          1775:          return 1;
        !          1776:        if (TREE_VEC_LENGTH (parm) != TREE_VEC_LENGTH (arg))
        !          1777:          return 1;
        !          1778:        for (i = TREE_VEC_LENGTH (parm) - 1; i >= 0; i--)
        !          1779:          if (unify (tparms, targs, ntparms,
        !          1780:                     TREE_VEC_ELT (parm, i), TREE_VEC_ELT (arg, i),
        !          1781:                     nsubsts))
        !          1782:            return 1;
        !          1783:        return 0;
        !          1784:       }
        !          1785: 
        !          1786:     case UNINSTANTIATED_P_TYPE:
        !          1787:       {
        !          1788:        tree a = IDENTIFIER_TEMPLATE (DECL_NAME (TYPE_NAME (arg)));
        !          1789:        if (UPT_TEMPLATE (parm) != TREE_PURPOSE (a))
        !          1790:          /* different templates */
        !          1791:          return 1;
        !          1792:        return unify (tparms, targs, ntparms, UPT_PARMS (parm), TREE_VALUE (a),
        !          1793:                      nsubsts);
        !          1794:       }
        !          1795: 
        !          1796:     default:
        !          1797:       sorry ("use of `%s' in template type unification",
        !          1798:             tree_code_name [(int) TREE_CODE (parm)]);
        !          1799:       return 1;
        !          1800:     }
        !          1801: }
        !          1802: 
        !          1803: 
        !          1804: #undef DEBUG
        !          1805: 
        !          1806: int
        !          1807: do_pending_expansions ()
        !          1808: {
        !          1809:   struct pending_inline *i, *new_list = 0;
        !          1810: 
        !          1811:   if (!pending_template_expansions)
        !          1812:     return 0;
        !          1813: 
        !          1814: #ifdef DEBUG
        !          1815:   fprintf (stderr, "\n\n\t\t IN DO_PENDING_EXPANSIONS\n\n");
        !          1816: #endif
        !          1817: 
        !          1818:   i = pending_template_expansions;
        !          1819:   while (i)
        !          1820:     {
        !          1821:       tree context;
        !          1822: 
        !          1823:       struct pending_inline *next = i->next;
        !          1824:       tree t = i->fndecl;
        !          1825: 
        !          1826:       int decision = 0;
        !          1827: #define DECIDE(N) if(1){decision=(N); goto decided;}else
        !          1828: 
        !          1829:       assert (TREE_CODE (t) == FUNCTION_DECL || TREE_CODE (t) == VAR_DECL);
        !          1830:       if (TREE_ASM_WRITTEN (t))
        !          1831:        DECIDE (0);
        !          1832:       /* If it's a method, let the class type decide it.
        !          1833:         @@ What if the method template is in a separate file?
        !          1834:         Maybe both file contexts should be taken into account?  */
        !          1835:       context = DECL_CONTEXT (t);
        !          1836:       if (context)
        !          1837:        {
        !          1838:          /* If `unknown', we might want a static copy.
        !          1839:             If `implementation', we want a global one.
        !          1840:             If `interface', ext ref.  */
        !          1841:          if (!CLASSTYPE_INTERFACE_UNKNOWN (context))
        !          1842:            DECIDE (!CLASSTYPE_INTERFACE_ONLY (context));
        !          1843: #if 0 /* This doesn't get us stuff needed only by the file initializer.  */
        !          1844:          DECIDE (TREE_USED (t));
        !          1845: #else /* This compiles too much stuff, but that's probably better in
        !          1846:         most cases than never compiling the stuff we need.  */
        !          1847:          DECIDE (1);
        !          1848: #endif
        !          1849:        }
        !          1850:       /* else maybe call extract_interface_info? */
        !          1851:       if (TREE_USED (t)) /* is this right? */
        !          1852:        DECIDE (1);
        !          1853: 
        !          1854:     decided:
        !          1855: #ifdef DEBUG
        !          1856:       print_node_brief (stderr, decision ? "yes: " : "no: ", t, 0);
        !          1857:       fprintf (stderr, "\t%s\n",
        !          1858:               (DECL_ASSEMBLER_NAME (t)
        !          1859:                ? IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (t))
        !          1860:                : ""));
        !          1861: #endif
        !          1862:       if (decision == 1)
        !          1863:        {
        !          1864:          i->next = pending_inlines;
        !          1865:          pending_inlines = i;
        !          1866:        }
        !          1867:       else
        !          1868:        {
        !          1869:          i->next = new_list;
        !          1870:          new_list = i;
        !          1871:        }
        !          1872:       i = next;
        !          1873:     }
        !          1874:   pending_template_expansions = new_list;
        !          1875:   if (!pending_inlines)
        !          1876:     return 0;
        !          1877:   do_pending_inlines ();
        !          1878:   return 1;
        !          1879: }
        !          1880: 
        !          1881: struct pending_template {
        !          1882:   struct pending_template *next;
        !          1883:   tree id;
        !          1884: };
        !          1885: 
        !          1886: 
        !          1887: struct pending_template* pending_templates;
        !          1888: 
        !          1889: void
        !          1890: do_pending_templates ()
        !          1891: {
        !          1892:   struct pending_template* t;
        !          1893:   
        !          1894:   for ( t = pending_templates; t; t = t->next)
        !          1895:     {
        !          1896:       instantiate_class_template (t->id, 1);
        !          1897:     }
        !          1898: 
        !          1899:   for ( t = pending_templates; t; t = pending_templates)
        !          1900:     {
        !          1901:       pending_templates = t->next;
        !          1902:       free(t);
        !          1903:     }
        !          1904: }
        !          1905: 
        !          1906: int
        !          1907: add_pending_template (pt)
        !          1908:      tree pt;
        !          1909: {
        !          1910:   struct pending_template *p;
        !          1911:   
        !          1912:   p = (struct pending_template *) malloc (sizeof (struct pending_template));
        !          1913:   p->next = pending_templates;
        !          1914:   pending_templates = p;
        !          1915:   p->id = pt;
        !          1916: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.