User:9rnsr/DIP: Template Parameter Constraint

Title:	Template Parameter Constraint
DIP:	xx
Version:	1
Status:	Draft
Created:	2015-09-11
Last Modified:	2015-09-11
Author:	Kenji Hara
Links:

Abstract

A new feature proposal to constraint template parameter deduction. It supports interaction with IFTI. It's a solution for the Phobos regression issue: https://issues.dlang.org/show_bug.cgi?id=15027#c1

In a nutshell

template Foo(      T if isInputRange) { ... }
template Foo(  int v if GreaterThan!2) { ... }
template Foo(alias s if isPropertyFunction) { ... }
template Foo(      A... if SetOf!(int, long)) { ... }

// instantiation suceeds when:
alias F1 = Foo!R;				// isInputRange!R returns true
alias F2 = Foo!10;				// GreaterThan!2.GreaterThan!10 returns true
alias F3 = Foo!func;			// isPropertyFunction!func returns true
alias F4 = Foo!(long, int);		// when SetOf!(int, long).SetOf!(long, int) returns true

alias InputRange = std.range.primitives.isInputRange;

// Prefix style constraint is a syntactic sugar
auto foo(InputRange R)(R range);
auto foo(SetOf!(int, long) A...)(A args) { ... }

Description

Each template parameters can have a constraint to limit deduced template arguments.

For the template parameter constraint, compiler requires a template which takes one template parameter and its instantiation should return a compile time boolean value.

When a template parameter Param with constraint template Constraint matches a template argument Arg, compiler tries to instantiate Constraint!Arg, and Param will succeed to be deduced with Arg iff it's evaluated to true.

template Foo(Param if Constraint) { ... }
alias F = Foo!Arg;
// if Constraint!Arg returns true, the Param will be deduced to Arg.
// If Constraint doesn't match to Arg, or Constraint!Arg returns false, Param will fail to deduction,

If any errors happen during the Constraint!Arg instantiation, those are not gagged.

For TemplateValueParameter, TemplateAliasParameter, and TemplateTupleParameter, same constraint evaluation happens in parameter deduction.

In IFTI, the constraint works very well. For example:

