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-2020 by The D Language Foundation, All Rights Reserved
32
 * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
33
 * License:     $(LINK2 http://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.ast_node;
47
import dmd.dcast;
48
import dmd.dclass;
49
import dmd.declaration;
50
import dmd.dmangle;
51
import dmd.dmodule;
52
import dmd.dscope;
53
import dmd.dsymbol;
54
import dmd.dsymbolsem;
55
import dmd.errors;
56
import dmd.expression;
57
import dmd.expressionsem;
58
import dmd.func;
59
import dmd.globals;
60
import dmd.hdrgen;
61
import dmd.id;
62
import dmd.identifier;
63
import dmd.impcnvtab;
64
import dmd.init;
65
import dmd.initsem;
66
import dmd.mtype;
67
import dmd.opover;
68
import dmd.root.array;
69
import dmd.root.outbuffer;
70
import dmd.root.rmem;
71
import dmd.root.rootobject;
72
import dmd.semantic2;
73
import dmd.semantic3;
74
import dmd.tokens;
75
import dmd.typesem;
76
import dmd.visitor;
77

78
import dmd.templateparamsem;
79

80
//debug = FindExistingInstance; // print debug stats of findExistingInstance
81
private enum LOG = false;
82

83
enum IDX_NOTFOUND = 0x12345678;
84

85
pure nothrow @nogc
86
{
87

88
/********************************************
89
 * These functions substitute for dynamic_cast. dynamic_cast does not work
90
 * on earlier versions of gcc.
91
 */
92
extern (C++) inout(Expression) isExpression(inout RootObject o)
93
{
94
    //return dynamic_cast<Expression *>(o);
95 1
    if (!o || o.dyncast() != DYNCAST.expression)
96 1
        return null;
97 1
    return cast(inout(Expression))o;
98
}
99

100
extern (C++) inout(Dsymbol) isDsymbol(inout RootObject o)
101
{
102
    //return dynamic_cast<Dsymbol *>(o);
103 1
    if (!o || o.dyncast() != DYNCAST.dsymbol)
104 1
        return null;
105 1
    return cast(inout(Dsymbol))o;
106
}
107

108
extern (C++) inout(Type) isType(inout RootObject o)
109
{
110
    //return dynamic_cast<Type *>(o);
111 1
    if (!o || o.dyncast() != DYNCAST.type)
112 1
        return null;
113 1
    return cast(inout(Type))o;
114
}
115

116
extern (C++) inout(Tuple) isTuple(inout RootObject o)
117
{
118
    //return dynamic_cast<Tuple *>(o);
119 1
    if (!o || o.dyncast() != DYNCAST.tuple)
120 1
        return null;
121 1
    return cast(inout(Tuple))o;
122
}
123

124
extern (C++) inout(Parameter) isParameter(inout RootObject o)
125
{
126
    //return dynamic_cast<Parameter *>(o);
127 1
    if (!o || o.dyncast() != DYNCAST.parameter)
128 1
        return null;
129 1
    return cast(inout(Parameter))o;
130
}
131

132
extern (C++) inout(TemplateParameter) isTemplateParameter(inout RootObject o)
133
{
134 1
    if (!o || o.dyncast() != DYNCAST.templateparameter)
135 0
        return null;
136 1
    return cast(inout(TemplateParameter))o;
137
}
138

139
/**************************************
140
 * Is this Object an error?
141
 */
142
extern (C++) bool isError(const RootObject o)
143
{
144 1
    if (const t = isType(o))
145 1
        return (t.ty == Terror);
146 1
    if (const e = isExpression(o))
147 1
        return (e.op == TOK.error || !e.type || e.type.ty == Terror);
148 1
    if (const v = isTuple(o))
149 1
        return arrayObjectIsError(&v.objects);
150 1
    const s = isDsymbol(o);
151 1
    assert(s);
152 1
    if (s.errors)
153 1
        return true;
154 1
    return s.parent ? isError(s.parent) : false;
155
}
156

157
/**************************************
158
 * Are any of the Objects an error?
159
 */
160
bool arrayObjectIsError(const Objects* args)
161
{
162 1
    foreach (const o; *args)
163
    {
164 1
        if (isError(o))
165 1
            return true;
166
    }
167 1
    return false;
168
}
169

170
/***********************
171
 * Try to get arg as a type.
172
 */
173
inout(Type) getType(inout RootObject o)
174
{
175 1
    inout t = isType(o);
176 1
    if (!t)
177
    {
178 1
        if (inout e = isExpression(o))
179 1
            return e.type;
180
    }
181 1
    return t;
182
}
183

184
}
185

186
Dsymbol getDsymbol(RootObject oarg)
187
{
188
    //printf("getDsymbol()\n");
189
    //printf("e %p s %p t %p v %p\n", isExpression(oarg), isDsymbol(oarg), isType(oarg), isTuple(oarg));
190 1
    if (auto ea = isExpression(oarg))
191
    {
192
        // Try to convert Expression to symbol
193 1
        if (auto ve = ea.isVarExp())
194 1
            return ve.var;
195 1
        else if (auto fe = ea.isFuncExp())
196 1
            return fe.td ? fe.td : fe.fd;
197 1
        else if (auto te = ea.isTemplateExp())
198 1
            return te.td;
199 1
        else if (auto te = ea.isScopeExp())
200 1
            return te.sds;
201
        else
202 1
            return null;
203
    }
204
    else
205
    {
206
        // Try to convert Type to symbol
207 1
        if (auto ta = isType(oarg))
208 1
            return ta.toDsymbol(null);
209
        else
210 1
            return isDsymbol(oarg); // if already a symbol
211
    }
212
}
213

214

215
private Expression getValue(ref Dsymbol s)
216
{
217 1
    if (s)
218
    {
219 1
        if (VarDeclaration v = s.isVarDeclaration())
220
        {
221 1
            if (v.storage_class & STC.manifest)
222 1
                return v.getConstInitializer();
223
        }
224
    }
225 1
    return null;
226
}
227

228
/***********************
229
 * Try to get value from manifest constant
230
 */
231
private Expression getValue(Expression e)
232
{
233 1
    if (e && e.op == TOK.variable)
234
    {
235 1
        VarDeclaration v = (cast(VarExp)e).var.isVarDeclaration();
236 1
        if (v && v.storage_class & STC.manifest)
237
        {
238 1
            e = v.getConstInitializer();
239
        }
240
    }
241 1
    return e;
242
}
243

244
private Expression getExpression(RootObject o)
245
{
246 1
    auto s = isDsymbol(o);
247 1
    return s ? .getValue(s) : .getValue(isExpression(o));
248
}
249

250
/******************************
251
 * If o1 matches o2, return true.
252
 * Else, return false.
253
 */
254
private bool match(RootObject o1, RootObject o2)
255
{
256
    enum log = false;
257

258
    static if (log)
259
    {
260
        printf("match() o1 = %p %s (%d), o2 = %p %s (%d)\n",
261
            o1, o1.toChars(), o1.dyncast(), o2, o2.toChars(), o2.dyncast());
262
    }
263

264
    /* A proper implementation of the various equals() overrides
265
     * should make it possible to just do o1.equals(o2), but
266
     * we'll do that another day.
267
     */
268
    /* Manifest constants should be compared by their values,
269
     * at least in template arguments.
270
     */
271

272 1
    if (auto t1 = isType(o1))
273
    {
274 1
        auto t2 = isType(o2);
275 1
        if (!t2)
276 0
            goto Lnomatch;
277

278
        static if (log)
279
        {
280
            printf("\tt1 = %s\n", t1.toChars());
281
            printf("\tt2 = %s\n", t2.toChars());
282
        }
283 1
        if (!t1.equals(t2))
284 1
            goto Lnomatch;
285

286 1
        goto Lmatch;
287
    }
288 1
    if (auto e1 = getExpression(o1))
289
    {
290 1
        auto e2 = getExpression(o2);
291 1
        if (!e2)
292 0
            goto Lnomatch;
293

294
        static if (log)
295
        {
296
            printf("\te1 = %s '%s' %s\n", e1.type ? e1.type.toChars() : "null", Token.toChars(e1.op), e1.toChars());
297
            printf("\te2 = %s '%s' %s\n", e2.type ? e2.type.toChars() : "null", Token.toChars(e2.op), e2.toChars());
298
        }
299

300
        // two expressions can be equal although they do not have the same
301
        // type; that happens when they have the same value. So check type
302
        // as well as expression equality to ensure templates are properly
303
        // matched.
304 1
        if (!(e1.type && e2.type && e1.type.equals(e2.type)) || !e1.equals(e2))
305 1
            goto Lnomatch;
306

307 1
        goto Lmatch;
308
    }
309 1
    if (auto s1 = isDsymbol(o1))
310
    {
311 1
        auto s2 = isDsymbol(o2);
312 1
        if (!s2)
313 0
            goto Lnomatch;
314

315
        static if (log)
316
        {
317
            printf("\ts1 = %s \n", s1.kind(), s1.toChars());
318
            printf("\ts2 = %s \n", s2.kind(), s2.toChars());
319
        }
320 1
        if (!s1.equals(s2))
321 1
            goto Lnomatch;
322 1
        if (s1.parent != s2.parent && !s1.isFuncDeclaration() && !s2.isFuncDeclaration())
323 0
            goto Lnomatch;
324

325 1
        goto Lmatch;
326
    }
327 1
    if (auto u1 = isTuple(o1))
328
    {
329 1
        auto u2 = isTuple(o2);
330 1
        if (!u2)
331 0
            goto Lnomatch;
332

333
        static if (log)
334
        {
335
            printf("\tu1 = %s\n", u1.toChars());
336
            printf("\tu2 = %s\n", u2.toChars());
337
        }
338 1
        if (!arrayObjectMatch(&u1.objects, &u2.objects))
339 1
            goto Lnomatch;
340

341 1
        goto Lmatch;
342
    }
343
Lmatch:
344
    static if (log)
345
        printf("\t. match\n");
346 1
    return true;
347

348
Lnomatch:
349
    static if (log)
350
        printf("\t. nomatch\n");
351 1
    return false;
352
}
353

354
/************************************
355
 * Match an array of them.
356
 */
357
private bool arrayObjectMatch(Objects* oa1, Objects* oa2)
358
{
359 1
    if (oa1 == oa2)
360 1
        return true;
361 1
    if (oa1.dim != oa2.dim)
362 1
        return false;
363 1
    immutable oa1dim = oa1.dim;
364 1
    auto oa1d = (*oa1)[].ptr;
365 1
    auto oa2d = (*oa2)[].ptr;
366 1
    foreach (j; 0 .. oa1dim)
367
    {
368 1
        RootObject o1 = oa1d[j];
369 1
        RootObject o2 = oa2d[j];
370 1
        if (!match(o1, o2))
371
        {
372 1
            return false;
373
        }
374
    }
375 1
    return true;
376
}
377

378
/************************************
379
 * Return hash of Objects.
380
 */
381
private size_t arrayObjectHash(Objects* oa1)
382
{
383
    import dmd.root.hash : mixHash;
384

385 1
    size_t hash = 0;
386 1
    foreach (o1; *oa1)
387
    {
388
        /* Must follow the logic of match()
389
         */
390 1
        if (auto t1 = isType(o1))
391 1
            hash = mixHash(hash, cast(size_t)t1.deco);
392 1
        else if (auto e1 = getExpression(o1))
393 1
            hash = mixHash(hash, expressionHash(e1));
394 1
        else if (auto s1 = isDsymbol(o1))
395
        {
396 1
            auto fa1 = s1.isFuncAliasDeclaration();
397 1
            if (fa1)
398 1
                s1 = fa1.toAliasFunc();
399 1
            hash = mixHash(hash, mixHash(cast(size_t)cast(void*)s1.getIdent(), cast(size_t)cast(void*)s1.parent));
400
        }
401 1
        else if (auto u1 = isTuple(o1))
402 1
            hash = mixHash(hash, arrayObjectHash(&u1.objects));
403
    }
404 1
    return hash;
405
}
406

407

408
/************************************
409
 * Computes hash of expression.
410
 * Handles all Expression classes and MUST match their equals method,
411
 * i.e. e1.equals(e2) implies expressionHash(e1) == expressionHash(e2).
412
 */
413
private size_t expressionHash(Expression e)
414
{
415
    import dmd.root.ctfloat : CTFloat;
416
    import dmd.root.hash : calcHash, mixHash;
417

418 1
    switch (e.op)
419
    {
420 1
    case TOK.int64:
421 1
        return cast(size_t) (cast(IntegerExp)e).getInteger();
422

423 1
    case TOK.float64:
424 1
        return CTFloat.hash((cast(RealExp)e).value);
425

426 1
    case TOK.complex80:
427 1
        auto ce = cast(ComplexExp)e;
428 1
        return mixHash(CTFloat.hash(ce.toReal), CTFloat.hash(ce.toImaginary));
429

430 0
    case TOK.identifier:
431 0
        return cast(size_t)cast(void*) (cast(IdentifierExp)e).ident;
432

433 1
    case TOK.null_:
434 1
        return cast(size_t)cast(void*) (cast(NullExp)e).type;
435

436 1
    case TOK.string_:
437 1
        return calcHash(e.isStringExp.peekData());
438

439 0
    case TOK.tuple:
440
    {
441 0
        auto te = cast(TupleExp)e;
442 0
        size_t hash = 0;
443 0
        hash += te.e0 ? expressionHash(te.e0) : 0;
444 0
        foreach (elem; *te.exps)
445 0
            hash = mixHash(hash, expressionHash(elem));
446 0
        return hash;
447
    }
448

449 1
    case TOK.arrayLiteral:
450
    {
451 1
        auto ae = cast(ArrayLiteralExp)e;
452 1
        size_t hash;
453 1
        foreach (i; 0 .. ae.elements.dim)
454 1
            hash = mixHash(hash, expressionHash(ae[i]));
455 1
        return hash;
456
    }
457

458 1
    case TOK.assocArrayLiteral:
459
    {
460 1
        auto ae = cast(AssocArrayLiteralExp)e;
461 1
        size_t hash;
462 1
        foreach (i; 0 .. ae.keys.dim)
463
            // reduction needs associative op as keys are unsorted (use XOR)
464 1
            hash ^= mixHash(expressionHash((*ae.keys)[i]), expressionHash((*ae.values)[i]));
465 1
        return hash;
466
    }
467

468 1
    case TOK.structLiteral:
469
    {
470 1
        auto se = cast(StructLiteralExp)e;
471 1
        size_t hash;
472 1
        foreach (elem; *se.elements)
473 1
            hash = mixHash(hash, elem ? expressionHash(elem) : 0);
474 1
        return hash;
475
    }
476

477 1
    case TOK.variable:
478 1
        return cast(size_t)cast(void*) (cast(VarExp)e).var;
479

480 1
    case TOK.function_:
481 1
        return cast(size_t)cast(void*) (cast(FuncExp)e).fd;
482

483 0
    default:
484
        // no custom equals for this expression
485 0
        assert((&e.equals).funcptr is &RootObject.equals);
486
        // equals based on identity
487 0
        return cast(size_t)cast(void*) e;
488
    }
489
}
490

491
RootObject objectSyntaxCopy(RootObject o)
492
{
493 1
    if (!o)
494 1
        return null;
495 1
    if (Type t = isType(o))
496 1
        return t.syntaxCopy();
497 1
    if (Expression e = isExpression(o))
498 1
        return e.syntaxCopy();
499 0
    return o;
500
}
501

502
extern (C++) final class Tuple : RootObject
503
{
504
    Objects objects;
505

506 1
    extern (D) this() {}
507

508
    /**
509
    Params:
510
        numObjects = The initial number of objects.
511
    */
512 1
    extern (D) this(size_t numObjects)
513
    {
514 1
        objects.setDim(numObjects);
515
    }
516

517
    // kludge for template.isType()
518
    override DYNCAST dyncast() const
519
    {
520 1
        return DYNCAST.tuple;
521
    }
522

523
    override const(char)* toChars() const
524
    {
525 0
        return objects.toChars();
526
    }
527
}
528

529
struct TemplatePrevious
530
{
531
    TemplatePrevious* prev;
532
    Scope* sc;
533
    Objects* dedargs;
534
}
535

536
/***********************************************************
537
 * [mixin] template Identifier (parameters) [Constraint]
538
 * https://dlang.org/spec/template.html
539
 * https://dlang.org/spec/template-mixin.html
540
 */
541
extern (C++) final class TemplateDeclaration : ScopeDsymbol
542
{
543
    import dmd.root.array : Array;
544

545
    TemplateParameters* parameters;     // array of TemplateParameter's
546
    TemplateParameters* origParameters; // originals for Ddoc
547

548
    Expression constraint;
549

550
    // Hash table to look up TemplateInstance's of this TemplateDeclaration
551
    TemplateInstance[TemplateInstanceBox] instances;
552

553
    TemplateDeclaration overnext;       // next overloaded TemplateDeclaration
554
    TemplateDeclaration overroot;       // first in overnext list
555
    FuncDeclaration funcroot;           // first function in unified overload list
556

557
    Dsymbol onemember;      // if !=null then one member of this template
558

559
    bool literal;           // this template declaration is a literal
560
    bool ismixin;           // this is a mixin template declaration
561
    bool isstatic;          // this is static template declaration
562
    bool isTrivialAliasSeq; /// matches pattern `template AliasSeq(T...) { alias AliasSeq = T; }`
563
    bool isTrivialAlias;    /// matches pattern `template Alias(T) { alias Alias = qualifiers(T); }`
564
    bool deprecated_;       /// this template declaration is deprecated
565
    Prot protection;
566
    int inuse;              /// for recursive expansion detection
567

568
    // threaded list of previous instantiation attempts on stack
569
    TemplatePrevious* previous;
570

571
    private Expression lastConstraint; /// the constraint after the last failed evaluation
572
    private Array!Expression lastConstraintNegs; /// its negative parts
573
    private Objects* lastConstraintTiargs; /// template instance arguments for `lastConstraint`
574

575 1
    extern (D) this(const ref Loc loc, Identifier ident, TemplateParameters* parameters, Expression constraint, Dsymbols* decldefs, bool ismixin = false, bool literal = false)
576
    {
577 1
        super(loc, ident);
578
        static if (LOG)
579
        {
580
            printf("TemplateDeclaration(this = %p, id = '%s')\n", this, ident.toChars());
581
        }
582
        version (none)
583
        {
584
            if (parameters)
585
                for (int i = 0; i < parameters.dim; i++)
586
                {
587
                    TemplateParameter tp = (*parameters)[i];
588
                    //printf("\tparameter[%d] = %p\n", i, tp);
589
                    TemplateTypeParameter ttp = tp.isTemplateTypeParameter();
590
                    if (ttp)
591
                    {
592
                        printf("\tparameter[%d] = %s : %s\n", i, tp.ident.toChars(), ttp.specType ? ttp.specType.toChars() : "");
593
                    }
594
                }
595
        }
596 1
        this.parameters = parameters;
597 1
        this.origParameters = parameters;
598 1
        this.constraint = constraint;
599 1
        this.members = decldefs;
600 1
        this.literal = literal;
601 1
        this.ismixin = ismixin;
602 1
        this.isstatic = true;
603 1
        this.protection = Prot(Prot.Kind.undefined);
604

605
        // Compute in advance for Ddoc's use
606
        // https://issues.dlang.org/show_bug.cgi?id=11153: ident could be NULL if parsing fails.
607 1
        if (!members || !ident)
608 1
            return;
609

610 1
        Dsymbol s;
611 1
        if (!Dsymbol.oneMembers(members, &s, ident) || !s)
612 1
            return;
613

614 1
        onemember = s;
615 1
        s.parent = this;
616

617
        /* Set isTrivialAliasSeq if this fits the pattern:
618
         *   template AliasSeq(T...) { alias AliasSeq = T; }
619
         * or set isTrivialAlias if this fits the pattern:
620
         *   template Alias(T) { alias Alias = qualifiers(T); }
621
         */
622 1
        if (!(parameters && parameters.length == 1))
623 1
            return;
624

625 1
        auto ad = s.isAliasDeclaration();
626 1
        if (!ad || !ad.type)
627 1
            return;
628

629 1
        auto ti = ad.type.isTypeIdentifier();
630

631 1
        if (!ti || ti.idents.length != 0)
632 1
            return;
633

634 1
        if (auto ttp = (*parameters)[0].isTemplateTupleParameter())
635
        {
636 1
            if (ti.ident is ttp.ident &&
637 1
                ti.mod == 0)
638
            {
639
                //printf("found isTrivialAliasSeq %s %s\n", s.toChars(), ad.type.toChars());
640 1
                isTrivialAliasSeq = true;
641
            }
642
        }
643 1
        else if (auto ttp = (*parameters)[0].isTemplateTypeParameter())
644
        {
645 1
            if (ti.ident is ttp.ident)
646
            {
647
                //printf("found isTrivialAlias %s %s\n", s.toChars(), ad.type.toChars());
648 1
                isTrivialAlias = true;
649
            }
650
        }
651
    }
652

653
    override Dsymbol syntaxCopy(Dsymbol)
654
    {
655
        //printf("TemplateDeclaration.syntaxCopy()\n");
656 1
        TemplateParameters* p = null;
657 1
        if (parameters)
658
        {
659 1
            p = new TemplateParameters(parameters.dim);
660 1
            foreach (i, ref param; *p)
661 1
                param = (*parameters)[i].syntaxCopy();
662
        }
663 1
        return new TemplateDeclaration(loc, ident, p, constraint ? constraint.syntaxCopy() : null, Dsymbol.arraySyntaxCopy(members), ismixin, literal);
664
    }
665

666
    /**********************************
667
     * Overload existing TemplateDeclaration 'this' with the new one 's'.
668
     * Return true if successful; i.e. no conflict.
669
     */
670
    override bool overloadInsert(Dsymbol s)
671
    {
672
        static if (LOG)
673
        {
674
            printf("TemplateDeclaration.overloadInsert('%s')\n", s.toChars());
675
        }
676 1
        FuncDeclaration fd = s.isFuncDeclaration();
677 1
        if (fd)
678
        {
679 1
            if (funcroot)
680 1
                return funcroot.overloadInsert(fd);
681 1
            funcroot = fd;
682 1
            return funcroot.overloadInsert(this);
683
        }
684

685
        // https://issues.dlang.org/show_bug.cgi?id=15795
686
        // if candidate is an alias and its sema is not run then
687
        // insertion can fail because the thing it alias is not known
688 1
        if (AliasDeclaration ad = s.isAliasDeclaration())
689
        {
690 1
            if (s._scope)
691 1
                aliasSemantic(ad, s._scope);
692 1
            if (ad.aliassym && ad.aliassym is this)
693 1
                return false;
694
        }
695 1
        TemplateDeclaration td = s.toAlias().isTemplateDeclaration();
696 1
        if (!td)
697 0
            return false;
698

699 1
        TemplateDeclaration pthis = this;
700 1
        TemplateDeclaration* ptd;
701 1
        for (ptd = &pthis; *ptd; ptd = &(*ptd).overnext)
702
        {
703
        }
704

705 1
        td.overroot = this;
706 1
        *ptd = td;
707
        static if (LOG)
708
        {
709
            printf("\ttrue: no conflict\n");
710
        }
711 1
        return true;
712
    }
713

714
    override bool hasStaticCtorOrDtor()
715
    {
716 1
        return false; // don't scan uninstantiated templates
717
    }
718

719
    override const(char)* kind() const
720
    {
721 1
        return (onemember && onemember.isAggregateDeclaration()) ? onemember.kind() : "template";
722
    }
723

724
    override const(char)* toChars() const
725
    {
726 1
        if (literal)
727 1
            return Dsymbol.toChars();
728

729 1
        OutBuffer buf;
730 1
        HdrGenState hgs;
731

732 1
        buf.writestring(ident.toString());
733 1
        buf.writeByte('(');
734 1
        foreach (i, const tp; *parameters)
735
        {
736 1
            if (i)
737 1
                buf.writestring(", ");
738 1
            .toCBuffer(tp, &buf, &hgs);
739
        }
740 1
        buf.writeByte(')');
741

742 1
        if (onemember)
743
        {
744 1
            const FuncDeclaration fd = onemember.isFuncDeclaration();
745 1
            if (fd && fd.type)
746
            {
747 1
                TypeFunction tf = cast(TypeFunction)fd.type;
748 1
                buf.writestring(parametersTypeToChars(tf.parameterList));
749
            }
750
        }
751

752 1
        if (constraint)
753
        {
754 1
            buf.writestring(" if (");
755 1
            .toCBuffer(constraint, &buf, &hgs);
756 1
            buf.writeByte(')');
757
        }
758 1
        return buf.extractChars();
759
    }
760

761
    /****************************
762
     * Similar to `toChars`, but does not print the template constraints
763
     */
764
    const(char)* toCharsNoConstraints()
765
    {
766 1
        if (literal)
767 1
            return Dsymbol.toChars();
768

769 1
        OutBuffer buf;
770 1
        HdrGenState hgs;
771

772 1
        buf.writestring(ident.toChars());
773 1
        buf.writeByte('(');
774 1
        foreach (i, tp; *parameters)
775
        {
776 1
            if (i > 0)
777 1
                buf.writestring(", ");
778 1
            .toCBuffer(tp, &buf, &hgs);
779
        }
780 1
        buf.writeByte(')');
781

782 1
        if (onemember)
783
        {
784 1
            FuncDeclaration fd = onemember.isFuncDeclaration();
785 1
            if (fd && fd.type)
786
            {
787 1
                TypeFunction tf = fd.type.isTypeFunction();
788 1
                buf.writestring(parametersTypeToChars(tf.parameterList));
789
            }
790
        }
791 1
        return buf.extractChars();
792
    }
793

794
    override Prot prot() pure nothrow @nogc @safe
795
    {
796 1
        return protection;
797
    }
798

799
    /****************************
800
     * Check to see if constraint is satisfied.
801
     */
802
    extern (D) bool evaluateConstraint(TemplateInstance ti, Scope* sc, Scope* paramscope, Objects* dedargs, FuncDeclaration fd)
803
    {
804
        /* Detect recursive attempts to instantiate this template declaration,
805
         * https://issues.dlang.org/show_bug.cgi?id=4072
806
         *  void foo(T)(T x) if (is(typeof(foo(x)))) { }
807
         *  static assert(!is(typeof(foo(7))));
808
         * Recursive attempts are regarded as a constraint failure.
809
         */
810
        /* There's a chicken-and-egg problem here. We don't know yet if this template
811
         * instantiation will be a local one (enclosing is set), and we won't know until
812
         * after selecting the correct template. Thus, function we're nesting inside
813
         * is not on the sc scope chain, and this can cause errors in FuncDeclaration.getLevel().
814
         * Workaround the problem by setting a flag to relax the checking on frame errors.
815
         */
816

817 1
        for (TemplatePrevious* p = previous; p; p = p.prev)
818
        {
819 1
            if (arrayObjectMatch(p.dedargs, dedargs))
820
            {
821
                //printf("recursive, no match p.sc=%p %p %s\n", p.sc, this, this.toChars());
822
                /* It must be a subscope of p.sc, other scope chains are not recursive
823
                 * instantiations.
824
                 * the chain of enclosing scopes is broken by paramscope (its enclosing
825
                 * scope is _scope, but paramscope.callsc is the instantiating scope). So
826
                 * it's good enough to check the chain of callsc
827
                 */
828 1
                for (Scope* scx = paramscope.callsc; scx; scx = scx.callsc)
829
                {
830 1
                    if (scx == p.sc)
831 1
                        return false;
832
                }
833
            }
834
            /* BUG: should also check for ref param differences
835
             */
836
        }
837

838 1
        TemplatePrevious pr;
839 1
        pr.prev = previous;
840 1
        pr.sc = paramscope.callsc;
841 1
        pr.dedargs = dedargs;
842 1
        previous = &pr; // add this to threaded list
843

844 1
        Scope* scx = paramscope.push(ti);
845 1
        scx.parent = ti;
846 1
        scx.tinst = null;
847 1
        scx.minst = null;
848

849 1
        assert(!ti.symtab);
850 1
        if (fd)
851
        {
852
            /* Declare all the function parameters as variables and add them to the scope
853
             * Making parameters is similar to FuncDeclaration.semantic3
854
             */
855 1
            TypeFunction tf = cast(TypeFunction)fd.type;
856 1
            assert(tf.ty == Tfunction);
857

858 1
            scx.parent = fd;
859

860 1
            Parameters* fparameters = tf.parameterList.parameters;
861 1
            const nfparams = tf.parameterList.length;
862 1
            foreach (i, fparam; tf.parameterList)
863
            {
864 1
                fparam.storageClass &= (STC.IOR | STC.lazy_ | STC.final_ | STC.TYPECTOR | STC.nodtor);
865 1
                fparam.storageClass |= STC.parameter;
866 1
                if (tf.parameterList.varargs == VarArg.typesafe && i + 1 == nfparams)
867
                {
868 1
                    fparam.storageClass |= STC.variadic;
869
                    /* Don't need to set STC.scope_ because this will only
870
                     * be evaluated at compile time
871
                     */
872
                }
873
            }
874 1
            foreach (fparam; *fparameters)
875
            {
876 1
                if (!fparam.ident)
877 1
                    continue;
878
                // don't add it, if it has no name
879 1
                auto v = new VarDeclaration(loc, fparam.type, fparam.ident, null);
880 1
                fparam.storageClass |= STC.parameter;
881 1
                v.storage_class = fparam.storageClass;
882 1
                v.dsymbolSemantic(scx);
883 1
                if (!ti.symtab)
884 1
                    ti.symtab = new DsymbolTable();
885 1
                if (!scx.insert(v))
886 0
                    error("parameter `%s.%s` is already defined", toChars(), v.toChars());
887
                else
888 1
                    v.parent = fd;
889
            }
890 1
            if (isstatic)
891 1
                fd.storage_class |= STC.static_;
892 1
            fd.declareThis(scx);
893
        }
894

895 1
        lastConstraint = constraint.syntaxCopy();
896 1
        lastConstraintTiargs = ti.tiargs;
897 1
        lastConstraintNegs.setDim(0);
898

899
        import dmd.staticcond;
900

901 1
        assert(ti.inst is null);
902 1
        ti.inst = ti; // temporary instantiation to enable genIdent()
903 1
        scx.flags |= SCOPE.constraint;
904 1
        bool errors;
905 1
        const bool result = evalStaticCondition(scx, constraint, lastConstraint, errors, &lastConstraintNegs);
906 1
        if (result || errors)
907
        {
908 1
            lastConstraint = null;
909 1
            lastConstraintTiargs = null;
910 1
            lastConstraintNegs.setDim(0);
911
        }
912 1
        ti.inst = null;
913 1
        ti.symtab = null;
914 1
        scx = scx.pop();
915 1
        previous = pr.prev; // unlink from threaded list
916 1
        if (errors)
917 1
            return false;
918 1
        return result;
919
    }
920

921
    /****************************
922
     * Destructively get the error message from the last constraint evaluation
923
     * Params:
924
     *      tip = tip to show after printing all overloads
925
     */
926
    const(char)* getConstraintEvalError(ref const(char)* tip)
927
    {
928
        import dmd.staticcond;
929

930
        // there will be a full tree view in verbose mode, and more compact list in the usual
931 1
        const full = global.params.verbose;
932 1
        uint count;
933 1
        const msg = visualizeStaticCondition(constraint, lastConstraint, lastConstraintNegs[], full, count);
934
        scope (exit)
935
        {
936 1
            lastConstraint = null;
937 1
            lastConstraintTiargs = null;
938 1
            lastConstraintNegs.setDim(0);
939
        }
940 1
        if (msg)
941
        {
942 1
            OutBuffer buf;
943

944 1
            assert(parameters && lastConstraintTiargs);
945 1
            if (parameters.length > 0)
946
            {
947 1
                formatParamsWithTiargs(*lastConstraintTiargs, buf);
948 1
                buf.writenl();
949
            }
950 1
            if (!full)
951
            {
952
                // choosing singular/plural
953 1
                const s = (count == 1) ?
954 1
                    "  must satisfy the following constraint:" :
955 1
                    "  must satisfy one of the following constraints:";
956 1
                buf.writestring(s);
957 1
                buf.writenl();
958
                // the constraints
959 1
                buf.writeByte('`');
960 1
                buf.writestring(msg);
961 1
                buf.writeByte('`');
962
            }
963
            else
964
            {
965 1
                buf.writestring("  whose parameters have the following constraints:");
966 1
                buf.writenl();
967 1
                const sep = "  `~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`";
968 1
                buf.writestring(sep);
969 1
                buf.writenl();
970
                // the constraints
971 1
                buf.writeByte('`');
972 1
                buf.writestring(msg);
973 1
                buf.writeByte('`');
974 1
                buf.writestring(sep);
975 1
                tip = "not satisfied constraints are marked with `>`";
976
            }
977 1
            return buf.extractChars();
978
        }
979
        else
980 1
            return null;
981
    }
982

983
    private void formatParamsWithTiargs(ref Objects tiargs, ref OutBuffer buf)
984
    {
985 1
        buf.writestring("  with `");
986

987
        // write usual arguments line-by-line
988
        // skips trailing default ones - they are not present in `tiargs`
989 1
        const bool variadic = isVariadic() !is null;
990 1
        const end = cast(int)parameters.length - (variadic ? 1 : 0);
991 1
        uint i;
992 1
        for (; i < tiargs.length && i < end; i++)
993
        {
994 1
            if (i > 0)
995
            {
996 1
                buf.writeByte(',');
997 1
                buf.writenl();
998 1
                buf.writestring("       ");
999
            }
1000 1
            buf.write((*parameters)[i]);
1001 1
            buf.writestring(" = ");
1002 1
            buf.write(tiargs[i]);
1003
        }
1004
        // write remaining variadic arguments on the last line
1005 1
        if (variadic)
1006
        {
1007 1
            if (i > 0)
1008
            {
1009 1
                buf.writeByte(',');
1010 1
                buf.writenl();
1011 1
                buf.writestring("       ");
1012
            }
1013 1
            buf.write((*parameters)[end]);
1014 1
            buf.writestring(" = ");
1015 1
            buf.writeByte('(');
1016 1
            if (cast(int)tiargs.length - end > 0)
1017
            {
1018 1
                buf.write(tiargs[end]);
1019 1
                foreach (j; parameters.length .. tiargs.length)
1020
                {
1021 1
                    buf.writestring(", ");
1022 1
                    buf.write(tiargs[j]);
1023
                }
1024
            }
1025 1
            buf.writeByte(')');
1026
        }
1027 1
        buf.writeByte('`');
1028
    }
1029

1030
    /******************************
1031
     * Create a scope for the parameters of the TemplateInstance
1032
     * `ti` in the parent scope sc from the ScopeDsymbol paramsym.
1033
     *
1034
     * If paramsym is null a new ScopeDsymbol is used in place of
1035
     * paramsym.
1036
     * Params:
1037
     *      ti = the TemplateInstance whose parameters to generate the scope for.
1038
     *      sc = the parent scope of ti
1039
     * Returns:
1040
     *      a scope for the parameters of ti
1041
     */
1042
    Scope* scopeForTemplateParameters(TemplateInstance ti, Scope* sc)
1043
    {
1044 1
        ScopeDsymbol paramsym = new ScopeDsymbol();
1045 1
        paramsym.parent = _scope.parent;
1046 1
        Scope* paramscope = _scope.push(paramsym);
1047 1
        paramscope.tinst = ti;
1048 1
        paramscope.minst = sc.minst;
1049 1
        paramscope.callsc = sc;
1050 1
        paramscope.stc = 0;
1051 1
        return paramscope;
1052
    }
1053

1054
    /***************************************
1055
     * Given that ti is an instance of this TemplateDeclaration,
1056
     * deduce the types of the parameters to this, and store
1057
     * those deduced types in dedtypes[].
1058
     * Input:
1059
     *      flag    1: don't do semantic() because of dummy types
1060
     *              2: don't change types in matchArg()
1061
     * Output:
1062
     *      dedtypes        deduced arguments
1063
     * Return match level.
1064
     */
1065
    extern (D) MATCH matchWithInstance(Scope* sc, TemplateInstance ti, Objects* dedtypes, Expressions* fargs, int flag)
1066
    {
1067
        enum LOGM = 0;
1068
        static if (LOGM)
1069
        {
1070
            printf("\n+TemplateDeclaration.matchWithInstance(this = %s, ti = %s, flag = %d)\n", toChars(), ti.toChars(), flag);
1071
        }
1072
        version (none)
1073
        {
1074
            printf("dedtypes.dim = %d, parameters.dim = %d\n", dedtypes.dim, parameters.dim);
1075
            if (ti.tiargs.dim)
1076
                printf("ti.tiargs.dim = %d, [0] = %p\n", ti.tiargs.dim, (*ti.tiargs)[0]);
1077
        }
1078 1
        MATCH m;
1079 1
        size_t dedtypes_dim = dedtypes.dim;
1080

1081 1
        dedtypes.zero();
1082

1083 1
        if (errors)
1084 1
            return MATCH.nomatch;
1085

1086 1
        size_t parameters_dim = parameters.dim;
1087 1
        int variadic = isVariadic() !is null;
1088

1089
        // If more arguments than parameters, no match
1090 1
        if (ti.tiargs.dim > parameters_dim && !variadic)
1091
        {
1092
            static if (LOGM)
1093
            {
1094
                printf(" no match: more arguments than parameters\n");
1095
            }
1096 1
            return MATCH.nomatch;
1097
        }
1098

1099 1
        assert(dedtypes_dim == parameters_dim);
1100 1
        assert(dedtypes_dim >= ti.tiargs.dim || variadic);
1101

1102 1
        assert(_scope);
1103

1104
        // Set up scope for template parameters
1105 1
        Scope* paramscope = scopeForTemplateParameters(ti,sc);
1106

1107
        // Attempt type deduction
1108 1
        m = MATCH.exact;
1109 1
        for (size_t i = 0; i < dedtypes_dim; i++)
1110
        {
1111 1
            MATCH m2;
1112 1
            TemplateParameter tp = (*parameters)[i];
1113 1
            Declaration sparam;
1114

1115
            //printf("\targument [%d]\n", i);
1116
            static if (LOGM)
1117
            {
1118
                //printf("\targument [%d] is %s\n", i, oarg ? oarg.toChars() : "null");
1119
                TemplateTypeParameter ttp = tp.isTemplateTypeParameter();
1120
                if (ttp)
1121
                    printf("\tparameter[%d] is %s : %s\n", i, tp.ident.toChars(), ttp.specType ? ttp.specType.toChars() : "");
1122
            }
1123

1124 1
            inuse++;
1125 1
            m2 = tp.matchArg(ti.loc, paramscope, ti.tiargs, i, parameters, dedtypes, &sparam);
1126 1
            inuse--;
1127
            //printf("\tm2 = %d\n", m2);
1128 1
            if (m2 == MATCH.nomatch)
1129
            {
1130
                version (none)
1131
                {
1132
                    printf("\tmatchArg() for parameter %i failed\n", i);
1133
                }
1134 1
                goto Lnomatch;
1135
            }
1136

1137 1
            if (m2 < m)
1138 1
                m = m2;
1139

1140 1
            if (!flag)
1141 1
                sparam.dsymbolSemantic(paramscope);
1142 1
            if (!paramscope.insert(sparam)) // TODO: This check can make more early
1143
            {
1144
                // in TemplateDeclaration.semantic, and
1145
                // then we don't need to make sparam if flags == 0
1146 0
                goto Lnomatch;
1147
            }
1148
        }
1149

1150 1
        if (!flag)
1151
        {
1152
            /* Any parameter left without a type gets the type of
1153
             * its corresponding arg
1154
             */
1155 1
            foreach (i, ref dedtype; *dedtypes)
1156
            {
1157 1
                if (!dedtype)
1158
                {
1159 0
                    assert(i < ti.tiargs.dim);
1160 0
                    dedtype = cast(Type)(*ti.tiargs)[i];
1161
                }
1162
            }
1163
        }
1164

1165 1
        if (m > MATCH.nomatch && constraint && !flag)
1166
        {
1167 1
            if (ti.hasNestedArgs(ti.tiargs, this.isstatic)) // TODO: should gag error
1168 1
                ti.parent = ti.enclosing;
1169
            else
1170 1
                ti.parent = this.parent;
1171

1172
            // Similar to doHeaderInstantiation
1173 1
            FuncDeclaration fd = onemember ? onemember.isFuncDeclaration() : null;
1174 1
            if (fd)
1175
            {
1176 1
                assert(fd.type.ty == Tfunction);
1177 1
                TypeFunction tf = cast(TypeFunction)fd.type.syntaxCopy();
1178

1179 1
                fd = new FuncDeclaration(fd.loc, fd.endloc, fd.ident, fd.storage_class, tf);
1180 1
                fd.parent = ti;
1181 1
                fd.inferRetType = true;
1182

1183
                // Shouldn't run semantic on default arguments and return type.
1184 1
                foreach (ref param; *tf.parameterList.parameters)
1185 1
                    param.defaultArg = null;
1186

1187 1
                tf.next = null;
1188 1
                tf.incomplete = true;
1189

1190
                // Resolve parameter types and 'auto ref's.
1191 1
                tf.fargs = fargs;
1192 1
                uint olderrors = global.startGagging();
1193 1
                fd.type = tf.typeSemantic(loc, paramscope);
1194 1
                global.endGagging(olderrors);
1195 1
                if (fd.type.ty != Tfunction)
1196 1
                    goto Lnomatch;
1197 1
                fd.originalType = fd.type; // for mangling
1198
            }
1199

1200
            // TODO: dedtypes => ti.tiargs ?
1201 1
            if (!evaluateConstraint(ti, sc, paramscope, dedtypes, fd))
1202 1
                goto Lnomatch;
1203
        }
1204

1205
        static if (LOGM)
1206
        {
1207
            // Print out the results
1208
            printf("--------------------------\n");
1209
            printf("template %s\n", toChars());
1210
            printf("instance %s\n", ti.toChars());
1211
            if (m > MATCH.nomatch)
1212
            {
1213
                for (size_t i = 0; i < dedtypes_dim; i++)
1214
                {
1215
                    TemplateParameter tp = (*parameters)[i];
1216
                    RootObject oarg;
1217
                    printf(" [%d]", i);
1218
                    if (i < ti.tiargs.dim)
1219
                        oarg = (*ti.tiargs)[i];
1220
                    else
1221
                        oarg = null;
1222
                    tp.print(oarg, (*dedtypes)[i]);
1223
                }
1224
            }
1225
            else
1226
                goto Lnomatch;
1227
        }
1228
        static if (LOGM)
1229
        {
1230
            printf(" match = %d\n", m);
1231
        }
1232 1
        goto Lret;
1233

1234
    Lnomatch:
1235
        static if (LOGM)
1236
        {
1237
            printf(" no match\n");
1238
        }
1239 1
        m = MATCH.nomatch;
1240

1241
    Lret:
1242 1
        paramscope.pop();
1243
        static if (LOGM)
1244
        {
1245
            printf("-TemplateDeclaration.matchWithInstance(this = %p, ti = %p) = %d\n", this, ti, m);
1246
        }
1247 1
        return m;
1248
    }
1249

1250
    /********************************************
1251
     * Determine partial specialization order of 'this' vs td2.
1252
     * Returns:
1253
     *      match   this is at least as specialized as td2
1254
     *      0       td2 is more specialized than this
1255
     */
1256
    MATCH leastAsSpecialized(Scope* sc, TemplateDeclaration td2, Expressions* fargs)
1257
    {
1258
        enum LOG_LEASTAS = 0;
1259
        static if (LOG_LEASTAS)
1260
        {
1261
            printf("%s.leastAsSpecialized(%s)\n", toChars(), td2.toChars());
1262
        }
1263

1264
        /* This works by taking the template parameters to this template
1265
         * declaration and feeding them to td2 as if it were a template
1266
         * instance.
1267
         * If it works, then this template is at least as specialized
1268
         * as td2.
1269
         */
1270

1271
        // Set type arguments to dummy template instance to be types
1272
        // generated from the parameters to this template declaration
1273 1
        auto tiargs = new Objects();
1274 1
        tiargs.reserve(parameters.dim);
1275 1
        foreach (tp; *parameters)
1276
        {
1277 1
            if (tp.dependent)
1278 1
                break;
1279 1
            RootObject p = tp.dummyArg();
1280 1
            if (!p) //TemplateTupleParameter
1281 1
                break;
1282

1283 1
            tiargs.push(p);
1284
        }
1285 1
        scope TemplateInstance ti = new TemplateInstance(Loc.initial, ident, tiargs); // create dummy template instance
1286

1287
        // Temporary Array to hold deduced types
1288 1
        Objects dedtypes = Objects(td2.parameters.dim);
1289

1290
        // Attempt a type deduction
1291 1
        MATCH m = td2.matchWithInstance(sc, ti, &dedtypes, fargs, 1);
1292 1
        if (m > MATCH.nomatch)
1293
        {
1294
            /* A non-variadic template is more specialized than a
1295
             * variadic one.
1296
             */
1297 1
            TemplateTupleParameter tp = isVariadic();
1298 1
            if (tp && !tp.dependent && !td2.isVariadic())
1299 1
                goto L1;
1300

1301
            static if (LOG_LEASTAS)
1302
            {
1303
                printf("  matches %d, so is least as specialized\n", m);
1304
            }
1305 1
            return m;
1306
        }
1307
    L1:
1308
        static if (LOG_LEASTAS)
1309
        {
1310
            printf("  doesn't match, so is not as specialized\n");
1311
        }
1312 1
        return MATCH.nomatch;
1313
    }
1314

1315
    /*************************************************
1316
     * Match function arguments against a specific template function.
1317
     * Input:
1318
     *      ti
1319
     *      sc              instantiation scope
1320
     *      fd
1321
     *      tthis           'this' argument if !NULL
1322
     *      fargs           arguments to function
1323
     * Output:
1324
     *      fd              Partially instantiated function declaration
1325
     *      ti.tdtypes     Expression/Type deduced template arguments
1326
     * Returns:
1327
     *      match level
1328
     *          bit 0-3     Match template parameters by inferred template arguments
1329
     *          bit 4-7     Match template parameters by initial template arguments
1330
     */
1331
    extern (D) MATCH deduceFunctionTemplateMatch(TemplateInstance ti, Scope* sc, ref FuncDeclaration fd, Type tthis, Expressions* fargs)
1332
    {
1333 1
        size_t nfparams;
1334 1
        size_t nfargs;
1335 1
        size_t ntargs; // array size of tiargs
1336 1
        size_t fptupindex = IDX_NOTFOUND;
1337 1
        MATCH match = MATCH.exact;
1338 1
        MATCH matchTiargs = MATCH.exact;
1339 1
        ParameterList fparameters; // function parameter list
1340 1
        VarArg fvarargs; // function varargs
1341 1
        uint wildmatch = 0;
1342 1
        size_t inferStart = 0;
1343

1344 1
        Loc instLoc = ti.loc;
1345 1
        Objects* tiargs = ti.tiargs;
1346 1
        auto dedargs = new Objects();
1347 1
        Objects* dedtypes = &ti.tdtypes; // for T:T*, the dedargs is the T*, dedtypes is the T
1348

1349
        version (none)
1350
        {
1351
            printf("\nTemplateDeclaration.deduceFunctionTemplateMatch() %s\n", toChars());
1352
            for (size_t i = 0; i < (fargs ? fargs.dim : 0); i++)
1353
            {
1354
                Expression e = (*fargs)[i];
1355
                printf("\tfarg[%d] is %s, type is %s\n", i, e.toChars(), e.type.toChars());
1356
            }
1357
            printf("fd = %s\n", fd.toChars());
1358
            printf("fd.type = %s\n", fd.type.toChars());
1359
            if (tthis)
1360
                printf("tthis = %s\n", tthis.toChars());
1361
        }
1362

1363 1
        assert(_scope);
1364

1365 1
        dedargs.setDim(parameters.dim);
1366 1
        dedargs.zero();
1367

1368 1
        dedtypes.setDim(parameters.dim);
1369 1
        dedtypes.zero();
1370

1371 1
        if (errors || fd.errors)
1372 0
            return MATCH.nomatch;
1373

1374
        // Set up scope for parameters
1375 1
        Scope* paramscope = scopeForTemplateParameters(ti,sc);
1376

1377
        // Mark the parameter scope as deprecated if the templated
1378
        // function is deprecated (since paramscope.enclosing is the
1379
        // calling scope already)
1380 1
        paramscope.stc |= fd.storage_class & STC.deprecated_;
1381

1382 1
        TemplateTupleParameter tp = isVariadic();
1383 1
        Tuple declaredTuple = null;
1384

1385
        version (none)
1386
        {
1387
            for (size_t i = 0; i < dedargs.dim; i++)
1388
            {
1389
                printf("\tdedarg[%d] = ", i);
1390
                RootObject oarg = (*dedargs)[i];
1391
                if (oarg)
1392
                    printf("%s", oarg.toChars());
1393
                printf("\n");
1394
            }
1395
        }
1396

1397 1
        ntargs = 0;
1398 1
        if (tiargs)
1399
        {
1400
            // Set initial template arguments
1401 1
            ntargs = tiargs.dim;
1402 1
            size_t n = parameters.dim;
1403 1
            if (tp)
1404 1
                n--;
1405 1
            if (ntargs > n)
1406
            {
1407 1
                if (!tp)
1408 1
                    goto Lnomatch;
1409

1410
                /* The extra initial template arguments
1411
                 * now form the tuple argument.
1412
                 */
1413 1
                auto t = new Tuple(ntargs - n);
1414 1
                assert(parameters.dim);
1415 1
                (*dedargs)[parameters.dim - 1] = t;
1416

1417 1
                for (size_t i = 0; i < t.objects.dim; i++)
1418
                {
1419 1
                    t.objects[i] = (*tiargs)[n + i];
1420
                }
1421 1
                declareParameter(paramscope, tp, t);
1422 1
                declaredTuple = t;
1423
            }
1424
            else
1425 1
                n = ntargs;
1426

1427 1
            memcpy(dedargs.tdata(), tiargs.tdata(), n * (*dedargs.tdata()).sizeof);
1428

1429 1
            for (size_t i = 0; i < n; i++)
1430
            {
1431 1
                assert(i < parameters.dim);
1432 1
                Declaration sparam = null;
1433 1
                MATCH m = (*parameters)[i].matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, &sparam);
1434
                //printf("\tdeduceType m = %d\n", m);
1435 1
                if (m <= MATCH.nomatch)
1436 1
                    goto Lnomatch;
1437 1
                if (m < matchTiargs)
1438 1
                    matchTiargs = m;
1439

1440 1
                sparam.dsymbolSemantic(paramscope);
1441 1
                if (!paramscope.insert(sparam))
1442 0
                    goto Lnomatch;
1443
            }
1444 1
            if (n < parameters.dim && !declaredTuple)
1445
            {
1446 1
                inferStart = n;
1447
            }
1448
            else
1449 1
                inferStart = parameters.dim;
1450
            //printf("tiargs matchTiargs = %d\n", matchTiargs);
1451
        }
1452
        version (none)
1453
        {
1454
            for (size_t i = 0; i < dedargs.dim; i++)
1455
            {
1456
                printf("\tdedarg[%d] = ", i);
1457
                RootObject oarg = (*dedargs)[i];
1458
                if (oarg)
1459
                    printf("%s", oarg.toChars());
1460
                printf("\n");
1461
            }
1462
        }
1463

1464 1
        fparameters = fd.getParameterList();
1465 1
        nfparams = fparameters.length; // number of function parameters
1466 1
        nfargs = fargs ? fargs.dim : 0; // number of function arguments
1467

1468
        /* Check for match of function arguments with variadic template
1469
         * parameter, such as:
1470
         *
1471
         * void foo(T, A...)(T t, A a);
1472
         * void main() { foo(1,2,3); }
1473
         */
1474 1
        if (tp) // if variadic
1475
        {
1476
            // TemplateTupleParameter always makes most lesser matching.
1477 1
            matchTiargs = MATCH.convert;
1478

1479 1
            if (nfparams == 0 && nfargs != 0) // if no function parameters
1480
            {
1481 1
                if (!declaredTuple)
1482
                {
1483 1
                    auto t = new Tuple();
1484
                    //printf("t = %p\n", t);
1485 1
                    (*dedargs)[parameters.dim - 1] = t;
1486 1
                    declareParameter(paramscope, tp, t);
1487 1
                    declaredTuple = t;
1488
                }
1489
            }
1490
            else
1491
            {
1492
                /* Figure out which of the function parameters matches
1493
                 * the tuple template parameter. Do this by matching
1494
                 * type identifiers.
1495
                 * Set the index of this function parameter to fptupindex.
1496
                 */
1497 1
                for (fptupindex = 0; fptupindex < nfparams; fptupindex++)
1498
                {
1499 1
                    auto fparam = (*fparameters.parameters)[fptupindex]; // fparameters[fptupindex] ?
1500 1
                    if (fparam.type.ty != Tident)
1501 1
                        continue;
1502 1
                    TypeIdentifier tid = cast(TypeIdentifier)fparam.type;
1503 1
                    if (!tp.ident.equals(tid.ident) || tid.idents.dim)
1504 1
                        continue;
1505

1506 1
                    if (fparameters.varargs != VarArg.none) // variadic function doesn't
1507 0
                        goto Lnomatch; // go with variadic template
1508

1509 1
                    goto L1;
1510
                }
1511 1
                fptupindex = IDX_NOTFOUND;
1512
            L1:
1513
            }
1514
        }
1515

1516 1
        if (toParent().isModule() || (_scope.stc & STC.static_))
1517 1
            tthis = null;
1518 1
        if (tthis)
1519
        {
1520 1
            bool hasttp = false;
1521

1522
            // Match 'tthis' to any TemplateThisParameter's
1523 1
            foreach (param; *parameters)
1524
            {
1525 1
                if (auto ttp = param.isTemplateThisParameter())
1526
                {
1527 1
                    hasttp = true;
1528 1
                    scope t = new TypeIdentifier(Loc.initial, ttp.ident);
1529 1
                    MATCH m = deduceType(tthis, paramscope, t, parameters, dedtypes);
1530 1
                    if (m <= MATCH.nomatch)
1531 0
                        goto Lnomatch;
1532 1
                    if (m < match)
1533 0
                        match = m; // pick worst match
1534
                }
1535
            }
1536

1537
            // Match attributes of tthis against attributes of fd
1538 1
            if (fd.type && !fd.isCtorDeclaration())
1539
            {
1540 1
                StorageClass stc = _scope.stc | fd.storage_class2;
1541
                // Propagate parent storage class, https://issues.dlang.org/show_bug.cgi?id=5504
1542 1
                Dsymbol p = parent;
1543 1
                while (p.isTemplateDeclaration() || p.isTemplateInstance())
1544 1
                    p = p.parent;
1545 1
                AggregateDeclaration ad = p.isAggregateDeclaration();
1546 1
                if (ad)
1547 1
                    stc |= ad.storage_class;
1548

1549 1
                ubyte mod = fd.type.mod;
1550 1
                if (stc & STC.immutable_)
1551 1
                    mod = MODFlags.immutable_;
1552
                else
1553
                {
1554 1
                    if (stc & (STC.shared_ | STC.synchronized_))
1555 1
                        mod |= MODFlags.shared_;
1556 1
                    if (stc & STC.const_)
1557 0
                        mod |= MODFlags.const_;
1558 1
                    if (stc & STC.wild)
1559 0
                        mod |= MODFlags.wild;
1560
                }
1561

1562 1
                ubyte thismod = tthis.mod;
1563 1
                if (hasttp)
1564 1
                    mod = MODmerge(thismod, mod);
1565 1
                MATCH m = MODmethodConv(thismod, mod);
1566 1
                if (m <= MATCH.nomatch)
1567 1
                    goto Lnomatch;
1568 1
                if (m < match)
1569 1
                    match = m;
1570
            }
1571
        }
1572

1573
        // Loop through the function parameters
1574
        {
1575
            //printf("%s\n\tnfargs = %d, nfparams = %d, tuple_dim = %d\n", toChars(), nfargs, nfparams, declaredTuple ? declaredTuple.objects.dim : 0);
1576
            //printf("\ttp = %p, fptupindex = %d, found = %d, declaredTuple = %s\n", tp, fptupindex, fptupindex != IDX_NOTFOUND, declaredTuple ? declaredTuple.toChars() : NULL);
1577 1
            size_t argi = 0;
1578 1
            size_t nfargs2 = nfargs; // nfargs + supplied defaultArgs
1579 1
            for (size_t parami = 0; parami < nfparams; parami++)
1580
            {
1581 1
                Parameter fparam = fparameters[parami];
1582

1583
                // Apply function parameter storage classes to parameter types
1584 1
                Type prmtype = fparam.type.addStorageClass(fparam.storageClass);
1585

1586 1
                Expression farg;
1587

1588
                /* See function parameters which wound up
1589
                 * as part of a template tuple parameter.
1590
                 */
1591 1
                if (fptupindex != IDX_NOTFOUND && parami == fptupindex)
1592
                {
1593 1
                    assert(prmtype.ty == Tident);
1594 1
                    TypeIdentifier tid = cast(TypeIdentifier)prmtype;
1595 1
                    if (!declaredTuple)
1596
                    {
1597
                        /* The types of the function arguments
1598
                         * now form the tuple argument.
1599
                         */
1600 1
                        declaredTuple = new Tuple();
1601 1
                        (*dedargs)[parameters.dim - 1] = declaredTuple;
1602

1603
                        /* Count function parameters with no defaults following a tuple parameter.
1604
                         * void foo(U, T...)(int y, T, U, double, int bar = 0) {}  // rem == 2 (U, double)
1605
                         */
1606 1
                        size_t rem = 0;
1607 1
                        for (size_t j = parami + 1; j < nfparams; j++)
1608
                        {
1609 1
                            Parameter p = fparameters[j];
1610 1
                            if (p.defaultArg)
1611
                            {
1612 1
                               break;
1613
                            }
1614 1
                            if (!reliesOnTemplateParameters(p.type, (*parameters)[inferStart .. parameters.dim]))
1615
                            {
1616 1
                                Type pt = p.type.syntaxCopy().typeSemantic(fd.loc, paramscope);
1617 1
                                rem += pt.ty == Ttuple ? (cast(TypeTuple)pt).arguments.dim : 1;
1618
                            }
1619
                            else
1620
                            {
1621 1
                                ++rem;
1622
                            }
1623
                        }
1624

1625 1
                        if (nfargs2 - argi < rem)
1626 1
                            goto Lnomatch;
1627 1
                        declaredTuple.objects.setDim(nfargs2 - argi - rem);
1628 1
                        for (size_t i = 0; i < declaredTuple.objects.dim; i++)
1629
                        {
1630 1
                            farg = (*fargs)[argi + i];
1631

1632
                            // Check invalid arguments to detect errors early.
1633 1
                            if (farg.op == TOK.error || farg.type.ty == Terror)
1634 0
                                goto Lnomatch;
1635

1636 1
                            if (!(fparam.storageClass & STC.lazy_) && farg.type.ty == Tvoid)
1637 1
                                goto Lnomatch;
1638

1639 1
                            Type tt;
1640 1
                            MATCH m;
1641 1
                            if (ubyte wm = deduceWildHelper(farg.type, &tt, tid))
1642
                            {
1643 1
                                wildmatch |= wm;
1644 1
                                m = MATCH.constant;
1645
                            }
1646
                            else
1647
                            {
1648 1
                                m = deduceTypeHelper(farg.type, &tt, tid);
1649
                            }
1650 1
                            if (m <= MATCH.nomatch)
1651 0
                                goto Lnomatch;
1652 1
                            if (m < match)
1653 1
                                match = m;
1654

1655
                            /* Remove top const for dynamic array types and pointer types
1656
                             */
1657 1
                            if ((tt.ty == Tarray || tt.ty == Tpointer) && !tt.isMutable() && (!(fparam.storageClass & STC.ref_) || (fparam.storageClass & STC.auto_) && !farg.isLvalue()))
1658
                            {
1659 1
                                tt = tt.mutableOf();
1660
                            }
1661 1
                            declaredTuple.objects[i] = tt;
1662
                        }
1663 1
                        declareParameter(paramscope, tp, declaredTuple);
1664
                    }
1665
                    else
1666
                    {
1667
                        // https://issues.dlang.org/show_bug.cgi?id=6810
1668
                        // If declared tuple is not a type tuple,
1669
                        // it cannot be function parameter types.
1670 1
                        for (size_t i = 0; i < declaredTuple.objects.dim; i++)
1671
                        {
1672 1
                            if (!isType(declaredTuple.objects[i]))
1673 1
                                goto Lnomatch;
1674
                        }
1675
                    }
1676 1
                    assert(declaredTuple);
1677 1
                    argi += declaredTuple.objects.dim;
1678 1
                    continue;
1679
                }
1680

1681
                // If parameter type doesn't depend on inferred template parameters,
1682
                // semantic it to get actual type.
1683 1
                if (!reliesOnTemplateParameters(prmtype, (*parameters)[inferStart .. parameters.dim]))
1684
                {
1685
                    // should copy prmtype to avoid affecting semantic result
1686 1
                    prmtype = prmtype.syntaxCopy().typeSemantic(fd.loc, paramscope);
1687

1688 1
                    if (prmtype.ty == Ttuple)
1689
                    {
1690 1
                        TypeTuple tt = cast(TypeTuple)prmtype;
1691 1
                        size_t tt_dim = tt.arguments.dim;
1692 1
                        for (size_t j = 0; j < tt_dim; j++, ++argi)
1693
                        {
1694 1
                            Parameter p = (*tt.arguments)[j];
1695 1
                            if (j == tt_dim - 1 && fparameters.varargs == VarArg.typesafe &&
1696 1
                                parami + 1 == nfparams && argi < nfargs)
1697
                            {
1698 1
                                prmtype = p.type;
1699 1
                                goto Lvarargs;
1700
                            }
1701 1
                            if (argi >= nfargs)
1702
                            {
1703 1
                                if (p.defaultArg)
1704 0
                                    continue;
1705

1706
                                // https://issues.dlang.org/show_bug.cgi?id=19888
1707 1
                                if (fparam.defaultArg)
1708 1
                                    break;
1709

1710 1
                                goto Lnomatch;
1711
                            }
1712 1
                            farg = (*fargs)[argi];
1713 1
                            if (!farg.implicitConvTo(p.type))
1714 1
                                goto Lnomatch;
1715
                        }
1716 1
                        continue;
1717
                    }
1718
                }
1719

1720 1
                if (argi >= nfargs) // if not enough arguments
1721
                {
1722 1
                    if (!fparam.defaultArg)
1723 1
                        goto Lvarargs;
1724

1725
                    /* https://issues.dlang.org/show_bug.cgi?id=2803
1726
                     * Before the starting of type deduction from the function
1727
                     * default arguments, set the already deduced parameters into paramscope.
1728
                     * It's necessary to avoid breaking existing acceptable code. Cases:
1729
                     *
1730
                     * 1. Already deduced template parameters can appear in fparam.defaultArg:
1731
                     *  auto foo(A, B)(A a, B b = A.stringof);
1732
                     *  foo(1);
1733
                     *  // at fparam == 'B b = A.string', A is equivalent with the deduced type 'int'
1734
                     *
1735
                     * 2. If prmtype depends on default-specified template parameter, the
1736
                     * default type should be preferred.
1737
                     *  auto foo(N = size_t, R)(R r, N start = 0)
1738
                     *  foo([1,2,3]);
1739
                     *  // at fparam `N start = 0`, N should be 'size_t' before
1740
                     *  // the deduction result from fparam.defaultArg.
1741
                     */
1742 1
                    if (argi == nfargs)
1743
                    {
1744 1
                        foreach (ref dedtype; *dedtypes)
1745
                        {
1746 1
                            Type at = isType(dedtype);
1747 1
                            if (at && at.ty == Tnone)
1748
                            {
1749 1
                                TypeDeduced xt = cast(TypeDeduced)at;
1750 1
                                dedtype = xt.tded; // 'unbox'
1751
                            }
1752
                        }
1753 1
                        for (size_t i = ntargs; i < dedargs.dim; i++)
1754
                        {
1755 1
                            TemplateParameter tparam = (*parameters)[i];
1756

1757 1
                            RootObject oarg = (*dedargs)[i];
1758 1
                            RootObject oded = (*dedtypes)[i];
1759 1
                            if (!oarg)
1760
                            {
1761 1
                                if (oded)
1762
                                {
1763 1
                                    if (tparam.specialization() || !tparam.isTemplateTypeParameter())
1764
                                    {
1765
                                        /* The specialization can work as long as afterwards
1766
                                         * the oded == oarg
1767
                                         */
1768 1
                                        (*dedargs)[i] = oded;
1769 1
                                        MATCH m2 = tparam.matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, null);
1770
                                        //printf("m2 = %d\n", m2);
1771 1
                                        if (m2 <= MATCH.nomatch)
1772 1
                                            goto Lnomatch;
1773 1
                                        if (m2 < matchTiargs)
1774 0
                                            matchTiargs = m2; // pick worst match
1775 1
                                        if (!(*dedtypes)[i].equals(oded))
1776 0
                                            error("specialization not allowed for deduced parameter `%s`", tparam.ident.toChars());
1777
                                    }
1778
                                    else
1779
                                    {
1780 1
                                        if (MATCH.convert < matchTiargs)
1781 1
                                            matchTiargs = MATCH.convert;
1782
                                    }
1783 1
                                    (*dedargs)[i] = declareParameter(paramscope, tparam, oded);
1784
                                }
1785
                                else
1786
                                {
1787 1
                                    inuse++;
1788 1
                                    oded = tparam.defaultArg(instLoc, paramscope);
1789 1
                                    inuse--;
1790 1
                                    if (oded)
1791 1
                                        (*dedargs)[i] = declareParameter(paramscope, tparam, oded);
1792
                                }
1793
                            }
1794
                        }
1795
                    }
1796 1
                    nfargs2 = argi + 1;
1797

1798
                    /* If prmtype does not depend on any template parameters:
1799
                     *
1800
                     *  auto foo(T)(T v, double x = 0);
1801
                     *  foo("str");
1802
                     *  // at fparam == 'double x = 0'
1803
                     *
1804
                     * or, if all template parameters in the prmtype are already deduced:
1805
                     *
1806
                     *  auto foo(R)(R range, ElementType!R sum = 0);
1807
                     *  foo([1,2,3]);
1808
                     *  // at fparam == 'ElementType!R sum = 0'
1809
                     *
1810
                     * Deducing prmtype from fparam.defaultArg is not necessary.
1811
                     */
1812 1
                    if (prmtype.deco || prmtype.syntaxCopy().trySemantic(loc, paramscope))
1813
                    {
1814 1
                        ++argi;
1815 1
                        continue;
1816
                    }
1817

1818
                    // Deduce prmtype from the defaultArg.
1819 1
                    farg = fparam.defaultArg.syntaxCopy();
1820 1
                    farg = farg.expressionSemantic(paramscope);
1821 1
                    farg = resolveProperties(paramscope, farg);
1822
                }
1823
                else
1824
                {
1825 1
                    farg = (*fargs)[argi];
1826
                }
1827
                {
1828
                    // Check invalid arguments to detect errors early.
1829 1
                    if (farg.op == TOK.error || farg.type.ty == Terror)
1830 0
                        goto Lnomatch;
1831

1832 1
                    Type att = null;
1833
                Lretry:
1834
                    version (none)
1835
                    {
1836
                        printf("\tfarg.type   = %s\n", farg.type.toChars());
1837
                        printf("\tfparam.type = %s\n", prmtype.toChars());
1838
                    }
1839 1
                    Type argtype = farg.type;
1840

1841 1
                    if (!(fparam.storageClass & STC.lazy_) && argtype.ty == Tvoid && farg.op != TOK.function_)
1842 0
                        goto Lnomatch;
1843

1844
                    // https://issues.dlang.org/show_bug.cgi?id=12876
1845
                    // Optimize argument to allow CT-known length matching
1846 1
                    farg = farg.optimize(WANTvalue, (fparam.storageClass & (STC.ref_ | STC.out_)) != 0);
1847
                    //printf("farg = %s %s\n", farg.type.toChars(), farg.toChars());
1848

1849 1
                    RootObject oarg = farg;
1850 1
                    if ((fparam.storageClass & STC.ref_) && (!(fparam.storageClass & STC.auto_) || farg.isLvalue()))
1851
                    {
1852
                        /* Allow expressions that have CT-known boundaries and type [] to match with [dim]
1853
                         */
1854 1
                        Type taai;
1855 1
                        if (argtype.ty == Tarray && (prmtype.ty == Tsarray || prmtype.ty == Taarray && (taai = (cast(TypeAArray)prmtype).index).ty == Tident && (cast(TypeIdentifier)taai).idents.dim == 0))
1856
                        {
1857 1
                            if (farg.op == TOK.string_)
1858
                            {
1859 1
                                StringExp se = cast(StringExp)farg;
1860 1
                                argtype = se.type.nextOf().sarrayOf(se.len);
1861
                            }
1862 1
                            else if (farg.op == TOK.arrayLiteral)
1863
                            {
1864 0
                                ArrayLiteralExp ae = cast(ArrayLiteralExp)farg;
1865 0
                                argtype = ae.type.nextOf().sarrayOf(ae.elements.dim);
1866
                            }
1867 1
                            else if (farg.op == TOK.slice)
1868
                            {
1869 1
                                SliceExp se = cast(SliceExp)farg;
1870 1
                                if (Type tsa = toStaticArrayType(se))
1871 1
                                    argtype = tsa;
1872
                            }
1873
                        }
1874

1875 1
                        oarg = argtype;
1876
                    }
1877 1
                    else if ((fparam.storageClass & STC.out_) == 0 && (argtype.ty == Tarray || argtype.ty == Tpointer) && templateParameterLookup(prmtype, parameters) != IDX_NOTFOUND && (cast(TypeIdentifier)prmtype).idents.dim == 0)
1878
                    {
1879
                        /* The farg passing to the prmtype always make a copy. Therefore,
1880
                         * we can shrink the set of the deduced type arguments for prmtype
1881
                         * by adjusting top-qualifier of the argtype.
1882
                         *
1883
                         *  prmtype         argtype     ta
1884
                         *  T            <- const(E)[]  const(E)[]
1885
                         *  T            <- const(E[])  const(E)[]
1886
                         *  qualifier(T) <- const(E)[]  const(E[])
1887
                         *  qualifier(T) <- const(E[])  const(E[])
1888
                         */
1889 1
                        Type ta = argtype.castMod(prmtype.mod ? argtype.nextOf().mod : 0);
1890 1
                        if (ta != argtype)
1891
                        {
1892 1
                            Expression ea = farg.copy();
1893 1
                            ea.type = ta;
1894 1
                            oarg = ea;
1895
                        }
1896
                    }
1897

1898 1
                    if (fparameters.varargs == VarArg.typesafe && parami + 1 == nfparams && argi + 1 < nfargs)
1899 1
                        goto Lvarargs;
1900

1901 1
                    uint wm = 0;
1902 1
                    MATCH m = deduceType(oarg, paramscope, prmtype, parameters, dedtypes, &wm, inferStart);
1903
                    //printf("\tL%d deduceType m = %d, wm = x%x, wildmatch = x%x\n", __LINE__, m, wm, wildmatch);
1904 1
                    wildmatch |= wm;
1905

1906
                    /* If no match, see if the argument can be matched by using
1907
                     * implicit conversions.
1908
                     */
1909 1
                    if (m == MATCH.nomatch && prmtype.deco)
1910 1
                        m = farg.implicitConvTo(prmtype);
1911

1912 1
                    if (m == MATCH.nomatch)
1913
                    {
1914 1
                        AggregateDeclaration ad = isAggregate(farg.type);
1915 1
                        if (ad && ad.aliasthis && argtype != att)
1916
                        {
1917 1
                            if (!att && argtype.checkAliasThisRec())   // https://issues.dlang.org/show_bug.cgi?id=12537
1918 1
                                att = argtype;
1919
                            /* If a semantic error occurs while doing alias this,
1920
                             * eg purity(https://issues.dlang.org/show_bug.cgi?id=7295),
1921
                             * just regard it as not a match.
1922
                             */
1923 1
                            if (auto e = resolveAliasThis(sc, farg, true))
1924
                            {
1925 1
                                farg = e;
1926 1
                                goto Lretry;
1927
                            }
1928
                        }
1929
                    }
1930

1931 1
                    if (m > MATCH.nomatch && (fparam.storageClass & (STC.ref_ | STC.auto_)) == STC.ref_)
1932
                    {
1933 1
                        if (!farg.isLvalue())
1934
                        {
1935 1
                            if ((farg.op == TOK.string_ || farg.op == TOK.slice) && (prmtype.ty == Tsarray || prmtype.ty == Taarray))
1936
                            {
1937
                                // Allow conversion from T[lwr .. upr] to ref T[upr-lwr]
1938
                            }
1939
                            else
1940 1
                                goto Lnomatch;
1941
                        }
1942
                    }
1943 1
                    if (m > MATCH.nomatch && (fparam.storageClass & STC.out_))
1944
                    {
1945 1
                        if (!farg.isLvalue())
1946 1
                            goto Lnomatch;
1947 1
                        if (!farg.type.isMutable()) // https://issues.dlang.org/show_bug.cgi?id=11916
1948 1
                            goto Lnomatch;
1949
                    }
1950 1
                    if (m == MATCH.nomatch && (fparam.storageClass & STC.lazy_) && prmtype.ty == Tvoid && farg.type.ty != Tvoid)
1951 1
                        m = MATCH.convert;
1952 1
                    if (m != MATCH.nomatch)
1953
                    {
1954 1
                        if (m < match)
1955 1
                            match = m; // pick worst match
1956 1
                        argi++;
1957 1
                        continue;
1958
                    }
1959
                }
1960

1961
            Lvarargs:
1962
                /* The following code for variadic arguments closely
1963
                 * matches TypeFunction.callMatch()
1964
                 */
1965 1
                if (!(fparameters.varargs == VarArg.typesafe && parami + 1 == nfparams))
1966 1
                    goto Lnomatch;
1967

1968
                /* Check for match with function parameter T...
1969
                 */
1970 1
                Type tb = prmtype.toBasetype();
1971 1
                switch (tb.ty)
1972
                {
1973
                    // 6764 fix - TypeAArray may be TypeSArray have not yet run semantic().
1974 1
                case Tsarray:
1975 1
                case Taarray:
1976
                    {
1977
                        // Perhaps we can do better with this, see TypeFunction.callMatch()
1978 1
                        if (tb.ty == Tsarray)
1979
                        {
1980 1
                            TypeSArray tsa = cast(TypeSArray)tb;
1981 1
                            dinteger_t sz = tsa.dim.toInteger();
1982 1
                            if (sz != nfargs - argi)
1983 1
                                goto Lnomatch;
1984
                        }
1985 1
                        else if (tb.ty == Taarray)
1986
                        {
1987 1
                            TypeAArray taa = cast(TypeAArray)tb;
1988 1
                            Expression dim = new IntegerExp(instLoc, nfargs - argi, Type.tsize_t);
1989

1990 1
                            size_t i = templateParameterLookup(taa.index, parameters);
1991 1
                            if (i == IDX_NOTFOUND)
1992
                            {
1993 1
                                Expression e;
1994 1
                                Type t;
1995 1
                                Dsymbol s;
1996 1
                                Scope *sco;
1997

1998 1
                                uint errors = global.startGagging();
1999
                                /* ref: https://issues.dlang.org/show_bug.cgi?id=11118
2000
                                 * The parameter isn't part of the template
2001
                                 * ones, let's try to find it in the
2002
                                 * instantiation scope 'sc' and the one
2003
                                 * belonging to the template itself. */
2004 1
                                sco = sc;
2005 1
                                taa.index.resolve(instLoc, sco, &e, &t, &s);
2006 1
                                if (!e)
2007
                                {
2008 1
                                    sco = paramscope;
2009 1
                                    taa.index.resolve(instLoc, sco, &e, &t, &s);
2010
                                }
2011 1
                                global.endGagging(errors);
2012

2013 1
                                if (!e)
2014
                                {
2015 0
                                    goto Lnomatch;
2016
                                }
2017

2018 1
                                e = e.ctfeInterpret();
2019 1
                                e = e.implicitCastTo(sco, Type.tsize_t);
2020 1
                                e = e.optimize(WANTvalue);
2021 1
                                if (!dim.equals(e))
2022 0
                                    goto Lnomatch;
2023
                            }
2024
                            else
2025
                            {
2026
                                // This code matches code in TypeInstance.deduceType()
2027 1
                                TemplateParameter tprm = (*parameters)[i];
2028 1
                                TemplateValueParameter tvp = tprm.isTemplateValueParameter();
2029 1
                                if (!tvp)
2030 0
                                    goto Lnomatch;
2031 1
                                Expression e = cast(Expression)(*dedtypes)[i];
2032 1
                                if (e)
2033
                                {
2034 0
                                    if (!dim.equals(e))
2035 0
                                        goto Lnomatch;
2036
                                }
2037
                                else
2038
                                {
2039 1
                                    Type vt = tvp.valType.typeSemantic(Loc.initial, sc);
2040 1
                                    MATCH m = dim.implicitConvTo(vt);
2041 1
                                    if (m <= MATCH.nomatch)
2042 0
                                        goto Lnomatch;
2043 1
                                    (*dedtypes)[i] = dim;
2044
                                }
2045
                            }
2046
                        }
2047 1
                        goto case Tarray;
2048
                    }
2049 1
                case Tarray:
2050
                    {
2051 1
                        TypeArray ta = cast(TypeArray)tb;
2052 1
                        Type tret = fparam.isLazyArray();
2053 1
                        for (; argi < nfargs; argi++)
2054
                        {
2055 1
                            Expression arg = (*fargs)[argi];
2056 1
                            assert(arg);
2057

2058 1
                            MATCH m;
2059
                            /* If lazy array of delegates,
2060
                             * convert arg(s) to delegate(s)
2061
                             */
2062 1
                            if (tret)
2063
                            {
2064 0
                                if (ta.next.equals(arg.type))
2065
                                {
2066 0
                                    m = MATCH.exact;
2067
                                }
2068
                                else
2069
                                {
2070 0
                                    m = arg.implicitConvTo(tret);
2071 0
                                    if (m == MATCH.nomatch)
2072
                                    {
2073 0
                                        if (tret.toBasetype().ty == Tvoid)
2074 0
                                            m = MATCH.convert;
2075
                                    }
2076
                                }
2077
                            }
2078
                            else
2079
                            {
2080 1
                                uint wm = 0;
2081 1
                                m = deduceType(arg, paramscope, ta.next, parameters, dedtypes, &wm, inferStart);
2082 1
                                wildmatch |= wm;
2083
                            }
2084 1
                            if (m == MATCH.nomatch)
2085 1
                                goto Lnomatch;
2086 1
                            if (m < match)
2087 1
                                match = m;
2088
                        }
2089 1
                        goto Lmatch;
2090
                    }
2091 0
                case Tclass:
2092 0
                case Tident:
2093 0
                    goto Lmatch;
2094

2095 1
                default:
2096 1
                    goto Lnomatch;
2097
                }
2098 0
                assert(0);
2099
            }
2100
            //printf(". argi = %d, nfargs = %d, nfargs2 = %d\n", argi, nfargs, nfargs2);
2101 1
            if (argi != nfargs2 && fparameters.varargs == VarArg.none)
2102 1
                goto Lnomatch;
2103
        }
2104

2105
    Lmatch:
2106 1
        foreach (ref dedtype; *dedtypes)
2107
        {
2108 1
            Type at = isType(dedtype);
2109 1
            if (at)
2110
            {
2111 1
                if (at.ty == Tnone)
2112
                {
2113 1
                    TypeDeduced xt = cast(TypeDeduced)at;
2114 1
                    at = xt.tded; // 'unbox'
2115
                }
2116 1
                dedtype = at.merge2();
2117
            }
2118
        }
2119 1
        for (size_t i = ntargs; i < dedargs.dim; i++)
2120
        {
2121 1
            TemplateParameter tparam = (*parameters)[i];
2122
            //printf("tparam[%d] = %s\n", i, tparam.ident.toChars());
2123

2124
            /* For T:T*, the dedargs is the T*, dedtypes is the T
2125
             * But for function templates, we really need them to match
2126
             */
2127 1
            RootObject oarg = (*dedargs)[i];
2128 1
            RootObject oded = (*dedtypes)[i];
2129
            //printf("1dedargs[%d] = %p, dedtypes[%d] = %p\n", i, oarg, i, oded);
2130
            //if (oarg) printf("oarg: %s\n", oarg.toChars());
2131
            //if (oded) printf("oded: %s\n", oded.toChars());
2132 1
            if (!oarg)
2133
            {
2134 1
                if (oded)
2135
                {
2136 1
                    if (tparam.specialization() || !tparam.isTemplateTypeParameter())
2137
                    {
2138
                        /* The specialization can work as long as afterwards
2139
                         * the oded == oarg
2140
                         */
2141 1
                        (*dedargs)[i] = oded;
2142 1
                        MATCH m2 = tparam.matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, null);
2143
                        //printf("m2 = %d\n", m2);
2144 1
                        if (m2 <= MATCH.nomatch)
2145 1
                            goto Lnomatch;
2146 1
                        if (m2 < matchTiargs)
2147 1
                            matchTiargs = m2; // pick worst match
2148 1
                        if (!(*dedtypes)[i].equals(oded))
2149 0
                            error("specialization not allowed for deduced parameter `%s`", tparam.ident.toChars());
2150
                    }
2151
                    else
2152
                    {
2153
                        // Discussion: https://issues.dlang.org/show_bug.cgi?id=16484
2154 1
                        if (MATCH.convert < matchTiargs)
2155 1
                            matchTiargs = MATCH.convert;
2156
                    }
2157
                }
2158
                else
2159
                {
2160 1
                    inuse++;
2161 1
                    oded = tparam.defaultArg(instLoc, paramscope);
2162 1
                    inuse--;
2163 1
                    if (!oded)
2164
                    {
2165
                        // if tuple parameter and
2166
                        // tuple parameter was not in function parameter list and
2167
                        // we're one or more arguments short (i.e. no tuple argument)
2168 1
                        if (tparam == tp &&
2169 1
                            fptupindex == IDX_NOTFOUND &&
2170 1
                            ntargs <= dedargs.dim - 1)
2171
                        {
2172
                            // make tuple argument an empty tuple
2173 1
                            oded = new Tuple();
2174
                        }
2175
                        else
2176 1
                            goto Lnomatch;
2177
                    }
2178 1
                    if (isError(oded))
2179 1
                        goto Lerror;
2180 1
                    ntargs++;
2181

2182
                    /* At the template parameter T, the picked default template argument
2183
                     * X!int should be matched to T in order to deduce dependent
2184
                     * template parameter A.
2185
                     *  auto foo(T : X!A = X!int, A...)() { ... }
2186
                     *  foo();  // T <-- X!int, A <-- (int)
2187
                     */
2188 1
                    if (tparam.specialization())
2189
                    {
2190 1
                        (*dedargs)[i] = oded;
2191 1
                        MATCH m2 = tparam.matchArg(instLoc, paramscope, dedargs, i, parameters, dedtypes, null);
2192
                        //printf("m2 = %d\n", m2);
2193 1
                        if (m2 <= MATCH.nomatch)
2194 0
                            goto Lnomatch;
2195 1
                        if (m2 < matchTiargs)
2196 1
                            matchTiargs = m2; // pick worst match
2197 1
                        if (!(*dedtypes)[i].equals(oded))
2198 0
                            error("specialization not allowed for deduced parameter `%s`", tparam.ident.toChars());
2199
                    }
2200
                }
2201 1
                oded = declareParameter(paramscope, tparam, oded);
2202 1
                (*dedargs)[i] = oded;
2203
            }
2204
        }
