| Field | Value |
|---|---|
| DIP: | 1023 |
| Review Count: | 1 |
| Author: | Stefanos Baziotis (sdi1600105@di.uoa.gr) |
| Implementation: | dlang/dmd#9778 (Prototype) |
| Status: | Postponed |
D has type aliases that can be templates:
struct TemplateType(T) { }
alias TemplateAlias(T) = TemplateType!T;D also has template functions for which the template parameters are resolved when the template is instantiatied:
struct TemplateType(T) { }
void templateFunction(T)(TemplateType!T arg) { }
TemplateType!int inst;
templateFunction(inst); /* template instantiated with T = int */Combining template aliases and template functions, it should be possible to have template aliases as formal parameter types of template functions:
struct TemplateType(T) { }
alias TemplateAlias(T) = TemplateType!T;
void templateFunction(T)(TemplateAlias!T arg) { }However, the compiler produces an error when trying to use IFTI to call a template function that has a template alias type instance as a formal function parameter. This is not a bug because the desired behaviour is not specified. As such, existing reports of the issue are tagged as 'Enhancements'.
This DIP proposes a specification for template aliases as formal function parameters.
It is quite common for a series of (one or more) nested template instantiations to be considered as one semantic entity, especially for data science libraries. Consider the following D template function:
auto foo(T)(Slice!(StairsIterator!(T*, "-")) m)
{
}The following example demonstrates a possible real-world example using the Mir library :
alias PackedUpperTriangularMatrix(T) = Slice!(StairsIterator!(T*, "-"));
// IFTI will fail, issue 16486
auto foo(T)(PackedUpperTriangularMatrix!T m) { }Packing the RHS instances in an alias is not only a way to reduce code size but, most importantly,
it removes the burden from the user to know what a PackedUpperTriangularMatrix actually is. Right now,
the user is exposed to unnecessary details, leading to code that is not as easy to comprehend.
Consider that currently, similar functionality can be implemented as:
enum isPackedUpperTriangularMatrix(T) = is(T: Slice!(StairsIterator!(U*, "-")), U);
auto foo(T)(T m) if(isPackedUpperTriangularMatrix!T) { /* ... */ }The thesis is that in real-world situations, this alternative produces quite more unreadable code. It is has been discussed more extensively on the comments of the pull request
Current behavior: A template alias function parameter is not resolved to its aliased instance until after the function resolution stage. So with the following code:
struct TemplateType(T) {}
template aliasAlias(T) = TemplateType!T;
void templateFunction(T)(TemplateAlias!T arg) {}
void main()
{
TemplateAlias!int inst;
templateFunction(inst); /* "cannot deduce function from argument types !()(TemplateType!int)" */
}We get the following error message:
template templateFunction cannot deduce function from argument types !()(TemplateType!int), candidates are:
templateFunction(T)(TemplateAlias!T arg)
The compiler sees TemplateAlias and TemplateType as two different types, so it can't match TemplateType!int against
TemplateAlias!T. Although the compiler has resolved the type of inst to TemplateType!int, it has not resolved the
formal parameter type to be TemplateType!T.
New behavior: Full handling of the feature is complicated because a template (alias) has arbitrary pattern matching and rewrite abilities over types. For instance, a template alias:
- can accept type parameters that it never uses (e.g.,
alias TemplateAlias(T) = int;) - can accept a type parameter and use it multiple times (e.g.,
alias TemplateAlias(T) = TemplateType!(T,T);) - can infer a type parameter when given a complex type expression (e.g.,
alias TemplateAlias(A: A*, B) = TemplateType!(A, B);).
Therefore, the crux of the proposal is to encode this pattern matching and type rewriting into a function, Gen, and invoke it at the right time during compilation. It is not to define that pattern-matching or the type-rewriting.
Specifically, if the type of the formal parameter of a template function is an instance of a template alias declaration, instantiate the type that the declaration aliases; that becomes the new type of the parameter. This is done by calling the function below in each parameter. This should be done before function calls are resolved. In pseudocode:
resolveAlias(ref parameterType) {
while (parameterType is templateInstance) {
for (arg in parameterType.paramMap.values) {
if (arg is templateInstance && arg.TD is templateAliasDeclaration) {
// Recursively resolve nested aliases
resolveAlias(arg);
}
}
// Assume that parameterType was generated using `Gen`
if (parameterType.TD is templateAliasDeclaration) {
aliasedType = TD.aliasedType;
if (aliasedType is templateInstance) {
newTD = aliasedType.TD;
newArgumentList = matchParams(aliasedType.argumentList, parameterType.paramMap);
parameterType = Gen(newTD, newArgumentList);
continue;
} else {
parameterType = aliasedType;
}
}
break;
}
}For the following discussion, the recursive nature of the procedure (i.e., the nexted for) is ignored.
Gen is a function that takes 2 arguments, TD and the list T1, ..., Tn.
TD is a template declaration.
T1, ..., T2 are arguments (actual parameters) provided to a template declaration.
The expression Gen(TD, (T1, ..., Tn) generates an instance of the declaration TD when T1, ..., Tn are provided
as arguments. The generated instance also fills:
.paramMap, which maps each formal parameter to the corresponding argument..TD, which is the template declaration used.
A template argument can be:
- A type declarator referencing known types like
int,int*,int[long]etc. - A type declarator using a template declaration formal parameter like
T,T*, etc. - A type declarator using both known types and formal parameters, like
T[int].
For 2. to be true, the instantiation should happen inside a template declaration. In this case, the formal parameters that are used by any argument must be a subset of the formal parameters of the declaration.
Additional notes:
- The number of arguments must be the same with the number of formal parameters of the template declaration.
- The argument list may contain duplicate elements.
- The generation should take into consideration the pattern-matching capabilities of the language in template parameters. Examples:
Gen(struct TemplateType(T) { }, (int*)) -> TemplateType!(int*)
Gen(struct TemplateType(T) { }, (T[int])) -> TemplateType!(T[int])
Gen(alias TemplateAlias(T) = TemplateType!T, (int*)) -> TemplateAlias!(int*)
Gen(alias TemplateAlias(T, Q) = TestType!T, (int*)) -> TemplateAlias!(int*)
We assume that all instances have been generated using Gen.
If TD is a template alias declaration, then TD.aliasedType is the type that TD aliases.
Example:
struct TemplateType(T) { }
alias TemplateAlias(T) = TemplateType!T.aliasedType of alias TemplateAlias(T) is TemplateType!T.
If that type is an instantiation of a template declaration, we find that declaration using findTempDecl().
Notice that if aliasedType isn't a template instance, we stop. This is important, because there are other reasons that
we want to stop that have to do with the implementation. (More on that in the article referenced below.)
matchParams() is a function that takes 2 arguments: one argument list (call it al) and one parameter map (call
it m, a map of formal parameters to arguments / type declarators). al is of course a list of template arguments.
It generates a new argument list so any formal parameter used in some argument in al is replaced
with the argument that it maps to (using the m).
A sample loop execution:
// Declarations
struct TemplateType(W) { }
alias TemplateAlias(Q, S) = TemplateType!Q;
parameterType := TemplateAlias!(int*, float)
// Gen looks like this: Gen(alias TemplateAlias(Q, S) = TemplateType!Q, (int*, float)) -> TemplateAlias!(int*, float)
TD := alias TemplateAlias(Q, S) = TemplateType!Q
(T1, ..., Tn) := (int*, float) (where T1 := int* and T2 := float)
parameterType := TemplateAlias!(int*, float)
parameterType.paramMap := { Q: int*, S: float }
TD.aliasedType := TemplateType!Q
newTD := struct TemplateType(W) { }
aliasedType.paramList := (Q)
newArgumentList = (int*) // 'Q' was replaced by int* using the map
parameterType = TemplateType!(int*)The last thing to be explained is the for at the start of the function. Consider the following example:
struct TemplateType1(T) { }
struct TemplateType2(Q) { }
alias TemplateAlias1(S) = TemplateType2!S
alias TemplateAlias2(V) = TemplateType1!(TemplateAlias1!V)It is clear that the procedure of resolving an alias instance has a recursive nature. That is because
aliases can instantiate other aliases. So thr for, for each argument on the map of arguments that the parameterType instance
received, first resolves any nested aliases.
Consider this example:
struct TemplateType(W) {}
alias TemplateAlias(S, V) = TemplateType!(S);
void templateFunction(T, Q)(TemplateAlias!(T, Q) arg) {}Using the above logic, the parameter resolves to this:
void templateFunction(T, Q)(TemplateType!T arg) {}Notice that this does not compile. The reason is that Q is never used. It was dropped in the process
of resolving the alias. For the specification to be complete, we need to consider that, if in the resolution
process a formal parameter of the function is dropped, then the type of the function has to change in more ways than
the function parameters. Its template parameters should also be reduced.
Templates in D are Turing-complete. Because of this, deciding a-priori if a template instantiation will ever finish retreats to the halting problem. For this reason, the DIP proposes the implementation for alias resolution detect cycles on the declaration level. That is, if an attempt is made to instantiate the same declaration again during an alias resolution, stop.
There are no breaking changes or deprecations and no problem with backwards compatibility. This is a pure addition to the language.
Copyright (c) 2019 by the D Language Foundation
Licensed under Creative Commons Zero 1.0
The primary discussion in this review centered on a remark by the DIP author that drew a distinction between shorthand and longhand alias template syntax. The DIP currently is restricted to shorthand syntax. The DIP author decided the DIP must be revised to account for all possible forms of alias declaration.
Three months after Community Review Round 1, the DIP author requested the DIP be postponed.