?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
tree-object-size: use size_for_offset in more cases
[official-gcc.git] / gcc / d / dmd / dtemplate.d
blobd181facfc249b39aa644188aba9e0ef71f465086
1 /**
2 * Defines `TemplateDeclaration`, `TemplateInstance` and a few utilities
3 *
4 * This modules holds the two main template types:
5 * `TemplateDeclaration`, which is the user-provided declaration of a template,
6 * and `TemplateInstance`, which is an instance of a `TemplateDeclaration`
7 * with specific arguments.
8 *
9 * Template_Parameter:
10 * Additionally, the classes for template parameters are defined in this module.
11 * The base class, `TemplateParameter`, is inherited by:
12 * - `TemplateTypeParameter`
13 * - `TemplateThisParameter`
14 * - `TemplateValueParameter`
15 * - `TemplateAliasParameter`
16 * - `TemplateTupleParameter`
17 *
18 * Templates_semantic:
19 * The start of the template instantiation process looks like this:
20 * - A `TypeInstance` or `TypeIdentifier` is encountered.
21 * `TypeInstance` have a bang (e.g. `Foo!(arg)`) while `TypeIdentifier` don't.
22 * - A `TemplateInstance` is instantiated
23 * - Semantic is run on the `TemplateInstance` (see `dmd.dsymbolsem`)
24 * - The `TemplateInstance` search for its `TemplateDeclaration`,
25 * runs semantic on the template arguments and deduce the best match
26 * among the possible overloads.
27 * - The `TemplateInstance` search for existing instances with the same
28 * arguments, and uses it if found.
29 * - Otherwise, the rest of semantic is run on the `TemplateInstance`.
30 *
31 * Copyright: Copyright (C) 1999-2024 by The D Language Foundation, All Rights Reserved
32 * Authors: $(LINK2 https://www.digitalmars.com, Walter Bright)
33 * License: $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
34 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/dtemplate.d, _dtemplate.d)
35 * Documentation: https://dlang.org/phobos/dmd_dtemplate.html
36 * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/dtemplate.d
37 */
38
39 module dmd.dtemplate;
40
41 import core.stdc.stdio;
42 import core.stdc.string;
43 import dmd.aggregate;
44 import dmd.aliasthis;
45 import dmd.arraytypes;
46 import dmd.astenums;
47 import dmd.ast_node;
48 import dmd.attrib;
49 import dmd.dcast;
50 import dmd.dclass;
51 import dmd.declaration;
52 import dmd.dinterpret;
53 import dmd.dmangle;
54 import dmd.dmodule;
55 import dmd.dscope;
56 import dmd.dsymbol;
57 import dmd.dsymbolsem;
58 import dmd.errors;
59 import dmd.errorsink;
60 import dmd.expression;
61 import dmd.expressionsem;
62 import dmd.func;
63 import dmd.funcsem;
64 import dmd.globals;
65 import dmd.hdrgen;
66 import dmd.id;
67 import dmd.identifier;
68 import dmd.impcnvtab;
69 import dmd.init;
70 import dmd.initsem;
71 import dmd.location;
72 import dmd.mtype;
73 import dmd.opover;
74 import dmd.optimize;
75 import dmd.root.array;
76 import dmd.common.outbuffer;
77 import dmd.rootobject;
78 import dmd.semantic2;
79 import dmd.semantic3;
80 import dmd.templatesem;
81 import dmd.tokens;
82 import dmd.typesem;
83 import dmd.visitor;
84
85 import dmd.templateparamsem;
86
87 //debug = FindExistingInstance; // print debug stats of findExistingInstance
88 private enum LOG = false;
89
90 enum IDX_NOTFOUND = 0x12345678;
91
92 pure nothrow @nogc @safe
93 {
94
95 /********************************************
96 * These functions substitute for dynamic_cast. dynamic_cast does not work
97 * on earlier versions of gcc.
98 */
99 inout(Expression) isExpression(inout RootObject o)
100 {
101 //return dynamic_cast<Expression *>(o);
102 if (!o || o.dyncast() != DYNCAST.expression)
103 return null;
104 return cast(inout(Expression))o;
105 }
106
107 inout(Dsymbol) isDsymbol(inout RootObject o)
108 {
109 //return dynamic_cast<Dsymbol *>(o);
110 if (!o || o.dyncast() != DYNCAST.dsymbol)
111 return null;
112 return cast(inout(Dsymbol))o;
113 }
114
115 inout(Type) isType(inout RootObject o)
116 {
117 //return dynamic_cast<Type *>(o);
118 if (!o || o.dyncast() != DYNCAST.type)
119 return null;
120 return cast(inout(Type))o;
121 }
122
123 inout(Tuple) isTuple(inout RootObject o)
124 {
125 //return dynamic_cast<Tuple *>(o);
126 if (!o || o.dyncast() != DYNCAST.tuple)
127 return null;
128 return cast(inout(Tuple))o;
129 }
130
131 inout(Parameter) isParameter(inout RootObject o)
132 {
133 //return dynamic_cast<Parameter *>(o);
134 if (!o || o.dyncast() != DYNCAST.parameter)
135 return null;
136 return cast(inout(Parameter))o;
137 }
138
139 inout(TemplateParameter) isTemplateParameter(inout RootObject o)
140 {
141 if (!o || o.dyncast() != DYNCAST.templateparameter)
142 return null;
143 return cast(inout(TemplateParameter))o;
144 }
145
146 /**************************************
147 * Is this Object an error?
148 */
149 bool isError(const RootObject o)
150 {
151 if (const t = isType(o))
152 return (t.ty == Terror);
153 if (const e = isExpression(o))
154 return (e.op == EXP.error || !e.type || e.type.ty == Terror);
155 if (const v = isTuple(o))
156 return arrayObjectIsError(v.objects);
157 const s = isDsymbol(o);
158 assert(s);
159 if (s.errors)
160 return true;
161 return s.parent ? isError(s.parent) : false;
162 }
163
164 /**************************************
165 * Are any of the Objects an error?
166 */
167 bool arrayObjectIsError(const ref Objects args)
168 {
169 foreach (const o; args)
170 {
171 if (isError(o))
172 return true;
173 }
174 return false;
175 }
176
177 /***********************
178 * Try to get arg as a type.
179 */
180 inout(Type) getType(inout RootObject o)
181 {
182 inout t = isType(o);
183 if (!t)
184 {
185 if (inout e = isExpression(o))
186 return e.type;
187 }
188 return t;
189 }
190
191 }
192
193 /***********************************
194 * If oarg represents a Dsymbol, return that Dsymbol
195 * Params:
196 * oarg = argument to check
197 * Returns:
198 * Dsymbol if a symbol, null if not
199 */
200 Dsymbol getDsymbol(RootObject oarg)
201 {
202 //printf("getDsymbol()\n");
203 //printf("e %p s %p t %p v %p\n", isExpression(oarg), isDsymbol(oarg), isType(oarg), isTuple(oarg));
204 if (auto ea = isExpression(oarg))
205 {
206 // Try to convert Expression to symbol
207 if (auto ve = ea.isVarExp())
208 return ve.var;
209 else if (auto fe = ea.isFuncExp())
210 return fe.td ? fe.td : fe.fd;
211 else if (auto te = ea.isTemplateExp())
212 return te.td;
213 else if (auto te = ea.isScopeExp())
214 return te.sds;
215 else
216 return null;
217 }
218 else
219 {
220 // Try to convert Type to symbol
221 if (auto ta = isType(oarg))
222 return ta.toDsymbol(null);
223 else
224 return isDsymbol(oarg); // if already a symbol
225 }
226 }
227
228
229 private Expression getValue(ref Dsymbol s)
230 {
231 if (s)
232 {
233 if (VarDeclaration v = s.isVarDeclaration())
234 {
235 if (v.storage_class & STC.manifest)
236 return v.getConstInitializer();
237 }
238 }
239 return null;
240 }
241
242 /***********************
243 * Try to get value from manifest constant
244 */
245 private Expression getValue(Expression e)
246 {
247 if (!e)
248 return null;
249 if (auto ve = e.isVarExp())
250 {
251 if (auto v = ve.var.isVarDeclaration())
252 {
253 if (v.storage_class & STC.manifest)
254 {
255 e = v.getConstInitializer();
256 }
257 }
258 }
259 return e;
260 }
261
262 private Expression getExpression(RootObject o)
263 {
264 auto s = isDsymbol(o);
265 return s ? .getValue(s) : .getValue(isExpression(o));
266 }
267
268 /******************************
269 * See if two objects match
270 * Params:
271 * o1 = first object
272 * o2 = second object
273 * Returns: true if they match
274 */
275 private bool match(RootObject o1, RootObject o2)
276 {
277 enum log = false;
278
279 static if (log)
280 {
281 printf("match() o1 = %p %s (%d), o2 = %p %s (%d)\n",
282 o1, o1.toChars(), o1.dyncast(), o2, o2.toChars(), o2.dyncast());
283 }
284
285 /* A proper implementation of the various equals() overrides
286 * should make it possible to just do o1.equals(o2), but
287 * we'll do that another day.
288 */
289 /* Manifest constants should be compared by their values,
290 * at least in template arguments.
291 */
292
293 if (auto t1 = isType(o1))
294 {
295 auto t2 = isType(o2);
296 if (!t2)
297 goto Lnomatch;
298
299 static if (log)
300 {
301 printf("\tt1 = %s\n", t1.toChars());
302 printf("\tt2 = %s\n", t2.toChars());
303 }
304 if (!t1.equals(t2))
305 goto Lnomatch;
306
307 goto Lmatch;
308 }
309 if (auto e1 = getExpression(o1))
310 {
311 auto e2 = getExpression(o2);
312 if (!e2)
313 goto Lnomatch;
314
315 static if (log)
316 {
317 printf("\te1 = %s '%s' %s\n", e1.type ? e1.type.toChars() : "null", EXPtoString(e1.op).ptr, e1.toChars());
318 printf("\te2 = %s '%s' %s\n", e2.type ? e2.type.toChars() : "null", EXPtoString(e2.op).ptr, e2.toChars());
319 }
320
321 // two expressions can be equal although they do not have the same
322 // type; that happens when they have the same value. So check type
323 // as well as expression equality to ensure templates are properly
324 // matched.
325 if (!(e1.type && e2.type && e1.type.equals(e2.type)) || !e1.equals(e2))
326 goto Lnomatch;
327
328 goto Lmatch;
329 }
330 if (auto s1 = isDsymbol(o1))
331 {
332 auto s2 = isDsymbol(o2);
333 if (!s2)
334 goto Lnomatch;
335
336 static if (log)
337 {
338 printf("\ts1 = %s \n", s1.kind(), s1.toChars());
339 printf("\ts2 = %s \n", s2.kind(), s2.toChars());
340 }
341 if (!s1.equals(s2))
342 goto Lnomatch;
343 if (s1.parent != s2.parent && !s1.isFuncDeclaration() && !s2.isFuncDeclaration())
344 goto Lnomatch;
345
346 goto Lmatch;
347 }
348 if (auto u1 = isTuple(o1))
349 {
350 auto u2 = isTuple(o2);
351 if (!u2)
352 goto Lnomatch;
353
354 static if (log)
355 {
356 printf("\tu1 = %s\n", u1.toChars());
357 printf("\tu2 = %s\n", u2.toChars());
358 }
359 if (!arrayObjectMatch(u1.objects, u2.objects))
360 goto Lnomatch;
361
362 goto Lmatch;
363 }
364 Lmatch:
365 static if (log)
366 printf("\t. match\n");
367 return true;
368
369 Lnomatch:
370 static if (log)
371 printf("\t. nomatch\n");
372 return false;
373 }
374
375 /************************************
376 * Match an array of them.
377 */
378 bool arrayObjectMatch(ref Objects oa1, ref Objects oa2)
379 {
380 if (&oa1 == &oa2)
381 return true;
382 if (oa1.length != oa2.length)
383 return false;
384 immutable oa1dim = oa1.length;
385 auto oa1d = oa1[].ptr;
386 auto oa2d = oa2[].ptr;
387 foreach (j; 0 .. oa1dim)
388 {
389 RootObject o1 = oa1d[j];
390 RootObject o2 = oa2d[j];
391 if (!match(o1, o2))
392 {
393 return false;
394 }
395 }
396 return true;
397 }
398
399 /************************************
400 * Return hash of Objects.
401 */
402 private size_t arrayObjectHash(ref Objects oa1)
403 {
404 import dmd.root.hash : mixHash;
405
406 size_t hash = 0;
407 foreach (o1; oa1)
408 {
409 /* Must follow the logic of match()
410 */
411 if (auto t1 = isType(o1))
412 hash = mixHash(hash, cast(size_t)t1.deco);
413 else if (auto e1 = getExpression(o1))
414 hash = mixHash(hash, expressionHash(e1));
415 else if (auto s1 = isDsymbol(o1))
416 {
417 auto fa1 = s1.isFuncAliasDeclaration();
418 if (fa1)
419 s1 = fa1.toAliasFunc();
420 hash = mixHash(hash, mixHash(cast(size_t)cast(void*)s1.getIdent(), cast(size_t)cast(void*)s1.parent));
421 }
422 else if (auto u1 = isTuple(o1))
423 hash = mixHash(hash, arrayObjectHash(u1.objects));
424 }
425 return hash;
426 }
427
428
429 /************************************
430 * Computes hash of expression.
431 * Handles all Expression classes and MUST match their equals method,
432 * i.e. e1.equals(e2) implies expressionHash(e1) == expressionHash(e2).
433 */
434 private size_t expressionHash(Expression e)
435 {
436 import dmd.root.ctfloat : CTFloat;
437 import dmd.root.hash : calcHash, mixHash;
438
439 switch (e.op)
440 {
441 case EXP.int64:
442 return cast(size_t) e.isIntegerExp().getInteger();
443
444 case EXP.float64:
445 return CTFloat.hash(e.isRealExp().value);
446
447 case EXP.complex80:
448 auto ce = e.isComplexExp();
449 return mixHash(CTFloat.hash(ce.toReal), CTFloat.hash(ce.toImaginary));
450
451 case EXP.identifier:
452 return cast(size_t)cast(void*) e.isIdentifierExp().ident;
453
454 case EXP.null_:
455 return cast(size_t)cast(void*) e.isNullExp().type;
456
457 case EXP.string_:
458 return calcHash(e.isStringExp.peekData());
459
460 case EXP.tuple:
461 {
462 auto te = e.isTupleExp();
463 size_t hash = 0;
464 hash += te.e0 ? expressionHash(te.e0) : 0;
465 foreach (elem; *te.exps)
466 hash = mixHash(hash, expressionHash(elem));
467 return hash;
468 }
469
470 case EXP.arrayLiteral:
471 {
472 auto ae = e.isArrayLiteralExp();
473 size_t hash;
474 foreach (i; 0 .. ae.elements.length)
475 hash = mixHash(hash, expressionHash(ae[i]));
476 return hash;
477 }
478
479 case EXP.assocArrayLiteral:
480 {
481 auto ae = e.isAssocArrayLiteralExp();
482 size_t hash;
483 foreach (i; 0 .. ae.keys.length)
484 // reduction needs associative op as keys are unsorted (use XOR)
485 hash ^= mixHash(expressionHash((*ae.keys)[i]), expressionHash((*ae.values)[i]));
486 return hash;
487 }
488
489 case EXP.structLiteral:
490 {
491 auto se = e.isStructLiteralExp();
492 size_t hash;
493 foreach (elem; *se.elements)
494 hash = mixHash(hash, elem ? expressionHash(elem) : 0);
495 return hash;
496 }
497
498 case EXP.variable:
499 return cast(size_t)cast(void*) e.isVarExp().var;
500
501 case EXP.function_:
502 return cast(size_t)cast(void*) e.isFuncExp().fd;
503
504 default:
505 // no custom equals for this expression
506 assert((&e.equals).funcptr is &RootObject.equals);
507 // equals based on identity
508 return cast(size_t)cast(void*) e;
509 }
510 }
511
512 RootObject objectSyntaxCopy(RootObject o)
513 {
514 if (!o)
515 return null;
516 if (Type t = isType(o))
517 return t.syntaxCopy();
518 if (Expression e = isExpression(o))
519 return e.syntaxCopy();
520 return o;
521 }
522
523 extern (C++) final class Tuple : RootObject
524 {
525 Objects objects;
526
527 extern (D) this() {}
528
529 /**
530 Params:
531 numObjects = The initial number of objects.
532 */
533 extern (D) this(size_t numObjects)
534 {
535 objects.setDim(numObjects);
536 }
537
538 // kludge for template.isType()
539 override DYNCAST dyncast() const
540 {
541 return DYNCAST.tuple;
542 }
543
544 override const(char)* toChars() const
545 {
546 return objects.toChars();
547 }
548 }
549
550 struct TemplatePrevious
551 {
552 TemplatePrevious* prev;
553 Scope* sc;
554 Objects* dedargs;
555 }
556
557 /***********************************************************
558 * [mixin] template Identifier (parameters) [Constraint]
559 * https://dlang.org/spec/template.html
560 * https://dlang.org/spec/template-mixin.html
561 */
562 extern (C++) final class TemplateDeclaration : ScopeDsymbol
563 {
564 import dmd.root.array : Array;
565
566 TemplateParameters* parameters; // array of TemplateParameter's
567 TemplateParameters* origParameters; // originals for Ddoc
568
569 Expression constraint;
570
571 // Hash table to look up TemplateInstance's of this TemplateDeclaration
572 TemplateInstance[TemplateInstanceBox] instances;
573
574 TemplateDeclaration overnext; // next overloaded TemplateDeclaration
575 TemplateDeclaration overroot; // first in overnext list
576 FuncDeclaration funcroot; // first function in unified overload list
577
578 Dsymbol onemember; // if !=null then one member of this template
579
580 bool literal; // this template declaration is a literal
581 bool ismixin; // this is a mixin template declaration
582 bool isstatic; // this is static template declaration
583 bool isTrivialAliasSeq; /// matches pattern `template AliasSeq(T...) { alias AliasSeq = T; }`
584 bool isTrivialAlias; /// matches pattern `template Alias(T) { alias Alias = qualifiers(T); }`
585 bool deprecated_; /// this template declaration is deprecated
586 Visibility visibility;
587
588 // threaded list of previous instantiation attempts on stack
589 TemplatePrevious* previous;
590
591 Expression lastConstraint; /// the constraint after the last failed evaluation
592 Array!Expression lastConstraintNegs; /// its negative parts
593 Objects* lastConstraintTiargs; /// template instance arguments for `lastConstraint`
594
595 extern (D) this(const ref Loc loc, Identifier ident, TemplateParameters* parameters, Expression constraint, Dsymbols* decldefs, bool ismixin = false, bool literal = false)
596 {
597 super(loc, ident);
598 static if (LOG)
599 {
600 printf("TemplateDeclaration(this = %p, id = '%s')\n", this, ident.toChars());
601 }
602 version (none)
603 {
604 if (parameters)
605 for (int i = 0; i < parameters.length; i++)
606 {
607 TemplateParameter tp = (*parameters)[i];
608 //printf("\tparameter[%d] = %p\n", i, tp);
609 TemplateTypeParameter ttp = tp.isTemplateTypeParameter();
610 if (ttp)
611 {
612 printf("\tparameter[%d] = %s : %s\n", i, tp.ident.toChars(), ttp.specType ? ttp.specType.toChars() : "");
613 }
614 }
615 }
616 this.parameters = parameters;
617 this.origParameters = parameters;
618 this.constraint = constraint;
619 this.members = decldefs;
620 this.literal = literal;
621 this.ismixin = ismixin;
622 this.isstatic = true;
623 this.visibility = Visibility(Visibility.Kind.undefined);
624
625 // Compute in advance for Ddoc's use
626 // https://issues.dlang.org/show_bug.cgi?id=11153: ident could be NULL if parsing fails.
627 if (!members || !ident)
628 return;
629
630 Dsymbol s;
631 if (!Dsymbol.oneMembers(members, s, ident) || !s)
632 return;
633
634 onemember = s;
635 s.parent = this;
636
637 /* Set isTrivialAliasSeq if this fits the pattern:
638 * template AliasSeq(T...) { alias AliasSeq = T; }
639 * or set isTrivialAlias if this fits the pattern:
640 * template Alias(T) { alias Alias = qualifiers(T); }
641 */
642 if (!(parameters && parameters.length == 1))
643 return;
644
645 auto ad = s.isAliasDeclaration();
646 if (!ad || !ad.type)
647 return;
648
649 auto ti = ad.type.isTypeIdentifier();
650
651 if (!ti || ti.idents.length != 0)
652 return;
653
654 if (auto ttp = (*parameters)[0].isTemplateTupleParameter())
655 {
656 if (ti.ident is ttp.ident &&
657 ti.mod == 0)
658 {
659 //printf("found isTrivialAliasSeq %s %s\n", s.toChars(), ad.type.toChars());
660 isTrivialAliasSeq = true;
661 }
662 }
663 else if (auto ttp = (*parameters)[0].isTemplateTypeParameter())
664 {
665 if (ti.ident is ttp.ident)
666 {
667 //printf("found isTrivialAlias %s %s\n", s.toChars(), ad.type.toChars());
668 isTrivialAlias = true;
669 }
670 }
671 }
672
673 override TemplateDeclaration syntaxCopy(Dsymbol)
674 {
675 //printf("TemplateDeclaration.syntaxCopy()\n");
676 TemplateParameters* p = null;
677 if (parameters)
678 {
679 p = new TemplateParameters(parameters.length);
680 foreach (i, ref param; *p)
681 param = (*parameters)[i].syntaxCopy();
682 }
683 return new TemplateDeclaration(loc, ident, p, constraint ? constraint.syntaxCopy() : null, Dsymbol.arraySyntaxCopy(members), ismixin, literal);
684 }
685
686 /**********************************
687 * Overload existing TemplateDeclaration 'this' with the new one 's'.
688 * Params:
689 * s = symbol to be inserted
690 * Return: true if successful; i.e. no conflict.
691 */
692 override bool overloadInsert(Dsymbol s)
693 {
694 static if (LOG)
695 {
696 printf("TemplateDeclaration.overloadInsert('%s')\n", s.toChars());
697 }
698 FuncDeclaration fd = s.isFuncDeclaration();
699 if (fd)
700 {
701 if (funcroot)
702 return funcroot.overloadInsert(fd);
703 funcroot = fd;
704 return funcroot.overloadInsert(this);
705 }
706
707 // https://issues.dlang.org/show_bug.cgi?id=15795
708 // if candidate is an alias and its sema is not run then
709 // insertion can fail because the thing it alias is not known
710 if (AliasDeclaration ad = s.isAliasDeclaration())
711 {
712 if (s._scope)
713 aliasSemantic(ad, s._scope);
714 if (ad.aliassym && ad.aliassym is this)
715 return false;
716 }
717 TemplateDeclaration td = s.toAlias().isTemplateDeclaration();
718 if (!td)
719 return false;
720
721 TemplateDeclaration pthis = this;
722 TemplateDeclaration* ptd;
723 for (ptd = &pthis; *ptd; ptd = &(*ptd).overnext)
724 {
725 }
726
727 td.overroot = this;
728 *ptd = td;
729 static if (LOG)
730 {
731 printf("\ttrue: no conflict\n");
732 }
733 return true;
734 }
735
736 override bool hasStaticCtorOrDtor()
737 {
738 return false; // don't scan uninstantiated templates
739 }
740
741 override const(char)* kind() const
742 {
743 return (onemember && onemember.isAggregateDeclaration()) ? onemember.kind() : "template";
744 }
745
746 override const(char)* toChars() const
747 {
748 HdrGenState hgs;
749 OutBuffer buf;
750 toCharsMaybeConstraints(this, buf, hgs);
751 return buf.extractChars();
752 }
753
754 override Visibility visible() pure nothrow @nogc @safe
755 {
756 return visibility;
757 }
758
759 /****************************
760 * Destructively get the error message from the last constraint evaluation
761 * Params:
762 * tip = tip to show after printing all overloads
763 */
764 const(char)* getConstraintEvalError(ref const(char)* tip)
765 {
766 import dmd.staticcond;
767
768 // there will be a full tree view in verbose mode, and more compact list in the usual
769 const full = global.params.v.verbose;
770 uint count;
771 const msg = visualizeStaticCondition(constraint, lastConstraint, lastConstraintNegs[], full, count);
772 scope (exit)
773 {
774 lastConstraint = null;
775 lastConstraintTiargs = null;
776 lastConstraintNegs.setDim(0);
777 }
778 if (!msg)
779 return null;
780
781 OutBuffer buf;
782
783 assert(parameters && lastConstraintTiargs);
784 if (parameters.length > 0)
785 {
786 formatParamsWithTiargs(*parameters, *lastConstraintTiargs, isVariadic() !is null, buf);
787 buf.writenl();
788 }
789 if (!full)
790 {
791 // choosing singular/plural
792 const s = (count == 1) ?
793 " must satisfy the following constraint:" :
794 " must satisfy one of the following constraints:";
795 buf.writestring(s);
796 buf.writenl();
797 // the constraints
798 buf.writeByte('`');
799 buf.writestring(msg);
800 buf.writeByte('`');
801 }
802 else
803 {
804 buf.writestring(" whose parameters have the following constraints:");
805 buf.writenl();
806 const sep = " `~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`";
807 buf.writestring(sep);
808 buf.writenl();
809 // the constraints
810 buf.writeByte('`');
811 buf.writestring(msg);
812 buf.writeByte('`');
813 buf.writestring(sep);
814 tip = "not satisfied constraints are marked with `>`";
815 }
816 return buf.extractChars();
817 }
818
819 debug (FindExistingInstance)
820 {
821 __gshared uint nFound, nNotFound, nAdded, nRemoved;
822
823 shared static ~this()
824 {
825 printf("debug (FindExistingInstance) nFound %u, nNotFound: %u, nAdded: %u, nRemoved: %u\n",
826 nFound, nNotFound, nAdded, nRemoved);
827 }
828 }
829
830 /****************************************************
831 * Given a new instance `tithis` of this TemplateDeclaration,
832 * see if there already exists an instance.
833 *
834 * Params:
835 * tithis = template instance to check
836 * argumentList = For function templates, needed because different
837 * `auto ref` resolutions create different instances,
838 * even when template parameters are identical
839 *
840 * Returns: that existing instance, or `null` when it doesn't exist
841 */
842 extern (D) TemplateInstance findExistingInstance(TemplateInstance tithis, ArgumentList argumentList)
843 {
844 //printf("findExistingInstance() %s\n", tithis.toChars());
845 tithis.fargs = argumentList.arguments;
846 tithis.fnames = argumentList.names;
847 auto tibox = TemplateInstanceBox(tithis);
848 auto p = tibox in this.instances;
849 debug (FindExistingInstance) ++(p ? nFound : nNotFound);
850 //if (p) printf("\tfound %p\n", *p); else printf("\tnot found\n");
851 return p ? *p : null;
852 }
853
854 /********************************************
855 * Add instance ti to TemplateDeclaration's table of instances.
856 * Return a handle we can use to later remove it if it fails instantiation.
857 */
858 extern (D) TemplateInstance addInstance(TemplateInstance ti)
859 {
860 //printf("addInstance() %p %s\n", instances, ti.toChars());
861 auto tibox = TemplateInstanceBox(ti);
862 instances[tibox] = ti;
863 debug (FindExistingInstance) ++nAdded;
864 return ti;
865 }
866
867 /*******************************************
868 * Remove TemplateInstance from table of instances.
869 * Input:
870 * handle returned by addInstance()
871 */
872 extern (D) void removeInstance(TemplateInstance ti)
873 {
874 //printf("removeInstance() %s\n", ti.toChars());
875 auto tibox = TemplateInstanceBox(ti);
876 debug (FindExistingInstance) ++nRemoved;
877 instances.remove(tibox);
878 }
879
880 override inout(TemplateDeclaration) isTemplateDeclaration() inout
881 {
882 return this;
883 }
884
885 /**
886 * Check if the last template parameter is a tuple one,
887 * and returns it if so, else returns `null`.
888 *
889 * Returns:
890 * The last template parameter if it's a `TemplateTupleParameter`
891 */
892 extern (D) TemplateTupleParameter isVariadic()
893 {
894 size_t dim = parameters.length;
895 if (dim == 0)
896 return null;
897 return (*parameters)[dim - 1].isTemplateTupleParameter();
898 }
899
900 extern(C++) override bool isDeprecated() const
901 {
902 return this.deprecated_;
903 }
904
905 /***********************************
906 * We can overload templates.
907 */
908 override bool isOverloadable() const
909 {
910 return true;
911 }
912
913 override void accept(Visitor v)
914 {
915 v.visit(this);
916 }
917 }
918
919 extern (C++) final class TypeDeduced : Type
920 {
921 Type tded;
922 Expressions argexps; // corresponding expressions
923 Types tparams; // tparams[i].mod
924
925 extern (D) this(Type tt, Expression e, Type tparam)
926 {
927 super(Tnone);
928 tded = tt;
929 argexps.push(e);
930 tparams.push(tparam);
931 }
932
933 void update(Expression e, Type tparam)
934 {
935 argexps.push(e);
936 tparams.push(tparam);
937 }
938
939 void update(Type tt, Expression e, Type tparam)
940 {
941 tded = tt;
942 argexps.push(e);
943 tparams.push(tparam);
944 }
945
946 MATCH matchAll(Type tt)
947 {
948 MATCH match = MATCH.exact;
949 foreach (j, e; argexps)
950 {
951 assert(e);
952 if (e == emptyArrayElement)
953 continue;
954
955 Type t = tt.addMod(tparams[j].mod).substWildTo(MODFlags.const_);
956
957 MATCH m = e.implicitConvTo(t);
958 if (match > m)
959 match = m;
960 if (match == MATCH.nomatch)
961 break;
962 }
963 return match;
964 }
965 }
966
967
968 /* ======================== Type ============================================ */
969
970 /****
971 * Given an identifier, figure out which TemplateParameter it is.
972 * Return IDX_NOTFOUND if not found.
973 */
974 private size_t templateIdentifierLookup(Identifier id, TemplateParameters* parameters)
975 {
976 for (size_t i = 0; i < parameters.length; i++)
977 {
978 TemplateParameter tp = (*parameters)[i];
979 if (tp.ident.equals(id))
980 return i;
981 }
982 return IDX_NOTFOUND;
983 }
984
985 size_t templateParameterLookup(Type tparam, TemplateParameters* parameters)
986 {
987 if (TypeIdentifier tident = tparam.isTypeIdentifier())
988 {
989 //printf("\ttident = '%s'\n", tident.toChars());
990 return templateIdentifierLookup(tident.ident, parameters);
991 }
992 return IDX_NOTFOUND;
993 }
994
995 ubyte deduceWildHelper(Type t, Type* at, Type tparam)
996 {
997 if ((tparam.mod & MODFlags.wild) == 0)
998 return 0;
999
1000 *at = null;
1001
1002 auto X(T, U)(T U, U T)
1003 {
1004 return (U << 4) | T;
1005 }
1006
1007 switch (X(tparam.mod, t.mod))
1008 {
1009 case X(MODFlags.wild, 0):
1010 case X(MODFlags.wild, MODFlags.const_):
1011 case X(MODFlags.wild, MODFlags.shared_):
1012 case X(MODFlags.wild, MODFlags.shared_ | MODFlags.const_):
1013 case X(MODFlags.wild, MODFlags.immutable_):
1014 case X(MODFlags.wildconst, 0):
1015 case X(MODFlags.wildconst, MODFlags.const_):
1016 case X(MODFlags.wildconst, MODFlags.shared_):
1017 case X(MODFlags.wildconst, MODFlags.shared_ | MODFlags.const_):
1018 case X(MODFlags.wildconst, MODFlags.immutable_):
1019 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_):
1020 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_ | MODFlags.const_):
1021 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.immutable_):
1022 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_):
1023 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_ | MODFlags.const_):
1024 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.immutable_):
1025 {
1026 ubyte wm = (t.mod & ~MODFlags.shared_);
1027 if (wm == 0)
1028 wm = MODFlags.mutable;
1029 ubyte m = (t.mod & (MODFlags.const_ | MODFlags.immutable_)) | (tparam.mod & t.mod & MODFlags.shared_);
1030 *at = t.unqualify(m);
1031 return wm;
1032 }
1033 case X(MODFlags.wild, MODFlags.wild):
1034 case X(MODFlags.wild, MODFlags.wildconst):
1035 case X(MODFlags.wild, MODFlags.shared_ | MODFlags.wild):
1036 case X(MODFlags.wild, MODFlags.shared_ | MODFlags.wildconst):
1037 case X(MODFlags.wildconst, MODFlags.wild):
1038 case X(MODFlags.wildconst, MODFlags.wildconst):
1039 case X(MODFlags.wildconst, MODFlags.shared_ | MODFlags.wild):
1040 case X(MODFlags.wildconst, MODFlags.shared_ | MODFlags.wildconst):
1041 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_ | MODFlags.wild):
1042 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_ | MODFlags.wildconst):
1043 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_ | MODFlags.wild):
1044 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_ | MODFlags.wildconst):
1045 {
1046 *at = t.unqualify(tparam.mod & t.mod);
1047 return MODFlags.wild;
1048 }
1049 default:
1050 return 0;
1051 }
1052 }
1053
1054 /**
1055 * Returns the common type of the 2 types.
1056 */
1057 private Type rawTypeMerge(Type t1, Type t2)
1058 {
1059 if (t1.equals(t2))
1060 return t1;
1061 if (t1.equivalent(t2))
1062 return t1.castMod(MODmerge(t1.mod, t2.mod));
1063
1064 auto t1b = t1.toBasetype();
1065 auto t2b = t2.toBasetype();
1066 if (t1b.equals(t2b))
1067 return t1b;
1068 if (t1b.equivalent(t2b))
1069 return t1b.castMod(MODmerge(t1b.mod, t2b.mod));
1070
1071 auto ty = implicitConvCommonTy(t1b.ty, t2b.ty);
1072 if (ty != Terror)
1073 return Type.basic[ty];
1074
1075 return null;
1076 }
1077
1078 MATCH deduceTypeHelper(Type t, out Type at, Type tparam)
1079 {
1080 // 9*9 == 81 cases
1081
1082 auto X(T, U)(T U, U T)
1083 {
1084 return (U << 4) | T;
1085 }
1086
1087 switch (X(tparam.mod, t.mod))
1088 {
1089 case X(0, 0):
1090 case X(0, MODFlags.const_):
1091 case X(0, MODFlags.wild):
1092 case X(0, MODFlags.wildconst):
1093 case X(0, MODFlags.shared_):
1094 case X(0, MODFlags.shared_ | MODFlags.const_):
1095 case X(0, MODFlags.shared_ | MODFlags.wild):
1096 case X(0, MODFlags.shared_ | MODFlags.wildconst):
1097 case X(0, MODFlags.immutable_):
1098 // foo(U) T => T
1099 // foo(U) const(T) => const(T)
1100 // foo(U) inout(T) => inout(T)
1101 // foo(U) inout(const(T)) => inout(const(T))
1102 // foo(U) shared(T) => shared(T)
1103 // foo(U) shared(const(T)) => shared(const(T))
1104 // foo(U) shared(inout(T)) => shared(inout(T))
1105 // foo(U) shared(inout(const(T))) => shared(inout(const(T)))
1106 // foo(U) immutable(T) => immutable(T)
1107 {
1108 at = t;
1109 return MATCH.exact;
1110 }
1111 case X(MODFlags.const_, MODFlags.const_):
1112 case X(MODFlags.wild, MODFlags.wild):
1113 case X(MODFlags.wildconst, MODFlags.wildconst):
1114 case X(MODFlags.shared_, MODFlags.shared_):
1115 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.shared_ | MODFlags.const_):
1116 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_ | MODFlags.wild):
1117 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_ | MODFlags.wildconst):
1118 case X(MODFlags.immutable_, MODFlags.immutable_):
1119 // foo(const(U)) const(T) => T
1120 // foo(inout(U)) inout(T) => T
1121 // foo(inout(const(U))) inout(const(T)) => T
1122 // foo(shared(U)) shared(T) => T
1123 // foo(shared(const(U))) shared(const(T)) => T
1124 // foo(shared(inout(U))) shared(inout(T)) => T
1125 // foo(shared(inout(const(U)))) shared(inout(const(T))) => T
1126 // foo(immutable(U)) immutable(T) => T
1127 {
1128 at = t.mutableOf().unSharedOf();
1129 return MATCH.exact;
1130 }
1131 case X(MODFlags.const_, MODFlags.shared_ | MODFlags.const_):
1132 case X(MODFlags.wild, MODFlags.shared_ | MODFlags.wild):
1133 case X(MODFlags.wildconst, MODFlags.shared_ | MODFlags.wildconst):
1134 // foo(const(U)) shared(const(T)) => shared(T)
1135 // foo(inout(U)) shared(inout(T)) => shared(T)
1136 // foo(inout(const(U))) shared(inout(const(T))) => shared(T)
1137 {
1138 at = t.mutableOf();
1139 return MATCH.exact;
1140 }
1141 case X(MODFlags.const_, 0):
1142 case X(MODFlags.const_, MODFlags.wild):
1143 case X(MODFlags.const_, MODFlags.wildconst):
1144 case X(MODFlags.const_, MODFlags.shared_ | MODFlags.wild):
1145 case X(MODFlags.const_, MODFlags.shared_ | MODFlags.wildconst):
1146 case X(MODFlags.const_, MODFlags.immutable_):
1147 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.immutable_):
1148 // foo(const(U)) T => T
1149 // foo(const(U)) inout(T) => T
1150 // foo(const(U)) inout(const(T)) => T
1151 // foo(const(U)) shared(inout(T)) => shared(T)
1152 // foo(const(U)) shared(inout(const(T))) => shared(T)
1153 // foo(const(U)) immutable(T) => T
1154 // foo(shared(const(U))) immutable(T) => T
1155 {
1156 at = t.mutableOf();
1157 return MATCH.constant;
1158 }
1159 case X(MODFlags.const_, MODFlags.shared_):
1160 // foo(const(U)) shared(T) => shared(T)
1161 {
1162 at = t;
1163 return MATCH.constant;
1164 }
1165 case X(MODFlags.shared_, MODFlags.shared_ | MODFlags.const_):
1166 case X(MODFlags.shared_, MODFlags.shared_ | MODFlags.wild):
1167 case X(MODFlags.shared_, MODFlags.shared_ | MODFlags.wildconst):
1168 // foo(shared(U)) shared(const(T)) => const(T)
1169 // foo(shared(U)) shared(inout(T)) => inout(T)
1170 // foo(shared(U)) shared(inout(const(T))) => inout(const(T))
1171 {
1172 at = t.unSharedOf();
1173 return MATCH.exact;
1174 }
1175 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.shared_):
1176 // foo(shared(const(U))) shared(T) => T
1177 {
1178 at = t.unSharedOf();
1179 return MATCH.constant;
1180 }
1181 case X(MODFlags.wildconst, MODFlags.immutable_):
1182 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.shared_ | MODFlags.wildconst):
1183 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.immutable_):
1184 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_ | MODFlags.wild):
1185 // foo(inout(const(U))) immutable(T) => T
1186 // foo(shared(const(U))) shared(inout(const(T))) => T
1187 // foo(shared(inout(const(U)))) immutable(T) => T
1188 // foo(shared(inout(const(U)))) shared(inout(T)) => T
1189 {
1190 at = t.unSharedOf().mutableOf();
1191 return MATCH.constant;
1192 }
1193 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.shared_ | MODFlags.wild):
1194 // foo(shared(const(U))) shared(inout(T)) => T
1195 {
1196 at = t.unSharedOf().mutableOf();
1197 return MATCH.constant;
1198 }
1199 case X(MODFlags.wild, 0):
1200 case X(MODFlags.wild, MODFlags.const_):
1201 case X(MODFlags.wild, MODFlags.wildconst):
1202 case X(MODFlags.wild, MODFlags.immutable_):
1203 case X(MODFlags.wild, MODFlags.shared_):
1204 case X(MODFlags.wild, MODFlags.shared_ | MODFlags.const_):
1205 case X(MODFlags.wild, MODFlags.shared_ | MODFlags.wildconst):
1206 case X(MODFlags.wildconst, 0):
1207 case X(MODFlags.wildconst, MODFlags.const_):
1208 case X(MODFlags.wildconst, MODFlags.wild):
1209 case X(MODFlags.wildconst, MODFlags.shared_):
1210 case X(MODFlags.wildconst, MODFlags.shared_ | MODFlags.const_):
1211 case X(MODFlags.wildconst, MODFlags.shared_ | MODFlags.wild):
1212 case X(MODFlags.shared_, 0):
1213 case X(MODFlags.shared_, MODFlags.const_):
1214 case X(MODFlags.shared_, MODFlags.wild):
1215 case X(MODFlags.shared_, MODFlags.wildconst):
1216 case X(MODFlags.shared_, MODFlags.immutable_):
1217 case X(MODFlags.shared_ | MODFlags.const_, 0):
1218 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.const_):
1219 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.wild):
1220 case X(MODFlags.shared_ | MODFlags.const_, MODFlags.wildconst):
1221 case X(MODFlags.shared_ | MODFlags.wild, 0):
1222 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.const_):
1223 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.wild):
1224 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.wildconst):
1225 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.immutable_):
1226 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_):
1227 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_ | MODFlags.const_):
1228 case X(MODFlags.shared_ | MODFlags.wild, MODFlags.shared_ | MODFlags.wildconst):
1229 case X(MODFlags.shared_ | MODFlags.wildconst, 0):
1230 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.const_):
1231 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.wild):
1232 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.wildconst):
1233 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_):
1234 case X(MODFlags.shared_ | MODFlags.wildconst, MODFlags.shared_ | MODFlags.const_):
1235 case X(MODFlags.immutable_, 0):
1236 case X(MODFlags.immutable_, MODFlags.const_):
1237 case X(MODFlags.immutable_, MODFlags.wild):
1238 case X(MODFlags.immutable_, MODFlags.wildconst):
1239 case X(MODFlags.immutable_, MODFlags.shared_):
1240 case X(MODFlags.immutable_, MODFlags.shared_ | MODFlags.const_):
1241 case X(MODFlags.immutable_, MODFlags.shared_ | MODFlags.wild):
1242 case X(MODFlags.immutable_, MODFlags.shared_ | MODFlags.wildconst):
1243 // foo(inout(U)) T => nomatch
1244 // foo(inout(U)) const(T) => nomatch
1245 // foo(inout(U)) inout(const(T)) => nomatch
1246 // foo(inout(U)) immutable(T) => nomatch
1247 // foo(inout(U)) shared(T) => nomatch
1248 // foo(inout(U)) shared(const(T)) => nomatch
1249 // foo(inout(U)) shared(inout(const(T))) => nomatch
1250 // foo(inout(const(U))) T => nomatch
1251 // foo(inout(const(U))) const(T) => nomatch
1252 // foo(inout(const(U))) inout(T) => nomatch
1253 // foo(inout(const(U))) shared(T) => nomatch
1254 // foo(inout(const(U))) shared(const(T)) => nomatch
1255 // foo(inout(const(U))) shared(inout(T)) => nomatch
1256 // foo(shared(U)) T => nomatch
1257 // foo(shared(U)) const(T) => nomatch
1258 // foo(shared(U)) inout(T) => nomatch
1259 // foo(shared(U)) inout(const(T)) => nomatch
1260 // foo(shared(U)) immutable(T) => nomatch
1261 // foo(shared(const(U))) T => nomatch
1262 // foo(shared(const(U))) const(T) => nomatch
1263 // foo(shared(const(U))) inout(T) => nomatch
1264 // foo(shared(const(U))) inout(const(T)) => nomatch
1265 // foo(shared(inout(U))) T => nomatch
1266 // foo(shared(inout(U))) const(T) => nomatch
1267 // foo(shared(inout(U))) inout(T) => nomatch
1268 // foo(shared(inout(U))) inout(const(T)) => nomatch
1269 // foo(shared(inout(U))) immutable(T) => nomatch
1270 // foo(shared(inout(U))) shared(T) => nomatch
1271 // foo(shared(inout(U))) shared(const(T)) => nomatch
1272 // foo(shared(inout(U))) shared(inout(const(T))) => nomatch
1273 // foo(shared(inout(const(U)))) T => nomatch
1274 // foo(shared(inout(const(U)))) const(T) => nomatch
1275 // foo(shared(inout(const(U)))) inout(T) => nomatch
1276 // foo(shared(inout(const(U)))) inout(const(T)) => nomatch
1277 // foo(shared(inout(const(U)))) shared(T) => nomatch
1278 // foo(shared(inout(const(U)))) shared(const(T)) => nomatch
1279 // foo(immutable(U)) T => nomatch
1280 // foo(immutable(U)) const(T) => nomatch
1281 // foo(immutable(U)) inout(T) => nomatch
1282 // foo(immutable(U)) inout(const(T)) => nomatch
1283 // foo(immutable(U)) shared(T) => nomatch
1284 // foo(immutable(U)) shared(const(T)) => nomatch
1285 // foo(immutable(U)) shared(inout(T)) => nomatch
1286 // foo(immutable(U)) shared(inout(const(T))) => nomatch
1287 return MATCH.nomatch;
1288
1289 default:
1290 assert(0);
1291 }
1292 }
1293
1294 __gshared Expression emptyArrayElement = null;
1295
1296 /* These form the heart of template argument deduction.
1297 * Given 'this' being the type argument to the template instance,
1298 * it is matched against the template declaration parameter specialization
1299 * 'tparam' to determine the type to be used for the parameter.
1300 * Example:
1301 * template Foo(T:T*) // template declaration
1302 * Foo!(int*) // template instantiation
1303 * Input:
1304 * this = int*
1305 * tparam = T*
1306 * parameters = [ T:T* ] // Array of TemplateParameter's
1307 * Output:
1308 * dedtypes = [ int ] // Array of Expression/Type's
1309 */
1310 MATCH deduceType(RootObject o, Scope* sc, Type tparam, ref TemplateParameters parameters, ref Objects dedtypes, uint* wm = null, size_t inferStart = 0, bool ignoreAliasThis = false)
1311 {
1312 extern (C++) final class DeduceType : Visitor
1313 {
1314 alias visit = Visitor.visit;
1315 public:
1316 MATCH result;
1317
1318 extern (D) this() @safe
1319 {
1320 result = MATCH.nomatch;
1321 }
1322
1323 override void visit(Type t)
1324 {
1325 if (!tparam)
1326 goto Lnomatch;
1327
1328 if (t == tparam)
1329 goto Lexact;
1330
1331 if (tparam.ty == Tident)
1332 {
1333 // Determine which parameter tparam is
1334 size_t i = templateParameterLookup(tparam, &parameters);
1335 if (i == IDX_NOTFOUND)
1336 {
1337 if (!sc)
1338 goto Lnomatch;
1339
1340 /* Need a loc to go with the semantic routine.
1341 */
1342 Loc loc;
1343 if (parameters.length)
1344 {
1345 TemplateParameter tp = parameters[0];
1346 loc = tp.loc;
1347 }
1348
1349 /* BUG: what if tparam is a template instance, that
1350 * has as an argument another Tident?
1351 */
1352 tparam = tparam.typeSemantic(loc, sc);
1353 assert(tparam.ty != Tident);
1354 result = deduceType(t, sc, tparam, parameters, dedtypes, wm);
1355 return;
1356 }
1357
1358 TemplateParameter tp = parameters[i];
1359
1360 TypeIdentifier tident = tparam.isTypeIdentifier();
1361 if (tident.idents.length > 0)
1362 {
1363 //printf("matching %s to %s\n", tparam.toChars(), t.toChars());
1364 Dsymbol s = t.toDsymbol(sc);
1365 for (size_t j = tident.idents.length; j-- > 0;)
1366 {
1367 RootObject id = tident.idents[j];
1368 if (id.dyncast() == DYNCAST.identifier)
1369 {
1370 if (!s || !s.parent)
1371 goto Lnomatch;
1372 Dsymbol s2 = s.parent.search(Loc.initial, cast(Identifier)id);
1373 if (!s2)
1374 goto Lnomatch;
1375 s2 = s2.toAlias();
1376 //printf("[%d] s = %s %s, s2 = %s %s\n", j, s.kind(), s.toChars(), s2.kind(), s2.toChars());
1377 if (s != s2)
1378 {
1379 if (Type tx = s2.getType())
1380 {
1381 if (s != tx.toDsymbol(sc))
1382 goto Lnomatch;
1383 }
1384 else
1385 goto Lnomatch;
1386 }
1387 s = s.parent;
1388 }
1389 else
1390 goto Lnomatch;
1391 }
1392 //printf("[e] s = %s\n", s?s.toChars():"(null)");
1393 if (tp.isTemplateTypeParameter())
1394 {
1395 Type tt = s.getType();
1396 if (!tt)
1397 goto Lnomatch;
1398 Type at = cast(Type)dedtypes[i];
1399 if (at && at.ty == Tnone)
1400 at = (cast(TypeDeduced)at).tded;
1401 if (!at || tt.equals(at))
1402 {
1403 dedtypes[i] = tt;
1404 goto Lexact;
1405 }
1406 }
1407 if (tp.isTemplateAliasParameter())
1408 {
1409 Dsymbol s2 = cast(Dsymbol)dedtypes[i];
1410 if (!s2 || s == s2)
1411 {
1412 dedtypes[i] = s;
1413 goto Lexact;
1414 }
1415 }
1416 goto Lnomatch;
1417 }
1418
1419 // Found the corresponding parameter tp
1420 /+
1421 https://issues.dlang.org/show_bug.cgi?id=23578
1422 To pattern match:
1423 static if (is(S!int == S!av, alias av))
1424
1425 We eventually need to deduce `int` (Tint32 [0]) and `av` (Tident).
1426 Previously this would not get pattern matched at all, but now we check if the
1427 template parameter `av` came from.
1428
1429 This note has been left to serve as a hint for further explorers into
1430 how IsExp matching works.
1431 +/
1432 if (auto ta = tp.isTemplateAliasParameter())
1433 {
1434 dedtypes[i] = t;
1435 goto Lexact;
1436 }
1437 // (23578) - ensure previous behaviour for non-alias template params
1438 if (!tp.isTemplateTypeParameter())
1439 {
1440 goto Lnomatch;
1441 }
1442
1443 Type at = cast(Type)dedtypes[i];
1444 Type tt;
1445 if (ubyte wx = wm ? deduceWildHelper(t, &tt, tparam) : 0)
1446 {
1447 // type vs (none)
1448 if (!at)
1449 {
1450 dedtypes[i] = tt;
1451 *wm |= wx;
1452 result = MATCH.constant;
1453 return;
1454 }
1455
1456 // type vs expressions
1457 if (at.ty == Tnone)
1458 {
1459 auto xt = cast(TypeDeduced)at;
1460 result = xt.matchAll(tt);
1461 if (result > MATCH.nomatch)
1462 {
1463 dedtypes[i] = tt;
1464 if (result > MATCH.constant)
1465 result = MATCH.constant; // limit level for inout matches
1466 }
1467 return;
1468 }
1469
1470 // type vs type
1471 if (tt.equals(at))
1472 {
1473 dedtypes[i] = tt; // Prefer current type match
1474 goto Lconst;
1475 }
1476 if (tt.implicitConvTo(at.constOf()))
1477 {
1478 dedtypes[i] = at.constOf().mutableOf();
1479 *wm |= MODFlags.const_;
1480 goto Lconst;
1481 }
1482 if (at.implicitConvTo(tt.constOf()))
1483 {
1484 dedtypes[i] = tt.constOf().mutableOf();
1485 *wm |= MODFlags.const_;
1486 goto Lconst;
1487 }
1488 goto Lnomatch;
1489 }
1490 else if (MATCH m = deduceTypeHelper(t, tt, tparam))
1491 {
1492 // type vs (none)
1493 if (!at)
1494 {
1495 dedtypes[i] = tt;
1496 result = m;
1497 return;
1498 }
1499
1500 // type vs expressions
1501 if (at.ty == Tnone)
1502 {
1503 auto xt = cast(TypeDeduced)at;
1504 result = xt.matchAll(tt);
1505 if (result > MATCH.nomatch)
1506 {
1507 dedtypes[i] = tt;
1508 }
1509 return;
1510 }
1511
1512 // type vs type
1513 if (tt.equals(at))
1514 {
1515 goto Lexact;
1516 }
1517 if (tt.ty == Tclass && at.ty == Tclass)
1518 {
1519 result = tt.implicitConvTo(at);
1520 return;
1521 }
1522 if (tt.ty == Tsarray && at.ty == Tarray && tt.nextOf().implicitConvTo(at.nextOf()) >= MATCH.constant)
1523 {
1524 goto Lexact;
1525 }
1526 }
1527 goto Lnomatch;
1528 }
1529
1530 if (tparam.ty == Ttypeof)
1531 {
1532 /* Need a loc to go with the semantic routine.
1533 */
1534 Loc loc;
1535 if (parameters.length)
1536 {
1537 TemplateParameter tp = parameters[0];
1538 loc = tp.loc;
1539 }
1540
1541 tparam = tparam.typeSemantic(loc, sc);
1542 }
1543 if (t.ty != tparam.ty)
1544 {
1545 if (Dsymbol sym = t.toDsymbol(sc))
1546 {
1547 if (sym.isforwardRef() && !tparam.deco)
1548 goto Lnomatch;
1549 }
1550
1551 MATCH m = t.implicitConvTo(tparam);
1552 if (m == MATCH.nomatch && !ignoreAliasThis)
1553 {
1554 if (auto tc = t.isTypeClass())
1555 {
1556 if (tc.sym.aliasthis && !(tc.att & AliasThisRec.tracingDT))
1557 {
1558 if (auto ato = t.aliasthisOf())
1559 {
1560 tc.att = cast(AliasThisRec)(tc.att | AliasThisRec.tracingDT);
1561 m = deduceType(ato, sc, tparam, parameters, dedtypes, wm);
1562 tc.att = cast(AliasThisRec)(tc.att & ~AliasThisRec.tracingDT);
1563 }
1564 }
1565 }
1566 else if (auto ts = t.isTypeStruct())
1567 {
1568 if (ts.sym.aliasthis && !(ts.att & AliasThisRec.tracingDT))
1569 {
1570 if (auto ato = t.aliasthisOf())
1571 {
1572 ts.att = cast(AliasThisRec)(ts.att | AliasThisRec.tracingDT);
1573 m = deduceType(ato, sc, tparam, parameters, dedtypes, wm);
1574 ts.att = cast(AliasThisRec)(ts.att & ~AliasThisRec.tracingDT);
1575 }
1576 }
1577 }
1578 }
1579 result = m;
1580 return;
1581 }
1582
1583 if (t.nextOf())
1584 {
1585 if (tparam.deco && !tparam.hasWild())
1586 {
1587 result = t.implicitConvTo(tparam);
1588 return;
1589 }
1590
1591 Type tpn = tparam.nextOf();
1592 if (wm && t.ty == Taarray && tparam.isWild())
1593 {
1594 // https://issues.dlang.org/show_bug.cgi?id=12403
1595 // In IFTI, stop inout matching on transitive part of AA types.
1596 tpn = tpn.substWildTo(MODFlags.mutable);
1597 }
1598
1599 result = deduceType(t.nextOf(), sc, tpn, parameters, dedtypes, wm);
1600 return;
1601 }
1602
1603 Lexact:
1604 result = MATCH.exact;
1605 return;
1606
1607 Lnomatch:
1608 result = MATCH.nomatch;
1609 return;
1610
1611 Lconst:
1612 result = MATCH.constant;
1613 }
1614
1615 override void visit(TypeVector t)
1616 {
1617 if (auto tp = tparam.isTypeVector())
1618 {
1619 result = deduceType(t.basetype, sc, tp.basetype, parameters, dedtypes, wm);
1620 return;
1621 }
1622 visit(cast(Type)t);
1623 }
1624
1625 override void visit(TypeDArray t)
1626 {
1627 visit(cast(Type)t);
1628 }
1629
1630 override void visit(TypeSArray t)
1631 {
1632 // Extra check that array dimensions must match
1633 if (tparam)
1634 {
1635 if (tparam.ty == Tarray)
1636 {
1637 MATCH m = deduceType(t.next, sc, tparam.nextOf(), parameters, dedtypes, wm);
1638 result = (m >= MATCH.constant) ? MATCH.convert : MATCH.nomatch;
1639 return;
1640 }
1641
1642 TemplateParameter tp = null;
1643 Expression edim = null;
1644 size_t i;
1645 if (auto tsa = tparam.isTypeSArray())
1646 {
1647 if (tsa.dim.isVarExp() && tsa.dim.isVarExp().var.storage_class & STC.templateparameter)
1648 {
1649 Identifier id = tsa.dim.isVarExp().var.ident;
1650 i = templateIdentifierLookup(id, &parameters);
1651 assert(i != IDX_NOTFOUND);
1652 tp = parameters[i];
1653 }
1654 else
1655 edim = tsa.dim;
1656 }
1657 else if (auto taa = tparam.isTypeAArray())
1658 {
1659 i = templateParameterLookup(taa.index, &parameters);
1660 if (i != IDX_NOTFOUND)
1661 tp = parameters[i];
1662 else
1663 {
1664 Loc loc;
1665 // The "type" (it hasn't been resolved yet) of the function parameter
1666 // does not have a location but the parameter it is related to does,
1667 // so we use that for the resolution (better error message).
1668 if (inferStart < parameters.length)
1669 {
1670 TemplateParameter loctp = parameters[inferStart];
1671 loc = loctp.loc;
1672 }
1673
1674 Expression e;
1675 Type tx;
1676 Dsymbol s;
1677 taa.index.resolve(loc, sc, e, tx, s);
1678 edim = s ? getValue(s) : getValue(e);
1679 }
1680 }
1681 if (tp && tp.matchArg(sc, t.dim, i, &parameters, dedtypes, null) || edim && edim.toInteger() == t.dim.toInteger())
1682 {
1683 result = deduceType(t.next, sc, tparam.nextOf(), parameters, dedtypes, wm);
1684 return;
1685 }
1686 }
1687 visit(cast(Type)t);
1688 }
1689
1690 override void visit(TypeAArray t)
1691 {
1692 // Extra check that index type must match
1693 if (tparam && tparam.ty == Taarray)
1694 {
1695 TypeAArray tp = tparam.isTypeAArray();
1696 if (!deduceType(t.index, sc, tp.index, parameters, dedtypes))
1697 {
1698 result = MATCH.nomatch;
1699 return;
1700 }
1701 }
1702 visit(cast(Type)t);
1703 }
1704
1705 override void visit(TypeFunction t)
1706 {
1707 // Extra check that function characteristics must match
1708 if (!tparam)
1709 return visit(cast(Type)t);
1710
1711 if (auto tp = tparam.isTypeFunction())
1712 {
1713 if (t.parameterList.varargs != tp.parameterList.varargs || t.linkage != tp.linkage)
1714 {
1715 result = MATCH.nomatch;
1716 return;
1717 }
1718
1719 foreach (fparam; *tp.parameterList.parameters)
1720 {
1721 // https://issues.dlang.org/show_bug.cgi?id=2579
1722 // Apply function parameter storage classes to parameter types
1723 fparam.type = fparam.type.addStorageClass(fparam.storageClass);
1724 fparam.storageClass &= ~STC.TYPECTOR;
1725
1726 // https://issues.dlang.org/show_bug.cgi?id=15243
1727 // Resolve parameter type if it's not related with template parameters
1728 if (!reliesOnTemplateParameters(fparam.type, parameters[inferStart .. parameters.length]))
1729 {
1730 auto tx = fparam.type.typeSemantic(Loc.initial, sc);
1731 if (tx.ty == Terror)
1732 {
1733 result = MATCH.nomatch;
1734 return;
1735 }
1736 fparam.type = tx;
1737 }
1738 }
1739
1740 const size_t nfargs = t.parameterList.length;
1741 size_t nfparams = tp.parameterList.length;
1742
1743 /* See if tuple match
1744 */
1745 if (nfparams > 0 && nfargs >= nfparams - 1)
1746 {
1747 /* See if 'A' of the template parameter matches 'A'
1748 * of the type of the last function parameter.
1749 */
1750 Parameter fparam = tp.parameterList[nfparams - 1];
1751 assert(fparam);
1752 assert(fparam.type);
1753 if (fparam.type.ty != Tident)
1754 goto L1;
1755 TypeIdentifier tid = fparam.type.isTypeIdentifier();
1756 if (tid.idents.length)
1757 goto L1;
1758
1759 /* Look through parameters to find tuple matching tid.ident
1760 */
1761 size_t tupi = 0;
1762 for (; 1; tupi++)
1763 {
1764 if (tupi == parameters.length)
1765 goto L1;
1766 TemplateParameter tx = parameters[tupi];
1767 TemplateTupleParameter tup = tx.isTemplateTupleParameter();
1768 if (tup && tup.ident.equals(tid.ident))
1769 break;
1770 }
1771
1772 /* The types of the function arguments [nfparams - 1 .. nfargs]
1773 * now form the tuple argument.
1774 */
1775 size_t tuple_dim = nfargs - (nfparams - 1);
1776
1777 /* See if existing tuple, and whether it matches or not
1778 */
1779 RootObject o = dedtypes[tupi];
1780 if (o)
1781 {
1782 // Existing deduced argument must be a tuple, and must match
1783 Tuple tup = isTuple(o);
1784 if (!tup || tup.objects.length != tuple_dim)
1785 {
1786 result = MATCH.nomatch;
1787 return;
1788 }
1789 for (size_t i = 0; i < tuple_dim; i++)
1790 {
1791 Parameter arg = t.parameterList[nfparams - 1 + i];
1792 if (!arg.type.equals(tup.objects[i]))
1793 {
1794 result = MATCH.nomatch;
1795 return;
1796 }
1797 }
1798 }
1799 else
1800 {
1801 // Create new tuple
1802 auto tup = new Tuple(tuple_dim);
1803 for (size_t i = 0; i < tuple_dim; i++)
1804 {
1805 Parameter arg = t.parameterList[nfparams - 1 + i];
1806 tup.objects[i] = arg.type;
1807 }
1808 dedtypes[tupi] = tup;
1809 }
1810 nfparams--; // don't consider the last parameter for type deduction
1811 goto L2;
1812 }
1813
1814 L1:
1815 if (nfargs != nfparams)
1816 {
1817 result = MATCH.nomatch;
1818 return;
1819 }
1820 L2:
1821 assert(nfparams <= tp.parameterList.length);
1822 foreach (i, ap; tp.parameterList)
1823 {
1824 if (i == nfparams)
1825 break;
1826
1827 Parameter a = t.parameterList[i];
1828
1829 if (!a.isCovariant(t.isref, ap) ||
1830 !deduceType(a.type, sc, ap.type, parameters, dedtypes))
1831 {
1832 result = MATCH.nomatch;
1833 return;
1834 }
1835 }
1836 }
1837 visit(cast(Type)t);
1838 }
1839
1840 override void visit(TypeIdentifier t)
1841 {
1842 // Extra check
1843 if (tparam && tparam.ty == Tident)
1844 {
1845 TypeIdentifier tp = tparam.isTypeIdentifier();
1846 for (size_t i = 0; i < t.idents.length; i++)
1847 {
1848 RootObject id1 = t.idents[i];
1849 RootObject id2 = tp.idents[i];
1850 if (!id1.equals(id2))
1851 {
1852 result = MATCH.nomatch;
1853 return;
1854 }
1855 }
1856 }
1857 visit(cast(Type)t);
1858 }
1859
1860 override void visit(TypeInstance t)
1861 {
1862 // Extra check
1863 if (tparam && tparam.ty == Tinstance && t.tempinst.tempdecl)
1864 {
1865 TemplateDeclaration tempdecl = t.tempinst.tempdecl.isTemplateDeclaration();
1866 assert(tempdecl);
1867
1868 TypeInstance tp = tparam.isTypeInstance();
1869
1870 //printf("tempinst.tempdecl = %p\n", tempdecl);
1871 //printf("tp.tempinst.tempdecl = %p\n", tp.tempinst.tempdecl);
1872 if (!tp.tempinst.tempdecl)
1873 {
1874 //printf("tp.tempinst.name = '%s'\n", tp.tempinst.name.toChars());
1875
1876 /* Handle case of:
1877 * template Foo(T : sa!(T), alias sa)
1878 */
1879 size_t i = templateIdentifierLookup(tp.tempinst.name, &parameters);
1880 if (i == IDX_NOTFOUND)
1881 {
1882 /* Didn't find it as a parameter identifier. Try looking
1883 * it up and seeing if is an alias.
1884 * https://issues.dlang.org/show_bug.cgi?id=1454
1885 */
1886 auto tid = new TypeIdentifier(tp.loc, tp.tempinst.name);
1887 Type tx;
1888 Expression e;
1889 Dsymbol s;
1890 tid.resolve(tp.loc, sc, e, tx, s);
1891 if (tx)
1892 {
1893 s = tx.toDsymbol(sc);
1894 if (TemplateInstance ti = s ? s.parent.isTemplateInstance() : null)
1895 {
1896 // https://issues.dlang.org/show_bug.cgi?id=14290
1897 // Try to match with ti.tempecl,
1898 // only when ti is an enclosing instance.
1899 Dsymbol p = sc.parent;
1900 while (p && p != ti)
1901 p = p.parent;
1902 if (p)
1903 s = ti.tempdecl;
1904 }
1905 }
1906 if (s)
1907 {
1908 s = s.toAlias();
1909 TemplateDeclaration td = s.isTemplateDeclaration();
1910 if (td)
1911 {
1912 if (td.overroot)
1913 td = td.overroot;
1914 for (; td; td = td.overnext)
1915 {
1916 if (td == tempdecl)
1917 goto L2;
1918 }
1919 }
1920 }
1921 goto Lnomatch;
1922 }
1923
1924 TemplateParameter tpx = parameters[i];
1925 if (!tpx.matchArg(sc, tempdecl, i, &parameters, dedtypes, null))
1926 goto Lnomatch;
1927 }
1928 else if (tempdecl != tp.tempinst.tempdecl)
1929 goto Lnomatch;
1930
1931 L2:
1932 if (!resolveTemplateInstantiation(sc, &parameters, t.tempinst.tiargs, &t.tempinst.tdtypes, tempdecl, tp, &dedtypes))
1933 goto Lnomatch;
1934 }
1935 visit(cast(Type)t);
1936 return;
1937
1938 Lnomatch:
1939 //printf("no match\n");
1940 result = MATCH.nomatch;
1941 }
1942
1943 override void visit(TypeStruct t)
1944 {
1945 /* If this struct is a template struct, and we're matching
1946 * it against a template instance, convert the struct type
1947 * to a template instance, too, and try again.
1948 */
1949 TemplateInstance ti = t.sym.parent.isTemplateInstance();
1950
1951 if (tparam && tparam.ty == Tinstance)
1952 {
1953 if (ti && ti.toAlias() == t.sym)
1954 {
1955 auto tx = new TypeInstance(Loc.initial, ti);
1956 auto m = deduceType(tx, sc, tparam, parameters, dedtypes, wm);
1957 // if we have a no match we still need to check alias this
1958 if (m != MATCH.nomatch)
1959 {
1960 result = m;
1961 return;
1962 }
1963 }
1964
1965 /* Match things like:
1966 * S!(T).foo
1967 */
1968 TypeInstance tpi = tparam.isTypeInstance();
1969 if (tpi.idents.length)
1970 {
1971 RootObject id = tpi.idents[tpi.idents.length - 1];
1972 if (id.dyncast() == DYNCAST.identifier && t.sym.ident.equals(cast(Identifier)id))
1973 {
1974 Type tparent = t.sym.parent.getType();
1975 if (tparent)
1976 {
1977 /* Slice off the .foo in S!(T).foo
1978 */
1979 tpi.idents.length--;
1980 result = deduceType(tparent, sc, tpi, parameters, dedtypes, wm);
1981 tpi.idents.length++;
1982 return;
1983 }
1984 }
1985 }
1986 }
1987
1988 // Extra check
1989 if (tparam && tparam.ty == Tstruct)
1990 {
1991 TypeStruct tp = tparam.isTypeStruct();
1992
1993 //printf("\t%d\n", cast(MATCH) t.implicitConvTo(tp));
1994 if (wm && t.deduceWild(tparam, false))
1995 {
1996 result = MATCH.constant;
1997 return;
1998 }
1999 result = t.implicitConvTo(tp);
2000 return;
2001 }
2002 visit(cast(Type)t);
2003 }
2004
2005 override void visit(TypeEnum t)
2006 {
2007 // Extra check
2008 if (tparam && tparam.ty == Tenum)
2009 {
2010 TypeEnum tp = tparam.isTypeEnum();
2011 if (t.sym == tp.sym)
2012 visit(cast(Type)t);
2013 else
2014 result = MATCH.nomatch;
2015 return;
2016 }
2017 Type tb = t.toBasetype();
2018 if (tb.ty == tparam.ty || tb.ty == Tsarray && tparam.ty == Taarray)
2019 {
2020 result = deduceType(tb, sc, tparam, parameters, dedtypes, wm);
2021 if (result == MATCH.exact)
2022 result = MATCH.convert;
2023 return;
2024 }
2025 visit(cast(Type)t);
2026 }
2027
2028 override void visit(TypeClass t)
2029 {
2030 //printf("TypeClass.deduceType(this = %s)\n", t.toChars());
2031
2032 /* If this class is a template class, and we're matching
2033 * it against a template instance, convert the class type
2034 * to a template instance, too, and try again.
2035 */
2036 TemplateInstance ti = t.sym.parent.isTemplateInstance();
2037
2038 if (tparam && tparam.ty == Tinstance)
2039 {
2040 if (ti && ti.toAlias() == t.sym)
2041 {
2042 auto tx = new TypeInstance(Loc.initial, ti);
2043 MATCH m = deduceType(tx, sc, tparam, parameters, dedtypes, wm);
2044 // Even if the match fails, there is still a chance it could match
2045 // a base class.
2046 if (m != MATCH.nomatch)
2047 {
2048 result = m;
2049 return;
2050 }
2051 }
2052
2053 /* Match things like:
2054 * S!(T).foo
2055 */
2056 TypeInstance tpi = tparam.isTypeInstance();
2057 if (tpi.idents.length)
2058 {
2059 RootObject id = tpi.idents[tpi.idents.length - 1];
2060 if (id.dyncast() == DYNCAST.identifier && t.sym.ident.equals(cast(Identifier)id))
2061 {
2062 Type tparent = t.sym.parent.getType();
2063 if (tparent)
2064 {
2065 /* Slice off the .foo in S!(T).foo
2066 */
2067 tpi.idents.length--;
2068 result = deduceType(tparent, sc, tpi, parameters, dedtypes, wm);
2069 tpi.idents.length++;
2070 return;
2071 }
2072 }
2073 }
2074
2075 // If it matches exactly or via implicit conversion, we're done
2076 visit(cast(Type)t);
2077 if (result != MATCH.nomatch)
2078 return;
2079
2080 /* There is still a chance to match via implicit conversion to
2081 * a base class or interface. Because there could be more than one such
2082 * match, we need to check them all.
2083 */
2084
2085 int numBaseClassMatches = 0; // Have we found an interface match?
2086
2087 // Our best guess at dedtypes
2088 auto best = new Objects(dedtypes.length);
2089
2090 ClassDeclaration s = t.sym;
2091 while (s && s.baseclasses.length > 0)
2092 {
2093 // Test the base class
2094 deduceBaseClassParameters(*(*s.baseclasses)[0], sc, tparam, parameters, dedtypes, *best, numBaseClassMatches);
2095
2096 // Test the interfaces inherited by the base class
2097 foreach (b; s.interfaces)
2098 {
2099 deduceBaseClassParameters(*b, sc, tparam, parameters, dedtypes, *best, numBaseClassMatches);
2100 }
2101 s = (*s.baseclasses)[0].sym;
2102 }
2103
2104 if (numBaseClassMatches == 0)
2105 {
2106 result = MATCH.nomatch;
2107 return;
2108 }
2109
2110 // If we got at least one match, copy the known types into dedtypes
2111 memcpy(dedtypes.tdata(), best.tdata(), best.length * (void*).sizeof);
2112 result = MATCH.convert;
2113 return;
2114 }
2115
2116 // Extra check
2117 if (tparam && tparam.ty == Tclass)
2118 {
2119 TypeClass tp = tparam.isTypeClass();
2120
2121 //printf("\t%d\n", cast(MATCH) t.implicitConvTo(tp));
2122 if (wm && t.deduceWild(tparam, false))
2123 {
2124 result = MATCH.constant;
2125 return;
2126 }
2127 result = t.implicitConvTo(tp);
2128 return;
2129 }
2130 visit(cast(Type)t);
2131 }
2132
2133 override void visit(Expression e)
2134 {
2135 //printf("Expression.deduceType(e = %s)\n", e.toChars());
2136 size_t i = templateParameterLookup(tparam, &parameters);
2137 if (i == IDX_NOTFOUND || tparam.isTypeIdentifier().idents.length > 0)
2138 {
2139 if (e == emptyArrayElement && tparam.ty == Tarray)
2140 {
2141 Type tn = (cast(TypeNext)tparam).next;
2142 result = deduceType(emptyArrayElement, sc, tn, parameters, dedtypes, wm);
2143 return;
2144 }
2145 e.type.accept(this);
2146 return;
2147 }
2148
2149 TemplateTypeParameter tp = parameters[i].isTemplateTypeParameter();
2150 if (!tp)
2151 return; // nomatch
2152
2153 if (e == emptyArrayElement)
2154 {
2155 if (dedtypes[i])
2156 {
2157 result = MATCH.exact;
2158 return;
2159 }
2160 if (tp.defaultType)
2161 {
2162 tp.defaultType.accept(this);
2163 return;
2164 }
2165 }
2166
2167 /* Returns `true` if `t` is a reference type, or an array of reference types
2168 */
2169 bool isTopRef(Type t)
2170 {
2171 auto tb = t.baseElemOf();
2172 return tb.ty == Tclass ||
2173 tb.ty == Taarray ||
2174 tb.ty == Tstruct && tb.hasPointers();
2175 }
2176
2177 Type at = cast(Type)dedtypes[i];
2178 Type tt;
2179 if (ubyte wx = deduceWildHelper(e.type, &tt, tparam))
2180 {
2181 *wm |= wx;
2182 result = MATCH.constant;
2183 }
2184 else if (MATCH m = deduceTypeHelper(e.type, tt, tparam))
2185 {
2186 result = m;
2187 }
2188 else if (!isTopRef(e.type))
2189 {
2190 /* https://issues.dlang.org/show_bug.cgi?id=15653
2191 * In IFTI, recognize top-qualifier conversions
2192 * through the value copy, e.g.
2193 * int --> immutable(int)
2194 * immutable(string[]) --> immutable(string)[]
2195 */
2196 tt = e.type.mutableOf();
2197 result = MATCH.convert;
2198 }
2199 else
2200 return; // nomatch
2201
2202 // expression vs (none)
2203 if (!at)
2204 {
2205 dedtypes[i] = new TypeDeduced(tt, e, tparam);
2206 return;
2207 }
2208
2209 TypeDeduced xt = null;
2210 if (at.ty == Tnone)
2211 {
2212 xt = cast(TypeDeduced)at;
2213 at = xt.tded;
2214 }
2215
2216 // From previous matched expressions to current deduced type
2217 MATCH match1 = xt ? xt.matchAll(tt) : MATCH.nomatch;
2218
2219 // From current expressions to previous deduced type
2220 Type pt = at.addMod(tparam.mod);
2221 if (*wm)
2222 pt = pt.substWildTo(*wm);
2223 MATCH match2 = e.implicitConvTo(pt);
2224
2225 if (match1 > MATCH.nomatch && match2 > MATCH.nomatch)
2226 {
2227 if (at.implicitConvTo(tt) == MATCH.nomatch)
2228 match1 = MATCH.nomatch; // Prefer at
2229 else if (tt.implicitConvTo(at) == MATCH.nomatch)
2230 match2 = MATCH.nomatch; // Prefer tt
2231 else if (tt.isTypeBasic() && tt.ty == at.ty && tt.mod != at.mod)
2232 {
2233 if (!tt.isMutable() && !at.isMutable())
2234 tt = tt.mutableOf().addMod(MODmerge(tt.mod, at.mod));
2235 else if (tt.isMutable())
2236 {
2237 if (at.mod == 0) // Prefer unshared
2238 match1 = MATCH.nomatch;
2239 else
2240 match2 = MATCH.nomatch;
2241 }
2242 else if (at.isMutable())
2243 {
2244 if (tt.mod == 0) // Prefer unshared
2245 match2 = MATCH.nomatch;
2246 else
2247 match1 = MATCH.nomatch;
2248 }
2249 //printf("tt = %s, at = %s\n", tt.toChars(), at.toChars());
2250 }
2251 else
2252 {
2253 match1 = MATCH.nomatch;
2254 match2 = MATCH.nomatch;
2255 }
2256 }
2257 if (match1 > MATCH.nomatch)
2258 {
2259 // Prefer current match: tt
2260 if (xt)
2261 xt.update(tt, e, tparam);
2262 else
2263 dedtypes[i] = tt;
2264 result = match1;
2265 return;
2266 }
2267 if (match2 > MATCH.nomatch)
2268 {
2269 // Prefer previous match: (*dedtypes)[i]
2270 if (xt)
2271 xt.update(e, tparam);
2272 result = match2;
2273 return;
2274 }
2275
2276 /* Deduce common type
2277 */
2278 if (Type t = rawTypeMerge(at, tt))
2279 {
2280 if (xt)
2281 xt.update(t, e, tparam);
2282 else
2283 dedtypes[i] = t;
2284
2285 pt = tt.addMod(tparam.mod);
2286 if (*wm)
2287 pt = pt.substWildTo(*wm);
2288 result = e.implicitConvTo(pt);
2289 return;
2290 }
2291
2292 result = MATCH.nomatch;
2293 }
2294
2295 MATCH deduceEmptyArrayElement()
2296 {
2297 if (!emptyArrayElement)
2298 {
2299 emptyArrayElement = new IdentifierExp(Loc.initial, Id.p); // dummy
2300 emptyArrayElement.type = Type.tvoid;
2301 }
2302 assert(tparam.ty == Tarray);
2303
2304 Type tn = (cast(TypeNext)tparam).next;
2305 return deduceType(emptyArrayElement, sc, tn, parameters, dedtypes, wm);
2306 }
2307
2308 override void visit(NullExp e)
2309 {
2310 if (tparam.ty == Tarray && e.type.ty == Tnull)
2311 {
2312 // tparam:T[] <- e:null (void[])
2313 result = deduceEmptyArrayElement();
2314 return;
2315 }
2316 visit(cast(Expression)e);
2317 }
2318
2319 override void visit(StringExp e)
2320 {
2321 Type taai;
2322 if (e.type.ty == Tarray && (tparam.ty == Tsarray || tparam.ty == Taarray && (taai = (cast(TypeAArray)tparam).index).ty == Tident && (cast(TypeIdentifier)taai).idents.length == 0))
2323 {
2324 // Consider compile-time known boundaries
2325 e.type.nextOf().sarrayOf(e.len).accept(this);
2326 return;
2327 }
2328 visit(cast(Expression)e);
2329 }
2330
2331 override void visit(ArrayLiteralExp e)
2332 {
2333 // https://issues.dlang.org/show_bug.cgi?id=20092
2334 if (e.elements && e.elements.length && e.type.toBasetype().nextOf().ty == Tvoid)
2335 {
2336 result = deduceEmptyArrayElement();
2337 return;
2338 }
2339 if ((!e.elements || !e.elements.length) && e.type.toBasetype().nextOf().ty == Tvoid && tparam.ty == Tarray)
2340 {
2341 // tparam:T[] <- e:[] (void[])
2342 result = deduceEmptyArrayElement();
2343 return;
2344 }
2345
2346 if (tparam.ty == Tarray && e.elements && e.elements.length)
2347 {
2348 Type tn = (cast(TypeDArray)tparam).next;
2349 result = MATCH.exact;
2350 if (e.basis)
2351 {
2352 MATCH m = deduceType(e.basis, sc, tn, parameters, dedtypes, wm);
2353 if (m < result)
2354 result = m;
2355 }
2356 foreach (el; *e.elements)
2357 {
2358 if (result == MATCH.nomatch)
2359 break;
2360 if (!el)
2361 continue;
2362 MATCH m = deduceType(el, sc, tn, parameters, dedtypes, wm);
2363 if (m < result)
2364 result = m;
2365 }
2366 return;
2367 }
2368
2369 Type taai;
2370 if (e.type.ty == Tarray && (tparam.ty == Tsarray || tparam.ty == Taarray && (taai = (cast(TypeAArray)tparam).index).ty == Tident && (cast(TypeIdentifier)taai).idents.length == 0))
2371 {
2372 // Consider compile-time known boundaries
2373 e.type.nextOf().sarrayOf(e.elements.length).accept(this);
2374 return;
2375 }
2376 visit(cast(Expression)e);
2377 }
2378
2379 override void visit(AssocArrayLiteralExp e)
2380 {
2381 if (tparam.ty == Taarray && e.keys && e.keys.length)
2382 {
2383 TypeAArray taa = cast(TypeAArray)tparam;
2384 result = MATCH.exact;
2385 foreach (i, key; *e.keys)
2386 {
2387 MATCH m1 = deduceType(key, sc, taa.index, parameters, dedtypes, wm);
2388 if (m1 < result)
2389 result = m1;
2390 if (result == MATCH.nomatch)
2391 break;
2392 MATCH m2 = deduceType((*e.values)[i], sc, taa.next, parameters, dedtypes, wm);
2393 if (m2 < result)
2394 result = m2;
2395 if (result == MATCH.nomatch)
2396 break;
2397 }
2398 return;
2399 }
2400 visit(cast(Expression)e);
2401 }
2402
2403 override void visit(FuncExp e)
2404 {
2405 //printf("e.type = %s, tparam = %s\n", e.type.toChars(), tparam.toChars());
2406 if (e.td)
2407 {
2408 Type to = tparam;
2409 if (!to.nextOf())
2410 return;
2411 auto tof = to.nextOf().isTypeFunction();
2412 if (!tof)
2413 return;
2414
2415 // Parameter types inference from 'tof'
2416 assert(e.td._scope);
2417 TypeFunction tf = e.fd.type.isTypeFunction();
2418 //printf("\ttof = %s\n", tof.toChars());
2419 //printf("\ttf = %s\n", tf.toChars());
2420 const dim = tf.parameterList.length;
2421
2422 if (tof.parameterList.length != dim || tof.parameterList.varargs != tf.parameterList.varargs)
2423 return;
2424
2425 auto tiargs = new Objects();
2426 tiargs.reserve(e.td.parameters.length);
2427
2428 foreach (tp; *e.td.parameters)
2429 {
2430 size_t u = 0;
2431 foreach (i, p; tf.parameterList)
2432 {
2433 if (p.type.ty == Tident && (cast(TypeIdentifier)p.type).ident == tp.ident)
2434 break;
2435 ++u;
2436 }
2437 assert(u < dim);
2438 Parameter pto = tof.parameterList[u];
2439 if (!pto)
2440 break;
2441 Type t = pto.type.syntaxCopy(); // https://issues.dlang.org/show_bug.cgi?id=11774
2442 if (reliesOnTemplateParameters(t, parameters[inferStart .. parameters.length]))
2443 return;
2444 t = t.typeSemantic(e.loc, sc);
2445 if (t.ty == Terror)
2446 return;
2447 tiargs.push(t);
2448 }
2449
2450 // Set target of return type inference
2451 if (!tf.next && tof.next)
2452 e.fd.treq = tparam;
2453
2454 auto ti = new TemplateInstance(e.loc, e.td, tiargs);
2455 Expression ex = (new ScopeExp(e.loc, ti)).expressionSemantic(e.td._scope);
2456
2457 // Reset inference target for the later re-semantic
2458 e.fd.treq = null;
2459
2460 if (ex.op == EXP.error)
2461 return;
2462 if (ex.op != EXP.function_)
2463 return;
2464 visit(ex.type);
2465 return;
2466 }
2467
2468 Type t = e.type;
2469
2470 if (t.ty == Tdelegate && tparam.ty == Tpointer)
2471 return;
2472
2473 // Allow conversion from implicit function pointer to delegate
2474 if (e.tok == TOK.reserved && t.ty == Tpointer && tparam.ty == Tdelegate)
2475 {
2476 TypeFunction tf = t.nextOf().isTypeFunction();
2477 t = (new TypeDelegate(tf)).merge();
2478 }
2479 //printf("tparam = %s <= e.type = %s, t = %s\n", tparam.toChars(), e.type.toChars(), t.toChars());
2480 visit(t);
2481 }
2482
2483 override void visit(SliceExp e)
2484 {
2485 Type taai;
2486 if (e.type.ty == Tarray && (tparam.ty == Tsarray || tparam.ty == Taarray && (taai = (cast(TypeAArray)tparam).index).ty == Tident && (cast(TypeIdentifier)taai).idents.length == 0))
2487 {
2488 // Consider compile-time known boundaries
2489 if (Type tsa = toStaticArrayType(e))
2490 {
2491 tsa.accept(this);
2492 if (result > MATCH.convert)
2493 result = MATCH.convert; // match with implicit conversion at most
2494 return;
2495 }
2496 }
2497 visit(cast(Expression)e);
2498 }
2499
2500 override void visit(CommaExp e)
2501 {
2502 e.e2.accept(this);
2503 }
2504 }
2505
2506 scope DeduceType v = new DeduceType();
2507 if (Type t = isType(o))
2508 t.accept(v);
2509 else if (Expression e = isExpression(o))
2510 {
2511 assert(wm);
2512 e.accept(v);
2513 }
2514 else
2515 assert(0);
2516 return v.result;
2517 }
2518
2519
2520 /* Helper for TypeClass.deduceType().
2521 * Classes can match with implicit conversion to a base class or interface.
2522 * This is complicated, because there may be more than one base class which
2523 * matches. In such cases, one or more parameters remain ambiguous.
2524 * For example,
2525 *
2526 * interface I(X, Y) {}
2527 * class C : I(uint, double), I(char, double) {}
2528 * C x;
2529 * foo(T, U)( I!(T, U) x)
2530 *
2531 * deduces that U is double, but T remains ambiguous (could be char or uint).
2532 *
2533 * Given a baseclass b, and initial deduced types 'dedtypes', this function
2534 * tries to match tparam with b, and also tries all base interfaces of b.
2535 * If a match occurs, numBaseClassMatches is incremented, and the new deduced
2536 * types are ANDed with the current 'best' estimate for dedtypes.
2537 */
2538 private void deduceBaseClassParameters(ref BaseClass b, Scope* sc, Type tparam, ref TemplateParameters parameters, ref Objects dedtypes, ref Objects best, ref int numBaseClassMatches)
2539 {
2540 TemplateInstance parti = b.sym ? b.sym.parent.isTemplateInstance() : null;
2541 if (parti)
2542 {
2543 // Make a temporary copy of dedtypes so we don't destroy it
2544 auto tmpdedtypes = new Objects(dedtypes.length);
2545 memcpy(tmpdedtypes.tdata(), dedtypes.tdata(), dedtypes.length * (void*).sizeof);
2546
2547 auto t = new TypeInstance(Loc.initial, parti);
2548 MATCH m = deduceType(t, sc, tparam, parameters, *tmpdedtypes);
2549 if (m > MATCH.nomatch)
2550 {
2551 // If this is the first ever match, it becomes our best estimate
2552 if (numBaseClassMatches == 0)
2553 memcpy(best.tdata(), tmpdedtypes.tdata(), tmpdedtypes.length * (void*).sizeof);
2554 else
2555 for (size_t k = 0; k < tmpdedtypes.length; ++k)
2556 {
2557 // If we've found more than one possible type for a parameter,
2558 // mark it as unknown.
2559 if ((*tmpdedtypes)[k] != best[k])
2560 best[k] = dedtypes[k];
2561 }
2562 ++numBaseClassMatches;
2563 }
2564 }
2565
2566 // Now recursively test the inherited interfaces
2567 foreach (ref bi; b.baseInterfaces)
2568 {
2569 deduceBaseClassParameters(bi, sc, tparam, parameters, dedtypes, best, numBaseClassMatches);
2570 }
2571 }
2572
2573 /********************
2574 * Match template `parameters` to the target template instance.
2575 * Example:
2576 * struct Temp(U, int Z) {}
2577 * void foo(T)(Temp!(T, 3));
2578 * foo(Temp!(int, 3)());
2579 * Input:
2580 * sc = context
2581 * parameters = template params of foo -> [T]
2582 * tiargs = <Temp!(int, 3)>.tiargs -> [int, 3]
2583 * tdtypes = <Temp!(int, 3)>.tdtypes -> [int, 3]
2584 * tempdecl = <struct Temp!(T, int Z)> -> [T, Z]
2585 * tp = <Temp!(T, 3)>
2586 * Output:
2587 * dedtypes = deduced params of `foo(Temp!(int, 3)())` -> [int]
2588 */
2589 private bool resolveTemplateInstantiation(Scope* sc, TemplateParameters* parameters, Objects* tiargs, Objects* tdtypes, TemplateDeclaration tempdecl, TypeInstance tp, Objects* dedtypes)
2590 {
2591 for (size_t i = 0; 1; i++)
2592 {
2593 //printf("\ttest: tempinst.tiargs[%zu]\n", i);
2594 RootObject o1 = null;
2595 if (i < tiargs.length)
2596 o1 = (*tiargs)[i];
2597 else if (i < tdtypes.length && i < tp.tempinst.tiargs.length)
2598 {
2599 // Pick up default arg
2600 o1 = (*tdtypes)[i];
2601 }
2602 else if (i >= tp.tempinst.tiargs.length)
2603 break;
2604 //printf("\ttest: o1 = %s\n", o1.toChars());
2605 if (i >= tp.tempinst.tiargs.length)
2606 {
2607 size_t dim = tempdecl.parameters.length - (tempdecl.isVariadic() ? 1 : 0);
2608 while (i < dim && ((*tempdecl.parameters)[i].dependent || (*tempdecl.parameters)[i].hasDefaultArg()))
2609 {
2610 i++;
2611 }
2612 if (i >= dim)
2613 break; // match if all remained parameters are dependent
2614 return false;
2615 }
2616
2617 RootObject o2 = (*tp.tempinst.tiargs)[i];
2618 Type t2 = isType(o2);
2619 //printf("\ttest: o2 = %s\n", o2.toChars());
2620 size_t j = (t2 && t2.ty == Tident && i == tp.tempinst.tiargs.length - 1)
2621 ? templateParameterLookup(t2, parameters) : IDX_NOTFOUND;
2622 if (j != IDX_NOTFOUND && j == parameters.length - 1 &&
2623 (*parameters)[j].isTemplateTupleParameter())
2624 {
2625 /* Given:
2626 * struct A(B...) {}
2627 * alias A!(int, float) X;
2628 * static if (is(X Y == A!(Z), Z...)) {}
2629 * deduce that Z is a tuple(int, float)
2630 */
2631
2632 /* Create tuple from remaining args
2633 */
2634 size_t vtdim = (tempdecl.isVariadic() ? tiargs.length : tdtypes.length) - i;
2635 auto vt = new Tuple(vtdim);
2636 for (size_t k = 0; k < vtdim; k++)
2637 {
2638 RootObject o;
2639 if (k < tiargs.length)
2640 o = (*tiargs)[i + k];
2641 else // Pick up default arg
2642 o = (*tdtypes)[i + k];
2643 vt.objects[k] = o;
2644 }
2645
2646 Tuple v = cast(Tuple)(*dedtypes)[j];
2647 if (v)
2648 {
2649 if (!match(v, vt))
2650 return false;
2651 }
2652 else
2653 (*dedtypes)[j] = vt;
2654 break;
2655 }
2656 else if (!o1)
2657 break;
2658
2659 Type t1 = isType(o1);
2660 Dsymbol s1 = isDsymbol(o1);
2661 Dsymbol s2 = isDsymbol(o2);
2662 Expression e1 = s1 ? getValue(s1) : getValue(isExpression(o1));
2663 Expression e2 = isExpression(o2);
2664 version (none)
2665 {
2666 Tuple v1 = isTuple(o1);
2667 Tuple v2 = isTuple(o2);
2668 if (t1)
2669 printf("t1 = %s\n", t1.toChars());
2670 if (t2)
2671 printf("t2 = %s\n", t2.toChars());
2672 if (e1)
2673 printf("e1 = %s\n", e1.toChars());
2674 if (e2)
2675 printf("e2 = %s\n", e2.toChars());
2676 if (s1)
2677 printf("s1 = %s\n", s1.toChars());
2678 if (s2)
2679 printf("s2 = %s\n", s2.toChars());
2680 if (v1)
2681 printf("v1 = %s\n", v1.toChars());
2682 if (v2)
2683 printf("v2 = %s\n", v2.toChars());
2684 }
2685
2686 if (t1 && t2)
2687 {
2688 if (!deduceType(t1, sc, t2, *parameters, *dedtypes))
2689 return false;
2690 }
2691 else if (e1 && e2)
2692 {
2693 Le:
2694 e1 = e1.ctfeInterpret();
2695
2696 /* If it is one of the template parameters for this template,
2697 * we should not attempt to interpret it. It already has a value.
2698 */
2699 if (e2.op == EXP.variable && (e2.isVarExp().var.storage_class & STC.templateparameter))
2700 {
2701 /*
2702 * (T:Number!(e2), int e2)
2703 */
2704 j = templateIdentifierLookup(e2.isVarExp().var.ident, parameters);
2705 if (j != IDX_NOTFOUND)
2706 goto L1;
2707 // The template parameter was not from this template
2708 // (it may be from a parent template, for example)
2709 }
2710
2711 e2 = e2.expressionSemantic(sc); // https://issues.dlang.org/show_bug.cgi?id=13417
2712 e2 = e2.ctfeInterpret();
2713
2714 //printf("e1 = %s, type = %s %d\n", e1.toChars(), e1.type.toChars(), e1.type.ty);
2715 //printf("e2 = %s, type = %s %d\n", e2.toChars(), e2.type.toChars(), e2.type.ty);
2716 if (!e1.equals(e2))
2717 {
2718 if (!e2.implicitConvTo(e1.type))
2719 return false;
2720
2721 e2 = e2.implicitCastTo(sc, e1.type);
2722 e2 = e2.ctfeInterpret();
2723 if (!e1.equals(e2))
2724 return false;
2725 }
2726 }
2727 else if (e1 && t2 && t2.ty == Tident)
2728 {
2729 j = templateParameterLookup(t2, parameters);
2730 L1:
2731 if (j == IDX_NOTFOUND)
2732 {
2733 t2.resolve((cast(TypeIdentifier)t2).loc, sc, e2, t2, s2);
2734 if (e2)
2735 goto Le;
2736 return false;
2737 }
2738 if (!(*parameters)[j].matchArg(sc, e1, j, parameters, *dedtypes, null))
2739 return false;
2740 }
2741 else if (s1 && s2)
2742 {
2743 Ls:
2744 if (!s1.equals(s2))
2745 return false;
2746 }
2747 else if (s1 && t2 && t2.ty == Tident)
2748 {
2749 j = templateParameterLookup(t2, parameters);
2750 if (j == IDX_NOTFOUND)
2751 {
2752 t2.resolve((cast(TypeIdentifier)t2).loc, sc, e2, t2, s2);
2753 if (s2)
2754 goto Ls;
2755 return false;
2756 }
2757 if (!(*parameters)[j].matchArg(sc, s1, j, parameters, *dedtypes, null))
2758 return false;
2759 }
2760 else
2761 return false;
2762 }
2763 return true;
2764 }
2765
2766
2767 /***********************************************************
2768 * Check whether the type t representation relies on one or more the template parameters.
2769 * Params:
2770 * t = Tested type, if null, returns false.
2771 * tparams = Template parameters.
2772 * iStart = Start index of tparams to limit the tested parameters. If it's
2773 * nonzero, tparams[0..iStart] will be excluded from the test target.
2774 */
2775 bool reliesOnTident(Type t, TemplateParameters* tparams, size_t iStart = 0)
2776 {
2777 return reliesOnTemplateParameters(t, (*tparams)[0 .. tparams.length]);
2778 }
2779
2780 /***********************************************************
2781 * Check whether the type t representation relies on one or more the template parameters.
2782 * Params:
2783 * t = Tested type, if null, returns false.
2784 * tparams = Template parameters.
2785 */
2786 bool reliesOnTemplateParameters(Type t, TemplateParameter[] tparams)
2787 {
2788 bool visitVector(TypeVector t)
2789 {
2790 return t.basetype.reliesOnTemplateParameters(tparams);
2791 }
2792
2793 bool visitAArray(TypeAArray t)
2794 {
2795 return t.next.reliesOnTemplateParameters(tparams) ||
2796 t.index.reliesOnTemplateParameters(tparams);
2797 }
2798
2799 bool visitFunction(TypeFunction t)
2800 {
2801 foreach (i, fparam; t.parameterList)
2802 {
2803 if (fparam.type.reliesOnTemplateParameters(tparams))
2804 return true;
2805 }
2806 return t.next.reliesOnTemplateParameters(tparams);
2807 }
2808
2809 bool visitIdentifier(TypeIdentifier t)
2810 {
2811 foreach (tp; tparams)
2812 {
2813 if (tp.ident.equals(t.ident))
2814 return true;
2815 }
2816 return false;
2817 }
2818
2819 bool visitInstance(TypeInstance t)
2820 {
2821 foreach (tp; tparams)
2822 {
2823 if (t.tempinst.name == tp.ident)
2824 return true;
2825 }
2826
2827 if (t.tempinst.tiargs)
2828 foreach (arg; *t.tempinst.tiargs)
2829 {
2830 if (Type ta = isType(arg))
2831 {
2832 if (ta.reliesOnTemplateParameters(tparams))
2833 return true;
2834 }
2835 }
2836
2837 return false;
2838 }
2839
2840 bool visitTypeof(TypeTypeof t)
2841 {
2842 //printf("TypeTypeof.reliesOnTemplateParameters('%s')\n", t.toChars());
2843 return t.exp.reliesOnTemplateParameters(tparams);
2844 }
2845
2846 bool visitTuple(TypeTuple t)
2847 {
2848 if (t.arguments)
2849 foreach (arg; *t.arguments)
2850 {
2851 if (arg.type.reliesOnTemplateParameters(tparams))
2852 return true;
2853 }
2854
2855 return false;
2856 }
2857
2858 if (!t)
2859 return false;
2860
2861 Type tb = t.toBasetype();
2862 switch (tb.ty)
2863 {
2864 case Tvector: return visitVector(tb.isTypeVector());
2865 case Taarray: return visitAArray(tb.isTypeAArray());
2866 case Tfunction: return visitFunction(tb.isTypeFunction());
2867 case Tident: return visitIdentifier(tb.isTypeIdentifier());
2868 case Tinstance: return visitInstance(tb.isTypeInstance());
2869 case Ttypeof: return visitTypeof(tb.isTypeTypeof());
2870 case Ttuple: return visitTuple(tb.isTypeTuple());
2871 case Tenum: return false;
2872 default: return tb.nextOf().reliesOnTemplateParameters(tparams);
2873 }
2874 }
2875
2876 /***********************************************************
2877 * Check whether the expression representation relies on one or more the template parameters.
2878 * Params:
2879 * e = expression to test
2880 * tparams = Template parameters.
2881 * Returns:
2882 * true if it does
2883 */
2884 private bool reliesOnTemplateParameters(Expression e, TemplateParameter[] tparams)
2885 {
2886 extern (C++) final class ReliesOnTemplateParameters : Visitor
2887 {
2888 alias visit = Visitor.visit;
2889 public:
2890 TemplateParameter[] tparams;
2891 bool result;
2892
2893 extern (D) this(TemplateParameter[] tparams) @safe
2894 {
2895 this.tparams = tparams;
2896 }
2897
2898 override void visit(Expression e)
2899 {
2900 //printf("Expression.reliesOnTemplateParameters('%s')\n", e.toChars());
2901 }
2902
2903 override void visit(IdentifierExp e)
2904 {
2905 //printf("IdentifierExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2906 foreach (tp; tparams)
2907 {
2908 if (e.ident == tp.ident)
2909 {
2910 result = true;
2911 return;
2912 }
2913 }
2914 }
2915
2916 override void visit(TupleExp e)
2917 {
2918 //printf("TupleExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2919 if (e.exps)
2920 {
2921 foreach (ea; *e.exps)
2922 {
2923 ea.accept(this);
2924 if (result)
2925 return;
2926 }
2927 }
2928 }
2929
2930 override void visit(ArrayLiteralExp e)
2931 {
2932 //printf("ArrayLiteralExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2933 if (e.elements)
2934 {
2935 foreach (el; *e.elements)
2936 {
2937 el.accept(this);
2938 if (result)
2939 return;
2940 }
2941 }
2942 }
2943
2944 override void visit(AssocArrayLiteralExp e)
2945 {
2946 //printf("AssocArrayLiteralExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2947 foreach (ek; *e.keys)
2948 {
2949 ek.accept(this);
2950 if (result)
2951 return;
2952 }
2953 foreach (ev; *e.values)
2954 {
2955 ev.accept(this);
2956 if (result)
2957 return;
2958 }
2959 }
2960
2961 override void visit(StructLiteralExp e)
2962 {
2963 //printf("StructLiteralExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2964 if (e.elements)
2965 {
2966 foreach (ea; *e.elements)
2967 {
2968 ea.accept(this);
2969 if (result)
2970 return;
2971 }
2972 }
2973 }
2974
2975 override void visit(TypeExp e)
2976 {
2977 //printf("TypeExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2978 result = e.type.reliesOnTemplateParameters(tparams);
2979 }
2980
2981 override void visit(NewExp e)
2982 {
2983 //printf("NewExp.reliesOnTemplateParameters('%s')\n", e.toChars());
2984 if (e.thisexp)
2985 e.thisexp.accept(this);
2986 result = e.newtype.reliesOnTemplateParameters(tparams);
2987 if (!result && e.arguments)
2988 {
2989 foreach (ea; *e.arguments)
2990 {
2991 ea.accept(this);
2992 if (result)
2993 return;
2994 }
2995 }
2996 }
2997
2998 override void visit(NewAnonClassExp e)
2999 {
3000 //printf("NewAnonClassExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3001 result = true;
3002 }
3003
3004 override void visit(FuncExp e)
3005 {
3006 //printf("FuncExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3007 result = true;
3008 }
3009
3010 override void visit(TypeidExp e)
3011 {
3012 //printf("TypeidExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3013 if (auto ea = isExpression(e.obj))
3014 ea.accept(this);
3015 else if (auto ta = isType(e.obj))
3016 result = ta.reliesOnTemplateParameters(tparams);
3017 }
3018
3019 override void visit(TraitsExp e)
3020 {
3021 //printf("TraitsExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3022 if (e.args)
3023 {
3024 foreach (oa; *e.args)
3025 {
3026 if (auto ea = isExpression(oa))
3027 ea.accept(this);
3028 else if (auto ta = isType(oa))
3029 result = ta.reliesOnTemplateParameters(tparams);
3030 if (result)
3031 return;
3032 }
3033 }
3034 }
3035
3036 override void visit(IsExp e)
3037 {
3038 //printf("IsExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3039 result = e.targ.reliesOnTemplateParameters(tparams);
3040 }
3041
3042 override void visit(UnaExp e)
3043 {
3044 //printf("UnaExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3045 e.e1.accept(this);
3046 }
3047
3048 override void visit(DotTemplateInstanceExp e)
3049 {
3050 //printf("DotTemplateInstanceExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3051 visit(e.isUnaExp());
3052 if (!result && e.ti.tiargs)
3053 {
3054 foreach (oa; *e.ti.tiargs)
3055 {
3056 if (auto ea = isExpression(oa))
3057 ea.accept(this);
3058 else if (auto ta = isType(oa))
3059 result = ta.reliesOnTemplateParameters(tparams);
3060 if (result)
3061 return;
3062 }
3063 }
3064 }
3065
3066 override void visit(CallExp e)
3067 {
3068 //printf("CallExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3069 visit(e.isUnaExp());
3070 if (!result && e.arguments)
3071 {
3072 foreach (ea; *e.arguments)
3073 {
3074 ea.accept(this);
3075 if (result)
3076 return;
3077 }
3078 }
3079 }
3080
3081 override void visit(CastExp e)
3082 {
3083 //printf("CallExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3084 visit(e.isUnaExp());
3085 // e.to can be null for cast() with no type
3086 if (!result && e.to)
3087 result = e.to.reliesOnTemplateParameters(tparams);
3088 }
3089
3090 override void visit(SliceExp e)
3091 {
3092 //printf("SliceExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3093 visit(e.isUnaExp());
3094 if (!result && e.lwr)
3095 e.lwr.accept(this);
3096 if (!result && e.upr)
3097 e.upr.accept(this);
3098 }
3099
3100 override void visit(IntervalExp e)
3101 {
3102 //printf("IntervalExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3103 e.lwr.accept(this);
3104 if (!result)
3105 e.upr.accept(this);
3106 }
3107
3108 override void visit(ArrayExp e)
3109 {
3110 //printf("ArrayExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3111 visit(e.isUnaExp());
3112 if (!result && e.arguments)
3113 {
3114 foreach (ea; *e.arguments)
3115 ea.accept(this);
3116 }
3117 }
3118
3119 override void visit(BinExp e)
3120 {
3121 //printf("BinExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3122 e.e1.accept(this);
3123 if (!result)
3124 e.e2.accept(this);
3125 }
3126
3127 override void visit(CondExp e)
3128 {
3129 //printf("BinExp.reliesOnTemplateParameters('%s')\n", e.toChars());
3130 e.econd.accept(this);
3131 if (!result)
3132 visit(e.isBinExp());
3133 }
3134 }
3135
3136 scope ReliesOnTemplateParameters v = new ReliesOnTemplateParameters(tparams);
3137 e.accept(v);
3138 return v.result;
3139 }
3140
3141 /***********************************************************
3142 * https://dlang.org/spec/template.html#TemplateParameter
3143 */
3144 extern (C++) class TemplateParameter : ASTNode
3145 {
3146 Loc loc;
3147 Identifier ident;
3148
3149 /* True if this is a part of precedent parameter specialization pattern.
3150 *
3151 * template A(T : X!TL, alias X, TL...) {}
3152 * // X and TL are dependent template parameter
3153 *
3154 * A dependent template parameter should return MATCH.exact in matchArg()
3155 * to respect the match level of the corresponding precedent parameter.
3156 */
3157 bool dependent;
3158
3159 /* ======================== TemplateParameter =============================== */
3160 extern (D) this(const ref Loc loc, Identifier ident) @safe
3161 {
3162 this.loc = loc;
3163 this.ident = ident;
3164 }
3165
3166 TemplateTypeParameter isTemplateTypeParameter()
3167 {
3168 return null;
3169 }
3170
3171 TemplateValueParameter isTemplateValueParameter()
3172 {
3173 return null;
3174 }
3175
3176 TemplateAliasParameter isTemplateAliasParameter()
3177 {
3178 return null;
3179 }
3180
3181 TemplateThisParameter isTemplateThisParameter()
3182 {
3183 return null;
3184 }
3185
3186 TemplateTupleParameter isTemplateTupleParameter()
3187 {
3188 return null;
3189 }
3190
3191 abstract TemplateParameter syntaxCopy();
3192
3193 abstract bool declareParameter(Scope* sc);
3194
3195 abstract void print(RootObject oarg, RootObject oded);
3196
3197 abstract RootObject specialization();
3198
3199 abstract RootObject defaultArg(const ref Loc instLoc, Scope* sc);
3200
3201 abstract bool hasDefaultArg();
3202
3203 override const(char)* toChars() const
3204 {
3205 return this.ident.toChars();
3206 }
3207
3208 override DYNCAST dyncast() const
3209 {
3210 return DYNCAST.templateparameter;
3211 }
3212
3213 /* Create dummy argument based on parameter.
3214 */
3215 abstract RootObject dummyArg();
3216
3217 override void accept(Visitor v)
3218 {
3219 v.visit(this);
3220 }
3221 }
3222
3223 /***********************************************************
3224 * https://dlang.org/spec/template.html#TemplateTypeParameter
3225 * Syntax:
3226 * ident : specType = defaultType
3227 */
3228 extern (C++) class TemplateTypeParameter : TemplateParameter
3229 {
3230 Type specType; // if !=null, this is the type specialization
3231 Type defaultType;
3232
3233 extern (D) __gshared Type tdummy = null;
3234
3235 extern (D) this(const ref Loc loc, Identifier ident, Type specType, Type defaultType) @safe
3236 {
3237 super(loc, ident);
3238 this.specType = specType;
3239 this.defaultType = defaultType;
3240 }
3241
3242 override final TemplateTypeParameter isTemplateTypeParameter()
3243 {
3244 return this;
3245 }
3246
3247 override TemplateTypeParameter syntaxCopy()
3248 {
3249 return new TemplateTypeParameter(loc, ident, specType ? specType.syntaxCopy() : null, defaultType ? defaultType.syntaxCopy() : null);
3250 }
3251
3252 override final bool declareParameter(Scope* sc)
3253 {
3254 //printf("TemplateTypeParameter.declareParameter('%s')\n", ident.toChars());
3255 auto ti = new TypeIdentifier(loc, ident);
3256 Declaration ad = new AliasDeclaration(loc, ident, ti);
3257 return sc.insert(ad) !is null;
3258 }
3259
3260 override final void print(RootObject oarg, RootObject oded)
3261 {
3262 printf(" %s\n", ident.toChars());
3263
3264 Type t = isType(oarg);
3265 Type ta = isType(oded);
3266 assert(ta);
3267
3268 if (specType)
3269 printf("\tSpecialization: %s\n", specType.toChars());
3270 if (defaultType)
3271 printf("\tDefault: %s\n", defaultType.toChars());
3272 printf("\tParameter: %s\n", t ? t.toChars() : "NULL");
3273 printf("\tDeduced Type: %s\n", ta.toChars());
3274 }
3275
3276 override final RootObject specialization()
3277 {
3278 return specType;
3279 }
3280
3281 override final RootObject defaultArg(const ref Loc instLoc, Scope* sc)
3282 {
3283 Type t = defaultType;
3284 if (t)
3285 {
3286 t = t.syntaxCopy();
3287 t = t.typeSemantic(loc, sc); // use the parameter loc
3288 }
3289 return t;
3290 }
3291
3292 override final bool hasDefaultArg()
3293 {
3294 return defaultType !is null;
3295 }
3296
3297 override final RootObject dummyArg()
3298 {
3299 Type t = specType;
3300 if (!t)
3301 {
3302 // Use this for alias-parameter's too (?)
3303 if (!tdummy)
3304 tdummy = new TypeIdentifier(loc, ident);
3305 t = tdummy;
3306 }
3307 return t;
3308 }
3309
3310 override void accept(Visitor v)
3311 {
3312 v.visit(this);
3313 }
3314 }
3315
3316 /***********************************************************
3317 * https://dlang.org/spec/template.html#TemplateThisParameter
3318 * Syntax:
3319 * this ident : specType = defaultType
3320 */
3321 extern (C++) final class TemplateThisParameter : TemplateTypeParameter
3322 {
3323 extern (D) this(const ref Loc loc, Identifier ident, Type specType, Type defaultType) @safe
3324 {
3325 super(loc, ident, specType, defaultType);
3326 }
3327
3328 override TemplateThisParameter isTemplateThisParameter()
3329 {
3330 return this;
3331 }
3332
3333 override TemplateThisParameter syntaxCopy()
3334 {
3335 return new TemplateThisParameter(loc, ident, specType ? specType.syntaxCopy() : null, defaultType ? defaultType.syntaxCopy() : null);
3336 }
3337
3338 override void accept(Visitor v)
3339 {
3340 v.visit(this);
3341 }
3342 }
3343
3344 /***********************************************************
3345 * https://dlang.org/spec/template.html#TemplateValueParameter
3346 * Syntax:
3347 * valType ident : specValue = defaultValue
3348 */
3349 extern (C++) final class TemplateValueParameter : TemplateParameter
3350 {
3351 Type valType;
3352 Expression specValue;
3353 Expression defaultValue;
3354
3355 extern (D) __gshared Expression[void*] edummies;
3356
3357 extern (D) this(const ref Loc loc, Identifier ident, Type valType,
3358 Expression specValue, Expression defaultValue) @safe
3359 {
3360 super(loc, ident);
3361 this.valType = valType;
3362 this.specValue = specValue;
3363 this.defaultValue = defaultValue;
3364 }
3365
3366 override TemplateValueParameter isTemplateValueParameter()
3367 {
3368 return this;
3369 }
3370
3371 override TemplateValueParameter syntaxCopy()
3372 {
3373 return new TemplateValueParameter(loc, ident,
3374 valType.syntaxCopy(),
3375 specValue ? specValue.syntaxCopy() : null,
3376 defaultValue ? defaultValue.syntaxCopy() : null);
3377 }
3378
3379 override bool declareParameter(Scope* sc)
3380 {
3381 /*
3382 Do type semantic earlier.
3383
3384 This means for certain erroneous value parameters
3385 their "type" can be known earlier and thus a better
3386 error message given.
3387
3388 For example:
3389 `template test(x* x) {}`
3390 now yields "undefined identifier" rather than the opaque
3391 "variable `x` is used as a type".
3392 */
3393 if (valType)
3394 valType = valType.typeSemantic(loc, sc);
3395 auto v = new VarDeclaration(loc, valType, ident, null);
3396 v.storage_class = STC.templateparameter;
3397 return sc.insert(v) !is null;
3398 }
3399
3400 override void print(RootObject oarg, RootObject oded)
3401 {
3402 printf(" %s\n", ident.toChars());
3403 Expression ea = isExpression(oded);
3404 if (specValue)
3405 printf("\tSpecialization: %s\n", specValue.toChars());
3406 printf("\tParameter Value: %s\n", ea ? ea.toChars() : "NULL");
3407 }
3408
3409 override RootObject specialization()
3410 {
3411 return specValue;
3412 }
3413
3414 override RootObject defaultArg(const ref Loc instLoc, Scope* sc)
3415 {
3416 Expression e = defaultValue;
3417 if (e)
3418 {
3419 e = e.syntaxCopy();
3420 Scope* sc2 = sc.push();
3421 sc2.inDefaultArg = true;
3422 e = e.expressionSemantic(sc2);
3423 sc2.pop();
3424 if (e is null)
3425 return null;
3426 if (auto te = e.isTemplateExp())
3427 {
3428 assert(sc && sc.tinst);
3429 if (te.td == sc.tinst.tempdecl)
3430 {
3431 // defaultValue is a reference to its template declaration
3432 // i.e: `template T(int arg = T)`
3433 // Raise error now before calling resolveProperties otherwise we'll
3434 // start looping on the expansion of the template instance.
3435 auto td = sc.tinst.tempdecl;
3436 .error(td.loc, "%s `%s` recursive template expansion", td.kind, td.toPrettyChars);
3437 return ErrorExp.get();
3438 }
3439 }
3440 if ((e = resolveProperties(sc, e)) is null)
3441 return null;
3442 e = e.resolveLoc(instLoc, sc); // use the instantiated loc
3443 e = e.optimize(WANTvalue);
3444 }
3445 return e;
3446 }
3447
3448 override bool hasDefaultArg()
3449 {
3450 return defaultValue !is null;
3451 }
3452
3453 override RootObject dummyArg()
3454 {
3455 Expression e = specValue;
3456 if (!e)
3457 {
3458 // Create a dummy value
3459 auto pe = cast(void*)valType in edummies;
3460 if (!pe)
3461 {
3462 e = valType.defaultInit(Loc.initial);
3463 edummies[cast(void*)valType] = e;
3464 }
3465 else
3466 e = *pe;
3467 }
3468 return e;
3469 }
3470
3471 override void accept(Visitor v)
3472 {
3473 v.visit(this);
3474 }
3475 }
3476
3477 /***********************************************************
3478 * https://dlang.org/spec/template.html#TemplateAliasParameter
3479 * Syntax:
3480 * specType ident : specAlias = defaultAlias
3481 */
3482 extern (C++) final class TemplateAliasParameter : TemplateParameter
3483 {
3484 Type specType;
3485 RootObject specAlias;
3486 RootObject defaultAlias;
3487
3488 extern (D) __gshared Dsymbol sdummy = null;
3489
3490 extern (D) this(const ref Loc loc, Identifier ident, Type specType, RootObject specAlias, RootObject defaultAlias) @safe
3491 {
3492 super(loc, ident);
3493 this.specType = specType;
3494 this.specAlias = specAlias;
3495 this.defaultAlias = defaultAlias;
3496 }
3497
3498 override TemplateAliasParameter isTemplateAliasParameter()
3499 {
3500 return this;
3501 }
3502
3503 override TemplateAliasParameter syntaxCopy()
3504 {
3505 return new TemplateAliasParameter(loc, ident, specType ? specType.syntaxCopy() : null, objectSyntaxCopy(specAlias), objectSyntaxCopy(defaultAlias));
3506 }
3507
3508 override bool declareParameter(Scope* sc)
3509 {
3510 auto ti = new TypeIdentifier(loc, ident);
3511 Declaration ad = new AliasDeclaration(loc, ident, ti);
3512 return sc.insert(ad) !is null;
3513 }
3514
3515 override void print(RootObject oarg, RootObject oded)
3516 {
3517 printf(" %s\n", ident.toChars());
3518 Dsymbol sa = isDsymbol(oded);
3519 assert(sa);
3520 printf("\tParameter alias: %s\n", sa.toChars());
3521 }
3522
3523 override RootObject specialization()
3524 {
3525 return specAlias;
3526 }
3527
3528 override RootObject defaultArg(const ref Loc instLoc, Scope* sc)
3529 {
3530 RootObject da = defaultAlias;
3531 if (auto ta = isType(defaultAlias))
3532 {
3533 switch (ta.ty)
3534 {
3535 // If the default arg is a template, instantiate for each type
3536 case Tinstance :
3537 // same if the default arg is a mixin, traits, typeof
3538 // since the content might rely on a previous parameter
3539 // (https://issues.dlang.org/show_bug.cgi?id=23686)
3540 case Tmixin, Ttypeof, Ttraits :
3541 da = ta.syntaxCopy();
3542 break;
3543 default:
3544 }
3545 }
3546
3547 RootObject o = aliasParameterSemantic(loc, sc, da, null); // use the parameter loc
3548 return o;
3549 }
3550
3551 override bool hasDefaultArg()
3552 {
3553 return defaultAlias !is null;
3554 }
3555
3556 override RootObject dummyArg()
3557 {
3558 RootObject s = specAlias;
3559 if (!s)
3560 {
3561 if (!sdummy)
3562 sdummy = new Dsymbol();
3563 s = sdummy;
3564 }
3565 return s;
3566 }
3567
3568 override void accept(Visitor v)
3569 {
3570 v.visit(this);
3571 }
3572 }
3573
3574 /***********************************************************
3575 * https://dlang.org/spec/template.html#TemplateSequenceParameter
3576 * Syntax:
3577 * ident ...
3578 */
3579 extern (C++) final class TemplateTupleParameter : TemplateParameter
3580 {
3581 extern (D) this(const ref Loc loc, Identifier ident) @safe
3582 {
3583 super(loc, ident);
3584 }
3585
3586 override TemplateTupleParameter isTemplateTupleParameter()
3587 {
3588 return this;
3589 }
3590
3591 override TemplateTupleParameter syntaxCopy()
3592 {
3593 return new TemplateTupleParameter(loc, ident);
3594 }
3595
3596 override bool declareParameter(Scope* sc)
3597 {
3598 auto ti = new TypeIdentifier(loc, ident);
3599 Declaration ad = new AliasDeclaration(loc, ident, ti);
3600 return sc.insert(ad) !is null;
3601 }
3602
3603 override void print(RootObject oarg, RootObject oded)
3604 {
3605 printf(" %s... [", ident.toChars());
3606 Tuple v = isTuple(oded);
3607 assert(v);
3608
3609 //printf("|%d| ", v.objects.length);
3610 foreach (i, o; v.objects)
3611 {
3612 if (i)
3613 printf(", ");
3614
3615 Dsymbol sa = isDsymbol(o);
3616 if (sa)
3617 printf("alias: %s", sa.toChars());
3618 Type ta = isType(o);
3619 if (ta)
3620 printf("type: %s", ta.toChars());
3621 Expression ea = isExpression(o);
3622 if (ea)
3623 printf("exp: %s", ea.toChars());
3624
3625 assert(!isTuple(o)); // no nested Tuple arguments
3626 }
3627 printf("]\n");
3628 }
3629
3630 override RootObject specialization()
3631 {
3632 return null;
3633 }
3634
3635 override RootObject defaultArg(const ref Loc instLoc, Scope* sc)
3636 {
3637 return null;
3638 }
3639
3640 override bool hasDefaultArg()
3641 {
3642 return false;
3643 }
3644
3645 override RootObject dummyArg()
3646 {
3647 return null;
3648 }
3649
3650 override void accept(Visitor v)
3651 {
3652 v.visit(this);
3653 }
3654 }
3655
3656 /***********************************************************
3657 * https://dlang.org/spec/template.html#explicit_tmp_instantiation
3658 * Given:
3659 * foo!(args) =>
3660 * name = foo
3661 * tiargs = args
3662 */
3663 extern (C++) class TemplateInstance : ScopeDsymbol
3664 {
3665 Identifier name;
3666
3667 // Array of Types/Expressions of template
3668 // instance arguments [int*, char, 10*10]
3669 Objects* tiargs;
3670
3671 // Array of Types/Expressions corresponding
3672 // to TemplateDeclaration.parameters
3673 // [int, char, 100]
3674 Objects tdtypes;
3675
3676 // Modules imported by this template instance
3677 Modules importedModules;
3678
3679 Dsymbol tempdecl; // referenced by foo.bar.abc
3680 Dsymbol enclosing; // if referencing local symbols, this is the context
3681 Dsymbol aliasdecl; // !=null if instance is an alias for its sole member
3682 TemplateInstance inst; // refer to existing instance
3683 ScopeDsymbol argsym; // argument symbol table
3684 size_t hash; // cached result of toHash()
3685
3686 /// For function template, these are the function names and arguments
3687 /// Relevant because different resolutions of `auto ref` parameters
3688 /// create different template instances even with the same template arguments
3689 Expressions* fargs;
3690 Identifiers* fnames;
3691
3692 TemplateInstances* deferred;
3693
3694 Module memberOf; // if !null, then this TemplateInstance appears in memberOf.members[]
3695
3696 // Used to determine the instance needs code generation.
3697 // Note that these are inaccurate until semantic analysis phase completed.
3698 TemplateInstance tinst; // enclosing template instance
3699 TemplateInstance tnext; // non-first instantiated instances
3700 Module minst; // the top module that instantiated this instance
3701
3702 private ushort _nest; // for recursive pretty printing detection, 3 MSBs reserved for flags (below)
3703 ubyte inuse; // for recursive expansion detection
3704
3705 private enum Flag : uint
3706 {
3707 semantictiargsdone = 1u << (_nest.sizeof * 8 - 1), // MSB of _nest
3708 havetempdecl = semantictiargsdone >> 1,
3709 gagged = semantictiargsdone >> 2,
3710 available = gagged - 1 // always last flag minus one, 1s for all available bits
3711 }
3712
3713 extern(D) final @safe @property pure nothrow @nogc
3714 {
3715 ushort nest() const { return _nest & Flag.available; }
3716 void nestUp() { assert(nest() < Flag.available); ++_nest; }
3717 void nestDown() { assert(nest() > 0); --_nest; }
3718 /// has semanticTiargs() been done?
3719 bool semantictiargsdone() const { return (_nest & Flag.semantictiargsdone) != 0; }
3720 void semantictiargsdone(bool x)
3721 {
3722 if (x) _nest |= Flag.semantictiargsdone;
3723 else _nest &= ~Flag.semantictiargsdone;
3724 }
3725 /// if used second constructor
3726 bool havetempdecl() const { return (_nest & Flag.havetempdecl) != 0; }
3727 void havetempdecl(bool x)
3728 {
3729 if (x) _nest |= Flag.havetempdecl;
3730 else _nest &= ~Flag.havetempdecl;
3731 }
3732 /// if the instantiation is done with error gagging
3733 bool gagged() const { return (_nest & Flag.gagged) != 0; }
3734 void gagged(bool x)
3735 {
3736 if (x) _nest |= Flag.gagged;
3737 else _nest &= ~Flag.gagged;
3738 }
3739 }
3740
3741 extern (D) this(const ref Loc loc, Identifier ident, Objects* tiargs) scope
3742 {
3743 super(loc, null);
3744 static if (LOG)
3745 {
3746 printf("TemplateInstance(this = %p, ident = '%s')\n", this, ident ? ident.toChars() : "null");
3747 }
3748 this.name = ident;
3749 this.tiargs = tiargs;
3750 }
3751
3752 /*****************
3753 * This constructor is only called when we figured out which function
3754 * template to instantiate.
3755 */
3756 extern (D) this(const ref Loc loc, TemplateDeclaration td, Objects* tiargs) scope
3757 {
3758 super(loc, null);
3759 static if (LOG)
3760 {
3761 printf("TemplateInstance(this = %p, tempdecl = '%s')\n", this, td.toChars());
3762 }
3763 this.name = td.ident;
3764 this.tiargs = tiargs;
3765 this.tempdecl = td;
3766 this.semantictiargsdone = true;
3767 this.havetempdecl = true;
3768 assert(tempdecl._scope);
3769 }
3770
3771 extern (D) static Objects* arraySyntaxCopy(Objects* objs)
3772 {
3773 Objects* a = null;
3774 if (objs)
3775 {
3776 a = new Objects(objs.length);
3777 foreach (i, o; *objs)
3778 (*a)[i] = objectSyntaxCopy(o);
3779 }
3780 return a;
3781 }
3782
3783 override TemplateInstance syntaxCopy(Dsymbol s)
3784 {
3785 TemplateInstance ti = s ? cast(TemplateInstance)s : new TemplateInstance(loc, name, null);
3786 ti.tiargs = arraySyntaxCopy(tiargs);
3787 TemplateDeclaration td;
3788 if (inst && tempdecl && (td = tempdecl.isTemplateDeclaration()) !is null)
3789 td.ScopeDsymbol.syntaxCopy(ti);
3790 else
3791 ScopeDsymbol.syntaxCopy(ti);
3792 return ti;
3793 }
3794
3795 // resolve real symbol
3796 override final Dsymbol toAlias()
3797 {
3798 static if (LOG)
3799 {
3800 printf("TemplateInstance.toAlias()\n");
3801 }
3802 if (!inst)
3803 {
3804 // Maybe we can resolve it
3805 if (_scope)
3806 {
3807 dsymbolSemantic(this, _scope);
3808 }
3809 if (!inst)
3810 {
3811 .error(loc, "%s `%s` cannot resolve forward reference", kind, toPrettyChars);
3812 errors = true;
3813 return this;
3814 }
3815 }
3816
3817 if (inst != this)
3818 return inst.toAlias();
3819
3820 if (aliasdecl)
3821 {
3822 return aliasdecl.toAlias();
3823 }
3824
3825 return inst;
3826 }
3827
3828 override const(char)* kind() const
3829 {
3830 return "template instance";
3831 }
3832
3833 override bool oneMember(out Dsymbol ps, Identifier ident)
3834 {
3835 ps = null;
3836 return true;
3837 }
3838
3839 override const(char)* toChars() const
3840 {
3841 OutBuffer buf;
3842 toCBufferInstance(this, buf);
3843 return buf.extractChars();
3844 }
3845
3846 override final const(char)* toPrettyCharsHelper()
3847 {
3848 OutBuffer buf;
3849 toCBufferInstance(this, buf, true);
3850 return buf.extractChars();
3851 }
3852
3853 /**************************************
3854 * Given an error instantiating the TemplateInstance,
3855 * give the nested TemplateInstance instantiations that got
3856 * us here. Those are a list threaded into the nested scopes.
3857 * Params:
3858 * cl = classification of this trace as printing either errors or deprecations
3859 * max_shown = maximum number of trace elements printed (controlled with -v/-verror-limit)
3860 */
3861 extern(D) final void printInstantiationTrace(Classification cl = Classification.error,
3862 const(uint) max_shown = global.params.v.errorSupplementCount())
3863 {
3864 if (global.gag)
3865 return;
3866
3867 // Print full trace for verbose mode, otherwise only short traces
3868 const(char)* format = "instantiated from here: `%s`";
3869
3870 // This returns a function pointer
3871 scope printFn = () {
3872 final switch (cl)
3873 {
3874 case Classification.error:
3875 return &errorSupplemental;
3876 case Classification.deprecation:
3877 return &deprecationSupplemental;
3878 case Classification.gagged, Classification.tip, Classification.warning:
3879 assert(0);
3880 }
3881 }();
3882
3883 // determine instantiation depth and number of recursive instantiations
3884 int n_instantiations = 1;
3885 int n_totalrecursions = 0;
3886 for (TemplateInstance cur = this; cur; cur = cur.tinst)
3887 {
3888 ++n_instantiations;
3889 // Set error here as we don't want it to depend on the number of
3890 // entries that are being printed.
3891 if (cl == Classification.error ||
3892 (cl == Classification.warning && global.params.warnings == DiagnosticReporting.error) ||
3893 (cl == Classification.deprecation && global.params.useDeprecated == DiagnosticReporting.error))
3894 cur.errors = true;
3895
3896 // If two instantiations use the same declaration, they are recursive.
3897 // (this works even if they are instantiated from different places in the
3898 // same template).
3899 // In principle, we could also check for multiple-template recursion, but it's
3900 // probably not worthwhile.
3901 if (cur.tinst && cur.tempdecl && cur.tinst.tempdecl && cur.tempdecl.loc.equals(cur.tinst.tempdecl.loc))
3902 ++n_totalrecursions;
3903 }
3904
3905 if (n_instantiations <= max_shown)
3906 {
3907 for (TemplateInstance cur = this; cur; cur = cur.tinst)
3908 printFn(cur.loc, format, cur.toChars());
3909 }
3910 else if (n_instantiations - n_totalrecursions <= max_shown)
3911 {
3912 // By collapsing recursive instantiations into a single line,
3913 // we can stay under the limit.
3914 int recursionDepth = 0;
3915 for (TemplateInstance cur = this; cur; cur = cur.tinst)
3916 {
3917 if (cur.tinst && cur.tempdecl && cur.tinst.tempdecl && cur.tempdecl.loc.equals(cur.tinst.tempdecl.loc))
3918 {
3919 ++recursionDepth;
3920 }
3921 else
3922 {
3923 if (recursionDepth)
3924 printFn(cur.loc, "%d recursive instantiations from here: `%s`", recursionDepth + 2, cur.toChars());
3925 else
3926 printFn(cur.loc, format, cur.toChars());
3927 recursionDepth = 0;
3928 }
3929 }
3930 }
3931 else
3932 {
3933 // Even after collapsing the recursions, the depth is too deep.
3934 // Just display the first few and last few instantiations.
3935 uint i = 0;
3936 for (TemplateInstance cur = this; cur; cur = cur.tinst)
3937 {
3938 if (i == max_shown / 2)
3939 printFn(cur.loc, "... (%d instantiations, -v to show) ...", n_instantiations - max_shown);
3940
3941 if (i < max_shown / 2 || i >= n_instantiations - max_shown + max_shown / 2)
3942 printFn(cur.loc, format, cur.toChars());
3943 ++i;
3944 }
3945 }
3946 }
3947
3948 /*************************************
3949 * Lazily generate identifier for template instance.
3950 * This is because 75% of the ident's are never needed.
3951 */
3952 override final Identifier getIdent()
3953 {
3954 if (!ident && inst && !errors)
3955 ident = genIdent(tiargs); // need an identifier for name mangling purposes.
3956 return ident;
3957 }
3958
3959 /*************************************
3960 * Compare proposed template instantiation with existing template instantiation.
3961 * Note that this is not commutative because of the auto ref check.
3962 * Params:
3963 * ti = existing template instantiation
3964 * Returns:
3965 * true for match
3966 */
3967 final bool equalsx(TemplateInstance ti)
3968 {
3969 //printf("this = %p, ti = %p\n", this, ti);
3970 assert(tdtypes.length == ti.tdtypes.length);
3971
3972 // Nesting must match
3973 if (enclosing != ti.enclosing)
3974 {
3975 //printf("test2 enclosing %s ti.enclosing %s\n", enclosing ? enclosing.toChars() : "", ti.enclosing ? ti.enclosing.toChars() : "");
3976 goto Lnotequals;
3977 }
3978 //printf("parent = %s, ti.parent = %s\n", parent.toPrettyChars(), ti.parent.toPrettyChars());
3979
3980 if (!arrayObjectMatch(tdtypes, ti.tdtypes))
3981 goto Lnotequals;
3982
3983 /* Template functions may have different instantiations based on
3984 * "auto ref" parameters.
3985 */
3986 if (auto fd = ti.toAlias().isFuncDeclaration())
3987 {
3988 if (!fd.errors)
3989 {
3990 auto resolvedArgs = fd.type.isTypeFunction().resolveNamedArgs(
3991 ArgumentList(this.fargs, this.fnames), null);
3992
3993 // resolvedArgs can be null when there's an error: fail_compilation/fail14669.d
3994 // In that case, equalsx returns true to prevent endless template instantiations
3995 // However, it can also mean the function was explicitly instantiated
3996 // without function arguments: fail_compilation/fail14669
3997 // Hence the following check:
3998 if (this.fargs && !resolvedArgs)
3999 return true;
4000
4001 Expression[] args = resolvedArgs ? (*resolvedArgs)[] : [];
4002
4003 auto fparameters = fd.getParameterList();
4004 size_t nfparams = fparameters.length; // Num function parameters
4005 for (size_t j = 0; j < nfparams; j++)
4006 {
4007 Parameter fparam = fparameters[j];
4008 if (fparam.storageClass & STC.autoref) // if "auto ref"
4009 {
4010 Expression farg = (j < args.length) ? args[j] : fparam.defaultArg;
4011 // resolveNamedArgs strips trailing nulls / default params
4012 // when it doesn't anymore, the ternary can be replaced with:
4013 // assert(j < resolvedArgs.length);
4014 if (!farg)
4015 farg = fparam.defaultArg;
4016 if (!farg)
4017 goto Lnotequals;
4018 if (farg.isLvalue())
4019 {
4020 if (!(fparam.storageClass & STC.ref_))
4021 goto Lnotequals; // auto ref's don't match
4022 }
4023 else
4024 {
4025 if (fparam.storageClass & STC.ref_)
4026 goto Lnotequals; // auto ref's don't match
4027 }
4028 }
4029 }
4030 }
4031 }
4032 return true;
4033
4034 Lnotequals:
4035 return false;
4036 }
4037
4038 extern (D) final size_t toHash()
4039 {
4040 if (!hash)
4041 {
4042 hash = cast(size_t)cast(void*)enclosing;
4043 hash += arrayObjectHash(tdtypes);
4044 hash += hash == 0;
4045 }
4046 return hash;
4047 }
4048
4049 /**
4050 Returns: true if the instances' innards are discardable.
4051
4052 The idea of this function is to see if the template instantiation
4053 can be 100% replaced with its eponymous member. All other members
4054 can be discarded, even in the compiler to free memory (for example,
4055 the template could be expanded in a region allocator, deemed trivial,
4056 the end result copied back out independently and the entire region freed),
4057 and can be elided entirely from the binary.
4058
4059 The current implementation affects code that generally looks like:
4060
4061 ---
4062 template foo(args...) {
4063 some_basic_type_or_string helper() { .... }
4064 enum foo = helper();
4065 }
4066 ---
4067
4068 since it was the easiest starting point of implementation but it can and
4069 should be expanded more later.
4070 */
4071 final bool isDiscardable()
4072 {
4073 if (aliasdecl is null)
4074 return false;
4075
4076 auto v = aliasdecl.isVarDeclaration();
4077 if (v is null)
4078 return false;
4079
4080 if (!(v.storage_class & STC.manifest))
4081 return false;
4082
4083 // Currently only doing basic types here because it is the easiest proof-of-concept
4084 // implementation with minimal risk of side effects, but it could likely be
4085 // expanded to any type that already exists outside this particular instance.
4086 if (!(v.type.equals(Type.tstring) || (v.type.isTypeBasic() !is null)))
4087 return false;
4088
4089 // Static ctors and dtors, even in an eponymous enum template, are still run,
4090 // so if any of them are in here, we'd better not assume it is trivial lest
4091 // we break useful code
4092 foreach(member; *members)
4093 {
4094 if(member.hasStaticCtorOrDtor())
4095 return false;
4096 if(member.isStaticDtorDeclaration())
4097 return false;
4098 if(member.isStaticCtorDeclaration())
4099 return false;
4100 }
4101
4102 // but if it passes through this gauntlet... it should be fine. D code will
4103 // see only the eponymous member, outside stuff can never access it, even through
4104 // reflection; the outside world ought to be none the wiser. Even dmd should be
4105 // able to simply free the memory of everything except the final result.
4106
4107 return true;
4108 }
4109
4110
4111 /***********************************************
4112 * Returns true if this is not instantiated in non-root module, and
4113 * is a part of non-speculative instantiatiation.
4114 *
4115 * Note: minst does not stabilize until semantic analysis is completed,
4116 * so don't call this function during semantic analysis to return precise result.
4117 */
4118 final bool needsCodegen()
4119 {
4120 //printf("needsCodegen() %s\n", toChars());
4121
4122 // minst is finalized after the 1st invocation.
4123 // tnext is only needed for the 1st invocation and
4124 // cleared for further invocations.
4125 TemplateInstance tnext = this.tnext;
4126 TemplateInstance tinst = this.tinst;
4127 this.tnext = null;
4128
4129 // Don't do codegen if the instance has errors,
4130 // is a dummy instance (see evaluateConstraint),
4131 // or is determined to be discardable.
4132 if (errors || inst is null || inst.isDiscardable())
4133 {
4134 minst = null; // mark as speculative
4135 return false;
4136 }
4137
4138 // This should only be called on the primary instantiation.
4139 assert(this is inst);
4140
4141 if (global.params.allInst)
4142 {
4143 // Do codegen if there is an instantiation from a root module, to maximize link-ability.
4144 static ThreeState needsCodegenAllInst(TemplateInstance tithis, TemplateInstance tinst)
4145 {
4146 // Do codegen if `this` is instantiated from a root module.
4147 if (tithis.minst && tithis.minst.isRoot())
4148 return ThreeState.yes;
4149
4150 // Do codegen if the ancestor needs it.
4151 if (tinst && tinst.inst && tinst.inst.needsCodegen())
4152 {
4153 tithis.minst = tinst.inst.minst; // cache result
4154 assert(tithis.minst);
4155 assert(tithis.minst.isRoot());
4156 return ThreeState.yes;
4157 }
4158 return ThreeState.none;
4159 }
4160
4161 if (const needsCodegen = needsCodegenAllInst(this, tinst))
4162 return needsCodegen == ThreeState.yes ? true : false;
4163
4164 // Do codegen if a sibling needs it.
4165 for (; tnext; tnext = tnext.tnext)
4166 {
4167 const needsCodegen = needsCodegenAllInst(tnext, tnext.tinst);
4168 if (needsCodegen == ThreeState.yes)
4169 {
4170 minst = tnext.minst; // cache result
4171 assert(minst);
4172 assert(minst.isRoot());
4173 return true;
4174 }
4175 else if (!minst && tnext.minst)
4176 {
4177 minst = tnext.minst; // cache result from non-speculative sibling
4178 // continue searching
4179 }
4180 else if (needsCodegen != ThreeState.none)
4181 break;
4182 }
4183
4184 // Elide codegen because there's no instantiation from any root modules.
4185 return false;
4186 }
4187 else
4188 {
4189 // Prefer instantiations from non-root modules, to minimize object code size.
4190
4191 /* If a TemplateInstance is ever instantiated from a non-root module,
4192 * we do not have to generate code for it,
4193 * because it will be generated when the non-root module is compiled.
4194 *
4195 * But, if the non-root 'minst' imports any root modules, it might still need codegen.
4196 *
4197 * The problem is if A imports B, and B imports A, and both A
4198 * and B instantiate the same template, does the compilation of A
4199 * or the compilation of B do the actual instantiation?
4200 *
4201 * See https://issues.dlang.org/show_bug.cgi?id=2500.
4202 *
4203 * => Elide codegen if there is at least one instantiation from a non-root module
4204 * which doesn't import any root modules.
4205 */
4206 static ThreeState needsCodegenRootOnly(TemplateInstance tithis, TemplateInstance tinst)
4207 {
4208 // If the ancestor isn't speculative,
4209 // 1. do codegen if the ancestor needs it
4210 // 2. elide codegen if the ancestor doesn't need it (non-root instantiation of ancestor incl. subtree)
4211 if (tinst && tinst.inst)
4212 {
4213 tinst = tinst.inst;
4214 const needsCodegen = tinst.needsCodegen(); // sets tinst.minst
4215 if (tinst.minst) // not speculative
4216 {
4217 tithis.minst = tinst.minst; // cache result
4218 return needsCodegen ? ThreeState.yes : ThreeState.no;
4219 }
4220 }
4221
4222 // Elide codegen if `this` doesn't need it.
4223 if (tithis.minst && !tithis.minst.isRoot() && !tithis.minst.rootImports())
4224 return ThreeState.no;
4225
4226 return ThreeState.none;
4227 }
4228
4229 if (const needsCodegen = needsCodegenRootOnly(this, tinst))
4230 return needsCodegen == ThreeState.yes ? true : false;
4231
4232 // Elide codegen if a (non-speculative) sibling doesn't need it.
4233 for (; tnext; tnext = tnext.tnext)
4234 {
4235 const needsCodegen = needsCodegenRootOnly(tnext, tnext.tinst); // sets tnext.minst
4236 if (tnext.minst) // not speculative
4237 {
4238 if (needsCodegen == ThreeState.no)
4239 {
4240 minst = tnext.minst; // cache result
4241 assert(!minst.isRoot() && !minst.rootImports());
4242 return false;
4243 }
4244 else if (!minst)
4245 {
4246 minst = tnext.minst; // cache result from non-speculative sibling
4247 // continue searching
4248 }
4249 else if (needsCodegen != ThreeState.none)
4250 break;
4251 }
4252 }
4253
4254 // Unless `this` is still speculative (=> all further siblings speculative too),
4255 // do codegen because we found no guaranteed-codegen'd non-root instantiation.
4256 return minst !is null;
4257 }
4258 }
4259
4260 /**********************************************
4261 * Find template declaration corresponding to template instance.
4262 *
4263 * Returns:
4264 * false if finding fails.
4265 * Note:
4266 * This function is reentrant against error occurrence. If returns false,
4267 * any members of this object won't be modified, and repetition call will
4268 * reproduce same error.
4269 */
4270 extern (D) final bool findTempDecl(Scope* sc, WithScopeSymbol* pwithsym)
4271 {
4272 if (pwithsym)
4273 *pwithsym = null;
4274
4275 if (havetempdecl)
4276 return true;
4277
4278 //printf("TemplateInstance.findTempDecl() %s\n", toChars());
4279 if (!tempdecl)
4280 {
4281 /* Given:
4282 * foo!( ... )
4283 * figure out which TemplateDeclaration foo refers to.
4284 */
4285 Identifier id = name;
4286 Dsymbol scopesym;
4287 Dsymbol s = sc.search(loc, id, scopesym);
4288 if (!s)
4289 {
4290 s = sc.search_correct(id);
4291 if (s)
4292 .error(loc, "%s `%s` template `%s` is not defined, did you mean %s?", kind, toPrettyChars, id.toChars(), s.toChars());
4293 else
4294 .error(loc, "%s `%s` template `%s` is not defined", kind, toPrettyChars, id.toChars());
4295 return false;
4296 }
4297 static if (LOG)
4298 {
4299 printf("It's an instance of '%s' kind '%s'\n", s.toChars(), s.kind());
4300 if (s.parent)
4301 printf("s.parent = '%s'\n", s.parent.toChars());
4302 }
4303 if (pwithsym)
4304 *pwithsym = scopesym.isWithScopeSymbol();
4305
4306 /* We might have found an alias within a template when
4307 * we really want the template.
4308 */
4309 TemplateInstance ti;
4310 if (s.parent && (ti = s.parent.isTemplateInstance()) !is null)
4311 {
4312 if (ti.tempdecl && ti.tempdecl.ident == id)
4313 {
4314 /* This is so that one can refer to the enclosing
4315 * template, even if it has the same name as a member
4316 * of the template, if it has a !(arguments)
4317 */
4318 TemplateDeclaration td = ti.tempdecl.isTemplateDeclaration();
4319 assert(td);
4320 if (td.overroot) // if not start of overloaded list of TemplateDeclaration's
4321 td = td.overroot; // then get the start
4322 s = td;
4323 }
4324 }
4325
4326 // The template might originate from a selective import which implies that
4327 // s is a lowered AliasDeclaration of the actual TemplateDeclaration.
4328 // This is the last place where we see the deprecated alias because it is
4329 // stripped below, so check if the selective import was deprecated.
4330 // See https://issues.dlang.org/show_bug.cgi?id=20840.
4331 if (s.isAliasDeclaration())
4332 s.checkDeprecated(this.loc, sc);
4333
4334 if (!updateTempDecl(sc, s))
4335 {
4336 return false;
4337 }
4338 }
4339 assert(tempdecl);
4340
4341 // Look for forward references
4342 auto tovers = tempdecl.isOverloadSet();
4343 foreach (size_t oi; 0 .. tovers ? tovers.a.length : 1)
4344 {
4345 Dsymbol dstart = tovers ? tovers.a[oi] : tempdecl;
4346 int r = overloadApply(dstart, (Dsymbol s)
4347 {
4348 auto td = s.isTemplateDeclaration();
4349 if (!td)
4350 return 0;
4351
4352 if (td.semanticRun == PASS.initial)
4353 {
4354 if (td._scope)
4355 {
4356 // Try to fix forward reference. Ungag errors while doing so.
4357 Ungag ungag = td.ungagSpeculative();
4358 td.dsymbolSemantic(td._scope);
4359 }
4360 if (td.semanticRun == PASS.initial)
4361 {
4362 .error(loc, "%s `%s` `%s` forward references template declaration `%s`", kind, toPrettyChars,
4363 toChars(), td.toChars());
4364 return 1;
4365 }
4366 }
4367 return 0;
4368 });
4369 if (r)
4370 return false;
4371 }
4372 return true;
4373 }
4374
4375 /**********************************************
4376 * Confirm s is a valid template, then store it.
4377 * Input:
4378 * sc
4379 * s candidate symbol of template. It may be:
4380 * TemplateDeclaration
4381 * FuncDeclaration with findTemplateDeclRoot() != NULL
4382 * OverloadSet which contains candidates
4383 * Returns:
4384 * true if updating succeeds.
4385 */
4386 extern (D) final bool updateTempDecl(Scope* sc, Dsymbol s)
4387 {
4388 if (!s)
4389 return tempdecl !is null;
4390
4391 Identifier id = name;
4392 s = s.toAlias();
4393
4394 /* If an OverloadSet, look for a unique member that is a template declaration
4395 */
4396 if (OverloadSet os = s.isOverloadSet())
4397 {
4398 s = null;
4399 foreach (s2; os.a)
4400 {
4401 if (FuncDeclaration f = s2.isFuncDeclaration())
4402 s2 = f.findTemplateDeclRoot();
4403 else
4404 s2 = s2.isTemplateDeclaration();
4405 if (s2)
4406 {
4407 if (s)
4408 {
4409 tempdecl = os;
4410 return true;
4411 }
4412 s = s2;
4413 }
4414 }
4415 if (!s)
4416 {
4417 .error(loc, "%s `%s` template `%s` is not defined", kind, toPrettyChars, id.toChars());
4418 return false;
4419 }
4420 }
4421
4422 if (OverDeclaration od = s.isOverDeclaration())
4423 {
4424 tempdecl = od; // TODO: more strict check
4425 return true;
4426 }
4427
4428 /* It should be a TemplateDeclaration, not some other symbol
4429 */
4430 if (FuncDeclaration f = s.isFuncDeclaration())
4431 tempdecl = f.findTemplateDeclRoot();
4432 else
4433 tempdecl = s.isTemplateDeclaration();
4434
4435 // We're done
4436 if (tempdecl)
4437 return true;
4438
4439 // Error already issued, just return `false`
4440 if (!s.parent && global.errors)
4441 return false;
4442
4443 if (!s.parent && s.getType())
4444 {
4445 Dsymbol s2 = s.getType().toDsymbol(sc);
4446 if (!s2)
4447 {
4448 .error(loc, "`%s` is not a valid template instance, because `%s` is not a template declaration but a type (`%s == %s`)", toChars(), id.toChars(), id.toChars(), s.getType.kind());
4449 return false;
4450 }
4451 // because s can be the alias created for a TemplateParameter
4452 const AliasDeclaration ad = s.isAliasDeclaration();
4453 version (none)
4454 {
4455 if (ad && ad.isAliasedTemplateParameter())
4456 printf("`%s` is an alias created from a template parameter\n", s.toChars());
4457 }
4458 if (!ad || !ad.isAliasedTemplateParameter())
4459 s = s2;
4460 }
4461
4462 TemplateInstance ti = s.parent ? s.parent.isTemplateInstance() : null;
4463
4464 /* This avoids the VarDeclaration.toAlias() which runs semantic() too soon
4465 */
4466 static bool matchId(TemplateInstance ti, Identifier id)
4467 {
4468 if (ti.aliasdecl && ti.aliasdecl.isVarDeclaration())
4469 return ti.aliasdecl.isVarDeclaration().ident == id;
4470 return ti.toAlias().ident == id;
4471 }
4472
4473 if (ti && (ti.name == s.ident || matchId(ti, s.ident)) && ti.tempdecl)
4474 {
4475 /* This is so that one can refer to the enclosing
4476 * template, even if it has the same name as a member
4477 * of the template, if it has a !(arguments)
4478 */
4479 TemplateDeclaration td = ti.tempdecl.isTemplateDeclaration();
4480 assert(td);
4481 if (td.overroot) // if not start of overloaded list of TemplateDeclaration's
4482 td = td.overroot; // then get the start
4483 tempdecl = td;
4484 return true;
4485 }
4486 else
4487 {
4488 .error(loc, "%s `%s` `%s` is not a template declaration, it is a %s", kind, toPrettyChars, id.toChars(), s.kind());
4489 return false;
4490 }
4491 }
4492
4493 /**********************************
4494 * Run semantic of tiargs as arguments of template.
4495 * Input:
4496 * loc
4497 * sc
4498 * tiargs array of template arguments
4499 * flags 1: replace const variables with their initializers
4500 * 2: don't devolve Parameter to Type
4501 * atd tuple being optimized. If found, it's not expanded here
4502 * but in AliasAssign semantic.
4503 * Returns:
4504 * false if one or more arguments have errors.
4505 */
4506 extern (D) static bool semanticTiargs(const ref Loc loc, Scope* sc, Objects* tiargs, int flags, TupleDeclaration atd = null)
4507 {
4508 // Run semantic on each argument, place results in tiargs[]
4509 //printf("+TemplateInstance.semanticTiargs()\n");
4510 if (!tiargs)
4511 return true;
4512 bool err = false;
4513
4514 // The arguments are not treated as part of a default argument,
4515 // because they are evaluated at compile time.
4516 sc = sc.push();
4517 sc.inDefaultArg = false;
4518
4519 for (size_t j = 0; j < tiargs.length; j++)
4520 {
4521 RootObject o = (*tiargs)[j];
4522 Type ta = isType(o);
4523 Expression ea = isExpression(o);
4524 Dsymbol sa = isDsymbol(o);
4525
4526 //printf("1: (*tiargs)[%d] = %p, s=%p, v=%p, ea=%p, ta=%p\n", j, o, isDsymbol(o), isTuple(o), ea, ta);
4527 if (ta)
4528 {
4529 //printf("type %s\n", ta.toChars());
4530
4531 // It might really be an Expression or an Alias
4532 ta.resolve(loc, sc, ea, ta, sa, (flags & 1) != 0);
4533 if (ea)
4534 goto Lexpr;
4535 if (sa)
4536 goto Ldsym;
4537 if (ta is null)
4538 {
4539 assert(global.errors);
4540 ta = Type.terror;
4541 }
4542
4543 Ltype:
4544 if (TypeTuple tt = ta.isTypeTuple())
4545 {
4546 // Expand tuple
4547 size_t dim = tt.arguments.length;
4548 tiargs.remove(j);
4549 if (dim)
4550 {
4551 tiargs.reserve(dim);
4552 foreach (i, arg; *tt.arguments)
4553 {
4554 if (flags & 2 && (arg.storageClass & STC.parameter))
4555 tiargs.insert(j + i, arg);
4556 else
4557 tiargs.insert(j + i, arg.type);
4558 }
4559 }
4560 j--;
4561 continue;
4562 }
4563 if (ta.ty == Terror)
4564 {
4565 err = true;
4566 continue;
4567 }
4568 (*tiargs)[j] = ta.merge2();
4569 }
4570 else if (ea)
4571 {
4572 Lexpr:
4573 //printf("+[%d] ea = %s %s\n", j, EXPtoString(ea.op).ptr, ea.toChars());
4574 if (flags & 1) // only used by __traits
4575 {
4576 ea = ea.expressionSemantic(sc);
4577
4578 // must not interpret the args, excepting template parameters
4579 if (!ea.isVarExp() || (ea.isVarExp().var.storage_class & STC.templateparameter))
4580 {
4581 ea = ea.optimize(WANTvalue);
4582 }
4583 }
4584 else
4585 {
4586 sc = sc.startCTFE();
4587 ea = ea.expressionSemantic(sc);
4588 sc = sc.endCTFE();
4589
4590 if (auto varExp = ea.isVarExp())
4591 {
4592 /* If the parameter is a function that is not called
4593 * explicitly, i.e. `foo!func` as opposed to `foo!func()`,
4594 * then it is a dsymbol, not the return value of `func()`
4595 */
4596 Declaration vd = varExp.var;
4597 if (auto fd = vd.isFuncDeclaration())
4598 {
4599 sa = fd;
4600 goto Ldsym;
4601 }
4602 /* Otherwise skip substituting a const var with
4603 * its initializer. The problem is the initializer won't
4604 * match with an 'alias' parameter. Instead, do the
4605 * const substitution in TemplateValueParameter.matchArg().
4606 */
4607 }
4608 else if (definitelyValueParameter(ea))
4609 {
4610 if (ea.checkValue()) // check void expression
4611 ea = ErrorExp.get();
4612 uint olderrs = global.errors;
4613 ea = ea.ctfeInterpret();
4614 if (global.errors != olderrs)
4615 ea = ErrorExp.get();
4616 }
4617 }
4618 //printf("-[%d] ea = %s %s\n", j, EXPtoString(ea.op).ptr, ea.toChars());
4619 if (TupleExp te = ea.isTupleExp())
4620 {
4621 // Expand tuple
4622 size_t dim = te.exps.length;
4623 tiargs.remove(j);
4624 if (dim)
4625 {
4626 tiargs.reserve(dim);
4627 foreach (i, exp; *te.exps)
4628 tiargs.insert(j + i, exp);
4629 }
4630 j--;
4631 continue;
4632 }
4633 if (ea.op == EXP.error)
4634 {
4635 err = true;
4636 continue;
4637 }
4638 (*tiargs)[j] = ea;
4639
4640 if (ea.op == EXP.type)
4641 {
4642 ta = ea.type;
4643 goto Ltype;
4644 }
4645 if (ea.op == EXP.scope_)
4646 {
4647 sa = ea.isScopeExp().sds;
4648 goto Ldsym;
4649 }
4650 if (FuncExp fe = ea.isFuncExp())
4651 {
4652 /* A function literal, that is passed to template and
4653 * already semanticed as function pointer, never requires
4654 * outer frame. So convert it to global function is valid.
4655 */
4656 if (fe.fd.tok == TOK.reserved && fe.type.ty == Tpointer)
4657 {
4658 // change to non-nested
4659 fe.fd.tok = TOK.function_;
4660 fe.fd.vthis = null;
4661 }
4662 else if (fe.td)
4663 {
4664 /* If template argument is a template lambda,
4665 * get template declaration itself. */
4666 //sa = fe.td;
4667 //goto Ldsym;
4668 }
4669 }
4670 if (ea.op == EXP.dotVariable && !(flags & 1))
4671 {
4672 // translate expression to dsymbol.
4673 sa = ea.isDotVarExp().var;
4674 goto Ldsym;
4675 }
4676 if (auto te = ea.isTemplateExp())
4677 {
4678 sa = te.td;
4679 goto Ldsym;
4680 }
4681 if (ea.op == EXP.dotTemplateDeclaration && !(flags & 1))
4682 {
4683 // translate expression to dsymbol.
4684 sa = ea.isDotTemplateExp().td;
4685 goto Ldsym;
4686 }
4687 if (auto de = ea.isDotExp())
4688 {
4689 if (auto se = de.e2.isScopeExp())
4690 {
4691 sa = se.sds;
4692 goto Ldsym;
4693 }
4694 }
4695 }
4696 else if (sa)
4697 {
4698 Ldsym:
4699 //printf("dsym %s %s\n", sa.kind(), sa.toChars());
4700 if (sa.errors)
4701 {
4702 err = true;
4703 continue;
4704 }
4705
4706 TupleDeclaration d = sa.toAlias().isTupleDeclaration();
4707 if (d)
4708 {
4709 if (d is atd)
4710 {
4711 (*tiargs)[j] = d;
4712 continue;
4713 }
4714 // Expand tuple
4715 tiargs.remove(j);
4716 tiargs.insert(j, d.objects);
4717 j--;
4718 continue;
4719 }
4720 if (FuncAliasDeclaration fa = sa.isFuncAliasDeclaration())
4721 {
4722 FuncDeclaration f = fa.toAliasFunc();
4723 if (!fa.hasOverloads && f.isUnique())
4724 {
4725 // Strip FuncAlias only when the aliased function
4726 // does not have any overloads.
4727 sa = f;
4728 }
4729 }
4730 (*tiargs)[j] = sa;
4731
4732 TemplateDeclaration td = sa.isTemplateDeclaration();
4733 if (td && td.semanticRun == PASS.initial && td.literal)
4734 {
4735 td.dsymbolSemantic(sc);
4736 }
4737 FuncDeclaration fd = sa.isFuncDeclaration();
4738 if (fd)
4739 functionSemantic(fd);
4740 }
4741 else if (isParameter(o))
4742 {
4743 }
4744 else
4745 {
4746 assert(0);
4747 }
4748 //printf("1: (*tiargs)[%d] = %p\n", j, (*tiargs)[j]);
4749 }
4750 sc.pop();
4751 version (none)
4752 {
4753 printf("-TemplateInstance.semanticTiargs()\n");
4754 for (size_t j = 0; j < tiargs.length; j++)
4755 {
4756 RootObject o = (*tiargs)[j];
4757 Type ta = isType(o);
4758 Expression ea = isExpression(o);
4759 Dsymbol sa = isDsymbol(o);
4760 Tuple va = isTuple(o);
4761 printf("\ttiargs[%d] = ta %p, ea %p, sa %p, va %p\n", j, ta, ea, sa, va);
4762 }
4763 }
4764 return !err;
4765 }
4766
4767 /**********************************
4768 * Run semantic on the elements of tiargs.
4769 * Input:
4770 * sc
4771 * Returns:
4772 * false if one or more arguments have errors.
4773 * Note:
4774 * This function is reentrant against error occurrence. If returns false,
4775 * all elements of tiargs won't be modified.
4776 */
4777 extern (D) final bool semanticTiargs(Scope* sc)
4778 {
4779 //printf("+TemplateInstance.semanticTiargs() %s\n", toChars());
4780 if (semantictiargsdone)
4781 return true;
4782 if (semanticTiargs(loc, sc, tiargs, 0))
4783 {
4784 // cache the result iff semantic analysis succeeded entirely
4785 semantictiargsdone = 1;
4786 return true;
4787 }
4788 return false;
4789 }
4790
4791 /**********************************
4792 * Find the TemplateDeclaration that matches this TemplateInstance best.
4793 *
4794 * Params:
4795 * sc = the scope this TemplateInstance resides in
4796 * argumentList = function arguments in case of a template function
4797 *
4798 * Returns:
4799 * `true` if a match was found, `false` otherwise
4800 */
4801 extern (D) final bool findBestMatch(Scope* sc, ArgumentList argumentList)
4802 {
4803 if (havetempdecl)
4804 {
4805 TemplateDeclaration tempdecl = this.tempdecl.isTemplateDeclaration();
4806 assert(tempdecl);
4807 assert(tempdecl._scope);
4808 // Deduce tdtypes
4809 tdtypes.setDim(tempdecl.parameters.length);
4810 if (!matchWithInstance(sc, tempdecl, this, tdtypes, argumentList, 2))
4811 {
4812 .error(loc, "%s `%s` incompatible arguments for template instantiation", kind, toPrettyChars);
4813 return false;
4814 }
4815 // TODO: Normalizing tiargs for https://issues.dlang.org/show_bug.cgi?id=7469 is necessary?
4816 return true;
4817 }
4818
4819 static if (LOG)
4820 {
4821 printf("TemplateInstance.findBestMatch()\n");
4822 }
4823
4824 uint errs = global.errors;
4825 TemplateDeclaration td_last = null;
4826 Objects dedtypes;
4827
4828 /* Since there can be multiple TemplateDeclaration's with the same
4829 * name, look for the best match.
4830 */
4831 auto tovers = tempdecl.isOverloadSet();
4832 foreach (size_t oi; 0 .. tovers ? tovers.a.length : 1)
4833 {
4834 TemplateDeclaration td_best;
4835 TemplateDeclaration td_ambig;
4836 MATCH m_best = MATCH.nomatch;
4837
4838 Dsymbol dstart = tovers ? tovers.a[oi] : tempdecl;
4839 overloadApply(dstart, (Dsymbol s)
4840 {
4841 auto td = s.isTemplateDeclaration();
4842 if (!td)
4843 return 0;
4844 if (td == td_best) // skip duplicates
4845 return 0;
4846
4847 //printf("td = %s\n", td.toPrettyChars());
4848 // If more arguments than parameters,
4849 // then this is no match.
4850 if (td.parameters.length < tiargs.length)
4851 {
4852 if (!td.isVariadic())
4853 return 0;
4854 }
4855
4856 dedtypes.setDim(td.parameters.length);
4857 dedtypes.zero();
4858 assert(td.semanticRun != PASS.initial);
4859
4860 MATCH m = matchWithInstance(sc, td, this, dedtypes, argumentList, 0);
4861 //printf("matchWithInstance = %d\n", m);
4862 if (m == MATCH.nomatch) // no match at all
4863 return 0;
4864 if (m < m_best) goto Ltd_best;
4865 if (m > m_best) goto Ltd;
4866
4867 // Disambiguate by picking the most specialized TemplateDeclaration
4868 {
4869 MATCH c1 = leastAsSpecialized(sc, td, td_best, argumentList);
4870 MATCH c2 = leastAsSpecialized(sc, td_best, td, argumentList);
4871 //printf("c1 = %d, c2 = %d\n", c1, c2);
4872 if (c1 > c2) goto Ltd;
4873 if (c1 < c2) goto Ltd_best;
4874 }
4875
4876 td_ambig = td;
4877 return 0;
4878
4879 Ltd_best:
4880 // td_best is the best match so far
4881 td_ambig = null;
4882 return 0;
4883
4884 Ltd:
4885 // td is the new best match
4886 td_ambig = null;
4887 td_best = td;
4888 m_best = m;
4889 tdtypes.setDim(dedtypes.length);
4890 memcpy(tdtypes.tdata(), dedtypes.tdata(), tdtypes.length * (void*).sizeof);
4891 return 0;
4892 });
4893
4894 if (td_ambig)
4895 {
4896 .error(loc, "%s `%s.%s` matches more than one template declaration:",
4897 td_best.kind(), td_best.parent.toPrettyChars(), td_best.ident.toChars());
4898 .errorSupplemental(td_best.loc, "`%s`\nand:", td_best.toChars());
4899 .errorSupplemental(td_ambig.loc, "`%s`", td_ambig.toChars());
4900 return false;
4901 }
4902 if (td_best)
4903 {
4904 if (!td_last)
4905 td_last = td_best;
4906 else if (td_last != td_best)
4907 {
4908 ScopeDsymbol.multiplyDefined(loc, td_last, td_best);
4909 return false;
4910 }
4911 }
4912 }
4913
4914 if (td_last)
4915 {
4916 /* https://issues.dlang.org/show_bug.cgi?id=7469
4917 * Normalize tiargs by using corresponding deduced
4918 * template value parameters and tuples for the correct mangling.
4919 *
4920 * By doing this before hasNestedArgs, CTFEable local variable will be
4921 * accepted as a value parameter. For example:
4922 *
4923 * void foo() {
4924 * struct S(int n) {} // non-global template
4925 * const int num = 1; // CTFEable local variable
4926 * S!num s; // S!1 is instantiated, not S!num
4927 * }
4928 */
4929 size_t dim = td_last.parameters.length - (td_last.isVariadic() ? 1 : 0);
4930 for (size_t i = 0; i < dim; i++)
4931 {
4932 if (tiargs.length <= i)
4933 tiargs.push(tdtypes[i]);
4934 assert(i < tiargs.length);
4935
4936 auto tvp = (*td_last.parameters)[i].isTemplateValueParameter();
4937 if (!tvp)
4938 continue;
4939 assert(tdtypes[i]);
4940 // tdtypes[i] is already normalized to the required type in matchArg
4941
4942 (*tiargs)[i] = tdtypes[i];
4943 }
4944 if (td_last.isVariadic() && tiargs.length == dim && tdtypes[dim])
4945 {
4946 Tuple va = isTuple(tdtypes[dim]);
4947 assert(va);
4948 tiargs.pushSlice(va.objects[]);
4949 }
4950 }
4951 else if (errors && inst)
4952 {
4953 // instantiation was failed with error reporting
4954 assert(global.errors);
4955 return false;
4956 }
4957 else
4958 {
4959 auto tdecl = tempdecl.isTemplateDeclaration();
4960
4961 if (errs != global.errors)
4962 errorSupplemental(loc, "while looking for match for `%s`", toChars());
4963 else if (tdecl && !tdecl.overnext)
4964 {
4965 // Only one template, so we can give better error message
4966 const(char)* msg = "does not match template declaration";
4967 const(char)* tip;
4968 OutBuffer buf;
4969 HdrGenState hgs;
4970 hgs.skipConstraints = true;
4971 toCharsMaybeConstraints(tdecl, buf, hgs);
4972 const tmsg = buf.peekChars();
4973 const cmsg = tdecl.getConstraintEvalError(tip);
4974 if (cmsg)
4975 {
4976 .error(loc, "%s `%s` %s `%s`\n%s", kind, toPrettyChars, msg, tmsg, cmsg);
4977 if (tip)
4978 .tip(tip);
4979 }
4980 else
4981 {
4982 .error(loc, "%s `%s` %s `%s`", kind, toPrettyChars, msg, tmsg);
4983
4984 if (tdecl.parameters.length == tiargs.length)
4985 {
4986 // https://issues.dlang.org/show_bug.cgi?id=7352
4987 // print additional information, e.g. `foo` is not a type
4988 foreach (i, param; *tdecl.parameters)
4989 {
4990 MATCH match = param.matchArg(loc, sc, tiargs, i, tdecl.parameters, dedtypes, null);
4991 auto arg = (*tiargs)[i];
4992 auto sym = arg.isDsymbol;
4993 auto exp = arg.isExpression;
4994
4995 if (exp)
4996 exp = exp.optimize(WANTvalue);
4997
4998 if (match == MATCH.nomatch &&
4999 ((sym && sym.isFuncDeclaration) ||
5000 (exp && exp.isVarExp)))
5001 {
5002 if (param.isTemplateTypeParameter)
5003 errorSupplemental(loc, "`%s` is not a type", arg.toChars);
5004 else if (auto tvp = param.isTemplateValueParameter)
5005 errorSupplemental(loc, "`%s` is not of a value of type `%s`",
5006 arg.toChars, tvp.valType.toChars);
5007
5008 }
5009 }
5010 }
5011 }
5012 }
5013 else
5014 {
5015 .error(loc, "%s `%s` does not match any template declaration", kind(), toPrettyChars());
5016 bool found;
5017 overloadApply(tempdecl, (s){
5018 if (!found)
5019 errorSupplemental(loc, "Candidates are:");
5020 found = true;
5021 errorSupplemental(s.loc, "%s", s.toChars());
5022 return 0;
5023 });
5024 }
5025 return false;
5026 }
5027
5028 /* The best match is td_last
5029 */
5030 tempdecl = td_last;
5031
5032 static if (LOG)
5033 {
5034 printf("\tIt's a match with template declaration '%s'\n", tempdecl.toChars());
5035 }
5036 return (errs == global.errors);
5037 }
5038
5039 /*****************************************************
5040 * Determine if template instance is really a template function,
5041 * and that template function needs to infer types from the function
5042 * arguments.
5043 *
5044 * Like findBestMatch, iterate possible template candidates,
5045 * but just looks only the necessity of type inference.
5046 */
5047 extern (D) final bool needsTypeInference(Scope* sc, int flag = 0)
5048 {
5049 //printf("TemplateInstance.needsTypeInference() %s\n", toChars());
5050 if (semanticRun != PASS.initial)
5051 return false;
5052
5053 uint olderrs = global.errors;
5054 Objects dedtypes;
5055 size_t count = 0;
5056
5057 auto tovers = tempdecl.isOverloadSet();
5058 foreach (size_t oi; 0 .. tovers ? tovers.a.length : 1)
5059 {
5060 Dsymbol dstart = tovers ? tovers.a[oi] : tempdecl;
5061 int r = overloadApply(dstart, (Dsymbol s)
5062 {
5063 auto td = s.isTemplateDeclaration();
5064 if (!td)
5065 return 0;
5066
5067 /* If any of the overloaded template declarations need inference,
5068 * then return true
5069 */
5070 if (!td.onemember)
5071 return 0;
5072 if (auto td2 = td.onemember.isTemplateDeclaration())
5073 {
5074 if (!td2.onemember || !td2.onemember.isFuncDeclaration())
5075 return 0;
5076 if (tiargs.length >= td.parameters.length - (td.isVariadic() ? 1 : 0))
5077 return 0;
5078 return 1;
5079 }
5080 auto fd = td.onemember.isFuncDeclaration();
5081 if (!fd || fd.type.ty != Tfunction)
5082 return 0;
5083
5084 foreach (tp; *td.parameters)
5085 {
5086 if (tp.isTemplateThisParameter())
5087 return 1;
5088 }
5089
5090 /* Determine if the instance arguments, tiargs, are all that is necessary
5091 * to instantiate the template.
5092 */
5093 //printf("tp = %p, td.parameters.length = %d, tiargs.length = %d\n", tp, td.parameters.length, tiargs.length);
5094 auto tf = fd.type.isTypeFunction();
5095 if (tf.parameterList.length)
5096 {
5097 auto tp = td.isVariadic();
5098 if (tp && td.parameters.length > 1)
5099 return 1;
5100
5101 if (!tp && tiargs.length < td.parameters.length)
5102 {
5103 // Can remain tiargs be filled by default arguments?
5104 foreach (size_t i; tiargs.length .. td.parameters.length)
5105 {
5106 if (!(*td.parameters)[i].hasDefaultArg())
5107 return 1;
5108 }
5109 }
5110
5111 foreach (i, fparam; tf.parameterList)
5112 {
5113 // 'auto ref' needs inference.
5114 if (fparam.storageClass & STC.auto_)
5115 return 1;
5116 }
5117 }
5118
5119 if (!flag)
5120 {
5121 /* Calculate the need for overload resolution.
5122 * When only one template can match with tiargs, inference is not necessary.
5123 */
5124 dedtypes.setDim(td.parameters.length);
5125 dedtypes.zero();
5126 if (td.semanticRun == PASS.initial)
5127 {
5128 if (td._scope)
5129 {
5130 // Try to fix forward reference. Ungag errors while doing so.
5131 Ungag ungag = td.ungagSpeculative();
5132 td.dsymbolSemantic(td._scope);
5133 }
5134 if (td.semanticRun == PASS.initial)
5135 {
5136 .error(loc, "%s `%s` `%s` forward references template declaration `%s`", kind, toPrettyChars, toChars(), td.toChars());
5137 return 1;
5138 }
5139 }
5140 MATCH m = matchWithInstance(sc, td, this, dedtypes, ArgumentList(), 0);
5141 if (m == MATCH.nomatch)
5142 return 0;
5143 }
5144
5145 /* If there is more than one function template which matches, we may
5146 * need type inference (see https://issues.dlang.org/show_bug.cgi?id=4430)
5147 */
5148 return ++count > 1 ? 1 : 0;
5149 });
5150 if (r)
5151 return true;
5152 }
5153
5154 if (olderrs != global.errors)
5155 {
5156 if (!global.gag)
5157 {
5158 errorSupplemental(loc, "while looking for match for `%s`", toChars());
5159 semanticRun = PASS.semanticdone;
5160 inst = this;
5161 }
5162 errors = true;
5163 }
5164 //printf("false\n");
5165 return false;
5166 }
5167
5168 /*****************************************
5169 * Determines if a TemplateInstance will need a nested
5170 * generation of the TemplateDeclaration.
5171 * Sets enclosing property if so, and returns != 0;
5172 */
5173 extern (D) final bool hasNestedArgs(Objects* args, bool isstatic)
5174 {
5175 int nested = 0;
5176 //printf("TemplateInstance.hasNestedArgs('%s')\n", tempdecl.ident.toChars());
5177
5178 // arguments from parent instances are also accessible
5179 if (!enclosing)
5180 {
5181 if (TemplateInstance ti = tempdecl.toParent().isTemplateInstance())
5182 enclosing = ti.enclosing;
5183 }
5184
5185 /* A nested instance happens when an argument references a local
5186 * symbol that is on the stack.
5187 */
5188 foreach (o; *args)
5189 {
5190 Expression ea = isExpression(o);
5191 Dsymbol sa = isDsymbol(o);
5192 Tuple va = isTuple(o);
5193 if (ea)
5194 {
5195 if (auto ve = ea.isVarExp())
5196 {
5197 sa = ve.var;
5198 goto Lsa;
5199 }
5200 if (auto te = ea.isThisExp())
5201 {
5202 sa = te.var;
5203 goto Lsa;
5204 }
5205 if (auto fe = ea.isFuncExp())
5206 {
5207 if (fe.td)
5208 sa = fe.td;
5209 else
5210 sa = fe.fd;
5211 goto Lsa;
5212 }
5213 // Emulate Expression.toMangleBuffer call that had exist in TemplateInstance.genIdent.
5214 if (ea.op != EXP.int64 && ea.op != EXP.float64 && ea.op != EXP.complex80 && ea.op != EXP.null_ && ea.op != EXP.string_ && ea.op != EXP.arrayLiteral && ea.op != EXP.assocArrayLiteral && ea.op != EXP.structLiteral)
5215 {
5216 if (!ea.type.isTypeError())
5217 .error(ea.loc, "%s `%s` expression `%s` is not a valid template value argument", kind, toPrettyChars, ea.toChars());
5218 errors = true;
5219 }
5220 }
5221 else if (sa)
5222 {
5223 Lsa:
5224 sa = sa.toAlias();
5225 TemplateDeclaration td = sa.isTemplateDeclaration();
5226 if (td)
5227 {
5228 TemplateInstance ti = sa.toParent().isTemplateInstance();
5229 if (ti && ti.enclosing)
5230 sa = ti;
5231 }
5232 TemplateInstance ti = sa.isTemplateInstance();
5233 Declaration d = sa.isDeclaration();
5234 if ((td && td.literal) || (ti && ti.enclosing) || (d && !d.isDataseg() && !(d.storage_class & STC.manifest) && (!d.isFuncDeclaration() || d.isFuncDeclaration().isNested()) && !isTemplateMixin()))
5235 {
5236 Dsymbol dparent = sa.toParent2();
5237 if (!dparent || dparent.isModule)
5238 goto L1;
5239 else if (!enclosing)
5240 enclosing = dparent;
5241 else if (enclosing != dparent)
5242 {
5243 /* Select the more deeply nested of the two.
5244 * Error if one is not nested inside the other.
5245 */
5246 for (Dsymbol p = enclosing; p; p = p.parent)
5247 {
5248 if (p == dparent)
5249 goto L1; // enclosing is most nested
5250 }
5251 for (Dsymbol p = dparent; p; p = p.parent)
5252 {
5253 if (p == enclosing)
5254 {
5255 enclosing = dparent;
5256 goto L1; // dparent is most nested
5257 }
5258 }
5259 //https://issues.dlang.org/show_bug.cgi?id=17870
5260 if (dparent.isClassDeclaration() && enclosing.isClassDeclaration())
5261 {
5262 auto pc = dparent.isClassDeclaration();
5263 auto ec = enclosing.isClassDeclaration();
5264 if (pc.isBaseOf(ec, null))
5265 goto L1;
5266 else if (ec.isBaseOf(pc, null))
5267 {
5268 enclosing = dparent;
5269 goto L1;
5270 }
5271 }
5272 .error(loc, "%s `%s` `%s` is nested in both `%s` and `%s`", kind, toPrettyChars, toChars(), enclosing.toChars(), dparent.toChars());
5273 errors = true;
5274 }
5275 L1:
5276 //printf("\tnested inside %s as it references %s\n", enclosing.toChars(), sa.toChars());
5277 nested |= 1;
5278 }
5279 }
5280 else if (va)
5281 {
5282 nested |= cast(int)hasNestedArgs(&va.objects, isstatic);
5283 }
5284 }
5285 //printf("-TemplateInstance.hasNestedArgs('%s') = %d\n", tempdecl.ident.toChars(), nested);
5286 return nested != 0;
5287 }
5288
5289 /*****************************************
5290 * Append 'this' to the specific module members[]
5291 */
5292 extern (D) final Dsymbols* appendToModuleMember()
5293 {
5294 Module mi = minst; // instantiated . inserted module
5295
5296 //printf("%s.appendToModuleMember() enclosing = %s mi = %s\n",
5297 // toPrettyChars(),
5298 // enclosing ? enclosing.toPrettyChars() : null,
5299 // mi ? mi.toPrettyChars() : null);
5300 if (global.params.allInst || !mi || mi.isRoot())
5301 {
5302 /* If the instantiated module is speculative or root, insert to the
5303 * member of a root module. Then:
5304 * - semantic3 pass will get called on the instance members.
5305 * - codegen pass will get a selection chance to do/skip it (needsCodegen()).
5306 */
5307 static Dsymbol getStrictEnclosing(TemplateInstance ti)
5308 {
5309 do
5310 {
5311 if (ti.enclosing)
5312 return ti.enclosing;
5313 ti = ti.tempdecl.isInstantiated();
5314 } while (ti);
5315 return null;
5316 }
5317
5318 Dsymbol enc = getStrictEnclosing(this);
5319 // insert target is made stable by using the module
5320 // where tempdecl is declared.
5321 mi = (enc ? enc : tempdecl).getModule();
5322 if (!mi.isRoot())
5323 {
5324 if (mi.importedFrom)
5325 {
5326 mi = mi.importedFrom;
5327 assert(mi.isRoot());
5328 }
5329 else
5330 {
5331 // This can happen when using the frontend as a library.
5332 // Append it to the non-root module.
5333 }
5334 }
5335 }
5336 else
5337 {
5338 /* If the instantiated module is non-root, insert to the member of the
5339 * non-root module. Then:
5340 * - semantic3 pass won't be called on the instance.
5341 * - codegen pass won't reach to the instance.
5342 * Unless it is re-appended to a root module later (with changed minst).
5343 */
5344 }
5345 //printf("\t-. mi = %s\n", mi.toPrettyChars());
5346
5347 if (memberOf) // already appended to some module
5348 {
5349 assert(mi.isRoot(), "can only re-append to a root module");
5350 if (memberOf.isRoot())
5351 return null; // no need to move to another root module
5352 }
5353
5354 Dsymbols* a = mi.members;
5355 a.push(this);
5356 memberOf = mi;
5357 if (mi.semanticRun >= PASS.semantic2done && mi.isRoot())
5358 Module.addDeferredSemantic2(this);
5359 if (mi.semanticRun >= PASS.semantic3done && mi.isRoot())
5360 Module.addDeferredSemantic3(this);
5361 return a;
5362 }
5363
5364 /****************************************************
5365 * Declare parameters of template instance, initialize them with the
5366 * template instance arguments.
5367 */
5368 extern (D) final void declareParameters(Scope* sc)
5369 {
5370 TemplateDeclaration tempdecl = this.tempdecl.isTemplateDeclaration();
5371 assert(tempdecl);
5372
5373 //printf("TemplateInstance.declareParameters()\n");
5374 foreach (i, o; tdtypes) // initializer for tp
5375 {
5376 TemplateParameter tp = (*tempdecl.parameters)[i];
5377 //printf("\ttdtypes[%d] = %p\n", i, o);
5378 declareParameter(tempdecl, sc, tp, o);
5379 }
5380 }
5381
5382 /****************************************
5383 * This instance needs an identifier for name mangling purposes.
5384 * Create one by taking the template declaration name and adding
5385 * the type signature for it.
5386 */
5387 extern (D) final Identifier genIdent(Objects* args)
5388 {
5389 //printf("TemplateInstance.genIdent('%s')\n", tempdecl.ident.toChars());
5390 assert(args is tiargs);
5391 OutBuffer buf;
5392 mangleToBuffer(this, buf);
5393 //printf("\tgenIdent = %s\n", buf.peekChars());
5394 return Identifier.idPool(buf[]);
5395 }
5396
5397 extern (D) final void expandMembers(Scope* sc2)
5398 {
5399 members.foreachDsymbol( (s) { s.setScope (sc2); } );
5400
5401 members.foreachDsymbol( (s) { s.importAll(sc2); } );
5402
5403 if (!aliasdecl)
5404 {
5405 /* static if's are crucial to evaluating aliasdecl correctly. But
5406 * evaluating the if/else bodies may require aliasdecl.
5407 * So, evaluate the condition for static if's, but not their if/else bodies.
5408 * Then try to set aliasdecl.
5409 * Later do the if/else bodies.
5410 * https://issues.dlang.org/show_bug.cgi?id=23598
5411 * It might be better to do this by attaching a lambda to the StaticIfDeclaration
5412 * to do the oneMembers call after the sid.include(sc2) is run as part of dsymbolSemantic().
5413 */
5414 bool done;
5415 void staticIfDg(Dsymbol s)
5416 {
5417 if (done || aliasdecl)
5418 return;
5419 //printf("\t staticIfDg on '%s %s' in '%s'\n", s.kind(), s.toChars(), this.toChars());
5420 if (!s.isStaticIfDeclaration())
5421 {
5422 //s.dsymbolSemantic(sc2);
5423 done = true;
5424 return;
5425 }
5426 auto sid = s.isStaticIfDeclaration();
5427 sid.include(sc2);
5428 if (members.length)
5429 {
5430 Dsymbol sa;
5431 if (Dsymbol.oneMembers(members, sa, tempdecl.ident) && sa)
5432 aliasdecl = sa;
5433 }
5434 done = true;
5435 }
5436
5437 members.foreachDsymbol(&staticIfDg);
5438 }
5439
5440 void symbolDg(Dsymbol s)
5441 {
5442 //printf("\t semantic on '%s' %p kind %s in '%s'\n", s.toChars(), s, s.kind(), this.toChars());
5443 //printf("test: enclosing = %d, sc2.parent = %s\n", enclosing, sc2.parent.toChars());
5444 //if (enclosing)
5445 // s.parent = sc.parent;
5446 //printf("test3: enclosing = %d, s.parent = %s\n", enclosing, s.parent.toChars());
5447 s.dsymbolSemantic(sc2);
5448 //printf("test4: enclosing = %d, s.parent = %s\n", enclosing, s.parent.toChars());
5449 Module.runDeferredSemantic();
5450 }
5451
5452 members.foreachDsymbol(&symbolDg);
5453 }
5454
5455 extern (D) final void tryExpandMembers(Scope* sc2)
5456 {
5457 __gshared int nest;
5458 // extracted to a function to allow windows SEH to work without destructors in the same function
5459 //printf("%d\n", nest);
5460 if (++nest > global.recursionLimit)
5461 {
5462 global.gag = 0; // ensure error message gets printed
5463 .error(loc, "%s `%s` recursive expansion exceeded allowed nesting limit", kind, toPrettyChars);
5464 fatal();
5465 }
5466
5467 expandMembers(sc2);
5468
5469 nest--;
5470 }
5471
5472 extern (D) final void trySemantic3(Scope* sc2)
5473 {
5474 // extracted to a function to allow windows SEH to work without destructors in the same function
5475 __gshared int nest;
5476 //printf("%d\n", nest);
5477 if (++nest > global.recursionLimit)
5478 {
5479 global.gag = 0; // ensure error message gets printed
5480 .error(loc, "%s `%s` recursive expansion exceeded allowed nesting limit", kind, toPrettyChars);
5481 fatal();
5482 }
5483
5484 semantic3(this, sc2);
5485
5486 --nest;
5487 }
5488
5489 override final inout(TemplateInstance) isTemplateInstance() inout
5490 {
5491 return this;
5492 }
5493
5494 override void accept(Visitor v)
5495 {
5496 v.visit(this);
5497 }
5498 }
5499
5500 /**************************************
5501 * IsExpression can evaluate the specified type speculatively, and even if
5502 * it instantiates any symbols, they are normally unnecessary for the
5503 * final executable.
5504 * However, if those symbols leak to the actual code, compiler should remark
5505 * them as non-speculative to generate their code and link to the final executable.
5506 */
5507 void unSpeculative(Scope* sc, RootObject o)
5508 {
5509 if (!o)
5510 return;
5511
5512 if (Tuple tup = isTuple(o))
5513 {
5514 foreach (obj; tup.objects)
5515 {
5516 unSpeculative(sc, obj);
5517 }
5518 return;
5519 }
5520
5521 Dsymbol s = getDsymbol(o);
5522 if (!s)
5523 return;
5524
5525 if (Declaration d = s.isDeclaration())
5526 {
5527 if (VarDeclaration vd = d.isVarDeclaration())
5528 o = vd.type;
5529 else if (AliasDeclaration ad = d.isAliasDeclaration())
5530 {
5531 o = ad.getType();
5532 if (!o)
5533 o = ad.toAlias();
5534 }
5535 else
5536 o = d.toAlias();
5537
5538 s = getDsymbol(o);
5539 if (!s)
5540 return;
5541 }
5542
5543 if (TemplateInstance ti = s.isTemplateInstance())
5544 {
5545 // If the instance is already non-speculative,
5546 // or it is leaked to the speculative scope.
5547 if (ti.minst !is null || sc.minst is null)
5548 return;
5549
5550 // Remark as non-speculative instance.
5551 ti.minst = sc.minst;
5552 if (!ti.tinst)
5553 ti.tinst = sc.tinst;
5554
5555 unSpeculative(sc, ti.tempdecl);
5556 }
5557
5558 if (TemplateInstance ti = s.isInstantiated())
5559 unSpeculative(sc, ti);
5560 }
5561
5562 /**********************************
5563 * Return true if e could be valid only as a template value parameter.
5564 * Return false if it might be an alias or tuple.
5565 * (Note that even in this case, it could still turn out to be a value).
5566 */
5567 bool definitelyValueParameter(Expression e) @safe
5568 {
5569 // None of these can be value parameters
5570 if (e.op == EXP.tuple || e.op == EXP.scope_ ||
5571 e.op == EXP.type || e.op == EXP.dotType ||
5572 e.op == EXP.template_ || e.op == EXP.dotTemplateDeclaration ||
5573 e.op == EXP.function_ || e.op == EXP.error ||
5574 e.op == EXP.this_ || e.op == EXP.super_ ||
5575 e.op == EXP.dot)
5576 return false;
5577
5578 if (e.op != EXP.dotVariable)
5579 return true;
5580
5581 /* Template instantiations involving a DotVar expression are difficult.
5582 * In most cases, they should be treated as a value parameter, and interpreted.
5583 * But they might also just be a fully qualified name, which should be treated
5584 * as an alias.
5585 */
5586
5587 // x.y.f cannot be a value
5588 FuncDeclaration f = e.isDotVarExp().var.isFuncDeclaration();
5589 if (f)
5590 return false;
5591
5592 while (e.op == EXP.dotVariable)
5593 {
5594 e = e.isDotVarExp().e1;
5595 }
5596 // this.x.y and super.x.y couldn't possibly be valid values.
5597 if (e.op == EXP.this_ || e.op == EXP.super_)
5598 return false;
5599
5600 // e.type.x could be an alias
5601 if (e.op == EXP.dotType)
5602 return false;
5603
5604 // var.x.y is the only other possible form of alias
5605 if (e.op != EXP.variable)
5606 return true;
5607
5608 VarDeclaration v = e.isVarExp().var.isVarDeclaration();
5609 // func.x.y is not an alias
5610 if (!v)
5611 return true;
5612
5613 // https://issues.dlang.org/show_bug.cgi?id=16685
5614 // var.x.y where var is a constant available at compile time
5615 if (v.storage_class & STC.manifest)
5616 return true;
5617
5618 // TODO: Should we force CTFE if it is a global constant?
5619 return false;
5620 }
5621
5622 /***********************************************************
5623 * https://dlang.org/spec/template-mixin.html
5624 * Syntax:
5625 * mixin MixinTemplateName [TemplateArguments] [Identifier];
5626 */
5627 extern (C++) final class TemplateMixin : TemplateInstance
5628 {
5629 TypeQualified tqual;
5630
5631 extern (D) this(const ref Loc loc, Identifier ident, TypeQualified tqual, Objects* tiargs)
5632 {
5633 super(loc,
5634 tqual.idents.length ? cast(Identifier)tqual.idents[tqual.idents.length - 1] : (cast(TypeIdentifier)tqual).ident,
5635 tiargs ? tiargs : new Objects());
5636 //printf("TemplateMixin(ident = '%s')\n", ident ? ident.toChars() : "");
5637 this.ident = ident;
5638 this.tqual = tqual;
5639 }
5640
5641 override TemplateInstance syntaxCopy(Dsymbol s)
5642 {
5643 auto tm = new TemplateMixin(loc, ident, tqual.syntaxCopy(), tiargs);
5644 return TemplateInstance.syntaxCopy(tm);
5645 }
5646
5647 override const(char)* kind() const
5648 {
5649 return "mixin";
5650 }
5651
5652 override bool oneMember(out Dsymbol ps, Identifier ident)
5653 {
5654 return Dsymbol.oneMember(ps, ident);
5655 }
5656
5657 override bool hasPointers()
5658 {
5659 //printf("TemplateMixin.hasPointers() %s\n", toChars());
5660 return members.foreachDsymbol( (s) { return s.hasPointers(); } ) != 0;
5661 }
5662
5663 override const(char)* toChars() const
5664 {
5665 OutBuffer buf;
5666 toCBufferInstance(this, buf);
5667 return buf.extractChars();
5668 }
5669
5670 extern (D) bool findTempDecl(Scope* sc)
5671 {
5672 // Follow qualifications to find the TemplateDeclaration
5673 if (!tempdecl)
5674 {
5675 Expression e;
5676 Type t;
5677 Dsymbol s;
5678 tqual.resolve(loc, sc, e, t, s);
5679 if (!s)
5680 {
5681 .error(loc, "%s `%s` is not defined", kind, toPrettyChars);
5682 return false;
5683 }
5684 s = s.toAlias();
5685 tempdecl = s.isTemplateDeclaration();
5686 OverloadSet os = s.isOverloadSet();
5687
5688 /* If an OverloadSet, look for a unique member that is a template declaration
5689 */
5690 if (os)
5691 {
5692 Dsymbol ds = null;
5693 foreach (i, sym; os.a)
5694 {
5695 Dsymbol s2 = sym.isTemplateDeclaration();
5696 if (s2)
5697 {
5698 if (ds)
5699 {
5700 tempdecl = os;
5701 break;
5702 }
5703 ds = s2;
5704 }
5705 }
5706 }
5707 if (!tempdecl)
5708 {
5709 .error(loc, "%s `%s` - `%s` is a %s, not a template", kind, toPrettyChars, s.toChars(), s.kind());
5710 return false;
5711 }
5712 }
5713 assert(tempdecl);
5714
5715 // Look for forward references
5716 auto tovers = tempdecl.isOverloadSet();
5717 foreach (size_t oi; 0 .. tovers ? tovers.a.length : 1)
5718 {
5719 Dsymbol dstart = tovers ? tovers.a[oi] : tempdecl;
5720 int r = overloadApply(dstart, (Dsymbol s)
5721 {
5722 auto td = s.isTemplateDeclaration();
5723 if (!td)
5724 return 0;
5725
5726 if (td.semanticRun == PASS.initial)
5727 {
5728 if (td._scope)
5729 td.dsymbolSemantic(td._scope);
5730 else
5731 {
5732 semanticRun = PASS.initial;
5733 return 1;
5734 }
5735 }
5736 return 0;
5737 });
5738 if (r)
5739 return false;
5740 }
5741 return true;
5742 }
5743
5744 override inout(TemplateMixin) isTemplateMixin() inout
5745 {
5746 return this;
5747 }
5748
5749 override void accept(Visitor v)
5750 {
5751 v.visit(this);
5752 }
5753 }
5754
5755 /************************************
5756 * This struct is needed for TemplateInstance to be the key in an associative array.
5757 * Fixing https://issues.dlang.org/show_bug.cgi?id=15813 would make it unnecessary.
5758 */
5759 struct TemplateInstanceBox
5760 {
5761 TemplateInstance ti;
5762
5763 this(TemplateInstance ti)
5764 {
5765 this.ti = ti;
5766 this.ti.toHash();
5767 assert(this.ti.hash);
5768 }
5769
5770 size_t toHash() const @trusted pure nothrow
5771 {
5772 assert(ti.hash);
5773 return ti.hash;
5774 }
5775
5776 bool opEquals(ref const TemplateInstanceBox s) @trusted const
5777 {
5778 bool res = void;
5779 if (ti.inst && s.ti.inst)
5780 {
5781 /* This clause is only used when an instance with errors
5782 * is replaced with a correct instance.
5783 */
5784 res = ti is s.ti;
5785 }
5786 else
5787 {
5788 /* Used when a proposed instance is used to see if there's
5789 * an existing instance.
5790 */
5791 static if (__VERSION__ < 2099) // https://issues.dlang.org/show_bug.cgi?id=22717
5792 res = (cast()s.ti).equalsx(cast()ti);
5793 else
5794 res = (cast()ti).equalsx(cast()s.ti);
5795 }
5796
5797 debug (FindExistingInstance) ++(res ? nHits : nCollisions);
5798 return res;
5799 }
5800
5801 debug (FindExistingInstance)
5802 {
5803 __gshared uint nHits, nCollisions;
5804
5805 shared static ~this()
5806 {
5807 printf("debug (FindExistingInstance) TemplateInstanceBox.equals hits: %u collisions: %u\n",
5808 nHits, nCollisions);
5809 }
5810 }
5811 }
5812
5813 /*******************************************
5814 * Match to a particular TemplateParameter.
5815 * Input:
5816 * instLoc location that the template is instantiated.
5817 * tiargs[] actual arguments to template instance
5818 * i i'th argument
5819 * parameters[] template parameters
5820 * dedtypes[] deduced arguments to template instance
5821 * *psparam set to symbol declared and initialized to dedtypes[i]
5822 */
5823 MATCH matchArg(TemplateParameter tp, Loc instLoc, Scope* sc, Objects* tiargs, size_t i, TemplateParameters* parameters, ref Objects dedtypes, Declaration* psparam)
5824 {
5825 MATCH matchArgNoMatch()
5826 {
5827 if (psparam)
5828 *psparam = null;
5829 return MATCH.nomatch;
5830 }
5831
5832 MATCH matchArgParameter()
5833 {
5834 RootObject oarg;
5835
5836 if (i < tiargs.length)
5837 oarg = (*tiargs)[i];
5838 else
5839 {
5840 // Get default argument instead
5841 oarg = tp.defaultArg(instLoc, sc);
5842 if (!oarg)
5843 {
5844 assert(i < dedtypes.length);
5845 // It might have already been deduced
5846 oarg = dedtypes[i];
5847 if (!oarg)
5848 return matchArgNoMatch();
5849 }
5850 }
5851 return tp.matchArg(sc, oarg, i, parameters, dedtypes, psparam);
5852 }
5853
5854 MATCH matchArgTuple(TemplateTupleParameter ttp)
5855 {
5856 /* The rest of the actual arguments (tiargs[]) form the match
5857 * for the variadic parameter.
5858 */
5859 assert(i + 1 == dedtypes.length); // must be the last one
5860 Tuple ovar;
5861
5862 if (Tuple u = isTuple(dedtypes[i]))
5863 {
5864 // It has already been deduced
5865 ovar = u;
5866 }
5867 else if (i + 1 == tiargs.length && isTuple((*tiargs)[i]))
5868 ovar = isTuple((*tiargs)[i]);
5869 else
5870 {
5871 ovar = new Tuple();
5872 //printf("ovar = %p\n", ovar);
5873 if (i < tiargs.length)
5874 {
5875 //printf("i = %d, tiargs.length = %d\n", i, tiargs.length);
5876 ovar.objects.setDim(tiargs.length - i);
5877 foreach (j, ref obj; ovar.objects)
5878 obj = (*tiargs)[i + j];
5879 }
5880 }
5881 return ttp.matchArg(sc, ovar, i, parameters, dedtypes, psparam);
5882 }
5883
5884 if (auto ttp = tp.isTemplateTupleParameter())
5885 return matchArgTuple(ttp);
5886 else
5887 return matchArgParameter();
5888 }
5889
5890 MATCH matchArg(TemplateParameter tp, Scope* sc, RootObject oarg, size_t i, TemplateParameters* parameters, ref Objects dedtypes, Declaration* psparam)
5891 {
5892 MATCH matchArgNoMatch()
5893 {
5894 //printf("\tm = %d\n", MATCH.nomatch);
5895 if (psparam)
5896 *psparam = null;
5897 return MATCH.nomatch;
5898 }
5899
5900 MATCH matchArgType(TemplateTypeParameter ttp)
5901 {
5902 //printf("TemplateTypeParameter.matchArg('%s')\n", ttp.ident.toChars());
5903 MATCH m = MATCH.exact;
5904 Type ta = isType(oarg);
5905 if (!ta)
5906 {
5907 //printf("%s %p %p %p\n", oarg.toChars(), isExpression(oarg), isDsymbol(oarg), isTuple(oarg));
5908 return matchArgNoMatch();
5909 }
5910 //printf("ta is %s\n", ta.toChars());
5911
5912 if (ttp.specType)
5913 {
5914 if (!ta || ta == TemplateTypeParameter.tdummy)
5915 return matchArgNoMatch();
5916
5917 //printf("\tcalling deduceType(): ta is %s, specType is %s\n", ta.toChars(), ttp.specType.toChars());
5918 MATCH m2 = deduceType(ta, sc, ttp.specType, *parameters, dedtypes);
5919 if (m2 == MATCH.nomatch)
5920 {
5921 //printf("\tfailed deduceType\n");
5922 return matchArgNoMatch();
5923 }
5924
5925 if (m2 < m)
5926 m = m2;
5927 if (dedtypes[i])
5928 {
5929 Type t = cast(Type)dedtypes[i];
5930
5931 if (ttp.dependent && !t.equals(ta)) // https://issues.dlang.org/show_bug.cgi?id=14357
5932 return matchArgNoMatch();
5933
5934 /* This is a self-dependent parameter. For example:
5935 * template X(T : T*) {}
5936 * template X(T : S!T, alias S) {}
5937 */
5938 //printf("t = %s ta = %s\n", t.toChars(), ta.toChars());
5939 ta = t;
5940 }
5941 }
5942 else
5943 {
5944 if (dedtypes[i])
5945 {
5946 // Must match already deduced type
5947 Type t = cast(Type)dedtypes[i];
5948
5949 if (!t.equals(ta))
5950 {
5951 //printf("t = %s ta = %s\n", t.toChars(), ta.toChars());
5952 return matchArgNoMatch();
5953 }
5954 }
5955 else
5956 {
5957 // So that matches with specializations are better
5958 m = MATCH.convert;
5959 }
5960 }
5961 dedtypes[i] = ta;
5962
5963 if (psparam)
5964 *psparam = new AliasDeclaration(ttp.loc, ttp.ident, ta);
5965 //printf("\tm = %d\n", m);
5966 return ttp.dependent ? MATCH.exact : m;
5967 }
5968
5969 MATCH matchArgValue(TemplateValueParameter tvp)
5970 {
5971 //printf("TemplateValueParameter.matchArg('%s')\n", tvp.ident.toChars());
5972 MATCH m = MATCH.exact;
5973
5974 Expression ei = isExpression(oarg);
5975 Type vt;
5976
5977 if (!ei && oarg)
5978 {
5979 Dsymbol si = isDsymbol(oarg);
5980 FuncDeclaration f = si ? si.isFuncDeclaration() : null;
5981 if (!f || !f.fbody || f.needThis())
5982 return matchArgNoMatch();
5983
5984 ei = new VarExp(tvp.loc, f);
5985 ei = ei.expressionSemantic(sc);
5986
5987 /* If a function is really property-like, and then
5988 * it's CTFEable, ei will be a literal expression.
5989 */
5990 uint olderrors = global.startGagging();
5991 ei = resolveProperties(sc, ei);
5992 ei = ei.ctfeInterpret();
5993 if (global.endGagging(olderrors) || ei.op == EXP.error)
5994 return matchArgNoMatch();
5995
5996 /* https://issues.dlang.org/show_bug.cgi?id=14520
5997 * A property-like function can match to both
5998 * TemplateAlias and ValueParameter. But for template overloads,
5999 * it should always prefer alias parameter to be consistent
6000 * template match result.
6001 *
6002 * template X(alias f) { enum X = 1; }
6003 * template X(int val) { enum X = 2; }
6004 * int f1() { return 0; } // CTFEable
6005 * int f2(); // body-less function is not CTFEable
6006 * enum x1 = X!f1; // should be 1
6007 * enum x2 = X!f2; // should be 1
6008 *
6009 * e.g. The x1 value must be same even if the f1 definition will be moved
6010 * into di while stripping body code.
6011 */
6012 m = MATCH.convert;
6013 }
6014
6015 if (ei && ei.op == EXP.variable)
6016 {
6017 // Resolve const variables that we had skipped earlier
6018 ei = ei.ctfeInterpret();
6019 }
6020
6021 //printf("\tvalType: %s, ty = %d\n", tvp.valType.toChars(), tvp.valType.ty);
6022 vt = tvp.valType.typeSemantic(tvp.loc, sc);
6023 //printf("ei: %s, ei.type: %s\n", ei.toChars(), ei.type.toChars());
6024 //printf("vt = %s\n", vt.toChars());
6025
6026 if (ei.type)
6027 {
6028 MATCH m2 = ei.implicitConvTo(vt);
6029 //printf("m: %d\n", m);
6030 if (m2 < m)
6031 m = m2;
6032 if (m == MATCH.nomatch)
6033 return matchArgNoMatch();
6034 ei = ei.implicitCastTo(sc, vt);
6035 ei = ei.ctfeInterpret();
6036 }
6037
6038 if (tvp.specValue)
6039 {
6040 if (ei is null || (cast(void*)ei.type in TemplateValueParameter.edummies &&
6041 TemplateValueParameter.edummies[cast(void*)ei.type] == ei))
6042 return matchArgNoMatch();
6043
6044 Expression e = tvp.specValue;
6045
6046 sc = sc.startCTFE();
6047 e = e.expressionSemantic(sc);
6048 e = resolveProperties(sc, e);
6049 sc = sc.endCTFE();
6050 e = e.implicitCastTo(sc, vt);
6051 e = e.ctfeInterpret();
6052
6053 ei = ei.syntaxCopy();
6054 sc = sc.startCTFE();
6055 ei = ei.expressionSemantic(sc);
6056 sc = sc.endCTFE();
6057 ei = ei.implicitCastTo(sc, vt);
6058 ei = ei.ctfeInterpret();
6059 //printf("\tei: %s, %s\n", ei.toChars(), ei.type.toChars());
6060 //printf("\te : %s, %s\n", e.toChars(), e.type.toChars());
6061 if (!ei.equals(e))
6062 return matchArgNoMatch();
6063 }
6064 else
6065 {
6066 if (dedtypes[i])
6067 {
6068 // Must match already deduced value
6069 Expression e = cast(Expression)dedtypes[i];
6070 if (!ei || !ei.equals(e))
6071 return matchArgNoMatch();
6072 }
6073 }
6074 dedtypes[i] = ei;
6075
6076 if (psparam)
6077 {
6078 Initializer _init = new ExpInitializer(tvp.loc, ei);
6079 Declaration sparam = new VarDeclaration(tvp.loc, vt, tvp.ident, _init);
6080 sparam.storage_class = STC.manifest;
6081 *psparam = sparam;
6082 }
6083 return tvp.dependent ? MATCH.exact : m;
6084 }
6085
6086 MATCH matchArgAlias(TemplateAliasParameter tap)
6087 {
6088 //printf("TemplateAliasParameter.matchArg('%s')\n", tap.ident.toChars());
6089 MATCH m = MATCH.exact;
6090 Type ta = isType(oarg);
6091 RootObject sa = ta && !ta.deco ? null : getDsymbol(oarg);
6092 Expression ea = isExpression(oarg);
6093 if (ea)
6094 {
6095 if (auto te = ea.isThisExp())
6096 sa = te.var;
6097 else if (auto se = ea.isSuperExp())
6098 sa = se.var;
6099 else if (auto se = ea.isScopeExp())
6100 sa = se.sds;
6101 }
6102 if (sa)
6103 {
6104 if ((cast(Dsymbol)sa).isAggregateDeclaration())
6105 m = MATCH.convert;
6106
6107 /* specType means the alias must be a declaration with a type
6108 * that matches specType.
6109 */
6110 if (tap.specType)
6111 {
6112 tap.specType = typeSemantic(tap.specType, tap.loc, sc);
6113 Declaration d = (cast(Dsymbol)sa).isDeclaration();
6114 if (!d)
6115 return matchArgNoMatch();
6116 if (!d.type.equals(tap.specType))
6117 return matchArgNoMatch();
6118 }
6119 }
6120 else
6121 {
6122 sa = oarg;
6123 if (ea)
6124 {
6125 if (tap.specType)
6126 {
6127 if (!ea.type.equals(tap.specType))
6128 return matchArgNoMatch();
6129 }
6130 }
6131 else if (ta && ta.ty == Tinstance && !tap.specAlias)
6132 {
6133 /* Specialized parameter should be preferred
6134 * match to the template type parameter.
6135 * template X(alias a) {} // a == this
6136 * template X(alias a : B!A, alias B, A...) {} // B!A => ta
6137 */
6138 }
6139 else if (sa && sa == TemplateTypeParameter.tdummy)
6140 {
6141 /* https://issues.dlang.org/show_bug.cgi?id=2025
6142 * Aggregate Types should preferentially
6143 * match to the template type parameter.
6144 * template X(alias a) {} // a == this
6145 * template X(T) {} // T => sa
6146 */
6147 }
6148 else if (ta && ta.ty != Tident)
6149 {
6150 /* Match any type that's not a TypeIdentifier to alias parameters,
6151 * but prefer type parameter.
6152 * template X(alias a) { } // a == ta
6153 *
6154 * TypeIdentifiers are excluded because they might be not yet resolved aliases.
6155 */
6156 m = MATCH.convert;
6157 }
6158 else
6159 return matchArgNoMatch();
6160 }
6161
6162 if (tap.specAlias)
6163 {
6164 if (sa == TemplateAliasParameter.sdummy)
6165 return matchArgNoMatch();
6166 // check specialization if template arg is a symbol
6167 Dsymbol sx = isDsymbol(sa);
6168 if (sa != tap.specAlias && sx)
6169 {
6170 Type talias = isType(tap.specAlias);
6171 if (!talias)
6172 return matchArgNoMatch();
6173
6174 TemplateInstance ti = sx.isTemplateInstance();
6175 if (!ti && sx.parent)
6176 {
6177 ti = sx.parent.isTemplateInstance();
6178 if (ti && ti.name != sx.ident)
6179 return matchArgNoMatch();
6180 }
6181 if (!ti)
6182 return matchArgNoMatch();
6183
6184 Type t = new TypeInstance(Loc.initial, ti);
6185 MATCH m2 = deduceType(t, sc, talias, *parameters, dedtypes);
6186 if (m2 == MATCH.nomatch)
6187 return matchArgNoMatch();
6188 }
6189 // check specialization if template arg is a type
6190 else if (ta)
6191 {
6192 if (Type tspec = isType(tap.specAlias))
6193 {
6194 MATCH m2 = ta.implicitConvTo(tspec);
6195 if (m2 == MATCH.nomatch)
6196 return matchArgNoMatch();
6197 }
6198 else
6199 {
6200 error(tap.loc, "template parameter specialization for a type must be a type and not `%s`",
6201 tap.specAlias.toChars());
6202 return matchArgNoMatch();
6203 }
6204 }
6205 }
6206 else if (dedtypes[i])
6207 {
6208 // Must match already deduced symbol
6209 RootObject si = dedtypes[i];
6210 if (!sa || si != sa)
6211 return matchArgNoMatch();
6212 }
6213 dedtypes[i] = sa;
6214
6215 if (psparam)
6216 {
6217 if (Dsymbol s = isDsymbol(sa))
6218 {
6219 *psparam = new AliasDeclaration(tap.loc, tap.ident, s);
6220 }
6221 else if (Type t = isType(sa))
6222 {
6223 *psparam = new AliasDeclaration(tap.loc, tap.ident, t);
6224 }
6225 else
6226 {
6227 assert(ea);
6228
6229 // Declare manifest constant
6230 Initializer _init = new ExpInitializer(tap.loc, ea);
6231 auto v = new VarDeclaration(tap.loc, null, tap.ident, _init);
6232 v.storage_class = STC.manifest;
6233 v.dsymbolSemantic(sc);
6234 *psparam = v;
6235 }
6236 }
6237 return tap.dependent ? MATCH.exact : m;
6238 }
6239
6240 MATCH matchArgTuple(TemplateTupleParameter ttp)
6241 {
6242 //printf("TemplateTupleParameter.matchArg('%s')\n", ttp.ident.toChars());
6243 Tuple ovar = isTuple(oarg);
6244 if (!ovar)
6245 return MATCH.nomatch;
6246 if (dedtypes[i])
6247 {
6248 Tuple tup = isTuple(dedtypes[i]);
6249 if (!tup)
6250 return MATCH.nomatch;
6251 if (!match(tup, ovar))
6252 return MATCH.nomatch;
6253 }
6254 dedtypes[i] = ovar;
6255
6256 if (psparam)
6257 *psparam = new TupleDeclaration(ttp.loc, ttp.ident, &ovar.objects);
6258 return ttp.dependent ? MATCH.exact : MATCH.convert;
6259 }
6260
6261 if (auto ttp = tp.isTemplateTypeParameter())
6262 return matchArgType(ttp);
6263 else if (auto tvp = tp.isTemplateValueParameter())
6264 return matchArgValue(tvp);
6265 else if (auto tap = tp.isTemplateAliasParameter())
6266 return matchArgAlias(tap);
6267 else if (auto ttp = tp.isTemplateTupleParameter())
6268 return matchArgTuple(ttp);
6269 else
6270 assert(0);
6271 }
6272
6273
6274 /***********************************************
6275 * Collect and print statistics on template instantiations.
6276 */
6277 struct TemplateStats
6278 {
6279 __gshared TemplateStats[const void*] stats;
6280
6281 uint numInstantiations; // number of instantiations of the template
6282 uint uniqueInstantiations; // number of unique instantiations of the template
6283
6284 TemplateInstances* allInstances;
6285
6286 /*******************************
6287 * Add this instance
6288 * Params:
6289 * td = template declaration
6290 * ti = instance of td
6291 * listInstances = keep track of instances of templates
6292 */
6293 static void incInstance(const TemplateDeclaration td,
6294 const TemplateInstance ti,
6295 bool listInstances)
6296 {
6297 void log(ref TemplateStats ts)
6298 {
6299 if (ts.allInstances is null)
6300 ts.allInstances = new TemplateInstances();
6301 if (listInstances)
6302 ts.allInstances.push(cast() ti);
6303 }
6304
6305 // message(ti.loc, "incInstance %p %p", td, ti);
6306 if (!td)
6307 return;
6308 assert(ti);
6309 if (auto ts = cast(const void*) td in stats)
6310 {
6311 log(*ts);
6312 ++ts.numInstantiations;
6313 }
6314 else
6315 {
6316 stats[cast(const void*) td] = TemplateStats(1, 0);
6317 log(stats[cast(const void*) td]);
6318 }
6319 }
6320
6321 /*******************************
6322 * Add this unique instance
6323 */
6324 static void incUnique(const TemplateDeclaration td,
6325 const TemplateInstance ti)
6326 {
6327 // message(ti.loc, "incUnique %p %p", td, ti);
6328 if (!td)
6329 return;
6330 assert(ti);
6331 if (auto ts = cast(const void*) td in stats)
6332 ++ts.uniqueInstantiations;
6333 else
6334 stats[cast(const void*) td] = TemplateStats(0, 1);
6335 }
6336 }
6337
6338 /********************************
6339 * Print informational statistics on template instantiations.
6340 * Params:
6341 * listInstances = list instances of templates
6342 * eSink = where the print is sent
6343 */
6344 void printTemplateStats(bool listInstances, ErrorSink eSink)
6345 {
6346 static struct TemplateDeclarationStats
6347 {
6348 TemplateDeclaration td;
6349 TemplateStats ts;
6350 static int compare(scope const TemplateDeclarationStats* a,
6351 scope const TemplateDeclarationStats* b) @safe nothrow @nogc pure
6352 {
6353 auto diff = b.ts.uniqueInstantiations - a.ts.uniqueInstantiations;
6354 if (diff)
6355 return diff;
6356 else
6357 return b.ts.numInstantiations - a.ts.numInstantiations;
6358 }
6359 }
6360
6361 const stats_length = TemplateStats.stats.length;
6362 if (!stats_length)
6363 return; // nothing to report
6364
6365 Array!(TemplateDeclarationStats) sortedStats;
6366 sortedStats.reserve(stats_length);
6367 foreach (td_, ref ts; TemplateStats.stats)
6368 {
6369 sortedStats.push(TemplateDeclarationStats(cast(TemplateDeclaration) td_, ts));
6370 }
6371
6372 sortedStats.sort!(TemplateDeclarationStats.compare);
6373
6374 OutBuffer buf;
6375 foreach (const ref ss; sortedStats[])
6376 {
6377 buf.reset();
6378 HdrGenState hgs;
6379 hgs.skipConstraints = true;
6380 toCharsMaybeConstraints(ss.td, buf, hgs);
6381 const tchars = buf.peekChars();
6382 if (listInstances && ss.ts.allInstances)
6383 {
6384 eSink.message(ss.td.loc,
6385 "vtemplate: %u (%u distinct) instantiation(s) of template `%s` found, they are:",
6386 ss.ts.numInstantiations,
6387 ss.ts.uniqueInstantiations,
6388 tchars);
6389 foreach (const ti; (*ss.ts.allInstances)[])
6390 {
6391 if (ti.tinst) // if has enclosing instance
6392 eSink.message(ti.loc, "vtemplate: implicit instance `%s`", ti.toChars());
6393 else
6394 eSink.message(ti.loc, "vtemplate: explicit instance `%s`", ti.toChars());
6395 }
6396 }
6397 else
6398 {
6399 eSink.message(ss.td.loc,
6400 "vtemplate: %u (%u distinct) instantiation(s) of template `%s` found",
6401 ss.ts.numInstantiations,
6402 ss.ts.uniqueInstantiations,
6403 tchars);
6404 }
6405 }
6406 }
6407
6408 /// Pair of MATCHes
6409 struct MATCHpair
6410 {
6411 MATCH mta; /// match template parameters by initial template arguments
6412 MATCH mfa; /// match template parameters by inferred template arguments
6413
6414 debug this(MATCH mta, MATCH mfa)
6415 {
6416 assert(MATCH.min <= mta && mta <= MATCH.max);
6417 assert(MATCH.min <= mfa && mfa <= MATCH.max);
6418 this.mta = mta;
6419 this.mfa = mfa;
6420 }
6421 }
6422
6423 void write(ref OutBuffer buf, RootObject obj)
6424 {
6425 if (obj)
6426 {
6427 buf.writestring(obj.toChars());
6428 }
6429 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org