2205

2206
        /* https://issues.dlang.org/show_bug.cgi?id=7469
2207
         * As same as the code for 7469 in findBestMatch,
2208
         * expand a Tuple in dedargs to normalize template arguments.
2209
         */
2210 1
        if (auto d = dedargs.dim)
2211
        {
2212 1
            if (auto va = isTuple((*dedargs)[d - 1]))
2213
            {
2214 1
                dedargs.setDim(d - 1);
2215 1
                dedargs.insert(d - 1, &va.objects);
2216
            }
2217
        }
2218 1
        ti.tiargs = dedargs; // update to the normalized template arguments.
2219

2220
        // Partially instantiate function for constraint and fd.leastAsSpecialized()
2221
        {
2222 1
            assert(paramscope.scopesym);
2223 1
            Scope* sc2 = _scope;
2224 1
            sc2 = sc2.push(paramscope.scopesym);
2225 1
            sc2 = sc2.push(ti);
2226 1
            sc2.parent = ti;
2227 1
            sc2.tinst = ti;
2228 1
            sc2.minst = sc.minst;
2229 1
            sc2.stc |= fd.storage_class & STC.deprecated_;
2230

2231 1
            fd = doHeaderInstantiation(ti, sc2, fd, tthis, fargs);
2232

2233 1
            sc2 = sc2.pop();
2234 1
            sc2 = sc2.pop();
2235

2236 1
            if (!fd)
2237 1
                goto Lnomatch;
2238
        }
