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