void popFront(T)(ref T[] a) { a = a[1..$]; }
enum bool isInputRange(R) = is(typeof( R r; r.popFront(); }

struct DirEntry { @property string name(); alias name this; }
pragma(msg, isInputRange!DirEntry); // prints 'false'
pragma(msg, isInputRange!(typeof(DirEntry.init.name))); // prints 'true'

bool isDir(R if isInputRange)(R r) { return true; }

void test() {
    DirEntry de;
    isDir(de);     // line [A]
}

At line [A], first compiler tries to deduce R with the typeof(de) == DirEntry. But the constraint is evaluated to false. Next, the function argument will be converted to de.name considering 'alias this', and R is tried to deduce with typeof(de.name) == string. In the second time, the constraint is evaluated to true, then R is deduced to string. Finally, isDir!string is instantiated and called successfully.

Syntactic sugar

In TemplateTypeParameter, constraint can be placed at the ahead of parameter identifier.

template Foo(isInputRange R) {}

It's completely same with:

template Foo(R if isInputRange) {}

The syntax is reusing the current grammar for TemplateValueParamter. In parsing stage:

template Foo(InputRange R) {}  // 'InputRange' is an identifier
tempalte Foo(string     s) {}  // 'string' is an identifier
// both are parsed as valueType of TemplateValueParamter

In semantic analysis stage, the prefix Type can be determined whether it's a type or not. If it's really a type, the template parameter will become TemplateValueParamter. If it's a non-type symbol (e.g. template), it will become constrainted TemplateTypeParamter.

Similar to that, TemplateTupleParameter can have prefix style constraint.

template Foo(A...) {}
template Foo(TypeNamePair A...) {}

Fixed Grammar

TemplateParameter:
    TemplateTypeOrValueParameter
    TemplateAliasParameter
    TemplateTupleParameter
    TemplateThisParameter

TemplateParameterConstraint:
    if Type

TemplateTypeOrValueParameter:
    BasicType Declarator
    TemplateTypeParameter
    TemplateValueParameter

TemplateTypeParameter:
    Identifier TemplateParameterConstraint_opt
    Identifier TemplateParameterConstraint_opt TemplateTypeParameterSpecialization
    Identifier TemplateParameterConstraint_opt TemplateTypeParameterDefault
    Identifier TemplateParameterConstraint_opt TemplateTypeParameterSpecialization TemplateTypeParameterDefault

TemplateValueParameter:
    BasicType Declarator TemplateParameterConstraint
    BasicType Declarator TemplateParameterConstraint_opt TemplateValueParameterSpecialization
    BasicType Declarator TemplateParameterConstraint_opt TemplateValueParameterDefault
    BasicType Declarator TemplateParameterConstraint_opt TemplateValueParameterSpecialization TemplateValueParameterDefault

TemplateAliasParameter:
    alias Identifier TemplateParameterConstraint_opt TemplateAliasParameterSpecialization_opt TemplateAliasParameterDefault_opt
    alias BasicType Declarator TemplateParameterConstraint_opt TemplateAliasParameterSpecialization_opt TemplateAliasParameterDefault_opt

TemplateTupleParameter:
    Identifier ... TemplateParameterConstraint_opt
    BasicType Declarator Identifier ...

Usage

Define a descriptive name template for the complex constraint and use it.

// in std/file.d
enum bool InputRangeOfChars(R) = isInputRange!R && isChars!(ElementType!R);

void[] read  (InputRangeOfChars R)(R name, size_t upTo = size_t.max) { ... }
void   write (InputRangeOfChars R)(R name, const void[] buffer) { ... }
void   append(InputRangeOfChars R)(R name, const void[] buffer) { ... }
...

Define a template for parameterized constraint and use it.

template InstanceOf(Template) {
    enum bool InstanceOf(T) = is(T : Template!Args, ...);
}

class C(T) {}
alias C1 = C!int;
alias C2 = C!string;
template Foo(T if InstanceOf!C) {}
// the parameter constraint is `enum bool InstanceOf(T)`

More concept-specific Range definitions.

enum bool InputRange(R) = is(typeof({ ...; }));
enum bool ForwardRange(InputRange R) = is(typeof({ ...; }));
enum bool BidirectionalRange(ForwardRange R) = is(typeof({ ...; }));
enum bool RandomAccessRange(BidirectionalRange R) = is(typeof({ ...; }));

Benefits

• Fix issue 15027

• A small descriptive template signature and documentation

Compare:

auto foo(R)(R range) if (isInputRange!R);

With:

auto foo(isInputRange R)(R range);

The constraints can be nearby the corresponding template parameters.

• More understandable compiler error messages

Each template parameter constraints is bounded to the temlate parameter identifier. Threfore when a parameter constraint is not satisfied, compiler can recognize it and can reproduce descriptive error message for the code:

void foo(Constraint T)(T v) {}
void test() { foo(1); }

like:

Error: template 'foo' cannot deduce function from argument types !()(int)
       constraint 'Constraint' is not satisfied

Design decisions in this DIP

• Q. Each template parameters has specialization part. Why not reuse the existing syntax?
• A. Because it happens conflict with TemplateAliasParameter.

Currently a template alias parameter can accept both symbols and values.

template Foo(alias a) {}
alias F1 = Foo!func;    // ok
alias F2 = Foo!true;    // also ok

So, if a template symbol is at the specialization part it would be ambiguous.

template Foo(alias a : isInputRange) {}    // problematic

// : isInputRange could work as a constraint
alias F1 = Foo!(int[]);

// isInputRange template matches to a with the specialization `: isInputRange`,
// or fail to satisfy constraint evaluation `isInputRange!isInputRange` ?
alias F2 = Foo!(isInputRange)

• Q. Why not consistently support prefix style constraint for all kinds of template parameters?
• A. Because it would add a grammar ambiguity to TemplateValueParameter and TemplateValueParameter.

If we add support for the prefix style parameter constraint to TemplateValueParameter, it would become:

template Foo(Constraing valueType ident)

However, the syntax will cause ambiguity with module scope operator.

moduel test;
alias someType = int;
template Foo(isInputRange .someType ident) {}

Same problem happens in TemplateAliasParameter and its specType part.

• Q. Why not use explicit instantiation syntax for the constraint like R if isInputRange!R?
• A. Because it's redundant.

By definition, a template parameter constraint should be "unary predicate". Therefore such the explicit specification for the only one argument for the predicate is merely redundant.

template Foo(R if isInputRange!R) {}      // R ... R
template Foo(InputRange!R R) {}           // R R

And, current D syntax does not accept a chain of instantiations like Template!Arg1!Arg2. Therefore, it would make the use of parameterized constraints more difficult.

template isSameWith(U) { enum bool isSameWith(T) = is(T == U); }
template Foo(T if isSameWith!int!T) {}    // invalid syntax

template isSame(U) { enum bool With(T) = is(T == U); }
template Foo(T if isSame!int.With!T) {}   // an alternation

Note

This is inspired by C++1y Concepts Lite.

Copyright

This document has been placed in the Public Domain.