2239

2240 1
        if (constraint)
2241
        {
2242 1
            if (!evaluateConstraint(ti, sc, paramscope, dedargs, fd))
2243 1
                goto Lnomatch;
2244
        }
2245

2246
        version (none)
2247
        {
2248
            for (size_t i = 0; i < dedargs.dim; i++)
2249
            {
2250
                RootObject o = (*dedargs)[i];
2251
                printf("\tdedargs[%d] = %d, %s\n", i, o.dyncast(), o.toChars());
2252
            }
2253
        }
2254

2255 1
        paramscope.pop();
2256
        //printf("\tmatch %d\n", match);
2257 1
        return cast(MATCH)(match | (matchTiargs << 4));
2258

2259
    Lnomatch:
2260 1
        paramscope.pop();
2261
        //printf("\tnomatch\n");
2262 1
        return MATCH.nomatch;
2263

2264
    Lerror:
2265
        // todo: for the future improvement
2266 1
        paramscope.pop();
2267
        //printf("\terror\n");
2268 1
        return MATCH.nomatch;
2269
    }
2270

2271
    /**************************************************
2272
     * Declare template parameter tp with value o, and install it in the scope sc.
2273
     */
2274
    RootObject declareParameter(Scope* sc, TemplateParameter tp, RootObject o)
