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, bool dltSource)
 265     : ScopeDsymbol(id), dltSource(dltSource)
 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, dltSource);
 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 (tparam->ty == Tmaybe)
1328         tparam = tparam->nextOf();
1329     if (this->ty == Tmaybe)
1330         return nextOf()->deduceType(sc, tparam, parameters, dedtypes);
1331
1332     if (this == tparam)
1333         goto Lexact;
1334
1335     if (tparam->ty == Tident)
1336     {
1337         // Determine which parameter tparam is
1338         int i = templateParameterLookup(tparam, parameters);
1339         if (i == -1)
1340         {
1341             if (!sc)
1342                 goto Lnomatch;
1343             /* BUG: what if tparam is a template instance, that
1344              * has as an argument another Tident?
1345              */
1346             tparam = tparam->semantic(0, sc);
1347             assert(tparam->ty != Tident);
1348             return deduceType(sc, tparam, parameters, dedtypes);
1349         }
1350
1351         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1352
1353         // Found the corresponding parameter tp
1354         if (!tp->isTemplateTypeParameter())
1355             goto Lnomatch;
1356         Type *at = (Type *)dedtypes->data[i];
1357         if (!at)
1358         {   // 3*3 == 9 cases
1359             if (tparam->isMutable())
1360             {   // foo(U:U) T            => T
1361                 // foo(U:U) const(T)     => const(T)
1362                 // foo(U:U) invariant(T) => invariant(T)
1363                 dedtypes->data[i] = (void *)this;
1364                 goto Lexact;
1365             }
1366             else if (mod == tparam->mod)
1367             {   // foo(U:const(U))     const(T)     => T
1368                 // foo(U:invariant(U)) invariant(T) => T
1369                 dedtypes->data[i] = (void *)mutableOf();
1370                 goto Lexact;
1371             }
1372             else if (tparam->isConst())
1373             {   // foo(U:const(U)) T            => T
1374                 // foo(U:const(U)) invariant(T) => T
1375                 dedtypes->data[i] = (void *)mutableOf();
1376                 goto Lconst;
1377             }
1378             else
1379             {   // foo(U:invariant(U)) T        => nomatch
1380                 // foo(U:invariant(U)) const(T) => nomatch
1381                 goto Lnomatch;
1382             }
1383         }
1384         if (equals(at))
1385             goto Lexact;
1386         else if (ty == Tclass && at->ty == Tclass)
1387         {
1388             return implicitConvTo(at);
1389         }
1390         else if (ty == Tsarray && at->ty == Tarray &&
1391             nextOf()->implicitConvTo(at->nextOf()) >= MATCHconst)
1392         {
1393             goto Lexact;
1394         }
1395         else
1396             goto Lnomatch;
1397     }
1398
1399     if (ty != tparam->ty)
1400         goto Lnomatch;
1401
1402     if (nextOf())
1403         return nextOf()->deduceType(sc, tparam->nextOf(), parameters, dedtypes);
1404
1405 Lexact:
1406     return MATCHexact;
1407
1408 Lnomatch:
1409     return MATCHnomatch;
1410
1411 Lconst:
1412     return MATCHconst;
1413 }
1414
1415 MATCH TypeSArray::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters,
1416         Objects *dedtypes)
1417 {
1418 #if 0
1419     printf("TypeSArray::deduceType()\n");
1420     printf("\tthis   = %d, ", ty); print();
1421     printf("\ttparam = %d, ", tparam->ty); tparam->print();
1422 #endif
1423
1424     // Extra check that array dimensions must match
1425     if (tparam)
1426     {
1427         if (tparam->ty == Tsarray)
1428         {
1429             TypeSArray *tp = (TypeSArray *)tparam;
1430
1431             if (tp->dim->op == TOKvar &&
1432                 ((VarExp *)tp->dim)->var->storage_class & STCtemplateparameter)
1433             {   int i = templateIdentifierLookup(((VarExp *)tp->dim)->var->ident, parameters);
1434                 // This code matches code in TypeInstance::deduceType()
1435                 if (i == -1)
1436                     goto Lnomatch;
1437                 TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1438                 TemplateValueParameter *tvp = tp->isTemplateValueParameter();
1439                 if (!tvp)
1440                     goto Lnomatch;
1441                 Expression *e = (Expression *)dedtypes->data[i];
1442                 if (e)
1443                 {
1444                     if (!dim->equals(e))
1445                         goto Lnomatch;
1446                 }
1447                 else
1448                 {   Type *vt = tvp->valType->semantic(0, sc);
1449                     MATCH m = (MATCH)dim->implicitConvTo(vt);
1450                     if (!m)
1451                         goto Lnomatch;
1452                     dedtypes->data[i] = dim;
1453                 }
1454             }
1455             else if (dim->toInteger() != tp->dim->toInteger())
1456                 return MATCHnomatch;
1457         }
1458         else if (tparam->ty == Taarray)
1459         {
1460             TypeAArray *tp = (TypeAArray *)tparam;
1461             if (tp->index->ty == Tident)
1462             {   TypeIdentifier *tident = (TypeIdentifier *)tp->index;
1463
1464                 if (tident->idents.dim == 0)
1465                 {   Identifier *id = tident->ident;
1466
1467                     for (size_t i = 0; i < parameters->dim; i++)
1468                     {
1469                         TemplateParameter *tp = (TemplateParameter *)parameters->data[i];
1470
1471                         if (tp->ident->equals(id))
1472                         {   // Found the corresponding template parameter
1473                             TemplateValueParameter *tvp = tp->isTemplateValueParameter();
1474                             if (!tvp || !tvp->valType->isintegral())
1475                                 goto Lnomatch;
1476
1477                             if (dedtypes->data[i])
1478                             {
1479                                 if (!dim->equals((Object *)dedtypes->data[i]))
1480                                     goto Lnomatch;
1481                             }
1482                             else
1483                             {   dedtypes->data[i] = (void *)dim;
1484                             }
1485                             return next->deduceType(sc, tparam->nextOf(), parameters, dedtypes);
1486                         }
1487                     }
1488                 }
1489             }
1490         }
1491         else if (tparam->ty == Tarray)
1492         {   MATCH m;
1493
1494             m = next->deduceType(sc, tparam->nextOf(), parameters, dedtypes);
1495             if (m == MATCHexact)
1496                 m = MATCHconvert;
1497             return m;
1498         }
1499     }
1500     return Type::deduceType(sc, tparam, parameters, dedtypes);
1501
1502   Lnomatch:
1503     return MATCHnomatch;
1504 }
1505
1506 MATCH TypeAArray::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1507 {
1508 #if 0
1509     printf("TypeAArray::deduceType()\n");
1510     printf("\tthis   = %d, ", ty); print();
1511     printf("\ttparam = %d, ", tparam->ty); tparam->print();
1512 #endif
1513
1514     // Extra check that index type must match
1515     if (tparam && tparam->ty == Taarray)
1516     {
1517         TypeAArray *tp = (TypeAArray *)tparam;
1518         if (!index->deduceType(sc, tp->index, parameters, dedtypes))
1519         {
1520             return MATCHnomatch;
1521         }
1522     }
1523     return Type::deduceType(sc, tparam, parameters, dedtypes);
1524 }
1525
1526 MATCH TypeFunction::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1527 {
1528     //printf("TypeFunction::deduceType()\n");
1529     //printf("\tthis   = %d, ", ty); print();
1530     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1531
1532     // Extra check that function characteristics must match
1533     if (tparam && tparam->ty == Tfunction)
1534     {
1535         TypeFunction *tp = (TypeFunction *)tparam;
1536         if (varargs != tp->varargs ||
1537             linkage != tp->linkage)
1538             return MATCHnomatch;
1539
1540         size_t nfargs = Argument::dim(this->parameters);
1541         size_t nfparams = Argument::dim(tp->parameters);
1542
1543         /* See if tuple match
1544          */
1545         if (nfparams > 0 && nfargs >= nfparams - 1)
1546         {
1547             /* See if 'A' of the template parameter matches 'A'
1548              * of the type of the last function parameter.
1549              */
1550             Argument *fparam = (Argument *)tp->parameters->data[nfparams - 1];
1551             if (fparam->type->ty != Tident)
1552                 goto L1;
1553             TypeIdentifier *tid = (TypeIdentifier *)fparam->type;
1554             if (tid->idents.dim)
1555                 goto L1;
1556
1557             /* Look through parameters to find tuple matching tid->ident
1558              */
1559             size_t tupi = 0;
1560             for (; 1; tupi++)
1561             {   if (tupi == parameters->dim)
1562                     goto L1;
1563                 TemplateParameter *t = (TemplateParameter *)parameters->data[tupi];
1564                 TemplateTupleParameter *tup = t->isTemplateTupleParameter();
1565                 if (tup && tup->ident->equals(tid->ident))
1566                     break;
1567             }
1568
1569             /* The types of the function arguments [nfparams - 1 .. nfargs]
1570              * now form the tuple argument.
1571              */
1572             int tuple_dim = nfargs - (nfparams - 1);
1573
1574             /* See if existing tuple, and whether it matches or not
1575              */
1576             Object *o = (Object *)dedtypes->data[tupi];
1577             if (o)
1578             {   // Existing deduced argument must be a tuple, and must match
1579                 Tuple *t = isTuple(o);
1580                 if (!t || t->objects.dim != tuple_dim)
1581                     return MATCHnomatch;
1582                 for (size_t i = 0; i < tuple_dim; i++)
1583                 {   Argument *arg = Argument::getNth(this->parameters, nfparams - 1 + i);
1584                     if (!arg->type->equals((Object *)t->objects.data[i]))
1585                         return MATCHnomatch;
1586                 }
1587             }
1588             else
1589             {   // Create new tuple
1590                 Tuple *t = new Tuple();
1591                 t->objects.setDim(tuple_dim);
1592                 for (size_t i = 0; i < tuple_dim; i++)
1593                 {   Argument *arg = Argument::getNth(this->parameters, nfparams - 1 + i);
1594                     t->objects.data[i] = (void *)arg->type;
1595                 }
1596                 dedtypes->data[tupi] = (void *)t;
1597             }
1598             nfparams--; // don't consider the last parameter for type deduction
1599             goto L2;
1600         }
1601
1602     L1:
1603         if (nfargs != nfparams)
1604             return MATCHnomatch;
1605     L2:
1606         for (size_t i = 0; i < nfparams; i++)
1607         {
1608             Argument *a = Argument::getNth(this->parameters, i);
1609             Argument *ap = Argument::getNth(tp->parameters, i);
1610             if (a->storageClass != ap->storageClass ||
1611                 !a->type->deduceType(sc, ap->type, parameters, dedtypes))
1612                 return MATCHnomatch;
1613         }
1614     }
1615     return Type::deduceType(sc, tparam, parameters, dedtypes);
1616 }
1617
1618 MATCH TypeIdentifier::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1619 {
1620     // Extra check
1621     if (tparam && tparam->ty == Tident)
1622     {
1623         TypeIdentifier *tp = (TypeIdentifier *)tparam;
1624
1625         for (int i = 0; i < idents.dim; i++)
1626         {
1627             Identifier *id1 = (Identifier *)idents.data[i];
1628             Identifier *id2 = (Identifier *)tp->idents.data[i];
1629
1630             if (!id1->equals(id2))
1631                 return MATCHnomatch;
1632         }
1633     }
1634     return Type::deduceType(sc, tparam, parameters, dedtypes);
1635 }
1636
1637 MATCH TypeInstance::deduceType(Scope *sc,
1638         Type *tparam, TemplateParameters *parameters,
1639         Objects *dedtypes)
1640 {
1641     //printf("TypeInstance::deduceType(tparam = %s) %s\n", tparam->toChars(), toChars());
1642     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1643
1644     // Extra check
1645     if (tparam && tparam->ty == Tinstance)
1646     {
1647         TypeInstance *tp = (TypeInstance *)tparam;
1648
1649         //printf("tempinst->tempdecl = %p\n", tempinst->tempdecl);
1650         //printf("tp->tempinst->tempdecl = %p\n", tp->tempinst->tempdecl);
1651         if (!tp->tempinst->tempdecl)
1652         {   //printf("tp->tempinst->name = '%s'\n", tp->tempinst->name->toChars());
1653             if (!tp->tempinst->name->equals(tempinst->name))
1654             {
1655                 /* Handle case of:
1656                  *  template Foo(T : sa!(T), alias sa)
1657                  */
1658                 int i = templateIdentifierLookup(tp->tempinst->name, parameters);
1659                 if (i == -1)
1660                 {   /* Didn't find it as a parameter identifier. Try looking
1661                      * it up and seeing if is an alias. See Bugzilla 1454
1662                      */
1663                     Dsymbol *s = tempinst->tempdecl->scope->search(0, tp->tempinst->name, NULL);
1664                     if (s)
1665                     {
1666                         s = s->toAlias();
1667                         TemplateDeclaration *td = s->isTemplateDeclaration();
1668                         if (td && td == tempinst->tempdecl)
1669                             goto L2;
1670                     }
1671                     goto Lnomatch;
1672                 }
1673                 TemplateParameter *tpx = (TemplateParameter *)parameters->data[i];
1674                 // This logic duplicates tpx->matchArg()
1675                 TemplateAliasParameter *ta = tpx->isTemplateAliasParameter();
1676                 if (!ta)
1677                     goto Lnomatch;
1678                 Dsymbol *sa = tempinst->tempdecl;
1679                 if (!sa)
1680                     goto Lnomatch;
1681                 if (ta->specAlias && sa != ta->specAlias)
1682                     goto Lnomatch;
1683                 if (dedtypes->data[i])
1684                 {   // Must match already deduced symbol
1685                     Dsymbol *s = (Dsymbol *)dedtypes->data[i];
1686
1687                     if (s != sa)
1688                         goto Lnomatch;
1689                 }
1690                 dedtypes->data[i] = sa;
1691             }
1692         }
1693         else if (tempinst->tempdecl != tp->tempinst->tempdecl)
1694             goto Lnomatch;
1695
1696       L2:
1697         if (tempinst->tiargs->dim != tp->tempinst->tiargs->dim)
1698             goto Lnomatch;
1699
1700         for (int i = 0; i < tempinst->tiargs->dim; i++)
1701         {
1702             //printf("\ttest: tempinst->tiargs[%d]\n", i);
1703             int j;
1704             Object *o1 = (Object *)tempinst->tiargs->data[i];
1705             Object *o2 = (Object *)tp->tempinst->tiargs->data[i];
1706
1707             Type *t1 = isType(o1);
1708             Type *t2 = isType(o2);
1709
1710             Expression *e1 = isExpression(o1);
1711             Expression *e2 = isExpression(o2);
1712
1713 #if 0
1714             if (t1)     printf("t1 = %s\n", t1->toChars());
1715             if (t2)     printf("t2 = %s\n", t2->toChars());
1716             if (e1)     printf("e1 = %s\n", e1->toChars());
1717             if (e2)     printf("e2 = %s\n", e2->toChars());
1718 #endif
1719
1720             if (t1 && t2)
1721             {
1722                 if (!t1->deduceType(sc, t2, parameters, dedtypes))
1723                     goto Lnomatch;
1724             }
1725             else if (e1 && e2)
1726             {
1727                 if (!e1->equals(e2))
1728                 {   if (e2->op == TOKvar)
1729                     {
1730                         /*
1731                          * (T:Number!(e2), int e2)
1732                          */
1733                         j = templateIdentifierLookup(((VarExp *)e2)->var->ident, parameters);
1734                         goto L1;
1735                     }
1736                     goto Lnomatch;
1737                 }
1738             }
1739             else if (e1 && t2 && t2->ty == Tident)
1740             {
1741                 j = templateParameterLookup(t2, parameters);
1742             L1:
1743                 if (j == -1)
1744                     goto Lnomatch;
1745                 TemplateParameter *tp = (TemplateParameter *)parameters->data[j];
1746                 // BUG: use tp->matchArg() instead of the following
1747                 TemplateValueParameter *tv = tp->isTemplateValueParameter();
1748                 if (!tv)
1749                     goto Lnomatch;
1750                 Expression *e = (Expression *)dedtypes->data[j];
1751                 if (e)
1752                 {
1753                     if (!e1->equals(e))
1754                         goto Lnomatch;
1755                 }
1756                 else
1757                 {   Type *vt = tv->valType->semantic(0, sc);
1758                     MATCH m = (MATCH)e1->implicitConvTo(vt);
1759                     if (!m)
1760                         goto Lnomatch;
1761                     dedtypes->data[j] = e1;
1762                 }
1763             }
1764             // BUG: Need to handle alias and tuple parameters
1765             else
1766                 goto Lnomatch;
1767         }
1768     }
1769     return Type::deduceType(sc, tparam, parameters, dedtypes);
1770
1771 Lnomatch:
1772     return MATCHnomatch;
1773 }
1774
1775 MATCH TypeStruct::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1776 {
1777     //printf("TypeStruct::deduceType()\n");
1778     //printf("\tthis->parent   = %s, ", sym->parent->toChars()); print();
1779     //printf("\ttparam = %d, ", tparam->ty); tparam->print();
1780
1781     /* If this struct is a template struct, and we're matching
1782      * it against a template instance, convert the struct type
1783      * to a template instance, too, and try again.
1784      */
1785     TemplateInstance *ti = sym->parent->isTemplateInstance();
1786
1787     if (tparam && tparam->ty == Tinstance)
1788     {
1789         if (ti && ti->toAlias() == sym)
1790         {
1791             TypeInstance *t = new TypeInstance(0, ti);
1792             return t->deduceType(sc, tparam, parameters, dedtypes);
1793         }
1794
1795         /* Match things like:
1796          *  S!(T).foo
1797          */
1798         TypeInstance *tpi = (TypeInstance *)tparam;
1799         if (tpi->idents.dim)
1800         {   Identifier *id = (Identifier *)tpi->idents.data[tpi->idents.dim - 1];
1801             if (id->dyncast() == DYNCAST_IDENTIFIER && sym->ident->equals(id))
1802             {
1803                 Type *tparent = sym->parent->getType();
1804                 if (tparent)
1805                 {
1806                     /* Slice off the .foo in S!(T).foo
1807                      */
1808                     tpi->idents.dim--;
1809                     MATCH m = tparent->deduceType(sc, tpi, parameters, dedtypes);
1810                     tpi->idents.dim++;
1811                     return m;
1812                 }
1813             }
1814         }
1815     }
1816
1817     // Extra check
1818     if (tparam && tparam->ty == Tstruct)
1819     {
1820         TypeStruct *tp = (TypeStruct *)tparam;
1821
1822         if (sym != tp->sym)
1823             return MATCHnomatch;
1824     }
1825     return Type::deduceType(sc, tparam, parameters, dedtypes);
1826 }
1827
1828 MATCH TypeEnum::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1829 {
1830     // Extra check
1831     if (tparam && tparam->ty == Tenum)
1832     {
1833         TypeEnum *tp = (TypeEnum *)tparam;
1834
1835         if (sym != tp->sym)
1836             return MATCHnomatch;
1837     }
1838     return Type::deduceType(sc, tparam, parameters, dedtypes);
1839 }
1840
1841 MATCH TypeTypedef::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1842 {
1843     // Extra check
1844     if (tparam && tparam->ty == Ttypedef)
1845     {
1846         TypeTypedef *tp = (TypeTypedef *)tparam;
1847
1848         if (sym != tp->sym)
1849             return MATCHnomatch;
1850     }
1851     return Type::deduceType(sc, tparam, parameters, dedtypes);
1852 }
1853
1854 MATCH TypeClass::deduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes)
1855 {
1856     //printf("TypeClass::deduceType(this = %s)\n", toChars());
1857
1858     /* If this class is a template class, and we're matching
1859      * it against a template instance, convert the class type
1860      * to a template instance, too, and try again.
1861      */
1862     TemplateInstance *ti = sym->parent->isTemplateInstance();
1863
1864     if (tparam && tparam->ty == Tinstance)
1865     {
1866         if (ti && ti->toAlias() == sym)
1867         {
1868             TypeInstance *t = new TypeInstance(0, ti);
1869             return t->deduceType(sc, tparam, parameters, dedtypes);
1870         }
1871
1872         /* Match things like:
1873          *  S!(T).foo
1874          */
1875         TypeInstance *tpi = (TypeInstance *)tparam;
1876         if (tpi->idents.dim)
1877         {   Identifier *id = (Identifier *)tpi->idents.data[tpi->idents.dim - 1];
1878             if (id->dyncast() == DYNCAST_IDENTIFIER && sym->ident->equals(id))
1879             {
1880                 Type *tparent = sym->parent->getType();
1881                 if (tparent)
1882                 {
1883                     /* Slice off the .foo in S!(T).foo
1884                      */
1885                     tpi->idents.dim--;
1886                     MATCH m = tparent->deduceType(sc, tpi, parameters, dedtypes);
1887                     tpi->idents.dim++;
1888                     return m;
1889                 }
1890             }
1891         }
1892     }
1893
1894     // Extra check
1895     if (tparam && tparam->ty == Tclass)
1896     {
1897         TypeClass *tp = (TypeClass *)tparam;
1898
1899         //printf("\t%d\n", (MATCH) implicitConvTo(tp));
1900         return implicitConvTo(tp);
1901     }
1902     return Type::deduceType(sc, tparam, parameters, dedtypes);
1903 }
1904
1905 /* ======================== TemplateParameter =============================== */
1906
1907 TemplateParameter::TemplateParameter(Loc loc, Identifier *ident)
1908 {
1909     this->loc = loc;
1910     this->ident = ident;
1911     this->sparam = NULL;
1912 }
1913
1914 TemplateTypeParameter  *TemplateParameter::isTemplateTypeParameter()
1915 {
1916     return NULL;
1917 }
1918
1919 TemplateValueParameter *TemplateParameter::isTemplateValueParameter()
1920 {
1921     return NULL;
1922 }
1923
1924 TemplateAliasParameter *TemplateParameter::isTemplateAliasParameter()
1925 {
1926     return NULL;
1927 }
1928
1929 TemplateTupleParameter *TemplateParameter::isTemplateTupleParameter()
1930 {
1931     return NULL;
1932 }
1933
1934 #if V2
1935 TemplateThisParameter  *TemplateParameter::isTemplateThisParameter()
1936 {
1937     return NULL;
1938 }
1939 #endif
1940
1941 /* ======================== TemplateTypeParameter =========================== */
1942
1943 // type-parameter
1944
1945 TemplateTypeParameter::TemplateTypeParameter(Loc loc, Identifier *ident, Type *specType,
1946         Type *defaultType)
1947     : TemplateParameter(loc, ident)
1948 {
1949     this->ident = ident;
1950     this->specType = specType;
1951     this->defaultType = defaultType;
1952 }
1953
1954 TemplateTypeParameter  *TemplateTypeParameter::isTemplateTypeParameter()
1955 {
1956     return this;
1957 }
1958
1959 TemplateParameter *TemplateTypeParameter::syntaxCopy()
1960 {
1961     TemplateTypeParameter *tp = new TemplateTypeParameter(loc, ident, specType, defaultType);
1962     if (tp->specType)
1963         tp->specType = specType->syntaxCopy();
1964     if (defaultType)
1965         tp->defaultType = defaultType->syntaxCopy();
1966     return tp;
1967 }
1968
1969 void TemplateTypeParameter::declareParameter(Scope *sc)
1970 {
1971     //printf("TemplateTypeParameter::declareParameter('%s')\n", ident->toChars());
1972     TypeIdentifier *ti = new TypeIdentifier(loc, ident);
1973     sparam = new AliasDeclaration(loc, ident, ti);
1974     if (!sc->insert(sparam))
1975         error(loc, "parameter '%s' multiply defined", ident->toChars());
1976 }
1977
1978 void TemplateTypeParameter::semantic(Scope *sc)
1979 {
1980     //printf("TemplateTypeParameter::semantic('%s')\n", ident->toChars());
1981     if (specType)
1982     {
1983         specType = specType->semantic(loc, sc);
1984     }
1985 #if 0 // Don't do semantic() until instantiation
1986     if (defaultType)
1987     {
1988         defaultType = defaultType->semantic(loc, sc);
1989     }
1990 #endif
1991 }
1992
1993 /****************************************
1994  * Determine if two TemplateParameters are the same
1995  * as far as TemplateDeclaration overloading goes.
1996  * Returns:
1997  *      1       match
1998  *      0       no match
1999  */
2000
2001 int TemplateTypeParameter::overloadMatch(TemplateParameter *tp)
2002 {
2003     TemplateTypeParameter *ttp = tp->isTemplateTypeParameter();
2004
2005     if (ttp)
2006     {
2007         if (specType != ttp->specType)
2008             goto Lnomatch;
2009
2010         if (specType && !specType->equals(ttp->specType))
2011             goto Lnomatch;
2012
2013         return 1;                       // match
2014     }
2015
2016 Lnomatch:
2017     return 0;
2018 }
2019
2020 /*******************************************
2021  * Match to a particular TemplateParameter.
2022  * Input:
2023  *      i               i'th argument
2024  *      tiargs[]        actual arguments to template instance
2025  *      parameters[]    template parameters
2026  *      dedtypes[]      deduced arguments to template instance
2027  *      *psparam        set to symbol declared and initialized to dedtypes[i]
2028  *      flags           1: don't do 'toHeadMutable()'
2029  */
2030
2031 MATCH TemplateTypeParameter::matchArg(Scope *sc, Objects *tiargs,
2032         int i, TemplateParameters *parameters, Objects *dedtypes,
2033         Declaration **psparam, int flags)
2034 {
2035     //printf("TemplateTypeParameter::matchArg()\n");
2036     Type *t;
2037     Object *oarg;
2038     MATCH m = MATCHexact;
2039     Type *ta;
2040
2041     if (i < tiargs->dim)
2042         oarg = (Object *)tiargs->data[i];
2043     else
2044     {   // Get default argument instead
2045         oarg = defaultArg(loc, sc);
2046         if (!oarg)
2047         {   assert(i < dedtypes->dim);
2048             // It might have already been deduced
2049             oarg = (Object *)dedtypes->data[i];
2050             if (!oarg)
2051             {
2052                 goto Lnomatch;
2053             }
2054             flags |= 1;         // already deduced, so don't to toHeadMutable()
2055         }
2056     }
2057
2058     ta = isType(oarg);
2059     if (!ta)
2060     {
2061         //printf("test1 %s %p %p %p\n", oarg->toChars(), isExpression(oarg), isDsymbol(oarg), isTuple(oarg));
2062         goto Lnomatch;
2063     }
2064     //printf("ta is %s\n", ta->toChars());
2065
2066     t = (Type *)dedtypes->data[i];
2067
2068     if (specType)
2069     {
2070         //printf("\tcalling deduceType(): ta is %s, specType is %s\n", ta->toChars(), specType->toChars());
2071         MATCH m2 = ta->deduceType(sc, specType, parameters, dedtypes);
2072         if (m2 == MATCHnomatch)
2073         {   //printf("\tfailed deduceType\n");
2074             goto Lnomatch;
2075         }
2076
2077         if (m2 < m)
2078             m = m2;
2079         t = (Type *)dedtypes->data[i];
2080     }
2081     else
2082     {
2083         // So that matches with specializations are better
2084         m = MATCHconvert;
2085
2086         /* This is so that:
2087          *   template Foo(T), Foo!(const int), => ta == int
2088          */
2089 //      if (!(flags & 1))
2090 //          ta = ta->toHeadMutable();
2091
2092         if (t)
2093         {   // Must match already deduced type
2094
2095             m = MATCHexact;
2096             if (!t->equals(ta))
2097             {   //printf("t = %s ta = %s\n", t->toChars(), ta->toChars());
2098                 goto Lnomatch;
2099             }
2100         }
2101     }
2102
2103     if (!t)
2104     {
2105         dedtypes->data[i] = ta;
2106         t = ta;
2107     }
2108     *psparam = new AliasDeclaration(loc, ident, t);
2109     //printf("\tm = %d\n", m);
2110     return m;
2111
2112 Lnomatch:
2113     *psparam = NULL;
2114     //printf("\tm = %d\n", MATCHnomatch);
2115     return MATCHnomatch;
2116 }
2117
2118
2119 void TemplateTypeParameter::print(Object *oarg, Object *oded)
2120 {
2121     fprintf(stderr, " %s\n", ident->toChars());
2122
2123     Type *t  = isType(oarg);
2124     Type *ta = isType(oded);
2125
2126     assert(ta);
2127
2128     if (specType)
2129         fprintf(stderr, "\tSpecialization: %s\n", specType->toChars());
2130     if (defaultType)
2131         fprintf(stderr, "\tDefault:        %s\n", defaultType->toChars());
2132     fprintf(stderr, "\tArgument:       %s\n", t ? t->toChars() : "NULL");
2133     fprintf(stderr, "\tDeduced Type:   %s\n", ta->toChars());
2134 }
2135
2136
2137 void TemplateTypeParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2138 {
2139     buf->writestring(ident->toChars());
2140     if (specType)
2141     {
2142         buf->writestring(" : ");
2143         specType->toCBuffer(buf, NULL, hgs);
2144     }
2145     if (defaultType)
2146     {
2147         buf->writestring(" = ");
2148         defaultType->toCBuffer(buf, NULL, hgs);
2149     }
2150 }
2151
2152
2153 void *TemplateTypeParameter::dummyArg()
2154 {   Type *t;
2155
2156     if (specType)
2157         t = specType;
2158     else
2159     {   // Use this for alias-parameter's too (?)
2160         t = new TypeIdentifier(loc, ident);
2161     }
2162     return (void *)t;
2163 }
2164
2165
2166 Object *TemplateTypeParameter::specialization()
2167 {
2168     return specType;
2169 }
2170
2171
2172 Object *TemplateTypeParameter::defaultArg(Loc loc, Scope *sc)
2173 {
2174     Type *t;
2175
2176     t = defaultType;
2177     if (t)
2178     {
2179         t = t->syntaxCopy();
2180         t = t->semantic(loc, sc);
2181     }
2182     return t;
2183 }
2184
2185 /* ======================== TemplateThisParameter =========================== */
2186
2187 #if V2
2188 // this-parameter
2189
2190 TemplateThisParameter::TemplateThisParameter(Loc loc, Identifier *ident,
2191         Type *specType,
2192         Type *defaultType)
2193     : TemplateTypeParameter(loc, ident, specType, defaultType)
2194 {
2195 }
2196
2197 TemplateThisParameter  *TemplateThisParameter::isTemplateThisParameter()
2198 {
2199     return this;
2200 }
2201
2202 TemplateParameter *TemplateThisParameter::syntaxCopy()
2203 {
2204     TemplateThisParameter *tp = new TemplateThisParameter(loc, ident, specType, defaultType);
2205     if (tp->specType)
2206         tp->specType = specType->syntaxCopy();
2207     if (defaultType)
2208         tp->defaultType = defaultType->syntaxCopy();
2209     return tp;
2210 }
2211
2212 void TemplateThisParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2213 {
2214     buf->writestring("this ");
2215     TemplateTypeParameter::toCBuffer(buf, hgs);
2216 }
2217 #endif
2218
2219 /* ======================== TemplateAliasParameter ========================== */
2220
2221 // alias-parameter
2222
2223 Dsymbol *TemplateAliasParameter::sdummy = NULL;
2224
2225 TemplateAliasParameter::TemplateAliasParameter(Loc loc, Identifier *ident, Type *specAliasT, Type *defaultAlias)
2226     : TemplateParameter(loc, ident)
2227 {
2228     this->ident = ident;
2229     this->specAliasT = specAliasT;
2230     this->defaultAlias = defaultAlias;
2231
2232     this->specAlias = NULL;
2233 }
2234
2235 TemplateAliasParameter *TemplateAliasParameter::isTemplateAliasParameter()
2236 {
2237     return this;
2238 }
2239
2240 TemplateParameter *TemplateAliasParameter::syntaxCopy()
2241 {
2242     TemplateAliasParameter *tp = new TemplateAliasParameter(loc, ident, specAliasT, defaultAlias);
2243     if (tp->specAliasT)
2244         tp->specAliasT = specAliasT->syntaxCopy();
2245     if (defaultAlias)
2246         tp->defaultAlias = defaultAlias->syntaxCopy();
2247     return tp;
2248 }
2249
2250 void TemplateAliasParameter::declareParameter(Scope *sc)
2251 {
2252     TypeIdentifier *ti = new TypeIdentifier(loc, ident);
2253     sparam = new AliasDeclaration(loc, ident, ti);
2254     if (!sc->insert(sparam))
2255         error(loc, "parameter '%s' multiply defined", ident->toChars());
2256 }
2257
2258 void TemplateAliasParameter::semantic(Scope *sc)
2259 {
2260     if (specAliasT)
2261     {
2262         specAlias = specAliasT->toDsymbol(sc);
2263         if (!specAlias)
2264             error("%s is not a symbol", specAliasT->toChars());
2265     }
2266 #if 0 // Don't do semantic() until instantiation
2267     if (defaultAlias)
2268         defaultAlias = defaultAlias->semantic(loc, sc);
2269 #endif
2270 }
2271
2272 int TemplateAliasParameter::overloadMatch(TemplateParameter *tp)
2273 {
2274     TemplateAliasParameter *tap = tp->isTemplateAliasParameter();
2275
2276     if (tap)
2277     {
2278         if (specAlias != tap->specAlias)
2279             goto Lnomatch;
2280
2281         return 1;                       // match
2282     }
2283
2284 Lnomatch:
2285     return 0;
2286 }
2287
2288 MATCH TemplateAliasParameter::matchArg(Scope *sc,
2289         Objects *tiargs, int i, TemplateParameters *parameters, Objects *dedtypes,
2290         Declaration **psparam, int flags)
2291 {
2292     Dsymbol *sa;
2293     Object *oarg;
2294     Expression *ea;
2295
2296     //printf("TemplateAliasParameter::matchArg()\n");
2297
2298     if (i < tiargs->dim)
2299         oarg = (Object *)tiargs->data[i];
2300     else
2301     {   // Get default argument instead
2302         oarg = defaultArg(loc, sc);
2303         if (!oarg)
2304         {   assert(i < dedtypes->dim);
2305             // It might have already been deduced
2306             oarg = (Object *)dedtypes->data[i];
2307             if (!oarg)
2308                 goto Lnomatch;
2309         }
2310     }
2311
2312     sa = getDsymbol(oarg);
2313     if (!sa)
2314         goto Lnomatch;
2315
2316     if (specAlias)
2317     {
2318         if (!sa || sa == sdummy)
2319             goto Lnomatch;
2320         if (sa != specAlias)
2321             goto Lnomatch;
2322     }
2323     else if (dedtypes->data[i])
2324     {   // Must match already deduced symbol
2325         Dsymbol *s = (Dsymbol *)dedtypes->data[i];
2326
2327         if (!sa || s != sa)
2328             goto Lnomatch;
2329     }
2330     dedtypes->data[i] = sa;
2331
2332     *psparam = new AliasDeclaration(loc, ident, sa);
2333     return MATCHexact;
2334
2335 Lnomatch:
2336     *psparam = NULL;
2337     return MATCHnomatch;
2338 }
2339
2340
2341 void TemplateAliasParameter::print(Object *oarg, Object *oded)
2342 {
2343     fprintf(stderr, " %s\n", ident->toChars());
2344
2345     Dsymbol *sa = isDsymbol(oded);
2346     assert(sa);
2347
2348     fprintf(stderr, "\tArgument alias: %s\n", sa->toChars());
2349 }
2350
2351 void TemplateAliasParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2352 {
2353     buf->writestring("alias ");
2354     buf->writestring(ident->toChars());
2355     if (specAliasT)
2356     {
2357         buf->writestring(" : ");
2358         specAliasT->toCBuffer(buf, NULL, hgs);
2359     }
2360     if (defaultAlias)
2361     {
2362         buf->writestring(" = ");
2363         defaultAlias->toCBuffer(buf, NULL, hgs);
2364     }
2365 }
2366
2367
2368 void *TemplateAliasParameter::dummyArg()
2369 {   Dsymbol *s;
2370
2371     s = specAlias;
2372     if (!s)
2373     {
2374         if (!sdummy)
2375             sdummy = new Dsymbol();
2376         s = sdummy;
2377     }
2378     return (void*)s;
2379 }
2380
2381
2382 Object *TemplateAliasParameter::specialization()
2383 {
2384     return specAliasT;
2385 }
2386
2387
2388 Object *TemplateAliasParameter::defaultArg(Loc loc, Scope *sc)
2389 {
2390     Dsymbol *s = NULL;
2391
2392     if (defaultAlias)
2393     {
2394         s = defaultAlias->toDsymbol(sc);
2395         if (!s)
2396             error("%s is not a symbol", defaultAlias->toChars());
2397     }
2398     return s;
2399 }
2400
2401 /* ======================== TemplateValueParameter ========================== */
2402
2403 // value-parameter
2404
2405 Expression *TemplateValueParameter::edummy = NULL;
2406
2407 TemplateValueParameter::TemplateValueParameter(Loc loc, Identifier *ident, Type *valType,
2408         Expression *specValue, Expression *defaultValue)
2409     : TemplateParameter(loc, ident)
2410 {
2411     this->ident = ident;
2412     this->valType = valType;
2413     this->specValue = specValue;
2414     this->defaultValue = defaultValue;
2415 }
2416
2417 TemplateValueParameter *TemplateValueParameter::isTemplateValueParameter()
2418 {
2419     return this;
2420 }
2421
2422 TemplateParameter *TemplateValueParameter::syntaxCopy()
2423 {
2424     TemplateValueParameter *tp =
2425         new TemplateValueParameter(loc, ident, valType, specValue, defaultValue);
2426     tp->valType = valType->syntaxCopy();
2427     if (specValue)
2428         tp->specValue = specValue->syntaxCopy();
2429     if (defaultValue)
2430         tp->defaultValue = defaultValue->syntaxCopy();
2431     return tp;
2432 }
2433
2434 void TemplateValueParameter::declareParameter(Scope *sc)
2435 {
2436     VarDeclaration *v = new VarDeclaration(loc, valType, ident, NULL);
2437     v->storage_class = STCtemplateparameter;
2438     if (!sc->insert(v))
2439         error(loc, "parameter '%s' multiply defined", ident->toChars());
2440     sparam = v;
2441 }
2442
2443 void TemplateValueParameter::semantic(Scope *sc)
2444 {
2445     sparam->semantic(sc);
2446     valType = valType->semantic(loc, sc);
2447     if (!(valType->isintegral() || valType->isfloating() || valType->isString()) &&
2448         valType->ty != Tident)
2449         error(loc, "arithmetic/string type expected for value-parameter, not %s", valType->toChars());
2450
2451     if (specValue)
2452     {   Expression *e = specValue;
2453
2454         e = e->semantic(sc);
2455         e = e->implicitCastTo(sc, valType);
2456         e = e->optimize(WANTvalue | WANTinterpret);
2457         if (e->op == TOKint64 || e->op == TOKfloat64 ||
2458             e->op == TOKcomplex80 || e->op == TOKnull || e->op == TOKstring)
2459             specValue = e;
2460         //e->toInteger();
2461     }
2462
2463 #if 0   // defer semantic analysis to arg match
2464     if (defaultValue)
2465     {   Expression *e = defaultValue;
2466
2467         e = e->semantic(sc);
2468         e = e->implicitCastTo(sc, valType);
2469         e = e->optimize(WANTvalue | WANTinterpret);
2470         if (e->op == TOKint64)
2471             defaultValue = e;
2472         //e->toInteger();
2473     }
2474 #endif
2475 }
2476
2477 int TemplateValueParameter::overloadMatch(TemplateParameter *tp)
2478 {
2479     TemplateValueParameter *tvp = tp->isTemplateValueParameter();
2480
2481     if (tvp)
2482     {
2483         if (valType != tvp->valType)
2484             goto Lnomatch;
2485
2486         if (valType && !valType->equals(tvp->valType))
2487             goto Lnomatch;
2488
2489         if (specValue != tvp->specValue)
2490             goto Lnomatch;
2491
2492         return 1;                       // match
2493     }
2494
2495 Lnomatch:
2496     return 0;
2497 }
2498
2499
2500 MATCH TemplateValueParameter::matchArg(Scope *sc,
2501         Objects *tiargs, int i, TemplateParameters *parameters, Objects *dedtypes,
2502         Declaration **psparam, int flags)
2503 {
2504     //printf("TemplateValueParameter::matchArg()\n");
2505
2506     Initializer *init;
2507     Declaration *sparam;
2508     MATCH m = MATCHexact;
2509     Expression *ei;
2510     Object *oarg;
2511
2512     if (i < tiargs->dim)
2513         oarg = (Object *)tiargs->data[i];
2514     else
2515     {   // Get default argument instead
2516         oarg = defaultArg(loc, sc);
2517         if (!oarg)
2518         {   assert(i < dedtypes->dim);
2519             // It might have already been deduced
2520             oarg = (Object *)dedtypes->data[i];
2521             if (!oarg)
2522                 goto Lnomatch;
2523         }
2524     }
2525
2526     ei = isExpression(oarg);
2527     Type *vt;
2528
2529     if (!ei && oarg)
2530         goto Lnomatch;
2531
2532     if (ei && ei->op == TOKvar)
2533     {   // Resolve const variables that we had skipped earlier
2534         ei = ei->optimize(WANTvalue | WANTinterpret);
2535     }
2536
2537     if (specValue)
2538     {
2539         if (!ei || ei == edummy)
2540             goto Lnomatch;
2541
2542         Expression *e = specValue;
2543
2544         e = e->semantic(sc);
2545         e = e->implicitCastTo(sc, valType);
2546         e = e->optimize(WANTvalue | WANTinterpret);
2547         //e->type = e->type->toHeadMutable();
2548
2549         ei = ei->syntaxCopy();
2550         ei = ei->semantic(sc);
2551         ei = ei->optimize(WANTvalue | WANTinterpret);
2552         //ei->type = ei->type->toHeadMutable();
2553         //printf("\tei: %s, %s\n", ei->toChars(), ei->type->toChars());
2554         //printf("\te : %s, %s\n", e->toChars(), e->type->toChars());
2555         if (!ei->equals(e))
2556             goto Lnomatch;
2557     }
2558     else if (dedtypes->data[i])
2559     {   // Must match already deduced value
2560         Expression *e = (Expression *)dedtypes->data[i];
2561
2562         if (!ei || !ei->equals(e))
2563             goto Lnomatch;
2564     }
2565 Lmatch:
2566     //printf("\tvalType: %s, ty = %d\n", valType->toChars(), valType->ty);
2567     vt = valType->semantic(0, sc);
2568     //printf("ei: %s, ei->type: %s\n", ei->toChars(), ei->type->toChars());
2569     //printf("vt = %s\n", vt->toChars());
2570     if (ei->type)
2571     {
2572         //ei->type = ei->type->toHeadMutable();
2573         m = (MATCH)ei->implicitConvTo(vt);
2574         //printf("m: %d\n", m);
2575         if (!m)
2576             goto Lnomatch;
2577     }
2578     dedtypes->data[i] = ei;
2579
2580     init = new ExpInitializer(loc, ei);
2581     sparam = new VarDeclaration(loc, vt, ident, init);
2582     sparam->storage_class = STCmanifest;
2583     *psparam = sparam;
2584     return m;
2585
2586 Lnomatch:
2587     //printf("\tno match\n");
2588     *psparam = NULL;
2589     return MATCHnomatch;
2590 }
2591
2592
2593 void TemplateValueParameter::print(Object *oarg, Object *oded)
2594 {
2595     fprintf(stderr, " %s\n", ident->toChars());
2596
2597     Expression *ea = isExpression(oded);
2598
2599     if (specValue)
2600         fprintf(stderr, "\tSpecialization: %s\n", specValue->toChars());
2601     fprintf(stderr, "\tArgument Value: %s\n", ea ? ea->toChars() : "NULL");
2602 }
2603
2604
2605 void TemplateValueParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2606 {
2607     valType->toCBuffer(buf, ident, hgs);
2608     if (specValue)
2609     {
2610         buf->writestring(" : ");
2611         specValue->toCBuffer(buf, hgs);
2612     }
2613     if (defaultValue)
2614     {
2615         buf->writestring(" = ");
2616         defaultValue->toCBuffer(buf, hgs);
2617     }
2618 }
2619
2620
2621 void *TemplateValueParameter::dummyArg()
2622 {   Expression *e;
2623
2624     e = specValue;
2625     if (!e)
2626     {
2627         // Create a dummy value
2628         if (!edummy)
2629             edummy = valType->defaultInit();
2630         e = edummy;
2631     }
2632     return (void *)e;
2633 }
2634
2635
2636 Object *TemplateValueParameter::specialization()
2637 {
2638     return specValue;
2639 }
2640
2641
2642 Object *TemplateValueParameter::defaultArg(Loc loc, Scope *sc)
2643 {
2644     Expression *e = defaultValue;
2645     if (e)
2646     {
2647         e = e->syntaxCopy();
2648         e = e->semantic(sc);
2649 #if V2
2650         if (e->op == TOKdefault)
2651         {   DefaultInitExp *de = (DefaultInitExp *)e;
2652             e = de->resolve(loc, sc);
2653         }
2654 #endif
2655     }
2656     return e;
2657 }
2658
2659 /* ======================== TemplateTupleParameter ========================== */
2660
2661 // variadic-parameter
2662
2663 TemplateTupleParameter::TemplateTupleParameter(Loc loc, Identifier *ident)
2664     : TemplateParameter(loc, ident)
2665 {
2666     this->ident = ident;
2667 }
2668
2669 TemplateTupleParameter *TemplateTupleParameter::isTemplateTupleParameter()
2670 {
2671     return this;
2672 }
2673
2674 TemplateParameter *TemplateTupleParameter::syntaxCopy()
2675 {
2676     TemplateTupleParameter *tp = new TemplateTupleParameter(loc, ident);
2677     return tp;
2678 }
2679
2680 void TemplateTupleParameter::declareParameter(Scope *sc)
2681 {
2682     TypeIdentifier *ti = new TypeIdentifier(loc, ident);
2683     sparam = new AliasDeclaration(loc, ident, ti);
2684     if (!sc->insert(sparam))
2685         error(loc, "parameter '%s' multiply defined", ident->toChars());
2686 }
2687
2688 void TemplateTupleParameter::semantic(Scope *sc)
2689 {
2690 }
2691
2692 int TemplateTupleParameter::overloadMatch(TemplateParameter *tp)
2693 {
2694     TemplateTupleParameter *tvp = tp->isTemplateTupleParameter();
2695
2696     if (tvp)
2697     {
2698         return 1;                       // match
2699     }
2700
2701 Lnomatch:
2702     return 0;
2703 }
2704
2705 MATCH TemplateTupleParameter::matchArg(Scope *sc,
2706         Objects *tiargs, int i, TemplateParameters *parameters,
2707         Objects *dedtypes,
2708         Declaration **psparam, int flags)
2709 {
2710     //printf("TemplateTupleParameter::matchArg()\n");
2711
2712     /* The rest of the actual arguments (tiargs[]) form the match
2713      * for the variadic parameter.
2714      */
2715     assert(i + 1 == dedtypes->dim);     // must be the last one
2716     Tuple *ovar;
2717     if (i + 1 == tiargs->dim && isTuple((Object *)tiargs->data[i]))
2718         ovar = isTuple((Object *)tiargs->data[i]);
2719     else
2720     {
2721         ovar = new Tuple();
2722         //printf("ovar = %p\n", ovar);
2723         if (i < tiargs->dim)
2724         {
2725             //printf("i = %d, tiargs->dim = %d\n", i, tiargs->dim);
2726             ovar->objects.setDim(tiargs->dim - i);
2727             for (size_t j = 0; j < ovar->objects.dim; j++)
2728                 ovar->objects.data[j] = tiargs->data[i + j];
2729         }
2730     }
2731     *psparam = new TupleDeclaration(loc, ident, &ovar->objects);
2732     dedtypes->data[i] = (void *)ovar;
2733     return MATCHexact;
2734 }
2735
2736
2737 void TemplateTupleParameter::print(Object *oarg, Object *oded)
2738 {
2739     printf(" %s... [", ident->toChars());
2740     Tuple *v = isTuple(oded);
2741     assert(v);
2742
2743     //printf("|%d| ", v->objects.dim);
2744     for (int i = 0; i < v->objects.dim; i++)
2745     {
2746         if (i)
2747             printf(", ");
2748
2749         Object *o = (Object *)v->objects.data[i];
2750
2751         Dsymbol *sa = isDsymbol(o);
2752         if (sa)
2753             printf("alias: %s", sa->toChars());
2754
2755         Type *ta = isType(o);
2756         if (ta)
2757             printf("type: %s", ta->toChars());
2758
2759         Expression *ea = isExpression(o);
2760         if (ea)
2761             printf("exp: %s", ea->toChars());
2762
2763         assert(!isTuple(o));            // no nested Tuple arguments
2764     }
2765
2766     printf("]\n");
2767 }
2768
2769 void TemplateTupleParameter::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
2770 {
2771     buf->writestring(ident->toChars());
2772     buf->writestring("...");
2773 }
2774
2775
2776 void *TemplateTupleParameter::dummyArg()
2777 {
2778     return NULL;
2779 }
2780
2781
2782 Object *TemplateTupleParameter::specialization()
2783 {
2784     return NULL;
2785 }
2786
2787
2788 Object *TemplateTupleParameter::defaultArg(Loc loc, Scope *sc)
2789 {
2790     return NULL;
2791 }
2792
2793 /* ======================== TemplateInstance ================================ */
2794
2795 TemplateInstance::TemplateInstance(Loc loc, Identifier *ident)
2796     : ScopeDsymbol(NULL)
2797 {
2798 #if LOG
2799     printf("TemplateInstance(this = %p, ident = '%s')\n", this, ident ? ident->toChars() : "null");
2800 #endif
2801     this->loc = loc;
2802     this->name = ident;
2803     this->tiargs = NULL;
2804     this->tempdecl = NULL;
2805     this->inst = NULL;
2806     this->argsym = NULL;
2807     this->aliasdecl = NULL;
2808     this->semanticdone = 0;
2809     this->withsym = NULL;
2810     this->nest = 0;
2811 #ifdef IN_GCC
2812     this->objFileModule = NULL;
2813 #endif
2814     this->havetempdecl = 0;
2815     this->isnested = NULL;
2816     this->errors = 0;
2817 }
2818
2819
2820 TemplateInstance::TemplateInstance(Loc loc, TemplateDeclaration *td, Objects *tiargs)
2821     : ScopeDsymbol(NULL)
2822 {
2823 #if LOG
2824     printf("TemplateInstance(this = %p, tempdecl = '%s')\n", this, td->toChars());
2825 #endif
2826     this->loc = loc;
2827     this->name = td->ident;
2828     this->tiargs = tiargs;
2829     this->tempdecl = td;
2830     this->inst = NULL;
2831     this->argsym = NULL;
2832     this->aliasdecl = NULL;
2833     this->semanticdone = 0;
2834     this->withsym = NULL;
2835     this->nest = 0;
2836 #ifdef IN_GCC
2837     this->objFileModule = NULL;
2838 #endif
2839     this->havetempdecl = 1;
2840     this->isnested = NULL;
2841     this->errors = 0;
2842
2843     assert((size_t)tempdecl->scope > 0x10000);
2844 }
2845
2846
2847 Objects *TemplateInstance::arraySyntaxCopy(Objects *objs)
2848 {
2849     Objects *a = NULL;
2850     if (objs)
2851     {   a = new Objects();
2852         a->setDim(objs->dim);
2853         for (size_t i = 0; i < objs->dim; i++)
2854         {
2855             Type *ta = isType((Object *)objs->data[i]);
2856             if (ta)
2857                 a->data[i] = ta->syntaxCopy();
2858             else
2859             {
2860                 Expression *ea = isExpression((Object *)objs->data[i]);
2861                 assert(ea);
2862                 a->data[i] = ea->syntaxCopy();
2863             }
2864         }
2865     }
2866     return a;
2867 }
2868
2869 Dsymbol *TemplateInstance::syntaxCopy(Dsymbol *s)
2870 {
2871     TemplateInstance *ti;
2872     int i;
2873
2874     if (s)
2875         ti = (TemplateInstance *)s;
2876     else
2877         ti = new TemplateInstance(loc, name);
2878
2879     ti->tiargs = arraySyntaxCopy(tiargs);
2880
2881     ScopeDsymbol::syntaxCopy(ti);
2882     return ti;
2883 }
2884
2885
2886 #ifdef IN_GCC
2887 #include "d-dmd-gcc.h"
2888 #endif
2889
2890 void TemplateInstance::semantic(Scope *sc)
2891 {
2892     if (global.errors)
2893     {
2894         if (!global.gag)
2895         {
2896             /* Trying to soldier on rarely generates useful messages
2897              * at this point.
2898              */
2899             fatal();
2900         }
2901         return;
2902     }
2903 #if LOG
2904     printf("\n+TemplateInstance::semantic('%s', this=%p)\n", toChars(), this);
2905 #endif
2906 #ifdef IN_GCC
2907     /*
2908     fprintf(stderr, "ti '%s' (%p), belongs in '%s'\n", toChars(), this,
2909         sc->module->toPrettyChars());
2910     if (inst) {
2911         fprintf(stderr, "  -- really '%s' (%p)\n", inst->toChars(), inst);
2912     } else {
2913         fprintf(stderr, "  -- doing semantic\n");
2914     }
2915     */
2916 #endif
2917     if (inst)           // if semantic() was already run
2918     {
2919 #if LOG
2920         printf("-TemplateInstance::semantic('%s', this=%p) already run\n", inst->toChars(), inst);
2921 #endif
2922         return;
2923     }
2924
2925     if (semanticdone != 0)
2926     {
2927         error(loc, "recursive template expansion");
2928 //      inst = this;
2929         return;
2930     }
2931     semanticdone = 1;
2932
2933 #if LOG
2934     printf("\tdo semantic\n");
2935 #endif
2936     if (havetempdecl)
2937     {
2938         assert((size_t)tempdecl->scope > 0x10000);
2939         // Deduce tdtypes
2940         tdtypes.setDim(tempdecl->parameters->dim);
2941         if (!tempdecl->matchWithInstance(this, &tdtypes, 2))
2942         {
2943             error("incompatible arguments for template instantiation");
2944             inst = this;
2945             return;
2946         }
2947     }
2948     else
2949     {
2950         // Run semantic on each argument, place results in tiargs[]
2951         semanticTiargs(sc);
2952
2953         tempdecl = findTemplateDeclaration(sc);
2954         if (tempdecl)
2955             tempdecl = findBestMatch(sc);
2956         if (!tempdecl || global.errors)
2957         {   inst = this;
2958             //printf("error return %p, %d\n", tempdecl, global.errors);
2959             return;             // error recovery
2960         }
2961     }
2962
2963     isNested(tiargs);
2964
2965     /* See if there is an existing TemplateInstantiation that already
2966      * implements the typeargs. If so, just refer to that one instead.
2967      */
2968
2969     for (size_t i = 0; i < tempdecl->instances.dim; i++)
2970     {
2971         TemplateInstance *ti = (TemplateInstance *)tempdecl->instances.data[i];
2972 #if LOG
2973         printf("\t%s: checking for match with instance %d (%p): '%s'\n", toChars(), i, ti, ti->toChars());
2974 #endif
2975         assert(tdtypes.dim == ti->tdtypes.dim);
2976
2977         // Nesting must match
2978         if (isnested != ti->isnested)
2979             continue;
2980 #if 0
2981         if (isnested && sc->parent != ti->parent)
2982             continue;
2983 #endif
2984         for (size_t j = 0; j < tdtypes.dim; j++)
2985         {   Object *o1 = (Object *)tdtypes.data[j];
2986             Object *o2 = (Object *)ti->tdtypes.data[j];
2987             if (!match(o1, o2, tempdecl, sc))
2988                 goto L1;
2989         }
2990
2991         // It's a match
2992         inst = ti;
2993         parent = ti->parent;
2994 #if LOG
2995         printf("\tit's a match with instance %p\n", inst);
2996 #endif
2997         return;
2998
2999      L1:
3000         ;
3001     }
3002
3003     /* So, we need to implement 'this' instance.
3004      */
3005 #if LOG
3006     printf("\timplement template instance '%s'\n", toChars());
3007 #endif
3008     unsigned errorsave = global.errors;
3009     inst = this;
3010     int tempdecl_instance_idx = tempdecl->instances.dim;
3011     tempdecl->instances.push(this);
3012     parent = tempdecl->parent;
3013     //printf("parent = '%s'\n", parent->kind());
3014
3015     ident = genIdent();         // need an identifier for name mangling purposes.
3016
3017 #if 1
3018     if (isnested)
3019         parent = isnested;
3020 #endif
3021     //printf("parent = '%s'\n", parent->kind());
3022
3023     // Add 'this' to the enclosing scope's members[] so the semantic routines
3024     // will get called on the instance members
3025 #if 1
3026     int dosemantic3 = 0;
3027     {   Array *a;
3028
3029         Scope *scx = sc;
3030 #if 0
3031         for (scx = sc; scx; scx = scx->enclosing)
3032             if (scx->scopesym)
3033                 break;
3034 #endif
3035
3036 #ifdef IN_GCC
3037         /* For "all" and "private" template modes, templates are always
3038            emitted.  Problem:  This picks up templates that aren't even
3039            needed in the current module. */
3040
3041         if (d_gcc_force_templates())
3042         {
3043             //fprintf(stderr, "\t0: adding to %s %s\n", sc->scopesym->kind(), sc->scopesym->toChars());
3044             objFileModule = d_gcc_get_output_module();
3045             a = objFileModule->members;
3046         }
3047         else
3048 #endif
3049
3050         //if (scx && scx->scopesym) printf("3: scx is %s %s\n", scx->scopesym->kind(), scx->scopesym->toChars());
3051         if (scx && scx->scopesym && scx->scopesym->members && !scx->scopesym->isTemplateMixin())
3052         {
3053             //printf("\t1: adding to %s %s\n", scx->scopesym->kind(), scx->scopesym->toChars());
3054             a = scx->scopesym->members;
3055 #ifdef IN_GCC
3056             {
3057                 Dsymbol * p = scx->scopesym;
3058                 Module * m;
3059                 TemplateInstance * i;
3060
3061                 while (p) {
3062                     if ( (i = p->isTemplateInstance()) ) {
3063                         if (i->objFileModule) {
3064                             objFileModule = i->objFileModule;
3065                             break;
3066                         }
3067                     } else if ( (m = p->isModule()) ) {
3068                         objFileModule = m; // %% importedFrom ?
3069                         break;
3070                     }
3071                     p = p->parent;
3072                 }
3073                 // fprintf(stderr, "\t1: adding %s to module %s via %s %s\n", tempdecl->toChars(), objFileModule?objFileModule->toChars():"", sc->scopesym->kind(), sc->scopesym->toChars());
3074             }
3075 #endif
3076         }
3077         else
3078         {   Module *m = sc->module->importedFrom;
3079             //printf("\t2: adding to module %s instead of module %s\n", m->toChars(), sc->module->toChars());
3080             a = m->members;
3081             if (m->semanticdone >= 3)
3082                 dosemantic3 = 1;
3083 #ifdef IN_GCC
3084             objFileModule = m;
3085 #endif
3086         }
3087         for (int i = 0; 1; i++)
3088         {
3089             if (i == a->dim)
3090             {
3091                 a->push(this);
3092                 break;
3093             }
3094             if (this == (Dsymbol *)a->data[i])  // if already in Array
3095                 break;
3096         }
3097     }
3098 #endif
3099
3100     // Copy the syntax trees from the TemplateDeclaration
3101     members = Dsymbol::arraySyntaxCopy(tempdecl->members);
3102
3103     // Create our own scope for the template parameters
3104     Scope *scope = tempdecl->scope;
3105     if (!scope)
3106     {
3107         error("forward reference to template declaration %s\n", tempdecl->toChars());
3108         return;
3109     }
3110
3111 #if LOG
3112     printf("\tcreate scope for template parameters '%s'\n", toChars());
3113 #endif
3114     argsym = new ScopeDsymbol();
3115     argsym->parent = scope->parent;
3116     scope = scope->push(argsym);
3117
3118     // Declare each template parameter as an alias for the argument type
3119     declareParameters(scope);
3120
3121     // Add members of template instance to template instance symbol table
3122 //    parent = scope->scopesym;
3123     symtab = new DsymbolTable();
3124     int memnum = 0;
3125     for (int i = 0; i < members->dim; i++)
3126     {
3127         Dsymbol *s = (Dsymbol *)members->data[i];
3128 #if LOG
3129         printf("\t[%d] adding member '%s' %p kind %s to '%s', memnum = %d\n", i, s->toChars(), s, s->kind(), this->toChars(), memnum);
3130 #endif
3131         memnum |= s->addMember(scope, this, memnum);
3132     }
3133 #if LOG
3134     printf("adding members done\n");
3135 #endif
3136
3137     /* See if there is only one member of template instance, and that
3138      * member has the same name as the template instance.
3139      * If so, this template instance becomes an alias for that member.
3140      */
3141     //printf("members->dim = %d\n", members->dim);
3142     if (members->dim)
3143     {
3144         Dsymbol *s;
3145         if (Dsymbol::oneMembers(members, &s) && s)
3146         {
3147             //printf("s->kind = '%s'\n", s->kind());
3148             //s->print();
3149             //printf("'%s', '%s'\n", s->ident->toChars(), tempdecl->ident->toChars());
3150             if (s->ident && s->ident->equals(tempdecl->ident))
3151             {
3152                 //printf("setting aliasdecl\n");
3153                 aliasdecl = new AliasDeclaration(loc, s->ident, s);
3154             }
3155         }
3156     }
3157
3158     // Do semantic() analysis on template instance members
3159 #if LOG
3160     printf("\tdo semantic() on template instance members '%s'\n", toChars());
3161 #endif
3162     Scope *sc2;
3163     sc2 = scope->push(this);
3164     //printf("isnested = %d, sc->parent = %s\n", isnested, sc->parent->toChars());
3165     sc2->parent = /*isnested ? sc->parent :*/ this;
3166     sc2->fromDcode = !tempdecl->dltSource;
3167
3168 #ifndef IN_GCC
3169 #if _WIN32
3170   __try
3171   {
3172 #endif
3173 #endif
3174     for (int i = 0; i < members->dim; i++)
3175     {
3176         Dsymbol *s = (Dsymbol *)members->data[i];
3177         //printf("\t[%d] semantic on '%s' %p kind %s in '%s'\n", i, s->toChars(), s, s->kind(), this->toChars());
3178         //printf("test: isnested = %d, sc2->parent = %s\n", isnested, sc2->parent->toChars());
3179 //      if (isnested)
3180 //          s->parent = sc->parent;
3181         //printf("test3: isnested = %d, s->parent = %s\n", isnested, s->parent->toChars());
3182         s->semantic(sc2);
3183         //printf("test4: isnested = %d, s->parent = %s\n", isnested, s->parent->toChars());
3184         sc2->module->runDeferredSemantic();
3185     }
3186 #ifndef IN_GCC
3187 #if _WIN32
3188   }
3189   __except (__ehfilter(GetExceptionInformation()))
3190   {
3191     global.gag = 0;                     // ensure error message gets printed
3192     error("recursive expansion");
3193     fatal();
3194   }
3195 #endif
3196 #endif
3197
3198     /* If any of the instantiation members didn't get semantic() run
3199      * on them due to forward references, we cannot run semantic2()
3200      * or semantic3() yet.
3201      */
3202     for (size_t i = 0; i < Module::deferred.dim; i++)
3203     {   Dsymbol *sd = (Dsymbol *)Module::deferred.data[i];
3204
3205         if (sd->parent == this)
3206             goto Laftersemantic;
3207     }
3208
3209     /* The problem is when to parse the initializer for a variable.
3210      * Perhaps VarDeclaration::semantic() should do it like it does
3211      * for initializers inside a function.
3212      */
3213 //    if (sc->parent->isFuncDeclaration())
3214
3215         /* BUG 782: this has problems if the classes this depends on
3216          * are forward referenced. Find a way to defer semantic()
3217          * on this template.
3218          */
3219         semantic2(sc2);
3220
3221     if (sc->func || dosemantic3)
3222     {
3223         semantic3(sc2);
3224     }
3225
3226   Laftersemantic:
3227     sc2->pop();
3228
3229     scope->pop();
3230
3231     // Give additional context info if error occurred during instantiation
3232     if (global.errors != errorsave)
3233     {
3234         error("error instantiating");
3235         errors = 1;
3236         if (global.gag)
3237             tempdecl->instances.remove(tempdecl_instance_idx);
3238     }
3239
3240 #if LOG
3241     printf("-TemplateInstance::semantic('%s', this=%p)\n", toChars(), this);
3242 #endif
3243 }
3244
3245
3246 void TemplateInstance::semanticTiargs(Scope *sc)
3247 {
3248     //printf("+TemplateInstance::semanticTiargs() %s\n", toChars());
3249     semanticTiargs(loc, sc, tiargs, 0);
3250 }
3251
3252 /**********************************
3253  * Input:
3254  *      flags   1: replace const variables with their initializers
3255  */
3256
3257 void TemplateInstance::semanticTiargs(Loc loc, Scope *sc, Objects *tiargs, int flags)
3258 {
3259     // Run semantic on each argument, place results in tiargs[]
3260     //printf("+TemplateInstance::semanticTiargs()\n");
3261     if (!tiargs)
3262         return;
3263     for (size_t j = 0; j < tiargs->dim; j++)
3264     {
3265         Object *o = (Object *)tiargs->data[j];
3266         Type *ta = isType(o);
3267         Expression *ea = isExpression(o);
3268         Dsymbol *sa = isDsymbol(o);
3269
3270         //printf("1: tiargs->data[%d] = %p, %p, %p, ea=%p, ta=%p\n", j, o, isDsymbol(o), isTuple(o), ea, ta);
3271         if (ta)
3272         {
3273             //printf("type %s\n", ta->toChars());
3274             // It might really be an Expression or an Alias
3275             ta->resolve(loc, sc, &ea, &ta, &sa);
3276             if (ea)
3277             {
3278                 ea = ea->semantic(sc);
3279                 /* This test is to skip substituting a const var with
3280                  * its initializer. The problem is the initializer won't
3281                  * match with an 'alias' parameter. Instead, do the
3282                  * const substitution in TemplateValueParameter::matchArg().
3283                  */
3284                 if (ea->op != TOKvar || flags & 1)
3285                     ea = ea->optimize(WANTvalue | WANTinterpret);
3286                 tiargs->data[j] = ea;
3287             }
3288             else if (sa)
3289             {   tiargs->data[j] = sa;
3290                 TupleDeclaration *d = sa->toAlias()->isTupleDeclaration();
3291                 if (d)
3292                 {
3293                     size_t dim = d->objects->dim;
3294                     tiargs->remove(j);
3295                     tiargs->insert(j, d->objects);
3296                     j--;
3297                 }
3298             }
3299             else if (ta)
3300             {
3301                 if (ta->ty == Ttuple)
3302                 {   // Expand tuple
3303                     TypeTuple *tt = (TypeTuple *)ta;
3304                     size_t dim = tt->arguments->dim;
3305                     tiargs->remove(j);
3306                     if (dim)
3307                     {   tiargs->reserve(dim);
3308                         for (size_t i = 0; i < dim; i++)
3309                         {   Argument *arg = (Argument *)tt->arguments->data[i];
3310                             tiargs->insert(j + i, arg->type);
3311                         }
3312                     }
3313                     j--;
3314                 }
3315                 else
3316                     tiargs->data[j] = ta;
3317             }
3318             else
3319             {
3320                 assert(global.errors);
3321                 tiargs->data[j] = Type::terror;
3322             }
3323         }
3324         else if (ea)
3325         {
3326             if (!ea)
3327             {   assert(global.errors);
3328                 ea = new IntegerExp(0);
3329             }
3330             assert(ea);
3331             ea = ea->semantic(sc);
3332             if (ea->op != TOKvar || flags & 1)
3333                 ea = ea->optimize(WANTvalue | WANTinterpret);
3334             tiargs->data[j] = ea;
3335             if (ea->op == TOKtype)
3336                 tiargs->data[j] = ea->type;
3337         }
3338         else if (sa)
3339         {
3340         }
3341         else
3342         {
3343             assert(0);
3344         }
3345         //printf("1: tiargs->data[%d] = %p\n", j, tiargs->data[j]);
3346     }
3347 #if 0
3348     printf("-TemplateInstance::semanticTiargs('%s', this=%p)\n", toChars(), this);
3349     for (size_t j = 0; j < tiargs->dim; j++)
3350     {
3351         Object *o = (Object *)tiargs->data[j];
3352         Type *ta = isType(o);
3353         Expression *ea = isExpression(o);
3354         Dsymbol *sa = isDsymbol(o);
3355         Tuple *va = isTuple(o);
3356
3357         printf("\ttiargs[%d] = ta %p, ea %p, sa %p, va %p\n", j, ta, ea, sa, va);
3358     }
3359 #endif
3360 }
3361
3362 /**********************************************
3363  * Find template declaration corresponding to template instance.
3364  */
3365
3366 TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
3367 {
3368     //printf("TemplateInstance::findTemplateDeclaration() %s\n", toChars());
3369     if (!tempdecl)
3370     {
3371         /* Given:
3372          *    foo!( ... )
3373          * figure out which TemplateDeclaration foo refers to.
3374          */
3375         Dsymbol *s;
3376         Dsymbol *scopesym;
3377         Identifier *id;
3378         int i;
3379
3380         id = name;
3381         s = sc->search(loc, id, &scopesym);
3382         if (!s)
3383         {   error("identifier '%s' is not defined", id->toChars());
3384             return NULL;
3385         }
3386 #if LOG
3387         printf("It's an instance of '%s' kind '%s'\n", s->toChars(), s->kind());
3388         if (s->parent)
3389             printf("s->parent = '%s'\n", s->parent->toChars());
3390 #endif
3391         withsym = scopesym->isWithScopeSymbol();
3392
3393         /* We might have found an alias within a template when
3394          * we really want the template.
3395          */
3396         TemplateInstance *ti;
3397         if (s->parent &&
3398             (ti = s->parent->isTemplateInstance()) != NULL)
3399         {
3400             if (
3401                 (ti->name == id ||
3402                  ti->toAlias()->ident == id)
3403                 &&
3404                 ti->tempdecl)
3405             {
3406                 /* This is so that one can refer to the enclosing
3407                  * template, even if it has the same name as a member
3408                  * of the template, if it has a !(arguments)
3409                  */
3410                 tempdecl = ti->tempdecl;
3411                 if (tempdecl->overroot)         // if not start of overloaded list of TemplateDeclaration's
3412                     tempdecl = tempdecl->overroot; // then get the start
3413                 s = tempdecl;
3414             }
3415         }
3416
3417         s = s->toAlias();
3418
3419         /* It should be a TemplateDeclaration, not some other symbol
3420          */
3421         tempdecl = s->isTemplateDeclaration();
3422         if (!tempdecl)
3423         {
3424             if (!s->parent && global.errors)
3425                 return NULL;
3426             if (!s->parent && s->getType())
3427             {   Dsymbol *s2 = s->getType()->toDsymbol(sc);
3428                 if (!s2)
3429                 {
3430                     error("%s is not a template declaration, it is a %s", id->toChars(), s->kind());
3431                     return NULL;
3432                 }
3433                 s = s2;
3434             }
3435 #ifdef DEBUG
3436             //if (!s->parent) printf("s = %s %s\n", s->kind(), s->toChars());
3437 #endif
3438             //assert(s->parent);
3439             TemplateInstance *ti = s->parent ? s->parent->isTemplateInstance() : NULL;
3440             if (ti &&
3441                 (ti->name == id ||
3442                  ti->toAlias()->ident == id)
3443                 &&
3444                 ti->tempdecl)
3445             {
3446                 /* This is so that one can refer to the enclosing
3447                  * template, even if it has the same name as a member
3448                  * of the template, if it has a !(arguments)
3449                  */
3450                 tempdecl = ti->tempdecl;
3451                 if (tempdecl->overroot)         // if not start of overloaded list of TemplateDeclaration's
3452                     tempdecl = tempdecl->overroot; // then get the start
3453             }
3454             else
3455             {
3456                 error("%s is not a template declaration, it is a %s", id->toChars(), s->kind());
3457                 return NULL;
3458             }
3459         }
3460     }
3461     else
3462         assert(tempdecl->isTemplateDeclaration());
3463     return tempdecl;
3464 }
3465
3466 TemplateDeclaration *TemplateInstance::findBestMatch(Scope *sc)
3467 {
3468     /* Since there can be multiple TemplateDeclaration's with the same
3469      * name, look for the best match.
3470      */
3471     TemplateDeclaration *td_ambig = NULL;
3472     TemplateDeclaration *td_best = NULL;
3473     MATCH m_best = MATCHnomatch;
3474     Objects dedtypes;
3475
3476 #if LOG
3477     printf("TemplateInstance::findBestMatch()\n");
3478 #endif
3479     for (TemplateDeclaration *td = tempdecl; td; td = td->overnext)
3480     {
3481         MATCH m;
3482
3483 //if (tiargs->dim) printf("2: tiargs->dim = %d, data[0] = %p\n", tiargs->dim, tiargs->data[0]);
3484
3485         // If more arguments than parameters,
3486         // then this is no match.
3487         if (td->parameters->dim < tiargs->dim)
3488         {
3489             if (!td->isVariadic())
3490                 continue;
3491         }
3492
3493         dedtypes.setDim(td->parameters->dim);
3494         dedtypes.zero();
3495         if (!td->scope)
3496         {
3497             error("forward reference to template declaration %s", td->toChars());
3498             return NULL;
3499         }
3500         m = td->matchWithInstance(this, &dedtypes, 0);
3501         //printf("m = %d\n", m);
3502         if (!m)                 // no match at all
3503             continue;
3504
3505 #if 1
3506         if (m < m_best)
3507             goto Ltd_best;
3508         if (m > m_best)
3509             goto Ltd;
3510 #else
3511         if (!m_best)
3512             goto Ltd;
3513 #endif
3514         {
3515         // Disambiguate by picking the most specialized TemplateDeclaration
3516         MATCH c1 = td->leastAsSpecialized(td_best);
3517         MATCH c2 = td_best->leastAsSpecialized(td);
3518         //printf("c1 = %d, c2 = %d\n", c1, c2);
3519
3520         if (c1 > c2)
3521             goto Ltd;
3522         else if (c1 < c2)
3523             goto Ltd_best;
3524         else
3525             goto Lambig;
3526         }
3527
3528       Lambig:           // td_best and td are ambiguous
3529         td_ambig = td;
3530         continue;
3531
3532       Ltd_best:         // td_best is the best match so far
3533         td_ambig = NULL;
3534         continue;
3535
3536       Ltd:              // td is the new best match
3537         td_ambig = NULL;
3538         td_best = td;
3539         m_best = m;
3540         tdtypes.setDim(dedtypes.dim);
3541         memcpy(tdtypes.data, dedtypes.data, tdtypes.dim * sizeof(void *));
3542         continue;
3543     }
3544
3545     if (!td_best)
3546     {
3547         error("%s does not match any template declaration", toChars());
3548         return NULL;
3549     }
3550     if (td_ambig)
3551     {
3552         error("%s matches more than one template declaration, %s and %s",
3553                 toChars(), td_best->toChars(), td_ambig->toChars());
3554     }
3555
3556     /* The best match is td_best
3557      */
3558     tempdecl = td_best;
3559
3560 #if 0
3561     /* Cast any value arguments to be same type as value parameter
3562      */
3563     for (size_t i = 0; i < tiargs->dim; i++)
3564     {   Object *o = (Object *)tiargs->data[i];
3565         Expression *ea = isExpression(o);       // value argument
3566         TemplateParameter *tp = (TemplateParameter *)tempdecl->parameters->data[i];
3567         assert(tp);
3568         TemplateValueParameter *tvp = tp->isTemplateValueParameter();
3569         if (tvp)
3570         {
3571             assert(ea);
3572             ea = ea->castTo(tvp->valType);
3573             ea = ea->optimize(WANTvalue | WANTinterpret);
3574             tiargs->data[i] = (Object *)ea;
3575         }
3576     }
3577 #endif
3578
3579 #if LOG
3580     printf("\tIt's a match with template declaration '%s'\n", tempdecl->toChars());
3581 #endif
3582     return tempdecl;
3583 }
3584
3585
3586 /*****************************************
3587  * Determines if a TemplateInstance will need a nested
3588  * generation of the TemplateDeclaration.
3589  */
3590
3591 int TemplateInstance::isNested(Objects *args)
3592 {   int nested = 0;
3593     //printf("TemplateInstance::isNested('%s')\n", tempdecl->ident->toChars());
3594
3595     /* A nested instance happens when an argument references a local
3596      * symbol that is on the stack.
3597      */
3598     for (size_t i = 0; i < args->dim; i++)
3599     {   Object *o = (Object *)args->data[i];
3600         Expression *ea = isExpression(o);
3601         Dsymbol *sa = isDsymbol(o);
3602         Tuple *va = isTuple(o);
3603         if (ea)
3604         {
3605             if (ea->op == TOKvar)
3606             {
3607                 sa = ((VarExp *)ea)->var;
3608                 goto Lsa;
3609             }
3610             if (ea->op == TOKfunction)
3611             {
3612                 sa = ((FuncExp *)ea)->fd;
3613                 goto Lsa;
3614             }
3615         }
3616         else if (sa)
3617         {
3618           Lsa:
3619             Declaration *d = sa->isDeclaration();
3620             if (d && !d->isDataseg() &&
3621 #if V2
3622                 !(d->storage_class & STCmanifest) &&
3623 #endif
3624                 (!d->isFuncDeclaration() || d->isFuncDeclaration()->isNested()) &&
3625                 !isTemplateMixin())
3626             {
3627                 // if module level template
3628                 if (tempdecl->toParent()->isModule())
3629                 {   Dsymbol *dparent = d->toParent();
3630                     if (!isnested)
3631                         isnested = dparent;
3632                     else if (isnested != dparent)
3633                     {
3634                         /* Select the more deeply nested of the two.
3635                          * Error if one is not nested inside the other.
3636                          */
3637                         for (Dsymbol *p = isnested; p; p = p->parent)
3638                         {
3639                             if (p == dparent)
3640                                 goto L1;        // isnested is most nested
3641                         }
3642                         for (Dsymbol *p = dparent; 1; p = p->parent)
3643                         {
3644                             if (p == isnested)
3645                             {   isnested = dparent;
3646                                 goto L1;        // dparent is most nested
3647                             }
3648                         }
3649                         error("is nested in both %s and %s", isnested->toChars(), dparent->toChars());
3650                     }
3651                   L1:
3652                     //printf("\tnested inside %s\n", isnested->toChars());
3653                     nested |= 1;
3654                 }
3655                 else
3656                     error("cannot use local '%s' as template parameter", d->toChars());
3657             }
3658         }
3659         else if (va)
3660         {
3661             nested |= isNested(&va->objects);
3662         }
3663     }
3664     return nested;
3665 }
3666
3667 /****************************************
3668  * This instance needs an identifier for name mangling purposes.
3669  * Create one by taking the template declaration name and adding
3670  * the type signature for it.
3671  */
3672
3673 Identifier *TemplateInstance::genIdent()
3674 {   OutBuffer buf;
3675     char *id;
3676     Objects *args;
3677
3678     //printf("TemplateInstance::genIdent('%s')\n", tempdecl->ident->toChars());
3679     id = tempdecl->ident->toChars();
3680     buf.printf("__T%"PRIuSIZE"%s", strlen(id), id);
3681     args = tiargs;
3682     for (int i = 0; i < args->dim; i++)
3683     {   Object *o = (Object *)args->data[i];
3684         Type *ta = isType(o);
3685         Expression *ea = isExpression(o);
3686         Dsymbol *sa = isDsymbol(o);
3687         Tuple *va = isTuple(o);
3688         //printf("\to %p ta %p ea %p sa %p va %p\n", o, ta, ea, sa, va);
3689         if (ta)
3690         {
3691             buf.writeByte('T');
3692             if (ta->deco)
3693                 buf.writestring(ta->deco);
3694             else
3695             {
3696 #ifdef DEBUG
3697                 printf("ta = %d, %s\n", ta->ty, ta->toChars());
3698 #endif
3699                 assert(global.errors);
3700             }
3701         }
3702         else if (ea)
3703         {   sinteger_t v;
3704             real_t r;
3705
3706             ea = ea->optimize(WANTvalue | WANTinterpret);
3707             if (ea->op == TOKvar)
3708             {
3709                 sa = ((VarExp *)ea)->var;
3710                 ea = NULL;
3711                 goto Lsa;
3712             }
3713             if (ea->op == TOKfunction)
3714             {
3715                 sa = ((FuncExp *)ea)->fd;
3716                 ea = NULL;
3717                 goto Lsa;
3718             }
3719             buf.writeByte('V');
3720             if (ea->op == TOKtuple)
3721             {   ea->error("tuple is not a valid template value argument");
3722                 continue;
3723             }
3724 #if 1
3725             /* Use deco that matches what it would be for a function parameter
3726              */
3727             //buf.writestring(ea->type->toHeadMutable()->deco);
3728             buf.writestring(ea->type->deco);
3729 #else
3730             // Use type of parameter, not type of argument
3731             TemplateParameter *tp = (TemplateParameter *)tempdecl->parameters->data[i];
3732             assert(tp);
3733             TemplateValueParameter *tvp = tp->isTemplateValueParameter();
3734             assert(tvp);
3735             buf.writestring(tvp->valType->deco);
3736 #endif
3737             ea->toMangleBuffer(&buf);
3738         }
3739         else if (sa)
3740         {
3741           Lsa:
3742             buf.writeByte('S');
3743             Declaration *d = sa->isDeclaration();
3744             if (d && !d->type->deco)
3745                 error("forward reference of %s", d->toChars());
3746             else
3747             {
3748                 char *p = sa->mangle();
3749                 buf.printf("%"PRIuSIZE"%s", strlen(p), p);
3750             }
3751         }
3752         else if (va)
3753         {
3754             assert(i + 1 == args->dim);         // must be last one
3755             args = &va->objects;
3756             i = -1;
3757         }
3758         else
3759             assert(0);
3760     }
3761     buf.writeByte('Z');
3762     id = buf.toChars();
3763     buf.data = NULL;
3764     return new Identifier(id, TOKidentifier);
3765 }
3766
3767
3768 /****************************************************
3769  * Declare parameters of template instance, initialize them with the
3770  * template instance arguments.
3771  */
3772
3773 void TemplateInstance::declareParameters(Scope *scope)
3774 {
3775     //printf("TemplateInstance::declareParameters()\n");
3776     for (int i = 0; i < tdtypes.dim; i++)
3777     {
3778         TemplateParameter *tp = (TemplateParameter *)tempdecl->parameters->data[i];
3779         //Object *o = (Object *)tiargs->data[i];
3780         Object *o = (Object *)tdtypes.data[i];
3781
3782         //printf("\ttdtypes[%d] = %p\n", i, o);
3783         tempdecl->declareParameter(scope, tp, o);
3784     }
3785 }
3786
3787
3788 void TemplateInstance::semantic2(Scope *sc)
3789 {   int i;
3790
3791     if (semanticdone >= 2)
3792         return;
3793     semanticdone = 2;
3794 #if LOG
3795     printf("+TemplateInstance::semantic2('%s')\n", toChars());
3796 #endif
3797     if (!errors && members)
3798     {
3799         sc = tempdecl->scope;
3800         assert(sc);
3801         sc = sc->push(argsym);
3802         sc = sc->push(this);
3803         for (i = 0; i < members->dim; i++)
3804         {
3805             Dsymbol *s = (Dsymbol *)members->data[i];
3806 #if LOG
3807 printf("\tmember '%s', kind = '%s'\n", s->toChars(), s->kind());
3808 #endif
3809             s->semantic2(sc);
3810         }
3811         sc = sc->pop();
3812         sc->pop();
3813     }
3814 #if LOG
3815     printf("-TemplateInstance::semantic2('%s')\n", toChars());
3816 #endif
3817 }
3818
3819 void TemplateInstance::semantic3(Scope *sc)
3820 {
3821 #if LOG
3822     printf("TemplateInstance::semantic3('%s'), semanticdone = %d\n", toChars(), semanticdone);
3823 #endif
3824 //if (toChars()[0] == 'D') *(char*)0=0;
3825     if (semanticdone >= 3)
3826         return;
3827     semanticdone = 3;
3828     if (!errors && members)
3829     {
3830         sc = tempdecl->scope;
3831         sc = sc->push(argsym);
3832         sc = sc->push(this);
3833         sc->fromDcode = !tempdecl->dltSource;
3834         for (int i = 0; i < members->dim; i++)
3835         {
3836             Dsymbol *s = (Dsymbol *)members->data[i];
3837             s->semantic3(sc);
3838         }
3839         sc = sc->pop();
3840         sc->pop();
3841     }
3842 }
3843
3844 void TemplateInstance::toObjFile(int multiobj)
3845 {
3846 #if LOG
3847     printf("TemplateInstance::toObjFile('%s', this = %p)\n", toChars(), this);
3848 #endif
3849     if (!errors && members)
3850     {
3851         if (multiobj)
3852             // Append to list of object files to be written later
3853             obj_append(this);
3854         else
3855         {
3856             for (int i = 0; i < members->dim; i++)
3857             {
3858                 Dsymbol *s = (Dsymbol *)members->data[i];
3859                 s->toObjFile(multiobj);
3860             }
3861         }
3862     }
3863 }
3864
3865 void TemplateInstance::inlineScan()
3866 {
3867 #if LOG
3868     printf("TemplateInstance::inlineScan('%s')\n", toChars());
3869 #endif
3870     if (!errors && members)
3871     {
3872         for (int i = 0; i < members->dim; i++)
3873         {
3874             Dsymbol *s = (Dsymbol *)members->data[i];
3875             s->inlineScan();
3876         }
3877     }
3878 }
3879
3880 void TemplateInstance::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
3881 {
3882     int i;
3883
3884     Identifier *id = name;
3885     buf->writestring(id->toChars());
3886     buf->writestring("!(");
3887     if (nest)
3888         buf->writestring("...");
3889     else
3890     {
3891         nest++;
3892         Objects *args = tiargs;
3893         for (i = 0; i < args->dim; i++)
3894         {
3895             if (i)
3896                 buf->writeByte(',');
3897             Object *oarg = (Object *)args->data[i];
3898             ObjectToCBuffer(buf, hgs, oarg);
3899         }
3900         nest--;
3901     }
3902     buf->writeByte(')');
3903 }
3904
3905
3906 Dsymbol *TemplateInstance::toAlias()
3907 {
3908 #if LOG
3909     printf("TemplateInstance::toAlias()\n");
3910 #endif
3911     if (!inst)
3912     {   error("cannot resolve forward reference");
3913         return this;
3914     }
3915
3916     if (inst != this)
3917         return inst->toAlias();
3918
3919     if (aliasdecl)
3920         return aliasdecl->toAlias();
3921
3922     return inst;
3923 }
3924
3925 AliasDeclaration *TemplateInstance::isAliasDeclaration()
3926 {
3927     return aliasdecl;
3928 }
3929
3930 char *TemplateInstance::kind()
3931 {
3932     return "template instance";
3933 }
3934
3935 int TemplateInstance::oneMember(Dsymbol **ps)
3936 {
3937     *ps = NULL;
3938     return TRUE;
3939 }
3940
3941 char *TemplateInstance::toChars()
3942 {
3943     OutBuffer buf;
3944     HdrGenState hgs;
3945     char *s;
3946
3947     toCBuffer(&buf, &hgs);
3948     s = buf.toChars();
3949     buf.data = NULL;
3950     return s;
3951 }
3952
3953 /* ======================== TemplateMixin ================================ */
3954
3955 TemplateMixin::TemplateMixin(Loc loc, Identifier *ident, Type *tqual,
3956         Array *idents, Objects *tiargs)
3957         : TemplateInstance(loc, (Identifier *)idents->data[idents->dim - 1])
3958 {
3959     //printf("TemplateMixin(ident = '%s')\n", ident ? ident->toChars() : "");
3960     this->ident = ident;
3961     this->tqual = tqual;
3962     this->idents = idents;
3963     this->tiargs = tiargs ? tiargs : new Objects();
3964     this->scope = NULL;
3965 }
3966
3967 Dsymbol *TemplateMixin::syntaxCopy(Dsymbol *s)
3968 {   TemplateMixin *tm;
3969
3970     Array *ids = new Array();
3971     ids->setDim(idents->dim);
3972     for (int i = 0; i < idents->dim; i++)
3973     {   // Matches TypeQualified::syntaxCopyHelper()
3974         Identifier *id = (Identifier *)idents->data[i];
3975         if (id->dyncast() == DYNCAST_DSYMBOL)
3976         {
3977             TemplateInstance *ti = (TemplateInstance *)id;
3978
3979             ti = (TemplateInstance *)ti->syntaxCopy(NULL);
3980             id = (Identifier *)ti;
3981         }
3982         ids->data[i] = id;
3983     }
3984
3985     tm = new TemplateMixin(loc, ident,
3986                 (Type *)(tqual ? tqual->syntaxCopy() : NULL),
3987                 ids, tiargs);
3988     TemplateInstance::syntaxCopy(tm);
3989     return tm;
3990 }
3991
3992 void TemplateMixin::semantic(Scope *sc)
3993 {
3994 #if LOG
3995     printf("+TemplateMixin::semantic('%s', this=%p)\n", toChars(), this);
3996     fflush(stdout);
3997 #endif
3998     if (semanticdone &&
3999         // This for when a class/struct contains mixin members, and
4000         // is done over because of forward references
4001         (!parent || !toParent()->isAggregateDeclaration()))
4002     {
4003 #if LOG
4004         printf("\tsemantic done\n");
4005 #endif
4006         return;
4007     }
4008     if (!semanticdone)
4009         semanticdone = 1;
4010 #if LOG
4011     printf("\tdo semantic\n");
4012 #endif
4013
4014     Scope *scx = NULL;
4015     if (scope)
4016     {   sc = scope;
4017         scx = scope;            // save so we don't make redundant copies
4018         scope = NULL;
4019     }
4020
4021     // Follow qualifications to find the TemplateDeclaration
4022     if (!tempdecl)
4023     {   Dsymbol *s;
4024         int i;
4025         Identifier *id;
4026
4027         if (tqual)
4028         {   s = tqual->toDsymbol(sc);
4029             i = 0;
4030         }
4031         else
4032         {
4033             i = 1;
4034             id = (Identifier *)idents->data[0];
4035             switch (id->dyncast())
4036             {
4037                 case DYNCAST_IDENTIFIER:
4038                     s = sc->search(loc, id, NULL);
4039                     break;
4040
4041                 case DYNCAST_DSYMBOL:
4042                 {
4043                     TemplateInstance *ti = (TemplateInstance *)id;
4044                     ti->semantic(sc);
4045                     s = ti;
4046                     break;
4047                 }
4048                 default:
4049                     assert(0);
4050             }
4051         }
4052
4053         for (; i < idents->dim; i++)
4054         {
4055             if (!s)
4056                 break;
4057             id = (Identifier *)idents->data[i];
4058             s = s->searchX(loc, sc, id);
4059         }
4060         if (!s)
4061         {
4062             error("is not defined");
4063             inst = this;
4064             return;
4065         }
4066         tempdecl = s->toAlias()->isTemplateDeclaration();
4067         if (!tempdecl)
4068         {
4069             error("%s isn't a template", s->toChars());
4070             inst = this;
4071             return;
4072         }
4073     }
4074
4075     // Look for forward reference
4076     assert(tempdecl);
4077     for (TemplateDeclaration *td = tempdecl; td; td = td->overnext)
4078     {
4079         if (!td->scope)
4080         {
4081             /* Cannot handle forward references if mixin is a struct member,
4082              * because addField must happen during struct's semantic, not
4083              * during the mixin semantic.
4084              * runDeferred will re-run mixin's semantic outside of the struct's
4085              * semantic.
4086              */
4087             semanticdone = 0;
4088             AggregateDeclaration *ad = toParent()->isAggregateDeclaration();
4089             if (ad)
4090                 ad->sizeok = 2;
4091             else
4092             {
4093                 // Forward reference
4094                 //printf("forward reference - deferring\n");
4095                 scope = scx ? scx : new Scope(*sc);
4096                 scope->setNoFree();
4097                 scope->module->addDeferredSemantic(this);
4098             }
4099             return;
4100         }
4101     }
4102
4103     // Run semantic on each argument, place results in tiargs[]
4104     semanticTiargs(sc);
4105
4106     tempdecl = findBestMatch(sc);
4107     if (!tempdecl)
4108     {   inst = this;
4109         return;         // error recovery
4110     }
4111
4112     if (!ident)
4113         ident = genIdent();
4114
4115     inst = this;
4116     parent = sc->parent;
4117
4118     /* Detect recursive mixin instantiations.
4119      */
4120     for (Dsymbol *s = parent; s; s = s->parent)
4121     {
4122         //printf("\ts = '%s'\n", s->toChars());
4123         TemplateMixin *tm = s->isTemplateMixin();
4124         if (!tm || tempdecl != tm->tempdecl)
4125             continue;
4126
4127         for (int i = 0; i < tiargs->dim; i++)
4128         {   Object *o = (Object *)tiargs->data[i];
4129             Type *ta = isType(o);
4130             Expression *ea = isExpression(o);
4131             Dsymbol *sa = isDsymbol(o);
4132             Object *tmo = (Object *)tm->tiargs->data[i];
4133             if (ta)
4134             {
4135                 Type *tmta = isType(tmo);
4136                 if (!tmta)
4137                     goto Lcontinue;
4138                 if (!ta->equals(tmta))
4139                     goto Lcontinue;
4140             }
4141             else if (ea)
4142             {   Expression *tme = isExpression(tmo);
4143                 if (!tme || !ea->equals(tme))
4144                     goto Lcontinue;
4145             }
4146             else if (sa)
4147             {
4148                 Dsymbol *tmsa = isDsymbol(tmo);
4149                 if (sa != tmsa)
4150                     goto Lcontinue;
4151             }
4152             else
4153                 assert(0);
4154         }
4155         error("recursive mixin instantiation");
4156         return;
4157
4158     Lcontinue:
4159         continue;
4160     }
4161
4162     // Copy the syntax trees from the TemplateDeclaration
4163     members = Dsymbol::arraySyntaxCopy(tempdecl->members);
4164     if (!members)
4165         return;
4166
4167     symtab = new DsymbolTable();
4168
4169     for (Scope *sce = sc; 1; sce = sce->enclosing)
4170     {
4171         ScopeDsymbol *sds = (ScopeDsymbol *)sce->scopesym;
4172         if (sds)
4173         {
4174             sds->importScope(this, PROTpublic);
4175             break;
4176         }
4177     }
4178
4179 #if LOG
4180     printf("\tcreate scope for template parameters '%s'\n", toChars());
4181 #endif
4182     Scope *scy = sc;
4183     scy = sc->push(this);
4184     scy->parent = this;
4185
4186     argsym = new ScopeDsymbol();
4187     argsym->parent = scy->parent;
4188     Scope *scope = scy->push(argsym);
4189
4190     unsigned errorsave = global.errors;
4191
4192     // Declare each template parameter as an alias for the argument type
4193     declareParameters(scope);
4194
4195     // Add members to enclosing scope, as well as this scope
4196     for (unsigned i = 0; i < members->dim; i++)
4197     {   Dsymbol *s;
4198
4199         s = (Dsymbol *)members->data[i];
4200         s->addMember(scope, this, i);
4201         //sc->insert(s);
4202         //printf("sc->parent = %p, sc->scopesym = %p\n", sc->parent, sc->scopesym);
4203         //printf("s->parent = %s\n", s->parent->toChars());
4204     }
4205
4206     // Do semantic() analysis on template instance members
4207 #if LOG
4208     printf("\tdo semantic() on template instance members '%s'\n", toChars());
4209 #endif
4210     Scope *sc2;
4211     sc2 = scope->push(this);
4212     sc2->offset = sc->offset;
4213     for (int i = 0; i < members->dim; i++)
4214     {
4215         Dsymbol *s = (Dsymbol *)members->data[i];
4216         s->semantic(sc2);
4217     }
4218     sc->offset = sc2->offset;
4219
4220     /* The problem is when to parse the initializer for a variable.
4221      * Perhaps VarDeclaration::semantic() should do it like it does
4222      * for initializers inside a function.
4223      */
4224 //    if (sc->parent->isFuncDeclaration())
4225
4226         semantic2(sc2);
4227
4228     if (sc->func)
4229     {
4230         semantic3(sc2);
4231     }
4232
4233     // Give additional context info if error occurred during instantiation
4234     if (global.errors != errorsave)
4235     {
4236         error("error instantiating");
4237     }
4238
4239     sc2->pop();
4240
4241     scope->pop();
4242
4243 //    if (!isAnonymous())
4244     {
4245         scy->pop();
4246     }
4247 #if LOG
4248     printf("-TemplateMixin::semantic('%s', this=%p)\n", toChars(), this);
4249 #endif
4250 }
4251
4252 void TemplateMixin::semantic2(Scope *sc)
4253 {   int i;
4254
4255     if (semanticdone >= 2)
4256         return;
4257     semanticdone = 2;
4258 #if LOG
4259     printf("+TemplateMixin::semantic2('%s')\n", toChars());
4260 #endif
4261     if (members)
4262     {
4263         assert(sc);
4264         sc = sc->push(argsym);
4265         sc = sc->push(this);
4266         for (i = 0; i < members->dim; i++)
4267         {
4268             Dsymbol *s = (Dsymbol *)members->data[i];
4269 #if LOG
4270             printf("\tmember '%s', kind = '%s'\n", s->toChars(), s->kind());
4271 #endif
4272             s->semantic2(sc);
4273         }
4274         sc = sc->pop();
4275         sc->pop();
4276     }
4277 #if LOG
4278     printf("-TemplateMixin::semantic2('%s')\n", toChars());
4279 #endif
4280 }
4281
4282 void TemplateMixin::semantic3(Scope *sc)
4283 {   int i;
4284
4285     if (semanticdone >= 3)
4286         return;
4287     semanticdone = 3;
4288 #if LOG
4289     printf("TemplateMixin::semantic3('%s')\n", toChars());
4290 #endif
4291     if (members)
4292     {
4293         sc = sc->push(argsym);
4294         sc = sc->push(this);
4295         for (i = 0; i < members->dim; i++)
4296         {
4297             Dsymbol *s = (Dsymbol *)members->data[i];
4298             s->semantic3(sc);
4299         }
4300         sc = sc->pop();
4301         sc->pop();
4302     }
4303 }
4304
4305 void TemplateMixin::inlineScan()
4306 {
4307     TemplateInstance::inlineScan();
4308 }
4309
4310 char *TemplateMixin::kind()
4311 {
4312     return "mixin";
4313 }
4314
4315 int TemplateMixin::oneMember(Dsymbol **ps)
4316 {
4317     return Dsymbol::oneMember(ps);
4318 }
4319
4320 int TemplateMixin::hasPointers()
4321 {
4322     //printf("TemplateMixin::hasPointers() %s\n", toChars());
4323     for (size_t i = 0; i < members->dim; i++)
4324     {
4325         Dsymbol *s = (Dsymbol *)members->data[i];
4326         //printf(" s = %s %s\n", s->kind(), s->toChars());
4327         if (s->hasPointers())
4328         {
4329             return 1;
4330         }
4331     }
4332     return 0;
4333 }
4334
4335 char *TemplateMixin::toChars()
4336 {
4337     OutBuffer buf;
4338     HdrGenState hgs;
4339     char *s;
4340
4341     TemplateInstance::toCBuffer(&buf, &hgs);
4342     s = buf.toChars();
4343     buf.data = NULL;
4344     return s;
4345 }
4346
4347 void TemplateMixin::toCBuffer(OutBuffer *buf, HdrGenState *hgs)
4348 {
4349     buf->writestring("mixin ");
4350     int i;
4351     for (i = 0; i < idents->dim; i++)
4352     {   Identifier *id = (Identifier *)idents->data[i];
4353
4354         if (i)
4355             buf->writeByte('.');
4356         buf->writestring(id->toChars());
4357     }
4358     buf->writestring("!(");
4359     if (tiargs)
4360     {
4361         for (i = 0; i < tiargs->dim; i++)
4362         {   if (i)
4363                 buf->writebyte(',');
4364             Object *oarg = (Object *)tiargs->data[i];
4365             Type *t = isType(oarg);
4366             Expression *e = isExpression(oarg);
4367             Dsymbol *s = isDsymbol(oarg);
4368             if (t)
4369                 t->toCBuffer(buf, NULL, hgs);
4370             else if (e)
4371                 e->toCBuffer(buf, hgs);
4372             else if (s)
4373             {
4374                 char *p = s->ident ? s->ident->toChars() : s->toChars();
4375                 buf->writestring(p);
4376             }
4377             else if (!oarg)
4378             {
4379                 buf->writestring("NULL");
4380             }
4381             else
4382             {
4383                 assert(0);
4384             }
4385         }
4386     }
4387     buf->writebyte(')');
4388     buf->writebyte(';');
4389     buf->writenl();
4390 }
4391
4392
4393 void TemplateMixin::toObjFile(int multiobj)
4394 {
4395     //printf("TemplateMixin::toObjFile('%s')\n", toChars());
4396     TemplateInstance::toObjFile(multiobj);
4397 }
4398