dmd2/template.c

   1
   2 // Compiler implementation of the D programming language
   3 // Copyright (c) 1999-2008 by Digital Mars
   4 // All Rights Reserved
   5 // written by Walter Bright
   6 // http://www.digitalmars.com
   7 // License for redistribution is by either the Artistic License
   8 // in artistic.txt, or the GNU General Public License in gnu.txt.
   9 // See the included readme.txt for details.
  10
  11 /* NOTE: This file has been patched from the original DMD distribution to
  12    work with the GDC compiler.
  13
  14    Modified by David Friedman, December 2006
  15 */
  16
  17 // Handle template implementation
  18
  19 #include <stdio.h>
  20 #include <assert.h>
  21
  22 #if _WIN32
  23 #include <windows.h>
  24 long __cdecl __ehfilter(LPEXCEPTION_POINTERS ep);
  25 #endif
  26
  27 #include "root.h"
  28 #include "mem.h"
  29 #include "stringtable.h"
  30
  31 #include "mtype.h"
  32 #include "template.h"
  33 #include "init.h"
  34 #include "expression.h"
  35 #include "scope.h"
  36 #include "module.h"
  37 #include "aggregate.h"
  38 #include "declaration.h"
  39 #include "dsymbol.h"
  40 #include "mars.h"
  41 #include "dsymbol.h"
  42 #include "identifier.h"
  43 #include "hdrgen.h"
  44
  45 #define LOG     0
  46
  47 /********************************************
  48  * These functions substitute for dynamic_cast. dynamic_cast does not work
  49  * on earlier versions of gcc.
  50  */
  51
  52 Expression *isExpression(Object *o)
  53 {
  54     //return dynamic_cast<Expression *>(o);
  55     if (!o || o->dyncast() != DYNCAST_EXPRESSION)
  56         return NULL;
  57     return (Expression *)o;
  58 }
  59
  60 Dsymbol *isDsymbol(Object *o)
  61 {
  62     //return dynamic_cast<Dsymbol *>(o);
  63     if (!o || o->dyncast() != DYNCAST_DSYMBOL)
  64         return NULL;
  65     return (Dsymbol *)o;
  66 }
  67
  68 Type *isType(Object *o)
  69 {
  70     //return dynamic_cast<Type *>(o);
  71     if (!o || o->dyncast() != DYNCAST_TYPE)
  72         return NULL;
  73     return (Type *)o;
  74 }
  75
  76 Tuple *isTuple(Object *o)
  77 {
  78     //return dynamic_cast<Tuple *>(o);
  79     if (!o || o->dyncast() != DYNCAST_TUPLE)
  80         return NULL;
  81     return (Tuple *)o;
  82 }
  83
  84
  85 /***********************
  86  * Try to get arg as a type.
  87  */
  88
  89 Type *getType(Object *o)
  90 {
  91     Type *t = isType(o);
  92     if (!t)
  93     {   Expression *e = isExpression(o);
  94         if (e)
  95             t = e->type;
  96     }
  97     return t;
  98 }
  99
 100 Dsymbol *getDsymbol(Object *oarg)
 101 {
 102     Dsymbol *sa;
 103     Expression *ea = isExpression(oarg);
 104     if (ea)
 105     {   // Try to convert Expression to symbol
 106         if (ea->op == TOKvar)
 107             sa = ((VarExp *)ea)->var;
 108         else if (ea->op == TOKfunction)
 109             sa = ((FuncExp *)ea)->fd;
 110         else
 111             sa = NULL;
 112     }
 113     else
 114     {   // Try to convert Type to symbol
 115         Type *ta = isType(oarg);
 116         if (ta)
 117             sa = ta->toDsymbol(NULL);
 118         else
 119             sa = isDsymbol(oarg);       // if already a symbol
 120     }
 121     return sa;
 122 }
 123
 124 /******************************
 125  * If o1 matches o2, return 1.
 126  * Else, return 0.
 127  */
 128
 129 int match(Object *o1, Object *o2, TemplateDeclaration *tempdecl, Scope *sc)
 130 {
 131     Type *t1 = isType(o1);
 132     Type *t2 = isType(o2);
 133     Expression *e1 = isExpression(o1);
 134     Expression *e2 = isExpression(o2);
 135     Dsymbol *s1 = isDsymbol(o1);
 136     Dsymbol *s2 = isDsymbol(o2);
 137     Tuple *v1 = isTuple(o1);
 138     Tuple *v2 = isTuple(o2);
 139
 140     //printf("\t match t1 %p t2 %p, e1 %p e2 %p, s1 %p s2 %p, v1 %p v2 %p\n", t1,t2,e1,e2,s1,s2,v1,v2);
 141
 142     /* A proper implementation of the various equals() overrides
 143      * should make it possible to just do o1->equals(o2), but
 144      * we'll do that another day.
 145      */
 146
 147     if (t1)
 148     {
 149         /* if t1 is an instance of ti, then give error
 150          * about recursive expansions.
 151          */
 152         Dsymbol *s = t1->toDsymbol(sc);
 153         if (s && s->parent)
 154         {   TemplateInstance *ti1 = s->parent->isTemplateInstance();
 155             if (ti1 && ti1->tempdecl == tempdecl)
 156             {
 157                 for (Scope *sc1 = sc; sc1; sc1 = sc1->enclosing)
 158                 {
 159                     if (sc1->scopesym == ti1)
 160                     {
 161                         error("recursive template expansion for template argument %s", t1->toChars());
 162                         return 1;       // fake a match
 163                     }
 164                 }
 165             }
 166         }
 167
 168         if (!t2 || !t1->equals(t2))
 169             goto Lnomatch;
 170     }
 171     else if (e1)
 172     {
 173 #if 0
 174         if (e1 && e2)
 175         {
 176             printf("match %d\n", e1->equals(e2));
 177             e1->print();
 178             e2->print();
 179             e1->type->print();
 180             e2->type->print();
 181         }
 182 #endif
 183         if (!e2)
 184             goto Lnomatch;
 185         if (!e1->equals(e2))
 186             goto Lnomatch;
 187     }
 188     else if (s1)
 189     {
 190         //printf("%p %s, %p %s\n", s1, s1->toChars(), s2, s2->toChars());
 191         if (!s2 || !s1->equals(s2) || s1->parent != s2->parent)
 192         {
 193             goto Lnomatch;
 194         }
 195     }
 196     else if (v1)
 197     {
 198         if (!v2)
 199             goto Lnomatch;
 200         if (v1->objects.dim != v2->objects.dim)
 201             goto Lnomatch;
 202         for (size_t i = 0; i < v1->objects.dim; i++)
 203         {
 204             if (!match((Object *)v1->objects.data[i],
 205                        (Object *)v2->objects.data[i],
 206                        tempdecl, sc))
 207                 goto Lnomatch;
 208         }
 209     }
 210     return 1;   // match
 211 Lnomatch:
 212     return 0;   // nomatch;
 213 }
 214
 215 /****************************************
 216  */
 217
 218 void ObjectToCBuffer(OutBuffer *buf, HdrGenState *hgs, Object *oarg)
 219 {
 220     //printf("ObjectToCBuffer()\n");
 221     Type *t = isType(oarg);
 222     Expression *e = isExpression(oarg);
 223     Dsymbol *s = isDsymbol(oarg);
 224     Tuple *v = isTuple(oarg);
 225     if (t)
 226     {   //printf("\tt: %s ty = %d\n", t->toChars(), t->ty);
 227         t->toCBuffer(buf, NULL, hgs);
 228     }
 229     else if (e)
 230         e->toCBuffer(buf, hgs);
 231     else if (s)
 232     {
 233         char *p = s->ident ? s->ident->toChars() : s->toChars();
 234         buf->writestring(p);
 235     }
 236     else if (v)
 237     {
 238         Objects *args = &v->objects;
 239         for (size_t i = 0; i < args->dim; i++)
 240         {
 241             if (i)
 242                 buf->writeByte(',');
 243             Object *o = (Object *)args->data[i];
 244             ObjectToCBuffer(buf, hgs, o);
 245         }
 246     }
 247     else if (!oarg)
 248     {
 249         buf->writestring("NULL");
 250     }
 251     else
 252     {
 253 #ifdef DEBUG
 254         printf("bad Object = %p\n", oarg);
 255 #endif
 256         assert(0);
 257     }
 258 }
 259
 260
 261
 262 /* ======================== TemplateDeclaration ============================= */
 263
 264 TemplateDeclaration::TemplateDeclaration(Loc loc, Identifier *id, TemplateParameters *parameters, Array *decldefs)
 265     : ScopeDsymbol(id)
 266 {
 267 #if LOG
 268     printf("TemplateDeclaration(this = %p, id = '%s')\n", this, id->toChars());
 269 #endif
 270 #if 0
 271     if (parameters)
 272         for (int i = 0; i < parameters->dim; i++)
 273         {   TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 274             //printf("\tparameter[%d] = %p\n", i, tp);
 275             TemplateTypeParameter *ttp = tp->isTemplateTypeParameter();
 276
 277             if (ttp)
 278             {
 279                 printf("\tparameter[%d] = %s : %s\n", i, tp->ident->toChars(), ttp->specType ? ttp->specType->toChars() : "");
 280             }
 281         }
 282 #endif
 283     this->loc = loc;
 284     this->parameters = parameters;
 285     this->origParameters = parameters;
 286     this->members = decldefs;
 287     this->overnext = NULL;
 288     this->overroot = NULL;
 289     this->scope = NULL;
 290     this->onemember = NULL;
 291 }
 292
 293 Dsymbol *TemplateDeclaration::syntaxCopy(Dsymbol *)
 294 {
 295     //printf("TemplateDeclaration::syntaxCopy()\n");
 296     TemplateDeclaration *td;
 297     TemplateParameters *p;
 298     Array *d;
 299
 300     p = NULL;
 301     if (parameters)
 302     {
 303         p = new TemplateParameters();
 304         p->setDim(parameters->dim);
 305         for (int i = 0; i < p->dim; i++)
 306         {   TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 307             p->data[i] = (void *)tp->syntaxCopy();
 308         }
 309     }
 310     d = Dsymbol::arraySyntaxCopy(members);
 311     td = new TemplateDeclaration(loc, ident, p, d);
 312     return td;
 313 }
 314
 315 void TemplateDeclaration::semantic(Scope *sc)
 316 {
 317 #if LOG
 318     printf("TemplateDeclaration::semantic(this = %p, id = '%s')\n", this, ident->toChars());
 319 #endif
 320     if (scope)
 321         return;         // semantic() already run
 322
 323     if (sc->func)
 324     {
 325 //      error("cannot declare template at function scope %s", sc->func->toChars());
 326     }
 327
 328     if (/*global.params.useArrayBounds &&*/ sc->module)
 329     {
 330         // Generate this function as it may be used
 331         // when template is instantiated in other modules
 332         sc->module->toModuleArray();
 333     }
 334
 335     if (/*global.params.useAssert &&*/ sc->module)
 336     {
 337         // Generate this function as it may be used
 338         // when template is instantiated in other modules
 339         sc->module->toModuleAssert();
 340     }
 341
 342     /* Remember Scope for later instantiations, but make
 343      * a copy since attributes can change.
 344      */
 345     this->scope = new Scope(*sc);
 346     this->scope->setNoFree();
 347
 348     // Set up scope for parameters
 349     ScopeDsymbol *paramsym = new ScopeDsymbol();
 350     paramsym->parent = sc->parent;
 351     Scope *paramscope = sc->push(paramsym);
 352     paramscope->parameterSpecialization = 1;
 353
 354     if (global.params.doDocComments)
 355     {
 356         origParameters = new TemplateParameters();
 357         origParameters->setDim(parameters->dim);
 358         for (int i = 0; i < parameters->dim; i++)
 359         {
 360             TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 361             origParameters->data[i] = (void *)tp->syntaxCopy();
 362         }
 363     }
 364
 365     for (int i = 0; i < parameters->dim; i++)
 366     {
 367         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 368
 369         tp->declareParameter(paramscope);
 370     }
 371
 372     for (int i = 0; i < parameters->dim; i++)
 373     {
 374         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 375
 376         tp->semantic(paramscope);
 377         if (i + 1 != parameters->dim && tp->isTemplateTupleParameter())
 378             error("template tuple parameter must be last one");
 379     }
 380
 381     paramscope->pop();
 382
 383     if (members)
 384     {
 385         Dsymbol *s;
 386         if (Dsymbol::oneMembers(members, &s))
 387         {
 388             if (s && s->ident && s->ident->equals(ident))
 389             {
 390                 onemember = s;
 391                 s->parent = this;
 392             }
 393         }
 394     }
 395
 396     /* BUG: should check:
 397      *  o no virtual functions or non-static data members of classes
 398      */
 399 }
 400
 401 char *TemplateDeclaration::kind()
 402 {
 403     return (onemember && onemember->isAggregateDeclaration())
 404                 ? onemember->kind()
 405                 : (char *)"template";
 406 }
 407
 408 /**********************************
 409  * Overload existing TemplateDeclaration 'this' with the new one 's'.
 410  * Return !=0 if successful; i.e. no conflict.
 411  */
 412
 413 int TemplateDeclaration::overloadInsert(Dsymbol *s)
 414 {
 415     TemplateDeclaration **pf;
 416     TemplateDeclaration *f;
 417
 418 #if LOG
 419     printf("TemplateDeclaration::overloadInsert('%s')\n", s->toChars());
 420 #endif
 421     f = s->isTemplateDeclaration();
 422     if (!f)
 423         return FALSE;
 424     TemplateDeclaration *pthis = this;
 425     for (pf = &pthis; *pf; pf = &(*pf)->overnext)
 426     {
 427 #if 0
 428         // Conflict if TemplateParameter's match
 429         // Will get caught anyway later with TemplateInstance, but
 430         // should check it now.
 431         TemplateDeclaration *f2 = *pf;
 432
 433         if (f->parameters->dim != f2->parameters->dim)
 434             goto Lcontinue;
 435
 436         for (int i = 0; i < f->parameters->dim; i++)
 437         {   TemplateParameter *p1 = (TemplateParameter *)f->parameters->data[i];
 438             TemplateParameter *p2 = (TemplateParameter *)f2->parameters->data[i];
 439
 440             if (!p1->overloadMatch(p2))
 441                 goto Lcontinue;
 442         }
 443
 444 #if LOG
 445         printf("\tfalse: conflict\n");
 446 #endif
 447         return FALSE;
 448
 449      Lcontinue:
 450         ;
 451 #endif
 452     }
 453
 454     f->overroot = this;
 455     *pf = f;
 456 #if LOG
 457     printf("\ttrue: no conflict\n");
 458 #endif
 459     return TRUE;
 460 }
 461
 462 /***************************************
 463  * Given that ti is an instance of this TemplateDeclaration,
 464  * deduce the types of the parameters to this, and store
 465  * those deduced types in dedtypes[].
 466  * Input:
 467  *      flag    1: don't do semantic() because of dummy types
 468  *              2: don't change types in matchArg()
 469  * Output:
 470  *      dedtypes        deduced arguments
 471  * Return match level.
 472  */
 473
 474 MATCH TemplateDeclaration::matchWithInstance(TemplateInstance *ti,
 475         Objects *dedtypes, int flag)
 476 {   MATCH m;
 477     int dedtypes_dim = dedtypes->dim;
 478
 479 #define LOGM 0
 480 #if LOGM
 481     printf("\n+TemplateDeclaration::matchWithInstance(this = %s, ti = %s, flag = %d)\n", toChars(), ti->toChars(), flag);
 482 #endif
 483
 484 #if 0
 485     printf("dedtypes->dim = %d, parameters->dim = %d\n", dedtypes_dim, parameters->dim);
 486     if (ti->tiargs->dim)
 487         printf("ti->tiargs->dim = %d, [0] = %p\n",
 488             ti->tiargs->dim,
 489             ti->tiargs->data[0]);
 490 #endif
 491     dedtypes->zero();
 492
 493     int parameters_dim = parameters->dim;
 494     int variadic = isVariadic() != NULL;
 495
 496     // If more arguments than parameters, no match
 497     if (ti->tiargs->dim > parameters_dim && !variadic)
 498     {
 499 #if LOGM
 500         printf(" no match: more arguments than parameters\n");
 501 #endif
 502         return MATCHnomatch;
 503     }
 504
 505     assert(dedtypes_dim == parameters_dim);
 506     assert(dedtypes_dim >= ti->tiargs->dim || variadic);
 507
 508     // Set up scope for parameters
 509     assert((size_t)scope > 0x10000);
 510     ScopeDsymbol *paramsym = new ScopeDsymbol();
 511     paramsym->parent = scope->parent;
 512     Scope *paramscope = scope->push(paramsym);
 513
 514     // Attempt type deduction
 515     m = MATCHexact;
 516     for (int i = 0; i < dedtypes_dim; i++)
 517     {   MATCH m2;
 518         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 519         Declaration *sparam;
 520
 521         //printf("\targument [%d]\n", i);
 522 #if LOGM
 523         //printf("\targument [%d] is %s\n", i, oarg ? oarg->toChars() : "null");
 524         TemplateTypeParameter *ttp = tp->isTemplateTypeParameter();
 525         if (ttp)
 526             printf("\tparameter[%d] is %s : %s\n", i, tp->ident->toChars(), ttp->specType ? ttp->specType->toChars() : "");
 527 #endif
 528
 529 #if V1
 530         m2 = tp->matchArg(paramscope, ti->tiargs, i, parameters, dedtypes, &sparam);
 531 #else
 532         m2 = tp->matchArg(paramscope, ti->tiargs, i, parameters, dedtypes, &sparam, (flag & 2) ? 1 : 0);
 533
 534 #endif
 535         //printf("\tm2 = %d\n", m2);
 536
 537         if (m2 == MATCHnomatch)
 538         {
 539 #if 0
 540             printf("\tmatchArg() for parameter %i failed\n", i);
 541 #endif
 542             goto Lnomatch;
 543         }
 544
 545         if (m2 < m)
 546             m = m2;
 547
 548         if (!flag)
 549             sparam->semantic(paramscope);
 550         if (!paramscope->insert(sparam))
 551             goto Lnomatch;
 552     }
 553
 554     if (!flag)
 555     {
 556         // Any parameter left without a type gets the type of its corresponding arg
 557         for (int i = 0; i < dedtypes_dim; i++)
 558         {
 559             if (!dedtypes->data[i])
 560             {   assert(i < ti->tiargs->dim);
 561                 dedtypes->data[i] = ti->tiargs->data[i];
 562             }
 563         }
 564     }
 565
 566 #if LOGM
 567     // Print out the results
 568     printf("--------------------------\n");
 569     printf("template %s\n", toChars());
 570     printf("instance %s\n", ti->toChars());
 571     if (m)
 572     {
 573         for (int i = 0; i < dedtypes_dim; i++)
 574         {
 575             TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 576             Object *oarg;
 577
 578             printf(" [%d]", i);
 579
 580             if (i < ti->tiargs->dim)
 581                 oarg = (Object *)ti->tiargs->data[i];
 582             else
 583                 oarg = NULL;
 584             tp->print(oarg, (Object *)dedtypes->data[i]);
 585         }
 586     }
 587     else
 588         goto Lnomatch;
 589 #endif
 590
 591 #if LOGM
 592     printf(" match = %d\n", m);
 593 #endif
 594     goto Lret;
 595
 596 Lnomatch:
 597 #if LOGM
 598     printf(" no match\n");
 599 #endif
 600     m = MATCHnomatch;
 601
 602 Lret:
 603     paramscope->pop();
 604 #if LOGM
 605     printf("-TemplateDeclaration::matchWithInstance(this = %p, ti = %p) = %d\n", this, ti, m);
 606 #endif
 607     return m;
 608 }
 609
 610 /********************************************
 611  * Determine partial specialization order of 'this' vs td2.
 612  * Returns:
 613  *      match   this is at least as specialized as td2
 614  *      0       td2 is more specialized than this
 615  */
 616
 617 MATCH TemplateDeclaration::leastAsSpecialized(TemplateDeclaration *td2)
 618 {
 619     /* This works by taking the template parameters to this template
 620      * declaration and feeding them to td2 as if it were a template
 621      * instance.
 622      * If it works, then this template is at least as specialized
 623      * as td2.
 624      */
 625
 626     TemplateInstance ti(0, ident);      // create dummy template instance
 627     Objects dedtypes;
 628
 629 #define LOG_LEASTAS     0
 630
 631 #if LOG_LEASTAS
 632     printf("%s.leastAsSpecialized(%s)\n", toChars(), td2->toChars());
 633 #endif
 634
 635     // Set type arguments to dummy template instance to be types
 636     // generated from the parameters to this template declaration
 637     ti.tiargs = new Objects();
 638     ti.tiargs->setDim(parameters->dim);
 639     for (int i = 0; i < ti.tiargs->dim; i++)
 640     {
 641         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 642
 643         void *p = tp->dummyArg();
 644         if (p)
 645             ti.tiargs->data[i] = p;
 646         else
 647             ti.tiargs->setDim(i);
 648     }
 649
 650     // Temporary Array to hold deduced types
 651     //dedtypes.setDim(parameters->dim);
 652     dedtypes.setDim(td2->parameters->dim);
 653
 654     // Attempt a type deduction
 655     MATCH m = td2->matchWithInstance(&ti, &dedtypes, 1);
 656     if (m)
 657     {
 658         /* A non-variadic template is more specialized than a
 659          * variadic one.
 660          */
 661         if (isVariadic() && !td2->isVariadic())
 662             goto L1;
 663
 664 #if LOG_LEASTAS
 665         printf("  matches %d, so is least as specialized\n", m);
 666 #endif
 667         return m;
 668     }
 669   L1:
 670 #if LOG_LEASTAS
 671     printf("  doesn't match, so is not as specialized\n");
 672 #endif
 673     return MATCHnomatch;
 674 }
 675
 676
 677 /*************************************************
 678  * Match function arguments against a specific template function.
 679  * Input:
 680  *      loc             instantiation location
 681  *      targsi          Expression/Type initial list of template arguments
 682  *      ethis           'this' argument if !NULL
 683  *      fargs           arguments to function
 684  * Output:
 685  *      dedargs         Expression/Type deduced template arguments
 686  * Returns:
 687  *      match level
 688  */
 689
 690 MATCH TemplateDeclaration::deduceFunctionTemplateMatch(Loc loc, Objects *targsi,
 691         Expression *ethis, Expressions *fargs,
 692         Objects *dedargs)
 693 {
 694     size_t i;
 695     size_t nfparams;
 696     size_t nfargs;
 697     size_t nargsi;              // array size of targsi
 698     int fptupindex = -1;
 699     int tuple_dim = 0;
 700     MATCH match = MATCHexact;
 701     FuncDeclaration *fd = onemember->toAlias()->isFuncDeclaration();
 702     TypeFunction *fdtype;               // type of fd
 703     TemplateTupleParameter *tp;
 704     Objects dedtypes;   // for T:T*, the dedargs is the T*, dedtypes is the T
 705
 706 #if 0
 707     printf("\nTemplateDeclaration::deduceFunctionTemplateMatch() %s\n", toChars());
 708     for (i = 0; i < fargs->dim; i++)
 709     {   Expression *e = (Expression *)fargs->data[i];
 710         printf("\tfarg[%d] is %s, type is %s\n", i, e->toChars(), e->type->toChars());
 711     }
 712 #endif
 713
 714     assert((size_t)scope > 0x10000);
 715
 716     dedargs->setDim(parameters->dim);
 717     dedargs->zero();
 718
 719     dedtypes.setDim(parameters->dim);
 720     dedtypes.zero();
 721
 722     // Set up scope for parameters
 723     ScopeDsymbol *paramsym = new ScopeDsymbol();
 724     paramsym->parent = scope->parent;
 725     Scope *paramscope = scope->push(paramsym);
 726
 727     tp = isVariadic();
 728
 729     nargsi = 0;
 730     if (targsi)
 731     {   // Set initial template arguments
 732
 733         nargsi = targsi->dim;
 734         if (nargsi > parameters->dim)
 735         {   if (!tp)
 736                 goto Lnomatch;
 737             dedargs->setDim(nargsi);
 738             dedargs->zero();
 739         }
 740
 741         memcpy(dedargs->data, targsi->data, nargsi * sizeof(*dedargs->data));
 742
 743         for (i = 0; i < nargsi; i++)
 744         {   TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 745             MATCH m;
 746             Declaration *sparam;
 747
 748             m = tp->matchArg(paramscope, dedargs, i, parameters, &dedtypes, &sparam);
 749             //printf("\tdeduceType m = %d\n", m);
 750             if (m == MATCHnomatch)
 751                 goto Lnomatch;
 752             if (m < match)
 753                 match = m;
 754
 755             sparam->semantic(paramscope);
 756             if (!paramscope->insert(sparam))
 757                 goto Lnomatch;
 758         }
 759     }
 760
 761     assert(fd->type->ty == Tfunction);
 762     fdtype = (TypeFunction *)fd->type;
 763
 764     nfparams = Argument::dim(fdtype->parameters); // number of function parameters
 765     nfargs = fargs->dim;                // number of function arguments
 766
 767     /* Check for match of function arguments with variadic template
 768      * parameter, such as:
 769      *
 770      * template Foo(T, A...) { void Foo(T t, A a); }
 771      * void main() { Foo(1,2,3); }
 772      */
 773     if (tp)                             // if variadic
 774     {
 775         if (nfparams == 0)              // if no function parameters
 776         {
 777             Tuple *t = new Tuple();
 778             //printf("t = %p\n", t);
 779             dedargs->data[parameters->dim - 1] = (void *)t;
 780             goto L2;
 781         }
 782         else if (nfargs < nfparams - 1)
 783             goto L1;
 784         else
 785         {
 786             /* Figure out which of the function parameters matches
 787              * the tuple template parameter. Do this by matching
 788              * type identifiers.
 789              * Set the index of this function parameter to fptupindex.
 790              */
 791             for (fptupindex = 0; fptupindex < nfparams; fptupindex++)
 792             {
 793                 Argument *fparam = (Argument *)fdtype->parameters->data[fptupindex];
 794                 if (fparam->type->ty != Tident)
 795                     continue;
 796                 TypeIdentifier *tid = (TypeIdentifier *)fparam->type;
 797                 if (!tp->ident->equals(tid->ident) || tid->idents.dim)
 798                     continue;
 799
 800                 if (fdtype->varargs)    // variadic function doesn't
 801                     goto Lnomatch;      // go with variadic template
 802
 803                 /* The types of the function arguments
 804                  * now form the tuple argument.
 805                  */
 806                 Tuple *t = new Tuple();
 807                 dedargs->data[parameters->dim - 1] = (void *)t;
 808
 809                 tuple_dim = nfargs - (nfparams - 1);
 810                 t->objects.setDim(tuple_dim);
 811                 for (i = 0; i < tuple_dim; i++)
 812                 {   Expression *farg = (Expression *)fargs->data[fptupindex + i];
 813                     t->objects.data[i] = (void *)farg->type;
 814                 }
 815                 goto L2;
 816             }
 817             fptupindex = -1;
 818         }
 819     }
 820
 821 L1:
 822     if (nfparams == nfargs)
 823         ;
 824     else if (nfargs > nfparams)
 825     {
 826         if (fdtype->varargs == 0)
 827             goto Lnomatch;              // too many args, no match
 828         match = MATCHconvert;           // match ... with a conversion
 829     }
 830
 831 L2:
 832     // Match 'ethis' to any TemplateThisParameter's
 833     if (ethis)
 834     {
 835         for (size_t i = 0; i < parameters->dim; i++)
 836         {   TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 837             TemplateThisParameter *ttp = tp->isTemplateThisParameter();
 838             if (ttp)
 839             {   MATCH m;
 840
 841                 Type *t = new TypeIdentifier(0, ttp->ident);
 842                 m = ethis->type->deduceType(scope, t, parameters, &dedtypes);
 843                 if (!m)
 844                     goto Lnomatch;
 845                 if (m < match)
 846                     match = m;          // pick worst match
 847             }
 848         }
 849     }
 850
 851     // Loop through the function parameters
 852     for (i = 0; i < nfparams; i++)
 853     {
 854         /* Skip over function parameters which wound up
 855          * as part of a template tuple parameter.
 856          */
 857         if (i == fptupindex)
 858         {   if (fptupindex == nfparams - 1)
 859                 break;
 860             i += tuple_dim - 1;
 861             continue;
 862         }
 863
 864         Argument *fparam = Argument::getNth(fdtype->parameters, i);
 865
 866         if (i >= nfargs)                // if not enough arguments
 867         {
 868             if (fparam->defaultArg)
 869             {   /* Default arguments do not participate in template argument
 870                  * deduction.
 871                  */
 872                 goto Lmatch;
 873             }
 874         }
 875         else
 876         {   Expression *farg = (Expression *)fargs->data[i];
 877 #if 0
 878             printf("\tfarg->type   = %s\n", farg->type->toChars());
 879             printf("\tfparam->type = %s\n", fparam->type->toChars());
 880 #endif
 881             MATCH m;
 882             //m = farg->type->toHeadMutable()->deduceType(scope, fparam->type, parameters, &dedtypes);
 883             m = farg->type->deduceType(scope, fparam->type, parameters, &dedtypes);
 884             //printf("\tdeduceType m = %d\n", m);
 885
 886             /* If no match, see if there's a conversion to a delegate
 887              */
 888             if (!m && fparam->type->toBasetype()->ty == Tdelegate)
 889             {
 890                 TypeDelegate *td = (TypeDelegate *)fparam->type->toBasetype();
 891                 TypeFunction *tf = (TypeFunction *)td->next;
 892
 893                 if (!tf->varargs && Argument::dim(tf->parameters) == 0)
 894                 {
 895                     m = farg->type->deduceType(scope, tf->next, parameters, &dedtypes);
 896                     if (!m && tf->next->toBasetype()->ty == Tvoid)
 897                         m = MATCHconvert;
 898                 }
 899                 //printf("\tm2 = %d\n", m);
 900             }
 901
 902             if (m)
 903             {   if (m < match)
 904                     match = m;          // pick worst match
 905                 continue;
 906             }
 907         }
 908         if (!(fdtype->varargs == 2 && i + 1 == nfparams))
 909             goto Lnomatch;
 910
 911         /* Check for match with function parameter T...
 912          */
 913         Type *t = fparam->type;
 914         switch (t->ty)
 915         {
 916             // Perhaps we can do better with this, see TypeFunction::callMatch()
 917             case Tsarray:
 918             case Tarray:
 919             case Tclass:
 920             case Tident:
 921                 goto Lmatch;
 922
 923             default:
 924                 goto Lnomatch;
 925         }
 926     }
 927
 928 Lmatch:
 929
 930     /* Fill in any missing arguments with their defaults.
 931      */
 932     for (i = nargsi; i < dedargs->dim; i++)
 933     {
 934         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
 935         //printf("tp[%d] = %s\n", i, tp->ident->toChars());
 936         /* For T:T*, the dedargs is the T*, dedtypes is the T
 937          * But for function templates, we really need them to match
 938          */
 939         Object *oarg = (Object *)dedargs->data[i];
 940         Object *oded = (Object *)dedtypes.data[i];
 941         //printf("1dedargs[%d] = %p, dedtypes[%d] = %p\n", i, oarg, i, oded);
 942         if (!oarg)
 943         {
 944             if (oded)
 945             {
 946                 if (tp->specialization())
 947                 {   /* The specialization can work as long as afterwards
 948                      * the oded == oarg
 949                      */
 950                     Declaration *sparam;
 951                     dedargs->data[i] = (void *)oded;
 952                     MATCH m2 = tp->matchArg(paramscope, dedargs, i, parameters, &dedtypes, &sparam, 0);
 953                     //printf("m2 = %d\n", m2);
 954                     if (!m2)
 955                         goto Lnomatch;
 956                     if (m2 < match)
 957                         match = m2;             // pick worst match
 958                     if (dedtypes.data[i] != oded)
 959                         error("specialization not allowed for deduced parameter %s", tp->ident->toChars());
 960                 }
 961             }
 962             else
 963             {   oded = tp->defaultArg(loc, paramscope);
 964                 if (!oded)
 965                     goto Lnomatch;
 966             }
 967             declareParameter(paramscope, tp, oded);
 968             dedargs->data[i] = (void *)oded;
 969         }
 970     }
 971
 972 #if 0
 973     for (i = 0; i < dedargs->dim; i++)
 974     {   Type *t = (Type *)dedargs->data[i];
 975         printf("\tdedargs[%d] = %d, %s\n", i, t->dyncast(), t->toChars());
 976     }
 977 #endif
 978
 979     paramscope->pop();
 980     //printf("\tmatch %d\n", match);
 981     return match;
 982
 983 Lnomatch:
 984     paramscope->pop();
 985     //printf("\tnomatch\n");
 986     return MATCHnomatch;
 987 }
 988
 989 /**************************************************
 990  * Declare template parameter tp with value o.
 991  */
 992
 993 void TemplateDeclaration::declareParameter(Scope *sc, TemplateParameter *tp, Object *o)
 994 {
 995     //printf("TemplateDeclaration::declareParameter('%s', o = %p)\n", tp->ident->toChars(), o);
 996
 997     Type *targ = isType(o);
 998     Expression *ea = isExpression(o);
 999     Dsymbol *sa = isDsymbol(o);
1000     Tuple *va = isTuple(o);
1001
1002     Dsymbol *s;
1003
1004     if (targ)
1005     {
1006         //printf("type %s\n", targ->toChars());
1007         s = new AliasDeclaration(0, tp->ident, targ);
1008     }
1009     else if (sa)
1010     {
1011         //printf("Alias %s %s;\n", sa->ident->toChars(), tp->ident->toChars());
1012         s = new AliasDeclaration(0, tp->ident, sa);
1013     }
1014     else if (ea)
1015     {
1016         // tdtypes.data[i] always matches ea here
1017         Initializer *init = new ExpInitializer(loc, ea);
1018         TemplateValueParameter *tvp = tp->isTemplateValueParameter();
1019         assert(tvp);
1020
1021         VarDeclaration *v = new VarDeclaration(loc, tvp->valType, tp->ident, init);
1022         v->storage_class = STCmanifest;
1023         s = v;
1024     }
1025     else if (va)
1026     {
1027         //printf("\ttuple\n");
1028         s = new TupleDeclaration(loc, tp->ident, &va->objects);
1029     }
1030     else
1031     {
1032 #ifdef DEBUG
1033         o->print();
1034 #endif
1035         assert(0);
1036     }
1037     if (!sc->insert(s))
1038         error("declaration %s is already defined", tp->ident->toChars());
1039     s->semantic(sc);
1040 }
1041
1042 /**************************************
1043  * Determine if TemplateDeclaration is variadic.
1044  */
1045
1046 TemplateTupleParameter *isVariadic(TemplateParameters *parameters)
1047 {   size_t dim = parameters->dim;
1048     TemplateTupleParameter *tp = NULL;
1049
1050     if (dim)
1051         tp = ((TemplateParameter *)parameters->data[dim - 1])->isTemplateTupleParameter();
1052     return tp;
1053 }
1054
1055 TemplateTupleParameter *TemplateDeclaration::isVariadic()
1056 {
1057     return ::isVariadic(parameters);
1058 }
1059
1060 /***********************************
1061  * We can overload templates.
1062  */
1063
1064 int TemplateDeclaration::isOverloadable()
1065 {
1066     return 1;
1067 }
1068
1069 /*************************************************
1070  * Given function arguments, figure out which template function
1071  * to expand, and return that function.
1072  * If no match, give error message and return NULL.
1073  * Input:
1074  *      sc              instantiation scope
1075  *      loc             instantiation location
1076  *      targsi          initial list of template arguments
1077  *      ethis           if !NULL, the 'this' pointer argument
1078  *      fargs           arguments to function
1079  *      flags           1: do not issue error message on no match, just return NULL
1080  */
1081
1082 FuncDeclaration *TemplateDeclaration::deduceFunctionTemplate(Scope *sc, Loc loc,
1083         Objects *targsi, Expression *ethis, Expressions *fargs, int flags)
1084 {
1085     MATCH m_best = MATCHnomatch;
1086     TemplateDeclaration *td_ambig = NULL;
1087     TemplateDeclaration *td_best = NULL;
1088     Objects *tdargs = new Objects();
1089     TemplateInstance *ti;
1090     FuncDeclaration *fd;
1091
1092 #if 0
1093     printf("TemplateDeclaration::deduceFunctionTemplate() %s\n", toChars());
1094     printf("    targsi:\n");
1095     if (targsi)
1096     {   for (int i = 0; i < targsi->dim; i++)
1097         {   Object *arg = (Object *)targsi->data[i];
1098             printf("\t%s\n", arg->toChars());
1099         }
1100     }
1101     printf("    fargs:\n");
1102     for (int i = 0; i < fargs->dim; i++)
1103     {   Expression *arg = (Expression *)fargs->data[i];
1104         printf("\t%s %s\n", arg->type->toChars(), arg->toChars());
1105         //printf("\tty = %d\n", arg->type->ty);
1106     }
1107 #endif
1108
1109     for (TemplateDeclaration *td = this; td; td = td->overnext)
1110     {
1111         if (!td->scope)
1112         {
1113             error("forward reference to template %s", td->toChars());
1114             goto Lerror;
1115         }
1116         if (!td->onemember || !td->onemember->toAlias()->isFuncDeclaration())
1117         {
1118             error("is not a function template");
1119             goto Lerror;
1120         }
1121
1122         MATCH m;
1123         Objects dedargs;
1124
1125         m = td->deduceFunctionTemplateMatch(loc, targsi, ethis, fargs, &dedargs);
1126         //printf("deduceFunctionTemplateMatch = %d\n", m);
1127         if (!m)                 // if no match
1128             continue;
1129
1130         if (m < m_best)
1131             goto Ltd_best;
1132         if (m > m_best)
1133             goto Ltd;
1134
1135         {
1136         // Disambiguate by picking the most specialized TemplateDeclaration
1137         MATCH c1 = td->leastAsSpecialized(td_best);
1138         MATCH c2 = td_best->leastAsSpecialized(td);
1139         //printf("c1 = %d, c2 = %d\n", c1, c2);
1140
1141         if (c1 > c2)
1142             goto Ltd;
1143         else if (c1 < c2)
1144             goto Ltd_best;
1145         else
1146             goto Lambig;
1147         }
1148
1149       Lambig:           // td_best and td are ambiguous
1150         td_ambig = td;
1151         continue;
1152
1153       Ltd_best:         // td_best is the best match so far
1154         td_ambig = NULL;
1155         continue;
1156
1157       Ltd:              // td is the new best match
1158         td_ambig = NULL;
1159         assert((size_t)td->scope > 0x10000);
1160         td_best = td;
1161         m_best = m;
1162         tdargs->setDim(dedargs.dim);
1163         memcpy(tdargs->data, dedargs.data, tdargs->dim * sizeof(void *));
1164         continue;
1165     }
1166     if (!td_best)
1167     {
1168         if (!(flags & 1))
1169             error(loc, "does not match any function template declaration");
1170         goto Lerror;
1171     }
1172     if (td_ambig)
1173     {
1174         error(loc, "%s matches more than one function template declaration, %s and %s",
1175                 toChars(), td_best->toChars(), td_ambig->toChars());
1176     }
1177
1178     /* The best match is td_best with arguments tdargs.
1179      * Now instantiate the template.
1180      */
1181     assert((size_t)td_best->scope > 0x10000);
1182     ti = new TemplateInstance(loc, td_best, tdargs);
1183     ti->semantic(sc);
1184     fd = ti->toAlias()->isFuncDeclaration();
1185     if (!fd)
1186         goto Lerror;
1187     return fd;
1188
1189   Lerror:
1190     if (!(flags & 1))
1191     {
1192         HdrGenState hgs;
1193
1194         OutBuffer bufa;
1195         Objects *args = targsi;
1196         if (args)
1197         {   for (int i = 0; i < args->dim; i++)
1198             {
1199                 if (i)
1200                     bufa.writeByte(',');
1201                 Object *oarg = (Object *)args->data[i];
1202                 ObjectToCBuffer(&bufa, &hgs, oarg);
1203             }
1204         }
1205
1206         OutBuffer buf;
1207         argExpTypesToCBuffer(&buf, fargs, &hgs);
1208
1209         error(loc, "cannot deduce template function from argument types !(%s)(%s)",
1210                 bufa.toChars(), buf.toChars());
1211     }
1212     return NULL;
1213 }
1214
1215 void TemplateDeclaration::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
1216 {
1217 #if 0 // Should handle template functions
1218     if (onemember && onemember->isFuncDeclaration())
1219         buf->writestring("foo ");
1220 #endif
1221     buf->writestring(kind());
1222     buf->writeByte(' ');
1223     buf->writestring(ident->toChars());
1224     buf->writeByte('(');
1225     for (int i = 0; i < parameters->dim; i++)
1226     {
1227         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1228         if (hgs->ddoc)
1229             tp = (TemplateParameter *)origParameters->data[i];
1230         if (i)
1231             buf->writeByte(',');
1232         tp->toCBuffer(buf, hgs);
1233     }
1234     buf->writeByte(')');
1235
1236     if (hgs->hdrgen)
1237     {
1238         hgs->tpltMember++;
1239         buf->writenl();
1240         buf->writebyte('{');
1241         buf->writenl();
1242         for (int i = 0; i < members->dim; i++)
1243         {
1244             Dsymbol *s = (Dsymbol *)members->data[i];
1245             s->toCBuffer(buf, hgs);
1246         }
1247         buf->writebyte('}');
1248         buf->writenl();
1249         hgs->tpltMember--;
1250     }
1251 }
1252
1253
1254 char *TemplateDeclaration::toChars()
1255 {   OutBuffer buf;
1256     HdrGenState hgs;
1257
1258     memset(&hgs, 0, sizeof(hgs));
1259     buf.writestring(ident->toChars());
1260     buf.writeByte('(');
1261     for (int i = 0; i < parameters->dim; i++)
1262     {
1263         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1264         if (i)
1265             buf.writeByte(',');
1266         tp->toCBuffer(&buf, &hgs);
1267     }
1268     buf.writeByte(')');
1269     buf.writeByte(0);
1270     return (char *)buf.extractData();
1271 }
1272
1273 /* ======================== Type ============================================ */
1274
1275 /****
1276  * Given an identifier, figure out which TemplateParameter it is.
1277  * Return -1 if not found.
1278  */
1279
1280 int templateIdentifierLookup(Identifier *id, TemplateParameters *parameters)
1281 {
1282     for (size_t i = 0; i < parameters->dim; i++)
1283     {   TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1284
1285         if (tp->ident->equals(id))
1286             return i;
1287     }
1288     return -1;
1289 }
1290
1291 int templateParameterLookup(Type *tparam, TemplateParameters *parameters)
1292 {
1293     assert(tparam->ty == Tident);
1294     TypeIdentifier *tident = (TypeIdentifier *)tparam;
1295     //printf("\ttident = '%s'\n", tident->toChars());
1296     if (tident->idents.dim == 0)
1297     {
1298         return templateIdentifierLookup(tident->ident, parameters);
1299     }
1300     return -1;
1301 }
1302
1303 /* These form the heart of template argument deduction.
1304  * Given 'this' being the type argument to the template instance,
1305  * it is matched against the template declaration parameter specialization
1306  * 'tparam' to determine the type to be used for the parameter.
1307  * Example:
1308  *      template Foo(T:T*)      // template declaration
1309  *      Foo!(int*)              // template instantiation
1310  * Input:
1311  *      this = int*
1312  *      tparam = T
1313  *      parameters = [ T:T* ]   // Array of TemplateParameter's
1314  * Output:
1315  *      dedtypes = [ int ]      // Array of Expression/Type's
1316  */
1317
1318 MATCH Type::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters,
1319         Objects *dedtypes)
1320 {
1321     //printf("Type::deduceType()\n");
1322     //printf("\tthis   = %d, ", ty); print();
1323     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1324     if (!tparam)
1325         goto Lnomatch;
1326
1327     if (this == tparam)
1328         goto Lexact;
1329
1330     if (tparam->ty == Tident)
1331     {
1332         // Determine which parameter tparam is
1333         int i = templateParameterLookup(tparam, parameters);
1334         if (i == -1)
1335         {
1336             if (!sc)
1337                 goto Lnomatch;
1338             /* BUG: what if tparam is a template instance, that
1339              * has as an argument another Tident?
1340              */
1341             tparam = tparam->semantic(0, sc);
1342             assert(tparam->ty != Tident);
1343             return deduceType(sc, tparam, parameters, dedtypes);
1344         }
1345
1346         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1347
1348         // Found the corresponding parameter tp
1349         if (!tp->isTemplateTypeParameter())
1350             goto Lnomatch;
1351         Type *at = (Type *)dedtypes->data[i];
1352         if (!at)
1353         {   // 3*3 == 9 cases
1354             if (tparam->isMutable())
1355             {   // foo(U:U) T            => T
1356                 // foo(U:U) const(T)     => const(T)
1357                 // foo(U:U) invariant(T) => invariant(T)
1358                 dedtypes->data[i] = (void *)this;
1359                 goto Lexact;
1360             }
1361             else if (mod == tparam->mod)
1362             {   // foo(U:const(U))     const(T)     => T
1363                 // foo(U:invariant(U)) invariant(T) => T
1364                 dedtypes->data[i] = (void *)mutableOf();
1365                 goto Lexact;
1366             }
1367             else if (tparam->isConst())
1368             {   // foo(U:const(U)) T            => T
1369                 // foo(U:const(U)) invariant(T) => T
1370                 dedtypes->data[i] = (void *)mutableOf();
1371                 goto Lconst;
1372             }
1373             else
1374             {   // foo(U:invariant(U)) T        => nomatch
1375                 // foo(U:invariant(U)) const(T) => nomatch
1376                 goto Lnomatch;
1377             }
1378         }
1379         if (equals(at))
1380             goto Lexact;
1381         else if (ty == Tclass && at->ty == Tclass)
1382         {
1383             return implicitConvTo(at);
1384         }
1385         else if (ty == Tsarray && at->ty == Tarray &&
1386             nextOf()->implicitConvTo(at->nextOf()) >= MATCHconst)
1387         {
1388             goto Lexact;
1389         }
1390         else
1391             goto Lnomatch;
1392     }
1393
1394     if (ty != tparam->ty)
1395         goto Lnomatch;
1396
1397     if (nextOf())
1398         return nextOf()->deduceType(sc, tparam->nextOf(), parameters, dedtypes);
1399
1400 Lexact:
1401     return MATCHexact;
1402
1403 Lnomatch:
1404     return MATCHnomatch;
1405
1406 Lconst:
1407     return MATCHconst;
1408 }
1409
1410 MATCH TypeSArray::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters,
1411         Objects *dedtypes)
1412 {
1413 #if 0
1414     printf("TypeSArray::deduceType()\n");
1415     printf("\tthis   = %d, ", ty); print();
1416     printf("\ttparam = %d, ", tparam->ty); tparam->print();
1417 #endif
1418
1419     // Extra check that array dimensions must match
1420     if (tparam)
1421     {
1422         if (tparam->ty == Tsarray)
1423         {
1424             TypeSArray *tp = (TypeSArray *)tparam;
1425
1426             if (tp->dim->op == TOKvar &&
1427                 ((VarExp *)tp->dim)->var->storage_class & STCtemplateparameter)
1428             {   int i = templateIdentifierLookup(((VarExp *)tp->dim)->var->ident, parameters);
1429                 // This code matches code in TypeInstance::deduceType()
1430                 if (i == -1)
1431                     goto Lnomatch;
1432                 TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1433                 TemplateValueParameter *tvp = tp->isTemplateValueParameter();
1434                 if (!tvp)
1435                     goto Lnomatch;
1436                 Expression *e = (Expression *)dedtypes->data[i];
1437                 if (e)
1438                 {
1439                     if (!dim->equals(e))
1440                         goto Lnomatch;
1441                 }
1442                 else
1443                 {   Type *vt = tvp->valType->semantic(0, sc);
1444                     MATCH m = (MATCH)dim->implicitConvTo(vt);
1445                     if (!m)
1446                         goto Lnomatch;
1447                     dedtypes->data[i] = dim;
1448                 }
1449             }
1450             else if (dim->toInteger() != tp->dim->toInteger())
1451                 return MATCHnomatch;
1452         }
1453         else if (tparam->ty == Taarray)
1454         {
1455             TypeAArray *tp = (TypeAArray *)tparam;
1456             if (tp->index->ty == Tident)
1457             {   TypeIdentifier *tident = (TypeIdentifier *)tp->index;
1458
1459                 if (tident->idents.dim == 0)
1460                 {   Identifier *id = tident->ident;
1461
1462                     for (size_t i = 0; i < parameters->dim; i++)
1463                     {
1464                         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1465
1466                         if (tp->ident->equals(id))
1467                         {   // Found the corresponding template parameter
1468                             TemplateValueParameter *tvp = tp->isTemplateValueParameter();
1469                             if (!tvp || !tvp->valType->isintegral())
1470                                 goto Lnomatch;
1471
1472                             if (dedtypes->data[i])
1473                             {
1474                                 if (!dim->equals((Object *)dedtypes->data[i]))
1475                                     goto Lnomatch;
1476                             }
1477                             else
1478                             {   dedtypes->data[i] = (void *)dim;
1479                             }
1480                             return next->deduceType(sc, tparam->nextOf(), parameters, dedtypes);
1481                         }
1482                     }
1483                 }
1484             }
1485         }
1486         else if (tparam->ty == Tarray)
1487         {   MATCH m;
1488
1489             m = next->deduceType(sc, tparam->nextOf(), parameters, dedtypes);
1490             if (m == MATCHexact)
1491                 m = MATCHconvert;
1492             return m;
1493         }
1494     }
1495     return Type::deduceType(sc, tparam, parameters, dedtypes);
1496
1497   Lnomatch:
1498     return MATCHnomatch;
1499 }
1500
1501 MATCH TypeAArray::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1502 {
1503 #if 0
1504     printf("TypeAArray::deduceType()\n");
1505     printf("\tthis   = %d, ", ty); print();
1506     printf("\ttparam = %d, ", tparam->ty); tparam->print();
1507 #endif
1508
1509     // Extra check that index type must match
1510     if (tparam && tparam->ty == Taarray)
1511     {
1512         TypeAArray *tp = (TypeAArray *)tparam;
1513         if (!index->deduceType(sc, tp->index, parameters, dedtypes))
1514         {
1515             return MATCHnomatch;
1516         }
1517     }
1518     return Type::deduceType(sc, tparam, parameters, dedtypes);
1519 }
1520
1521 MATCH TypeFunction::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1522 {
1523     //printf("TypeFunction::deduceType()\n");
1524     //printf("\tthis   = %d, ", ty); print();
1525     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1526
1527     // Extra check that function characteristics must match
1528     if (tparam && tparam->ty == Tfunction)
1529     {
1530         TypeFunction *tp = (TypeFunction *)tparam;
1531         if (varargs != tp->varargs ||
1532             linkage != tp->linkage)
1533             return MATCHnomatch;
1534
1535         size_t nfargs = Argument::dim(this->parameters);
1536         size_t nfparams = Argument::dim(tp->parameters);
1537
1538         /* See if tuple match
1539          */
1540         if (nfparams > 0 && nfargs >= nfparams - 1)
1541         {
1542             /* See if 'A' of the template parameter matches 'A'
1543              * of the type of the last function parameter.
1544              */
1545             Argument *fparam = (Argument *)tp->parameters->data[nfparams - 1];
1546             if (fparam->type->ty != Tident)
1547                 goto L1;
1548             TypeIdentifier *tid = (TypeIdentifier *)fparam->type;
1549             if (tid->idents.dim)
1550                 goto L1;
1551
1552             /* Look through parameters to find tuple matching tid->ident
1553              */
1554             size_t tupi = 0;
1555             for (; 1; tupi++)
1556             {   if (tupi == parameters->dim)
1557                     goto L1;
1558                 TemplateParameter *t = (TemplateParameter *)parameters->data[tupi];
1559                 TemplateTupleParameter *tup = t->isTemplateTupleParameter();
1560                 if (tup && tup->ident->equals(tid->ident))
1561                     break;
1562             }
1563
1564             /* The types of the function arguments [nfparams - 1 .. nfargs]
1565              * now form the tuple argument.
1566              */
1567             int tuple_dim = nfargs - (nfparams - 1);
1568
1569             /* See if existing tuple, and whether it matches or not
1570              */
1571             Object *o = (Object *)dedtypes->data[tupi];
1572             if (o)
1573             {   // Existing deduced argument must be a tuple, and must match
1574                 Tuple *t = isTuple(o);
1575                 if (!t || t->objects.dim != tuple_dim)
1576                     return MATCHnomatch;
1577                 for (size_t i = 0; i < tuple_dim; i++)
1578                 {   Argument *arg = Argument::getNth(this->parameters, nfparams - 1 + i);
1579                     if (!arg->type->equals((Object *)t->objects.data[i]))
1580                         return MATCHnomatch;
1581                 }
1582             }
1583             else
1584             {   // Create new tuple
1585                 Tuple *t = new Tuple();
1586                 t->objects.setDim(tuple_dim);
1587                 for (size_t i = 0; i < tuple_dim; i++)
1588                 {   Argument *arg = Argument::getNth(this->parameters, nfparams - 1 + i);
1589                     t->objects.data[i] = (void *)arg->type;
1590                 }
1591                 dedtypes->data[tupi] = (void *)t;
1592             }
1593             nfparams--; // don't consider the last parameter for type deduction
1594             goto L2;
1595         }
1596
1597     L1:
1598         if (nfargs != nfparams)
1599             return MATCHnomatch;
1600     L2:
1601         for (size_t i = 0; i < nfparams; i++)
1602         {
1603             Argument *a = Argument::getNth(this->parameters, i);
1604             Argument *ap = Argument::getNth(tp->parameters, i);
1605             if (a->storageClass != ap->storageClass ||
1606                 !a->type->deduceType(sc, ap->type, parameters, dedtypes))
1607                 return MATCHnomatch;
1608         }
1609     }
1610     return Type::deduceType(sc, tparam, parameters, dedtypes);
1611 }
1612
1613 MATCH TypeIdentifier::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1614 {
1615     // Extra check
1616     if (tparam && tparam->ty == Tident)
1617     {
1618         TypeIdentifier *tp = (TypeIdentifier *)tparam;
1619
1620         for (int i = 0; i < idents.dim; i++)
1621         {
1622             Identifier *id1 = (Identifier *)idents.data[i];
1623             Identifier *id2 = (Identifier *)tp->idents.data[i];
1624
1625             if (!id1->equals(id2))
1626                 return MATCHnomatch;
1627         }
1628     }
1629     return Type::deduceType(sc, tparam, parameters, dedtypes);
1630 }
1631
1632 MATCH TypeInstance::deduceType(Scope *sc,
1633         Type *tparam, TemplateParameters *parameters,
1634         Objects *dedtypes)
1635 {
1636     //printf("TypeInstance::deduceType(tparam = %s) %s\n", tparam->toChars(), toChars());
1637     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1638
1639     // Extra check
1640     if (tparam && tparam->ty == Tinstance)
1641     {
1642         TypeInstance *tp = (TypeInstance *)tparam;
1643
1644         //printf("tempinst->tempdecl = %p\n", tempinst->tempdecl);
1645         //printf("tp->tempinst->tempdecl = %p\n", tp->tempinst->tempdecl);
1646         if (!tp->tempinst->tempdecl)
1647         {   //printf("tp->tempinst->name = '%s'\n", tp->tempinst->name->toChars());
1648             if (!tp->tempinst->name->equals(tempinst->name))
1649             {
1650                 /* Handle case of:
1651                  *  template Foo(T : sa!(T), alias sa)
1652                  */
1653                 int i = templateIdentifierLookup(tp->tempinst->name, parameters);
1654                 if (i == -1)
1655                 {   /* Didn't find it as a parameter identifier. Try looking
1656                      * it up and seeing if is an alias. See Bugzilla 1454
1657                      */
1658                     Dsymbol *s = tempinst->tempdecl->scope->search(0, tp->tempinst->name, NULL);
1659                     if (s)
1660                     {
1661                         s = s->toAlias();
1662                         TemplateDeclaration *td = s->isTemplateDeclaration();
1663                         if (td && td == tempinst->tempdecl)
1664                             goto L2;
1665                     }
1666                     goto Lnomatch;
1667                 }
1668                 TemplateParameter *tpx = (TemplateParameter *)parameters->data[i];
1669                 // This logic duplicates tpx->matchArg()
1670                 TemplateAliasParameter *ta = tpx->isTemplateAliasParameter();
1671                 if (!ta)
1672                     goto Lnomatch;
1673                 Dsymbol *sa = tempinst->tempdecl;
1674                 if (!sa)
1675                     goto Lnomatch;
1676                 if (ta->specAlias && sa != ta->specAlias)
1677                     goto Lnomatch;
1678                 if (dedtypes->data[i])
1679                 {   // Must match already deduced symbol
1680                     Dsymbol *s = (Dsymbol *)dedtypes->data[i];
1681
1682                     if (s != sa)
1683                         goto Lnomatch;
1684                 }
1685                 dedtypes->data[i] = sa;
1686             }
1687         }
1688         else if (tempinst->tempdecl != tp->tempinst->tempdecl)
1689             goto Lnomatch;
1690
1691       L2:
1692         if (tempinst->tiargs->dim != tp->tempinst->tiargs->dim)
1693             goto Lnomatch;
1694
1695         for (int i = 0; i < tempinst->tiargs->dim; i++)
1696         {
1697             //printf("\ttest: tempinst->tiargs[%d]\n", i);
1698             int j;
1699             Object *o1 = (Object *)tempinst->tiargs->data[i];
1700             Object *o2 = (Object *)tp->tempinst->tiargs->data[i];
1701
1702             Type *t1 = isType(o1);
1703             Type *t2 = isType(o2);
1704
1705             Expression *e1 = isExpression(o1);
1706             Expression *e2 = isExpression(o2);
1707
1708 #if 0
1709             if (t1)     printf("t1 = %s\n", t1->toChars());
1710             if (t2)     printf("t2 = %s\n", t2->toChars());
1711             if (e1)     printf("e1 = %s\n", e1->toChars());
1712             if (e2)     printf("e2 = %s\n", e2->toChars());
1713 #endif
1714
1715             if (t1 && t2)
1716             {
1717                 if (!t1->deduceType(sc, t2, parameters, dedtypes))
1718                     goto Lnomatch;
1719             }
1720             else if (e1 && e2)
1721             {
1722                 if (!e1->equals(e2))
1723                 {   if (e2->op == TOKvar)
1724                     {
1725                         /*
1726                          * (T:Number!(e2), int e2)
1727                          */
1728                         j = templateIdentifierLookup(((VarExp *)e2)->var->ident, parameters);
1729                         goto L1;
1730                     }
1731                     goto Lnomatch;
1732                 }
1733             }
1734             else if (e1 && t2 && t2->ty == Tident)
1735             {
1736                 j = templateParameterLookup(t2, parameters);
1737             L1:
1738                 if (j == -1)
1739                     goto Lnomatch;
1740                 TemplateParameter *tp = (TemplateParameter *)parameters->data[j];
1741                 // BUG: use tp->matchArg() instead of the following
1742                 TemplateValueParameter *tv = tp->isTemplateValueParameter();
1743                 if (!tv)
1744                     goto Lnomatch;
1745                 Expression *e = (Expression *)dedtypes->data[j];
1746                 if (e)
1747                 {
1748                     if (!e1->equals(e))
1749                         goto Lnomatch;
1750                 }
1751                 else
1752                 {   Type *vt = tv->valType->semantic(0, sc);
1753                     MATCH m = (MATCH)e1->implicitConvTo(vt);
1754                     if (!m)
1755                         goto Lnomatch;
1756                     dedtypes->data[j] = e1;
1757                 }
1758             }
1759             // BUG: Need to handle alias and tuple parameters
1760             else
1761                 goto Lnomatch;
1762         }
1763     }
1764     return Type::deduceType(sc, tparam, parameters, dedtypes);
1765
1766 Lnomatch:
1767     return MATCHnomatch;
1768 }
1769
1770 MATCH TypeStruct::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1771 {
1772     //printf("TypeStruct::deduceType()\n");
1773     //printf("\tthis->parent   = %s, ", sym->parent->toChars()); print();
1774     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1775
1776     /* If this struct is a template struct, and we're matching
1777      * it against a template instance, convert the struct type
1778      * to a template instance, too, and try again.
1779      */
1780     TemplateInstance *ti = sym->parent->isTemplateInstance();
1781
1782     if (tparam && tparam->ty == Tinstance)
1783     {
1784         if (ti && ti->toAlias() == sym)
1785         {
1786             TypeInstance *t = new TypeInstance(0, ti);
1787             return t->deduceType(sc, tparam, parameters, dedtypes);
1788         }
1789
1790         /* Match things like:
1791          *  S!(T).foo
1792          */
1793         TypeInstance *tpi = (TypeInstance *)tparam;
1794         if (tpi->idents.dim)
1795         {   Identifier *id = (Identifier *)tpi->idents.data[tpi->idents.dim - 1];
1796             if (id->dyncast() == DYNCAST_IDENTIFIER && sym->ident->equals(id))
1797             {
1798                 Type *tparent = sym->parent->getType();
1799                 if (tparent)
1800                 {
1801                     /* Slice off the .foo in S!(T).foo
1802                      */
1803                     tpi->idents.dim--;
1804                     MATCH m = tparent->deduceType(sc, tpi, parameters, dedtypes);
1805                     tpi->idents.dim++;
1806                     return m;
1807                 }
1808             }
1809         }
1810     }
1811
1812     // Extra check
1813     if (tparam && tparam->ty == Tstruct)
1814     {
1815         TypeStruct *tp = (TypeStruct *)tparam;
1816
1817         if (sym != tp->sym)
1818             return MATCHnomatch;
1819     }
1820     return Type::deduceType(sc, tparam, parameters, dedtypes);
1821 }
1822
1823 MATCH TypeEnum::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1824 {
1825     // Extra check
1826     if (tparam && tparam->ty == Tenum)
1827     {
1828         TypeEnum *tp = (TypeEnum *)tparam;
1829
1830         if (sym != tp->sym)
1831             return MATCHnomatch;
1832     }
1833     return Type::deduceType(sc, tparam, parameters, dedtypes);
1834 }
1835
1836 MATCH TypeTypedef::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1837 {
1838     // Extra check
1839     if (tparam && tparam->ty == Ttypedef)
1840     {
1841         TypeTypedef *tp = (TypeTypedef *)tparam;
1842
1843         if (sym != tp->sym)
1844             return MATCHnomatch;
1845     }
1846     return Type::deduceType(sc, tparam, parameters, dedtypes);
1847 }
1848
1849 MATCH TypeClass::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1850 {
1851     //printf("TypeClass::deduceType(this = %s)\n", toChars());
1852
1853     /* If this class is a template class, and we're matching
1854      * it against a template instance, convert the class type
1855      * to a template instance, too, and try again.
1856      */
1857     TemplateInstance *ti = sym->parent->isTemplateInstance();
1858
1859     if (tparam && tparam->ty == Tinstance)
1860     {
1861         if (ti && ti->toAlias() == sym)
1862         {
1863             TypeInstance *t = new TypeInstance(0, ti);
1864             return t->deduceType(sc, tparam, parameters, dedtypes);
1865         }
1866
1867         /* Match things like:
1868          *  S!(T).foo
1869          */
1870         TypeInstance *tpi = (TypeInstance *)tparam;
1871         if (tpi->idents.dim)
1872         {   Identifier *id = (Identifier *)tpi->idents.data[tpi->idents.dim - 1];
1873             if (id->dyncast() == DYNCAST_IDENTIFIER && sym->ident->equals(id))
1874             {
1875                 Type *tparent = sym->parent->getType();
1876                 if (tparent)
1877                 {
1878                     /* Slice off the .foo in S!(T).foo
1879                      */
1880                     tpi->idents.dim--;
1881                     MATCH m = tparent->deduceType(sc, tpi, parameters, dedtypes);
1882                     tpi->idents.dim++;
1883                     return m;
1884                 }
1885             }
1886         }
1887     }
1888
1889     // Extra check
1890     if (tparam && tparam->ty == Tclass)
1891     {
1892         TypeClass *tp = (TypeClass *)tparam;
1893
1894         //printf("\t%d\n", (MATCH) implicitConvTo(tp));
1895         return implicitConvTo(tp);
1896     }
1897     return Type::deduceType(sc, tparam, parameters, dedtypes);
1898 }
1899
1900 /* ======================== TemplateParameter =============================== */
1901
1902 TemplateParameter::TemplateParameter(Loc loc, Identifier *ident)
1903 {
1904     this->loc = loc;
1905     this->ident = ident;
1906     this->sparam = NULL;
1907 }
1908
1909 TemplateTypeParameter  *TemplateParameter::isTemplateTypeParameter()
1910 {
1911     return NULL;
1912 }
1913
1914 TemplateValueParameter *TemplateParameter::isTemplateValueParameter()
1915 {
1916     return NULL;
1917 }
1918
1919 TemplateAliasParameter *TemplateParameter::isTemplateAliasParameter()
1920 {
1921     return NULL;
1922 }
1923
1924 TemplateTupleParameter *TemplateParameter::isTemplateTupleParameter()
1925 {
1926     return NULL;
1927 }
1928
1929 #if V2
1930 TemplateThisParameter  *TemplateParameter::isTemplateThisParameter()
1931 {
1932     return NULL;
1933 }
1934 #endif
1935
1936 /* ======================== TemplateTypeParameter =========================== */
1937
1938 // type-parameter
1939
1940 TemplateTypeParameter::TemplateTypeParameter(Loc loc, Identifier *ident, Type *specType,
1941         Type *defaultType)
1942     : TemplateParameter(loc, ident)
1943 {
1944     this->ident = ident;
1945     this->specType = specType;
1946     this->defaultType = defaultType;
1947 }
1948
1949 TemplateTypeParameter  *TemplateTypeParameter::isTemplateTypeParameter()
1950 {
1951     return this;
1952 }
1953
1954 TemplateParameter *TemplateTypeParameter::syntaxCopy()
1955 {
1956     TemplateTypeParameter *tp = new TemplateTypeParameter(loc, ident, specType, defaultType);
1957     if (tp->specType)
1958         tp->specType = specType->syntaxCopy();
1959     if (defaultType)
1960         tp->defaultType = defaultType->syntaxCopy();
1961     return tp;
1962 }
1963
1964 void TemplateTypeParameter::declareParameter(Scope *sc)
1965 {
1966     //printf("TemplateTypeParameter::declareParameter('%s')\n", ident->toChars());
1967     TypeIdentifier *ti = new TypeIdentifier(loc, ident);
1968     sparam = new AliasDeclaration(loc, ident, ti);
1969     if (!sc->insert(sparam))
1970         error(loc, "parameter '%s' multiply defined", ident->toChars());
1971 }
1972
1973 void TemplateTypeParameter::semantic(Scope *sc)
1974 {
1975     //printf("TemplateTypeParameter::semantic('%s')\n", ident->toChars());
1976     if (specType)
1977     {
1978         specType = specType->semantic(loc, sc);
1979     }
1980 #if 0 // Don't do semantic() until instantiation
1981     if (defaultType)
1982     {
1983         defaultType = defaultType->semantic(loc, sc);
1984     }
1985 #endif
1986 }
1987
1988 /****************************************
1989  * Determine if two TemplateParameters are the same
1990  * as far as TemplateDeclaration overloading goes.
1991  * Returns:
1992  *      1       match
1993  *      0       no match
1994  */
1995
1996 int TemplateTypeParameter::overloadMatch(TemplateParameter *tp)
1997 {
1998     TemplateTypeParameter *ttp = tp->isTemplateTypeParameter();
1999
2000     if (ttp)
2001     {
2002         if (specType != ttp->specType)
2003             goto Lnomatch;
2004
2005         if (specType && !specType->equals(ttp->specType))
2006             goto Lnomatch;
2007
2008         return 1;                       // match
2009     }
2010
2011 Lnomatch:
2012     return 0;
2013 }
2014
2015 /*******************************************
2016  * Match to a particular TemplateParameter.
2017  * Input:
2018  *      i               i'th argument
2019  *      tiargs[]        actual arguments to template instance
2020  *      parameters[]    template parameters
2021  *      dedtypes[]      deduced arguments to template instance
2022  *      *psparam        set to symbol declared and initialized to dedtypes[i]
2023  *      flags           1: don't do 'toHeadMutable()'
2024  */
2025
2026 MATCH TemplateTypeParameter::matchArg(Scope *sc, Objects *tiargs,
2027         int i, TemplateParameters *parameters, Objects *dedtypes,
2028         Declaration **psparam, int flags)
2029 {
2030     //printf("TemplateTypeParameter::matchArg()\n");
2031     Type *t;
2032     Object *oarg;
2033     MATCH m = MATCHexact;
2034     Type *ta;
2035
2036     if (i < tiargs->dim)
2037         oarg = (Object *)tiargs->data[i];
2038     else
2039     {   // Get default argument instead
2040         oarg = defaultArg(loc, sc);
2041         if (!oarg)
2042         {   assert(i < dedtypes->dim);
2043             // It might have already been deduced
2044             oarg = (Object *)dedtypes->data[i];
2045             if (!oarg)
2046             {
2047                 goto Lnomatch;
2048             }
2049             flags |= 1;         // already deduced, so don't to toHeadMutable()
2050         }
2051     }
2052
2053     ta = isType(oarg);
2054     if (!ta)
2055     {
2056         //printf("test1 %s %p %p %p\n", oarg->toChars(), isExpression(oarg), isDsymbol(oarg), isTuple(oarg));
2057         goto Lnomatch;
2058     }
2059     //printf("ta is %s\n", ta->toChars());
2060
2061     t = (Type *)dedtypes->data[i];
2062
2063     if (specType)
2064     {
2065         //printf("\tcalling deduceType(): ta is %s, specType is %s\n", ta->toChars(), specType->toChars());
2066         MATCH m2 = ta->deduceType(sc, specType, parameters, dedtypes);
2067         if (m2 == MATCHnomatch)
2068         {   //printf("\tfailed deduceType\n");
2069             goto Lnomatch;
2070         }
2071
2072         if (m2 < m)
2073             m = m2;
2074         t = (Type *)dedtypes->data[i];
2075     }
2076     else
2077     {
2078         // So that matches with specializations are better
2079         m = MATCHconvert;
2080
2081         /* This is so that:
2082          *   template Foo(T), Foo!(const int), => ta == int
2083          */
2084 //      if (!(flags & 1))
2085 //          ta = ta->toHeadMutable();
2086
2087         if (t)
2088         {   // Must match already deduced type
2089
2090             m = MATCHexact;
2091             if (!t->equals(ta))
2092             {   //printf("t = %s ta = %s\n", t->toChars(), ta->toChars());
2093                 goto Lnomatch;
2094             }
2095         }
2096     }
2097
2098     if (!t)
2099     {
2100         dedtypes->data[i] = ta;
2101         t = ta;
2102     }
2103     *psparam = new AliasDeclaration(loc, ident, t);
2104     //printf("\tm = %d\n", m);
2105     return m;
2106
2107 Lnomatch:
2108     *psparam = NULL;
2109     //printf("\tm = %d\n", MATCHnomatch);
2110     return MATCHnomatch;
2111 }
2112
2113
2114 void TemplateTypeParameter::print(Object *oarg, Object *oded)
2115 {
2116     fprintf(stderr, " %s\n", ident->toChars());
2117
2118     Type *t  = isType(oarg);
2119     Type *ta = isType(oded);
2120
2121     assert(ta);
2122
2123     if (specType)
2124         fprintf(stderr, "\tSpecialization: %s\n", specType->toChars());
2125     if (defaultType)
2126         fprintf(stderr, "\tDefault:        %s\n", defaultType->toChars());
2127     fprintf(stderr, "\tArgument:       %s\n", t ? t->toChars() : "NULL");
2128     fprintf(stderr, "\tDeduced Type:   %s\n", ta->toChars());
2129 }
2130
2131
2132 void TemplateTypeParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2133 {
2134     buf->writestring(ident->toChars());
2135     if (specType)
2136     {
2137         buf->writestring(" : ");
2138         specType->toCBuffer(buf, NULL, hgs);
2139     }
2140     if (defaultType)
2141     {
2142         buf->writestring(" = ");
2143         defaultType->toCBuffer(buf, NULL, hgs);
2144     }
2145 }
2146
2147
2148 void *TemplateTypeParameter::dummyArg()
2149 {   Type *t;
2150
2151     if (specType)
2152         t = specType;
2153     else
2154     {   // Use this for alias-parameter's too (?)
2155         t = new TypeIdentifier(loc, ident);
2156     }
2157     return (void *)t;
2158 }
2159
2160
2161 Object *TemplateTypeParameter::specialization()
2162 {
2163     return specType;
2164 }
2165
2166
2167 Object *TemplateTypeParameter::defaultArg(Loc loc, Scope *sc)
2168 {
2169     Type *t;
2170
2171     t = defaultType;
2172     if (t)
2173     {
2174         t = t->syntaxCopy();
2175         t = t->semantic(loc, sc);
2176     }
2177     return t;
2178 }
2179
2180 /* ======================== TemplateThisParameter =========================== */
2181
2182 #if V2
2183 // this-parameter
2184
2185 TemplateThisParameter::TemplateThisParameter(Loc loc, Identifier *ident,
2186         Type *specType,
2187         Type *defaultType)
2188     : TemplateTypeParameter(loc, ident, specType, defaultType)
2189 {
2190 }
2191
2192 TemplateThisParameter  *TemplateThisParameter::isTemplateThisParameter()
2193 {
2194     return this;
2195 }
2196
2197 TemplateParameter *TemplateThisParameter::syntaxCopy()
2198 {
2199     TemplateThisParameter *tp = new TemplateThisParameter(loc, ident, specType, defaultType);
2200     if (tp->specType)
2201         tp->specType = specType->syntaxCopy();
2202     if (defaultType)
2203         tp->defaultType = defaultType->syntaxCopy();
2204     return tp;
2205 }
2206
2207 void TemplateThisParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2208 {
2209     buf->writestring("this ");
2210     TemplateTypeParameter::toCBuffer(buf, hgs);
2211 }
2212 #endif
2213
2214 /* ======================== TemplateAliasParameter ========================== */
2215
2216 // alias-parameter
2217
2218 Dsymbol *TemplateAliasParameter::sdummy = NULL;
2219
2220 TemplateAliasParameter::TemplateAliasParameter(Loc loc, Identifier *ident, Type *specAliasT, Type *defaultAlias)
2221     : TemplateParameter(loc, ident)
2222 {
2223     this->ident = ident;
2224     this->specAliasT = specAliasT;
2225     this->defaultAlias = defaultAlias;
2226
2227     this->specAlias = NULL;
2228 }
2229
2230 TemplateAliasParameter *TemplateAliasParameter::isTemplateAliasParameter()
2231 {
2232     return this;
2233 }
2234
2235 TemplateParameter *TemplateAliasParameter::syntaxCopy()
2236 {
2237     TemplateAliasParameter *tp = new TemplateAliasParameter(loc, ident, specAliasT, defaultAlias);
2238     if (tp->specAliasT)
2239         tp->specAliasT = specAliasT->syntaxCopy();
2240     if (defaultAlias)
2241         tp->defaultAlias = defaultAlias->syntaxCopy();
2242     return tp;
2243 }
2244
2245 void TemplateAliasParameter::declareParameter(Scope *sc)
2246 {
2247     TypeIdentifier *ti = new TypeIdentifier(loc, ident);
2248     sparam = new AliasDeclaration(loc, ident, ti);
2249     if (!sc->insert(sparam))
2250         error(loc, "parameter '%s' multiply defined", ident->toChars());
2251 }
2252
2253 void TemplateAliasParameter::semantic(Scope *sc)
2254 {
2255     if (specAliasT)
2256     {
2257         specAlias = specAliasT->toDsymbol(sc);
2258         if (!specAlias)
2259             error("%s is not a symbol", specAliasT->toChars());
2260     }
2261 #if 0 // Don't do semantic() until instantiation
2262     if (defaultAlias)
2263         defaultAlias = defaultAlias->semantic(loc, sc);
2264 #endif
2265 }
2266
2267 int TemplateAliasParameter::overloadMatch(TemplateParameter *tp)
2268 {
2269     TemplateAliasParameter *tap = tp->isTemplateAliasParameter();
2270
2271     if (tap)
2272     {
2273         if (specAlias != tap->specAlias)
2274             goto Lnomatch;
2275
2276         return 1;                       // match
2277     }
2278
2279 Lnomatch:
2280     return 0;
2281 }
2282
2283 MATCH TemplateAliasParameter::matchArg(Scope *sc,
2284         Objects *tiargs, int i, TemplateParameters *parameters, Objects *dedtypes,
2285         Declaration **psparam, int flags)
2286 {
2287     Dsymbol *sa;
2288     Object *oarg;
2289     Expression *ea;
2290
2291     //printf("TemplateAliasParameter::matchArg()\n");
2292
2293     if (i < tiargs->dim)
2294         oarg = (Object *)tiargs->data[i];
2295     else
2296     {   // Get default argument instead
2297         oarg = defaultArg(loc, sc);
2298         if (!oarg)
2299         {   assert(i < dedtypes->dim);
2300             // It might have already been deduced
2301             oarg = (Object *)dedtypes->data[i];
2302             if (!oarg)
2303                 goto Lnomatch;
2304         }
2305     }
2306
2307     sa = getDsymbol(oarg);
2308     if (!sa)
2309         goto Lnomatch;
2310
2311     if (specAlias)
2312     {
2313         if (!sa || sa == sdummy)
2314             goto Lnomatch;
2315         if (sa != specAlias)
2316             goto Lnomatch;
2317     }
2318     else if (dedtypes->data[i])
2319     {   // Must match already deduced symbol
2320         Dsymbol *s = (Dsymbol *)dedtypes->data[i];
2321
2322         if (!sa || s != sa)
2323             goto Lnomatch;
2324     }
2325     dedtypes->data[i] = sa;
2326
2327     *psparam = new AliasDeclaration(loc, ident, sa);
2328     return MATCHexact;
2329
2330 Lnomatch:
2331     *psparam = NULL;
2332     return MATCHnomatch;
2333 }
2334
2335
2336 void TemplateAliasParameter::print(Object *oarg, Object *oded)
2337 {
2338     fprintf(stderr, " %s\n", ident->toChars());
2339
2340     Dsymbol *sa = isDsymbol(oded);
2341     assert(sa);
2342
2343     fprintf(stderr, "\tArgument alias: %s\n", sa->toChars());
2344 }
2345
2346 void TemplateAliasParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2347 {
2348     buf->writestring("alias ");
2349     buf->writestring(ident->toChars());
2350     if (specAliasT)
2351     {
2352         buf->writestring(" : ");
2353         specAliasT->toCBuffer(buf, NULL, hgs);
2354     }
2355     if (defaultAlias)
2356     {
2357         buf->writestring(" = ");
2358         defaultAlias->toCBuffer(buf, NULL, hgs);
2359     }
2360 }
2361
2362
2363 void *TemplateAliasParameter::dummyArg()
2364 {   Dsymbol *s;
2365
2366     s = specAlias;
2367     if (!s)
2368     {
2369         if (!sdummy)
2370             sdummy = new Dsymbol();
2371         s = sdummy;
2372     }
2373     return (void*)s;
2374 }
2375
2376
2377 Object *TemplateAliasParameter::specialization()
2378 {
2379     return specAliasT;
2380 }
2381
2382
2383 Object *TemplateAliasParameter::defaultArg(Loc loc, Scope *sc)
2384 {
2385     Dsymbol *s = NULL;
2386
2387     if (defaultAlias)
2388     {
2389         s = defaultAlias->toDsymbol(sc);
2390         if (!s)
2391             error("%s is not a symbol", defaultAlias->toChars());
2392     }
2393     return s;
2394 }
2395
2396 /* ======================== TemplateValueParameter ========================== */
2397
2398 // value-parameter
2399
2400 Expression *TemplateValueParameter::edummy = NULL;
2401
2402 TemplateValueParameter::TemplateValueParameter(Loc loc, Identifier *ident, Type *valType,
2403         Expression *specValue, Expression *defaultValue)
2404     : TemplateParameter(loc, ident)
2405 {
2406     this->ident = ident;
2407     this->valType = valType;
2408     this->specValue = specValue;
2409     this->defaultValue = defaultValue;
2410 }
2411
2412 TemplateValueParameter *TemplateValueParameter::isTemplateValueParameter()
2413 {
2414     return this;
2415 }
2416
2417 TemplateParameter *TemplateValueParameter::syntaxCopy()
2418 {
2419     TemplateValueParameter *tp =
2420         new TemplateValueParameter(loc, ident, valType, specValue, defaultValue);
2421     tp->valType = valType->syntaxCopy();
2422     if (specValue)
2423         tp->specValue = specValue->syntaxCopy();
2424     if (defaultValue)
2425         tp->defaultValue = defaultValue->syntaxCopy();
2426     return tp;
2427 }
2428
2429 void TemplateValueParameter::declareParameter(Scope *sc)
2430 {
2431     VarDeclaration *v = new VarDeclaration(loc, valType, ident, NULL);
2432     v->storage_class = STCtemplateparameter;
2433     if (!sc->insert(v))
2434         error(loc, "parameter '%s' multiply defined", ident->toChars());
2435     sparam = v;
2436 }
2437
2438 void TemplateValueParameter::semantic(Scope *sc)
2439 {
2440     sparam->semantic(sc);
2441     valType = valType->semantic(loc, sc);
2442     if (!(valType->isintegral() || valType->isfloating() || valType->isString()) &&
2443         valType->ty != Tident)
2444         error(loc, "arithmetic/string type expected for value-parameter, not %s", valType->toChars());
2445
2446     if (specValue)
2447     {   Expression *e = specValue;
2448
2449         e = e->semantic(sc);
2450         e = e->implicitCastTo(sc, valType);
2451         e = e->optimize(WANTvalue | WANTinterpret);
2452         if (e->op == TOKint64 || e->op == TOKfloat64 ||
2453             e->op == TOKcomplex80 || e->op == TOKnull || e->op == TOKstring)
2454             specValue = e;
2455         //e->toInteger();
2456     }
2457
2458 #if 0   // defer semantic analysis to arg match
2459     if (defaultValue)
2460     {   Expression *e = defaultValue;
2461
2462         e = e->semantic(sc);
2463         e = e->implicitCastTo(sc, valType);
2464         e = e->optimize(WANTvalue | WANTinterpret);
2465         if (e->op == TOKint64)
2466             defaultValue = e;
2467         //e->toInteger();
2468     }
2469 #endif
2470 }
2471
2472 int TemplateValueParameter::overloadMatch(TemplateParameter *tp)
2473 {
2474     TemplateValueParameter *tvp = tp->isTemplateValueParameter();
2475
2476     if (tvp)
2477     {
2478         if (valType != tvp->valType)
2479             goto Lnomatch;
2480
2481         if (valType && !valType->equals(tvp->valType))
2482             goto Lnomatch;
2483
2484         if (specValue != tvp->specValue)
2485             goto Lnomatch;
2486
2487         return 1;                       // match
2488     }
2489
2490 Lnomatch:
2491     return 0;
2492 }
2493
2494
2495 MATCH TemplateValueParameter::matchArg(Scope *sc,
2496         Objects *tiargs, int i, TemplateParameters *parameters, Objects *dedtypes,
2497         Declaration **psparam, int flags)
2498 {
2499     //printf("TemplateValueParameter::matchArg()\n");
2500
2501     Initializer *init;
2502     Declaration *sparam;
2503     MATCH m = MATCHexact;
2504     Expression *ei;
2505     Object *oarg;
2506
2507     if (i < tiargs->dim)
2508         oarg = (Object *)tiargs->data[i];
2509     else
2510     {   // Get default argument instead
2511         oarg = defaultArg(loc, sc);
2512         if (!oarg)
2513         {   assert(i < dedtypes->dim);
2514             // It might have already been deduced
2515             oarg = (Object *)dedtypes->data[i];
2516             if (!oarg)
2517                 goto Lnomatch;
2518         }
2519     }
2520
2521     ei = isExpression(oarg);
2522     Type *vt;
2523
2524     if (!ei && oarg)
2525         goto Lnomatch;
2526
2527     if (ei && ei->op == TOKvar)
2528     {   // Resolve const variables that we had skipped earlier
2529         ei = ei->optimize(WANTvalue | WANTinterpret);
2530     }
2531
2532     if (specValue)
2533     {
2534         if (!ei || ei == edummy)
2535             goto Lnomatch;
2536
2537         Expression *e = specValue;
2538
2539         e = e->semantic(sc);
2540         e = e->implicitCastTo(sc, valType);
2541         e = e->optimize(WANTvalue | WANTinterpret);
2542         //e->type = e->type->toHeadMutable();
2543
2544         ei = ei->syntaxCopy();
2545         ei = ei->semantic(sc);
2546         ei = ei->optimize(WANTvalue | WANTinterpret);
2547         //ei->type = ei->type->toHeadMutable();
2548         //printf("\tei: %s, %s\n", ei->toChars(), ei->type->toChars());
2549         //printf("\te : %s, %s\n", e->toChars(), e->type->toChars());
2550         if (!ei->equals(e))
2551             goto Lnomatch;
2552     }
2553     else if (dedtypes->data[i])
2554     {   // Must match already deduced value
2555         Expression *e = (Expression *)dedtypes->data[i];
2556
2557         if (!ei || !ei->equals(e))
2558             goto Lnomatch;
2559     }
2560 Lmatch:
2561     //printf("\tvalType: %s, ty = %d\n", valType->toChars(), valType->ty);
2562     vt = valType->semantic(0, sc);
2563     //printf("ei: %s, ei->type: %s\n", ei->toChars(), ei->type->toChars());
2564     //printf("vt = %s\n", vt->toChars());
2565     if (ei->type)
2566     {
2567         //ei->type = ei->type->toHeadMutable();
2568         m = (MATCH)ei->implicitConvTo(vt);
2569         //printf("m: %d\n", m);
2570         if (!m)
2571             goto Lnomatch;
2572     }
2573     dedtypes->data[i] = ei;
2574
2575     init = new ExpInitializer(loc, ei);
2576     sparam = new VarDeclaration(loc, vt, ident, init);
2577     sparam->storage_class = STCmanifest;
2578     *psparam = sparam;
2579     return m;
2580
2581 Lnomatch:
2582     //printf("\tno match\n");
2583     *psparam = NULL;
2584     return MATCHnomatch;
2585 }
2586
2587
2588 void TemplateValueParameter::print(Object *oarg, Object *oded)
2589 {
2590     fprintf(stderr, " %s\n", ident->toChars());
2591
2592     Expression *ea = isExpression(oded);
2593
2594     if (specValue)
2595         fprintf(stderr, "\tSpecialization: %s\n", specValue->toChars());
2596     fprintf(stderr, "\tArgument Value: %s\n", ea ? ea->toChars() : "NULL");
2597 }
2598
2599
2600 void TemplateValueParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2601 {
2602     valType->toCBuffer(buf, ident, hgs);
2603     if (specValue)
2604     {
2605         buf->writestring(" : ");
2606         specValue->toCBuffer(buf, hgs);
2607     }
2608     if (defaultValue)
2609     {
2610         buf->writestring(" = ");
2611         defaultValue->toCBuffer(buf, hgs);
2612     }
2613 }
2614
2615
2616 void *TemplateValueParameter::dummyArg()
2617 {   Expression *e;
2618
2619     e = specValue;
2620     if (!e)
2621     {
2622         // Create a dummy value
2623         if (!edummy)
2624             edummy = valType->defaultInit();
2625         e = edummy;
2626     }
2627     return (void *)e;
2628 }
2629
2630
2631 Object *TemplateValueParameter::specialization()
2632 {
2633     return specValue;
2634 }
2635
2636
2637 Object *TemplateValueParameter::defaultArg(Loc loc, Scope *sc)
2638 {
2639     Expression *e = defaultValue;
2640     if (e)
2641     {
2642         e = e->syntaxCopy();
2643         e = e->semantic(sc);
2644 #if V2
2645         if (e->op == TOKdefault)
2646         {   DefaultInitExp *de = (DefaultInitExp *)e;
2647             e = de->resolve(loc, sc);
2648         }
2649 #endif
2650     }
2651     return e;
2652 }
2653
2654 /* ======================== TemplateTupleParameter ========================== */
2655
2656 // variadic-parameter
2657
2658 TemplateTupleParameter::TemplateTupleParameter(Loc loc, Identifier *ident)
2659     : TemplateParameter(loc, ident)
2660 {
2661     this->ident = ident;
2662 }
2663
2664 TemplateTupleParameter *TemplateTupleParameter::isTemplateTupleParameter()
2665 {
2666     return this;
2667 }
2668
2669 TemplateParameter *TemplateTupleParameter::syntaxCopy()
2670 {
2671     TemplateTupleParameter *tp = new TemplateTupleParameter(loc, ident);
2672     return tp;
2673 }
2674
2675 void TemplateTupleParameter::declareParameter(Scope *sc)
2676 {
2677     TypeIdentifier *ti = new TypeIdentifier(loc, ident);
2678     sparam = new AliasDeclaration(loc, ident, ti);
2679     if (!sc->insert(sparam))
2680         error(loc, "parameter '%s' multiply defined", ident->toChars());
2681 }
2682
2683 void TemplateTupleParameter::semantic(Scope *sc)
2684 {
2685 }
2686
2687 int TemplateTupleParameter::overloadMatch(TemplateParameter *tp)
2688 {
2689     TemplateTupleParameter *tvp = tp->isTemplateTupleParameter();
2690
2691     if (tvp)
2692     {
2693         return 1;                       // match
2694     }
2695
2696 Lnomatch:
2697     return 0;
2698 }
2699
2700 MATCH TemplateTupleParameter::matchArg(Scope *sc,
2701         Objects *tiargs, int i, TemplateParameters *parameters,
2702         Objects *dedtypes,
2703         Declaration **psparam, int flags)
2704 {
2705     //printf("TemplateTupleParameter::matchArg()\n");
2706
2707     /* The rest of the actual arguments (tiargs[]) form the match
2708      * for the variadic parameter.
2709      */
2710     assert(i + 1 == dedtypes->dim);     // must be the last one
2711     Tuple *ovar;
2712     if (i + 1 == tiargs->dim && isTuple((Object *)tiargs->data[i]))
2713         ovar = isTuple((Object *)tiargs->data[i]);
2714     else
2715     {
2716         ovar = new Tuple();
2717         //printf("ovar = %p\n", ovar);
2718         if (i < tiargs->dim)
2719         {
2720             //printf("i = %d, tiargs->dim = %d\n", i, tiargs->dim);
2721             ovar->objects.setDim(tiargs->dim - i);
2722             for (size_t j = 0; j < ovar->objects.dim; j++)
2723                 ovar->objects.data[j] = tiargs->data[i + j];
2724         }
2725     }
2726     *psparam = new TupleDeclaration(loc, ident, &ovar->objects);
2727     dedtypes->data[i] = (void *)ovar;
2728     return MATCHexact;
2729 }
2730
2731
2732 void TemplateTupleParameter::print(Object *oarg, Object *oded)
2733 {
2734     printf(" %s... [", ident->toChars());
2735     Tuple *v = isTuple(oded);
2736     assert(v);
2737
2738     //printf("|%d| ", v->objects.dim);
2739     for (int i = 0; i < v->objects.dim; i++)
2740     {
2741         if (i)
2742             printf(", ");
2743
2744         Object *o = (Object *)v->objects.data[i];
2745
2746         Dsymbol *sa = isDsymbol(o);
2747         if (sa)
2748             printf("alias: %s", sa->toChars());
2749
2750         Type *ta = isType(o);
2751         if (ta)
2752             printf("type: %s", ta->toChars());
2753
2754         Expression *ea = isExpression(o);
2755         if (ea)
2756             printf("exp: %s", ea->toChars());
2757
2758         assert(!isTuple(o));            // no nested Tuple arguments
2759     }
2760
2761     printf("]\n");
2762 }
2763
2764 void TemplateTupleParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2765 {
2766     buf->writestring(ident->toChars());
2767     buf->writestring("...");
2768 }
2769
2770
2771 void *TemplateTupleParameter::dummyArg()
2772 {
2773     return NULL;
2774 }
2775
2776
2777 Object *TemplateTupleParameter::specialization()
2778 {
2779     return NULL;
2780 }
2781
2782
2783 Object *TemplateTupleParameter::defaultArg(Loc loc, Scope *sc)
2784 {
2785     return NULL;
2786 }
2787
2788 /* ======================== TemplateInstance ================================ */
2789
2790 TemplateInstance::TemplateInstance(Loc loc, Identifier *ident)
2791     : ScopeDsymbol(NULL)
2792 {
2793 #if LOG
2794     printf("TemplateInstance(this = %p, ident = '%s')\n", this, ident ? ident->toChars() : "null");
2795 #endif
2796     this->loc = loc;
2797     this->name = ident;
2798     this->tiargs = NULL;
2799     this->tempdecl = NULL;
2800     this->inst = NULL;
2801     this->argsym = NULL;
2802     this->aliasdecl = NULL;
2803     this->semanticdone = 0;
2804     this->withsym = NULL;
2805     this->nest = 0;
2806 #ifdef IN_GCC
2807     this->objFileModule = NULL;
2808 #endif
2809     this->havetempdecl = 0;
2810     this->isnested = NULL;
2811     this->errors = 0;
2812 }
2813
2814
2815 TemplateInstance::TemplateInstance(Loc loc, TemplateDeclaration *td, Objects *tiargs)
2816     : ScopeDsymbol(NULL)
2817 {
2818 #if LOG
2819     printf("TemplateInstance(this = %p, tempdecl = '%s')\n", this, td->toChars());
2820 #endif
2821     this->loc = loc;
2822     this->name = td->ident;
2823     this->tiargs = tiargs;
2824     this->tempdecl = td;
2825     this->inst = NULL;
2826     this->argsym = NULL;
2827     this->aliasdecl = NULL;
2828     this->semanticdone = 0;
2829     this->withsym = NULL;
2830     this->nest = 0;
2831 #ifdef IN_GCC
2832     this->objFileModule = NULL;
2833 #endif
2834     this->havetempdecl = 1;
2835     this->isnested = NULL;
2836     this->errors = 0;
2837
2838     assert((size_t)tempdecl->scope > 0x10000);
2839 }
2840
2841
2842 Objects *TemplateInstance::arraySyntaxCopy(Objects *objs)
2843 {
2844     Objects *a = NULL;
2845     if (objs)
2846     {   a = new Objects();
2847         a->setDim(objs->dim);
2848         for (size_t i = 0; i < objs->dim; i++)
2849         {
2850             Type *ta = isType((Object *)objs->data[i]);
2851             if (ta)
2852                 a->data[i] = ta->syntaxCopy();
2853             else
2854             {
2855                 Expression *ea = isExpression((Object *)objs->data[i]);
2856                 assert(ea);
2857                 a->data[i] = ea->syntaxCopy();
2858             }
2859         }
2860     }
2861     return a;
2862 }
2863
2864 Dsymbol *TemplateInstance::syntaxCopy(Dsymbol *s)
2865 {
2866     TemplateInstance *ti;
2867     int i;
2868
2869     if (s)
2870         ti = (TemplateInstance *)s;
2871     else
2872         ti = new TemplateInstance(loc, name);
2873
2874     ti->tiargs = arraySyntaxCopy(tiargs);
2875
2876     ScopeDsymbol::syntaxCopy(ti);
2877     return ti;
2878 }
2879
2880
2881 #ifdef IN_GCC
2882 #include "d-dmd-gcc.h"
2883 #endif
2884
2885 void TemplateInstance::semantic(Scope *sc)
2886 {
2887     if (global.errors)
2888     {
2889         if (!global.gag)
2890         {
2891             /* Trying to soldier on rarely generates useful messages
2892              * at this point.
2893              */
2894             fatal();
2895         }
2896         return;
2897     }
2898 #if LOG
2899     printf("\n+TemplateInstance::semantic('%s', this=%p)\n", toChars(), this);
2900 #endif
2901 #ifdef IN_GCC
2902     /*
2903     fprintf(stderr, "ti '%s' (%p), belongs in '%s'\n", toChars(), this,
2904         sc->module->toPrettyChars());
2905     if (inst) {
2906         fprintf(stderr, "  -- really '%s' (%p)\n", inst->toChars(), inst);
2907     } else {
2908         fprintf(stderr, "  -- doing semantic\n");
2909     }
2910     */
2911 #endif
2912     if (inst)           // if semantic() was already run
2913     {
2914 #if LOG
2915         printf("-TemplateInstance::semantic('%s', this=%p) already run\n", inst->toChars(), inst);
2916 #endif
2917         return;
2918     }
2919
2920     if (semanticdone != 0)
2921     {
2922         error(loc, "recursive template expansion");
2923 //      inst = this;
2924         return;
2925     }
2926     semanticdone = 1;
2927
2928 #if LOG
2929     printf("\tdo semantic\n");
2930 #endif
2931     if (havetempdecl)
2932     {
2933         assert((size_t)tempdecl->scope > 0x10000);
2934         // Deduce tdtypes
2935         tdtypes.setDim(tempdecl->parameters->dim);
2936         if (!tempdecl->matchWithInstance(this, &tdtypes, 2))
2937         {
2938             error("incompatible arguments for template instantiation");
2939             inst = this;
2940             return;
2941         }
2942     }
2943     else
2944     {
2945         // Run semantic on each argument, place results in tiargs[]
2946         semanticTiargs(sc);
2947
2948         tempdecl = findTemplateDeclaration(sc);
2949         if (tempdecl)
2950             tempdecl = findBestMatch(sc);
2951         if (!tempdecl || global.errors)
2952         {   inst = this;
2953             //printf("error return %p, %d\n", tempdecl, global.errors);
2954             return;             // error recovery
2955         }
2956     }
2957
2958     isNested(tiargs);
2959
2960     /* See if there is an existing TemplateInstantiation that already
2961      * implements the typeargs. If so, just refer to that one instead.
2962      */
2963
2964     for (size_t i = 0; i < tempdecl->instances.dim; i++)
2965     {
2966         TemplateInstance *ti = (TemplateInstance *)tempdecl->instances.data[i];
2967 #if LOG
2968         printf("\t%s: checking for match with instance %d (%p): '%s'\n", toChars(), i, ti, ti->toChars());
2969 #endif
2970         assert(tdtypes.dim == ti->tdtypes.dim);
2971
2972         // Nesting must match
2973         if (isnested != ti->isnested)
2974             continue;
2975 #if 0
2976         if (isnested && sc->parent != ti->parent)
2977             continue;
2978 #endif
2979         for (size_t j = 0; j < tdtypes.dim; j++)
2980         {   Object *o1 = (Object *)tdtypes.data[j];
2981             Object *o2 = (Object *)ti->tdtypes.data[j];
2982             if (!match(o1, o2, tempdecl, sc))
2983                 goto L1;
2984         }
2985
2986         // It's a match
2987         inst = ti;
2988         parent = ti->parent;
2989 #if LOG
2990         printf("\tit's a match with instance %p\n", inst);
2991 #endif
2992         return;
2993
2994      L1:
2995         ;
2996     }
2997
2998     /* So, we need to implement 'this' instance.
2999      */
3000 #if LOG
3001     printf("\timplement template instance '%s'\n", toChars());
3002 #endif
3003     unsigned errorsave = global.errors;
3004     inst = this;
3005     int tempdecl_instance_idx = tempdecl->instances.dim;
3006     tempdecl->instances.push(this);
3007     parent = tempdecl->parent;
3008     //printf("parent = '%s'\n", parent->kind());
3009
3010     ident = genIdent();         // need an identifier for name mangling purposes.
3011
3012 #if 1
3013     if (isnested)
3014         parent = isnested;
3015 #endif
3016     //printf("parent = '%s'\n", parent->kind());
3017
3018     // Add 'this' to the enclosing scope's members[] so the semantic routines
3019     // will get called on the instance members
3020 #if 1
3021     int dosemantic3 = 0;
3022     {   Array *a;
3023
3024         Scope *scx = sc;
3025 #if 0
3026         for (scx = sc; scx; scx = scx->enclosing)
3027             if (scx->scopesym)
3028                 break;
3029 #endif
3030
3031 #ifdef IN_GCC
3032         /* For "all" and "private" template modes, templates are always
3033            emitted.  Problem:  This picks up templates that aren't even
3034            needed in the current module. */
3035
3036         if (d_gcc_force_templates())
3037         {
3038             //fprintf(stderr, "\t0: adding to %s %s\n", sc->scopesym->kind(), sc->scopesym->toChars());
3039             objFileModule = d_gcc_get_output_module();
3040             a = objFileModule->members;
3041         }
3042         else
3043 #endif
3044
3045         //if (scx && scx->scopesym) printf("3: scx is %s %s\n", scx->scopesym->kind(), scx->scopesym->toChars());
3046         if (scx && scx->scopesym && scx->scopesym->members && !scx->scopesym->isTemplateMixin())
3047         {
3048             //printf("\t1: adding to %s %s\n", scx->scopesym->kind(), scx->scopesym->toChars());
3049             a = scx->scopesym->members;
3050 #ifdef IN_GCC
3051             {
3052                 Dsymbol * p = scx->scopesym;
3053                 Module * m;
3054                 TemplateInstance * i;
3055
3056                 while (p) {
3057                     if ( (i = p->isTemplateInstance()) ) {
3058                         if (i->objFileModule) {
3059                             objFileModule = i->objFileModule;
3060                             break;
3061                         }
3062                     } else if ( (m = p->isModule()) ) {
3063                         objFileModule = m; // %% importedFrom ?
3064                         break;
3065                     }
3066                     p = p->parent;
3067                 }
3068                 // fprintf(stderr, "\t1: adding %s to module %s via %s %s\n", tempdecl->toChars(), objFileModule?objFileModule->toChars():"", sc->scopesym->kind(), sc->scopesym->toChars());
3069             }
3070 #endif
3071         }
3072         else
3073         {   Module *m = sc->module->importedFrom;
3074             //printf("\t2: adding to module %s instead of module %s\n", m->toChars(), sc->module->toChars());
3075             a = m->members;
3076             if (m->semanticdone >= 3)
3077                 dosemantic3 = 1;
3078 #ifdef IN_GCC
3079             objFileModule = m;
3080 #endif
3081         }
3082         for (int i = 0; 1; i++)
3083         {
3084             if (i == a->dim)
3085             {
3086                 a->push(this);
3087                 break;
3088             }
3089             if (this == (Dsymbol *)a->data[i])  // if already in Array
3090                 break;
3091         }
3092     }
3093 #endif
3094
3095     // Copy the syntax trees from the TemplateDeclaration
3096     members = Dsymbol::arraySyntaxCopy(tempdecl->members);
3097
3098     // Create our own scope for the template parameters
3099     Scope *scope = tempdecl->scope;
3100     if (!scope)
3101     {
3102         error("forward reference to template declaration %s\n", tempdecl->toChars());
3103         return;
3104     }
3105
3106 #if LOG
3107     printf("\tcreate scope for template parameters '%s'\n", toChars());
3108 #endif
3109     argsym = new ScopeDsymbol();
3110     argsym->parent = scope->parent;
3111     scope = scope->push(argsym);
3112
3113     // Declare each template parameter as an alias for the argument type
3114     declareParameters(scope);
3115
3116     // Add members of template instance to template instance symbol table
3117 //    parent = scope->scopesym;
3118     symtab = new DsymbolTable();
3119     int memnum = 0;
3120     for (int i = 0; i < members->dim; i++)
3121     {
3122         Dsymbol *s = (Dsymbol *)members->data[i];
3123 #if LOG
3124         printf("\t[%d] adding member '%s' %p kind %s to '%s', memnum = %d\n", i, s->toChars(), s, s->kind(), this->toChars(), memnum);
3125 #endif
3126         memnum |= s->addMember(scope, this, memnum);
3127     }
3128 #if LOG
3129     printf("adding members done\n");
3130 #endif
3131
3132     /* See if there is only one member of template instance, and that
3133      * member has the same name as the template instance.
3134      * If so, this template instance becomes an alias for that member.
3135      */
3136     //printf("members->dim = %d\n", members->dim);
3137     if (members->dim)
3138     {
3139         Dsymbol *s;
3140         if (Dsymbol::oneMembers(members, &s) && s)
3141         {
3142             //printf("s->kind = '%s'\n", s->kind());
3143             //s->print();
3144             //printf("'%s', '%s'\n", s->ident->toChars(), tempdecl->ident->toChars());
3145             if (s->ident && s->ident->equals(tempdecl->ident))
3146             {
3147                 //printf("setting aliasdecl\n");
3148                 aliasdecl = new AliasDeclaration(loc, s->ident, s);
3149             }
3150         }
3151     }
3152
3153     // Do semantic() analysis on template instance members
3154 #if LOG
3155     printf("\tdo semantic() on template instance members '%s'\n", toChars());
3156 #endif
3157     Scope *sc2;
3158     sc2 = scope->push(this);
3159     //printf("isnested = %d, sc->parent = %s\n", isnested, sc->parent->toChars());
3160     sc2->parent = /*isnested ? sc->parent :*/ this;
3161
3162 #ifndef IN_GCC
3163 #if _WIN32
3164   __try
3165   {
3166 #endif
3167 #endif
3168     for (int i = 0; i < members->dim; i++)
3169     {
3170         Dsymbol *s = (Dsymbol *)members->data[i];
3171         //printf("\t[%d] semantic on '%s' %p kind %s in '%s'\n", i, s->toChars(), s, s->kind(), this->toChars());
3172         //printf("test: isnested = %d, sc2->parent = %s\n", isnested, sc2->parent->toChars());
3173 //      if (isnested)
3174 //          s->parent = sc->parent;
3175         //printf("test3: isnested = %d, s->parent = %s\n", isnested, s->parent->toChars());
3176         s->semantic(sc2);
3177         //printf("test4: isnested = %d, s->parent = %s\n", isnested, s->parent->toChars());
3178         sc2->module->runDeferredSemantic();
3179     }
3180 #ifndef IN_GCC
3181 #if _WIN32
3182   }
3183   __except (__ehfilter(GetExceptionInformation()))
3184   {
3185     global.gag = 0;                     // ensure error message gets printed
3186     error("recursive expansion");
3187     fatal();
3188   }
3189 #endif
3190 #endif
3191
3192     /* If any of the instantiation members didn't get semantic() run
3193      * on them due to forward references, we cannot run semantic2()
3194      * or semantic3() yet.
3195      */
3196     for (size_t i = 0; i < Module::deferred.dim; i++)
3197     {   Dsymbol *sd = (Dsymbol *)Module::deferred.data[i];
3198
3199         if (sd->parent == this)
3200             goto Laftersemantic;
3201     }
3202
3203     /* The problem is when to parse the initializer for a variable.
3204      * Perhaps VarDeclaration::semantic() should do it like it does
3205      * for initializers inside a function.
3206      */
3207 //    if (sc->parent->isFuncDeclaration())
3208
3209         /* BUG 782: this has problems if the classes this depends on
3210          * are forward referenced. Find a way to defer semantic()
3211          * on this template.
3212          */
3213         semantic2(sc2);
3214
3215     if (sc->func || dosemantic3)
3216     {
3217         semantic3(sc2);
3218     }
3219
3220   Laftersemantic:
3221     sc2->pop();
3222
3223     scope->pop();
3224
3225     // Give additional context info if error occurred during instantiation
3226     if (global.errors != errorsave)
3227     {
3228         error("error instantiating");
3229         errors = 1;
3230         if (global.gag)
3231             tempdecl->instances.remove(tempdecl_instance_idx);
3232     }
3233
3234 #if LOG
3235     printf("-TemplateInstance::semantic('%s', this=%p)\n", toChars(), this);
3236 #endif
3237 }
3238
3239
3240 void TemplateInstance::semanticTiargs(Scope *sc)
3241 {
3242     //printf("+TemplateInstance::semanticTiargs() %s\n", toChars());
3243     semanticTiargs(loc, sc, tiargs, 0);
3244 }
3245
3246 /**********************************
3247  * Input:
3248  *      flags   1: replace const variables with their initializers
3249  */
3250
3251 void TemplateInstance::semanticTiargs(Loc loc, Scope *sc, Objects *tiargs, int flags)
3252 {
3253     // Run semantic on each argument, place results in tiargs[]
3254     //printf("+TemplateInstance::semanticTiargs()\n");
3255     if (!tiargs)
3256         return;
3257     for (size_t j = 0; j < tiargs->dim; j++)
3258     {
3259         Object *o = (Object *)tiargs->data[j];
3260         Type *ta = isType(o);
3261         Expression *ea = isExpression(o);
3262         Dsymbol *sa = isDsymbol(o);
3263
3264         //printf("1: tiargs->data[%d] = %p, %p, %p, ea=%p, ta=%p\n", j, o, isDsymbol(o), isTuple(o), ea, ta);
3265         if (ta)
3266         {
3267             //printf("type %s\n", ta->toChars());
3268             // It might really be an Expression or an Alias
3269             ta->resolve(loc, sc, &ea, &ta, &sa);
3270             if (ea)
3271             {
3272                 ea = ea->semantic(sc);
3273                 /* This test is to skip substituting a const var with
3274                  * its initializer. The problem is the initializer won't
3275                  * match with an 'alias' parameter. Instead, do the
3276                  * const substitution in TemplateValueParameter::matchArg().
3277                  */
3278                 if (ea->op != TOKvar || flags & 1)
3279                     ea = ea->optimize(WANTvalue | WANTinterpret);
3280                 tiargs->data[j] = ea;
3281             }
3282             else if (sa)
3283             {   tiargs->data[j] = sa;
3284                 TupleDeclaration *d = sa->toAlias()->isTupleDeclaration();
3285                 if (d)
3286                 {
3287                     size_t dim = d->objects->dim;
3288                     tiargs->remove(j);
3289                     tiargs->insert(j, d->objects);
3290                     j--;
3291                 }
3292             }
3293             else if (ta)
3294             {
3295                 if (ta->ty == Ttuple)
3296                 {   // Expand tuple
3297                     TypeTuple *tt = (TypeTuple *)ta;
3298                     size_t dim = tt->arguments->dim;
3299                     tiargs->remove(j);
3300                     if (dim)
3301                     {   tiargs->reserve(dim);
3302                         for (size_t i = 0; i < dim; i++)
3303                         {   Argument *arg = (Argument *)tt->arguments->data[i];
3304                             tiargs->insert(j + i, arg->type);
3305                         }
3306                     }
3307                     j--;
3308                 }
3309                 else
3310                     tiargs->data[j] = ta;
3311             }
3312             else
3313             {
3314                 assert(global.errors);
3315                 tiargs->data[j] = Type::terror;
3316             }
3317         }
3318         else if (ea)
3319         {
3320             if (!ea)
3321             {   assert(global.errors);
3322                 ea = new IntegerExp(0);
3323             }
3324             assert(ea);
3325             ea = ea->semantic(sc);
3326             if (ea->op != TOKvar || flags & 1)
3327                 ea = ea->optimize(WANTvalue | WANTinterpret);
3328             tiargs->data[j] = ea;
3329             if (ea->op == TOKtype)
3330                 tiargs->data[j] = ea->type;
3331         }
3332         else if (sa)
3333         {
3334         }
3335         else
3336         {
3337             assert(0);
3338         }
3339         //printf("1: tiargs->data[%d] = %p\n", j, tiargs->data[j]);
3340     }
3341 #if 0
3342     printf("-TemplateInstance::semanticTiargs('%s', this=%p)\n", toChars(), this);
3343     for (size_t j = 0; j < tiargs->dim; j++)
3344     {
3345         Object *o = (Object *)tiargs->data[j];
3346         Type *ta = isType(o);
3347         Expression *ea = isExpression(o);
3348         Dsymbol *sa = isDsymbol(o);
3349         Tuple *va = isTuple(o);
3350
3351         printf("\ttiargs[%d] = ta %p, ea %p, sa %p, va %p\n", j, ta, ea, sa, va);
3352     }
3353 #endif
3354 }
3355
3356 /**********************************************
3357  * Find template declaration corresponding to template instance.
3358  */
3359
3360 TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
3361 {
3362     //printf("TemplateInstance::findTemplateDeclaration() %s\n", toChars());
3363     if (!tempdecl)
3364     {
3365         /* Given:
3366          *    foo!( ... )
3367          * figure out which TemplateDeclaration foo refers to.
3368          */
3369         Dsymbol *s;
3370         Dsymbol *scopesym;
3371         Identifier *id;
3372         int i;
3373
3374         id = name;
3375         s = sc->search(loc, id, &scopesym);
3376         if (!s)
3377         {   error("identifier '%s' is not defined", id->toChars());
3378             return NULL;
3379         }
3380 #if LOG
3381         printf("It's an instance of '%s' kind '%s'\n", s->toChars(), s->kind());
3382         if (s->parent)
3383             printf("s->parent = '%s'\n", s->parent->toChars());
3384 #endif
3385         withsym = scopesym->isWithScopeSymbol();
3386
3387         /* We might have found an alias within a template when
3388          * we really want the template.
3389          */
3390         TemplateInstance *ti;
3391         if (s->parent &&
3392             (ti = s->parent->isTemplateInstance()) != NULL)
3393         {
3394             if (
3395                 (ti->name == id ||
3396                  ti->toAlias()->ident == id)
3397                 &&
3398                 ti->tempdecl)
3399             {
3400                 /* This is so that one can refer to the enclosing
3401                  * template, even if it has the same name as a member
3402                  * of the template, if it has a !(arguments)
3403                  */
3404                 tempdecl = ti->tempdecl;
3405                 if (tempdecl->overroot)         // if not start of overloaded list of TemplateDeclaration's
3406                     tempdecl = tempdecl->overroot; // then get the start
3407                 s = tempdecl;
3408             }
3409         }
3410
3411         s = s->toAlias();
3412
3413         /* It should be a TemplateDeclaration, not some other symbol
3414          */
3415         tempdecl = s->isTemplateDeclaration();
3416         if (!tempdecl)
3417         {
3418             if (!s->parent && global.errors)
3419                 return NULL;
3420             if (!s->parent && s->getType())
3421             {   Dsymbol *s2 = s->getType()->toDsymbol(sc);
3422                 if (!s2)
3423                 {
3424                     error("%s is not a template declaration, it is a %s", id->toChars(), s->kind());
3425                     return NULL;
3426                 }
3427                 s = s2;
3428             }
3429 #ifdef DEBUG
3430             //if (!s->parent) printf("s = %s %s\n", s->kind(), s->toChars());
3431 #endif
3432             //assert(s->parent);
3433             TemplateInstance *ti = s->parent ? s->parent->isTemplateInstance() : NULL;
3434             if (ti &&
3435                 (ti->name == id ||
3436                  ti->toAlias()->ident == id)
3437                 &&
3438                 ti->tempdecl)
3439             {
3440                 /* This is so that one can refer to the enclosing
3441                  * template, even if it has the same name as a member
3442                  * of the template, if it has a !(arguments)
3443                  */
3444                 tempdecl = ti->tempdecl;
3445                 if (tempdecl->overroot)         // if not start of overloaded list of TemplateDeclaration's
3446                     tempdecl = tempdecl->overroot; // then get the start
3447             }
3448             else
3449             {
3450                 error("%s is not a template declaration, it is a %s", id->toChars(), s->kind());
3451                 return NULL;
3452             }
3453         }
3454     }
3455     else
3456         assert(tempdecl->isTemplateDeclaration());
3457     return tempdecl;
3458 }
3459
3460 TemplateDeclaration *TemplateInstance::findBestMatch(Scope *sc)
3461 {
3462     /* Since there can be multiple TemplateDeclaration's with the same
3463      * name, look for the best match.
3464      */
3465     TemplateDeclaration *td_ambig = NULL;
3466     TemplateDeclaration *td_best = NULL;
3467     MATCH m_best = MATCHnomatch;
3468     Objects dedtypes;
3469
3470 #if LOG
3471     printf("TemplateInstance::findBestMatch()\n");
3472 #endif
3473     for (TemplateDeclaration *td = tempdecl; td; td = td->overnext)
3474     {
3475         MATCH m;
3476
3477 //if (tiargs->dim) printf("2: tiargs->dim = %d, data[0] = %p\n", tiargs->dim, tiargs->data[0]);
3478
3479         // If more arguments than parameters,
3480         // then this is no match.
3481         if (td->parameters->dim < tiargs->dim)
3482         {
3483             if (!td->isVariadic())
3484                 continue;
3485         }
3486
3487         dedtypes.setDim(td->parameters->dim);
3488         dedtypes.zero();
3489         if (!td->scope)
3490         {
3491             error("forward reference to template declaration %s", td->toChars());
3492             return NULL;
3493         }
3494         m = td->matchWithInstance(this, &dedtypes, 0);
3495         //printf("m = %d\n", m);
3496         if (!m)                 // no match at all
3497             continue;
3498
3499 #if 1
3500         if (m < m_best)
3501             goto Ltd_best;
3502         if (m > m_best)
3503             goto Ltd;
3504 #else
3505         if (!m_best)
3506             goto Ltd;
3507 #endif
3508         {
3509         // Disambiguate by picking the most specialized TemplateDeclaration
3510         MATCH c1 = td->leastAsSpecialized(td_best);
3511         MATCH c2 = td_best->leastAsSpecialized(td);
3512         //printf("c1 = %d, c2 = %d\n", c1, c2);
3513
3514         if (c1 > c2)
3515             goto Ltd;
3516         else if (c1 < c2)
3517             goto Ltd_best;
3518         else
3519             goto Lambig;
3520         }
3521
3522       Lambig:           // td_best and td are ambiguous
3523         td_ambig = td;
3524         continue;
3525
3526       Ltd_best:         // td_best is the best match so far
3527         td_ambig = NULL;
3528         continue;
3529
3530       Ltd:              // td is the new best match
3531         td_ambig = NULL;
3532         td_best = td;
3533         m_best = m;
3534         tdtypes.setDim(dedtypes.dim);
3535         memcpy(tdtypes.data, dedtypes.data, tdtypes.dim * sizeof(void *));
3536         continue;
3537     }
3538
3539     if (!td_best)
3540     {
3541         error("%s does not match any template declaration", toChars());
3542         return NULL;
3543     }
3544     if (td_ambig)
3545     {
3546         error("%s matches more than one template declaration, %s and %s",
3547                 toChars(), td_best->toChars(), td_ambig->toChars());
3548     }
3549
3550     /* The best match is td_best
3551      */
3552     tempdecl = td_best;
3553
3554 #if 0
3555     /* Cast any value arguments to be same type as value parameter
3556      */
3557     for (size_t i = 0; i < tiargs->dim; i++)
3558     {   Object *o = (Object *)tiargs->data[i];
3559         Expression *ea = isExpression(o);       // value argument
3560         TemplateParameter *tp = (TemplateParameter *)tempdecl->parameters->data[i];
3561         assert(tp);
3562         TemplateValueParameter *tvp = tp->isTemplateValueParameter();
3563         if (tvp)
3564         {
3565             assert(ea);
3566             ea = ea->castTo(tvp->valType);
3567             ea = ea->optimize(WANTvalue | WANTinterpret);
3568             tiargs->data[i] = (Object *)ea;
3569         }
3570     }
3571 #endif
3572
3573 #if LOG
3574     printf("\tIt's a match with template declaration '%s'\n", tempdecl->toChars());
3575 #endif
3576     return tempdecl;
3577 }
3578
3579
3580 /*****************************************
3581  * Determines if a TemplateInstance will need a nested
3582  * generation of the TemplateDeclaration.
3583  */
3584
3585 int TemplateInstance::isNested(Objects *args)
3586 {   int nested = 0;
3587     //printf("TemplateInstance::isNested('%s')\n", tempdecl->ident->toChars());
3588
3589     /* A nested instance happens when an argument references a local
3590      * symbol that is on the stack.
3591      */
3592     for (size_t i = 0; i < args->dim; i++)
3593     {   Object *o = (Object *)args->data[i];
3594         Expression *ea = isExpression(o);
3595         Dsymbol *sa = isDsymbol(o);
3596         Tuple *va = isTuple(o);
3597         if (ea)
3598         {
3599             if (ea->op == TOKvar)
3600             {
3601                 sa = ((VarExp *)ea)->var;
3602                 goto Lsa;
3603             }
3604             if (ea->op == TOKfunction)
3605             {
3606                 sa = ((FuncExp *)ea)->fd;
3607                 goto Lsa;
3608             }
3609         }
3610         else if (sa)
3611         {
3612           Lsa:
3613             Declaration *d = sa->isDeclaration();
3614             if (d && !d->isDataseg() &&
3615 #if V2
3616                 !(d->storage_class & STCmanifest) &&
3617 #endif
3618                 (!d->isFuncDeclaration() || d->isFuncDeclaration()->isNested()) &&
3619                 !isTemplateMixin())
3620             {
3621                 // if module level template
3622                 if (tempdecl->toParent()->isModule())
3623                 {   Dsymbol *dparent = d->toParent();
3624                     if (!isnested)
3625                         isnested = dparent;
3626                     else if (isnested != dparent)
3627                     {
3628                         /* Select the more deeply nested of the two.
3629                          * Error if one is not nested inside the other.
3630                          */
3631                         for (Dsymbol *p = isnested; p; p = p->parent)
3632                         {
3633                             if (p == dparent)
3634                                 goto L1;        // isnested is most nested
3635                         }
3636                         for (Dsymbol *p = dparent; 1; p = p->parent)
3637                         {
3638                             if (p == isnested)
3639                             {   isnested = dparent;
3640                                 goto L1;        // dparent is most nested
3641                             }
3642                         }
3643                         error("is nested in both %s and %s", isnested->toChars(), dparent->toChars());
3644                     }
3645                   L1:
3646                     //printf("\tnested inside %s\n", isnested->toChars());
3647                     nested |= 1;
3648                 }
3649                 else
3650                     error("cannot use local '%s' as template parameter", d->toChars());
3651             }
3652         }
3653         else if (va)
3654         {
3655             nested |= isNested(&va->objects);
3656         }
3657     }
3658     return nested;
3659 }
3660
3661 /****************************************
3662  * This instance needs an identifier for name mangling purposes.
3663  * Create one by taking the template declaration name and adding
3664  * the type signature for it.
3665  */
3666
3667 Identifier *TemplateInstance::genIdent()
3668 {   OutBuffer buf;
3669     char *id;
3670     Objects *args;
3671
3672     //printf("TemplateInstance::genIdent('%s')\n", tempdecl->ident->toChars());
3673     id = tempdecl->ident->toChars();
3674     buf.printf("__T%"PRIuSIZE"%s", strlen(id), id);
3675     args = tiargs;
3676     for (int i = 0; i < args->dim; i++)
3677     {   Object *o = (Object *)args->data[i];
3678         Type *ta = isType(o);
3679         Expression *ea = isExpression(o);
3680         Dsymbol *sa = isDsymbol(o);
3681         Tuple *va = isTuple(o);
3682         //printf("\to %p ta %p ea %p sa %p va %p\n", o, ta, ea, sa, va);
3683         if (ta)
3684         {
3685             buf.writeByte('T');
3686             if (ta->deco)
3687                 buf.writestring(ta->deco);
3688             else
3689             {
3690 #ifdef DEBUG
3691                 printf("ta = %d, %s\n", ta->ty, ta->toChars());
3692 #endif
3693                 assert(global.errors);
3694             }
3695         }
3696         else if (ea)
3697         {   sinteger_t v;
3698             real_t r;
3699
3700             ea = ea->optimize(WANTvalue | WANTinterpret);
3701             if (ea->op == TOKvar)
3702             {
3703                 sa = ((VarExp *)ea)->var;
3704                 ea = NULL;
3705                 goto Lsa;
3706             }
3707             if (ea->op == TOKfunction)
3708             {
3709                 sa = ((FuncExp *)ea)->fd;
3710                 ea = NULL;
3711                 goto Lsa;
3712             }
3713             buf.writeByte('V');
3714             if (ea->op == TOKtuple)
3715             {   ea->error("tuple is not a valid template value argument");
3716                 continue;
3717             }
3718 #if 1
3719             /* Use deco that matches what it would be for a function parameter
3720              */
3721             //buf.writestring(ea->type->toHeadMutable()->deco);
3722             buf.writestring(ea->type->deco);
3723 #else
3724             // Use type of parameter, not type of argument
3725             TemplateParameter *tp = (TemplateParameter *)tempdecl->parameters->data[i];
3726             assert(tp);
3727             TemplateValueParameter *tvp = tp->isTemplateValueParameter();
3728             assert(tvp);
3729             buf.writestring(tvp->valType->deco);
3730 #endif
3731             ea->toMangleBuffer(&buf);
3732         }
3733         else if (sa)
3734         {
3735           Lsa:
3736             buf.writeByte('S');
3737             Declaration *d = sa->isDeclaration();
3738             if (d && !d->type->deco)
3739                 error("forward reference of %s", d->toChars());
3740             else
3741             {
3742                 char *p = sa->mangle();
3743                 buf.printf("%"PRIuSIZE"%s", strlen(p), p);
3744             }
3745         }
3746         else if (va)
3747         {
3748             assert(i + 1 == args->dim);         // must be last one
3749             args = &va->objects;
3750             i = -1;
3751         }
3752         else
3753             assert(0);
3754     }
3755     buf.writeByte('Z');
3756     id = buf.toChars();
3757     buf.data = NULL;
3758     return new Identifier(id, TOKidentifier);
3759 }
3760
3761
3762 /****************************************************
3763  * Declare parameters of template instance, initialize them with the
3764  * template instance arguments.
3765  */
3766
3767 void TemplateInstance::declareParameters(Scope *scope)
3768 {
3769     //printf("TemplateInstance::declareParameters()\n");
3770     for (int i = 0; i < tdtypes.dim; i++)
3771     {
3772         TemplateParameter *tp = (TemplateParameter *)tempdecl->parameters->data[i];
3773         //Object *o = (Object *)tiargs->data[i];
3774         Object *o = (Object *)tdtypes.data[i];
3775
3776         //printf("\ttdtypes[%d] = %p\n", i, o);
3777         tempdecl->declareParameter(scope, tp, o);
3778     }
3779 }
3780
3781
3782 void TemplateInstance::semantic2(Scope *sc)
3783 {   int i;
3784
3785     if (semanticdone >= 2)
3786         return;
3787     semanticdone = 2;
3788 #if LOG
3789     printf("+TemplateInstance::semantic2('%s')\n", toChars());
3790 #endif
3791     if (!errors && members)
3792     {
3793         sc = tempdecl->scope;
3794         assert(sc);
3795         sc = sc->push(argsym);
3796         sc = sc->push(this);
3797         for (i = 0; i < members->dim; i++)
3798         {
3799             Dsymbol *s = (Dsymbol *)members->data[i];
3800 #if LOG
3801 printf("\tmember '%s', kind = '%s'\n", s->toChars(), s->kind());
3802 #endif
3803             s->semantic2(sc);
3804         }
3805         sc = sc->pop();
3806         sc->pop();
3807     }
3808 #if LOG
3809     printf("-TemplateInstance::semantic2('%s')\n", toChars());
3810 #endif
3811 }
3812
3813 void TemplateInstance::semantic3(Scope *sc)
3814 {
3815 #if LOG
3816     printf("TemplateInstance::semantic3('%s'), semanticdone = %d\n", toChars(), semanticdone);
3817 #endif
3818 //if (toChars()[0] == 'D') *(char*)0=0;
3819     if (semanticdone >= 3)
3820         return;
3821     semanticdone = 3;
3822     if (!errors && members)
3823     {
3824         sc = tempdecl->scope;
3825         sc = sc->push(argsym);
3826         sc = sc->push(this);
3827         for (int i = 0; i < members->dim; i++)
3828         {
3829             Dsymbol *s = (Dsymbol *)members->data[i];
3830             s->semantic3(sc);
3831         }
3832         sc = sc->pop();
3833         sc->pop();
3834     }
3835 }
3836
3837 void TemplateInstance::toObjFile(int multiobj)
3838 {
3839 #if LOG
3840     printf("TemplateInstance::toObjFile('%s', this = %p)\n", toChars(), this);
3841 #endif
3842     if (!errors && members)
3843     {
3844         if (multiobj)
3845             // Append to list of object files to be written later
3846             obj_append(this);
3847         else
3848         {
3849             for (int i = 0; i < members->dim; i++)
3850             {
3851                 Dsymbol *s = (Dsymbol *)members->data[i];
3852                 s->toObjFile(multiobj);
3853             }
3854         }
3855     }
3856 }
3857
3858 void TemplateInstance::inlineScan()
3859 {
3860 #if LOG
3861     printf("TemplateInstance::inlineScan('%s')\n", toChars());
3862 #endif
3863     if (!errors && members)
3864     {
3865         for (int i = 0; i < members->dim; i++)
3866         {
3867             Dsymbol *s = (Dsymbol *)members->data[i];
3868             s->inlineScan();
3869         }
3870     }
3871 }
3872
3873 void TemplateInstance::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
3874 {
3875     int i;
3876
3877     Identifier *id = name;
3878     buf->writestring(id->toChars());
3879     buf->writestring("!(");
3880     if (nest)
3881         buf->writestring("...");
3882     else
3883     {
3884         nest++;
3885         Objects *args = tiargs;
3886         for (i = 0; i < args->dim; i++)
3887         {
3888             if (i)
3889                 buf->writeByte(',');
3890             Object *oarg = (Object *)args->data[i];
3891             ObjectToCBuffer(buf, hgs, oarg);
3892         }
3893         nest--;
3894     }
3895     buf->writeByte(')');
3896 }
3897
3898
3899 Dsymbol *TemplateInstance::toAlias()
3900 {
3901 #if LOG
3902     printf("TemplateInstance::toAlias()\n");
3903 #endif
3904     if (!inst)
3905     {   error("cannot resolve forward reference");
3906         return this;
3907     }
3908
3909     if (inst != this)
3910         return inst->toAlias();
3911
3912     if (aliasdecl)
3913         return aliasdecl->toAlias();
3914
3915     return inst;
3916 }
3917
3918 AliasDeclaration *TemplateInstance::isAliasDeclaration()
3919 {
3920     return aliasdecl;
3921 }
3922
3923 char *TemplateInstance::kind()
3924 {
3925     return "template instance";
3926 }
3927
3928 int TemplateInstance::oneMember(Dsymbol **ps)
3929 {
3930     *ps = NULL;
3931     return TRUE;
3932 }
3933
3934 char *TemplateInstance::toChars()
3935 {
3936     OutBuffer buf;
3937     HdrGenState hgs;
3938     char *s;
3939
3940     toCBuffer(&buf, &hgs);
3941     s = buf.toChars();
3942     buf.data = NULL;
3943     return s;
3944 }
3945
3946 /* ======================== TemplateMixin ================================ */
3947
3948 TemplateMixin::TemplateMixin(Loc loc, Identifier *ident, Type *tqual,
3949         Array *idents, Objects *tiargs)
3950         : TemplateInstance(loc, (Identifier *)idents->data[idents->dim - 1])
3951 {
3952     //printf("TemplateMixin(ident = '%s')\n", ident ? ident->toChars() : "");
3953     this->ident = ident;
3954     this->tqual = tqual;
3955     this->idents = idents;
3956     this->tiargs = tiargs ? tiargs : new Objects();
3957     this->scope = NULL;
3958 }
3959
3960 Dsymbol *TemplateMixin::syntaxCopy(Dsymbol *s)
3961 {   TemplateMixin *tm;
3962
3963     Array *ids = new Array();
3964     ids->setDim(idents->dim);
3965     for (int i = 0; i < idents->dim; i++)
3966     {   // Matches TypeQualified::syntaxCopyHelper()
3967         Identifier *id = (Identifier *)idents->data[i];
3968         if (id->dyncast() == DYNCAST_DSYMBOL)
3969         {
3970             TemplateInstance *ti = (TemplateInstance *)id;
3971
3972             ti = (TemplateInstance *)ti->syntaxCopy(NULL);
3973             id = (Identifier *)ti;
3974         }
3975         ids->data[i] = id;
3976     }
3977
3978     tm = new TemplateMixin(loc, ident,
3979                 (Type *)(tqual ? tqual->syntaxCopy() : NULL),
3980                 ids, tiargs);
3981     TemplateInstance::syntaxCopy(tm);
3982     return tm;
3983 }
3984
3985 void TemplateMixin::semantic(Scope *sc)
3986 {
3987 #if LOG
3988     printf("+TemplateMixin::semantic('%s', this=%p)\n", toChars(), this);
3989     fflush(stdout);
3990 #endif
3991     if (semanticdone &&
3992         // This for when a class/struct contains mixin members, and
3993         // is done over because of forward references
3994         (!parent || !toParent()->isAggregateDeclaration()))
3995     {
3996 #if LOG
3997         printf("\tsemantic done\n");
3998 #endif
3999         return;
4000     }
4001     if (!semanticdone)
4002         semanticdone = 1;
4003 #if LOG
4004     printf("\tdo semantic\n");
4005 #endif
4006
4007     Scope *scx = NULL;
4008     if (scope)
4009     {   sc = scope;
4010         scx = scope;            // save so we don't make redundant copies
4011         scope = NULL;
4012     }
4013
4014     // Follow qualifications to find the TemplateDeclaration
4015     if (!tempdecl)
4016     {   Dsymbol *s;
4017         int i;
4018         Identifier *id;
4019
4020         if (tqual)
4021         {   s = tqual->toDsymbol(sc);
4022             i = 0;
4023         }
4024         else
4025         {
4026             i = 1;
4027             id = (Identifier *)idents->data[0];
4028             switch (id->dyncast())
4029             {
4030                 case DYNCAST_IDENTIFIER:
4031                     s = sc->search(loc, id, NULL);
4032                     break;
4033
4034                 case DYNCAST_DSYMBOL:
4035                 {
4036                     TemplateInstance *ti = (TemplateInstance *)id;
4037                     ti->semantic(sc);
4038                     s = ti;
4039                     break;
4040                 }
4041                 default:
4042                     assert(0);
4043             }
4044         }
4045
4046         for (; i < idents->dim; i++)
4047         {
4048             if (!s)
4049                 break;
4050             id = (Identifier *)idents->data[i];
4051             s = s->searchX(loc, sc, id);
4052         }
4053         if (!s)
4054         {
4055             error("is not defined");
4056             inst = this;
4057             return;
4058         }
4059         tempdecl = s->toAlias()->isTemplateDeclaration();
4060         if (!tempdecl)
4061         {
4062             error("%s isn't a template", s->toChars());
4063             inst = this;
4064             return;
4065         }
4066     }
4067
4068     // Look for forward reference
4069     assert(tempdecl);
4070     for (TemplateDeclaration *td = tempdecl; td; td = td->overnext)
4071     {
4072         if (!td->scope)
4073         {
4074             /* Cannot handle forward references if mixin is a struct member,
4075              * because addField must happen during struct's semantic, not
4076              * during the mixin semantic.
4077              * runDeferred will re-run mixin's semantic outside of the struct's
4078              * semantic.
4079              */
4080             semanticdone = 0;
4081             AggregateDeclaration *ad = toParent()->isAggregateDeclaration();
4082             if (ad)
4083                 ad->sizeok = 2;
4084             else
4085             {
4086                 // Forward reference
4087                 //printf("forward reference - deferring\n");
4088                 scope = scx ? scx : new Scope(*sc);
4089                 scope->setNoFree();
4090                 scope->module->addDeferredSemantic(this);
4091             }
4092             return;
4093         }
4094     }
4095
4096     // Run semantic on each argument, place results in tiargs[]
4097     semanticTiargs(sc);
4098
4099     tempdecl = findBestMatch(sc);
4100     if (!tempdecl)
4101     {   inst = this;
4102         return;         // error recovery
4103     }
4104
4105     if (!ident)
4106         ident = genIdent();
4107
4108     inst = this;
4109     parent = sc->parent;
4110
4111     /* Detect recursive mixin instantiations.
4112      */
4113     for (Dsymbol *s = parent; s; s = s->parent)
4114     {
4115         //printf("\ts = '%s'\n", s->toChars());
4116         TemplateMixin *tm = s->isTemplateMixin();
4117         if (!tm || tempdecl != tm->tempdecl)
4118             continue;
4119
4120         for (int i = 0; i < tiargs->dim; i++)
4121         {   Object *o = (Object *)tiargs->data[i];
4122             Type *ta = isType(o);
4123             Expression *ea = isExpression(o);
4124             Dsymbol *sa = isDsymbol(o);
4125             Object *tmo = (Object *)tm->tiargs->data[i];
4126             if (ta)
4127             {
4128                 Type *tmta = isType(tmo);
4129                 if (!tmta)
4130                     goto Lcontinue;
4131                 if (!ta->equals(tmta))
4132                     goto Lcontinue;
4133             }
4134             else if (ea)
4135             {   Expression *tme = isExpression(tmo);
4136                 if (!tme || !ea->equals(tme))
4137                     goto Lcontinue;
4138             }
4139             else if (sa)
4140             {
4141                 Dsymbol *tmsa = isDsymbol(tmo);
4142                 if (sa != tmsa)
4143                     goto Lcontinue;
4144             }
4145             else
4146                 assert(0);
4147         }
4148         error("recursive mixin instantiation");
4149         return;
4150
4151     Lcontinue:
4152         continue;
4153     }
4154
4155     // Copy the syntax trees from the TemplateDeclaration
4156     members = Dsymbol::arraySyntaxCopy(tempdecl->members);
4157     if (!members)
4158         return;
4159
4160     symtab = new DsymbolTable();
4161
4162     for (Scope *sce = sc; 1; sce = sce->enclosing)
4163     {
4164         ScopeDsymbol *sds = (ScopeDsymbol *)sce->scopesym;
4165         if (sds)
4166         {
4167             sds->importScope(this, PROTpublic);
4168             break;
4169         }
4170     }
4171
4172 #if LOG
4173     printf("\tcreate scope for template parameters '%s'\n", toChars());
4174 #endif
4175     Scope *scy = sc;
4176     scy = sc->push(this);
4177     scy->parent = this;
4178
4179     argsym = new ScopeDsymbol();
4180     argsym->parent = scy->parent;
4181     Scope *scope = scy->push(argsym);
4182
4183     unsigned errorsave = global.errors;
4184
4185     // Declare each template parameter as an alias for the argument type
4186     declareParameters(scope);
4187
4188     // Add members to enclosing scope, as well as this scope
4189     for (unsigned i = 0; i < members->dim; i++)
4190     {   Dsymbol *s;
4191
4192         s = (Dsymbol *)members->data[i];
4193         s->addMember(scope, this, i);
4194         //sc->insert(s);
4195         //printf("sc->parent = %p, sc->scopesym = %p\n", sc->parent, sc->scopesym);
4196         //printf("s->parent = %s\n", s->parent->toChars());
4197     }
4198
4199     // Do semantic() analysis on template instance members
4200 #if LOG
4201     printf("\tdo semantic() on template instance members '%s'\n", toChars());
4202 #endif
4203     Scope *sc2;
4204     sc2 = scope->push(this);
4205     sc2->offset = sc->offset;
4206     for (int i = 0; i < members->dim; i++)
4207     {
4208         Dsymbol *s = (Dsymbol *)members->data[i];
4209         s->semantic(sc2);
4210     }
4211     sc->offset = sc2->offset;
4212
4213     /* The problem is when to parse the initializer for a variable.
4214      * Perhaps VarDeclaration::semantic() should do it like it does
4215      * for initializers inside a function.
4216      */
4217 //    if (sc->parent->isFuncDeclaration())
4218
4219         semantic2(sc2);
4220
4221     if (sc->func)
4222     {
4223         semantic3(sc2);
4224     }
4225
4226     // Give additional context info if error occurred during instantiation
4227     if (global.errors != errorsave)
4228     {
4229         error("error instantiating");
4230     }
4231
4232     sc2->pop();
4233
4234     scope->pop();
4235
4236 //    if (!isAnonymous())
4237     {
4238         scy->pop();
4239     }
4240 #if LOG
4241     printf("-TemplateMixin::semantic('%s', this=%p)\n", toChars(), this);
4242 #endif
4243 }
4244
4245 void TemplateMixin::semantic2(Scope *sc)
4246 {   int i;
4247
4248     if (semanticdone >= 2)
4249         return;
4250     semanticdone = 2;
4251 #if LOG
4252     printf("+TemplateMixin::semantic2('%s')\n", toChars());
4253 #endif
4254     if (members)
4255     {
4256         assert(sc);
4257         sc = sc->push(argsym);
4258         sc = sc->push(this);
4259         for (i = 0; i < members->dim; i++)
4260         {
4261             Dsymbol *s = (Dsymbol *)members->data[i];
4262 #if LOG
4263             printf("\tmember '%s', kind = '%s'\n", s->toChars(), s->kind());
4264 #endif
4265             s->semantic2(sc);
4266         }
4267         sc = sc->pop();
4268         sc->pop();
4269     }
4270 #if LOG
4271     printf("-TemplateMixin::semantic2('%s')\n", toChars());
4272 #endif
4273 }
4274
4275 void TemplateMixin::semantic3(Scope *sc)
4276 {   int i;
4277
4278     if (semanticdone >= 3)
4279         return;
4280     semanticdone = 3;
4281 #if LOG
4282     printf("TemplateMixin::semantic3('%s')\n", toChars());
4283 #endif
4284     if (members)
4285     {
4286         sc = sc->push(argsym);
4287         sc = sc->push(this);
4288         for (i = 0; i < members->dim; i++)
4289         {
4290             Dsymbol *s = (Dsymbol *)members->data[i];
4291             s->semantic3(sc);
4292         }
4293         sc = sc->pop();
4294         sc->pop();
4295     }
4296 }
4297
4298 void TemplateMixin::inlineScan()
4299 {
4300     TemplateInstance::inlineScan();
4301 }
4302
4303 char *TemplateMixin::kind()
4304 {
4305     return "mixin";
4306 }
4307
4308 int TemplateMixin::oneMember(Dsymbol **ps)
4309 {
4310     return Dsymbol::oneMember(ps);
4311 }
4312
4313 int TemplateMixin::hasPointers()
4314 {
4315     //printf("TemplateMixin::hasPointers() %s\n", toChars());
4316     for (size_t i = 0; i < members->dim; i++)
4317     {
4318         Dsymbol *s = (Dsymbol *)members->data[i];
4319         //printf(" s = %s %s\n", s->kind(), s->toChars());
4320         if (s->hasPointers())
4321         {
4322             return 1;
4323         }
4324     }
4325     return 0;
4326 }
4327
4328 char *TemplateMixin::toChars()
4329 {
4330     OutBuffer buf;
4331     HdrGenState hgs;
4332     char *s;
4333
4334     TemplateInstance::toCBuffer(&buf, &hgs);
4335     s = buf.toChars();
4336     buf.data = NULL;
4337     return s;
4338 }
4339
4340 void TemplateMixin::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
4341 {
4342     buf->writestring("mixin ");
4343     int i;
4344     for (i = 0; i < idents->dim; i++)
4345     {   Identifier *id = (Identifier *)idents->data[i];
4346
4347         if (i)
4348             buf->writeByte('.');
4349         buf->writestring(id->toChars());
4350     }
4351     buf->writestring("!(");
4352     if (tiargs)
4353     {
4354         for (i = 0; i < tiargs->dim; i++)
4355         {   if (i)
4356                 buf->writebyte(',');
4357             Object *oarg = (Object *)tiargs->data[i];
4358             Type *t = isType(oarg);
4359             Expression *e = isExpression(oarg);
4360             Dsymbol *s = isDsymbol(oarg);
4361             if (t)
4362                 t->toCBuffer(buf, NULL, hgs);
4363             else if (e)
4364                 e->toCBuffer(buf, hgs);
4365             else if (s)
4366             {
4367                 char *p = s->ident ? s->ident->toChars() : s->toChars();
4368                 buf->writestring(p);
4369             }
4370             else if (!oarg)
4371             {
4372                 buf->writestring("NULL");
4373             }
4374             else
4375             {
4376                 assert(0);
4377             }
4378         }
4379     }
4380     buf->writebyte(')');
4381     buf->writebyte(';');
4382     buf->writenl();
4383 }
4384
4385
4386 void TemplateMixin::toObjFile(int multiobj)
4387 {
4388     //printf("TemplateMixin::toObjFile('%s')\n", toChars());
4389     TemplateInstance::toObjFile(multiobj);
4390 }
4391