2275
    {
2276
        //printf("TemplateDeclaration.declareParameter('%s', o = %p)\n", tp.ident.toChars(), o);
2277 1
        Type ta = isType(o);
2278 1
        Expression ea = isExpression(o);
2279 1
        Dsymbol sa = isDsymbol(o);
2280 1
        Tuple va = isTuple(o);
2281

2282 1
        Declaration d;
2283 1
        VarDeclaration v = null;
2284

2285 1
        if (ea && ea.op == TOK.type)
2286 0
            ta = ea.type;
2287 1
        else if (ea && ea.op == TOK.scope_)
2288 0
            sa = (cast(ScopeExp)ea).sds;
2289 1
        else if (ea && (ea.op == TOK.this_ || ea.op == TOK.super_))
2290 0
            sa = (cast(ThisExp)ea).var;
2291 1
        else if (ea && ea.op == TOK.function_)
2292
        {
2293 1
            if ((cast(FuncExp)ea).td)
2294 1
                sa = (cast(FuncExp)ea).td;
2295
            else
2296 1
                sa = (cast(FuncExp)ea).fd;
2297
        }
2298

2299 1
        if (ta)
2300
        {
2301
            //printf("type %s\n", ta.toChars());
2302 1
            auto ad = new AliasDeclaration(Loc.initial, tp.ident, ta);
2303 1
            ad.storage_class |= STC.templateparameter;
2304 1
            d = ad;
2305
        }
2306 1
        else if (sa)
2307
        {
2308
            //printf("Alias %s %s;\n", sa.ident.toChars(), tp.ident.toChars());
2309 1
            auto ad = new AliasDeclaration(Loc.initial, tp.ident, sa);
2310 1
            ad.storage_class |= STC.templateparameter;
2311 1
            d = ad;
2312
        }
2313 1
        else if (ea)
2314
        {
2315
            // tdtypes.data[i] always matches ea here
2316 1
            Initializer _init = new ExpInitializer(loc, ea);
2317 1
            TemplateValueParameter tvp = tp.isTemplateValueParameter();
2318 1
            Type t = tvp ? tvp.valType : null;
2319 1
            v = new VarDeclaration(loc, t, tp.ident, _init);
2320 1
            v.storage_class = STC.manifest | STC.templateparameter;
2321 1
            d = v;
2322
        }
2323 1
        else if (va)
2324
        {
2325
            //printf("\ttuple\n");
2326 1
            d = new TupleDeclaration(loc, tp.ident, &va.objects);
2327
        }
2328
        else
2329
        {
2330 0
            assert(0);
2331
        }
2332 1
        d.storage_class |= STC.templateparameter;
2333

2334 1
        if (ta)
2335
        {
2336 1
            Type t = ta;
2337
            // consistent with Type.checkDeprecated()
2338 1
            while (t.ty != Tenum)
2339
            {
2340 1
                if (!t.nextOf())
2341 1
                    break;
2342 1
                t = (cast(TypeNext)t).next;
2343
            }
2344 1
            if (Dsymbol s = t.toDsymbol(sc))
2345
            {
2346 1
                if (s.isDeprecated())
2347 1
                    d.storage_class |= STC.deprecated_;
2348
            }
2349
        }
2350 1
        else if (sa)
2351
        {
2352 1
            if (sa.isDeprecated())
2353 1
                d.storage_class |= STC.deprecated_;
2354
        }
2355

2356 1
        if (!sc.insert(d))
2357 0
            error("declaration `%s` is already defined", tp.ident.toChars());
2358 1
        d.dsymbolSemantic(sc);
2359
        /* So the caller's o gets updated with the result of semantic() being run on o
2360
         */
2361 1
        if (v)
2362 1
            o = v._init.initializerToExpression();
2363 1
        return o;
2364
    }
