dmd/template.c

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