1
2 /* Compiler implementation of the D programming language
3 * Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
4 * written by Walter Bright
5 * http://www.digitalmars.com
6 * Distributed under the Boost Software License, Version 1.0.
7 * http://www.boost.org/LICENSE_1_0.txt
8 * https://github.com/D-Programming-Language/dmd/blob/master/src/template.c
9 */
10
11 // Handle template implementation
12
13 #include "root/dsystem.h"
14 #include "root/root.h"
15 #include "root/aav.h"
16 #include "root/rmem.h"
17 #include "root/stringtable.h"
18 #include "root/hash.h"
19
20 #include "mangle.h"
21 #include "mtype.h"
22 #include "template.h"
23 #include "init.h"
24 #include "expression.h"
25 #include "scope.h"
26 #include "module.h"
27 #include "aggregate.h"
28 #include "declaration.h"
29 #include "dsymbol.h"
30 #include "mars.h"
31 #include "dsymbol.h"
32 #include "identifier.h"
33 #include "hdrgen.h"
34 #include "id.h"
35 #include "attrib.h"
36 #include "cond.h"
37 #include "tokens.h"
38
39 #define IDX_NOTFOUND (0x12345678) // index is not found
40
41 Type *rawTypeMerge(Type *t1, Type *t2);
42 bool MODimplicitConv(MOD modfrom, MOD modto);
43 MATCH MODmethodConv(MOD modfrom, MOD modto);
44 MOD MODmerge(MOD mod1, MOD mod2);
45
46 static size_t templateParameterLookup(Type *tparam, TemplateParameters *parameters);
47 static int arrayObjectMatch(Objects *oa1, Objects *oa2);
48 static unsigned char deduceWildHelper(Type *t, Type **at, Type *tparam);
49 static MATCH deduceTypeHelper(Type *t, Type **at, Type *tparam);
50 bool reliesOnTident(Type *t, TemplateParameters *tparams = NULL, size_t iStart = 0);
51 bool evalStaticCondition(Scope *sc, Expression *exp, Expression *e, bool &errors);
52
53 /********************************************
54 * These functions substitute for dynamic_cast. dynamic_cast does not work
55 * on earlier versions of gcc.
56 */
57
isExpression(RootObject * o)58 Expression *isExpression(RootObject *o)
59 {
60 //return dynamic_cast<Expression *>(o);
61 if (!o || o->dyncast() != DYNCAST_EXPRESSION)
62 return NULL;
63 return (Expression *)o;
64 }
65
isDsymbol(RootObject * o)66 Dsymbol *isDsymbol(RootObject *o)
67 {
68 //return dynamic_cast<Dsymbol *>(o);
69 if (!o || o->dyncast() != DYNCAST_DSYMBOL)
70 return NULL;
71 return (Dsymbol *)o;
72 }
73
isType(RootObject * o)74 Type *isType(RootObject *o)
75 {
76 //return dynamic_cast<Type *>(o);
77 if (!o || o->dyncast() != DYNCAST_TYPE)
78 return NULL;
79 return (Type *)o;
80 }
81
isTuple(RootObject * o)82 Tuple *isTuple(RootObject *o)
83 {
84 //return dynamic_cast<Tuple *>(o);
85 if (!o || o->dyncast() != DYNCAST_TUPLE)
86 return NULL;
87 return (Tuple *)o;
88 }
89
isParameter(RootObject * o)90 Parameter *isParameter(RootObject *o)
91 {
92 //return dynamic_cast<Parameter *>(o);
93 if (!o || o->dyncast() != DYNCAST_PARAMETER)
94 return NULL;
95 return (Parameter *)o;
96 }
97
98 /**************************************
99 * Is this Object an error?
100 */
isError(RootObject * o)101 bool isError(RootObject *o)
102 {
103 Type *t = isType(o);
104 if (t)
105 return (t->ty == Terror);
106 Expression *e = isExpression(o);
107 if (e)
108 return (e->op == TOKerror || !e->type || e->type->ty == Terror);
109 Tuple *v = isTuple(o);
110 if (v)
111 return arrayObjectIsError(&v->objects);
112 Dsymbol *s = isDsymbol(o);
113 assert(s);
114 if (s->errors)
115 return true;
116 return s->parent ? isError(s->parent) : false;
117 }
118
119 /**************************************
120 * Are any of the Objects an error?
121 */
arrayObjectIsError(Objects * args)122 bool arrayObjectIsError(Objects *args)
123 {
124 for (size_t i = 0; i < args->length; i++)
125 {
126 RootObject *o = (*args)[i];
127 if (isError(o))
128 return true;
129 }
130 return false;
131 }
132
133 /***********************
134 * Try to get arg as a type.
135 */
136
getType(RootObject * o)137 Type *getType(RootObject *o)
138 {
139 Type *t = isType(o);
140 if (!t)
141 {
142 Expression *e = isExpression(o);
143 if (e)
144 t = e->type;
145 }
146 return t;
147 }
148
getDsymbol(RootObject * oarg)149 Dsymbol *getDsymbol(RootObject *oarg)
150 {
151 //printf("getDsymbol()\n");
152 //printf("e %p s %p t %p v %p\n", isExpression(oarg), isDsymbol(oarg), isType(oarg), isTuple(oarg));
153
154 Dsymbol *sa;
155 Expression *ea = isExpression(oarg);
156 if (ea)
157 {
158 // Try to convert Expression to symbol
159 if (VarExp *ve = ea->isVarExp())
160 sa = ve->var;
161 else if (FuncExp *fe = ea->isFuncExp())
162 sa = fe->td ? (Dsymbol *)fe->td : (Dsymbol *)fe->fd;
163 else if (TemplateExp *te = ea->isTemplateExp())
164 sa = te->td;
165 else if (ScopeExp *se = ea->isScopeExp())
166 sa = se->sds;
167 else
168 sa = NULL;
169 }
170 else
171 {
172 // Try to convert Type to symbol
173 Type *ta = isType(oarg);
174 if (ta)
175 sa = ta->toDsymbol(NULL);
176 else
177 sa = isDsymbol(oarg); // if already a symbol
178 }
179 return sa;
180 }
181
182 /***********************
183 * Try to get value from manifest constant
184 */
185
getValue(Expression * e)186 static Expression *getValue(Expression *e)
187 {
188 if (e && e->op == TOKvar)
189 {
190 VarDeclaration *v = ((VarExp *)e)->var->isVarDeclaration();
191 if (v && v->storage_class & STCmanifest)
192 {
193 e = v->getConstInitializer();
194 }
195 }
196 return e;
197 }
198
getValue(Dsymbol * & s)199 static Expression *getValue(Dsymbol *&s)
200 {
201 Expression *e = NULL;
202 if (s)
203 {
204 VarDeclaration *v = s->isVarDeclaration();
205 if (v && v->storage_class & STCmanifest)
206 {
207 e = v->getConstInitializer();
208 }
209 }
210 return e;
211 }
212
213 /**********************************
214 * Return true if e could be valid only as a template value parameter.
215 * Return false if it might be an alias or tuple.
216 * (Note that even in this case, it could still turn out to be a value).
217 */
definitelyValueParameter(Expression * e)218 bool definitelyValueParameter(Expression *e)
219 {
220 // None of these can be value parameters
221 if (e->op == TOKtuple || e->op == TOKscope ||
222 e->op == TOKtype || e->op == TOKdottype ||
223 e->op == TOKtemplate || e->op == TOKdottd ||
224 e->op == TOKfunction || e->op == TOKerror ||
225 e->op == TOKthis || e->op == TOKsuper ||
226 e->op == TOKdot)
227 return false;
228
229 if (e->op != TOKdotvar)
230 return true;
231
232 /* Template instantiations involving a DotVar expression are difficult.
233 * In most cases, they should be treated as a value parameter, and interpreted.
234 * But they might also just be a fully qualified name, which should be treated
235 * as an alias.
236 */
237
238 // x.y.f cannot be a value
239 FuncDeclaration *f = ((DotVarExp *)e)->var->isFuncDeclaration();
240 if (f)
241 return false;
242
243 while (e->op == TOKdotvar)
244 {
245 e = ((DotVarExp *)e)->e1;
246 }
247 // this.x.y and super.x.y couldn't possibly be valid values.
248 if (e->op == TOKthis || e->op == TOKsuper)
249 return false;
250
251 // e.type.x could be an alias
252 if (e->op == TOKdottype)
253 return false;
254
255 // var.x.y is the only other possible form of alias
256 if (e->op != TOKvar)
257 return true;
258
259 VarDeclaration *v = ((VarExp *)e)->var->isVarDeclaration();
260
261 // func.x.y is not an alias
262 if (!v)
263 return true;
264
265 // TODO: Should we force CTFE if it is a global constant?
266
267 return false;
268 }
269
getExpression(RootObject * o)270 static Expression *getExpression(RootObject *o)
271 {
272 Dsymbol *s = isDsymbol(o);
273 return s ? getValue(s) : getValue(isExpression(o));
274 }
275
276 /******************************
277 * If o1 matches o2, return true.
278 * Else, return false.
279 */
280
match(RootObject * o1,RootObject * o2)281 static bool match(RootObject *o1, RootObject *o2)
282 {
283 //printf("match() o1 = %p %s (%d), o2 = %p %s (%d)\n",
284 // o1, o1->toChars(), o1->dyncast(), o2, o2->toChars(), o2->dyncast());
285
286 /* A proper implementation of the various equals() overrides
287 * should make it possible to just do o1->equals(o2), but
288 * we'll do that another day.
289 */
290
291 /* Manifest constants should be compared by their values,
292 * at least in template arguments.
293 */
294
295 if (Type *t1 = isType(o1))
296 {
297 Type *t2 = isType(o2);
298 if (!t2)
299 goto Lnomatch;
300
301 //printf("\tt1 = %s\n", t1->toChars());
302 //printf("\tt2 = %s\n", t2->toChars());
303 if (!t1->equals(t2))
304 goto Lnomatch;
305
306 goto Lmatch;
307 }
308 if (Expression *e1 = getExpression(o1))
309 {
310 Expression *e2 = getExpression(o2);
311 if (!e2)
312 goto Lnomatch;
313
314 //printf("\te1 = %s %s %s\n", e1->type->toChars(), Token::toChars(e1->op), e1->toChars());
315 //printf("\te2 = %s %s %s\n", e2->type->toChars(), Token::toChars(e2->op), e2->toChars());
316
317 // two expressions can be equal although they do not have the same
318 // type; that happens when they have the same value. So check type
319 // as well as expression equality to ensure templates are properly
320 // matched.
321 if (!e1->type->equals(e2->type) || !e1->equals(e2))
322 goto Lnomatch;
323
324 goto Lmatch;
325 }
326 if (Dsymbol *s1 = isDsymbol(o1))
327 {
328 Dsymbol *s2 = isDsymbol(o2);
329 if (!s2)
330 goto Lnomatch;
331
332 //printf("\ts1 = %s\n", s1->toChars());
333 //printf("\ts2 = %s\n", s2->toChars());
334 if (!s1->equals(s2))
335 goto Lnomatch;
336 if (s1->parent != s2->parent && !s1->isFuncDeclaration() && !s2->isFuncDeclaration())
337 goto Lnomatch;
338
339 goto Lmatch;
340 }
341 if (Tuple *u1 = isTuple(o1))
342 {
343 Tuple *u2 = isTuple(o2);
344 if (!u2)
345 goto Lnomatch;
346
347 //printf("\tu1 = %s\n", u1->toChars());
348 //printf("\tu2 = %s\n", u2->toChars());
349 if (!arrayObjectMatch(&u1->objects, &u2->objects))
350 goto Lnomatch;
351
352 goto Lmatch;
353 }
354 Lmatch:
355 //printf("\t-> match\n");
356 return true;
357
358 Lnomatch:
359 //printf("\t-> nomatch\n");
360 return false;
361 }
362
363
364 /************************************
365 * Match an array of them.
366 */
arrayObjectMatch(Objects * oa1,Objects * oa2)367 int arrayObjectMatch(Objects *oa1, Objects *oa2)
368 {
369 if (oa1 == oa2)
370 return 1;
371 if (oa1->length != oa2->length)
372 return 0;
373 for (size_t j = 0; j < oa1->length; j++)
374 {
375 RootObject *o1 = (*oa1)[j];
376 RootObject *o2 = (*oa2)[j];
377 if (!match(o1, o2))
378 {
379 return 0;
380 }
381 }
382 return 1;
383 }
384
385
386 /************************************
387 * Computes hash of expression.
388 * Handles all Expression classes and MUST match their equals method,
389 * i.e. e1->equals(e2) implies expressionHash(e1) == expressionHash(e2).
390 */
expressionHash(Expression * e)391 static hash_t expressionHash(Expression *e)
392 {
393 switch (e->op)
394 {
395 case TOKint64:
396 return (size_t) ((IntegerExp *)e)->getInteger();
397
398 case TOKfloat64:
399 return CTFloat::hash(((RealExp *)e)->value);
400
401 case TOKcomplex80:
402 {
403 ComplexExp *ce = (ComplexExp *)e;
404 return mixHash(CTFloat::hash(ce->toReal()), CTFloat::hash(ce->toImaginary()));
405 }
406
407 case TOKidentifier:
408 return (size_t)(void *) ((IdentifierExp *)e)->ident;
409
410 case TOKnull:
411 return (size_t)(void *) ((NullExp *)e)->type;
412
413 case TOKstring:
414 {
415 StringExp *se = (StringExp *)e;
416 return calcHash((const char *)se->string, se->len * se->sz);
417 }
418
419 case TOKtuple:
420 {
421 TupleExp *te = (TupleExp *)e;
422 size_t hash = 0;
423 hash += te->e0 ? expressionHash(te->e0) : 0;
424 for (size_t i = 0; i < te->exps->length; i++)
425 {
426 Expression *elem = (*te->exps)[i];
427 hash = mixHash(hash, expressionHash(elem));
428 }
429 return hash;
430 }
431
432 case TOKarrayliteral:
433 {
434 ArrayLiteralExp *ae = (ArrayLiteralExp *)e;
435 size_t hash = 0;
436 for (size_t i = 0; i < ae->elements->length; i++)
437 hash = mixHash(hash, expressionHash(ae->getElement(i)));
438 return hash;
439 }
440
441 case TOKassocarrayliteral:
442 {
443 AssocArrayLiteralExp *ae = (AssocArrayLiteralExp *)e;
444 size_t hash = 0;
445 for (size_t i = 0; i < ae->keys->length; i++)
446 // reduction needs associative op as keys are unsorted (use XOR)
447 hash ^= mixHash(expressionHash((*ae->keys)[i]), expressionHash((*ae->values)[i]));
448 return hash;
449 }
450
451 case TOKstructliteral:
452 {
453 StructLiteralExp *se = (StructLiteralExp *)e;
454 size_t hash = 0;
455 for (size_t i = 0; i < se->elements->length; i++)
456 {
457 Expression *elem = (*se->elements)[i];
458 hash = mixHash(hash, elem ? expressionHash(elem) : 0);
459 }
460 return hash;
461 }
462
463 case TOKvar:
464 return (size_t)(void *) ((VarExp *)e)->var;
465
466 case TOKfunction:
467 return (size_t)(void *) ((FuncExp *)e)->fd;
468
469 default:
470 // no custom equals for this expression
471 // equals based on identity
472 return (size_t)(void *) e;
473 }
474 }
475
476
477 /************************************
478 * Return hash of Objects.
479 */
arrayObjectHash(Objects * oa1)480 static hash_t arrayObjectHash(Objects *oa1)
481 {
482 hash_t hash = 0;
483 for (size_t j = 0; j < oa1->length; j++)
484 {
485 /* Must follow the logic of match()
486 */
487 RootObject *o1 = (*oa1)[j];
488 if (Type *t1 = isType(o1))
489 hash = mixHash(hash, (size_t)t1->deco);
490 else if (Expression *e1 = getExpression(o1))
491 hash = mixHash(hash, expressionHash(e1));
492 else if (Dsymbol *s1 = isDsymbol(o1))
493 {
494 FuncAliasDeclaration *fa1 = s1->isFuncAliasDeclaration();
495 if (fa1)
496 s1 = fa1->toAliasFunc();
497 hash = mixHash(hash, mixHash((size_t)(void *)s1->getIdent(), (size_t)(void *)s1->parent));
498 }
499 else if (Tuple *u1 = isTuple(o1))
500 hash = mixHash(hash, arrayObjectHash(&u1->objects));
501 }
502 return hash;
503 }
504
objectSyntaxCopy(RootObject * o)505 RootObject *objectSyntaxCopy(RootObject *o)
506 {
507 if (!o)
508 return NULL;
509 if (Type *t = isType(o))
510 return t->syntaxCopy();
511 if (Expression *e = isExpression(o))
512 return e->syntaxCopy();
513 return o;
514 }
515
516
517 /* ======================== TemplateDeclaration ============================= */
518
TemplateDeclaration(Loc loc,Identifier * id,TemplateParameters * parameters,Expression * constraint,Dsymbols * decldefs,bool ismixin,bool literal)519 TemplateDeclaration::TemplateDeclaration(Loc loc, Identifier *id,
520 TemplateParameters *parameters, Expression *constraint, Dsymbols *decldefs, bool ismixin, bool literal)
521 : ScopeDsymbol(id)
522 {
523 this->loc = loc;
524 this->parameters = parameters;
525 this->origParameters = parameters;
526 this->constraint = constraint;
527 this->members = decldefs;
528 this->overnext = NULL;
529 this->overroot = NULL;
530 this->funcroot = NULL;
531 this->onemember = NULL;
532 this->literal = literal;
533 this->ismixin = ismixin;
534 this->isstatic = true;
535 this->isTrivialAliasSeq = false;
536 this->isTrivialAlias = false;
537 this->previous = NULL;
538 this->protection = Prot(Prot::undefined);
539 this->inuse = 0;
540 this->instances = NULL;
541
542 // Compute in advance for Ddoc's use
543 // Bugzilla 11153: ident could be NULL if parsing fails.
544 if (!members || !ident)
545 return;
546
547 Dsymbol *s;
548 if (!Dsymbol::oneMembers(members, &s, ident) || !s)
549 return;
550
551 onemember = s;
552 s->parent = this;
553
554 /* Set isTrivialAliasSeq if this fits the pattern:
555 * template AliasSeq(T...) { alias AliasSeq = T; }
556 * or set isTrivialAlias if this fits the pattern:
557 * template Alias(T) { alias Alias = qualifiers(T); }
558 */
559 if (!(parameters && parameters->length == 1))
560 return;
561
562 AliasDeclaration *ad = s->isAliasDeclaration();
563 if (!ad || !ad->type)
564 return;
565
566 TypeIdentifier *ti = ad->type->isTypeIdentifier();
567 if (!ti || ti->idents.length != 0)
568 return;
569
570 if (TemplateTupleParameter *ttp = (*parameters)[0]->isTemplateTupleParameter())
571 {
572 if (ti->ident == ttp->ident && ti->mod == 0)
573 {
574 //printf("found isAliasSeq %s %s\n", s->toChars(), ad->type->toChars());
575 isTrivialAliasSeq = true;
576 }
577 }
578 else if (TemplateTypeParameter *ttp = (*parameters)[0]->isTemplateTypeParameter())
579 {
580 if (ti->ident == ttp->ident)
581 {
582 //printf("found isAlias %s %s\n", s->toChars(), ad->type->toChars());
583 isTrivialAlias = true;
584 }
585 }
586 }
587
syntaxCopy(Dsymbol *)588 Dsymbol *TemplateDeclaration::syntaxCopy(Dsymbol *)
589 {
590 //printf("TemplateDeclaration::syntaxCopy()\n");
591 TemplateParameters *p = NULL;
592 if (parameters)
593 {
594 p = new TemplateParameters();
595 p->setDim(parameters->length);
596 for (size_t i = 0; i < p->length; i++)
597 (*p)[i] = (*parameters)[i]->syntaxCopy();
598 }
599 return new TemplateDeclaration(loc, ident, p,
600 constraint ? constraint->syntaxCopy() : NULL,
601 Dsymbol::arraySyntaxCopy(members), ismixin, literal);
602 }
603
kind()604 const char *TemplateDeclaration::kind() const
605 {
606 return (onemember && onemember->isAggregateDeclaration())
607 ? onemember->kind()
608 : "template";
609 }
610
611 /**********************************
612 * Overload existing TemplateDeclaration 'this' with the new one 's'.
613 * Return true if successful; i.e. no conflict.
614 */
615
overloadInsert(Dsymbol * s)616 bool TemplateDeclaration::overloadInsert(Dsymbol *s)
617 {
618 FuncDeclaration *fd = s->isFuncDeclaration();
619 if (fd)
620 {
621 if (funcroot)
622 return funcroot->overloadInsert(fd);
623 funcroot = fd;
624 return funcroot->overloadInsert(this);
625 }
626
627 TemplateDeclaration *td = s->isTemplateDeclaration();
628 if (!td)
629 return false;
630
631 TemplateDeclaration *pthis = this;
632 TemplateDeclaration **ptd;
633 for (ptd = &pthis; *ptd; ptd = &(*ptd)->overnext)
634 {
635 }
636
637 td->overroot = this;
638 *ptd = td;
639 return true;
640 }
641
642 /****************************
643 * Check to see if constraint is satisfied.
644 */
evaluateConstraint(TemplateInstance * ti,Scope * sc,Scope * paramscope,Objects * dedargs,FuncDeclaration * fd)645 bool TemplateDeclaration::evaluateConstraint(
646 TemplateInstance *ti, Scope *sc, Scope *paramscope,
647 Objects *dedargs, FuncDeclaration *fd)
648 {
649 /* Detect recursive attempts to instantiate this template declaration,
650 * Bugzilla 4072
651 * void foo(T)(T x) if (is(typeof(foo(x)))) { }
652 * static assert(!is(typeof(foo(7))));
653 * Recursive attempts are regarded as a constraint failure.
654 */
655 /* There's a chicken-and-egg problem here. We don't know yet if this template
656 * instantiation will be a local one (enclosing is set), and we won't know until
657 * after selecting the correct template. Thus, function we're nesting inside
658 * is not on the sc scope chain, and this can cause errors in FuncDeclaration::getLevel().
659 * Workaround the problem by setting a flag to relax the checking on frame errors.
660 */
661
662 for (TemplatePrevious *p = previous; p; p = p->prev)
663 {
664 if (arrayObjectMatch(p->dedargs, dedargs))
665 {
666 //printf("recursive, no match p->sc=%p %p %s\n", p->sc, this, this->toChars());
667 /* It must be a subscope of p->sc, other scope chains are not recursive
668 * instantiations.
669 */
670 for (Scope *scx = sc; scx; scx = scx->enclosing)
671 {
672 if (scx == p->sc)
673 return false;
674 }
675 }
676 /* BUG: should also check for ref param differences
677 */
678 }
679
680 TemplatePrevious pr;
681 pr.prev = previous;
682 pr.sc = paramscope;
683 pr.dedargs = dedargs;
684 previous = ≺ // add this to threaded list
685
686 Scope *scx = paramscope->push(ti);
687 scx->parent = ti;
688 scx->tinst = NULL;
689 scx->minst = NULL;
690
691 assert(!ti->symtab);
692 if (fd)
693 {
694 /* Declare all the function parameters as variables and add them to the scope
695 * Making parameters is similar to FuncDeclaration::semantic3
696 */
697 TypeFunction *tf = (TypeFunction *)fd->type;
698 assert(tf->ty == Tfunction);
699
700 scx->parent = fd;
701
702 Parameters *fparameters = tf->parameterList.parameters;
703 VarArg fvarargs = tf->parameterList.varargs;
704
705 size_t nfparams = Parameter::dim(fparameters);
706 for (size_t i = 0; i < nfparams; i++)
707 {
708 Parameter *fparam = Parameter::getNth(fparameters, i);
709 fparam->storageClass &= (STCin | STCout | STCref | STClazy | STCfinal | STC_TYPECTOR | STCnodtor);
710 fparam->storageClass |= STCparameter;
711 if (fvarargs == VARARGtypesafe && i + 1 == nfparams)
712 fparam->storageClass |= STCvariadic;
713 }
714 for (size_t i = 0; i < fparameters->length; i++)
715 {
716 Parameter *fparam = (*fparameters)[i];
717 if (!fparam->ident)
718 continue; // don't add it, if it has no name
719 VarDeclaration *v = new VarDeclaration(loc, fparam->type, fparam->ident, NULL);
720 v->storage_class = fparam->storageClass;
721 dsymbolSemantic(v, scx);
722 if (!ti->symtab)
723 ti->symtab = new DsymbolTable();
724 if (!scx->insert(v))
725 error("parameter %s.%s is already defined", toChars(), v->toChars());
726 else
727 v->parent = fd;
728 }
729 if (isstatic)
730 fd->storage_class |= STCstatic;
731
732 fd->vthis = fd->declareThis(scx, fd->isThis());
733 }
734
735 Expression *e = constraint->syntaxCopy();
736
737 assert(ti->inst == NULL);
738 ti->inst = ti; // temporary instantiation to enable genIdent()
739
740 scx->flags |= SCOPEconstraint;
741 bool errors = false;
742 bool result = evalStaticCondition(scx, constraint, e, errors);
743 ti->inst = NULL;
744 ti->symtab = NULL;
745 scx = scx->pop();
746 previous = pr.prev; // unlink from threaded list
747 if (errors)
748 return false;
749 return result;
750 }
751
752 /***************************************
753 * Given that ti is an instance of this TemplateDeclaration,
754 * deduce the types of the parameters to this, and store
755 * those deduced types in dedtypes[].
756 * Input:
757 * flag 1: don't do semantic() because of dummy types
758 * 2: don't change types in matchArg()
759 * Output:
760 * dedtypes deduced arguments
761 * Return match level.
762 */
763
matchWithInstance(Scope * sc,TemplateInstance * ti,Objects * dedtypes,Expressions * fargs,int flag)764 MATCH TemplateDeclaration::matchWithInstance(Scope *sc, TemplateInstance *ti,
765 Objects *dedtypes, Expressions *fargs, int flag)
766 {
767 MATCH m;
768 size_t dedtypes_dim = dedtypes->length;
769
770 dedtypes->zero();
771
772 if (errors)
773 return MATCHnomatch;
774
775 size_t parameters_dim = parameters->length;
776 int variadic = isVariadic() != NULL;
777
778 // If more arguments than parameters, no match
779 if (ti->tiargs->length > parameters_dim && !variadic)
780 {
781 return MATCHnomatch;
782 }
783
784 assert(dedtypes_dim == parameters_dim);
785 assert(dedtypes_dim >= ti->tiargs->length || variadic);
786
787 assert(_scope);
788
789 // Set up scope for template parameters
790 ScopeDsymbol *paramsym = new ScopeDsymbol();
791 paramsym->parent = _scope->parent;
792 Scope *paramscope = _scope->push(paramsym);
793 paramscope->tinst = ti;
794 paramscope->minst = sc->minst;
795 paramscope->callsc = sc;
796 paramscope->stc = 0;
797
798 // Attempt type deduction
799 m = MATCHexact;
800 for (size_t i = 0; i < dedtypes_dim; i++)
801 {
802 MATCH m2;
803 TemplateParameter *tp = (*parameters)[i];
804 Declaration *sparam;
805
806 //printf("\targument [%d]\n", i);
807 inuse++;
808 m2 = tp->matchArg(ti->loc, paramscope, ti->tiargs, i, parameters, dedtypes, &sparam);
809 inuse--;
810 //printf("\tm2 = %d\n", m2);
811
812 if (m2 == MATCHnomatch)
813 {
814 goto Lnomatch;
815 }
816
817 if (m2 < m)
818 m = m2;
819
820 if (!flag)
821 dsymbolSemantic(sparam, paramscope);
822 if (!paramscope->insert(sparam)) // TODO: This check can make more early
823 goto Lnomatch; // in TemplateDeclaration::semantic, and
824 // then we don't need to make sparam if flags == 0
825 }
826
827 if (!flag)
828 {
829 /* Any parameter left without a type gets the type of
830 * its corresponding arg
831 */
832 for (size_t i = 0; i < dedtypes_dim; i++)
833 {
834 if (!(*dedtypes)[i])
835 {
836 assert(i < ti->tiargs->length);
837 (*dedtypes)[i] = (Type *)(*ti->tiargs)[i];
838 }
839 }
840 }
841
842 if (m > MATCHnomatch && constraint && !flag)
843 {
844 if (ti->hasNestedArgs(ti->tiargs, this->isstatic)) // TODO: should gag error
845 ti->parent = ti->enclosing;
846 else
847 ti->parent = this->parent;
848
849 // Similar to doHeaderInstantiation
850 FuncDeclaration *fd = onemember ? onemember->isFuncDeclaration() : NULL;
851 if (fd)
852 {
853 assert(fd->type->ty == Tfunction);
854 TypeFunction *tf = (TypeFunction *)fd->type->syntaxCopy();
855
856 fd = new FuncDeclaration(fd->loc, fd->endloc, fd->ident, fd->storage_class, tf);
857 fd->parent = ti;
858 fd->inferRetType = true;
859
860 // Shouldn't run semantic on default arguments and return type.
861 for (size_t i = 0; i < tf->parameterList.parameters->length; i++)
862 (*tf->parameterList.parameters)[i]->defaultArg = NULL;
863 tf->next = NULL;
864
865 // Resolve parameter types and 'auto ref's.
866 tf->fargs = fargs;
867 unsigned olderrors = global.startGagging();
868 fd->type = typeSemantic(tf, loc, paramscope);
869 if (global.endGagging(olderrors))
870 {
871 assert(fd->type->ty != Tfunction);
872 goto Lnomatch;
873 }
874 assert(fd->type->ty == Tfunction);
875 fd->originalType = fd->type; // for mangling
876 }
877
878 // TODO: dedtypes => ti->tiargs ?
879 if (!evaluateConstraint(ti, sc, paramscope, dedtypes, fd))
880 goto Lnomatch;
881 }
882
883 goto Lret;
884
885 Lnomatch:
886 m = MATCHnomatch;
887
888 Lret:
889 paramscope->pop();
890 return m;
891 }
892
893 /********************************************
894 * Determine partial specialization order of 'this' vs td2.
895 * Returns:
896 * match this is at least as specialized as td2
897 * 0 td2 is more specialized than this
898 */
899
leastAsSpecialized(Scope * sc,TemplateDeclaration * td2,Expressions * fargs)900 MATCH TemplateDeclaration::leastAsSpecialized(Scope *sc, TemplateDeclaration *td2, Expressions *fargs)
901 {
902 /* This works by taking the template parameters to this template
903 * declaration and feeding them to td2 as if it were a template
904 * instance.
905 * If it works, then this template is at least as specialized
906 * as td2.
907 */
908
909 TemplateInstance ti(Loc(), ident); // create dummy template instance
910 // Set type arguments to dummy template instance to be types
911 // generated from the parameters to this template declaration
912 ti.tiargs = new Objects();
913 ti.tiargs->reserve(parameters->length);
914 for (size_t i = 0; i < parameters->length; i++)
915 {
916 TemplateParameter *tp = (*parameters)[i];
917 if (tp->dependent)
918 break;
919 RootObject *p = (RootObject *)tp->dummyArg();
920 if (!p)
921 break;
922
923 ti.tiargs->push(p);
924 }
925
926 // Temporary Array to hold deduced types
927 Objects dedtypes;
928 dedtypes.setDim(td2->parameters->length);
929
930 // Attempt a type deduction
931 MATCH m = td2->matchWithInstance(sc, &ti, &dedtypes, fargs, 1);
932 if (m > MATCHnomatch)
933 {
934 /* A non-variadic template is more specialized than a
935 * variadic one.
936 */
937 TemplateTupleParameter *tp = isVariadic();
938 if (tp && !tp->dependent && !td2->isVariadic())
939 goto L1;
940
941 return m;
942 }
943 L1:
944 return MATCHnomatch;
945 }
946
947 static Expression *emptyArrayElement = NULL;
948
949 class TypeDeduced : public Type
950 {
951 public:
952 Type *tded;
953 Expressions argexps; // corresponding expressions
954 Types tparams; // tparams[i]->mod
955
TypeDeduced(Type * tt,Expression * e,Type * tparam)956 TypeDeduced(Type *tt, Expression *e, Type *tparam)
957 : Type(Tnone)
958 {
959 tded = tt;
960 argexps.push(e);
961 tparams.push(tparam);
962 }
963
~TypeDeduced()964 virtual ~TypeDeduced()
965 {
966 }
967
update(Expression * e,Type * tparam)968 void update(Expression *e, Type *tparam)
969 {
970 argexps.push(e);
971 tparams.push(tparam);
972 }
update(Type * tt,Expression * e,Type * tparam)973 void update(Type *tt, Expression *e, Type *tparam)
974 {
975 tded = tt;
976 argexps.push(e);
977 tparams.push(tparam);
978 }
matchAll(Type * tt)979 MATCH matchAll(Type *tt)
980 {
981 MATCH match = MATCHexact;
982 for (size_t j = 0; j < argexps.length; j++)
983 {
984 Expression *e = argexps[j];
985 assert(e);
986 if (e == emptyArrayElement)
987 continue;
988
989 Type *t = tt->addMod(tparams[j]->mod)->substWildTo(MODconst);
990
991 MATCH m = e->implicitConvTo(t);
992 if (match > m)
993 match = m;
994 if (match <= MATCHnomatch)
995 break;
996 }
997 return match;
998 }
999 };
1000
1001 /*************************************************
1002 * Match function arguments against a specific template function.
1003 * Input:
1004 * ti
1005 * sc instantiation scope
1006 * fd
1007 * tthis 'this' argument if !NULL
1008 * fargs arguments to function
1009 * Output:
1010 * fd Partially instantiated function declaration
1011 * ti->tdtypes Expression/Type deduced template arguments
1012 * Returns:
1013 * match level
1014 * bit 0-3 Match template parameters by inferred template arguments
1015 * bit 4-7 Match template parameters by initial template arguments
1016 */
1017
deduceFunctionTemplateMatch(TemplateInstance * ti,Scope * sc,FuncDeclaration * & fd,Type * tthis,Expressions * fargs)1018 MATCH TemplateDeclaration::deduceFunctionTemplateMatch(
1019 TemplateInstance *ti, Scope *sc,
1020 FuncDeclaration *&fd, Type *tthis, Expressions *fargs)
1021 {
1022 size_t nfparams;
1023 size_t nfargs;
1024 size_t ntargs; // array size of tiargs
1025 size_t fptupindex = IDX_NOTFOUND;
1026 MATCH match = MATCHexact;
1027 MATCH matchTiargs = MATCHexact;
1028 ParameterList fparameters; // function parameter list
1029 unsigned wildmatch = 0;
1030 size_t inferStart = 0;
1031
1032 Loc instLoc = ti->loc;
1033 Objects *tiargs = ti->tiargs;
1034 Objects *dedargs = new Objects();
1035 Objects* dedtypes = &ti->tdtypes; // for T:T*, the dedargs is the T*, dedtypes is the T
1036
1037 assert(_scope);
1038
1039 dedargs->setDim(parameters->length);
1040 dedargs->zero();
1041
1042 dedtypes->setDim(parameters->length);
1043 dedtypes->zero();
1044
1045 if (errors || fd->errors)
1046 return MATCHnomatch;
1047
1048 // Set up scope for parameters
1049 ScopeDsymbol *paramsym = new ScopeDsymbol();
1050 paramsym->parent = _scope->parent; // should use hasnestedArgs and enclosing?
1051 Scope *paramscope = _scope->push(paramsym);
1052 paramscope->tinst = ti;
1053 paramscope->minst = sc->minst;
1054 paramscope->callsc = sc;
1055 paramscope->stc = 0;
1056
1057 TemplateTupleParameter *tp = isVariadic();
1058 Tuple *declaredTuple = NULL;
1059
1060 ntargs = 0;
1061 if (tiargs)
1062 {
1063 // Set initial template arguments
1064 ntargs = tiargs->length;
1065 size_t n = parameters->length;
1066 if (tp)
1067 n--;
1068 if (ntargs > n)
1069 {
1070 if (!tp)
1071 goto Lnomatch;
1072
1073 /* The extra initial template arguments
1074 * now form the tuple argument.
1075 */
1076 Tuple *t = new Tuple();
1077 assert(parameters->length);
1078 (*dedargs)[parameters->length - 1] = t;
1079
1080 t->objects.setDim(ntargs - n);
1081 for (size_t i = 0; i < t->objects.length; i++)
1082 {
1083 t->objects[i] = (*tiargs)[n + i];
1084 }
1085 declareParameter(paramscope, tp, t);
1086 declaredTuple = t;
1087 }
1088 else
1089 n = ntargs;
1090
1091 memcpy(dedargs->tdata(), tiargs->tdata(), n * sizeof(*dedargs->tdata()));
1092
1093 for (size_t i = 0; i < n; i++)
1094 {
1095 assert(i < parameters->length);
1096 Declaration *sparam = NULL;
1097 MATCH m = (*parameters)[i]->matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, &sparam);
1098 //printf("\tdeduceType m = %d\n", m);
1099 if (m <= MATCHnomatch)
1100 goto Lnomatch;
1101 if (m < matchTiargs)
1102 matchTiargs = m;
1103
1104 dsymbolSemantic(sparam, paramscope);
1105 if (!paramscope->insert(sparam))
1106 goto Lnomatch;
1107 }
1108 if (n < parameters->length && !declaredTuple)
1109 {
1110 inferStart = n;
1111 }
1112 else
1113 inferStart = parameters->length;
1114 //printf("tiargs matchTiargs = %d\n", matchTiargs);
1115 }
1116
1117 fparameters = fd->getParameterList();
1118 nfparams = fparameters.length(); // number of function parameters
1119 nfargs = fargs ? fargs->length : 0; // number of function arguments
1120
1121 /* Check for match of function arguments with variadic template
1122 * parameter, such as:
1123 *
1124 * void foo(T, A...)(T t, A a);
1125 * void main() { foo(1,2,3); }
1126 */
1127 if (tp) // if variadic
1128 {
1129 // TemplateTupleParameter always makes most lesser matching.
1130 matchTiargs = MATCHconvert;
1131
1132 if (nfparams == 0 && nfargs != 0) // if no function parameters
1133 {
1134 if (!declaredTuple)
1135 {
1136 Tuple *t = new Tuple();
1137 //printf("t = %p\n", t);
1138 (*dedargs)[parameters->length - 1] = t;
1139 declareParameter(paramscope, tp, t);
1140 declaredTuple = t;
1141 }
1142 }
1143 else
1144 {
1145 /* Figure out which of the function parameters matches
1146 * the tuple template parameter. Do this by matching
1147 * type identifiers.
1148 * Set the index of this function parameter to fptupindex.
1149 */
1150 for (fptupindex = 0; fptupindex < nfparams; fptupindex++)
1151 {
1152 Parameter *fparam = (*fparameters.parameters)[fptupindex];
1153 if (fparam->type->ty != Tident)
1154 continue;
1155 TypeIdentifier *tid = (TypeIdentifier *)fparam->type;
1156 if (!tp->ident->equals(tid->ident) || tid->idents.length)
1157 continue;
1158
1159 if (fparameters.varargs != VARARGnone) // variadic function doesn't
1160 goto Lnomatch; // go with variadic template
1161
1162 goto L1;
1163 }
1164 fptupindex = IDX_NOTFOUND;
1165 L1:
1166 ;
1167 }
1168 }
1169
1170 if (toParent()->isModule() || (_scope->stc & STCstatic))
1171 tthis = NULL;
1172 if (tthis)
1173 {
1174 bool hasttp = false;
1175
1176 // Match 'tthis' to any TemplateThisParameter's
1177 for (size_t i = 0; i < parameters->length; i++)
1178 {
1179 TemplateThisParameter *ttp = (*parameters)[i]->isTemplateThisParameter();
1180 if (ttp)
1181 {
1182 hasttp = true;
1183
1184 Type *t = new TypeIdentifier(Loc(), ttp->ident);
1185 MATCH m = deduceType(tthis, paramscope, t, parameters, dedtypes);
1186 if (m <= MATCHnomatch)
1187 goto Lnomatch;
1188 if (m < match)
1189 match = m; // pick worst match
1190 }
1191 }
1192
1193 // Match attributes of tthis against attributes of fd
1194 if (fd->type && !fd->isCtorDeclaration())
1195 {
1196 StorageClass stc = _scope->stc | fd->storage_class2;
1197 // Propagate parent storage class (see bug 5504)
1198 Dsymbol *p = parent;
1199 while (p->isTemplateDeclaration() || p->isTemplateInstance())
1200 p = p->parent;
1201 AggregateDeclaration *ad = p->isAggregateDeclaration();
1202 if (ad)
1203 stc |= ad->storage_class;
1204
1205 unsigned char mod = fd->type->mod;
1206 if (stc & STCimmutable)
1207 mod = MODimmutable;
1208 else
1209 {
1210 if (stc & (STCshared | STCsynchronized))
1211 mod |= MODshared;
1212 if (stc & STCconst)
1213 mod |= MODconst;
1214 if (stc & STCwild)
1215 mod |= MODwild;
1216 }
1217
1218 unsigned char thismod = tthis->mod;
1219 if (hasttp)
1220 mod = MODmerge(thismod, mod);
1221 MATCH m = MODmethodConv(thismod, mod);
1222 if (m <= MATCHnomatch)
1223 goto Lnomatch;
1224 if (m < match)
1225 match = m;
1226 }
1227 }
1228
1229 // Loop through the function parameters
1230 {
1231 //printf("%s\n\tnfargs = %d, nfparams = %d, tuple_dim = %d\n", toChars(), nfargs, nfparams, declaredTuple ? declaredTuple->objects.length : 0);
1232 //printf("\ttp = %p, fptupindex = %d, found = %d, declaredTuple = %s\n", tp, fptupindex, fptupindex != IDX_NOTFOUND, declaredTuple ? declaredTuple->toChars() : NULL);
1233 size_t argi = 0;
1234 size_t nfargs2 = nfargs; // nfargs + supplied defaultArgs
1235 for (size_t parami = 0; parami < nfparams; parami++)
1236 {
1237 Parameter *fparam = fparameters[parami];
1238
1239 // Apply function parameter storage classes to parameter types
1240 Type *prmtype = fparam->type->addStorageClass(fparam->storageClass);
1241
1242 Expression *farg;
1243
1244 /* See function parameters which wound up
1245 * as part of a template tuple parameter.
1246 */
1247 if (fptupindex != IDX_NOTFOUND && parami == fptupindex)
1248 {
1249 assert(prmtype->ty == Tident);
1250 TypeIdentifier *tid = (TypeIdentifier *)prmtype;
1251 if (!declaredTuple)
1252 {
1253 /* The types of the function arguments
1254 * now form the tuple argument.
1255 */
1256 declaredTuple = new Tuple();
1257 (*dedargs)[parameters->length - 1] = declaredTuple;
1258
1259 /* Count function parameters following a tuple parameter.
1260 * void foo(U, T...)(int y, T, U, int) {} // rem == 2 (U, int)
1261 */
1262 size_t rem = 0;
1263 for (size_t j = parami + 1; j < nfparams; j++)
1264 {
1265 Parameter *p = fparameters[j];
1266 if (!reliesOnTident(p->type, parameters, inferStart))
1267 {
1268 Type *pt = typeSemantic(p->type->syntaxCopy(), fd->loc, paramscope);
1269 rem += pt->ty == Ttuple ? ((TypeTuple *)pt)->arguments->length : 1;
1270 }
1271 else
1272 {
1273 ++rem;
1274 }
1275 }
1276
1277 if (nfargs2 - argi < rem)
1278 goto Lnomatch;
1279 declaredTuple->objects.setDim(nfargs2 - argi - rem);
1280 for (size_t i = 0; i < declaredTuple->objects.length; i++)
1281 {
1282 farg = (*fargs)[argi + i];
1283
1284 // Check invalid arguments to detect errors early.
1285 if (farg->op == TOKerror || farg->type->ty == Terror)
1286 goto Lnomatch;
1287
1288 if (!(fparam->storageClass & STClazy) && farg->type->ty == Tvoid)
1289 goto Lnomatch;
1290
1291 Type *tt;
1292 MATCH m;
1293 if (unsigned char wm = deduceWildHelper(farg->type, &tt, tid))
1294 {
1295 wildmatch |= wm;
1296 m = MATCHconst;
1297 }
1298 else
1299 {
1300 m = deduceTypeHelper(farg->type, &tt, tid);
1301 }
1302 if (m <= MATCHnomatch)
1303 goto Lnomatch;
1304 if (m < match)
1305 match = m;
1306
1307 /* Remove top const for dynamic array types and pointer types
1308 */
1309 if ((tt->ty == Tarray || tt->ty == Tpointer) &&
1310 !tt->isMutable() &&
1311 (!(fparam->storageClass & STCref) ||
1312 ((fparam->storageClass & STCauto) && !farg->isLvalue())))
1313 {
1314 tt = tt->mutableOf();
1315 }
1316 declaredTuple->objects[i] = tt;
1317 }
1318 declareParameter(paramscope, tp, declaredTuple);
1319 }
1320 else
1321 {
1322 // Bugzilla 6810: If declared tuple is not a type tuple,
1323 // it cannot be function parameter types.
1324 for (size_t i = 0; i < declaredTuple->objects.length; i++)
1325 {
1326 if (!isType(declaredTuple->objects[i]))
1327 goto Lnomatch;
1328 }
1329 }
1330 assert(declaredTuple);
1331 argi += declaredTuple->objects.length;
1332 continue;
1333 }
1334
1335 // If parameter type doesn't depend on inferred template parameters,
1336 // semantic it to get actual type.
1337 if (!reliesOnTident(prmtype, parameters, inferStart))
1338 {
1339 // should copy prmtype to avoid affecting semantic result
1340 prmtype = typeSemantic(prmtype->syntaxCopy(), fd->loc, paramscope);
1341
1342 if (prmtype->ty == Ttuple)
1343 {
1344 TypeTuple *tt = (TypeTuple *)prmtype;
1345 size_t tt_dim = tt->arguments->length;
1346 for (size_t j = 0; j < tt_dim; j++, ++argi)
1347 {
1348 Parameter *p = (*tt->arguments)[j];
1349 if (j == tt_dim - 1 && fparameters.varargs == VARARGtypesafe &&
1350 parami + 1 == nfparams && argi < nfargs)
1351 {
1352 prmtype = p->type;
1353 goto Lvarargs;
1354 }
1355 if (argi >= nfargs)
1356 {
1357 if (p->defaultArg)
1358 continue;
1359 goto Lnomatch;
1360 }
1361 farg = (*fargs)[argi];
1362 if (!farg->implicitConvTo(p->type))
1363 goto Lnomatch;
1364 }
1365 continue;
1366 }
1367 }
1368
1369 if (argi >= nfargs) // if not enough arguments
1370 {
1371 if (!fparam->defaultArg)
1372 goto Lvarargs;
1373
1374 /* Bugzilla 2803: Before the starting of type deduction from the function
1375 * default arguments, set the already deduced parameters into paramscope.
1376 * It's necessary to avoid breaking existing acceptable code. Cases:
1377 *
1378 * 1. Already deduced template parameters can appear in fparam->defaultArg:
1379 * auto foo(A, B)(A a, B b = A.stringof);
1380 * foo(1);
1381 * // at fparam == 'B b = A.string', A is equivalent with the deduced type 'int'
1382 *
1383 * 2. If prmtype depends on default-specified template parameter, the
1384 * default type should be preferred.
1385 * auto foo(N = size_t, R)(R r, N start = 0)
1386 * foo([1,2,3]);
1387 * // at fparam `N start = 0`, N should be 'size_t' before
1388 * // the deduction result from fparam->defaultArg.
1389 */
1390 if (argi == nfargs)
1391 {
1392 for (size_t i = 0; i < dedtypes->length; i++)
1393 {
1394 Type *at = isType((*dedtypes)[i]);
1395 if (at && at->ty == Tnone)
1396 {
1397 TypeDeduced *xt = (TypeDeduced *)at;
1398 (*dedtypes)[i] = xt->tded; // 'unbox'
1399 delete xt;
1400 }
1401 }
1402 for (size_t i = ntargs; i < dedargs->length; i++)
1403 {
1404 TemplateParameter *tparam = (*parameters)[i];
1405
1406 RootObject *oarg = (*dedargs)[i];
1407 RootObject *oded = (*dedtypes)[i];
1408 if (!oarg)
1409 {
1410 if (oded)
1411 {
1412 if (tparam->specialization() || !tparam->isTemplateTypeParameter())
1413 {
1414 /* The specialization can work as long as afterwards
1415 * the oded == oarg
1416 */
1417 (*dedargs)[i] = oded;
1418 MATCH m2 = tparam->matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, NULL);
1419 //printf("m2 = %d\n", m2);
1420 if (m2 <= MATCHnomatch)
1421 goto Lnomatch;
1422 if (m2 < matchTiargs)
1423 matchTiargs = m2; // pick worst match
1424 if (!(*dedtypes)[i]->equals(oded))
1425 error("specialization not allowed for deduced parameter %s", tparam->ident->toChars());
1426 }
1427 else
1428 {
1429 if (MATCHconvert < matchTiargs)
1430 matchTiargs = MATCHconvert;
1431 }
1432 (*dedargs)[i] = declareParameter(paramscope, tparam, oded);
1433 }
1434 else
1435 {
1436 inuse++;
1437 oded = tparam->defaultArg(instLoc, paramscope);
1438 inuse--;
1439 if (oded)
1440 (*dedargs)[i] = declareParameter(paramscope, tparam, oded);
1441 }
1442 }
1443 }
1444 }
1445 nfargs2 = argi + 1;
1446
1447 /* If prmtype does not depend on any template parameters:
1448 *
1449 * auto foo(T)(T v, double x = 0);
1450 * foo("str");
1451 * // at fparam == 'double x = 0'
1452 *
1453 * or, if all template parameters in the prmtype are already deduced:
1454 *
1455 * auto foo(R)(R range, ElementType!R sum = 0);
1456 * foo([1,2,3]);
1457 * // at fparam == 'ElementType!R sum = 0'
1458 *
1459 * Deducing prmtype from fparam->defaultArg is not necessary.
1460 */
1461 if (prmtype->deco ||
1462 prmtype->syntaxCopy()->trySemantic(loc, paramscope))
1463 {
1464 ++argi;
1465 continue;
1466 }
1467
1468 // Deduce prmtype from the defaultArg.
1469 farg = fparam->defaultArg->syntaxCopy();
1470 farg = expressionSemantic(farg, paramscope);
1471 farg = resolveProperties(paramscope, farg);
1472 }
1473 else
1474 {
1475 farg = (*fargs)[argi];
1476 }
1477 {
1478 // Check invalid arguments to detect errors early.
1479 if (farg->op == TOKerror || farg->type->ty == Terror)
1480 goto Lnomatch;
1481
1482 Type *att = NULL;
1483 Lretry:
1484 Type *argtype = farg->type;
1485
1486 if (!(fparam->storageClass & STClazy) && argtype->ty == Tvoid && farg->op != TOKfunction)
1487 goto Lnomatch;
1488
1489 // Bugzilla 12876: optimize arugument to allow CT-known length matching
1490 farg = farg->optimize(WANTvalue, (fparam->storageClass & (STCref | STCout)) != 0);
1491 //printf("farg = %s %s\n", farg->type->toChars(), farg->toChars());
1492
1493 RootObject *oarg = farg;
1494 if ((fparam->storageClass & STCref) &&
1495 (!(fparam->storageClass & STCauto) || farg->isLvalue()))
1496 {
1497 /* Allow expressions that have CT-known boundaries and type [] to match with [dim]
1498 */
1499 Type *taai;
1500 if (argtype->ty == Tarray &&
1501 (prmtype->ty == Tsarray ||
1502 (prmtype->ty == Taarray && (taai = ((TypeAArray *)prmtype)->index)->ty == Tident &&
1503 ((TypeIdentifier *)taai)->idents.length == 0)))
1504 {
1505 if (farg->op == TOKstring)
1506 {
1507 StringExp *se = (StringExp *)farg;
1508 argtype = se->type->nextOf()->sarrayOf(se->len);
1509 }
1510 else if (farg->op == TOKarrayliteral)
1511 {
1512 ArrayLiteralExp *ae = (ArrayLiteralExp *)farg;
1513 argtype = ae->type->nextOf()->sarrayOf(ae->elements->length);
1514 }
1515 else if (farg->op == TOKslice)
1516 {
1517 SliceExp *se = (SliceExp *)farg;
1518 if (Type *tsa = toStaticArrayType(se))
1519 argtype = tsa;
1520 }
1521 }
1522
1523 oarg = argtype;
1524 }
1525 else if ((fparam->storageClass & STCout) == 0 &&
1526 (argtype->ty == Tarray || argtype->ty == Tpointer) &&
1527 templateParameterLookup(prmtype, parameters) != IDX_NOTFOUND &&
1528 ((TypeIdentifier *)prmtype)->idents.length == 0)
1529 {
1530 /* The farg passing to the prmtype always make a copy. Therefore,
1531 * we can shrink the set of the deduced type arguments for prmtype
1532 * by adjusting top-qualifier of the argtype.
1533 *
1534 * prmtype argtype ta
1535 * T <- const(E)[] const(E)[]
1536 * T <- const(E[]) const(E)[]
1537 * qualifier(T) <- const(E)[] const(E[])
1538 * qualifier(T) <- const(E[]) const(E[])
1539 */
1540 Type *ta = argtype->castMod(prmtype->mod ? argtype->nextOf()->mod : 0);
1541 if (ta != argtype)
1542 {
1543 Expression *ea = farg->copy();
1544 ea->type = ta;
1545 oarg = ea;
1546 }
1547 }
1548
1549 if (fparameters.varargs == VARARGtypesafe && parami + 1 == nfparams && argi + 1 < nfargs)
1550 goto Lvarargs;
1551
1552 unsigned wm = 0;
1553 MATCH m = deduceType(oarg, paramscope, prmtype, parameters, dedtypes, &wm, inferStart);
1554 //printf("\tL%d deduceType m = %d, wm = x%x, wildmatch = x%x\n", __LINE__, m, wm, wildmatch);
1555 wildmatch |= wm;
1556
1557 /* If no match, see if the argument can be matched by using
1558 * implicit conversions.
1559 */
1560 if (m == MATCHnomatch && prmtype->deco)
1561 m = farg->implicitConvTo(prmtype);
1562
1563 if (m == MATCHnomatch)
1564 {
1565 AggregateDeclaration *ad = isAggregate(farg->type);
1566 if (ad && ad->aliasthis && argtype != att)
1567 {
1568 if (!att && argtype->checkAliasThisRec()) // Bugzilla 12537
1569 att = argtype;
1570
1571 /* If a semantic error occurs while doing alias this,
1572 * eg purity(bug 7295), just regard it as not a match.
1573 */
1574 if (Expression *e = resolveAliasThis(sc, farg, true))
1575 {
1576 farg = e;
1577 goto Lretry;
1578 }
1579 }
1580 }
1581
1582 if (m > MATCHnomatch && (fparam->storageClass & (STCref | STCauto)) == STCref)
1583 {
1584 if (!farg->isLvalue())
1585 {
1586 if ((farg->op == TOKstring || farg->op == TOKslice) &&
1587 (prmtype->ty == Tsarray || prmtype->ty == Taarray))
1588 {
1589 // Allow conversion from T[lwr .. upr] to ref T[upr-lwr]
1590 }
1591 else
1592 goto Lnomatch;
1593 }
1594 }
1595 if (m > MATCHnomatch && (fparam->storageClass & STCout))
1596 {
1597 if (!farg->isLvalue())
1598 goto Lnomatch;
1599 if (!farg->type->isMutable()) // Bugzilla 11916
1600 goto Lnomatch;
1601 }
1602 if (m == MATCHnomatch && (fparam->storageClass & STClazy) && prmtype->ty == Tvoid &&
1603 farg->type->ty != Tvoid)
1604 m = MATCHconvert;
1605
1606 if (m != MATCHnomatch)
1607 {
1608 if (m < match)
1609 match = m; // pick worst match
1610 argi++;
1611 continue;
1612 }
1613 }
1614
1615 Lvarargs:
1616 /* The following code for variadic arguments closely
1617 * matches TypeFunction::callMatch()
1618 */
1619 if (!(fparameters.varargs == VARARGtypesafe && parami + 1 == nfparams))
1620 goto Lnomatch;
1621
1622 /* Check for match with function parameter T...
1623 */
1624 Type *tb = prmtype->toBasetype();
1625 switch (tb->ty)
1626 {
1627 // 6764 fix - TypeAArray may be TypeSArray have not yet run semantic().
1628 case Tsarray:
1629 case Taarray:
1630 // Perhaps we can do better with this, see TypeFunction::callMatch()
1631 if (tb->ty == Tsarray)
1632 {
1633 TypeSArray *tsa = (TypeSArray *)tb;
1634 dinteger_t sz = tsa->dim->toInteger();
1635 if (sz != nfargs - argi)
1636 goto Lnomatch;
1637 }
1638 else if (tb->ty == Taarray)
1639 {
1640 TypeAArray *taa = (TypeAArray *)tb;
1641 Expression *dim = new IntegerExp(instLoc, nfargs - argi, Type::tsize_t);
1642
1643 size_t i = templateParameterLookup(taa->index, parameters);
1644 if (i == IDX_NOTFOUND)
1645 {
1646 Expression *e;
1647 Type *t;
1648 Dsymbol *s;
1649 Scope *sco;
1650
1651 unsigned errors = global.startGagging();
1652 /* ref: https://issues.dlang.org/show_bug.cgi?id=11118
1653 * The parameter isn't part of the template
1654 * ones, let's try to find it in the
1655 * instantiation scope 'sc' and the one
1656 * belonging to the template itself. */
1657 sco = sc;
1658 taa->index->resolve(instLoc, sco, &e, &t, &s);
1659 if (!e)
1660 {
1661 sco = paramscope;
1662 taa->index->resolve(instLoc, sco, &e, &t, &s);
1663 }
1664 global.endGagging(errors);
1665
1666 if (!e)
1667 {
1668 goto Lnomatch;
1669 }
1670
1671 e = e->ctfeInterpret();
1672 e = e->implicitCastTo(sco, Type::tsize_t);
1673 e = e->optimize(WANTvalue);
1674 if (!dim->equals(e))
1675 goto Lnomatch;
1676 }
1677 else
1678 {
1679 // This code matches code in TypeInstance::deduceType()
1680 TemplateParameter *tprm = (*parameters)[i];
1681 TemplateValueParameter *tvp = tprm->isTemplateValueParameter();
1682 if (!tvp)
1683 goto Lnomatch;
1684 Expression *e = (Expression *)(*dedtypes)[i];
1685 if (e)
1686 {
1687 if (!dim->equals(e))
1688 goto Lnomatch;
1689 }
1690 else
1691 {
1692 Type *vt = typeSemantic(tvp->valType, Loc(), sc);
1693 MATCH m = (MATCH)dim->implicitConvTo(vt);
1694 if (m <= MATCHnomatch)
1695 goto Lnomatch;
1696 (*dedtypes)[i] = dim;
1697 }
1698 }
1699 }
1700 /* fall through */
1701 case Tarray:
1702 {
1703 TypeArray *ta = (TypeArray *)tb;
1704 Type *tret = fparam->isLazyArray();
1705 for (; argi < nfargs; argi++)
1706 {
1707 Expression *arg = (*fargs)[argi];
1708 assert(arg);
1709
1710 MATCH m;
1711 /* If lazy array of delegates,
1712 * convert arg(s) to delegate(s)
1713 */
1714 if (tret)
1715 {
1716 if (ta->next->equals(arg->type))
1717 {
1718 m = MATCHexact;
1719 }
1720 else
1721 {
1722 m = arg->implicitConvTo(tret);
1723 if (m == MATCHnomatch)
1724 {
1725 if (tret->toBasetype()->ty == Tvoid)
1726 m = MATCHconvert;
1727 }
1728 }
1729 }
1730 else
1731 {
1732 unsigned wm = 0;
1733 m = deduceType(arg, paramscope, ta->next, parameters, dedtypes, &wm, inferStart);
1734 wildmatch |= wm;
1735 }
1736 if (m == MATCHnomatch)
1737 goto Lnomatch;
1738 if (m < match)
1739 match = m;
1740 }
1741 goto Lmatch;
1742 }
1743 case Tclass:
1744 case Tident:
1745 goto Lmatch;
1746
1747 default:
1748 goto Lnomatch;
1749 }
1750 ++argi;
1751 }
1752 //printf("-> argi = %d, nfargs = %d, nfargs2 = %d\n", argi, nfargs, nfargs2);
1753 if (argi != nfargs2 && fparameters.varargs == VARARGnone)
1754 goto Lnomatch;
1755 }
1756
1757 Lmatch:
1758
1759 for (size_t i = 0; i < dedtypes->length; i++)
1760 {
1761 Type *at = isType((*dedtypes)[i]);
1762 if (at)
1763 {
1764 if (at->ty == Tnone)
1765 {
1766 TypeDeduced *xt = (TypeDeduced *)at;
1767 at = xt->tded; // 'unbox'
1768 delete xt;
1769 }
1770 (*dedtypes)[i] = at->merge2();
1771 }
1772 }
1773 for (size_t i = ntargs; i < dedargs->length; i++)
1774 {
1775 TemplateParameter *tparam = (*parameters)[i];
1776 //printf("tparam[%d] = %s\n", i, tparam->ident->toChars());
1777 /* For T:T*, the dedargs is the T*, dedtypes is the T
1778 * But for function templates, we really need them to match
1779 */
1780 RootObject *oarg = (*dedargs)[i];
1781 RootObject *oded = (*dedtypes)[i];
1782 //printf("1dedargs[%d] = %p, dedtypes[%d] = %p\n", i, oarg, i, oded);
1783 //if (oarg) printf("oarg: %s\n", oarg->toChars());
1784 //if (oded) printf("oded: %s\n", oded->toChars());
1785 if (!oarg)
1786 {
1787 if (oded)
1788 {
1789 if (tparam->specialization() || !tparam->isTemplateTypeParameter())
1790 {
1791 /* The specialization can work as long as afterwards
1792 * the oded == oarg
1793 */
1794 (*dedargs)[i] = oded;
1795 MATCH m2 = tparam->matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, NULL);
1796 //printf("m2 = %d\n", m2);
1797 if (m2 <= MATCHnomatch)
1798 goto Lnomatch;
1799 if (m2 < matchTiargs)
1800 matchTiargs = m2; // pick worst match
1801 if (!(*dedtypes)[i]->equals(oded))
1802 error("specialization not allowed for deduced parameter %s", tparam->ident->toChars());
1803 }
1804 else
1805 {
1806 if (MATCHconvert < matchTiargs)
1807 matchTiargs = MATCHconvert;
1808 }
1809 }
1810 else
1811 {
1812 inuse++;
1813 oded = tparam->defaultArg(instLoc, paramscope);
1814 inuse--;
1815 if (!oded)
1816 {
1817 // if tuple parameter and
1818 // tuple parameter was not in function parameter list and
1819 // we're one or more arguments short (i.e. no tuple argument)
1820 if (tparam == tp &&
1821 fptupindex == IDX_NOTFOUND &&
1822 ntargs <= dedargs->length - 1)
1823 {
1824 // make tuple argument an empty tuple
1825 oded = (RootObject *)new Tuple();
1826 }
1827 else
1828 goto Lnomatch;
1829 }
1830 if (isError(oded))
1831 goto Lerror;
1832 ntargs++;
1833
1834 /* At the template parameter T, the picked default template argument
1835 * X!int should be matched to T in order to deduce dependent
1836 * template parameter A.
1837 * auto foo(T : X!A = X!int, A...)() { ... }
1838 * foo(); // T <-- X!int, A <-- (int)
1839 */
1840 if (tparam->specialization())
1841 {
1842 (*dedargs)[i] = oded;
1843 MATCH m2 = tparam->matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, NULL);
1844 //printf("m2 = %d\n", m2);
1845 if (m2 <= MATCHnomatch)
1846 goto Lnomatch;
1847 if (m2 < matchTiargs)
1848 matchTiargs = m2; // pick worst match
1849 if (!(*dedtypes)[i]->equals(oded))
1850 error("specialization not allowed for deduced parameter %s", tparam->ident->toChars());
1851 }
1852 }
1853 oded = declareParameter(paramscope, tparam, oded);
1854 (*dedargs)[i] = oded;
1855 }
1856 }
1857
1858 /* Bugzilla 7469: As same as the code for 7469 in findBestMatch,
1859 * expand a Tuple in dedargs to normalize template arguments.
1860 */
1861 if (size_t d = dedargs->length)
1862 {
1863 if (Tuple *va = isTuple((*dedargs)[d - 1]))
1864 {
1865 if (va->objects.length)
1866 {
1867 dedargs->setDim(d - 1);
1868 dedargs->insert(d - 1, &va->objects);
1869 }
1870 }
1871 }
1872 ti->tiargs = dedargs; // update to the normalized template arguments.
1873
1874 // Partially instantiate function for constraint and fd->leastAsSpecialized()
1875 {
1876 assert(paramsym);
1877 Scope *sc2 = _scope;
1878 sc2 = sc2->push(paramsym);
1879 sc2 = sc2->push(ti);
1880 sc2->parent = ti;
1881 sc2->tinst = ti;
1882 sc2->minst = sc->minst;
1883
1884 fd = doHeaderInstantiation(ti, sc2, fd, tthis, fargs);
1885
1886 sc2 = sc2->pop();
1887 sc2 = sc2->pop();
1888
1889 if (!fd)
1890 goto Lnomatch;
1891 }
1892
1893 if (constraint)
1894 {
1895 if (!evaluateConstraint(ti, sc, paramscope, dedargs, fd))
1896 goto Lnomatch;
1897 }
1898
1899 paramscope->pop();
1900 //printf("\tmatch %d\n", match);
1901 return (MATCH)(match | (matchTiargs<<4));
1902
1903 Lnomatch:
1904 paramscope->pop();
1905 //printf("\tnomatch\n");
1906 return MATCHnomatch;
1907
1908 Lerror: // todo: for the future improvement
1909 paramscope->pop();
1910 //printf("\terror\n");
1911 return MATCHnomatch;
1912 }
1913
1914 /**************************************************
1915 * Declare template parameter tp with value o, and install it in the scope sc.
1916 */
1917
declareParameter(Scope * sc,TemplateParameter * tp,RootObject * o)1918 RootObject *TemplateDeclaration::declareParameter(Scope *sc, TemplateParameter *tp, RootObject *o)
1919 {
1920 //printf("TemplateDeclaration::declareParameter('%s', o = %p)\n", tp->ident->toChars(), o);
1921
1922 Type *ta = isType(o);
1923 Expression *ea = isExpression(o);
1924 Dsymbol *sa = isDsymbol(o);
1925 Tuple *va = isTuple(o);
1926
1927 Declaration *d;
1928 VarDeclaration *v = NULL;
1929
1930 if (ea && ea->op == TOKtype)
1931 ta = ea->type;
1932 else if (ea && ea->op == TOKscope)
1933 sa = ((ScopeExp *)ea)->sds;
1934 else if (ea && (ea->op == TOKthis || ea->op == TOKsuper))
1935 sa = ((ThisExp *)ea)->var;
1936 else if (ea && ea->op == TOKfunction)
1937 {
1938 if (((FuncExp *)ea)->td)
1939 sa = ((FuncExp *)ea)->td;
1940 else
1941 sa = ((FuncExp *)ea)->fd;
1942 }
1943
1944 if (ta)
1945 {
1946 //printf("type %s\n", ta->toChars());
1947 d = new AliasDeclaration(Loc(), tp->ident, ta);
1948 }
1949 else if (sa)
1950 {
1951 //printf("Alias %s %s;\n", sa->ident->toChars(), tp->ident->toChars());
1952 d = new AliasDeclaration(Loc(), tp->ident, sa);
1953 }
1954 else if (ea)
1955 {
1956 // tdtypes.data[i] always matches ea here
1957 Initializer *init = new ExpInitializer(loc, ea);
1958 TemplateValueParameter *tvp = tp->isTemplateValueParameter();
1959
1960 Type *t = tvp ? tvp->valType : NULL;
1961
1962 v = new VarDeclaration(loc, t, tp->ident, init);
1963 v->storage_class = STCmanifest | STCtemplateparameter;
1964 d = v;
1965 }
1966 else if (va)
1967 {
1968 //printf("\ttuple\n");
1969 d = new TupleDeclaration(loc, tp->ident, &va->objects);
1970 }
1971 else
1972 {
1973 assert(0);
1974 }
1975
1976 d->storage_class |= STCtemplateparameter;
1977 if (ta)
1978 {
1979 Type *t = ta;
1980 // consistent with Type::checkDeprecated()
1981 while (t->ty != Tenum)
1982 {
1983 if (!t->nextOf()) break;
1984 t = ((TypeNext *)t)->next;
1985 }
1986 if (Dsymbol *s = t->toDsymbol(sc))
1987 {
1988 if (s->isDeprecated())
1989 d->storage_class |= STCdeprecated;
1990 }
1991 }
1992 else if (sa)
1993 {
1994 if (sa->isDeprecated())
1995 d->storage_class |= STCdeprecated;
1996 }
1997
1998 if (!sc->insert(d))
1999 error("declaration %s is already defined", tp->ident->toChars());
2000 dsymbolSemantic(d, sc);
2001
2002 /* So the caller's o gets updated with the result of semantic() being run on o
2003 */
2004 if (v)
2005 o = initializerToExpression(v->_init);
2006 return o;
2007 }
2008
2009 /**************************************
2010 * Determine if TemplateDeclaration is variadic.
2011 */
2012
isVariadic(TemplateParameters * parameters)2013 TemplateTupleParameter *isVariadic(TemplateParameters *parameters)
2014 {
2015 size_t dim = parameters->length;
2016 TemplateTupleParameter *tp = NULL;
2017
2018 if (dim)
2019 tp = ((*parameters)[dim - 1])->isTemplateTupleParameter();
2020 return tp;
2021 }
2022
isVariadic()2023 TemplateTupleParameter *TemplateDeclaration::isVariadic()
2024 {
2025 return ::isVariadic(parameters);
2026 }
2027
2028 /***********************************
2029 * We can overload templates.
2030 */
2031
isOverloadable()2032 bool TemplateDeclaration::isOverloadable()
2033 {
2034 return true;
2035 }
2036
2037 /*************************************************
2038 * Given function arguments, figure out which template function
2039 * to expand, and return matching result.
2040 * Params:
2041 * m = matching result
2042 * dstart = the root of overloaded function templates
2043 * loc = instantiation location
2044 * sc = instantiation scope
2045 * tiargs = initial list of template arguments
2046 * tthis = if !NULL, the 'this' pointer argument
2047 * fargs = arguments to function
2048 * pMessage = address to store error message, or null
2049 */
2050
functionResolve(Match * m,Dsymbol * dstart,Loc loc,Scope * sc,Objects * tiargs,Type * tthis,Expressions * fargs,const char ** pMessage)2051 void functionResolve(Match *m, Dsymbol *dstart, Loc loc, Scope *sc,
2052 Objects *tiargs, Type *tthis, Expressions *fargs, const char **pMessage)
2053 {
2054 struct ParamDeduce
2055 {
2056 // context
2057 Loc loc;
2058 Scope *sc;
2059 Type *tthis;
2060 Objects *tiargs;
2061 Expressions *fargs;
2062 const char **pMessage;
2063 // result
2064 Match *m;
2065 int property; // 0: unintialized
2066 // 1: seen @property
2067 // 2: not @property
2068 size_t ov_index;
2069 TemplateDeclaration *td_best;
2070 TemplateInstance *ti_best;
2071 MATCH ta_last;
2072 Type *tthis_best;
2073
2074 static int fp(void *param, Dsymbol *s)
2075 {
2076 if (s->errors)
2077 return 0;
2078 if (FuncDeclaration *fd = s->isFuncDeclaration())
2079 return ((ParamDeduce *)param)->applyFunction(fd);
2080 if (TemplateDeclaration *td = s->isTemplateDeclaration())
2081 return ((ParamDeduce *)param)->applyTemplate(td);
2082 return 0;
2083 }
2084
2085 int applyFunction(FuncDeclaration *fd)
2086 {
2087 // skip duplicates
2088 if (fd == m->lastf)
2089 return 0;
2090 // explicitly specified tiargs never match to non template function
2091 if (tiargs && tiargs->length > 0)
2092 return 0;
2093
2094 // constructors need a valid scope in order to detect semantic errors
2095 if (!fd->isCtorDeclaration() &&
2096 fd->semanticRun < PASSsemanticdone)
2097 {
2098 Ungag ungag = fd->ungagSpeculative();
2099 dsymbolSemantic(fd, NULL);
2100 }
2101 if (fd->semanticRun < PASSsemanticdone)
2102 {
2103 ::error(loc, "forward reference to template %s", fd->toChars());
2104 return 1;
2105 }
2106 //printf("fd = %s %s, fargs = %s\n", fd->toChars(), fd->type->toChars(), fargs->toChars());
2107 m->anyf = fd;
2108 TypeFunction *tf = (TypeFunction *)fd->type;
2109
2110 int prop = (tf->isproperty) ? 1 : 2;
2111 if (property == 0)
2112 property = prop;
2113 else if (property != prop)
2114 error(fd->loc, "cannot overload both property and non-property functions");
2115
2116 /* For constructors, qualifier check will be opposite direction.
2117 * Qualified constructor always makes qualified object, then will be checked
2118 * that it is implicitly convertible to tthis.
2119 */
2120 Type *tthis_fd = fd->needThis() ? tthis : NULL;
2121 bool isCtorCall = tthis_fd && fd->isCtorDeclaration();
2122 if (isCtorCall)
2123 {
2124 //printf("%s tf->mod = x%x tthis_fd->mod = x%x %d\n", tf->toChars(),
2125 // tf->mod, tthis_fd->mod, fd->isolateReturn());
2126 if (MODimplicitConv(tf->mod, tthis_fd->mod) ||
2127 (tf->isWild() && tf->isShared() == tthis_fd->isShared()) ||
2128 fd->isolateReturn())
2129 {
2130 /* && tf->isShared() == tthis_fd->isShared()*/
2131 // Uniquely constructed object can ignore shared qualifier.
2132 // TODO: Is this appropriate?
2133 tthis_fd = NULL;
2134 }
2135 else
2136 return 0; // MATCHnomatch
2137 }
2138 MATCH mfa = tf->callMatch(tthis_fd, fargs, 0, pMessage);
2139 //printf("test1: mfa = %d\n", mfa);
2140 if (mfa > MATCHnomatch)
2141 {
2142 if (mfa > m->last) goto LfIsBetter;
2143 if (mfa < m->last) goto LlastIsBetter;
2144
2145 /* See if one of the matches overrides the other.
2146 */
2147 assert(m->lastf);
2148 if (m->lastf->overrides(fd)) goto LlastIsBetter;
2149 if (fd->overrides(m->lastf)) goto LfIsBetter;
2150
2151 /* Try to disambiguate using template-style partial ordering rules.
2152 * In essence, if f() and g() are ambiguous, if f() can call g(),
2153 * but g() cannot call f(), then pick f().
2154 * This is because f() is "more specialized."
2155 */
2156 {
2157 MATCH c1 = fd->leastAsSpecialized(m->lastf);
2158 MATCH c2 = m->lastf->leastAsSpecialized(fd);
2159 //printf("c1 = %d, c2 = %d\n", c1, c2);
2160 if (c1 > c2) goto LfIsBetter;
2161 if (c1 < c2) goto LlastIsBetter;
2162 }
2163
2164 /* The 'overrides' check above does covariant checking only
2165 * for virtual member functions. It should do it for all functions,
2166 * but in order to not risk breaking code we put it after
2167 * the 'leastAsSpecialized' check.
2168 * In the future try moving it before.
2169 * I.e. a not-the-same-but-covariant match is preferred,
2170 * as it is more restrictive.
2171 */
2172 if (!m->lastf->type->equals(fd->type))
2173 {
2174 //printf("cov: %d %d\n", m->lastf->type->covariant(fd->type), fd->type->covariant(m->lastf->type));
2175 if (m->lastf->type->covariant(fd->type) == 1) goto LlastIsBetter;
2176 if (fd->type->covariant(m->lastf->type) == 1) goto LfIsBetter;
2177 }
2178
2179 /* If the two functions are the same function, like:
2180 * int foo(int);
2181 * int foo(int x) { ... }
2182 * then pick the one with the body.
2183 */
2184 if (tf->equals(m->lastf->type) &&
2185 fd->storage_class == m->lastf->storage_class &&
2186 fd->parent == m->lastf->parent &&
2187 fd->protection == m->lastf->protection &&
2188 fd->linkage == m->lastf->linkage)
2189 {
2190 if ( fd->fbody && !m->lastf->fbody) goto LfIsBetter;
2191 if (!fd->fbody && m->lastf->fbody) goto LlastIsBetter;
2192 }
2193
2194 // Bugzilla 14450: Prefer exact qualified constructor for the creating object type
2195 if (isCtorCall && tf->mod != m->lastf->type->mod)
2196 {
2197 if (tthis->mod == tf->mod) goto LfIsBetter;
2198 if (tthis->mod == m->lastf->type->mod) goto LlastIsBetter;
2199 }
2200
2201 m->nextf = fd;
2202 m->count++;
2203 return 0;
2204
2205 LlastIsBetter:
2206 return 0;
2207
2208 LfIsBetter:
2209 td_best = NULL;
2210 ti_best = NULL;
2211 ta_last = MATCHexact;
2212 m->last = mfa;
2213 m->lastf = fd;
2214 tthis_best = tthis_fd;
2215 ov_index = 0;
2216 m->count = 1;
2217 return 0;
2218 }
2219 return 0;
2220 }
2221
2222 int applyTemplate(TemplateDeclaration *td)
2223 {
2224 //printf("applyTemplate()\n");
2225 if (td->inuse)
2226 {
2227 td->error(loc, "recursive template expansion");
2228 return 1;
2229 }
2230 if (td == td_best) // skip duplicates
2231 return 0;
2232
2233 if (!sc)
2234 sc = td->_scope; // workaround for Type::aliasthisOf
2235
2236 if (td->semanticRun == PASSinit && td->_scope)
2237 {
2238 // Try to fix forward reference. Ungag errors while doing so.
2239 Ungag ungag = td->ungagSpeculative();
2240 dsymbolSemantic(td, td->_scope);
2241 }
2242 if (td->semanticRun == PASSinit)
2243 {
2244 ::error(loc, "forward reference to template %s", td->toChars());
2245 Lerror:
2246 m->lastf = NULL;
2247 m->count = 0;
2248 m->last = MATCHnomatch;
2249 return 1;
2250 }
2251 //printf("td = %s\n", td->toChars());
2252
2253 FuncDeclaration *f;
2254 f = td->onemember ? td->onemember->isFuncDeclaration() : NULL;
2255 if (!f)
2256 {
2257 if (!tiargs)
2258 tiargs = new Objects();
2259 TemplateInstance *ti = new TemplateInstance(loc, td, tiargs);
2260 Objects dedtypes;
2261 dedtypes.setDim(td->parameters->length);
2262 assert(td->semanticRun != PASSinit);
2263 MATCH mta = td->matchWithInstance(sc, ti, &dedtypes, fargs, 0);
2264 //printf("matchWithInstance = %d\n", mta);
2265 if (mta <= MATCHnomatch || mta < ta_last) // no match or less match
2266 return 0;
2267
2268 templateInstanceSemantic(ti, sc, fargs);
2269 if (!ti->inst) // if template failed to expand
2270 return 0;
2271
2272 Dsymbol *s = ti->inst->toAlias();
2273 FuncDeclaration *fd;
2274 if (TemplateDeclaration *tdx = s->isTemplateDeclaration())
2275 {
2276 Objects dedtypesX; // empty tiargs
2277
2278 // Bugzilla 11553: Check for recursive instantiation of tdx.
2279 for (TemplatePrevious *p = tdx->previous; p; p = p->prev)
2280 {
2281 if (arrayObjectMatch(p->dedargs, &dedtypesX))
2282 {
2283 //printf("recursive, no match p->sc=%p %p %s\n", p->sc, this, this->toChars());
2284 /* It must be a subscope of p->sc, other scope chains are not recursive
2285 * instantiations.
2286 */
2287 for (Scope *scx = sc; scx; scx = scx->enclosing)
2288 {
2289 if (scx == p->sc)
2290 {
2291 error(loc, "recursive template expansion while looking for %s.%s", ti->toChars(), tdx->toChars());
2292 goto Lerror;
2293 }
2294 }
2295 }
2296 /* BUG: should also check for ref param differences
2297 */
2298 }
2299
2300 TemplatePrevious pr;
2301 pr.prev = tdx->previous;
2302 pr.sc = sc;
2303 pr.dedargs = &dedtypesX;
2304 tdx->previous = ≺ // add this to threaded list
2305
2306 fd = resolveFuncCall(loc, sc, s, NULL, tthis, fargs, 1);
2307
2308 tdx->previous = pr.prev; // unlink from threaded list
2309 }
2310 else if (s->isFuncDeclaration())
2311 {
2312 fd = resolveFuncCall(loc, sc, s, NULL, tthis, fargs, 1);
2313 }
2314 else
2315 goto Lerror;
2316
2317 if (!fd)
2318 return 0;
2319
2320 if (fd->type->ty != Tfunction)
2321 {
2322 m->lastf = fd; // to propagate "error match"
2323 m->count = 1;
2324 m->last = MATCHnomatch;
2325 return 1;
2326 }
2327
2328 Type *tthis_fd = fd->needThis() && !fd->isCtorDeclaration() ? tthis : NULL;
2329
2330 TypeFunction *tf = (TypeFunction *)fd->type;
2331 MATCH mfa = tf->callMatch(tthis_fd, fargs);
2332 if (mfa < m->last)
2333 return 0;
2334
2335 if (mta < ta_last) goto Ltd_best2;
2336 if (mta > ta_last) goto Ltd2;
2337
2338 if (mfa < m->last) goto Ltd_best2;
2339 if (mfa > m->last) goto Ltd2;
2340
2341 //printf("Lambig2\n");
2342 m->nextf = fd;
2343 m->count++;
2344 return 0;
2345
2346 Ltd_best2:
2347 return 0;
2348
2349 Ltd2:
2350 // td is the new best match
2351 assert(td->_scope);
2352 td_best = td;
2353 ti_best = NULL;
2354 property = 0; // (backward compatibility)
2355 ta_last = mta;
2356 m->last = mfa;
2357 m->lastf = fd;
2358 tthis_best = tthis_fd;
2359 ov_index = 0;
2360 m->nextf = NULL;
2361 m->count = 1;
2362 return 0;
2363 }
2364
2365 //printf("td = %s\n", td->toChars());
2366 for (size_t ovi = 0; f; f = f->overnext0, ovi++)
2367 {
2368 if (f->type->ty != Tfunction || f->errors)
2369 goto Lerror;
2370
2371 /* This is a 'dummy' instance to evaluate constraint properly.
2372 */
2373 TemplateInstance *ti = new TemplateInstance(loc, td, tiargs);
2374 ti->parent = td->parent; // Maybe calculating valid 'enclosing' is unnecessary.
2375
2376 FuncDeclaration *fd = f;
2377 int x = td->deduceFunctionTemplateMatch(ti, sc, fd, tthis, fargs);
2378 MATCH mta = (MATCH)(x >> 4);
2379 MATCH mfa = (MATCH)(x & 0xF);
2380 //printf("match:t/f = %d/%d\n", mta, mfa);
2381 if (!fd || mfa == MATCHnomatch)
2382 continue;
2383
2384 Type *tthis_fd = fd->needThis() ? tthis : NULL;
2385
2386 bool isCtorCall = tthis_fd && fd->isCtorDeclaration();
2387 if (isCtorCall)
2388 {
2389 // Constructor call requires additional check.
2390
2391 TypeFunction *tf = (TypeFunction *)fd->type;
2392 assert(tf->next);
2393 if (MODimplicitConv(tf->mod, tthis_fd->mod) ||
2394 (tf->isWild() && tf->isShared() == tthis_fd->isShared()) ||
2395 fd->isolateReturn())
2396 {
2397 tthis_fd = NULL;
2398 }
2399 else
2400 continue; // MATCHnomatch
2401 }
2402
2403 if (mta < ta_last) goto Ltd_best;
2404 if (mta > ta_last) goto Ltd;
2405
2406 if (mfa < m->last) goto Ltd_best;
2407 if (mfa > m->last) goto Ltd;
2408
2409 if (td_best)
2410 {
2411 // Disambiguate by picking the most specialized TemplateDeclaration
2412 MATCH c1 = td->leastAsSpecialized(sc, td_best, fargs);
2413 MATCH c2 = td_best->leastAsSpecialized(sc, td, fargs);
2414 //printf("1: c1 = %d, c2 = %d\n", c1, c2);
2415 if (c1 > c2) goto Ltd;
2416 if (c1 < c2) goto Ltd_best;
2417 }
2418 assert(fd && m->lastf);
2419 {
2420 // Disambiguate by tf->callMatch
2421 TypeFunction *tf1 = (TypeFunction *)fd->type;
2422 assert(tf1->ty == Tfunction);
2423 TypeFunction *tf2 = (TypeFunction *)m->lastf->type;
2424 assert(tf2->ty == Tfunction);
2425 MATCH c1 = tf1->callMatch(tthis_fd, fargs);
2426 MATCH c2 = tf2->callMatch(tthis_best, fargs);
2427 //printf("2: c1 = %d, c2 = %d\n", c1, c2);
2428 if (c1 > c2) goto Ltd;
2429 if (c1 < c2) goto Ltd_best;
2430 }
2431 {
2432 // Disambiguate by picking the most specialized FunctionDeclaration
2433 MATCH c1 = fd->leastAsSpecialized(m->lastf);
2434 MATCH c2 = m->lastf->leastAsSpecialized(fd);
2435 //printf("3: c1 = %d, c2 = %d\n", c1, c2);
2436 if (c1 > c2) goto Ltd;
2437 if (c1 < c2) goto Ltd_best;
2438 }
2439
2440 // Bugzilla 14450: Prefer exact qualified constructor for the creating object type
2441 if (isCtorCall && fd->type->mod != m->lastf->type->mod)
2442 {
2443 if (tthis->mod == fd->type->mod) goto Ltd;
2444 if (tthis->mod == m->lastf->type->mod) goto Ltd_best;
2445 }
2446
2447 m->nextf = fd;
2448 m->count++;
2449 continue;
2450
2451 Ltd_best: // td_best is the best match so far
2452 //printf("Ltd_best\n");
2453 continue;
2454
2455 Ltd: // td is the new best match
2456 //printf("Ltd\n");
2457 assert(td->_scope);
2458 td_best = td;
2459 ti_best = ti;
2460 property = 0; // (backward compatibility)
2461 ta_last = mta;
2462 m->last = mfa;
2463 m->lastf = fd;
2464 tthis_best = tthis_fd;
2465 ov_index = ovi;
2466 m->nextf = NULL;
2467 m->count = 1;
2468 continue;
2469 }
2470 return 0;
2471 }
2472 };
2473 ParamDeduce p;
2474 // context
2475 p.loc = loc;
2476 p.sc = sc;
2477 p.tthis = tthis;
2478 p.tiargs = tiargs;
2479 p.fargs = fargs;
2480 p.pMessage = pMessage;
2481
2482 // result
2483 p.m = m;
2484 p.property = 0;
2485 p.ov_index = 0;
2486 p.td_best = NULL;
2487 p.ti_best = NULL;
2488 p.ta_last = m->last != MATCHnomatch ? MATCHexact : MATCHnomatch;
2489 p.tthis_best = NULL;
2490
2491 TemplateDeclaration *td = dstart->isTemplateDeclaration();
2492 if (td && td->funcroot)
2493 dstart = td->funcroot;
2494
2495 overloadApply(dstart, &p, &ParamDeduce::fp);
2496
2497 //printf("td_best = %p, m->lastf = %p\n", p.td_best, m->lastf);
2498 if (p.td_best && p.ti_best && m->count == 1)
2499 {
2500 // Matches to template function
2501 assert(p.td_best->onemember && p.td_best->onemember->isFuncDeclaration());
2502
2503 /* The best match is td_best with arguments tdargs.
2504 * Now instantiate the template.
2505 */
2506 assert(p.td_best->_scope);
2507 if (!sc)
2508 sc = p.td_best->_scope; // workaround for Type::aliasthisOf
2509
2510 TemplateInstance *ti = new TemplateInstance(loc, p.td_best, p.ti_best->tiargs);
2511 templateInstanceSemantic(ti, sc, fargs);
2512
2513 m->lastf = ti->toAlias()->isFuncDeclaration();
2514 if (!m->lastf)
2515 goto Lnomatch;
2516 if (ti->errors)
2517 {
2518 Lerror:
2519 m->count = 1;
2520 assert(m->lastf);
2521 m->last = MATCHnomatch;
2522 return;
2523 }
2524
2525 // look forward instantiated overload function
2526 // Dsymbol::oneMembers is alredy called in TemplateInstance::semantic.
2527 // it has filled overnext0d
2528 while (p.ov_index--)
2529 {
2530 m->lastf = m->lastf->overnext0;
2531 assert(m->lastf);
2532 }
2533
2534 p.tthis_best = m->lastf->needThis() && !m->lastf->isCtorDeclaration() ? tthis : NULL;
2535
2536 TypeFunction *tf = (TypeFunction *)m->lastf->type;
2537 if (tf->ty == Terror)
2538 goto Lerror;
2539 assert(tf->ty == Tfunction);
2540 if (!tf->callMatch(p.tthis_best, fargs))
2541 goto Lnomatch;
2542
2543 /* As Bugzilla 3682 shows, a template instance can be matched while instantiating
2544 * that same template. Thus, the function type can be incomplete. Complete it.
2545 *
2546 * Bugzilla 9208: For auto function, completion should be deferred to the end of
2547 * its semantic3. Should not complete it in here.
2548 */
2549 if (tf->next && !m->lastf->inferRetType)
2550 {
2551 m->lastf->type = typeSemantic(tf, loc, sc);
2552 }
2553 }
2554 else if (m->lastf)
2555 {
2556 // Matches to non template function,
2557 // or found matches were ambiguous.
2558 assert(m->count >= 1);
2559 }
2560 else
2561 {
2562 Lnomatch:
2563 m->count = 0;
2564 m->lastf = NULL;
2565 m->last = MATCHnomatch;
2566 }
2567 }
2568
2569 /*************************************************
2570 * Limited function template instantiation for using fd->leastAsSpecialized()
2571 */
doHeaderInstantiation(TemplateInstance * ti,Scope * sc2,FuncDeclaration * fd,Type * tthis,Expressions * fargs)2572 FuncDeclaration *TemplateDeclaration::doHeaderInstantiation(
2573 TemplateInstance *ti, Scope *sc2,
2574 FuncDeclaration *fd, Type *tthis, Expressions *fargs)
2575 {
2576 assert(fd);
2577
2578 // function body and contracts are not need
2579 if (fd->isCtorDeclaration())
2580 fd = new CtorDeclaration(fd->loc, fd->endloc, fd->storage_class, fd->type->syntaxCopy());
2581 else
2582 fd = new FuncDeclaration(fd->loc, fd->endloc, fd->ident, fd->storage_class, fd->type->syntaxCopy());
2583 fd->parent = ti;
2584
2585 assert(fd->type->ty == Tfunction);
2586 TypeFunction *tf = (TypeFunction *)fd->type;
2587 tf->fargs = fargs;
2588
2589 if (tthis)
2590 {
2591 // Match 'tthis' to any TemplateThisParameter's
2592 bool hasttp = false;
2593 for (size_t i = 0; i < parameters->length; i++)
2594 {
2595 TemplateParameter *tp = (*parameters)[i];
2596 TemplateThisParameter *ttp = tp->isTemplateThisParameter();
2597 if (ttp)
2598 hasttp = true;
2599 }
2600 if (hasttp)
2601 {
2602 tf = (TypeFunction *)tf->addSTC(ModToStc(tthis->mod));
2603 assert(!tf->deco);
2604 }
2605 }
2606
2607 Scope *scx = sc2->push();
2608
2609 // Shouldn't run semantic on default arguments and return type.
2610 for (size_t i = 0; i < tf->parameterList.parameters->length; i++)
2611 (*tf->parameterList.parameters)[i]->defaultArg = NULL;
2612 if (fd->isCtorDeclaration())
2613 {
2614 // For constructors, emitting return type is necessary for
2615 // isolateReturn() in functionResolve.
2616 scx->flags |= SCOPEctor;
2617
2618 Dsymbol *parent = toParent2();
2619 Type *tret;
2620 AggregateDeclaration *ad = parent->isAggregateDeclaration();
2621 if (!ad || parent->isUnionDeclaration())
2622 {
2623 tret = Type::tvoid;
2624 }
2625 else
2626 {
2627 tret = ad->handleType();
2628 assert(tret);
2629 tret = tret->addStorageClass(fd->storage_class | scx->stc);
2630 tret = tret->addMod(tf->mod);
2631 }
2632 tf->next = tret;
2633 if (ad && ad->isStructDeclaration())
2634 tf->isref = 1;
2635 //printf("tf = %s\n", tf->toChars());
2636 }
2637 else
2638 tf->next = NULL;
2639 fd->type = tf;
2640 fd->type = fd->type->addSTC(scx->stc);
2641 fd->type = typeSemantic(fd->type, fd->loc, scx);
2642 scx = scx->pop();
2643
2644 if (fd->type->ty != Tfunction)
2645 return NULL;
2646
2647 fd->originalType = fd->type; // for mangling
2648 //printf("\t[%s] fd->type = %s, mod = %x, ", loc.toChars(), fd->type->toChars(), fd->type->mod);
2649 //printf("fd->needThis() = %d\n", fd->needThis());
2650
2651 return fd;
2652 }
2653
hasStaticCtorOrDtor()2654 bool TemplateDeclaration::hasStaticCtorOrDtor()
2655 {
2656 return false; // don't scan uninstantiated templates
2657 }
2658
toChars()2659 const char *TemplateDeclaration::toChars()
2660 {
2661 if (literal)
2662 return Dsymbol::toChars();
2663
2664 OutBuffer buf;
2665 HdrGenState hgs;
2666
2667 buf.writestring(ident->toChars());
2668 buf.writeByte('(');
2669 for (size_t i = 0; i < parameters->length; i++)
2670 {
2671 TemplateParameter *tp = (*parameters)[i];
2672 if (i)
2673 buf.writestring(", ");
2674 ::toCBuffer(tp, &buf, &hgs);
2675 }
2676 buf.writeByte(')');
2677
2678 if (onemember)
2679 {
2680 FuncDeclaration *fd = onemember->isFuncDeclaration();
2681 if (fd && fd->type)
2682 {
2683 TypeFunction *tf = (TypeFunction *)fd->type;
2684 buf.writestring(parametersTypeToChars(tf->parameterList));
2685 }
2686 }
2687
2688 if (constraint)
2689 {
2690 buf.writestring(" if (");
2691 ::toCBuffer(constraint, &buf, &hgs);
2692 buf.writeByte(')');
2693 }
2694 return buf.extractChars();
2695 }
2696
prot()2697 Prot TemplateDeclaration::prot()
2698 {
2699 return protection;
2700 }
2701
2702 /****************************************************
2703 * Given a new instance tithis of this TemplateDeclaration,
2704 * see if there already exists an instance.
2705 * If so, return that existing instance.
2706 */
2707
findExistingInstance(TemplateInstance * tithis,Expressions * fargs)2708 TemplateInstance *TemplateDeclaration::findExistingInstance(TemplateInstance *tithis, Expressions *fargs)
2709 {
2710 //printf("findExistingInstance(%p)\n", tithis);
2711 tithis->fargs = fargs;
2712 TemplateInstances *tinstances = (TemplateInstances *)dmd_aaGetRvalue((AA *)instances, (void *)tithis->toHash());
2713 if (tinstances)
2714 {
2715 for (size_t i = 0; i < tinstances->length; i++)
2716 {
2717 TemplateInstance *ti = (*tinstances)[i];
2718 if (tithis->compare(ti) == 0)
2719 return ti;
2720 }
2721 }
2722 return NULL;
2723 }
2724
2725 /********************************************
2726 * Add instance ti to TemplateDeclaration's table of instances.
2727 * Return a handle we can use to later remove it if it fails instantiation.
2728 */
2729
addInstance(TemplateInstance * ti)2730 TemplateInstance *TemplateDeclaration::addInstance(TemplateInstance *ti)
2731 {
2732 //printf("addInstance() %p %p\n", instances, ti);
2733 TemplateInstances **ptinstances = (TemplateInstances **)dmd_aaGet((AA **)&instances, (void *)ti->toHash());
2734 if (!*ptinstances)
2735 *ptinstances = new TemplateInstances();
2736 (*ptinstances)->push(ti);
2737 return ti;
2738 }
2739
2740 /*******************************************
2741 * Remove TemplateInstance from table of instances.
2742 * Input:
2743 * handle returned by addInstance()
2744 */
2745
removeInstance(TemplateInstance * handle)2746 void TemplateDeclaration::removeInstance(TemplateInstance *handle)
2747 {
2748 //printf("removeInstance()\n");
2749 TemplateInstances *tinstances = (TemplateInstances *)dmd_aaGetRvalue((AA *)instances, (void *)handle->toHash());
2750 if (tinstances)
2751 {
2752 for (size_t i = 0; i < tinstances->length; i++)
2753 {
2754 TemplateInstance *ti = (*tinstances)[i];
2755 if (handle == ti)
2756 {
2757 tinstances->remove(i);
2758 break;
2759 }
2760 }
2761 }
2762 }
2763
2764 /* ======================== Type ============================================ */
2765
2766 /****
2767 * Given an identifier, figure out which TemplateParameter it is.
2768 * Return IDX_NOTFOUND if not found.
2769 */
2770
templateIdentifierLookup(Identifier * id,TemplateParameters * parameters)2771 static size_t templateIdentifierLookup(Identifier *id, TemplateParameters *parameters)
2772 {
2773 for (size_t i = 0; i < parameters->length; i++)
2774 {
2775 TemplateParameter *tp = (*parameters)[i];
2776 if (tp->ident->equals(id))
2777 return i;
2778 }
2779 return IDX_NOTFOUND;
2780 }
2781
templateParameterLookup(Type * tparam,TemplateParameters * parameters)2782 size_t templateParameterLookup(Type *tparam, TemplateParameters *parameters)
2783 {
2784 if (tparam->ty == Tident)
2785 {
2786 TypeIdentifier *tident = (TypeIdentifier *)tparam;
2787 //printf("\ttident = '%s'\n", tident->toChars());
2788 return templateIdentifierLookup(tident->ident, parameters);
2789 }
2790 return IDX_NOTFOUND;
2791 }
2792
deduceWildHelper(Type * t,Type ** at,Type * tparam)2793 unsigned char deduceWildHelper(Type *t, Type **at, Type *tparam)
2794 {
2795 if ((tparam->mod & MODwild) == 0)
2796 return 0;
2797
2798 *at = NULL;
2799
2800 #define X(U,T) ((U) << 4) | (T)
2801 switch (X(tparam->mod, t->mod))
2802 {
2803 case X(MODwild, 0):
2804 case X(MODwild, MODconst):
2805 case X(MODwild, MODshared):
2806 case X(MODwild, MODshared | MODconst):
2807 case X(MODwild, MODimmutable):
2808 case X(MODwildconst, 0):
2809 case X(MODwildconst, MODconst):
2810 case X(MODwildconst, MODshared):
2811 case X(MODwildconst, MODshared | MODconst):
2812 case X(MODwildconst, MODimmutable):
2813 case X(MODshared | MODwild, MODshared):
2814 case X(MODshared | MODwild, MODshared | MODconst):
2815 case X(MODshared | MODwild, MODimmutable):
2816 case X(MODshared | MODwildconst, MODshared):
2817 case X(MODshared | MODwildconst, MODshared | MODconst):
2818 case X(MODshared | MODwildconst, MODimmutable):
2819 {
2820 unsigned char wm = (t->mod & ~MODshared);
2821 if (wm == 0)
2822 wm = MODmutable;
2823 unsigned char m = (t->mod & (MODconst | MODimmutable)) | (tparam->mod & t->mod & MODshared);
2824 *at = t->unqualify(m);
2825 return wm;
2826 }
2827
2828 case X(MODwild, MODwild):
2829 case X(MODwild, MODwildconst):
2830 case X(MODwild, MODshared | MODwild):
2831 case X(MODwild, MODshared | MODwildconst):
2832 case X(MODwildconst, MODwild):
2833 case X(MODwildconst, MODwildconst):
2834 case X(MODwildconst, MODshared | MODwild):
2835 case X(MODwildconst, MODshared | MODwildconst):
2836 case X(MODshared | MODwild, MODshared | MODwild):
2837 case X(MODshared | MODwild, MODshared | MODwildconst):
2838 case X(MODshared | MODwildconst, MODshared | MODwild):
2839 case X(MODshared | MODwildconst, MODshared | MODwildconst):
2840 {
2841 *at = t->unqualify(tparam->mod & t->mod);
2842 return MODwild;
2843 }
2844
2845 default:
2846 return 0;
2847 }
2848 #undef X
2849 }
2850
deduceTypeHelper(Type * t,Type ** at,Type * tparam)2851 MATCH deduceTypeHelper(Type *t, Type **at, Type *tparam)
2852 {
2853 // 9*9 == 81 cases
2854
2855 #define X(U,T) ((U) << 4) | (T)
2856 switch (X(tparam->mod, t->mod))
2857 {
2858 case X(0, 0):
2859 case X(0, MODconst):
2860 case X(0, MODwild):
2861 case X(0, MODwildconst):
2862 case X(0, MODshared):
2863 case X(0, MODshared | MODconst):
2864 case X(0, MODshared | MODwild):
2865 case X(0, MODshared | MODwildconst):
2866 case X(0, MODimmutable):
2867 // foo(U) T => T
2868 // foo(U) const(T) => const(T)
2869 // foo(U) inout(T) => inout(T)
2870 // foo(U) inout(const(T)) => inout(const(T))
2871 // foo(U) shared(T) => shared(T)
2872 // foo(U) shared(const(T)) => shared(const(T))
2873 // foo(U) shared(inout(T)) => shared(inout(T))
2874 // foo(U) shared(inout(const(T))) => shared(inout(const(T)))
2875 // foo(U) immutable(T) => immutable(T)
2876 {
2877 *at = t;
2878 return MATCHexact;
2879 }
2880
2881 case X(MODconst, MODconst):
2882 case X(MODwild, MODwild):
2883 case X(MODwildconst, MODwildconst):
2884 case X(MODshared, MODshared):
2885 case X(MODshared | MODconst, MODshared | MODconst):
2886 case X(MODshared | MODwild, MODshared | MODwild):
2887 case X(MODshared | MODwildconst, MODshared | MODwildconst):
2888 case X(MODimmutable, MODimmutable):
2889 // foo(const(U)) const(T) => T
2890 // foo(inout(U)) inout(T) => T
2891 // foo(inout(const(U))) inout(const(T)) => T
2892 // foo(shared(U)) shared(T) => T
2893 // foo(shared(const(U))) shared(const(T)) => T
2894 // foo(shared(inout(U))) shared(inout(T)) => T
2895 // foo(shared(inout(const(U)))) shared(inout(const(T))) => T
2896 // foo(immutable(U)) immutable(T) => T
2897 {
2898 *at = t->mutableOf()->unSharedOf();
2899 return MATCHexact;
2900 }
2901
2902 case X(MODconst, 0):
2903 case X(MODconst, MODwild):
2904 case X(MODconst, MODwildconst):
2905 case X(MODconst, MODshared | MODconst):
2906 case X(MODconst, MODshared | MODwild):
2907 case X(MODconst, MODshared | MODwildconst):
2908 case X(MODconst, MODimmutable):
2909 case X(MODwild, MODshared | MODwild):
2910 case X(MODwildconst, MODshared | MODwildconst):
2911 case X(MODshared | MODconst, MODimmutable):
2912 // foo(const(U)) T => T
2913 // foo(const(U)) inout(T) => T
2914 // foo(const(U)) inout(const(T)) => T
2915 // foo(const(U)) shared(const(T)) => shared(T)
2916 // foo(const(U)) shared(inout(T)) => shared(T)
2917 // foo(const(U)) shared(inout(const(T))) => shared(T)
2918 // foo(const(U)) immutable(T) => T
2919 // foo(inout(U)) shared(inout(T)) => shared(T)
2920 // foo(inout(const(U))) shared(inout(const(T))) => shared(T)
2921 // foo(shared(const(U))) immutable(T) => T
2922 {
2923 *at = t->mutableOf();
2924 return MATCHconst;
2925 }
2926
2927 case X(MODconst, MODshared):
2928 // foo(const(U)) shared(T) => shared(T)
2929 {
2930 *at = t;
2931 return MATCHconst;
2932 }
2933
2934 case X(MODshared, MODshared | MODconst):
2935 case X(MODshared, MODshared | MODwild):
2936 case X(MODshared, MODshared | MODwildconst):
2937 case X(MODshared | MODconst, MODshared):
2938 // foo(shared(U)) shared(const(T)) => const(T)
2939 // foo(shared(U)) shared(inout(T)) => inout(T)
2940 // foo(shared(U)) shared(inout(const(T))) => inout(const(T))
2941 // foo(shared(const(U))) shared(T) => T
2942 {
2943 *at = t->unSharedOf();
2944 return MATCHconst;
2945 }
2946
2947 case X(MODwildconst, MODimmutable):
2948 case X(MODshared | MODconst, MODshared | MODwildconst):
2949 case X(MODshared | MODwildconst, MODimmutable):
2950 case X(MODshared | MODwildconst, MODshared | MODwild):
2951 // foo(inout(const(U))) immutable(T) => T
2952 // foo(shared(const(U))) shared(inout(const(T))) => T
2953 // foo(shared(inout(const(U)))) immutable(T) => T
2954 // foo(shared(inout(const(U)))) shared(inout(T)) => T
2955 {
2956 *at = t->unSharedOf()->mutableOf();
2957 return MATCHconst;
2958 }
2959
2960 case X(MODshared | MODconst, MODshared | MODwild):
2961 // foo(shared(const(U))) shared(inout(T)) => T
2962 {
2963 *at = t->unSharedOf()->mutableOf();
2964 return MATCHconst;
2965 }
2966
2967 case X(MODwild, 0):
2968 case X(MODwild, MODconst):
2969 case X(MODwild, MODwildconst):
2970 case X(MODwild, MODimmutable):
2971 case X(MODwild, MODshared):
2972 case X(MODwild, MODshared | MODconst):
2973 case X(MODwild, MODshared | MODwildconst):
2974 case X(MODwildconst, 0):
2975 case X(MODwildconst, MODconst):
2976 case X(MODwildconst, MODwild):
2977 case X(MODwildconst, MODshared):
2978 case X(MODwildconst, MODshared | MODconst):
2979 case X(MODwildconst, MODshared | MODwild):
2980 case X(MODshared, 0):
2981 case X(MODshared, MODconst):
2982 case X(MODshared, MODwild):
2983 case X(MODshared, MODwildconst):
2984 case X(MODshared, MODimmutable):
2985 case X(MODshared | MODconst, 0):
2986 case X(MODshared | MODconst, MODconst):
2987 case X(MODshared | MODconst, MODwild):
2988 case X(MODshared | MODconst, MODwildconst):
2989 case X(MODshared | MODwild, 0):
2990 case X(MODshared | MODwild, MODconst):
2991 case X(MODshared | MODwild, MODwild):
2992 case X(MODshared | MODwild, MODwildconst):
2993 case X(MODshared | MODwild, MODimmutable):
2994 case X(MODshared | MODwild, MODshared):
2995 case X(MODshared | MODwild, MODshared | MODconst):
2996 case X(MODshared | MODwild, MODshared | MODwildconst):
2997 case X(MODshared | MODwildconst, 0):
2998 case X(MODshared | MODwildconst, MODconst):
2999 case X(MODshared | MODwildconst, MODwild):
3000 case X(MODshared | MODwildconst, MODwildconst):
3001 case X(MODshared | MODwildconst, MODshared):
3002 case X(MODshared | MODwildconst, MODshared | MODconst):
3003 case X(MODimmutable, 0):
3004 case X(MODimmutable, MODconst):
3005 case X(MODimmutable, MODwild):
3006 case X(MODimmutable, MODwildconst):
3007 case X(MODimmutable, MODshared):
3008 case X(MODimmutable, MODshared | MODconst):
3009 case X(MODimmutable, MODshared | MODwild):
3010 case X(MODimmutable, MODshared | MODwildconst):
3011 // foo(inout(U)) T => nomatch
3012 // foo(inout(U)) const(T) => nomatch
3013 // foo(inout(U)) inout(const(T)) => nomatch
3014 // foo(inout(U)) immutable(T) => nomatch
3015 // foo(inout(U)) shared(T) => nomatch
3016 // foo(inout(U)) shared(const(T)) => nomatch
3017 // foo(inout(U)) shared(inout(const(T))) => nomatch
3018 // foo(inout(const(U))) T => nomatch
3019 // foo(inout(const(U))) const(T) => nomatch
3020 // foo(inout(const(U))) inout(T) => nomatch
3021 // foo(inout(const(U))) shared(T) => nomatch
3022 // foo(inout(const(U))) shared(const(T)) => nomatch
3023 // foo(inout(const(U))) shared(inout(T)) => nomatch
3024 // foo(shared(U)) T => nomatch
3025 // foo(shared(U)) const(T) => nomatch
3026 // foo(shared(U)) inout(T) => nomatch
3027 // foo(shared(U)) inout(const(T)) => nomatch
3028 // foo(shared(U)) immutable(T) => nomatch
3029 // foo(shared(const(U))) T => nomatch
3030 // foo(shared(const(U))) const(T) => nomatch
3031 // foo(shared(const(U))) inout(T) => nomatch
3032 // foo(shared(const(U))) inout(const(T)) => nomatch
3033 // foo(shared(inout(U))) T => nomatch
3034 // foo(shared(inout(U))) const(T) => nomatch
3035 // foo(shared(inout(U))) inout(T) => nomatch
3036 // foo(shared(inout(U))) inout(const(T)) => nomatch
3037 // foo(shared(inout(U))) immutable(T) => nomatch
3038 // foo(shared(inout(U))) shared(T) => nomatch
3039 // foo(shared(inout(U))) shared(const(T)) => nomatch
3040 // foo(shared(inout(U))) shared(inout(const(T))) => nomatch
3041 // foo(shared(inout(const(U)))) T => nomatch
3042 // foo(shared(inout(const(U)))) const(T) => nomatch
3043 // foo(shared(inout(const(U)))) inout(T) => nomatch
3044 // foo(shared(inout(const(U)))) inout(const(T)) => nomatch
3045 // foo(shared(inout(const(U)))) shared(T) => nomatch
3046 // foo(shared(inout(const(U)))) shared(const(T)) => nomatch
3047 // foo(immutable(U)) T => nomatch
3048 // foo(immutable(U)) const(T) => nomatch
3049 // foo(immutable(U)) inout(T) => nomatch
3050 // foo(immutable(U)) inout(const(T)) => nomatch
3051 // foo(immutable(U)) shared(T) => nomatch
3052 // foo(immutable(U)) shared(const(T)) => nomatch
3053 // foo(immutable(U)) shared(inout(T)) => nomatch
3054 // foo(immutable(U)) shared(inout(const(T))) => nomatch
3055 return MATCHnomatch;
3056
3057 default:
3058 assert(0);
3059 return MATCHnomatch; // silence compiler warning about missing return
3060 }
3061 #undef X
3062 }
3063
3064 /* These form the heart of template argument deduction.
3065 * Given 'this' being the type argument to the template instance,
3066 * it is matched against the template declaration parameter specialization
3067 * 'tparam' to determine the type to be used for the parameter.
3068 * Example:
3069 * template Foo(T:T*) // template declaration
3070 * Foo!(int*) // template instantiation
3071 * Input:
3072 * this = int*
3073 * tparam = T*
3074 * parameters = [ T:T* ] // Array of TemplateParameter's
3075 * Output:
3076 * dedtypes = [ int ] // Array of Expression/Type's
3077 */
deduceType(RootObject * o,Scope * sc,Type * tparam,TemplateParameters * parameters,Objects * dedtypes,unsigned * wm,size_t inferStart)3078 MATCH deduceType(RootObject *o, Scope *sc, Type *tparam, TemplateParameters *parameters,
3079 Objects *dedtypes, unsigned *wm, size_t inferStart)
3080 {
3081 class DeduceType : public Visitor
3082 {
3083 public:
3084 Scope *sc;
3085 Type *tparam;
3086 TemplateParameters *parameters;
3087 Objects *dedtypes;
3088 unsigned *wm;
3089 size_t inferStart;
3090 MATCH result;
3091
3092 DeduceType(Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes, unsigned *wm, size_t inferStart)
3093 : sc(sc), tparam(tparam), parameters(parameters), dedtypes(dedtypes), wm(wm), inferStart(inferStart)
3094 {
3095 result = MATCHnomatch;
3096 }
3097
3098 void visit(Type *t)
3099 {
3100 if (!tparam)
3101 goto Lnomatch;
3102
3103 if (t == tparam)
3104 goto Lexact;
3105
3106 if (tparam->ty == Tident)
3107 {
3108 // Determine which parameter tparam is
3109 size_t i = templateParameterLookup(tparam, parameters);
3110 if (i == IDX_NOTFOUND)
3111 {
3112 if (!sc)
3113 goto Lnomatch;
3114
3115 /* Need a loc to go with the semantic routine.
3116 */
3117 Loc loc;
3118 if (parameters->length)
3119 {
3120 TemplateParameter *tp = (*parameters)[0];
3121 loc = tp->loc;
3122 }
3123
3124 /* BUG: what if tparam is a template instance, that
3125 * has as an argument another Tident?
3126 */
3127 tparam = typeSemantic(tparam, loc, sc);
3128 assert(tparam->ty != Tident);
3129 result = deduceType(t, sc, tparam, parameters, dedtypes, wm);
3130 return;
3131 }
3132
3133 TemplateParameter *tp = (*parameters)[i];
3134
3135 TypeIdentifier *tident = (TypeIdentifier *)tparam;
3136 if (tident->idents.length > 0)
3137 {
3138 //printf("matching %s to %s\n", tparam->toChars(), t->toChars());
3139 Dsymbol *s = t->toDsymbol(sc);
3140 for (size_t j = tident->idents.length; j-- > 0; )
3141 {
3142 RootObject *id = tident->idents[j];
3143 if (id->dyncast() == DYNCAST_IDENTIFIER)
3144 {
3145 if (!s || !s->parent)
3146 goto Lnomatch;
3147 Dsymbol *s2 = s->parent->search(Loc(), (Identifier *)id);
3148 if (!s2)
3149 goto Lnomatch;
3150 s2 = s2->toAlias();
3151 //printf("[%d] s = %s %s, s2 = %s %s\n", j, s->kind(), s->toChars(), s2->kind(), s2->toChars());
3152 if (s != s2)
3153 {
3154 if (Type *tx = s2->getType())
3155 {
3156 if (s != tx->toDsymbol(sc))
3157 goto Lnomatch;
3158 }
3159 else
3160 goto Lnomatch;
3161 }
3162 s = s->parent;
3163 }
3164 else
3165 goto Lnomatch;
3166 }
3167 //printf("[e] s = %s\n", s?s->toChars():"(null)");
3168 if (tp->isTemplateTypeParameter())
3169 {
3170 Type *tt = s->getType();
3171 if (!tt)
3172 goto Lnomatch;
3173 Type *at = (Type *)(*dedtypes)[i];
3174 if (at && at->ty == Tnone)
3175 at = ((TypeDeduced *)at)->tded;
3176 if (!at || tt->equals(at))
3177 {
3178 (*dedtypes)[i] = tt;
3179 goto Lexact;
3180 }
3181 }
3182 if (tp->isTemplateAliasParameter())
3183 {
3184 Dsymbol *s2 = (Dsymbol *)(*dedtypes)[i];
3185 if (!s2 || s == s2)
3186 {
3187 (*dedtypes)[i] = s;
3188 goto Lexact;
3189 }
3190 }
3191 goto Lnomatch;
3192 }
3193
3194 // Found the corresponding parameter tp
3195 if (!tp->isTemplateTypeParameter())
3196 goto Lnomatch;
3197
3198 Type *at = (Type *)(*dedtypes)[i];
3199 Type *tt;
3200 if (unsigned char wx = wm ? deduceWildHelper(t, &tt, tparam) : 0)
3201 {
3202 // type vs (none)
3203 if (!at)
3204 {
3205 (*dedtypes)[i] = tt;
3206 *wm |= wx;
3207 result = MATCHconst;
3208 return;
3209 }
3210
3211 // type vs expressions
3212 if (at->ty == Tnone)
3213 {
3214 TypeDeduced *xt = (TypeDeduced *)at;
3215 result = xt->matchAll(tt);
3216 if (result > MATCHnomatch)
3217 {
3218 (*dedtypes)[i] = tt;
3219 if (result > MATCHconst)
3220 result = MATCHconst; // limit level for inout matches
3221 delete xt;
3222 }
3223 return;
3224 }
3225
3226 // type vs type
3227 if (tt->equals(at))
3228 {
3229 (*dedtypes)[i] = tt; // Prefer current type match
3230 goto Lconst;
3231 }
3232 if (tt->implicitConvTo(at->constOf()))
3233 {
3234 (*dedtypes)[i] = at->constOf()->mutableOf();
3235 *wm |= MODconst;
3236 goto Lconst;
3237 }
3238 if (at->implicitConvTo(tt->constOf()))
3239 {
3240 (*dedtypes)[i] = tt->constOf()->mutableOf();
3241 *wm |= MODconst;
3242 goto Lconst;
3243 }
3244 goto Lnomatch;
3245 }
3246 else if (MATCH m = deduceTypeHelper(t, &tt, tparam))
3247 {
3248 // type vs (none)
3249 if (!at)
3250 {
3251 (*dedtypes)[i] = tt;
3252 result = m;
3253 return;
3254 }
3255
3256 // type vs expressions
3257 if (at->ty == Tnone)
3258 {
3259 TypeDeduced *xt = (TypeDeduced *)at;
3260 result = xt->matchAll(tt);
3261 if (result > MATCHnomatch)
3262 {
3263 (*dedtypes)[i] = tt;
3264 delete xt;
3265 }
3266 return;
3267 }
3268
3269 // type vs type
3270 if (tt->equals(at))
3271 {
3272 goto Lexact;
3273 }
3274 if (tt->ty == Tclass && at->ty == Tclass)
3275 {
3276 result = tt->implicitConvTo(at);
3277 return;
3278 }
3279 if (tt->ty == Tsarray && at->ty == Tarray &&
3280 tt->nextOf()->implicitConvTo(at->nextOf()) >= MATCHconst)
3281 {
3282 goto Lexact;
3283 }
3284 }
3285 goto Lnomatch;
3286 }
3287
3288 if (tparam->ty == Ttypeof)
3289 {
3290 /* Need a loc to go with the semantic routine.
3291 */
3292 Loc loc;
3293 if (parameters->length)
3294 {
3295 TemplateParameter *tp = (*parameters)[0];
3296 loc = tp->loc;
3297 }
3298
3299 tparam = typeSemantic(tparam, loc, sc);
3300 }
3301 if (t->ty != tparam->ty)
3302 {
3303 if (Dsymbol *sym = t->toDsymbol(sc))
3304 {
3305 if (sym->isforwardRef() && !tparam->deco)
3306 goto Lnomatch;
3307 }
3308
3309 MATCH m = t->implicitConvTo(tparam);
3310 if (m == MATCHnomatch)
3311 {
3312 if (t->ty == Tclass)
3313 {
3314 TypeClass *tc = (TypeClass *)t;
3315 if (tc->sym->aliasthis && !(tc->att & RECtracingDT))
3316 {
3317 tc->att = (AliasThisRec)(tc->att | RECtracingDT);
3318 m = deduceType(t->aliasthisOf(), sc, tparam, parameters, dedtypes, wm);
3319 tc->att = (AliasThisRec)(tc->att & ~RECtracingDT);
3320 }
3321 }
3322 else if (t->ty == Tstruct)
3323 {
3324 TypeStruct *ts = (TypeStruct *)t;
3325 if (ts->sym->aliasthis && !(ts->att & RECtracingDT))
3326 {
3327 ts->att = (AliasThisRec)(ts->att | RECtracingDT);
3328 m = deduceType(t->aliasthisOf(), sc, tparam, parameters, dedtypes, wm);
3329 ts->att = (AliasThisRec)(ts->att & ~RECtracingDT);
3330 }
3331 }
3332 }
3333 result = m;
3334 return;
3335 }
3336
3337 if (t->nextOf())
3338 {
3339 if (tparam->deco && !tparam->hasWild())
3340 {
3341 result = t->implicitConvTo(tparam);
3342 return;
3343 }
3344
3345 Type *tpn = tparam->nextOf();
3346 if (wm && t->ty == Taarray && tparam->isWild())
3347 {
3348 // Bugzilla 12403: In IFTI, stop inout matching on transitive part of AA types.
3349 tpn = tpn->substWildTo(MODmutable);
3350 }
3351
3352 result = deduceType(t->nextOf(), sc, tpn, parameters, dedtypes, wm);
3353 return;
3354 }
3355
3356 Lexact:
3357 result = MATCHexact;
3358 return;
3359
3360 Lnomatch:
3361 result = MATCHnomatch;
3362 return;
3363
3364 Lconst:
3365 result = MATCHconst;
3366 }
3367
3368 void visit(TypeVector *t)
3369 {
3370 if (tparam->ty == Tvector)
3371 {
3372 TypeVector *tp = (TypeVector *)tparam;
3373 result = deduceType(t->basetype, sc, tp->basetype, parameters, dedtypes, wm);
3374 return;
3375 }
3376 visit((Type *)t);
3377 }
3378
3379 void visit(TypeDArray *t)
3380 {
3381 visit((Type *)t);
3382 }
3383
3384 void visit(TypeSArray *t)
3385 {
3386 // Extra check that array dimensions must match
3387 if (tparam)
3388 {
3389 if (tparam->ty == Tarray)
3390 {
3391 MATCH m = deduceType(t->next, sc, tparam->nextOf(), parameters, dedtypes, wm);
3392 result = (m >= MATCHconst) ? MATCHconvert : MATCHnomatch;
3393 return;
3394 }
3395
3396 TemplateParameter *tp = NULL;
3397 Expression *edim = NULL;
3398 size_t i;
3399 if (tparam->ty == Tsarray)
3400 {
3401 TypeSArray *tsa = (TypeSArray *)tparam;
3402 if (tsa->dim->op == TOKvar &&
3403 ((VarExp *)tsa->dim)->var->storage_class & STCtemplateparameter)
3404 {
3405 Identifier *id = ((VarExp *)tsa->dim)->var->ident;
3406 i = templateIdentifierLookup(id, parameters);
3407 assert(i != IDX_NOTFOUND);
3408 tp = (*parameters)[i];
3409 }
3410 else
3411 edim = tsa->dim;
3412 }
3413 else if (tparam->ty == Taarray)
3414 {
3415 TypeAArray *taa = (TypeAArray *)tparam;
3416 i = templateParameterLookup(taa->index, parameters);
3417 if (i != IDX_NOTFOUND)
3418 tp = (*parameters)[i];
3419 else
3420 {
3421 Expression *e;
3422 Type *tx;
3423 Dsymbol *s;
3424 taa->index->resolve(Loc(), sc, &e, &tx, &s);
3425 edim = s ? getValue(s) : getValue(e);
3426 }
3427 }
3428 if ((tp && tp->matchArg(sc, t->dim, i, parameters, dedtypes, NULL)) ||
3429 (edim && edim->toInteger() == t->dim->toInteger()))
3430 {
3431 result = deduceType(t->next, sc, tparam->nextOf(), parameters, dedtypes, wm);
3432 return;
3433 }
3434 }
3435 visit((Type *)t);
3436 return;
3437
3438 result = MATCHnomatch;
3439 }
3440
3441 void visit(TypeAArray *t)
3442 {
3443 // Extra check that index type must match
3444 if (tparam && tparam->ty == Taarray)
3445 {
3446 TypeAArray *tp = (TypeAArray *)tparam;
3447 if (!deduceType(t->index, sc, tp->index, parameters, dedtypes))
3448 {
3449 result = MATCHnomatch;
3450 return;
3451 }
3452 }
3453 visit((Type *)t);
3454 }
3455
3456 void visit(TypeFunction *t)
3457 {
3458 //printf("TypeFunction::deduceType()\n");
3459 //printf("\tthis = %d, ", t->ty); t->print();
3460 //printf("\ttparam = %d, ", tparam->ty); tparam->print();
3461
3462 // Extra check that function characteristics must match
3463 if (tparam && tparam->ty == Tfunction)
3464 {
3465 TypeFunction *tp = (TypeFunction *)tparam;
3466 if (t->parameterList.varargs != tp->parameterList.varargs ||
3467 t->linkage != tp->linkage)
3468 {
3469 result = MATCHnomatch;
3470 return;
3471 }
3472
3473 size_t nfargs = t->parameterList.length();
3474 size_t nfparams = tp->parameterList.length();
3475
3476 // bug 2579 fix: Apply function parameter storage classes to parameter types
3477 for (size_t i = 0; i < nfparams; i++)
3478 {
3479 Parameter *fparam = tp->parameterList[i];
3480 fparam->type = fparam->type->addStorageClass(fparam->storageClass);
3481 fparam->storageClass &= ~(STC_TYPECTOR | STCin);
3482 }
3483 //printf("\t-> this = %d, ", t->ty); t->print();
3484 //printf("\t-> tparam = %d, ", tparam->ty); tparam->print();
3485
3486 /* See if tuple match
3487 */
3488 if (nfparams > 0 && nfargs >= nfparams - 1)
3489 {
3490 /* See if 'A' of the template parameter matches 'A'
3491 * of the type of the last function parameter.
3492 */
3493 Parameter *fparam = tp->parameterList[nfparams - 1];
3494 assert(fparam);
3495 assert(fparam->type);
3496 if (fparam->type->ty != Tident)
3497 goto L1;
3498 TypeIdentifier *tid = (TypeIdentifier *)fparam->type;
3499 if (tid->idents.length)
3500 goto L1;
3501
3502 /* Look through parameters to find tuple matching tid->ident
3503 */
3504 size_t tupi = 0;
3505 for (; 1; tupi++)
3506 {
3507 if (tupi == parameters->length)
3508 goto L1;
3509 TemplateParameter *tx = (*parameters)[tupi];
3510 TemplateTupleParameter *tup = tx->isTemplateTupleParameter();
3511 if (tup && tup->ident->equals(tid->ident))
3512 break;
3513 }
3514
3515 /* The types of the function arguments [nfparams - 1 .. nfargs]
3516 * now form the tuple argument.
3517 */
3518 size_t tuple_dim = nfargs - (nfparams - 1);
3519
3520 /* See if existing tuple, and whether it matches or not
3521 */
3522 RootObject *o = (*dedtypes)[tupi];
3523 if (o)
3524 {
3525 // Existing deduced argument must be a tuple, and must match
3526 Tuple *tup = isTuple(o);
3527 if (!tup || tup->objects.length != tuple_dim)
3528 {
3529 result = MATCHnomatch;
3530 return;
3531 }
3532 for (size_t i = 0; i < tuple_dim; i++)
3533 {
3534 Parameter *arg = t->parameterList[nfparams - 1 + i];
3535 if (!arg->type->equals(tup->objects[i]))
3536 {
3537 result = MATCHnomatch;
3538 return;
3539 }
3540 }
3541 }
3542 else
3543 {
3544 // Create new tuple
3545 Tuple *tup = new Tuple();
3546 tup->objects.setDim(tuple_dim);
3547 for (size_t i = 0; i < tuple_dim; i++)
3548 {
3549 Parameter *arg = t->parameterList[nfparams - 1 + i];
3550 tup->objects[i] = arg->type;
3551 }
3552 (*dedtypes)[tupi] = tup;
3553 }
3554 nfparams--; // don't consider the last parameter for type deduction
3555 goto L2;
3556 }
3557
3558 L1:
3559 if (nfargs != nfparams)
3560 {
3561 result = MATCHnomatch;
3562 return;
3563 }
3564 L2:
3565 for (size_t i = 0; i < nfparams; i++)
3566 {
3567 Parameter *a = t->parameterList[i];
3568 Parameter *ap = tp->parameterList[i];
3569
3570 if (!a->isCovariant(t->isref, ap) ||
3571 !deduceType(a->type, sc, ap->type, parameters, dedtypes))
3572 {
3573 result = MATCHnomatch;
3574 return;
3575 }
3576 }
3577 }
3578 visit((Type *)t);
3579 }
3580
3581 void visit(TypeIdentifier *t)
3582 {
3583 // Extra check
3584 if (tparam && tparam->ty == Tident)
3585 {
3586 TypeIdentifier *tp = (TypeIdentifier *)tparam;
3587
3588 for (size_t i = 0; i < t->idents.length; i++)
3589 {
3590 RootObject *id1 = t->idents[i];
3591 RootObject *id2 = tp->idents[i];
3592
3593 if (!id1->equals(id2))
3594 {
3595 result = MATCHnomatch;
3596 return;
3597 }
3598 }
3599 }
3600 visit((Type *)t);
3601 }
3602
3603 void visit(TypeInstance *t)
3604 {
3605 // Extra check
3606 if (tparam && tparam->ty == Tinstance && t->tempinst->tempdecl)
3607 {
3608 TemplateDeclaration *tempdecl = t->tempinst->tempdecl->isTemplateDeclaration();
3609 assert(tempdecl);
3610
3611 TypeInstance *tp = (TypeInstance *)tparam;
3612
3613 //printf("tempinst->tempdecl = %p\n", tempdecl);
3614 //printf("tp->tempinst->tempdecl = %p\n", tp->tempinst->tempdecl);
3615 if (!tp->tempinst->tempdecl)
3616 {
3617 //printf("tp->tempinst->name = '%s'\n", tp->tempinst->name->toChars());
3618
3619 /* Handle case of:
3620 * template Foo(T : sa!(T), alias sa)
3621 */
3622 size_t i = templateIdentifierLookup(tp->tempinst->name, parameters);
3623 if (i == IDX_NOTFOUND)
3624 {
3625 /* Didn't find it as a parameter identifier. Try looking
3626 * it up and seeing if is an alias. See Bugzilla 1454
3627 */
3628 TypeIdentifier *tid = new TypeIdentifier(tp->loc, tp->tempinst->name);
3629 Type *tx;
3630 Expression *e;
3631 Dsymbol *s;
3632 tid->resolve(tp->loc, sc, &e, &tx, &s);
3633 if (tx)
3634 {
3635 s = tx->toDsymbol(sc);
3636 if (TemplateInstance *ti = s ? s->parent->isTemplateInstance() : NULL)
3637 {
3638 // Bugzilla 14290: Try to match with ti->tempecl,
3639 // only when ti is an enclosing instance.
3640 Dsymbol *p = sc->parent;
3641 while (p && p != ti)
3642 p = p->parent;
3643 if (p)
3644 s = ti->tempdecl;
3645 }
3646 }
3647 if (s)
3648 {
3649 s = s->toAlias();
3650 TemplateDeclaration *td = s->isTemplateDeclaration();
3651 if (td)
3652 {
3653 if (td->overroot)
3654 td = td->overroot;
3655 for (; td; td = td->overnext)
3656 {
3657 if (td == tempdecl)
3658 goto L2;
3659 }
3660 }
3661 }
3662 goto Lnomatch;
3663 }
3664 TemplateParameter *tpx = (*parameters)[i];
3665 if (!tpx->matchArg(sc, tempdecl, i, parameters, dedtypes, NULL))
3666 goto Lnomatch;
3667 }
3668 else if (tempdecl != tp->tempinst->tempdecl)
3669 goto Lnomatch;
3670
3671 L2:
3672
3673 for (size_t i = 0; 1; i++)
3674 {
3675 //printf("\ttest: tempinst->tiargs[%d]\n", i);
3676 RootObject *o1 = NULL;
3677 if (i < t->tempinst->tiargs->length)
3678 o1 = (*t->tempinst->tiargs)[i];
3679 else if (i < t->tempinst->tdtypes.length && i < tp->tempinst->tiargs->length)
3680 {
3681 // Pick up default arg
3682 o1 = t->tempinst->tdtypes[i];
3683 }
3684 else if (i >= tp->tempinst->tiargs->length)
3685 break;
3686
3687 if (i >= tp->tempinst->tiargs->length)
3688 {
3689 size_t dim = tempdecl->parameters->length - (tempdecl->isVariadic() ? 1 : 0);
3690 while (i < dim && ((*tempdecl->parameters)[i]->dependent ||
3691 (*tempdecl->parameters)[i]->hasDefaultArg()))
3692 {
3693 i++;
3694 }
3695 if (i >= dim)
3696 break; // match if all remained parameters are dependent
3697 goto Lnomatch;
3698 }
3699
3700 RootObject *o2 = (*tp->tempinst->tiargs)[i];
3701 Type *t2 = isType(o2);
3702
3703 size_t j = (t2 && t2->ty == Tident && i == tp->tempinst->tiargs->length - 1)
3704 ? templateParameterLookup(t2, parameters) : IDX_NOTFOUND;
3705 if (j != IDX_NOTFOUND && j == parameters->length - 1 &&
3706 (*parameters)[j]->isTemplateTupleParameter())
3707 {
3708 /* Given:
3709 * struct A(B...) {}
3710 * alias A!(int, float) X;
3711 * static if (is(X Y == A!(Z), Z...)) {}
3712 * deduce that Z is a tuple(int, float)
3713 */
3714
3715 /* Create tuple from remaining args
3716 */
3717 Tuple *vt = new Tuple();
3718 size_t vtdim = (tempdecl->isVariadic()
3719 ? t->tempinst->tiargs->length : t->tempinst->tdtypes.length) - i;
3720 vt->objects.setDim(vtdim);
3721 for (size_t k = 0; k < vtdim; k++)
3722 {
3723 RootObject *o;
3724 if (k < t->tempinst->tiargs->length)
3725 o = (*t->tempinst->tiargs)[i + k];
3726 else // Pick up default arg
3727 o = t->tempinst->tdtypes[i + k];
3728 vt->objects[k] = o;
3729 }
3730
3731 Tuple *v = (Tuple *)(*dedtypes)[j];
3732 if (v)
3733 {
3734 if (!match(v, vt))
3735 goto Lnomatch;
3736 }
3737 else
3738 (*dedtypes)[j] = vt;
3739 break;
3740 }
3741 else if (!o1)
3742 break;
3743
3744 Type *t1 = isType(o1);
3745 Dsymbol *s1 = isDsymbol(o1);
3746 Dsymbol *s2 = isDsymbol(o2);
3747 Expression *e1 = s1 ? getValue(s1) : getValue(isExpression(o1));
3748 Expression *e2 = isExpression(o2);
3749
3750 if (t1 && t2)
3751 {
3752 if (!deduceType(t1, sc, t2, parameters, dedtypes))
3753 goto Lnomatch;
3754 }
3755 else if (e1 && e2)
3756 {
3757 Le:
3758 e1 = e1->ctfeInterpret();
3759
3760 /* If it is one of the template parameters for this template,
3761 * we should not attempt to interpret it. It already has a value.
3762 */
3763 if (e2->op == TOKvar &&
3764 (((VarExp *)e2)->var->storage_class & STCtemplateparameter))
3765 {
3766 /*
3767 * (T:Number!(e2), int e2)
3768 */
3769 j = templateIdentifierLookup(((VarExp *)e2)->var->ident, parameters);
3770 if (j != IDX_NOTFOUND)
3771 goto L1;
3772 // The template parameter was not from this template
3773 // (it may be from a parent template, for example)
3774 }
3775
3776 e2 = expressionSemantic(e2, sc); // Bugzilla 13417
3777 e2 = e2->ctfeInterpret();
3778
3779 //printf("e1 = %s, type = %s %d\n", e1->toChars(), e1->type->toChars(), e1->type->ty);
3780 //printf("e2 = %s, type = %s %d\n", e2->toChars(), e2->type->toChars(), e2->type->ty);
3781 if (!e1->equals(e2))
3782 {
3783 if (!e2->implicitConvTo(e1->type))
3784 goto Lnomatch;
3785
3786 e2 = e2->implicitCastTo(sc, e1->type);
3787 e2 = e2->ctfeInterpret();
3788 if (!e1->equals(e2))
3789 goto Lnomatch;
3790 }
3791 }
3792 else if (e1 && t2 && t2->ty == Tident)
3793 {
3794 j = templateParameterLookup(t2, parameters);
3795 L1:
3796 if (j == IDX_NOTFOUND)
3797 {
3798 t2->resolve(((TypeIdentifier *)t2)->loc, sc, &e2, &t2, &s2);
3799 if (e2)
3800 goto Le;
3801 goto Lnomatch;
3802 }
3803 if (!(*parameters)[j]->matchArg(sc, e1, j, parameters, dedtypes, NULL))
3804 goto Lnomatch;
3805 }
3806 else if (s1 && s2)
3807 {
3808 Ls:
3809 if (!s1->equals(s2))
3810 goto Lnomatch;
3811 }
3812 else if (s1 && t2 && t2->ty == Tident)
3813 {
3814 j = templateParameterLookup(t2, parameters);
3815 if (j == IDX_NOTFOUND)
3816 {
3817 t2->resolve(((TypeIdentifier *)t2)->loc, sc, &e2, &t2, &s2);
3818 if (s2)
3819 goto Ls;
3820 goto Lnomatch;
3821 }
3822 if (!(*parameters)[j]->matchArg(sc, s1, j, parameters, dedtypes, NULL))
3823 goto Lnomatch;
3824 }
3825 else
3826 goto Lnomatch;
3827 }
3828 }
3829 visit((Type *)t);
3830 return;
3831
3832 Lnomatch:
3833 //printf("no match\n");
3834 result = MATCHnomatch;
3835 }
3836
3837 void visit(TypeStruct *t)
3838 {
3839 /* If this struct is a template struct, and we're matching
3840 * it against a template instance, convert the struct type
3841 * to a template instance, too, and try again.
3842 */
3843 TemplateInstance *ti = t->sym->parent->isTemplateInstance();
3844
3845 if (tparam && tparam->ty == Tinstance)
3846 {
3847 if (ti && ti->toAlias() == t->sym)
3848 {
3849 TypeInstance *tx = new TypeInstance(Loc(), ti);
3850 result = deduceType(tx, sc, tparam, parameters, dedtypes, wm);
3851 return;
3852 }
3853
3854 /* Match things like:
3855 * S!(T).foo
3856 */
3857 TypeInstance *tpi = (TypeInstance *)tparam;
3858 if (tpi->idents.length)
3859 {
3860 RootObject *id = tpi->idents[tpi->idents.length - 1];
3861 if (id->dyncast() == DYNCAST_IDENTIFIER && t->sym->ident->equals((Identifier *)id))
3862 {
3863 Type *tparent = t->sym->parent->getType();
3864 if (tparent)
3865 {
3866 /* Slice off the .foo in S!(T).foo
3867 */
3868 tpi->idents.length--;
3869 result = deduceType(tparent, sc, tpi, parameters, dedtypes, wm);
3870 tpi->idents.length++;
3871 return;
3872 }
3873 }
3874 }
3875 }
3876
3877 // Extra check
3878 if (tparam && tparam->ty == Tstruct)
3879 {
3880 TypeStruct *tp = (TypeStruct *)tparam;
3881
3882 //printf("\t%d\n", (MATCH) t->implicitConvTo(tp));
3883 if (wm && t->deduceWild(tparam, false))
3884 {
3885 result = MATCHconst;
3886 return;
3887 }
3888 result = t->implicitConvTo(tp);
3889 return;
3890 }
3891 visit((Type *)t);
3892 }
3893
3894 void visit(TypeEnum *t)
3895 {
3896 // Extra check
3897 if (tparam && tparam->ty == Tenum)
3898 {
3899 TypeEnum *tp = (TypeEnum *)tparam;
3900 if (t->sym == tp->sym)
3901 visit((Type *)t);
3902 else
3903 result = MATCHnomatch;
3904 return;
3905 }
3906 Type *tb = t->toBasetype();
3907 if (tb->ty == tparam->ty ||
3908 (tb->ty == Tsarray && tparam->ty == Taarray))
3909 {
3910 result = deduceType(tb, sc, tparam, parameters, dedtypes, wm);
3911 return;
3912 }
3913 visit((Type *)t);
3914 }
3915
3916 /* Helper for TypeClass::deduceType().
3917 * Classes can match with implicit conversion to a base class or interface.
3918 * This is complicated, because there may be more than one base class which
3919 * matches. In such cases, one or more parameters remain ambiguous.
3920 * For example,
3921 *
3922 * interface I(X, Y) {}
3923 * class C : I(uint, double), I(char, double) {}
3924 * C x;
3925 * foo(T, U)( I!(T, U) x)
3926 *
3927 * deduces that U is double, but T remains ambiguous (could be char or uint).
3928 *
3929 * Given a baseclass b, and initial deduced types 'dedtypes', this function
3930 * tries to match tparam with b, and also tries all base interfaces of b.
3931 * If a match occurs, numBaseClassMatches is incremented, and the new deduced
3932 * types are ANDed with the current 'best' estimate for dedtypes.
3933 */
3934 static void deduceBaseClassParameters(BaseClass *b,
3935 Scope *sc, Type *tparam, TemplateParameters *parameters, Objects *dedtypes,
3936 Objects *best, int &numBaseClassMatches)
3937 {
3938 TemplateInstance *parti = b->sym ? b->sym->parent->isTemplateInstance() : NULL;
3939 if (parti)
3940 {
3941 // Make a temporary copy of dedtypes so we don't destroy it
3942 Objects *tmpdedtypes = new Objects();
3943 tmpdedtypes->setDim(dedtypes->length);
3944 memcpy(tmpdedtypes->tdata(), dedtypes->tdata(), dedtypes->length * sizeof(void *));
3945
3946 TypeInstance *t = new TypeInstance(Loc(), parti);
3947 MATCH m = deduceType(t, sc, tparam, parameters, tmpdedtypes);
3948 if (m > MATCHnomatch)
3949 {
3950 // If this is the first ever match, it becomes our best estimate
3951 if (numBaseClassMatches==0)
3952 memcpy(best->tdata(), tmpdedtypes->tdata(), tmpdedtypes->length * sizeof(void *));
3953 else for (size_t k = 0; k < tmpdedtypes->length; ++k)
3954 {
3955 // If we've found more than one possible type for a parameter,
3956 // mark it as unknown.
3957 if ((*tmpdedtypes)[k] != (*best)[k])
3958 (*best)[k] = (*dedtypes)[k];
3959 }
3960 ++numBaseClassMatches;
3961 }
3962 }
3963 // Now recursively test the inherited interfaces
3964 for (size_t j = 0; j < b->baseInterfaces.length; ++j)
3965 {
3966 BaseClass *bi = &b->baseInterfaces.ptr[j];
3967 deduceBaseClassParameters(bi,
3968 sc, tparam, parameters, dedtypes,
3969 best, numBaseClassMatches);
3970 }
3971
3972 }
3973
3974 void visit(TypeClass *t)
3975 {
3976 //printf("TypeClass::deduceType(this = %s)\n", t->toChars());
3977
3978 /* If this class is a template class, and we're matching
3979 * it against a template instance, convert the class type
3980 * to a template instance, too, and try again.
3981 */
3982 TemplateInstance *ti = t->sym->parent->isTemplateInstance();
3983
3984 if (tparam && tparam->ty == Tinstance)
3985 {
3986 if (ti && ti->toAlias() == t->sym)
3987 {
3988 TypeInstance *tx = new TypeInstance(Loc(), ti);
3989 MATCH m = deduceType(tx, sc, tparam, parameters, dedtypes, wm);
3990 // Even if the match fails, there is still a chance it could match
3991 // a base class.
3992 if (m != MATCHnomatch)
3993 {
3994 result = m;
3995 return;
3996 }
3997 }
3998
3999 /* Match things like:
4000 * S!(T).foo
4001 */
4002 TypeInstance *tpi = (TypeInstance *)tparam;
4003 if (tpi->idents.length)
4004 {
4005 RootObject *id = tpi->idents[tpi->idents.length - 1];
4006 if (id->dyncast() == DYNCAST_IDENTIFIER && t->sym->ident->equals((Identifier *)id))
4007 {
4008 Type *tparent = t->sym->parent->getType();
4009 if (tparent)
4010 {
4011 /* Slice off the .foo in S!(T).foo
4012 */
4013 tpi->idents.length--;
4014 result = deduceType(tparent, sc, tpi, parameters, dedtypes, wm);
4015 tpi->idents.length++;
4016 return;
4017 }
4018 }
4019 }
4020
4021 // If it matches exactly or via implicit conversion, we're done
4022 visit((Type *)t);
4023 if (result != MATCHnomatch)
4024 return;
4025
4026 /* There is still a chance to match via implicit conversion to
4027 * a base class or interface. Because there could be more than one such
4028 * match, we need to check them all.
4029 */
4030
4031 int numBaseClassMatches = 0; // Have we found an interface match?
4032
4033 // Our best guess at dedtypes
4034 Objects *best = new Objects();
4035 best->setDim(dedtypes->length);
4036
4037 ClassDeclaration *s = t->sym;
4038 while (s && s->baseclasses->length > 0)
4039 {
4040 // Test the base class
4041 deduceBaseClassParameters((*s->baseclasses)[0],
4042 sc, tparam, parameters, dedtypes,
4043 best, numBaseClassMatches);
4044
4045 // Test the interfaces inherited by the base class
4046 for (size_t i = 0; i < s->interfaces.length; ++i)
4047 {
4048 BaseClass *b = s->interfaces.ptr[i];
4049 deduceBaseClassParameters(b, sc, tparam, parameters, dedtypes,
4050 best, numBaseClassMatches);
4051 }
4052 s = (*s->baseclasses)[0]->sym;
4053 }
4054
4055 if (numBaseClassMatches == 0)
4056 {
4057 result = MATCHnomatch;
4058 return;
4059 }
4060
4061 // If we got at least one match, copy the known types into dedtypes
4062 memcpy(dedtypes->tdata(), best->tdata(), best->length * sizeof(void *));
4063 result = MATCHconvert;
4064 return;
4065 }
4066
4067 // Extra check
4068 if (tparam && tparam->ty == Tclass)
4069 {
4070 TypeClass *tp = (TypeClass *)tparam;
4071
4072 //printf("\t%d\n", (MATCH) t->implicitConvTo(tp));
4073 if (wm && t->deduceWild(tparam, false))
4074 {
4075 result = MATCHconst;
4076 return;
4077 }
4078 result = t->implicitConvTo(tp);
4079 return;
4080 }
4081 visit((Type *)t);
4082 }
4083
4084 void visit(Expression *e)
4085 {
4086 //printf("Expression::deduceType(e = %s)\n", e->toChars());
4087 size_t i = templateParameterLookup(tparam, parameters);
4088 if (i == IDX_NOTFOUND || ((TypeIdentifier *)tparam)->idents.length > 0)
4089 {
4090 if (e == emptyArrayElement && tparam->ty == Tarray)
4091 {
4092 Type *tn = ((TypeNext *)tparam)->next;
4093 result = deduceType(emptyArrayElement, sc, tn, parameters, dedtypes, wm);
4094 return;
4095 }
4096 e->type->accept(this);
4097 return;
4098 }
4099
4100 TemplateTypeParameter *tp = (*parameters)[i]->isTemplateTypeParameter();
4101 if (!tp)
4102 return; // nomatch
4103
4104 if (e == emptyArrayElement)
4105 {
4106 if ((*dedtypes)[i])
4107 {
4108 result = MATCHexact;
4109 return;
4110 }
4111 if (tp->defaultType)
4112 {
4113 tp->defaultType->accept(this);
4114 return;
4115 }
4116 }
4117
4118 Type *at = (Type *)(*dedtypes)[i];
4119 Type *tt;
4120 if (unsigned char wx = deduceWildHelper(e->type, &tt, tparam))
4121 {
4122 *wm |= wx;
4123 result = MATCHconst;
4124 }
4125 else if (MATCH m = deduceTypeHelper(e->type, &tt, tparam))
4126 {
4127 result = m;
4128 }
4129 else
4130 return; // nomatch
4131
4132 // expression vs (none)
4133 if (!at)
4134 {
4135 (*dedtypes)[i] = new TypeDeduced(tt, e, tparam);
4136 return;
4137 }
4138
4139 TypeDeduced *xt = NULL;
4140 if (at->ty == Tnone)
4141 {
4142 xt = (TypeDeduced *)at;
4143 at = xt->tded;
4144 }
4145
4146 // From previous matched expressions to current deduced type
4147 MATCH match1 = xt ? xt->matchAll(tt) : MATCHnomatch;
4148
4149 // From current expresssion to previous deduced type
4150 Type *pt = at->addMod(tparam->mod);
4151 if (*wm)
4152 pt = pt->substWildTo(*wm);
4153 MATCH match2 = e->implicitConvTo(pt);
4154
4155 if (match1 > MATCHnomatch && match2 > MATCHnomatch)
4156 {
4157 if (at->implicitConvTo(tt) <= MATCHnomatch)
4158 match1 = MATCHnomatch; // Prefer at
4159 else if (tt->implicitConvTo(at) <= MATCHnomatch)
4160 match2 = MATCHnomatch; // Prefer tt
4161 else if (tt->isTypeBasic() && tt->ty == at->ty && tt->mod != at->mod)
4162 {
4163 if (!tt->isMutable() && !at->isMutable())
4164 tt = tt->mutableOf()->addMod(MODmerge(tt->mod, at->mod));
4165 else if (tt->isMutable())
4166 {
4167 if (at->mod == 0) // Prefer unshared
4168 match1 = MATCHnomatch;
4169 else
4170 match2 = MATCHnomatch;
4171 }
4172 else if (at->isMutable())
4173 {
4174 if (tt->mod == 0) // Prefer unshared
4175 match2 = MATCHnomatch;
4176 else
4177 match1 = MATCHnomatch;
4178 }
4179 //printf("tt = %s, at = %s\n", tt->toChars(), at->toChars());
4180 }
4181 else
4182 {
4183 match1 = MATCHnomatch;
4184 match2 = MATCHnomatch;
4185 }
4186 }
4187 if (match1 > MATCHnomatch)
4188 {
4189 // Prefer current match: tt
4190 if (xt)
4191 xt->update(tt, e, tparam);
4192 else
4193 (*dedtypes)[i] = tt;
4194 result = match1;
4195 return;
4196 }
4197 if (match2 > MATCHnomatch)
4198 {
4199 // Prefer previous match: (*dedtypes)[i]
4200 if (xt)
4201 xt->update(e, tparam);
4202 result = match2;
4203 return;
4204 }
4205
4206 /* Deduce common type
4207 */
4208 if (Type *t = rawTypeMerge(at, tt))
4209 {
4210 if (xt)
4211 xt->update(t, e, tparam);
4212 else
4213 (*dedtypes)[i] = t;
4214
4215 pt = tt->addMod(tparam->mod);
4216 if (*wm)
4217 pt = pt->substWildTo(*wm);
4218 result = e->implicitConvTo(pt);
4219 return;
4220 }
4221
4222 result = MATCHnomatch;
4223 }
4224
4225 MATCH deduceEmptyArrayElement()
4226 {
4227 if (!emptyArrayElement)
4228 {
4229 emptyArrayElement = new IdentifierExp(Loc(), Id::p); // dummy
4230 emptyArrayElement->type = Type::tvoid;
4231 }
4232 assert(tparam->ty == Tarray);
4233
4234 Type *tn = ((TypeNext *)tparam)->next;
4235 return deduceType(emptyArrayElement, sc, tn, parameters, dedtypes, wm);
4236 }
4237
4238 void visit(NullExp *e)
4239 {
4240 if (tparam->ty == Tarray && e->type->ty == Tnull)
4241 {
4242 // tparam:T[] <- e:null (void[])
4243 result = deduceEmptyArrayElement();
4244 return;
4245 }
4246 visit((Expression *)e);
4247 }
4248
4249 void visit(StringExp *e)
4250 {
4251 Type *taai;
4252 if (e->type->ty == Tarray &&
4253 (tparam->ty == Tsarray ||
4254 (tparam->ty == Taarray && (taai = ((TypeAArray *)tparam)->index)->ty == Tident &&
4255 ((TypeIdentifier *)taai)->idents.length == 0)))
4256 {
4257 // Consider compile-time known boundaries
4258 e->type->nextOf()->sarrayOf(e->len)->accept(this);
4259 return;
4260 }
4261 visit((Expression *)e);
4262 }
4263
4264 void visit(ArrayLiteralExp *e)
4265 {
4266 // https://issues.dlang.org/show_bug.cgi?id=20092
4267 if (e->elements && e->elements->length &&
4268 e->type->toBasetype()->nextOf()->ty == Tvoid)
4269 {
4270 result = deduceEmptyArrayElement();
4271 return;
4272 }
4273 if ((!e->elements || !e->elements->length) &&
4274 e->type->toBasetype()->nextOf()->ty == Tvoid &&
4275 tparam->ty == Tarray)
4276 {
4277 // tparam:T[] <- e:[] (void[])
4278 result = deduceEmptyArrayElement();
4279 return;
4280 }
4281
4282 if (tparam->ty == Tarray && e->elements && e->elements->length)
4283 {
4284 Type *tn = ((TypeDArray *)tparam)->next;
4285 result = MATCHexact;
4286 if (e->basis)
4287 {
4288 MATCH m = deduceType(e->basis, sc, tn, parameters, dedtypes, wm);
4289 if (m < result)
4290 result = m;
4291 }
4292 for (size_t i = 0; i < e->elements->length; i++)
4293 {
4294 if (result <= MATCHnomatch)
4295 break;
4296 Expression *el = (*e->elements)[i];
4297 if (!el)
4298 continue;
4299 MATCH m = deduceType(el, sc, tn, parameters, dedtypes, wm);
4300 if (m < result)
4301 result = m;
4302 }
4303 return;
4304 }
4305
4306 Type *taai;
4307 if (e->type->ty == Tarray &&
4308 (tparam->ty == Tsarray ||
4309 (tparam->ty == Taarray && (taai = ((TypeAArray *)tparam)->index)->ty == Tident &&
4310 ((TypeIdentifier *)taai)->idents.length == 0)))
4311 {
4312 // Consider compile-time known boundaries
4313 e->type->nextOf()->sarrayOf(e->elements->length)->accept(this);
4314 return;
4315 }
4316 visit((Expression *)e);
4317 }
4318
4319 void visit(AssocArrayLiteralExp *e)
4320 {
4321 if (tparam->ty == Taarray && e->keys && e->keys->length)
4322 {
4323 TypeAArray *taa = (TypeAArray *)tparam;
4324 result = MATCHexact;
4325 for (size_t i = 0; i < e->keys->length; i++)
4326 {
4327 MATCH m1 = deduceType((*e->keys)[i], sc, taa->index, parameters, dedtypes, wm);
4328 if (m1 < result)
4329 result = m1;
4330 if (result <= MATCHnomatch)
4331 break;
4332 MATCH m2 = deduceType((*e->values)[i], sc, taa->next, parameters, dedtypes, wm);
4333 if (m2 < result)
4334 result = m2;
4335 if (result <= MATCHnomatch)
4336 break;
4337 }
4338 return;
4339 }
4340 visit((Expression *)e);
4341 }
4342
4343 void visit(FuncExp *e)
4344 {
4345 //printf("e->type = %s, tparam = %s\n", e->type->toChars(), tparam->toChars());
4346 if (e->td)
4347 {
4348 Type *to = tparam;
4349 if (!to->nextOf() || to->nextOf()->ty != Tfunction)
4350 return;
4351 TypeFunction *tof = (TypeFunction *)to->nextOf();
4352
4353 // Parameter types inference from 'tof'
4354 assert(e->td->_scope);
4355 TypeFunction *tf = (TypeFunction *)e->fd->type;
4356 //printf("\ttof = %s\n", tof->toChars());
4357 //printf("\ttf = %s\n", tf->toChars());
4358 size_t dim = tf->parameterList.length();
4359
4360 if (tof->parameterList.length() != dim ||
4361 tof->parameterList.varargs != tf->parameterList.varargs)
4362 return;
4363
4364 Objects *tiargs = new Objects();
4365 tiargs->reserve(e->td->parameters->length);
4366
4367 for (size_t i = 0; i < e->td->parameters->length; i++)
4368 {
4369 TemplateParameter *tp = (*e->td->parameters)[i];
4370 size_t u = 0;
4371 for (; u < dim; u++)
4372 {
4373 Parameter *p = tf->parameterList[u];
4374 if (p->type->ty == Tident &&
4375 ((TypeIdentifier *)p->type)->ident == tp->ident)
4376 {
4377 break;
4378 }
4379 }
4380 assert(u < dim);
4381 Parameter *pto = tof->parameterList[u];
4382 if (!pto)
4383 break;
4384 Type *t = pto->type->syntaxCopy(); // Bugzilla 11774
4385 if (reliesOnTident(t, parameters, inferStart))
4386 return;
4387 t = typeSemantic(t, e->loc, sc);
4388 if (t->ty == Terror)
4389 return;
4390 tiargs->push(t);
4391 }
4392
4393 // Set target of return type inference
4394 if (!tf->next && tof->next)
4395 e->fd->treq = tparam;
4396
4397 TemplateInstance *ti = new TemplateInstance(e->loc, e->td, tiargs);
4398 Expression *ex = new ScopeExp(e->loc, ti);
4399 ex = expressionSemantic(ex, e->td->_scope);
4400
4401 // Reset inference target for the later re-semantic
4402 e->fd->treq = NULL;
4403
4404 if (ex->op == TOKerror)
4405 return;
4406 if (ex->op != TOKfunction)
4407 return;
4408 visit(ex->type);
4409 return;
4410 }
4411
4412 Type *t = e->type;
4413
4414 if (t->ty == Tdelegate && tparam->ty == Tpointer)
4415 return;
4416
4417 // Allow conversion from implicit function pointer to delegate
4418 if (e->tok == TOKreserved &&
4419 t->ty == Tpointer && tparam->ty == Tdelegate)
4420 {
4421 TypeFunction *tf = (TypeFunction *)t->nextOf();
4422 t = (new TypeDelegate(tf))->merge();
4423 }
4424 //printf("tparam = %s <= e->type = %s, t = %s\n", tparam->toChars(), e->type->toChars(), t->toChars());
4425 visit(t);
4426 }
4427
4428 void visit(SliceExp *e)
4429 {
4430 Type *taai;
4431 if (e->type->ty == Tarray &&
4432 (tparam->ty == Tsarray ||
4433 (tparam->ty == Taarray && (taai = ((TypeAArray *)tparam)->index)->ty == Tident &&
4434 ((TypeIdentifier *)taai)->idents.length == 0)))
4435 {
4436 // Consider compile-time known boundaries
4437 if (Type *tsa = toStaticArrayType(e))
4438 {
4439 tsa->accept(this);
4440 return;
4441 }
4442 }
4443 visit((Expression *)e);
4444 }
4445
4446 void visit(CommaExp *e)
4447 {
4448 ((CommaExp *)e)->e2->accept(this);
4449 }
4450 };
4451
4452 DeduceType v(sc, tparam, parameters, dedtypes, wm, inferStart);
4453 if (Type *t = isType(o))
4454 t->accept(&v);
4455 else
4456 {
4457 assert(isExpression(o) && wm);
4458 ((Expression *)o)->accept(&v);
4459 }
4460 return v.result;
4461 }
4462
4463 /*******************************
4464 * Input:
4465 * t Tested type, if NULL, returns NULL.
4466 * tparams Optional template parameters.
4467 * == NULL:
4468 * If one of the subtypes of this type is a TypeIdentifier,
4469 * i.e. it's an unresolved type, return that type.
4470 * != NULL:
4471 * Only when the TypeIdentifier is one of template parameters,
4472 * return that type.
4473 */
4474
reliesOnTident(Type * t,TemplateParameters * tparams,size_t iStart)4475 bool reliesOnTident(Type *t, TemplateParameters *tparams, size_t iStart)
4476 {
4477 class ReliesOnTident : public Visitor
4478 {
4479 public:
4480 TemplateParameters *tparams;
4481 size_t iStart;
4482 bool result;
4483
4484 ReliesOnTident(TemplateParameters *tparams, size_t iStart)
4485 : tparams(tparams), iStart(iStart)
4486 {
4487 result = false;
4488 }
4489
4490 void visit(Type *)
4491 {
4492 }
4493
4494 void visit(TypeNext *t)
4495 {
4496 t->next->accept(this);
4497 }
4498
4499 void visit(TypeVector *t)
4500 {
4501 t->basetype->accept(this);
4502 }
4503
4504 void visit(TypeAArray *t)
4505 {
4506 visit((TypeNext *)t);
4507 if (!result)
4508 t->index->accept(this);
4509 }
4510
4511 void visit(TypeFunction *t)
4512 {
4513 size_t dim = t->parameterList.length();
4514 for (size_t i = 0; i < dim; i++)
4515 {
4516 Parameter *fparam = t->parameterList[i];
4517 fparam->type->accept(this);
4518 if (result)
4519 return;
4520 }
4521 if (t->next)
4522 t->next->accept(this);
4523 }
4524
4525 void visit(TypeIdentifier *t)
4526 {
4527 if (!tparams)
4528 {
4529 result = true;
4530 return;
4531 }
4532
4533 for (size_t i = iStart; i < tparams->length; i++)
4534 {
4535 TemplateParameter *tp = (*tparams)[i];
4536 if (tp->ident->equals(t->ident))
4537 {
4538 result = true;
4539 return;
4540 }
4541 }
4542 }
4543
4544 void visit(TypeInstance *t)
4545 {
4546 if (!tparams)
4547 return;
4548
4549 for (size_t i = iStart; i < tparams->length; i++)
4550 {
4551 TemplateParameter *tp = (*tparams)[i];
4552 if (t->tempinst->name == tp->ident)
4553 {
4554 result = true;
4555 return;
4556 }
4557 }
4558 if (!t->tempinst->tiargs)
4559 return;
4560 for (size_t i = 0; i < t->tempinst->tiargs->length; i++)
4561 {
4562 Type *ta = isType((*t->tempinst->tiargs)[i]);
4563 if (ta)
4564 {
4565 ta->accept(this);
4566 if (result)
4567 return;
4568 }
4569 }
4570 }
4571
4572 void visit(TypeTypeof *t)
4573 {
4574 //printf("TypeTypeof::reliesOnTident('%s')\n", t->toChars());
4575 t->exp->accept(this);
4576 }
4577
4578 void visit(TypeTuple *t)
4579 {
4580 if (t->arguments)
4581 {
4582 for (size_t i = 0; i < t->arguments->length; i++)
4583 {
4584 Parameter *arg = (*t->arguments)[i];
4585 arg->type->accept(this);
4586 if (result)
4587 return;
4588 }
4589 }
4590 }
4591
4592 void visit(Expression *)
4593 {
4594 //printf("Expression::reliesOnTident('%s')\n", e->toChars());
4595 }
4596
4597 void visit(IdentifierExp *e)
4598 {
4599 //printf("IdentifierExp::reliesOnTident('%s')\n", e->toChars());
4600 for (size_t i = iStart; i < tparams->length; i++)
4601 {
4602 TemplateParameter *tp = (*tparams)[i];
4603 if (e->ident == tp->ident)
4604 {
4605 result = true;
4606 return;
4607 }
4608 }
4609 }
4610
4611 void visit(TupleExp *e)
4612 {
4613 //printf("TupleExp::reliesOnTident('%s')\n", e->toChars());
4614 if (e->exps)
4615 {
4616 for (size_t i = 0; i < e->exps->length; i++)
4617 {
4618 Expression *ea = (*e->exps)[i];
4619 ea->accept(this);
4620 if (result)
4621 return;
4622 }
4623 }
4624 }
4625
4626 void visit(ArrayLiteralExp *e)
4627 {
4628 //printf("ArrayLiteralExp::reliesOnTident('%s')\n", e->toChars());
4629 if (e->elements)
4630 {
4631 for (size_t i = 0; i < e->elements->length; i++)
4632 {
4633 Expression *el = (*e->elements)[i];
4634 el->accept(this);
4635 if (result)
4636 return;
4637 }
4638 }
4639 }
4640
4641 void visit(AssocArrayLiteralExp *e)
4642 {
4643 //printf("AssocArrayLiteralExp::reliesOnTident('%s')\n", e->toChars());
4644 for (size_t i = 0; i < e->keys->length; i++)
4645 {
4646 Expression *ek = (*e->keys)[i];
4647 ek->accept(this);
4648 if (result)
4649 return;
4650 }
4651 for (size_t i = 0; i < e->values->length; i++)
4652 {
4653 Expression *ev = (*e->values)[i];
4654 ev->accept(this);
4655 if (result)
4656 return;
4657 }
4658 }
4659
4660 void visit(StructLiteralExp *e)
4661 {
4662 //printf("StructLiteralExp::reliesOnTident('%s')\n", e->toChars());
4663 if (e->elements)
4664 {
4665 for (size_t i = 0; i < e->elements->length; i++)
4666 {
4667 Expression *ea = (*e->elements)[i];
4668 ea->accept(this);
4669 if (result)
4670 return;
4671 }
4672 }
4673 }
4674
4675 void visit(TypeExp *e)
4676 {
4677 //printf("TypeExp::reliesOnTident('%s')\n", e->toChars());
4678 e->type->accept(this);
4679 }
4680
4681 void visit(NewExp *e)
4682 {
4683 //printf("NewExp::reliesOnTident('%s')\n", e->toChars());
4684 if (e->thisexp)
4685 e->thisexp->accept(this);
4686 if (!result && e->newargs)
4687 {
4688 for (size_t i = 0; i < e->newargs->length; i++)
4689 {
4690 Expression *ea = (*e->newargs)[i];
4691 ea->accept(this);
4692 if (result)
4693 return;
4694 }
4695 }
4696 e->newtype->accept(this);
4697 if (!result && e->arguments)
4698 {
4699 for (size_t i = 0; i < e->arguments->length; i++)
4700 {
4701 Expression *ea = (*e->arguments)[i];
4702 ea->accept(this);
4703 if (result)
4704 return;
4705 }
4706 }
4707 }
4708
4709 void visit(NewAnonClassExp *)
4710 {
4711 //printf("NewAnonClassExp::reliesOnTident('%s')\n", e->toChars());
4712 result = true;
4713 }
4714
4715 void visit(FuncExp *)
4716 {
4717 //printf("FuncExp::reliesOnTident('%s')\n", e->toChars());
4718 result = true;
4719 }
4720
4721 void visit(TypeidExp *e)
4722 {
4723 //printf("TypeidExp::reliesOnTident('%s')\n", e->toChars());
4724 if (Expression *ea = isExpression(e->obj))
4725 ea->accept(this);
4726 else if (Type *ta = isType(e->obj))
4727 ta->accept(this);
4728 }
4729
4730 void visit(TraitsExp *e)
4731 {
4732 //printf("TraitsExp::reliesOnTident('%s')\n", e->toChars());
4733 if (e->args)
4734 {
4735 for (size_t i = 0; i < e->args->length; i++)
4736 {
4737 RootObject *oa = (*e->args)[i];
4738 if (Expression *ea = isExpression(oa))
4739 ea->accept(this);
4740 else if (Type *ta = isType(oa))
4741 ta->accept(this);
4742 if (result)
4743 return;
4744 }
4745 }
4746 }
4747
4748 void visit(IsExp *e)
4749 {
4750 //printf("IsExp::reliesOnTident('%s')\n", e->toChars());
4751 e->targ->accept(this);
4752 }
4753
4754 void visit(UnaExp *e)
4755 {
4756 //printf("UnaExp::reliesOnTident('%s')\n", e->toChars());
4757 e->e1->accept(this);
4758 }
4759
4760 void visit(DotTemplateInstanceExp *e)
4761 {
4762 //printf("DotTemplateInstanceExp::reliesOnTident('%s')\n", e->toChars());
4763 visit((UnaExp *)e);
4764 if (!result && e->ti->tiargs)
4765 {
4766 for (size_t i = 0; i < e->ti->tiargs->length; i++)
4767 {
4768 RootObject *oa = (*e->ti->tiargs)[i];
4769 if (Expression *ea = isExpression(oa))
4770 ea->accept(this);
4771 else if (Type *ta = isType(oa))
4772 ta->accept(this);
4773 if (result)
4774 return;
4775 }
4776 }
4777 }
4778
4779 void visit(CallExp *e)
4780 {
4781 //printf("CallExp::reliesOnTident('%s')\n", e->toChars());
4782 visit((UnaExp *)e);
4783 if (!result && e->arguments)
4784 {
4785 for (size_t i = 0; i < e->arguments->length; i++)
4786 {
4787 Expression *ea = (*e->arguments)[i];
4788 ea->accept(this);
4789 if (result)
4790 return;
4791 }
4792 }
4793 }
4794
4795 void visit(CastExp *e)
4796 {
4797 //printf("CastExp::reliesOnTident('%s')\n", e->toChars());
4798 visit((UnaExp *)e);
4799 // e.to can be null for cast() with no type
4800 if (!result && e->to)
4801 e->to->accept(this);
4802 }
4803
4804 void visit(SliceExp *e)
4805 {
4806 //printf("SliceExp::reliesOnTident('%s')\n", e->toChars());
4807 visit((UnaExp *)e);
4808 if (!result && e->lwr)
4809 e->lwr->accept(this);
4810 if (!result && e->upr)
4811 e->upr->accept(this);
4812 }
4813
4814 void visit(IntervalExp *e)
4815 {
4816 //printf("IntervalExp::reliesOnTident('%s')\n", e->toChars());
4817 e->lwr->accept(this);
4818 if (!result)
4819 e->upr->accept(this);
4820 }
4821
4822 void visit(ArrayExp *e)
4823 {
4824 //printf("ArrayExp::reliesOnTident('%s')\n", e->toChars());
4825 visit((UnaExp *)e);
4826 if (!result && e->arguments)
4827 {
4828 for (size_t i = 0; i < e->arguments->length; i++)
4829 {
4830 Expression *ea = (*e->arguments)[i];
4831 ea->accept(this);
4832 }
4833 }
4834 }
4835
4836 void visit(BinExp *e)
4837 {
4838 //printf("BinExp::reliesOnTident('%s')\n", e->toChars());
4839 e->e1->accept(this);
4840 if (!result)
4841 e->e2->accept(this);
4842 }
4843
4844 void visit(CondExp *e)
4845 {
4846 //printf("BinExp::reliesOnTident('%s')\n", e->toChars());
4847 e->econd->accept(this);
4848 if (!result)
4849 visit((BinExp *)e);
4850 }
4851 };
4852
4853 if (!t)
4854 return false;
4855
4856 ReliesOnTident v(tparams, iStart);
4857 t->accept(&v);
4858 return v.result;
4859 }
4860
4861 /* ======================== TemplateParameter =============================== */
4862
TemplateParameter(Loc loc,Identifier * ident)4863 TemplateParameter::TemplateParameter(Loc loc, Identifier *ident)
4864 {
4865 this->loc = loc;
4866 this->ident = ident;
4867 this->dependent = false;
4868 }
4869
isTemplateTypeParameter()4870 TemplateTypeParameter *TemplateParameter::isTemplateTypeParameter()
4871 {
4872 return NULL;
4873 }
4874
isTemplateValueParameter()4875 TemplateValueParameter *TemplateParameter::isTemplateValueParameter()
4876 {
4877 return NULL;
4878 }
4879
isTemplateAliasParameter()4880 TemplateAliasParameter *TemplateParameter::isTemplateAliasParameter()
4881 {
4882 return NULL;
4883 }
4884
isTemplateTupleParameter()4885 TemplateTupleParameter *TemplateParameter::isTemplateTupleParameter()
4886 {
4887 return NULL;
4888 }
4889
isTemplateThisParameter()4890 TemplateThisParameter *TemplateParameter::isTemplateThisParameter()
4891 {
4892 return NULL;
4893 }
4894
4895 /*******************************************
4896 * Match to a particular TemplateParameter.
4897 * Input:
4898 * instLoc location that the template is instantiated.
4899 * tiargs[] actual arguments to template instance
4900 * i i'th argument
4901 * parameters[] template parameters
4902 * dedtypes[] deduced arguments to template instance
4903 * *psparam set to symbol declared and initialized to dedtypes[i]
4904 */
matchArg(Loc instLoc,Scope * sc,Objects * tiargs,size_t i,TemplateParameters * parameters,Objects * dedtypes,Declaration ** psparam)4905 MATCH TemplateParameter::matchArg(Loc instLoc, Scope *sc, Objects *tiargs,
4906 size_t i, TemplateParameters *parameters, Objects *dedtypes,
4907 Declaration **psparam)
4908 {
4909 RootObject *oarg;
4910
4911 if (i < tiargs->length)
4912 oarg = (*tiargs)[i];
4913 else
4914 {
4915 // Get default argument instead
4916 oarg = defaultArg(instLoc, sc);
4917 if (!oarg)
4918 {
4919 assert(i < dedtypes->length);
4920 // It might have already been deduced
4921 oarg = (*dedtypes)[i];
4922 if (!oarg)
4923 goto Lnomatch;
4924 }
4925 }
4926 return matchArg(sc, oarg, i, parameters, dedtypes, psparam);
4927
4928 Lnomatch:
4929 if (psparam)
4930 *psparam = NULL;
4931 return MATCHnomatch;
4932 }
4933
4934 /* ======================== TemplateTypeParameter =========================== */
4935
4936 // type-parameter
4937
4938 Type *TemplateTypeParameter::tdummy = NULL;
4939
TemplateTypeParameter(Loc loc,Identifier * ident,Type * specType,Type * defaultType)4940 TemplateTypeParameter::TemplateTypeParameter(Loc loc, Identifier *ident, Type *specType,
4941 Type *defaultType)
4942 : TemplateParameter(loc, ident)
4943 {
4944 this->ident = ident;
4945 this->specType = specType;
4946 this->defaultType = defaultType;
4947 }
4948
isTemplateTypeParameter()4949 TemplateTypeParameter *TemplateTypeParameter::isTemplateTypeParameter()
4950 {
4951 return this;
4952 }
4953
syntaxCopy()4954 TemplateParameter *TemplateTypeParameter::syntaxCopy()
4955 {
4956 return new TemplateTypeParameter(loc, ident,
4957 specType ? specType->syntaxCopy() : NULL,
4958 defaultType ? defaultType->syntaxCopy() : NULL);
4959 }
4960
declareParameter(Scope * sc)4961 bool TemplateTypeParameter::declareParameter(Scope *sc)
4962 {
4963 //printf("TemplateTypeParameter::declareParameter('%s')\n", ident->toChars());
4964 TypeIdentifier *ti = new TypeIdentifier(loc, ident);
4965 Declaration *ad = new AliasDeclaration(loc, ident, ti);
4966 return sc->insert(ad) != NULL;
4967 }
4968
matchArg(Scope * sc,RootObject * oarg,size_t i,TemplateParameters * parameters,Objects * dedtypes,Declaration ** psparam)4969 MATCH TemplateTypeParameter::matchArg(Scope *sc, RootObject *oarg,
4970 size_t i, TemplateParameters *parameters, Objects *dedtypes,
4971 Declaration **psparam)
4972 {
4973 //printf("TemplateTypeParameter::matchArg('%s')\n", ident->toChars());
4974 MATCH m = MATCHexact;
4975 Type *ta = isType(oarg);
4976 if (!ta)
4977 {
4978 //printf("%s %p %p %p\n", oarg->toChars(), isExpression(oarg), isDsymbol(oarg), isTuple(oarg));
4979 goto Lnomatch;
4980 }
4981 //printf("ta is %s\n", ta->toChars());
4982
4983 if (specType)
4984 {
4985 if (!ta || ta == tdummy)
4986 goto Lnomatch;
4987
4988 //printf("\tcalling deduceType(): ta is %s, specType is %s\n", ta->toChars(), specType->toChars());
4989 MATCH m2 = deduceType(ta, sc, specType, parameters, dedtypes);
4990 if (m2 <= MATCHnomatch)
4991 {
4992 //printf("\tfailed deduceType\n");
4993 goto Lnomatch;
4994 }
4995
4996 if (m2 < m)
4997 m = m2;
4998 if ((*dedtypes)[i])
4999 {
5000 Type *t = (Type *)(*dedtypes)[i];
5001
5002 if (dependent && !t->equals(ta)) // Bugzilla 14357
5003 goto Lnomatch;
5004
5005 /* This is a self-dependent parameter. For example:
5006 * template X(T : T*) {}
5007 * template X(T : S!T, alias S) {}
5008 */
5009 //printf("t = %s ta = %s\n", t->toChars(), ta->toChars());
5010 ta = t;
5011 }
5012 }
5013 else
5014 {
5015 if ((*dedtypes)[i])
5016 {
5017 // Must match already deduced type
5018 Type *t = (Type *)(*dedtypes)[i];
5019
5020 if (!t->equals(ta))
5021 {
5022 //printf("t = %s ta = %s\n", t->toChars(), ta->toChars());
5023 goto Lnomatch;
5024 }
5025 }
5026 else
5027 {
5028 // So that matches with specializations are better
5029 m = MATCHconvert;
5030 }
5031 }
5032 (*dedtypes)[i] = ta;
5033
5034 if (psparam)
5035 *psparam = new AliasDeclaration(loc, ident, ta);
5036 //printf("\tm = %d\n", m);
5037 return dependent ? MATCHexact : m;
5038
5039 Lnomatch:
5040 if (psparam)
5041 *psparam = NULL;
5042 //printf("\tm = %d\n", MATCHnomatch);
5043 return MATCHnomatch;
5044 }
5045
5046
print(RootObject * oarg,RootObject * oded)5047 void TemplateTypeParameter::print(RootObject *oarg, RootObject *oded)
5048 {
5049 printf(" %s\n", ident->toChars());
5050
5051 Type *t = isType(oarg);
5052 Type *ta = isType(oded);
5053
5054 assert(ta);
5055
5056 if (specType)
5057 printf("\tSpecialization: %s\n", specType->toChars());
5058 if (defaultType)
5059 printf("\tDefault: %s\n", defaultType->toChars());
5060 printf("\tParameter: %s\n", t ? t->toChars() : "NULL");
5061 printf("\tDeduced Type: %s\n", ta->toChars());
5062 }
5063
dummyArg()5064 void *TemplateTypeParameter::dummyArg()
5065 {
5066 Type *t = specType;
5067 if (!t)
5068 {
5069 // Use this for alias-parameter's too (?)
5070 if (!tdummy)
5071 tdummy = new TypeIdentifier(loc, ident);
5072 t = tdummy;
5073 }
5074 return (void *)t;
5075 }
5076
5077
specialization()5078 RootObject *TemplateTypeParameter::specialization()
5079 {
5080 return specType;
5081 }
5082
defaultArg(Loc,Scope * sc)5083 RootObject *TemplateTypeParameter::defaultArg(Loc, Scope *sc)
5084 {
5085 Type *t = defaultType;
5086 if (t)
5087 {
5088 t = t->syntaxCopy();
5089 t = typeSemantic(t, loc, sc); // use the parameter loc
5090 }
5091 return t;
5092 }
5093
hasDefaultArg()5094 bool TemplateTypeParameter::hasDefaultArg()
5095 {
5096 return defaultType != NULL;
5097 }
5098
5099 /* ======================== TemplateThisParameter =========================== */
5100
5101 // this-parameter
5102
TemplateThisParameter(Loc loc,Identifier * ident,Type * specType,Type * defaultType)5103 TemplateThisParameter::TemplateThisParameter(Loc loc, Identifier *ident,
5104 Type *specType,
5105 Type *defaultType)
5106 : TemplateTypeParameter(loc, ident, specType, defaultType)
5107 {
5108 }
5109
isTemplateThisParameter()5110 TemplateThisParameter *TemplateThisParameter::isTemplateThisParameter()
5111 {
5112 return this;
5113 }
5114
syntaxCopy()5115 TemplateParameter *TemplateThisParameter::syntaxCopy()
5116 {
5117 return new TemplateThisParameter(loc, ident,
5118 specType ? specType->syntaxCopy() : NULL,
5119 defaultType ? defaultType->syntaxCopy() : NULL);
5120 }
5121
5122 /* ======================== TemplateAliasParameter ========================== */
5123
5124 // alias-parameter
5125
5126 Dsymbol *TemplateAliasParameter::sdummy = NULL;
5127
TemplateAliasParameter(Loc loc,Identifier * ident,Type * specType,RootObject * specAlias,RootObject * defaultAlias)5128 TemplateAliasParameter::TemplateAliasParameter(Loc loc, Identifier *ident,
5129 Type *specType, RootObject *specAlias, RootObject *defaultAlias)
5130 : TemplateParameter(loc, ident)
5131 {
5132 this->ident = ident;
5133 this->specType = specType;
5134 this->specAlias = specAlias;
5135 this->defaultAlias = defaultAlias;
5136 }
5137
isTemplateAliasParameter()5138 TemplateAliasParameter *TemplateAliasParameter::isTemplateAliasParameter()
5139 {
5140 return this;
5141 }
5142
syntaxCopy()5143 TemplateParameter *TemplateAliasParameter::syntaxCopy()
5144 {
5145 return new TemplateAliasParameter(loc, ident,
5146 specType ? specType->syntaxCopy() : NULL,
5147 objectSyntaxCopy(specAlias),
5148 objectSyntaxCopy(defaultAlias));
5149 }
5150
declareParameter(Scope * sc)5151 bool TemplateAliasParameter::declareParameter(Scope *sc)
5152 {
5153 TypeIdentifier *ti = new TypeIdentifier(loc, ident);
5154 Declaration *ad = new AliasDeclaration(loc, ident, ti);
5155 return sc->insert(ad) != NULL;
5156 }
5157
matchArg(Scope * sc,RootObject * oarg,size_t i,TemplateParameters * parameters,Objects * dedtypes,Declaration ** psparam)5158 MATCH TemplateAliasParameter::matchArg(Scope *sc, RootObject *oarg,
5159 size_t i, TemplateParameters *parameters, Objects *dedtypes,
5160 Declaration **psparam)
5161 {
5162 //printf("TemplateAliasParameter::matchArg('%s')\n", ident->toChars());
5163 MATCH m = MATCHexact;
5164 Type *ta = isType(oarg);
5165 RootObject *sa = ta && !ta->deco ? NULL : getDsymbol(oarg);
5166 Expression *ea = isExpression(oarg);
5167 if (ea && (ea->op == TOKthis || ea->op == TOKsuper))
5168 sa = ((ThisExp *)ea)->var;
5169 else if (ea && ea->op == TOKscope)
5170 sa = ((ScopeExp *)ea)->sds;
5171 if (sa)
5172 {
5173 if (((Dsymbol *)sa)->isAggregateDeclaration())
5174 m = MATCHconvert;
5175
5176 /* specType means the alias must be a declaration with a type
5177 * that matches specType.
5178 */
5179 if (specType)
5180 {
5181 Declaration *d = ((Dsymbol *)sa)->isDeclaration();
5182 if (!d)
5183 goto Lnomatch;
5184 if (!d->type->equals(specType))
5185 goto Lnomatch;
5186 }
5187 }
5188 else
5189 {
5190 sa = oarg;
5191 if (ea)
5192 {
5193 if (specType)
5194 {
5195 if (!ea->type->equals(specType))
5196 goto Lnomatch;
5197 }
5198 }
5199 else if (ta && ta->ty == Tinstance && !specAlias)
5200 {
5201 /* Bugzilla xxxxx: Specialized parameter should be prefeerd
5202 * match to the template type parameter.
5203 * template X(alias a) {} // a == this
5204 * template X(alias a : B!A, alias B, A...) {} // B!A => ta
5205 */
5206 }
5207 else if (sa && sa == TemplateTypeParameter::tdummy)
5208 {
5209 /* Bugzilla 2025: Aggregate Types should preferentially
5210 * match to the template type parameter.
5211 * template X(alias a) {} // a == this
5212 * template X(T) {} // T => sa
5213 */
5214 }
5215 else if (ta && ta->ty != Tident)
5216 {
5217 /* Match any type that's not a TypeIdentifier to alias parameters,
5218 * but prefer type parameter.
5219 * template X(alias a) { } // a == ta
5220 *
5221 * TypeIdentifiers are excluded because they might be not yet resolved aliases.
5222 */
5223 m = MATCHconvert;
5224 }
5225 else
5226 goto Lnomatch;
5227 }
5228
5229 if (specAlias)
5230 {
5231 if (sa == sdummy)
5232 goto Lnomatch;
5233 Dsymbol *sx = isDsymbol(sa);
5234 if (sa != specAlias && sx)
5235 {
5236 Type *talias = isType(specAlias);
5237 if (!talias)
5238 goto Lnomatch;
5239
5240 TemplateInstance *ti = sx->isTemplateInstance();
5241 if (!ti && sx->parent)
5242 {
5243 ti = sx->parent->isTemplateInstance();
5244 if (ti && ti->name != sx->ident)
5245 goto Lnomatch;
5246 }
5247 if (!ti)
5248 goto Lnomatch;
5249
5250 Type *t = new TypeInstance(Loc(), ti);
5251 MATCH m2 = deduceType(t, sc, talias, parameters, dedtypes);
5252 if (m2 <= MATCHnomatch)
5253 goto Lnomatch;
5254 }
5255 }
5256 else if ((*dedtypes)[i])
5257 {
5258 // Must match already deduced symbol
5259 RootObject *si = (*dedtypes)[i];
5260 if (!sa || si != sa)
5261 goto Lnomatch;
5262 }
5263 (*dedtypes)[i] = sa;
5264
5265 if (psparam)
5266 {
5267 if (Dsymbol *s = isDsymbol(sa))
5268 {
5269 *psparam = new AliasDeclaration(loc, ident, s);
5270 }
5271 else if (Type *t = isType(sa))
5272 {
5273 *psparam = new AliasDeclaration(loc, ident, t);
5274 }
5275 else
5276 {
5277 assert(ea);
5278
5279 // Declare manifest constant
5280 Initializer *init = new ExpInitializer(loc, ea);
5281 VarDeclaration *v = new VarDeclaration(loc, NULL, ident, init);
5282 v->storage_class = STCmanifest;
5283 dsymbolSemantic(v, sc);
5284 *psparam = v;
5285 }
5286 }
5287 return dependent ? MATCHexact : m;
5288
5289 Lnomatch:
5290 if (psparam)
5291 *psparam = NULL;
5292 //printf("\tm = %d\n", MATCHnomatch);
5293 return MATCHnomatch;
5294 }
5295
5296
print(RootObject *,RootObject * oded)5297 void TemplateAliasParameter::print(RootObject *, RootObject *oded)
5298 {
5299 printf(" %s\n", ident->toChars());
5300
5301 Dsymbol *sa = isDsymbol(oded);
5302 assert(sa);
5303
5304 printf("\tParameter alias: %s\n", sa->toChars());
5305 }
5306
dummyArg()5307 void *TemplateAliasParameter::dummyArg()
5308 {
5309 RootObject *s = specAlias;
5310 if (!s)
5311 {
5312 if (!sdummy)
5313 sdummy = new Dsymbol();
5314 s = sdummy;
5315 }
5316 return (void*)s;
5317 }
5318
5319
specialization()5320 RootObject *TemplateAliasParameter::specialization()
5321 {
5322 return specAlias;
5323 }
5324
defaultArg(Loc,Scope * sc)5325 RootObject *TemplateAliasParameter::defaultArg(Loc, Scope *sc)
5326 {
5327 RootObject *da = defaultAlias;
5328 Type *ta = isType(defaultAlias);
5329 if (ta)
5330 {
5331 if (ta->ty == Tinstance)
5332 {
5333 // If the default arg is a template, instantiate for each type
5334 da = ta->syntaxCopy();
5335 }
5336 }
5337
5338 RootObject *o = aliasParameterSemantic(loc, sc, da, NULL); // use the parameter loc
5339 return o;
5340 }
5341
hasDefaultArg()5342 bool TemplateAliasParameter::hasDefaultArg()
5343 {
5344 return defaultAlias != NULL;
5345 }
5346
5347 /* ======================== TemplateValueParameter ========================== */
5348
5349 // value-parameter
5350
5351 AA *TemplateValueParameter::edummies = NULL;
5352
TemplateValueParameter(Loc loc,Identifier * ident,Type * valType,Expression * specValue,Expression * defaultValue)5353 TemplateValueParameter::TemplateValueParameter(Loc loc, Identifier *ident, Type *valType,
5354 Expression *specValue, Expression *defaultValue)
5355 : TemplateParameter(loc, ident)
5356 {
5357 this->ident = ident;
5358 this->valType = valType;
5359 this->specValue = specValue;
5360 this->defaultValue = defaultValue;
5361 }
5362
isTemplateValueParameter()5363 TemplateValueParameter *TemplateValueParameter::isTemplateValueParameter()
5364 {
5365 return this;
5366 }
5367
syntaxCopy()5368 TemplateParameter *TemplateValueParameter::syntaxCopy()
5369 {
5370 return new TemplateValueParameter(loc, ident,
5371 valType->syntaxCopy(),
5372 specValue ? specValue->syntaxCopy() : NULL,
5373 defaultValue ? defaultValue->syntaxCopy() : NULL);
5374 }
5375
declareParameter(Scope * sc)5376 bool TemplateValueParameter::declareParameter(Scope *sc)
5377 {
5378 VarDeclaration *v = new VarDeclaration(loc, valType, ident, NULL);
5379 v->storage_class = STCtemplateparameter;
5380 return sc->insert(v) != NULL;
5381 }
5382
matchArg(Scope * sc,RootObject * oarg,size_t i,TemplateParameters *,Objects * dedtypes,Declaration ** psparam)5383 MATCH TemplateValueParameter::matchArg(Scope *sc, RootObject *oarg,
5384 size_t i, TemplateParameters *, Objects *dedtypes, Declaration **psparam)
5385 {
5386 //printf("TemplateValueParameter::matchArg('%s')\n", ident->toChars());
5387
5388 MATCH m = MATCHexact;
5389
5390 Expression *ei = isExpression(oarg);
5391 Type *vt;
5392
5393 if (!ei && oarg)
5394 {
5395 Dsymbol *si = isDsymbol(oarg);
5396 FuncDeclaration *f = si ? si->isFuncDeclaration() : NULL;
5397 if (!f || !f->fbody || f->needThis())
5398 goto Lnomatch;
5399
5400 ei = new VarExp(loc, f);
5401 ei = expressionSemantic(ei, sc);
5402
5403 /* If a function is really property-like, and then
5404 * it's CTFEable, ei will be a literal expression.
5405 */
5406 unsigned int olderrors = global.startGagging();
5407 ei = resolveProperties(sc, ei);
5408 ei = ei->ctfeInterpret();
5409 if (global.endGagging(olderrors) || ei->op == TOKerror)
5410 goto Lnomatch;
5411
5412 /* Bugzilla 14520: A property-like function can match to both
5413 * TemplateAlias and ValueParameter. But for template overloads,
5414 * it should always prefer alias parameter to be consistent
5415 * template match result.
5416 *
5417 * template X(alias f) { enum X = 1; }
5418 * template X(int val) { enum X = 2; }
5419 * int f1() { return 0; } // CTFEable
5420 * int f2(); // body-less function is not CTFEable
5421 * enum x1 = X!f1; // should be 1
5422 * enum x2 = X!f2; // should be 1
5423 *
5424 * e.g. The x1 value must be same even if the f1 definition will be moved
5425 * into di while stripping body code.
5426 */
5427 m = MATCHconvert;
5428 }
5429
5430 if (ei && ei->op == TOKvar)
5431 {
5432 // Resolve const variables that we had skipped earlier
5433 ei = ei->ctfeInterpret();
5434 }
5435
5436 //printf("\tvalType: %s, ty = %d\n", valType->toChars(), valType->ty);
5437 vt = typeSemantic(valType, loc, sc);
5438 //printf("ei: %s, ei->type: %s\n", ei->toChars(), ei->type->toChars());
5439 //printf("vt = %s\n", vt->toChars());
5440
5441 if (ei->type)
5442 {
5443 MATCH m2 = ei->implicitConvTo(vt);
5444 //printf("m: %d\n", m);
5445 if (m2 < m)
5446 m = m2;
5447 if (m <= MATCHnomatch)
5448 goto Lnomatch;
5449 ei = ei->implicitCastTo(sc, vt);
5450 ei = ei->ctfeInterpret();
5451 }
5452
5453 if (specValue)
5454 {
5455 if (!ei || (Expression *)dmd_aaGetRvalue(edummies, (void *)ei->type) == ei)
5456 goto Lnomatch;
5457
5458 Expression *e = specValue;
5459
5460 sc = sc->startCTFE();
5461 e = expressionSemantic(e, sc);
5462 e = resolveProperties(sc, e);
5463 sc = sc->endCTFE();
5464 e = e->implicitCastTo(sc, vt);
5465 e = e->ctfeInterpret();
5466
5467 ei = ei->syntaxCopy();
5468 sc = sc->startCTFE();
5469 ei = expressionSemantic(ei, sc);
5470 sc = sc->endCTFE();
5471 ei = ei->implicitCastTo(sc, vt);
5472 ei = ei->ctfeInterpret();
5473 //printf("\tei: %s, %s\n", ei->toChars(), ei->type->toChars());
5474 //printf("\te : %s, %s\n", e->toChars(), e->type->toChars());
5475 if (!ei->equals(e))
5476 goto Lnomatch;
5477 }
5478 else
5479 {
5480 if ((*dedtypes)[i])
5481 {
5482 // Must match already deduced value
5483 Expression *e = (Expression *)(*dedtypes)[i];
5484
5485 if (!ei || !ei->equals(e))
5486 goto Lnomatch;
5487 }
5488 }
5489 (*dedtypes)[i] = ei;
5490
5491 if (psparam)
5492 {
5493 Initializer *init = new ExpInitializer(loc, ei);
5494 Declaration *sparam = new VarDeclaration(loc, vt, ident, init);
5495 sparam->storage_class = STCmanifest;
5496 *psparam = sparam;
5497 }
5498 return dependent ? MATCHexact : m;
5499
5500 Lnomatch:
5501 //printf("\tno match\n");
5502 if (psparam)
5503 *psparam = NULL;
5504 return MATCHnomatch;
5505 }
5506
5507
print(RootObject *,RootObject * oded)5508 void TemplateValueParameter::print(RootObject *, RootObject *oded)
5509 {
5510 printf(" %s\n", ident->toChars());
5511
5512 Expression *ea = isExpression(oded);
5513
5514 if (specValue)
5515 printf("\tSpecialization: %s\n", specValue->toChars());
5516 printf("\tParameter Value: %s\n", ea ? ea->toChars() : "NULL");
5517 }
5518
dummyArg()5519 void *TemplateValueParameter::dummyArg()
5520 {
5521 Expression *e = specValue;
5522 if (!e)
5523 {
5524 // Create a dummy value
5525 Expression **pe = (Expression **)dmd_aaGet(&edummies, (void *)valType);
5526 if (!*pe)
5527 *pe = valType->defaultInit();
5528 e = *pe;
5529 }
5530 return (void *)e;
5531 }
5532
5533
specialization()5534 RootObject *TemplateValueParameter::specialization()
5535 {
5536 return specValue;
5537 }
5538
defaultArg(Loc instLoc,Scope * sc)5539 RootObject *TemplateValueParameter::defaultArg(Loc instLoc, Scope *sc)
5540 {
5541 Expression *e = defaultValue;
5542 if (e)
5543 {
5544 e = e->syntaxCopy();
5545 unsigned olderrs = global.errors;
5546 if ((e = expressionSemantic(e, sc)) == NULL)
5547 return NULL;
5548 if ((e = resolveProperties(sc, e)) == NULL)
5549 return NULL;
5550 e = e->resolveLoc(instLoc, sc); // use the instantiated loc
5551 e = e->optimize(WANTvalue);
5552 if (global.errors != olderrs)
5553 e = new ErrorExp();
5554 }
5555 return e;
5556 }
5557
hasDefaultArg()5558 bool TemplateValueParameter::hasDefaultArg()
5559 {
5560 return defaultValue != NULL;
5561 }
5562
5563 /* ======================== TemplateTupleParameter ========================== */
5564
5565 // variadic-parameter
5566
TemplateTupleParameter(Loc loc,Identifier * ident)5567 TemplateTupleParameter::TemplateTupleParameter(Loc loc, Identifier *ident)
5568 : TemplateParameter(loc, ident)
5569 {
5570 this->ident = ident;
5571 }
5572
isTemplateTupleParameter()5573 TemplateTupleParameter *TemplateTupleParameter::isTemplateTupleParameter()
5574 {
5575 return this;
5576 }
5577
syntaxCopy()5578 TemplateParameter *TemplateTupleParameter::syntaxCopy()
5579 {
5580 return new TemplateTupleParameter(loc, ident);
5581 }
5582
declareParameter(Scope * sc)5583 bool TemplateTupleParameter::declareParameter(Scope *sc)
5584 {
5585 TypeIdentifier *ti = new TypeIdentifier(loc, ident);
5586 Declaration *ad = new AliasDeclaration(loc, ident, ti);
5587 return sc->insert(ad) != NULL;
5588 }
5589
matchArg(Loc,Scope * sc,Objects * tiargs,size_t i,TemplateParameters * parameters,Objects * dedtypes,Declaration ** psparam)5590 MATCH TemplateTupleParameter::matchArg(Loc, Scope *sc, Objects *tiargs,
5591 size_t i, TemplateParameters *parameters, Objects *dedtypes,
5592 Declaration **psparam)
5593 {
5594 /* The rest of the actual arguments (tiargs[]) form the match
5595 * for the variadic parameter.
5596 */
5597 assert(i + 1 == dedtypes->length); // must be the last one
5598 Tuple *ovar;
5599
5600 if (Tuple *u = isTuple((*dedtypes)[i]))
5601 {
5602 // It has already been deduced
5603 ovar = u;
5604 }
5605 else if (i + 1 == tiargs->length && isTuple((*tiargs)[i]))
5606 ovar = isTuple((*tiargs)[i]);
5607 else
5608 {
5609 ovar = new Tuple();
5610 //printf("ovar = %p\n", ovar);
5611 if (i < tiargs->length)
5612 {
5613 //printf("i = %d, tiargs->length = %d\n", i, tiargs->length);
5614 ovar->objects.setDim(tiargs->length - i);
5615 for (size_t j = 0; j < ovar->objects.length; j++)
5616 ovar->objects[j] = (*tiargs)[i + j];
5617 }
5618 }
5619 return matchArg(sc, ovar, i, parameters, dedtypes, psparam);
5620 }
5621
matchArg(Scope *,RootObject * oarg,size_t i,TemplateParameters *,Objects * dedtypes,Declaration ** psparam)5622 MATCH TemplateTupleParameter::matchArg(Scope *, RootObject *oarg,
5623 size_t i, TemplateParameters *, Objects *dedtypes, Declaration **psparam)
5624 {
5625 //printf("TemplateTupleParameter::matchArg('%s')\n", ident->toChars());
5626 Tuple *ovar = isTuple(oarg);
5627 if (!ovar)
5628 return MATCHnomatch;
5629 if ((*dedtypes)[i])
5630 {
5631 Tuple *tup = isTuple((*dedtypes)[i]);
5632 if (!tup)
5633 return MATCHnomatch;
5634 if (!match(tup, ovar))
5635 return MATCHnomatch;
5636 }
5637 (*dedtypes)[i] = ovar;
5638
5639 if (psparam)
5640 *psparam = new TupleDeclaration(loc, ident, &ovar->objects);
5641 return dependent ? MATCHexact : MATCHconvert;
5642 }
5643
5644
print(RootObject *,RootObject * oded)5645 void TemplateTupleParameter::print(RootObject *, RootObject *oded)
5646 {
5647 printf(" %s... [", ident->toChars());
5648 Tuple *v = isTuple(oded);
5649 assert(v);
5650
5651 //printf("|%d| ", v->objects.length);
5652 for (size_t i = 0; i < v->objects.length; i++)
5653 {
5654 if (i)
5655 printf(", ");
5656
5657 RootObject *o = v->objects[i];
5658
5659 Dsymbol *sa = isDsymbol(o);
5660 if (sa)
5661 printf("alias: %s", sa->toChars());
5662
5663 Type *ta = isType(o);
5664 if (ta)
5665 printf("type: %s", ta->toChars());
5666
5667 Expression *ea = isExpression(o);
5668 if (ea)
5669 printf("exp: %s", ea->toChars());
5670
5671 assert(!isTuple(o)); // no nested Tuple arguments
5672 }
5673
5674 printf("]\n");
5675 }
5676
dummyArg()5677 void *TemplateTupleParameter::dummyArg()
5678 {
5679 return NULL;
5680 }
5681
5682
specialization()5683 RootObject *TemplateTupleParameter::specialization()
5684 {
5685 return NULL;
5686 }
5687
defaultArg(Loc,Scope *)5688 RootObject *TemplateTupleParameter::defaultArg(Loc, Scope *)
5689 {
5690 return NULL;
5691 }
5692
hasDefaultArg()5693 bool TemplateTupleParameter::hasDefaultArg()
5694 {
5695 return false;
5696 }
5697
5698 /* ======================== TemplateInstance ================================ */
5699
TemplateInstance(Loc loc,Identifier * ident)5700 TemplateInstance::TemplateInstance(Loc loc, Identifier *ident)
5701 : ScopeDsymbol(NULL)
5702 {
5703 this->loc = loc;
5704 this->name = ident;
5705 this->tiargs = NULL;
5706 this->tempdecl = NULL;
5707 this->inst = NULL;
5708 this->tinst = NULL;
5709 this->tnext = NULL;
5710 this->minst = NULL;
5711 this->deferred = NULL;
5712 this->memberOf = NULL;
5713 this->argsym = NULL;
5714 this->aliasdecl = NULL;
5715 this->semantictiargsdone = false;
5716 this->inuse = 0;
5717 this->nest = 0;
5718 this->havetempdecl = false;
5719 this->enclosing = NULL;
5720 this->gagged = false;
5721 this->hash = 0;
5722 this->fargs = NULL;
5723 }
5724
5725 /*****************
5726 * This constructor is only called when we figured out which function
5727 * template to instantiate.
5728 */
5729
TemplateInstance(Loc loc,TemplateDeclaration * td,Objects * tiargs)5730 TemplateInstance::TemplateInstance(Loc loc, TemplateDeclaration *td, Objects *tiargs)
5731 : ScopeDsymbol(NULL)
5732 {
5733 this->loc = loc;
5734 this->name = td->ident;
5735 this->tiargs = tiargs;
5736 this->tempdecl = td;
5737 this->inst = NULL;
5738 this->tinst = NULL;
5739 this->tnext = NULL;
5740 this->minst = NULL;
5741 this->deferred = NULL;
5742 this->memberOf = NULL;
5743 this->argsym = NULL;
5744 this->aliasdecl = NULL;
5745 this->semantictiargsdone = true;
5746 this->inuse = 0;
5747 this->nest = 0;
5748 this->havetempdecl = true;
5749 this->enclosing = NULL;
5750 this->gagged = false;
5751 this->hash = 0;
5752 this->fargs = NULL;
5753
5754 assert(tempdecl->_scope);
5755 }
5756
5757
arraySyntaxCopy(Objects * objs)5758 Objects *TemplateInstance::arraySyntaxCopy(Objects *objs)
5759 {
5760 Objects *a = NULL;
5761 if (objs)
5762 {
5763 a = new Objects();
5764 a->setDim(objs->length);
5765 for (size_t i = 0; i < objs->length; i++)
5766 (*a)[i] = objectSyntaxCopy((*objs)[i]);
5767 }
5768 return a;
5769 }
5770
syntaxCopy(Dsymbol * s)5771 Dsymbol *TemplateInstance::syntaxCopy(Dsymbol *s)
5772 {
5773 TemplateInstance *ti =
5774 s ? (TemplateInstance *)s
5775 : new TemplateInstance(loc, name);
5776 ti->tiargs = arraySyntaxCopy(tiargs);
5777 TemplateDeclaration *td;
5778 if (inst && tempdecl && (td = tempdecl->isTemplateDeclaration()) != NULL)
5779 td->ScopeDsymbol::syntaxCopy(ti);
5780 else
5781 ScopeDsymbol::syntaxCopy(ti);
5782 return ti;
5783 }
5784
expandMembers(Scope * sc2)5785 void TemplateInstance::expandMembers(Scope *sc2)
5786 {
5787 for (size_t i = 0; i < members->length; i++)
5788 {
5789 Dsymbol *s = (*members)[i];
5790 s->setScope(sc2);
5791 }
5792
5793 for (size_t i = 0; i < members->length; i++)
5794 {
5795 Dsymbol *s = (*members)[i];
5796 s->importAll(sc2);
5797 }
5798
5799 for (size_t i = 0; i < members->length; i++)
5800 {
5801 Dsymbol *s = (*members)[i];
5802 //printf("\t[%d] semantic on '%s' %p kind %s in '%s'\n", i, s->toChars(), s, s->kind(), this->toChars());
5803 //printf("test: enclosing = %d, sc2->parent = %s\n", enclosing, sc2->parent->toChars());
5804 // if (enclosing)
5805 // s->parent = sc->parent;
5806 //printf("test3: enclosing = %d, s->parent = %s\n", enclosing, s->parent->toChars());
5807 dsymbolSemantic(s, sc2);
5808 //printf("test4: enclosing = %d, s->parent = %s\n", enclosing, s->parent->toChars());
5809 Module::runDeferredSemantic();
5810 }
5811 }
5812
tryExpandMembers(Scope * sc2)5813 void TemplateInstance::tryExpandMembers(Scope *sc2)
5814 {
5815 static int nest;
5816 // extracted to a function to allow windows SEH to work without destructors in the same function
5817 //printf("%d\n", nest);
5818 if (++nest > global.recursionLimit)
5819 {
5820 global.gag = 0; // ensure error message gets printed
5821 error("recursive expansion exceeded allowed nesting limit");
5822 fatal();
5823 }
5824
5825 expandMembers(sc2);
5826
5827 nest--;
5828 }
5829
trySemantic3(Scope * sc2)5830 void TemplateInstance::trySemantic3(Scope *sc2)
5831 {
5832 // extracted to a function to allow windows SEH to work without destructors in the same function
5833 static int nest;
5834 //printf("%d\n", nest);
5835 if (++nest > global.recursionLimit)
5836 {
5837 global.gag = 0; // ensure error message gets printed
5838 error("recursive expansion exceeded allowed nesting limit");
5839 fatal();
5840 }
5841 semantic3(this, sc2);
5842
5843 --nest;
5844 }
5845
5846 /**********************************************
5847 * Find template declaration corresponding to template instance.
5848 *
5849 * Returns:
5850 * false if finding fails.
5851 * Note:
5852 * This function is reentrant against error occurrence. If returns false,
5853 * any members of this object won't be modified, and repetition call will
5854 * reproduce same error.
5855 */
5856
findTempDecl(Scope * sc,WithScopeSymbol ** pwithsym)5857 bool TemplateInstance::findTempDecl(Scope *sc, WithScopeSymbol **pwithsym)
5858 {
5859 if (pwithsym)
5860 *pwithsym = NULL;
5861
5862 if (havetempdecl)
5863 return true;
5864
5865 //printf("TemplateInstance::findTempDecl() %s\n", toChars());
5866 if (!tempdecl)
5867 {
5868 /* Given:
5869 * foo!( ... )
5870 * figure out which TemplateDeclaration foo refers to.
5871 */
5872 Identifier *id = name;
5873 Dsymbol *scopesym;
5874 Dsymbol *s = sc->search(loc, id, &scopesym);
5875 if (!s)
5876 {
5877 s = sc->search_correct(id);
5878 if (s)
5879 error("template `%s` is not defined, did you mean %s?", id->toChars(), s->toChars());
5880 else
5881 error("template `%s` is not defined", id->toChars());
5882 return false;
5883 }
5884
5885 if (pwithsym)
5886 *pwithsym = scopesym->isWithScopeSymbol();
5887
5888 /* We might have found an alias within a template when
5889 * we really want the template.
5890 */
5891 TemplateInstance *ti;
5892 if (s->parent &&
5893 (ti = s->parent->isTemplateInstance()) != NULL)
5894 {
5895 if (ti->tempdecl && ti->tempdecl->ident == id)
5896 {
5897 /* This is so that one can refer to the enclosing
5898 * template, even if it has the same name as a member
5899 * of the template, if it has a !(arguments)
5900 */
5901 TemplateDeclaration *td = ti->tempdecl->isTemplateDeclaration();
5902 assert(td);
5903 if (td->overroot) // if not start of overloaded list of TemplateDeclaration's
5904 td = td->overroot; // then get the start
5905 s = td;
5906 }
5907 }
5908
5909 if (!updateTempDecl(sc, s))
5910 {
5911 return false;
5912 }
5913 }
5914 assert(tempdecl);
5915
5916 struct ParamFwdTi
5917 {
5918 static int fp(void *param, Dsymbol *s)
5919 {
5920 TemplateDeclaration *td = s->isTemplateDeclaration();
5921 if (!td)
5922 return 0;
5923
5924 TemplateInstance *ti = (TemplateInstance *)param;
5925 if (td->semanticRun == PASSinit)
5926 {
5927 if (td->_scope)
5928 {
5929 // Try to fix forward reference. Ungag errors while doing so.
5930 Ungag ungag = td->ungagSpeculative();
5931 dsymbolSemantic(td, td->_scope);
5932 }
5933 if (td->semanticRun == PASSinit)
5934 {
5935 ti->error("%s forward references template declaration %s", ti->toChars(), td->toChars());
5936 return 1;
5937 }
5938 }
5939 return 0;
5940 }
5941 };
5942 // Look for forward references
5943 OverloadSet *tovers = tempdecl->isOverloadSet();
5944 size_t overs_dim = tovers ? tovers->a.length : 1;
5945 for (size_t oi = 0; oi < overs_dim; oi++)
5946 {
5947 if (overloadApply(tovers ? tovers->a[oi] : tempdecl, (void *)this, &ParamFwdTi::fp))
5948 return false;
5949 }
5950 return true;
5951 }
5952
5953 /**********************************************
5954 * Confirm s is a valid template, then store it.
5955 * Input:
5956 * sc
5957 * s candidate symbol of template. It may be:
5958 * TemplateDeclaration
5959 * FuncDeclaration with findTemplateDeclRoot() != NULL
5960 * OverloadSet which contains candidates
5961 * Returns:
5962 * true if updating succeeds.
5963 */
5964
updateTempDecl(Scope * sc,Dsymbol * s)5965 bool TemplateInstance::updateTempDecl(Scope *sc, Dsymbol *s)
5966 {
5967 if (s)
5968 {
5969 Identifier *id = name;
5970 s = s->toAlias();
5971
5972 /* If an OverloadSet, look for a unique member that is a template declaration
5973 */
5974 OverloadSet *os = s->isOverloadSet();
5975 if (os)
5976 {
5977 s = NULL;
5978 for (size_t i = 0; i < os->a.length; i++)
5979 {
5980 Dsymbol *s2 = os->a[i];
5981 if (FuncDeclaration *f = s2->isFuncDeclaration())
5982 s2 = f->findTemplateDeclRoot();
5983 else
5984 s2 = s2->isTemplateDeclaration();
5985 if (s2)
5986 {
5987 if (s)
5988 {
5989 tempdecl = os;
5990 return true;
5991 }
5992 s = s2;
5993 }
5994 }
5995 if (!s)
5996 {
5997 error("template `%s` is not defined", id->toChars());
5998 return false;
5999 }
6000 }
6001
6002 OverDeclaration *od = s->isOverDeclaration();
6003 if (od)
6004 {
6005 tempdecl = od; // TODO: more strict check
6006 return true;
6007 }
6008
6009 /* It should be a TemplateDeclaration, not some other symbol
6010 */
6011 if (FuncDeclaration *f = s->isFuncDeclaration())
6012 tempdecl = f->findTemplateDeclRoot();
6013 else
6014 tempdecl = s->isTemplateDeclaration();
6015 if (!tempdecl)
6016 {
6017 if (!s->parent && global.errors)
6018 return false;
6019 if (!s->parent && s->getType())
6020 {
6021 Dsymbol *s2 = s->getType()->toDsymbol(sc);
6022 if (!s2)
6023 {
6024 error("%s is not a template declaration, it is a %s", id->toChars(), s->kind());
6025 return false;
6026 }
6027 s = s2;
6028 }
6029 //assert(s->parent);
6030 TemplateInstance *ti = s->parent ? s->parent->isTemplateInstance() : NULL;
6031 if (ti &&
6032 (ti->name == s->ident ||
6033 ti->toAlias()->ident == s->ident)
6034 &&
6035 ti->tempdecl)
6036 {
6037 /* This is so that one can refer to the enclosing
6038 * template, even if it has the same name as a member
6039 * of the template, if it has a !(arguments)
6040 */
6041 TemplateDeclaration *td = ti->tempdecl->isTemplateDeclaration();
6042 assert(td);
6043 if (td->overroot) // if not start of overloaded list of TemplateDeclaration's
6044 td = td->overroot; // then get the start
6045 tempdecl = td;
6046 }
6047 else
6048 {
6049 error("%s is not a template declaration, it is a %s", id->toChars(), s->kind());
6050 return false;
6051 }
6052 }
6053 }
6054 return (tempdecl != NULL);
6055 }
6056
6057 /**********************************
6058 * Run semantic on the elements of tiargs.
6059 * Input:
6060 * sc
6061 * Returns:
6062 * false if one or more arguments have errors.
6063 * Note:
6064 * This function is reentrant against error occurrence. If returns false,
6065 * all elements of tiargs won't be modified.
6066 */
6067
semanticTiargs(Scope * sc)6068 bool TemplateInstance::semanticTiargs(Scope *sc)
6069 {
6070 //printf("+TemplateInstance::semanticTiargs() %s\n", toChars());
6071 if (semantictiargsdone)
6072 return true;
6073 if (semanticTiargs(loc, sc, tiargs, 0))
6074 {
6075 // cache the result iff semantic analysis succeeded entirely
6076 semantictiargsdone = 1;
6077 return true;
6078 }
6079 return false;
6080 }
6081
6082 /**********************************
6083 * Run semantic of tiargs as arguments of template.
6084 * Input:
6085 * loc
6086 * sc
6087 * tiargs array of template arguments
6088 * flags 1: replace const variables with their initializers
6089 * 2: don't devolve Parameter to Type
6090 * Returns:
6091 * false if one or more arguments have errors.
6092 */
6093
semanticTiargs(Loc loc,Scope * sc,Objects * tiargs,int flags)6094 bool TemplateInstance::semanticTiargs(Loc loc, Scope *sc, Objects *tiargs, int flags)
6095 {
6096 // Run semantic on each argument, place results in tiargs[]
6097 //printf("+TemplateInstance::semanticTiargs()\n");
6098 if (!tiargs)
6099 return true;
6100 bool err = false;
6101 for (size_t j = 0; j < tiargs->length; j++)
6102 {
6103 RootObject *o = (*tiargs)[j];
6104 Type *ta = isType(o);
6105 Expression *ea = isExpression(o);
6106 Dsymbol *sa = isDsymbol(o);
6107
6108 //printf("1: (*tiargs)[%d] = %p, s=%p, v=%p, ea=%p, ta=%p\n", j, o, isDsymbol(o), isTuple(o), ea, ta);
6109 if (ta)
6110 {
6111 //printf("type %s\n", ta->toChars());
6112
6113 // It might really be an Expression or an Alias
6114 ta->resolve(loc, sc, &ea, &ta, &sa, (flags & 1) != 0);
6115 if (ea) goto Lexpr;
6116 if (sa) goto Ldsym;
6117 if (ta == NULL)
6118 {
6119 assert(global.errors);
6120 ta = Type::terror;
6121 }
6122
6123 Ltype:
6124 if (ta->ty == Ttuple)
6125 {
6126 // Expand tuple
6127 TypeTuple *tt = (TypeTuple *)ta;
6128 size_t dim = tt->arguments->length;
6129 tiargs->remove(j);
6130 if (dim)
6131 {
6132 tiargs->reserve(dim);
6133 for (size_t i = 0; i < dim; i++)
6134 {
6135 Parameter *arg = (*tt->arguments)[i];
6136 if (flags & 2 && (arg->ident || arg->userAttribDecl))
6137 tiargs->insert(j + i, arg);
6138 else
6139 tiargs->insert(j + i, arg->type);
6140 }
6141 }
6142 j--;
6143 continue;
6144 }
6145 if (ta->ty == Terror)
6146 {
6147 err = true;
6148 continue;
6149 }
6150 (*tiargs)[j] = ta->merge2();
6151 }
6152 else if (ea)
6153 {
6154 Lexpr:
6155 //printf("+[%d] ea = %s %s\n", j, Token::toChars(ea->op), ea->toChars());
6156 if (flags & 1) // only used by __traits
6157 {
6158 ea = expressionSemantic(ea, sc);
6159
6160 // must not interpret the args, excepting template parameters
6161 if (ea->op != TOKvar ||
6162 (((VarExp *)ea)->var->storage_class & STCtemplateparameter))
6163 {
6164 ea = ea->optimize(WANTvalue);
6165 }
6166 }
6167 else
6168 {
6169 sc = sc->startCTFE();
6170 ea = expressionSemantic(ea, sc);
6171 sc = sc->endCTFE();
6172
6173 if (ea->op == TOKvar)
6174 {
6175 /* This test is to skip substituting a const var with
6176 * its initializer. The problem is the initializer won't
6177 * match with an 'alias' parameter. Instead, do the
6178 * const substitution in TemplateValueParameter::matchArg().
6179 */
6180 }
6181 else if (definitelyValueParameter(ea))
6182 {
6183 if (ea->checkValue()) // check void expression
6184 ea = new ErrorExp();
6185 unsigned int olderrs = global.errors;
6186 ea = ea->ctfeInterpret();
6187 if (global.errors != olderrs)
6188 ea = new ErrorExp();
6189 }
6190 }
6191 //printf("-[%d] ea = %s %s\n", j, Token::toChars(ea->op), ea->toChars());
6192 if (ea->op == TOKtuple)
6193 {
6194 // Expand tuple
6195 TupleExp *te = (TupleExp *)ea;
6196 size_t dim = te->exps->length;
6197 tiargs->remove(j);
6198 if (dim)
6199 {
6200 tiargs->reserve(dim);
6201 for (size_t i = 0; i < dim; i++)
6202 tiargs->insert(j + i, (*te->exps)[i]);
6203 }
6204 j--;
6205 continue;
6206 }
6207 if (ea->op == TOKerror)
6208 {
6209 err = true;
6210 continue;
6211 }
6212 (*tiargs)[j] = ea;
6213
6214 if (ea->op == TOKtype)
6215 {
6216 ta = ea->type;
6217 goto Ltype;
6218 }
6219 if (ea->op == TOKscope)
6220 {
6221 sa = ((ScopeExp *)ea)->sds;
6222 goto Ldsym;
6223 }
6224 if (ea->op == TOKfunction)
6225 {
6226 FuncExp *fe = (FuncExp *)ea;
6227 /* A function literal, that is passed to template and
6228 * already semanticed as function pointer, never requires
6229 * outer frame. So convert it to global function is valid.
6230 */
6231 if (fe->fd->tok == TOKreserved && fe->type->ty == Tpointer)
6232 {
6233 // change to non-nested
6234 fe->fd->tok = TOKfunction;
6235 fe->fd->vthis = NULL;
6236 }
6237 else if (fe->td)
6238 {
6239 /* If template argument is a template lambda,
6240 * get template declaration itself. */
6241 //sa = fe->td;
6242 //goto Ldsym;
6243 }
6244 }
6245 if (ea->op == TOKdotvar && !(flags & 1))
6246 {
6247 // translate expression to dsymbol.
6248 sa = ((DotVarExp *)ea)->var;
6249 goto Ldsym;
6250 }
6251 if (ea->op == TOKtemplate)
6252 {
6253 sa = ((TemplateExp *)ea)->td;
6254 goto Ldsym;
6255 }
6256 if (ea->op == TOKdottd && !(flags & 1))
6257 {
6258 // translate expression to dsymbol.
6259 sa = ((DotTemplateExp *)ea)->td;
6260 goto Ldsym;
6261 }
6262 if (ea->op == TOKdot)
6263 {
6264 if (ScopeExp *se = ((DotExp *)ea)->e2->isScopeExp())
6265 {
6266 sa = se->sds;
6267 goto Ldsym;
6268 }
6269 }
6270 }
6271 else if (sa)
6272 {
6273 Ldsym:
6274 //printf("dsym %s %s\n", sa->kind(), sa->toChars());
6275 if (sa->errors)
6276 {
6277 err = true;
6278 continue;
6279 }
6280
6281 TupleDeclaration *d = sa->toAlias()->isTupleDeclaration();
6282 if (d)
6283 {
6284 // Expand tuple
6285 tiargs->remove(j);
6286 tiargs->insert(j, d->objects);
6287 j--;
6288 continue;
6289 }
6290 if (FuncAliasDeclaration *fa = sa->isFuncAliasDeclaration())
6291 {
6292 FuncDeclaration *f = fa->toAliasFunc();
6293 if (!fa->hasOverloads && f->isUnique())
6294 {
6295 // Strip FuncAlias only when the aliased function
6296 // does not have any overloads.
6297 sa = f;
6298 }
6299 }
6300 (*tiargs)[j] = sa;
6301
6302 TemplateDeclaration *td = sa->isTemplateDeclaration();
6303 if (td && td->semanticRun == PASSinit && td->literal)
6304 {
6305 dsymbolSemantic(td, sc);
6306 }
6307 FuncDeclaration *fd = sa->isFuncDeclaration();
6308 if (fd)
6309 fd->functionSemantic();
6310 }
6311 else if (isParameter(o))
6312 {
6313 }
6314 else
6315 {
6316 assert(0);
6317 }
6318 //printf("1: (*tiargs)[%d] = %p\n", j, (*tiargs)[j]);
6319 }
6320 return !err;
6321 }
6322
findBestMatch(Scope * sc,Expressions * fargs)6323 bool TemplateInstance::findBestMatch(Scope *sc, Expressions *fargs)
6324 {
6325 if (havetempdecl)
6326 {
6327 TemplateDeclaration *tempdecl = this->tempdecl->isTemplateDeclaration();
6328 assert(tempdecl);
6329 assert(tempdecl->_scope);
6330 // Deduce tdtypes
6331 tdtypes.setDim(tempdecl->parameters->length);
6332 if (!tempdecl->matchWithInstance(sc, this, &tdtypes, fargs, 2))
6333 {
6334 error("incompatible arguments for template instantiation");
6335 return false;
6336 }
6337 // TODO: Normalizing tiargs for bugzilla 7469 is necessary?
6338 return true;
6339 }
6340
6341 unsigned errs = global.errors;
6342 TemplateDeclaration *td_last = NULL;
6343
6344 struct ParamBest
6345 {
6346 // context
6347 Scope *sc;
6348 TemplateInstance *ti;
6349 Objects dedtypes;
6350 // result
6351 TemplateDeclaration *td_best;
6352 TemplateDeclaration *td_ambig;
6353 MATCH m_best;
6354
6355 static int fp(void *param, Dsymbol *s)
6356 {
6357 return ((ParamBest *)param)->fp(s);
6358 }
6359 int fp(Dsymbol *s)
6360 {
6361 TemplateDeclaration *td = s->isTemplateDeclaration();
6362 if (!td)
6363 return 0;
6364 if (td->inuse)
6365 {
6366 td->error(ti->loc, "recursive template expansion");
6367 return 1;
6368 }
6369 if (td == td_best) // skip duplicates
6370 return 0;
6371
6372 //printf("td = %s\n", td->toPrettyChars());
6373
6374 // If more arguments than parameters,
6375 // then this is no match.
6376 if (td->parameters->length < ti->tiargs->length)
6377 {
6378 if (!td->isVariadic())
6379 return 0;
6380 }
6381
6382 dedtypes.setDim(td->parameters->length);
6383 dedtypes.zero();
6384 assert(td->semanticRun != PASSinit);
6385 MATCH m = td->matchWithInstance(sc, ti, &dedtypes, ti->fargs, 0);
6386 //printf("matchWithInstance = %d\n", m);
6387 if (m <= MATCHnomatch) // no match at all
6388 return 0;
6389
6390 if (m < m_best) goto Ltd_best;
6391 if (m > m_best) goto Ltd;
6392
6393 {
6394 // Disambiguate by picking the most specialized TemplateDeclaration
6395 MATCH c1 = td->leastAsSpecialized(sc, td_best, ti->fargs);
6396 MATCH c2 = td_best->leastAsSpecialized(sc, td, ti->fargs);
6397 //printf("c1 = %d, c2 = %d\n", c1, c2);
6398 if (c1 > c2) goto Ltd;
6399 if (c1 < c2) goto Ltd_best;
6400 }
6401
6402 td_ambig = td;
6403 return 0;
6404
6405 Ltd_best: // td_best is the best match so far
6406 td_ambig = NULL;
6407 return 0;
6408
6409 Ltd: // td is the new best match
6410 td_ambig = NULL;
6411 td_best = td;
6412 m_best = m;
6413 ti->tdtypes.setDim(dedtypes.length);
6414 memcpy(ti->tdtypes.tdata(), dedtypes.tdata(), ti->tdtypes.length * sizeof(void *));
6415 return 0;
6416 }
6417 };
6418 ParamBest p;
6419 // context
6420 p.ti = this;
6421 p.sc = sc;
6422
6423 /* Since there can be multiple TemplateDeclaration's with the same
6424 * name, look for the best match.
6425 */
6426 OverloadSet *tovers = tempdecl->isOverloadSet();
6427 size_t overs_dim = tovers ? tovers->a.length : 1;
6428 for (size_t oi = 0; oi < overs_dim; oi++)
6429 {
6430 // result
6431 p.td_best = NULL;
6432 p.td_ambig = NULL;
6433 p.m_best = MATCHnomatch;
6434
6435 Dsymbol *dstart = tovers ? tovers->a[oi] : tempdecl;
6436 overloadApply(dstart, &p, &ParamBest::fp);
6437
6438 if (p.td_ambig)
6439 {
6440 ::error(loc, "%s %s.%s matches more than one template declaration:\n%s: %s\nand\n%s: %s",
6441 p.td_best->kind(), p.td_best->parent->toPrettyChars(), p.td_best->ident->toChars(),
6442 p.td_best->loc.toChars() , p.td_best->toChars(),
6443 p.td_ambig->loc.toChars(), p.td_ambig->toChars());
6444 return false;
6445 }
6446 if (p.td_best)
6447 {
6448 if (!td_last)
6449 td_last = p.td_best;
6450 else if (td_last != p.td_best)
6451 {
6452 ScopeDsymbol::multiplyDefined(loc, td_last, p.td_best);
6453 return false;
6454 }
6455 }
6456 }
6457
6458 if (td_last)
6459 {
6460 /* Bugzilla 7469: Normalize tiargs by using corresponding deduced
6461 * template value parameters and tuples for the correct mangling.
6462 *
6463 * By doing this before hasNestedArgs, CTFEable local variable will be
6464 * accepted as a value parameter. For example:
6465 *
6466 * void foo() {
6467 * struct S(int n) {} // non-global template
6468 * const int num = 1; // CTFEable local variable
6469 * S!num s; // S!1 is instantiated, not S!num
6470 * }
6471 */
6472 size_t dim = td_last->parameters->length - (td_last->isVariadic() ? 1 : 0);
6473 for (size_t i = 0; i < dim; i++)
6474 {
6475 if (tiargs->length <= i)
6476 tiargs->push(tdtypes[i]);
6477 assert(i < tiargs->length);
6478
6479 TemplateValueParameter *tvp = (*td_last->parameters)[i]->isTemplateValueParameter();
6480 if (!tvp)
6481 continue;
6482 assert(tdtypes[i]);
6483 // tdtypes[i] is already normalized to the required type in matchArg
6484
6485 (*tiargs)[i] = tdtypes[i];
6486 }
6487 if (td_last->isVariadic() && tiargs->length == dim && tdtypes[dim])
6488 {
6489 Tuple *va = isTuple(tdtypes[dim]);
6490 assert(va);
6491 for (size_t i = 0; i < va->objects.length; i++)
6492 tiargs->push(va->objects[i]);
6493 }
6494 }
6495 else if (errors && inst)
6496 {
6497 // instantiation was failed with error reporting
6498 assert(global.errors);
6499 return false;
6500 }
6501 else
6502 {
6503 TemplateDeclaration *tdecl = tempdecl->isTemplateDeclaration();
6504
6505 if (errs != global.errors)
6506 errorSupplemental(loc, "while looking for match for %s", toChars());
6507 else if (tdecl && !tdecl->overnext)
6508 {
6509 // Only one template, so we can give better error message
6510 error("does not match template declaration %s", tdecl->toChars());
6511 }
6512 else
6513 ::error(loc, "%s %s.%s does not match any template declaration",
6514 tempdecl->kind(), tempdecl->parent->toPrettyChars(), tempdecl->ident->toChars());
6515 return false;
6516 }
6517
6518 /* The best match is td_last
6519 */
6520 tempdecl = td_last;
6521
6522 return (errs == global.errors);
6523 }
6524
6525 /*****************************************************
6526 * Determine if template instance is really a template function,
6527 * and that template function needs to infer types from the function
6528 * arguments.
6529 *
6530 * Like findBestMatch, iterate possible template candidates,
6531 * but just looks only the necessity of type inference.
6532 */
6533
needsTypeInference(Scope * sc,int flag)6534 bool TemplateInstance::needsTypeInference(Scope *sc, int flag)
6535 {
6536 //printf("TemplateInstance::needsTypeInference() %s\n", toChars());
6537 if (semanticRun != PASSinit)
6538 return false;
6539
6540 struct ParamNeedsInf
6541 {
6542 // context
6543 Scope *sc;
6544 TemplateInstance *ti;
6545 int flag;
6546 // result
6547 Objects dedtypes;
6548 size_t count;
6549
6550 static int fp(void *param, Dsymbol *s)
6551 {
6552 return ((ParamNeedsInf *)param)->fp(s);
6553 }
6554 int fp(Dsymbol *s)
6555 {
6556 TemplateDeclaration *td = s->isTemplateDeclaration();
6557 if (!td)
6558 return 0;
6559 if (td->inuse)
6560 {
6561 td->error(ti->loc, "recursive template expansion");
6562 return 1;
6563 }
6564
6565 /* If any of the overloaded template declarations need inference,
6566 * then return true
6567 */
6568 FuncDeclaration *fd;
6569 if (!td->onemember)
6570 return 0;
6571 if (TemplateDeclaration *td2 = td->onemember->isTemplateDeclaration())
6572 {
6573 if (!td2->onemember || !td2->onemember->isFuncDeclaration())
6574 return 0;
6575 if (ti->tiargs->length >= td->parameters->length - (td->isVariadic() ? 1 : 0))
6576 return 0;
6577 return 1;
6578 }
6579 if ((fd = td->onemember->isFuncDeclaration()) == NULL ||
6580 fd->type->ty != Tfunction)
6581 {
6582 return 0;
6583 }
6584
6585 for (size_t i = 0; i < td->parameters->length; i++)
6586 {
6587 if ((*td->parameters)[i]->isTemplateThisParameter())
6588 return 1;
6589 }
6590
6591 /* Determine if the instance arguments, tiargs, are all that is necessary
6592 * to instantiate the template.
6593 */
6594 //printf("tp = %p, td->parameters->length = %d, tiargs->length = %d\n", tp, td->parameters->length, ti->tiargs->length);
6595 TypeFunction *tf = (TypeFunction *)fd->type;
6596 if (size_t dim = tf->parameterList.length())
6597 {
6598 TemplateParameter *tp = td->isVariadic();
6599 if (tp && td->parameters->length > 1)
6600 return 1;
6601
6602 if (!tp && ti->tiargs->length < td->parameters->length)
6603 {
6604 // Can remain tiargs be filled by default arguments?
6605 for (size_t i = ti->tiargs->length; i < td->parameters->length; i++)
6606 {
6607 if (!(*td->parameters)[i]->hasDefaultArg())
6608 return 1;
6609 }
6610 }
6611
6612 for (size_t i = 0; i < dim; i++)
6613 {
6614 // 'auto ref' needs inference.
6615 if (tf->parameterList[i]->storageClass & STCauto)
6616 return 1;
6617 }
6618 }
6619
6620 if (!flag)
6621 {
6622 /* Calculate the need for overload resolution.
6623 * When only one template can match with tiargs, inference is not necessary.
6624 */
6625 dedtypes.setDim(td->parameters->length);
6626 dedtypes.zero();
6627 if (td->semanticRun == PASSinit)
6628 {
6629 if (td->_scope)
6630 {
6631 // Try to fix forward reference. Ungag errors while doing so.
6632 Ungag ungag = td->ungagSpeculative();
6633 dsymbolSemantic(td, td->_scope);
6634 }
6635 if (td->semanticRun == PASSinit)
6636 {
6637 ti->error("%s forward references template declaration %s", ti->toChars(), td->toChars());
6638 return 1;
6639 }
6640 }
6641 assert(td->semanticRun != PASSinit);
6642 MATCH m = td->matchWithInstance(sc, ti, &dedtypes, NULL, 0);
6643 if (m <= MATCHnomatch)
6644 return 0;
6645 }
6646
6647 /* If there is more than one function template which matches, we may
6648 * need type inference (see Bugzilla 4430)
6649 */
6650 if (++count > 1)
6651 return 1;
6652
6653 return 0;
6654 }
6655 };
6656 ParamNeedsInf p;
6657 // context
6658 p.ti = this;
6659 p.sc = sc;
6660 p.flag = flag;
6661 // result
6662 p.count = 0;
6663
6664 OverloadSet *tovers = tempdecl->isOverloadSet();
6665 size_t overs_dim = tovers ? tovers->a.length : 1;
6666 unsigned olderrs = global.errors;
6667 for (size_t oi = 0; oi < overs_dim; oi++)
6668 {
6669 if (overloadApply(tovers ? tovers->a[oi] : tempdecl, &p, &ParamNeedsInf::fp))
6670 return true;
6671 }
6672 if (olderrs != global.errors)
6673 {
6674 if (!global.gag)
6675 {
6676 errorSupplemental(loc, "while looking for match for %s", toChars());
6677 semanticRun = PASSsemanticdone;
6678 inst = this;
6679 }
6680 errors = true;
6681 }
6682 //printf("false\n");
6683 return false;
6684 }
6685
6686
6687 /*****************************************
6688 * Determines if a TemplateInstance will need a nested
6689 * generation of the TemplateDeclaration.
6690 * Sets enclosing property if so, and returns != 0;
6691 */
6692
hasNestedArgs(Objects * args,bool isstatic)6693 bool TemplateInstance::hasNestedArgs(Objects *args, bool isstatic)
6694 {
6695 int nested = 0;
6696 //printf("TemplateInstance::hasNestedArgs('%s')\n", tempdecl->ident->toChars());
6697
6698 /* A nested instance happens when an argument references a local
6699 * symbol that is on the stack.
6700 */
6701 for (size_t i = 0; i < args->length; i++)
6702 {
6703 RootObject *o = (*args)[i];
6704 Expression *ea = isExpression(o);
6705 Dsymbol *sa = isDsymbol(o);
6706 Tuple *va = isTuple(o);
6707 if (ea)
6708 {
6709 if (ea->op == TOKvar)
6710 {
6711 sa = ((VarExp *)ea)->var;
6712 goto Lsa;
6713 }
6714 if (ea->op == TOKthis)
6715 {
6716 sa = ((ThisExp *)ea)->var;
6717 goto Lsa;
6718 }
6719 if (ea->op == TOKfunction)
6720 {
6721 if (((FuncExp *)ea)->td)
6722 sa = ((FuncExp *)ea)->td;
6723 else
6724 sa = ((FuncExp *)ea)->fd;
6725 goto Lsa;
6726 }
6727 // Emulate Expression::toMangleBuffer call that had exist in TemplateInstance::genIdent.
6728 if (ea->op != TOKint64 &&
6729 ea->op != TOKfloat64 &&
6730 ea->op != TOKcomplex80 &&
6731 ea->op != TOKnull &&
6732 ea->op != TOKstring &&
6733 ea->op != TOKarrayliteral &&
6734 ea->op != TOKassocarrayliteral &&
6735 ea->op != TOKstructliteral)
6736 {
6737 ea->error("expression %s is not a valid template value argument", ea->toChars());
6738 errors = true;
6739 }
6740 }
6741 else if (sa)
6742 {
6743 Lsa:
6744 sa = sa->toAlias();
6745 TemplateDeclaration *td = sa->isTemplateDeclaration();
6746 if (td)
6747 {
6748 TemplateInstance *ti = sa->toParent()->isTemplateInstance();
6749 if (ti && ti->enclosing)
6750 sa = ti;
6751 }
6752 TemplateInstance *ti = sa->isTemplateInstance();
6753 Declaration *d = sa->isDeclaration();
6754 if ((td && td->literal) ||
6755 (ti && ti->enclosing) ||
6756 (d && !d->isDataseg() &&
6757 !(d->storage_class & STCmanifest) &&
6758 (!d->isFuncDeclaration() || d->isFuncDeclaration()->isNested()) &&
6759 !isTemplateMixin()
6760 ))
6761 {
6762 // if module level template
6763 if (isstatic)
6764 {
6765 Dsymbol *dparent = sa->toParent2();
6766 if (!enclosing)
6767 enclosing = dparent;
6768 else if (enclosing != dparent)
6769 {
6770 /* Select the more deeply nested of the two.
6771 * Error if one is not nested inside the other.
6772 */
6773 for (Dsymbol *p = enclosing; p; p = p->parent)
6774 {
6775 if (p == dparent)
6776 goto L1; // enclosing is most nested
6777 }
6778 for (Dsymbol *p = dparent; p; p = p->parent)
6779 {
6780 if (p == enclosing)
6781 {
6782 enclosing = dparent;
6783 goto L1; // dparent is most nested
6784 }
6785 }
6786 error("%s is nested in both %s and %s",
6787 toChars(), enclosing->toChars(), dparent->toChars());
6788 errors = true;
6789 }
6790 L1:
6791 //printf("\tnested inside %s\n", enclosing->toChars());
6792 nested |= 1;
6793 }
6794 else
6795 {
6796 error("cannot use local `%s` as parameter to non-global template %s", sa->toChars(), tempdecl->toChars());
6797 errors = true;
6798 }
6799 }
6800 }
6801 else if (va)
6802 {
6803 nested |= (int)hasNestedArgs(&va->objects, isstatic);
6804 }
6805 }
6806 //printf("-TemplateInstance::hasNestedArgs('%s') = %d\n", tempdecl->ident->toChars(), nested);
6807 return nested != 0;
6808 }
6809
6810 /*****************************************
6811 * Append 'this' to the specific module members[]
6812 */
appendToModuleMember()6813 Dsymbols *TemplateInstance::appendToModuleMember()
6814 {
6815 Module *mi = minst; // instantiated -> inserted module
6816
6817 if (global.params.useUnitTests)
6818 {
6819 // Turn all non-root instances to speculative
6820 if (mi && !mi->isRoot())
6821 mi = NULL;
6822 }
6823
6824 //printf("%s->appendToModuleMember() enclosing = %s mi = %s\n",
6825 // toPrettyChars(),
6826 // enclosing ? enclosing->toPrettyChars() : NULL,
6827 // mi ? mi->toPrettyChars() : NULL);
6828 if (!mi || mi->isRoot())
6829 {
6830 /* If the instantiated module is speculative or root, insert to the
6831 * member of a root module. Then:
6832 * - semantic3 pass will get called on the instance members.
6833 * - codegen pass will get a selection chance to do/skip it.
6834 */
6835
6836 struct N
6837 {
6838 static Dsymbol *getStrictEnclosing(TemplateInstance *ti)
6839 {
6840 do
6841 {
6842 if (ti->enclosing)
6843 return ti->enclosing;
6844 ti = ti->tempdecl->isInstantiated();
6845 }
6846 while (ti);
6847 return NULL;
6848 }
6849 };
6850 Dsymbol *enc = N::getStrictEnclosing(this);
6851
6852 // insert target is made stable by using the module
6853 // where tempdecl is declared.
6854 mi = (enc ? enc : tempdecl)->getModule();
6855 if (!mi->isRoot())
6856 mi = mi->importedFrom;
6857 assert(mi->isRoot());
6858 }
6859 else
6860 {
6861 /* If the instantiated module is non-root, insert to the member of the
6862 * non-root module. Then:
6863 * - semantic3 pass won't be called on the instance.
6864 * - codegen pass won't reach to the instance.
6865 */
6866 }
6867 //printf("\t--> mi = %s\n", mi->toPrettyChars());
6868
6869 if (memberOf == mi) // already a member
6870 {
6871 return NULL;
6872 }
6873
6874 Dsymbols *a = mi->members;
6875 a->push(this);
6876 memberOf = mi;
6877 if (mi->semanticRun >= PASSsemantic2done && mi->isRoot())
6878 Module::addDeferredSemantic2(this);
6879 if (mi->semanticRun >= PASSsemantic3done && mi->isRoot())
6880 Module::addDeferredSemantic3(this);
6881 return a;
6882 }
6883
6884 /****************************************
6885 * This instance needs an identifier for name mangling purposes.
6886 * Create one by taking the template declaration name and adding
6887 * the type signature for it.
6888 */
6889
genIdent(Objects * args)6890 Identifier *TemplateInstance::genIdent(Objects *args)
6891 {
6892 //printf("TemplateInstance::genIdent('%s')\n", tempdecl->ident->toChars());
6893 assert(args == tiargs);
6894 OutBuffer buf;
6895 mangleToBuffer(this, &buf);
6896 //printf("\tgenIdent = %s\n", id);
6897 return Identifier::idPool(buf.peekChars());
6898 }
6899
6900 /*************************************
6901 * Lazily generate identifier for template instance.
6902 * This is because 75% of the ident's are never needed.
6903 */
6904
getIdent()6905 Identifier *TemplateInstance::getIdent()
6906 {
6907 if (!ident && inst && !errors)
6908 ident = genIdent(tiargs); // need an identifier for name mangling purposes.
6909 return ident;
6910 }
6911
6912 /****************************************************
6913 * Declare parameters of template instance, initialize them with the
6914 * template instance arguments.
6915 */
6916
declareParameters(Scope * sc)6917 void TemplateInstance::declareParameters(Scope *sc)
6918 {
6919 TemplateDeclaration *tempdecl = this->tempdecl->isTemplateDeclaration();
6920 assert(tempdecl);
6921
6922 //printf("TemplateInstance::declareParameters()\n");
6923 for (size_t i = 0; i < tdtypes.length; i++)
6924 {
6925 TemplateParameter *tp = (*tempdecl->parameters)[i];
6926 //RootObject *o = (*tiargs)[i];
6927 RootObject *o = tdtypes[i]; // initializer for tp
6928
6929 //printf("\ttdtypes[%d] = %p\n", i, o);
6930 tempdecl->declareParameter(sc, tp, o);
6931 }
6932 }
6933
6934 /**************************************
6935 * Given an error instantiating the TemplateInstance,
6936 * give the nested TemplateInstance instantiations that got
6937 * us here. Those are a list threaded into the nested scopes.
6938 */
printInstantiationTrace()6939 void TemplateInstance::printInstantiationTrace()
6940 {
6941 if (global.gag)
6942 return;
6943
6944 const unsigned max_shown = 6;
6945 const char format[] = "instantiated from here: %s";
6946
6947 // determine instantiation depth and number of recursive instantiations
6948 unsigned n_instantiations = 1;
6949 unsigned n_totalrecursions = 0;
6950 for (TemplateInstance *cur = this; cur; cur = cur->tinst)
6951 {
6952 ++n_instantiations;
6953 // If two instantiations use the same declaration, they are recursive.
6954 // (this works even if they are instantiated from different places in the
6955 // same template).
6956 // In principle, we could also check for multiple-template recursion, but it's
6957 // probably not worthwhile.
6958 if (cur->tinst && cur->tempdecl && cur->tinst->tempdecl
6959 && cur->tempdecl->loc.equals(cur->tinst->tempdecl->loc))
6960 ++n_totalrecursions;
6961 }
6962
6963 // show full trace only if it's short or verbose is on
6964 if (n_instantiations <= max_shown || global.params.verbose)
6965 {
6966 for (TemplateInstance *cur = this; cur; cur = cur->tinst)
6967 {
6968 cur->errors = true;
6969 errorSupplemental(cur->loc, format, cur->toChars());
6970 }
6971 }
6972 else if (n_instantiations - n_totalrecursions <= max_shown)
6973 {
6974 // By collapsing recursive instantiations into a single line,
6975 // we can stay under the limit.
6976 int recursionDepth=0;
6977 for (TemplateInstance *cur = this; cur; cur = cur->tinst)
6978 {
6979 cur->errors = true;
6980 if (cur->tinst && cur->tempdecl && cur->tinst->tempdecl
6981 && cur->tempdecl->loc.equals(cur->tinst->tempdecl->loc))
6982 {
6983 ++recursionDepth;
6984 }
6985 else
6986 {
6987 if (recursionDepth)
6988 errorSupplemental(cur->loc, "%d recursive instantiations from here: %s", recursionDepth+2, cur->toChars());
6989 else
6990 errorSupplemental(cur->loc, format, cur->toChars());
6991 recursionDepth = 0;
6992 }
6993 }
6994 }
6995 else
6996 {
6997 // Even after collapsing the recursions, the depth is too deep.
6998 // Just display the first few and last few instantiations.
6999 unsigned i = 0;
7000 for (TemplateInstance *cur = this; cur; cur = cur->tinst)
7001 {
7002 cur->errors = true;
7003
7004 if (i == max_shown / 2)
7005 errorSupplemental(cur->loc, "... (%d instantiations, -v to show) ...", n_instantiations - max_shown);
7006
7007 if (i < max_shown / 2 ||
7008 i >= n_instantiations - max_shown + max_shown / 2)
7009 errorSupplemental(cur->loc, format, cur->toChars());
7010 ++i;
7011 }
7012 }
7013 }
7014
toAlias()7015 Dsymbol *TemplateInstance::toAlias()
7016 {
7017 if (!inst)
7018 {
7019 // Maybe we can resolve it
7020 if (_scope)
7021 {
7022 dsymbolSemantic(this, _scope);
7023 }
7024 if (!inst)
7025 {
7026 error("cannot resolve forward reference");
7027 errors = true;
7028 return this;
7029 }
7030 }
7031
7032 if (inst != this)
7033 return inst->toAlias();
7034
7035 if (aliasdecl)
7036 {
7037 return aliasdecl->toAlias();
7038 }
7039
7040 return inst;
7041 }
7042
kind()7043 const char *TemplateInstance::kind() const
7044 {
7045 return "template instance";
7046 }
7047
oneMember(Dsymbol ** ps,Identifier *)7048 bool TemplateInstance::oneMember(Dsymbol **ps, Identifier *)
7049 {
7050 *ps = NULL;
7051 return true;
7052 }
7053
toChars()7054 const char *TemplateInstance::toChars()
7055 {
7056 OutBuffer buf;
7057 toCBufferInstance(this, &buf);
7058 return buf.extractChars();
7059 }
7060
toPrettyCharsHelper()7061 const char *TemplateInstance::toPrettyCharsHelper()
7062 {
7063 OutBuffer buf;
7064 toCBufferInstance(this, &buf, true);
7065 return buf.extractChars();
7066 }
7067
7068 /*************************************
7069 * Compare proposed template instantiation with existing template instantiation.
7070 * Note that this is not commutative because of the auto ref check.
7071 * Params:
7072 * this = proposed template instantiation
7073 * o = existing template instantiation
7074 * Returns:
7075 * 0 for match, 1 for no match
7076 */
compare(RootObject * o)7077 int TemplateInstance::compare(RootObject *o)
7078 {
7079 TemplateInstance *ti = (TemplateInstance *)o;
7080
7081 //printf("this = %p, ti = %p\n", this, ti);
7082 assert(tdtypes.length == ti->tdtypes.length);
7083
7084 // Nesting must match
7085 if (enclosing != ti->enclosing)
7086 {
7087 //printf("test2 enclosing %s ti->enclosing %s\n", enclosing ? enclosing->toChars() : "", ti->enclosing ? ti->enclosing->toChars() : "");
7088 goto Lnotequals;
7089 }
7090 //printf("parent = %s, ti->parent = %s\n", parent->toPrettyChars(), ti->parent->toPrettyChars());
7091
7092 if (!arrayObjectMatch(&tdtypes, &ti->tdtypes))
7093 goto Lnotequals;
7094
7095 /* Template functions may have different instantiations based on
7096 * "auto ref" parameters.
7097 */
7098 if (FuncDeclaration *fd = ti->toAlias()->isFuncDeclaration())
7099 {
7100 if (!fd->errors)
7101 {
7102 ParameterList fparameters = fd->getParameterList();
7103 size_t nfparams = fparameters.length(); // Num function parameters
7104 for (size_t j = 0; j < nfparams; j++)
7105 {
7106 Parameter *fparam = fparameters[j];
7107 if (fparam->storageClass & STCautoref) // if "auto ref"
7108 {
7109 if (!fargs)
7110 goto Lnotequals;
7111 if (fargs->length <= j)
7112 break;
7113 Expression *farg = (*fargs)[j];
7114 if (farg->isLvalue())
7115 {
7116 if (!(fparam->storageClass & STCref))
7117 goto Lnotequals; // auto ref's don't match
7118 }
7119 else
7120 {
7121 if (fparam->storageClass & STCref)
7122 goto Lnotequals; // auto ref's don't match
7123 }
7124 }
7125 }
7126 }
7127 }
7128 return 0;
7129
7130 Lnotequals:
7131 return 1;
7132 }
7133
toHash()7134 hash_t TemplateInstance::toHash()
7135 {
7136 if (!hash)
7137 {
7138 hash = (size_t)(void *)enclosing;
7139 hash += arrayObjectHash(&tdtypes);
7140 hash += hash == 0;
7141 }
7142 return hash;
7143 }
7144
7145 /**************************************
7146 * IsExpression can evaluate the specified type speculatively, and even if
7147 * it instantiates any symbols, they are normally unnecessary for the
7148 * final executable.
7149 * However, if those symbols leak to the actual code, compiler should remark
7150 * them as non-speculative to generate their code and link to the final executable.
7151 */
unSpeculative(Scope * sc,RootObject * o)7152 void unSpeculative(Scope *sc, RootObject *o)
7153 {
7154 if (!o)
7155 return;
7156
7157 if (Tuple *tup = isTuple(o))
7158 {
7159 for (size_t i = 0; i < tup->objects.length; i++)
7160 {
7161 unSpeculative(sc, tup->objects[i]);
7162 }
7163 return;
7164 }
7165
7166 Dsymbol *s = getDsymbol(o);
7167 if (!s)
7168 return;
7169
7170 if (Declaration *d = s->isDeclaration())
7171 {
7172 if (VarDeclaration *vd = d->isVarDeclaration())
7173 o = vd->type;
7174 else if (AliasDeclaration *ad = d->isAliasDeclaration())
7175 {
7176 o = ad->getType();
7177 if (!o)
7178 o = ad->toAlias();
7179 }
7180 else
7181 o = d->toAlias();
7182
7183 s = getDsymbol(o);
7184 if (!s)
7185 return;
7186 }
7187
7188 if (TemplateInstance *ti = s->isTemplateInstance())
7189 {
7190 // If the instance is already non-speculative,
7191 // or it is leaked to the speculative scope.
7192 if (ti->minst != NULL || sc->minst == NULL)
7193 return;
7194
7195 // Remark as non-speculative instance.
7196 ti->minst = sc->minst;
7197 if (!ti->tinst)
7198 ti->tinst = sc->tinst;
7199
7200 unSpeculative(sc, ti->tempdecl);
7201 }
7202
7203 if (TemplateInstance *ti = s->isInstantiated())
7204 unSpeculative(sc, ti);
7205 }
7206
7207 /**
7208 Returns: true if the instances' innards are discardable.
7209
7210 The idea of this function is to see if the template instantiation
7211 can be 100% replaced with its eponymous member. All other members
7212 can be discarded, even in the compiler to free memory (for example,
7213 the template could be expanded in a region allocator, deemed trivial,
7214 the end result copied back out independently and the entire region freed),
7215 and can be elided entirely from the binary.
7216
7217 The current implementation affects code that generally looks like:
7218
7219 ---
7220 template foo(args...) {
7221 some_basic_type_or_string helper() { .... }
7222 enum foo = helper();
7223 }
7224 ---
7225
7226 since it was the easiest starting point of implementation but it can and
7227 should be expanded more later.
7228 */
isDiscardable(TemplateInstance * ti)7229 static bool isDiscardable(TemplateInstance *ti)
7230 {
7231 if (ti->aliasdecl == NULL)
7232 return false;
7233
7234 VarDeclaration *v = ti->aliasdecl->isVarDeclaration();
7235 if (v == NULL)
7236 return false;
7237
7238 if (!(v->storage_class & STCmanifest))
7239 return false;
7240
7241 // Currently only doing basic types here because it is the easiest proof-of-concept
7242 // implementation with minimal risk of side effects, but it could likely be
7243 // expanded to any type that already exists outside this particular instance.
7244 if (!(v->type->equals(Type::tstring) || (v->type->isTypeBasic() != NULL)))
7245 return false;
7246
7247 // Static ctors and dtors, even in an eponymous enum template, are still run,
7248 // so if any of them are in here, we'd better not assume it is trivial lest
7249 // we break useful code
7250 for (size_t i = 0; i < ti->members->length; i++)
7251 {
7252 Dsymbol *member = (*ti->members)[i];
7253 if (member->hasStaticCtorOrDtor())
7254 return false;
7255 if (member->isStaticDtorDeclaration())
7256 return false;
7257 if (member->isStaticCtorDeclaration())
7258 return false;
7259 }
7260
7261 // but if it passes through this gauntlet... it should be fine. D code will
7262 // see only the eponymous member, outside stuff can never access it, even through
7263 // reflection; the outside world ought to be none the wiser. Even dmd should be
7264 // able to simply free the memory of everything except the final result.
7265
7266 return true;
7267 }
7268
7269 /***********************************************
7270 * Returns true if this is not instantiated in non-root module, and
7271 * is a part of non-speculative instantiatiation.
7272 *
7273 * Note: minst does not stabilize until semantic analysis is completed,
7274 * so don't call this function during semantic analysis to return precise result.
7275 */
needsCodegen()7276 bool TemplateInstance::needsCodegen()
7277 {
7278 if (!minst)
7279 {
7280 // If this is a speculative instantiation,
7281 // 1. do codegen if ancestors really needs codegen.
7282 // 2. become non-speculative if siblings are not speculative
7283
7284 TemplateInstance *tnext = this->tnext;
7285 TemplateInstance *tinst = this->tinst;
7286 // At first, disconnect chain first to prevent infinite recursion.
7287 this->tnext = NULL;
7288 this->tinst = NULL;
7289
7290 // Determine necessity of tinst before tnext.
7291 if (tinst && tinst->needsCodegen())
7292 {
7293 minst = tinst->minst; // cache result
7294 if (global.params.allInst && minst)
7295 {
7296 return true;
7297 }
7298 assert(minst);
7299 assert(minst->isRoot() || minst->rootImports());
7300 return true;
7301 }
7302 if (tnext && (tnext->needsCodegen() || tnext->minst))
7303 {
7304 minst = tnext->minst; // cache result
7305 if (global.params.allInst && minst)
7306 {
7307 return true;
7308 }
7309 assert(minst);
7310 return minst->isRoot() || minst->rootImports();
7311 }
7312
7313 // Elide codegen because this is really speculative.
7314 return false;
7315 }
7316
7317 if (global.params.allInst)
7318 {
7319 return true;
7320 }
7321
7322 if (isDiscardable(this))
7323 {
7324 return false;
7325 }
7326
7327 /* Even when this is reached to the codegen pass,
7328 * a non-root nested template should not generate code,
7329 * due to avoid ODR violation.
7330 */
7331 if (enclosing && enclosing->inNonRoot())
7332 {
7333 if (tinst)
7334 {
7335 bool r = tinst->needsCodegen();
7336 minst = tinst->minst; // cache result
7337 return r;
7338 }
7339 if (tnext)
7340 {
7341 bool r = tnext->needsCodegen();
7342 minst = tnext->minst; // cache result
7343 return r;
7344 }
7345 return false;
7346 }
7347
7348 if (global.params.useUnitTests)
7349 {
7350 // Prefer instantiations from root modules, to maximize link-ability.
7351 if (minst->isRoot())
7352 return true;
7353
7354 TemplateInstance *tnext = this->tnext;
7355 TemplateInstance *tinst = this->tinst;
7356 this->tnext = NULL;
7357 this->tinst = NULL;
7358
7359 if (tinst && tinst->needsCodegen())
7360 {
7361 minst = tinst->minst; // cache result
7362 assert(minst);
7363 assert(minst->isRoot() || minst->rootImports());
7364 return true;
7365 }
7366 if (tnext && tnext->needsCodegen())
7367 {
7368 minst = tnext->minst; // cache result
7369 assert(minst);
7370 assert(minst->isRoot() || minst->rootImports());
7371 return true;
7372 }
7373
7374 // Bugzilla 2500 case
7375 if (minst->rootImports())
7376 return true;
7377
7378 // Elide codegen because this is not included in root instances.
7379 return false;
7380 }
7381 else
7382 {
7383 // Prefer instantiations from non-root module, to minimize object code size.
7384
7385 /* If a TemplateInstance is ever instantiated by non-root modules,
7386 * we do not have to generate code for it,
7387 * because it will be generated when the non-root module is compiled.
7388 *
7389 * But, if the non-root 'minst' imports any root modules, it might still need codegen.
7390 *
7391 * The problem is if A imports B, and B imports A, and both A
7392 * and B instantiate the same template, does the compilation of A
7393 * or the compilation of B do the actual instantiation?
7394 *
7395 * See Bugzilla 2500.
7396 */
7397 if (!minst->isRoot() && !minst->rootImports())
7398 return false;
7399
7400 TemplateInstance *tnext = this->tnext;
7401 this->tnext = NULL;
7402
7403 if (tnext && !tnext->needsCodegen() && tnext->minst)
7404 {
7405 minst = tnext->minst; // cache result
7406 assert(!minst->isRoot());
7407 return false;
7408 }
7409
7410 // Do codegen because this is not included in non-root instances.
7411 return true;
7412 }
7413 }
7414
7415 /* ======================== TemplateMixin ================================ */
7416
TemplateMixin(Loc loc,Identifier * ident,TypeQualified * tqual,Objects * tiargs)7417 TemplateMixin::TemplateMixin(Loc loc, Identifier *ident, TypeQualified *tqual, Objects *tiargs)
7418 : TemplateInstance(loc, tqual->idents.length ? (Identifier *)tqual->idents[tqual->idents.length - 1]
7419 : ((TypeIdentifier *)tqual)->ident)
7420 {
7421 //printf("TemplateMixin(ident = '%s')\n", ident ? ident->toChars() : "");
7422 this->ident = ident;
7423 this->tqual = tqual;
7424 this->tiargs = tiargs ? tiargs : new Objects();
7425 }
7426
syntaxCopy(Dsymbol *)7427 Dsymbol *TemplateMixin::syntaxCopy(Dsymbol *)
7428 {
7429 TemplateMixin *tm = new TemplateMixin(loc, ident,
7430 (TypeQualified *)tqual->syntaxCopy(), tiargs);
7431 return TemplateInstance::syntaxCopy(tm);
7432 }
7433
findTempDecl(Scope * sc)7434 bool TemplateMixin::findTempDecl(Scope *sc)
7435 {
7436 // Follow qualifications to find the TemplateDeclaration
7437 if (!tempdecl)
7438 {
7439 Expression *e;
7440 Type *t;
7441 Dsymbol *s;
7442 tqual->resolve(loc, sc, &e, &t, &s);
7443 if (!s)
7444 {
7445 error("is not defined");
7446 return false;
7447 }
7448 s = s->toAlias();
7449 tempdecl = s->isTemplateDeclaration();
7450 OverloadSet *os = s->isOverloadSet();
7451
7452 /* If an OverloadSet, look for a unique member that is a template declaration
7453 */
7454 if (os)
7455 {
7456 Dsymbol *ds = NULL;
7457 for (size_t i = 0; i < os->a.length; i++)
7458 {
7459 Dsymbol *s2 = os->a[i]->isTemplateDeclaration();
7460 if (s2)
7461 {
7462 if (ds)
7463 {
7464 tempdecl = os;
7465 break;
7466 }
7467 ds = s2;
7468 }
7469 }
7470 }
7471 if (!tempdecl)
7472 {
7473 error("%s isn't a template", s->toChars());
7474 return false;
7475 }
7476 }
7477 assert(tempdecl);
7478
7479 struct ParamFwdResTm
7480 {
7481 static int fp(void *param, Dsymbol *s)
7482 {
7483 TemplateDeclaration *td = s->isTemplateDeclaration();
7484 if (!td)
7485 return 0;
7486
7487 TemplateMixin *tm = (TemplateMixin *)param;
7488 if (td->semanticRun == PASSinit)
7489 {
7490 if (td->_scope)
7491 dsymbolSemantic(td, td->_scope);
7492 else
7493 {
7494 tm->semanticRun = PASSinit;
7495 return 1;
7496 }
7497 }
7498 return 0;
7499 }
7500 };
7501 // Look for forward references
7502 OverloadSet *tovers = tempdecl->isOverloadSet();
7503 size_t overs_dim = tovers ? tovers->a.length : 1;
7504 for (size_t oi = 0; oi < overs_dim; oi++)
7505 {
7506 if (overloadApply(tovers ? tovers->a[oi] : tempdecl, (void *)this, &ParamFwdResTm::fp))
7507 return false;
7508 }
7509 return true;
7510 }
7511
kind()7512 const char *TemplateMixin::kind() const
7513 {
7514 return "mixin";
7515 }
7516
oneMember(Dsymbol ** ps,Identifier * ident)7517 bool TemplateMixin::oneMember(Dsymbol **ps, Identifier *ident)
7518 {
7519 return Dsymbol::oneMember(ps, ident);
7520 }
7521
apply(Dsymbol_apply_ft_t fp,void * param)7522 int TemplateMixin::apply(Dsymbol_apply_ft_t fp, void *param)
7523 {
7524 if (_scope) // if fwd reference
7525 dsymbolSemantic(this, NULL); // try to resolve it
7526 if (members)
7527 {
7528 for (size_t i = 0; i < members->length; i++)
7529 {
7530 Dsymbol *s = (*members)[i];
7531 if (s)
7532 {
7533 if (s->apply(fp, param))
7534 return 1;
7535 }
7536 }
7537 }
7538 return 0;
7539 }
7540
hasPointers()7541 bool TemplateMixin::hasPointers()
7542 {
7543 //printf("TemplateMixin::hasPointers() %s\n", toChars());
7544
7545 if (members)
7546 {
7547 for (size_t i = 0; i < members->length; i++)
7548 {
7549 Dsymbol *s = (*members)[i];
7550 //printf(" s = %s %s\n", s->kind(), s->toChars());
7551 if (s->hasPointers())
7552 {
7553 return true;
7554 }
7555 }
7556 }
7557 return false;
7558 }
7559
setFieldOffset(AggregateDeclaration * ad,unsigned * poffset,bool isunion)7560 void TemplateMixin::setFieldOffset(AggregateDeclaration *ad, unsigned *poffset, bool isunion)
7561 {
7562 //printf("TemplateMixin::setFieldOffset() %s\n", toChars());
7563 if (_scope) // if fwd reference
7564 dsymbolSemantic(this, NULL); // try to resolve it
7565 if (members)
7566 {
7567 for (size_t i = 0; i < members->length; i++)
7568 {
7569 Dsymbol *s = (*members)[i];
7570 //printf("\t%s\n", s->toChars());
7571 s->setFieldOffset(ad, poffset, isunion);
7572 }
7573 }
7574 }
7575
toChars()7576 const char *TemplateMixin::toChars()
7577 {
7578 OutBuffer buf;
7579 toCBufferInstance(this, &buf);
7580 return buf.extractChars();
7581 }
7582