2365

2366
    /*************************************************
2367
     * Limited function template instantiation for using fd.leastAsSpecialized()
2368
     */
2369
    extern (D) FuncDeclaration doHeaderInstantiation(TemplateInstance ti, Scope* sc2, FuncDeclaration fd, Type tthis, Expressions* fargs)
2370
    {
2371 1
        assert(fd);
2372
        version (none)
2373
        {
2374
            printf("doHeaderInstantiation this = %s\n", toChars());
2375
        }
2376

2377
        // function body and contracts are not need
2378 1
        if (fd.isCtorDeclaration())
2379 1
            fd = new CtorDeclaration(fd.loc, fd.endloc, fd.storage_class, fd.type.syntaxCopy());
2380
        else
2381 1
            fd = new FuncDeclaration(fd.loc, fd.endloc, fd.ident, fd.storage_class, fd.type.syntaxCopy());
2382 1
        fd.parent = ti;
2383

2384 1
        assert(fd.type.ty == Tfunction);
2385 1
        TypeFunction tf = cast(TypeFunction)fd.type;
2386 1
        tf.fargs = fargs;
2387

2388 1
        if (tthis)
2389
        {
2390
            // Match 'tthis' to any TemplateThisParameter's
2391 1
            bool hasttp = false;
2392 1
            foreach (tp; *parameters)
2393
            {
2394 1
                TemplateThisParameter ttp = tp.isTemplateThisParameter();
2395 1
                if (ttp)
2396 1
                    hasttp = true;
2397
            }
2398 1
            if (hasttp)
2399
            {
2400 1
                tf = cast(TypeFunction)tf.addSTC(ModToStc(tthis.mod));
2401 1
                assert(!tf.deco);
2402
            }
2403
        }
2404

2405 1
        Scope* scx = sc2.push();
2406

2407
        // Shouldn't run semantic on default arguments and return type.
2408 1
        foreach (ref params; *tf.parameterList.parameters)
2409 1
            params.defaultArg = null;
2410 1
        tf.incomplete = true;
2411

2412 1
        if (fd.isCtorDeclaration())
2413
        {
2414
            // For constructors, emitting return type is necessary for
2415
            // isReturnIsolated() in functionResolve.
2416 1
            scx.flags |= SCOPE.ctor;
2417

2418 1
            Dsymbol parent = toParentDecl();
2419 1
            Type tret;
2420 1
            AggregateDeclaration ad = parent.isAggregateDeclaration();
2421 1
            if (!ad || parent.isUnionDeclaration())
2422
            {
2423 0
                tret = Type.tvoid;
2424
            }
2425
            else
2426
            {
2427 1
                tret = ad.handleType();
2428 1
                assert(tret);
2429 1
                tret = tret.addStorageClass(fd.storage_class | scx.stc);
2430 1
                tret = tret.addMod(tf.mod);
2431
            }
2432 1
            tf.next = tret;
2433 1
            if (ad && ad.isStructDeclaration())
2434 1
                tf.isref = 1;
2435
            //printf("tf = %s\n", tf.toChars());
2436
        }
2437
        else
2438 1
            tf.next = null;
2439 1
        fd.type = tf;
2440 1
        fd.type = fd.type.addSTC(scx.stc);
2441 1
        fd.type = fd.type.typeSemantic(fd.loc, scx);
2442 1
        scx = scx.pop();
2443

2444 1
        if (fd.type.ty != Tfunction)
2445 1
            return null;
2446

2447 1
        fd.originalType = fd.type; // for mangling
2448
        //printf("\t[%s] fd.type = %s, mod = %x, ", loc.toChars(), fd.type.toChars(), fd.type.mod);
2449
        //printf("fd.needThis() = %d\n", fd.needThis());
2450

2451 1
        return fd;
2452
    }
2453

2454
    debug (FindExistingInstance)
2455
    {
2456
        __gshared uint nFound, nNotFound, nAdded, nRemoved;
2457

2458
        shared static ~this()
2459
        {
2460
            printf("debug (FindExistingInstance) nFound %u, nNotFound: %u, nAdded: %u, nRemoved: %u\n",
2461
                   nFound, nNotFound, nAdded, nRemoved);
2462
        }
2463
    }
2464

2465
    /****************************************************
2466
     * Given a new instance tithis of this TemplateDeclaration,
2467
     * see if there already exists an instance.
2468
     * If so, return that existing instance.
2469
     */
2470
    extern (D) TemplateInstance findExistingInstance(TemplateInstance tithis, Expressions* fargs)
2471
    {
2472
        //printf("findExistingInstance(%p)\n", tithis);
2473 1
        tithis.fargs = fargs;
2474 1
        auto tibox = TemplateInstanceBox(tithis);
2475 1
        auto p = tibox in instances;
2476
        debug (FindExistingInstance) ++(p ? nFound : nNotFound);
2477
        //if (p) printf("\tfound %p\n", *p); else printf("\tnot found\n");
2478 1
        return p ? *p : null;
2479
    }
2480

2481
    /********************************************
2482
     * Add instance ti to TemplateDeclaration's table of instances.
2483
     * Return a handle we can use to later remove it if it fails instantiation.
2484
     */
2485
    extern (D) TemplateInstance addInstance(TemplateInstance ti)
2486
    {
2487
        //printf("addInstance() %p %p\n", instances, ti);
2488 1
        auto tibox = TemplateInstanceBox(ti);
2489 1
        instances[tibox] = ti;
2490
        debug (FindExistingInstance) ++nAdded;
2491 1
        return ti;
2492
    }
2493

2494
    /*******************************************
2495
     * Remove TemplateInstance from table of instances.
2496
     * Input:
2497
     *      handle returned by addInstance()
2498
     */
2499
    extern (D) void removeInstance(TemplateInstance ti)
2500
    {
2501
        //printf("removeInstance()\n");
2502 1
        auto tibox = TemplateInstanceBox(ti);
2503
        debug (FindExistingInstance) ++nRemoved;
2504 1
        instances.remove(tibox);
2505
    }
2506

2507
    override inout(TemplateDeclaration) isTemplateDeclaration() inout
2508
    {
2509 1
        return this;
2510
    }
2511

2512
    /**
2513
     * Check if the last template parameter is a tuple one,
2514
     * and returns it if so, else returns `null`.
2515
     *
2516
     * Returns:
2517
     *   The last template parameter if it's a `TemplateTupleParameter`
2518
     */
2519
    TemplateTupleParameter isVariadic()
2520
    {
2521 1
        size_t dim = parameters.dim;
2522 1
        if (dim == 0)
2523 1
            return null;
2524 1
        return (*parameters)[dim - 1].isTemplateTupleParameter();
2525
    }
2526

2527
    extern(C++) override bool isDeprecated() const
2528
    {
2529 1
        return this.deprecated_;
2530
    }
2531

2532
    /***********************************
2533
     * We can overload templates.
2534
     */
2535
    override bool isOverloadable() const
2536
    {
2537 1
        return true;
2538
    }
2539

2540
    override void accept(Visitor v)
2541
    {
2542 1
        v.visit(this);
2543
    }
2544
}
2545

2546
extern (C++) final class TypeDeduced : Type
2547
{
2548
    Type tded;
2549
    Expressions argexps; // corresponding expressions
2550
    Types tparams; // tparams[i].mod
2551

2552 1
    extern (D) this(Type tt, Expression e, Type tparam)
2553
    {
2554 1
        super(Tnone);
2555 1
        tded = tt;
2556 1
        argexps.push(e);
2557 1
        tparams.push(tparam);
2558
    }
2559

2560
    void update(Expression e, Type tparam)
2561
    {
2562 1
        argexps.push(e);
2563 1
        tparams.push(tparam);
2564
    }
2565

2566
    void update(Type tt, Expression e, Type tparam)
2567
    {
2568 1
        tded = tt;
2569 1
        argexps.push(e);
2570 1
        tparams.push(tparam);
2571
    }
2572

2573
    MATCH matchAll(Type tt)
2574
    {
2575 1
        MATCH match = MATCH.exact;
2576 1
        foreach (j, e; argexps)
2577
        {
2578 1
            assert(e);
2579 1
            if (e == emptyArrayElement)
2580 1
                continue;
2581

2582 1
            Type t = tt.addMod(tparams[j].mod).substWildTo(MODFlags.const_);
2583

2584 1
            MATCH m = e.implicitConvTo(t);
2585 1
            if (match > m)
2586 1
                match = m;
2587 1
            if (match <= MATCH.nomatch)
2588 1
                break;
2589
        }
2590 1
        return match;
2591
    }
2592
}
2593

2594

2595
/*************************************************
2596
 * Given function arguments, figure out which template function
2597
 * to expand, and return matching result.
2598
 * Params:
2599
 *      m           = matching result
2600
 *      dstart      = the root of overloaded function templates
2601
 *      loc         = instantiation location
2602
 *      sc          = instantiation scope
2603
 *      tiargs      = initial list of template arguments
2604
 *      tthis       = if !NULL, the 'this' pointer argument
2605
 *      fargs       = arguments to function
2606
 *      pMessage    = address to store error message, or null
2607
 */
2608
void functionResolve(ref MatchAccumulator m, Dsymbol dstart, Loc loc, Scope* sc, Objects* tiargs,
2609
    Type tthis, Expressions* fargs, const(char)** pMessage = null)
2610
{
2611 1
    Expression[] fargs_ = fargs.peekSlice();
2612
    version (none)
2613
    {
2614
        printf("functionResolve() dstart = %s\n", dstart.toChars());
2615
        printf("    tiargs:\n");
2616
        if (tiargs)
2617
        {
2618
            for (size_t i = 0; i < tiargs.dim; i++)
2619
            {
2620
                RootObject arg = (*tiargs)[i];
2621
                printf("\t%s\n", arg.toChars());
2622
            }
2623
        }
2624
        printf("    fargs:\n");
2625
        for (size_t i = 0; i < (fargs ? fargs.dim : 0); i++)
2626
        {
2627
            Expression arg = (*fargs)[i];
2628
            printf("\t%s %s\n", arg.type.toChars(), arg.toChars());
2629
            //printf("\tty = %d\n", arg.type.ty);
2630
        }
2631
        //printf("stc = %llx\n", dstart.scope.stc);
2632
        //printf("match:t/f = %d/%d\n", ta_last, m.last);
2633
    }
2634

2635
    // results
2636 1
    int property = 0;   // 0: uninitialized
2637
                        // 1: seen @property
2638
                        // 2: not @property
2639 1
    size_t ov_index = 0;
2640 1
    TemplateDeclaration td_best;
2641 1
    TemplateInstance ti_best;
2642 1
    MATCH ta_last = m.last != MATCH.nomatch ? MATCH.exact : MATCH.nomatch;
2643 1
    Type tthis_best;
2644

2645
    int applyFunction(FuncDeclaration fd)
2646
    {
2647
        // skip duplicates
2648 1
        if (fd == m.lastf)
2649 1
            return 0;
2650
        // explicitly specified tiargs never match to non template function
2651 1
        if (tiargs && tiargs.dim > 0)
2652 0
            return 0;
2653

2654
        // constructors need a valid scope in order to detect semantic errors
2655 1
        if (!fd.isCtorDeclaration &&
2656 1
            fd.semanticRun < PASS.semanticdone)
2657
        {
2658 1
            Ungag ungag = fd.ungagSpeculative();
2659 1
            fd.dsymbolSemantic(null);
2660
        }
2661 1
        if (fd.semanticRun < PASS.semanticdone)
2662
        {
2663 1
            .error(loc, "forward reference to template `%s`", fd.toChars());
2664 1
            return 1;
2665
        }
2666
        //printf("fd = %s %s, fargs = %s\n", fd.toChars(), fd.type.toChars(), fargs.toChars());
2667 1
        auto tf = cast(TypeFunction)fd.type;
2668

2669 1
        int prop = tf.isproperty ? 1 : 2;
2670 1
        if (property == 0)
2671 1
            property = prop;
2672 1
        else if (property != prop)
2673 1
            error(fd.loc, "cannot overload both property and non-property functions");
2674

2675
        /* For constructors, qualifier check will be opposite direction.
2676
         * Qualified constructor always makes qualified object, then will be checked
2677
         * that it is implicitly convertible to tthis.
2678
         */
2679 1
        Type tthis_fd = fd.needThis() ? tthis : null;
2680 1
        bool isCtorCall = tthis_fd && fd.isCtorDeclaration();
2681 1
        if (isCtorCall)
2682
        {
2683
            //printf("%s tf.mod = x%x tthis_fd.mod = x%x %d\n", tf.toChars(),
2684
            //        tf.mod, tthis_fd.mod, fd.isReturnIsolated());
2685 1
            if (MODimplicitConv(tf.mod, tthis_fd.mod) ||
2686 1
                tf.isWild() && tf.isShared() == tthis_fd.isShared() ||
2687 1
                fd.isReturnIsolated())
2688
            {
2689
                /* && tf.isShared() == tthis_fd.isShared()*/
2690
                // Uniquely constructed object can ignore shared qualifier.
2691
                // TODO: Is this appropriate?
2692 1
                tthis_fd = null;
2693
            }
2694
            else
2695 1
                return 0;   // MATCH.nomatch
2696
        }
2697
        /* Fix Issue 17970:
2698
           If a struct is declared as shared the dtor is automatically
2699
           considered to be shared, but when the struct is instantiated
2700
           the instance is no longer considered to be shared when the
2701
           function call matching is done. The fix makes it so that if a
2702
           struct declaration is shared, when the destructor is called,
2703
           the instantiated struct is also considered shared.
2704
        */
2705 1
        if (auto dt = fd.isDtorDeclaration())
2706
        {
2707 1
            auto dtmod = dt.type.toTypeFunction();
2708 1
            auto shared_dtor = dtmod.mod & MODFlags.shared_;
2709 1
            auto shared_this = tthis_fd !is null ?
2710 1
                tthis_fd.mod & MODFlags.shared_ : 0;
2711 1
            if (shared_dtor && !shared_this)
2712 1
                tthis_fd = dtmod;
2713 1
            else if (shared_this && !shared_dtor && tthis_fd !is null)
2714 1
                tf.mod = tthis_fd.mod;
2715
        }
2716 1
        MATCH mfa = tf.callMatch(tthis_fd, fargs_, 0, pMessage, sc);
2717
        //printf("test1: mfa = %d\n", mfa);
2718 1
        if (mfa > MATCH.nomatch)
2719
        {
2720 1
            if (mfa > m.last) goto LfIsBetter;
2721 1
            if (mfa < m.last) goto LlastIsBetter;
2722

2723
            /* See if one of the matches overrides the other.
2724
             */
2725 1
            assert(m.lastf);
2726 1
            if (m.lastf.overrides(fd)) goto LlastIsBetter;
2727 1
            if (fd.overrides(m.lastf)) goto LfIsBetter;
2728

2729
            /* Try to disambiguate using template-style partial ordering rules.
2730
             * In essence, if f() and g() are ambiguous, if f() can call g(),
2731
             * but g() cannot call f(), then pick f().
2732
             * This is because f() is "more specialized."
2733
             */
2734
            {
2735 1
                MATCH c1 = fd.leastAsSpecialized(m.lastf);
2736 1
                MATCH c2 = m.lastf.leastAsSpecialized(fd);
2737
                //printf("c1 = %d, c2 = %d\n", c1, c2);
2738 1
                if (c1 > c2) goto LfIsBetter;
2739 1
                if (c1 < c2) goto LlastIsBetter;
2740
            }
2741

2742
            /* The 'overrides' check above does covariant checking only
2743
             * for virtual member functions. It should do it for all functions,
2744
             * but in order to not risk breaking code we put it after
2745
             * the 'leastAsSpecialized' check.
2746
             * In the future try moving it before.
2747
             * I.e. a not-the-same-but-covariant match is preferred,
2748
             * as it is more restrictive.
2749
             */
2750 1
            if (!m.lastf.type.equals(fd.type))
2751
            {
2752
                //printf("cov: %d %d\n", m.lastf.type.covariant(fd.type), fd.type.covariant(m.lastf.type));
2753 1
                const int lastCovariant = m.lastf.type.covariant(fd.type);
2754 1
                const int firstCovariant = fd.type.covariant(m.lastf.type);
2755

2756 1
                if (lastCovariant == 1 || lastCovariant == 2)
2757
                {
2758 1
                    if (firstCovariant != 1 && firstCovariant != 2)
2759
                    {
2760 0
                        goto LlastIsBetter;
2761
                    }
2762
                }
2763 1
                else if (firstCovariant == 1 || firstCovariant == 2)
2764
                {
2765 1
                    goto LfIsBetter;
2766
                }
2767
            }
2768

2769
            /* If the two functions are the same function, like:
2770
             *    int foo(int);
2771
             *    int foo(int x) { ... }
2772
             * then pick the one with the body.
2773
             *
2774
             * If none has a body then don't care because the same
2775
             * real function would be linked to the decl (e.g from object file)
2776
             */
2777 1
            if (tf.equals(m.lastf.type) &&
2778 1
                fd.storage_class == m.lastf.storage_class &&
2779 1
                fd.parent == m.lastf.parent &&
2780 1
                fd.protection == m.lastf.protection &&
2781 1
                fd.linkage == m.lastf.linkage)
2782
            {
2783 1
                if (fd.fbody && !m.lastf.fbody)
2784 1
                    goto LfIsBetter;
2785 1
                if (!fd.fbody)
2786 1
                    goto LlastIsBetter;
2787
            }
2788

2789
            // https://issues.dlang.org/show_bug.cgi?id=14450
2790
            // Prefer exact qualified constructor for the creating object type
2791 1
            if (isCtorCall && tf.mod != m.lastf.type.mod)
2792
            {
2793 1
                if (tthis.mod == tf.mod) goto LfIsBetter;
2794 1
                if (tthis.mod == m.lastf.type.mod) goto LlastIsBetter;
2795
            }
2796

2797 1
            m.nextf = fd;
2798 1
            m.count++;
2799 1
            return 0;
2800

2801
        LlastIsBetter:
2802 1
            return 0;
2803

2804
        LfIsBetter:
2805 1
            td_best = null;
2806 1
            ti_best = null;
2807 1
            ta_last = MATCH.exact;
2808 1
            m.last = mfa;
2809 1
            m.lastf = fd;
2810 1
            tthis_best = tthis_fd;
2811 1
            ov_index = 0;
2812 1
            m.count = 1;
2813 1
            return 0;
2814
        }
2815 1
        return 0;
2816
    }
2817

2818
    int applyTemplate(TemplateDeclaration td)
2819
    {
2820
        //printf("applyTemplate()\n");
2821 1
        if (td.inuse)
2822
        {
2823 1
            td.error(loc, "recursive template expansion");
2824 1
            return 1;
2825
        }
2826 1
        if (td == td_best)   // skip duplicates
2827 1
            return 0;
2828

2829 1
        if (!sc)
2830 1
            sc = td._scope; // workaround for Type.aliasthisOf
2831

2832 1
        if (td.semanticRun == PASS.init && td._scope)
2833
        {
2834
            // Try to fix forward reference. Ungag errors while doing so.
2835 1
            Ungag ungag = td.ungagSpeculative();
2836 1
            td.dsymbolSemantic(td._scope);
2837
        }
2838 1
        if (td.semanticRun == PASS.init)
2839
        {
2840 0
            .error(loc, "forward reference to template `%s`", td.toChars());
2841
        Lerror:
2842 1
            m.lastf = null;
2843 1
            m.count = 0;
2844 1
            m.last = MATCH.nomatch;
2845 1
            return 1;
2846
        }
2847
        //printf("td = %s\n", td.toChars());
2848

2849 1
        auto f = td.onemember ? td.onemember.isFuncDeclaration() : null;
2850 1
        if (!f)
2851
        {
2852 1
            if (!tiargs)
2853 1
                tiargs = new Objects();
2854 1
            auto ti = Pool!TemplateInstance.make(loc, td, tiargs);
2855 1
            Objects dedtypes = Objects(td.parameters.dim);
2856 1
            assert(td.semanticRun != PASS.init);
2857 1
            MATCH mta = td.matchWithInstance(sc, ti, &dedtypes, fargs, 0);
2858
            //printf("matchWithInstance = %d\n", mta);
2859 1
            if (mta <= MATCH.nomatch || mta < ta_last)   // no match or less match
2860
            {
2861 1
                Pool!TemplateInstance.dispose(ti);
2862 1
                return 0;
2863
            }
2864

2865 1
            ti.templateInstanceSemantic(sc, fargs);
2866 1
            if (!ti.inst)               // if template failed to expand
2867
            {
2868 0
                Pool!TemplateInstance.dispose(ti);
2869 0
                return 0;
2870
            }
2871

2872 1
            Dsymbol s = ti.inst.toAlias();
2873 1
            FuncDeclaration fd;
2874 1
            if (auto tdx = s.isTemplateDeclaration())
2875
            {
2876 1
                Objects dedtypesX;      // empty tiargs
2877

2878
                // https://issues.dlang.org/show_bug.cgi?id=11553
2879
                // Check for recursive instantiation of tdx.
2880 1
                for (TemplatePrevious* p = tdx.previous; p; p = p.prev)
2881
                {
2882 1
                    if (arrayObjectMatch(p.dedargs, &dedtypesX))
2883
                    {
2884
                        //printf("recursive, no match p.sc=%p %p %s\n", p.sc, this, this.toChars());
2885
                        /* It must be a subscope of p.sc, other scope chains are not recursive
2886
                         * instantiations.
2887
                         */
2888 1
                        for (Scope* scx = sc; scx; scx = scx.enclosing)
2889
                        {
2890 1
                            if (scx == p.sc)
2891
                            {
2892 1
                                error(loc, "recursive template expansion while looking for `%s.%s`", ti.toChars(), tdx.toChars());
2893 1
                                Pool!TemplateInstance.dispose(ti);
2894 1
                                goto Lerror;
2895
                            }
2896
                        }
2897
                    }
2898
                    /* BUG: should also check for ref param differences
2899
                     */
2900
                }
2901

2902 1
                TemplatePrevious pr;
2903 1
                pr.prev = tdx.previous;
2904 1
                pr.sc = sc;
2905 1
                pr.dedargs = &dedtypesX;
2906 1
                tdx.previous = &pr;             // add this to threaded list
2907

2908 1
                fd = resolveFuncCall(loc, sc, s, null, tthis, fargs, FuncResolveFlag.quiet);
2909

2910 1
                tdx.previous = pr.prev;         // unlink from threaded list
2911
            }
2912 1
            else if (s.isFuncDeclaration())
2913
            {
2914 1
                fd = resolveFuncCall(loc, sc, s, null, tthis, fargs, FuncResolveFlag.quiet);
2915
            }
2916
            else
2917 1
                goto Lerror;
2918

2919 1
            if (!fd)
2920 1
                return 0;
2921

2922 1
            if (fd.type.ty != Tfunction)
2923
            {
2924 0
                m.lastf = fd;   // to propagate "error match"
2925 0
                m.count = 1;
2926 0
                m.last = MATCH.nomatch;
2927 0
                Pool!TemplateInstance.dispose(ti);
2928 0
                return 1;
2929
            }
2930

2931 1
            Type tthis_fd = fd.needThis() && !fd.isCtorDeclaration() ? tthis : null;
2932

2933 1
            auto tf = cast(TypeFunction)fd.type;
2934 1
            MATCH mfa = tf.callMatch(tthis_fd, fargs_, 0, null