www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - #dbugfix Issue 16486 200$

reply 9il <ilyayaroshenko gmail.com> writes:
Hello,

Bugfix for the Issue 16486 [1] (originally [2]) is required for 
mir-algorithm types [3], [4].

For example, packed triangular matrix can be represented as

Slice!(Contiguous, [1], StairsIterator!(T*))
Slice!(Contiguous, [1], 
RetroIterator!(MapIterator!(StairsIterator!(RetroIterator!(T*)), 
retro)))

They are used in mir-lapack [5]. The bug fix also required for 
mir (Sparse, CompressedTensor), and for the future Dlang image 
library.

Workarounds aren't interesting.

200$  - bounty ( I can pay directly or transfer money to the 
Dlang Foundation )

Best Regards,
Ilya Yaroshenko

[1] https://issues.dlang.org/show_bug.cgi?id=16486
[2] https://issues.dlang.org/show_bug.cgi?id=16465
[3] 
http://docs.algorithm.dlang.io/latest/mir_ndslice_slice.html#Slice
[4] http://docs.algorithm.dlang.io/latest/mir_series.html#Series
[5] 
https://github.com/libmir/mir-lapack/blob/master/source/mir/lapack.d
Mar 29 2018
next sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 Hello,

 Bugfix for the Issue 16486 [1] (originally [2]) is required for 
 mir-algorithm types [3], [4].

 For example, packed triangular matrix can be represented as

 Slice!(Contiguous, [1], StairsIterator!(T*))
 Slice!(Contiguous, [1], 
 RetroIterator!(MapIterator!(StairsIterator!(RetroIterator!(T*)), retro)))

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.

 Workarounds aren't interesting.

 200$  - bounty ( I can pay directly or transfer money to the 
 Dlang Foundation )

 Best Regards,
 Ilya Yaroshenko

 [1] https://issues.dlang.org/show_bug.cgi?id=16486
 [2] https://issues.dlang.org/show_bug.cgi?id=16465
 [3] 
 http://docs.algorithm.dlang.io/latest/mir_ndslice_slice.html#Slice
 [4] http://docs.algorithm.dlang.io/latest/mir_series.html#Series
 [5] 
 https://github.com/libmir/mir-lapack/blob/master/source/mir/lapack.d


Given the recent blog post on std.variant, it occurs to me that 
this enhancement would also make writing functions that take 
Option types much easier. I'm adopting some of the code from the 
blog post below:

import std.variant;

alias Null = typeof(null); //for convenience
alias Option(T) = Algebraic!(T, Null);

Option!size_t indexOf(int[] haystack, int needle) {
     foreach (size_t i, int n; haystack)
         if (n == needle)
             return Option!size_t(i);
     return Option!size_t(null);
}

auto foo(T)(VariantN!(T.sizeof, T, typeof(null)) x)
{
     return x;
}

auto bar(T : Option!U, U)(T x)
{
     return x;
}

auto baz(T)(Option!T x)
{
     return x;
}

void main()
{
     import std.stdio : writeln;

     int[] a = [4, 2, 210, 42, 7];
     Option!size_t index = a.indexOf(42);

     writeln(index.foo!size_t); //works
     //writeln(index.foo); //doesn't work
     //writeln(index.bar); //doesn't work
     //writeln(index.baz); //doesn't work
}
Mar 30 2018
prev sibling next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [1] https://issues.dlang.org/show_bug.cgi?id=16486



Ah that is an interesting bug which further demonstrates that 
templates are a tricky thing :)
Basically you cannot _generally_ proof that one template just 
forwards to another.
Therefore you have to create separate types.
And since you create separate types the alias is not an alias but 
a separate template.
Solving this may be possible for special cases but in the general 
case is infeasible.
Mar 30 2018
next sibling parent reply jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 13:56:45 UTC, Stefan Koch wrote:

 On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [1] https://issues.dlang.org/show_bug.cgi?id=16486



 Ah that is an interesting bug which further demonstrates that 
 templates are a tricky thing :)
 Basically you cannot _generally_ proof that one template just 
 forwards to another.
 Therefore you have to create separate types.
 And since you create separate types the alias is not an alias 
 but a separate template.
 Solving this may be possible for special cases but in the 
 general case is infeasible.


What about something like this (using the reduced example from 
the bug report):

import std.traits : TemplateOf;

struct TestType(T) {}
alias TestAlias(T) = TestType!T;

template testFunction(T, alias U = TemplateOf!(TestAlias!T))
{
     void testFunction(U!T arg) {}
}

void main()
{
     TestAlias!int testObj;
     testFunction(testObj);
}
Mar 30 2018
parent reply jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 15:21:26 UTC, jmh530 wrote:

 [snip]


Doesn't extend to multiple template parameters that well...

import std.traits : TemplateOf;

struct TestType(T, U) {}
alias TestAlias(T) = TestType!(T, int);

template testFunction(T, alias U = TemplateOf!(TestAlias!T))
{
     void testFunction(U!(T, int) arg) {} //don't want to have to 
put the int here
}

void main()
{
     TestAlias!int testObj;
     testFunction(testObj);
}
Mar 30 2018
next sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 15:49:30 UTC, jmh530 wrote:

 On Friday, 30 March 2018 at 15:21:26 UTC, jmh530 wrote:

 [snip]


 Doesn't extend to multiple template parameters that well...
 [snip]


This works, but ugly...

template testFunction(T, U = TestAlias!T, alias V = 
TemplateOf!(U), W = TemplateArgsOf!U[1])
{
     void testFunction(V!(T, W) arg) {}
}
Mar 30 2018
prev sibling parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Friday, 30 March 2018 at 15:49:30 UTC, jmh530 wrote:

 On Friday, 30 March 2018 at 15:21:26 UTC, jmh530 wrote:

 [snip]


 Doesn't extend to multiple template parameters that well...

 import std.traits : TemplateOf;

 struct TestType(T, U) {}
 alias TestAlias(T) = TestType!(T, int);

 template testFunction(T, alias U = TemplateOf!(TestAlias!T))


What you're showing here is a somewhat different case. First, 
you're telling TestAlias to turn into a TestType. Then you ask 
which template that type is an instance of. That's going to be 
TestType, every single time. And it being anything else would be 
a source of great confusion:

     auto a = TestType!(string, int)();
     auto b = TestAlias!string();

     // We expect this to be true:
     assert(is(typeof(a) == typeof(b)));

     // And I'll be damned if this ain't:
     assert(__traits(isSame, TemplateOf!(typeof(a)), 
TemplateOf!(typeof(b))));

--
   Simen
Mar 31 2018
prev sibling next sibling parent reply 9il <ilyayaroshenko gmail.com> writes:
On Friday, 30 March 2018 at 13:56:45 UTC, Stefan Koch wrote:

 On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [1] https://issues.dlang.org/show_bug.cgi?id=16486



 Solving this may be possible for special cases but in the 
 general case is infeasible.


Can the case where the name of original template in scope of the 
alias template refers to an unique template template be 
implemented? It should be good enough for Mir and Phobos.

// There are unique defs for OriginalTemplate and ParamsMap
import lala : OriginalTemplate, ParamsMap;
alias AliasTemplate(SomeParams...) = 
OriginalTemplate!(ParamsMap!SomeParams);
Mar 30 2018
parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Friday, 30 March 2018 at 17:10:22 UTC, 9il wrote:

 On Friday, 30 March 2018 at 13:56:45 UTC, Stefan Koch wrote:

 On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [1] https://issues.dlang.org/show_bug.cgi?id=16486



 Solving this may be possible for special cases but in the 
 general case is infeasible.


 Can the case where the name of original template in scope of 
 the alias template refers to an unique template template be 
 implemented? It should be good enough for Mir and Phobos.

 // There are unique defs for OriginalTemplate and ParamsMap
 import lala : OriginalTemplate, ParamsMap;
 alias AliasTemplate(SomeParams...) = 
 OriginalTemplate!(ParamsMap!SomeParams);


Depends greatly on what ParamsMap does. Probably the simplest 
counterexample:

     alias ParamsMap(T...) = int;

So I have this instance of OriginalTemplate!int - did it come 
from an AliasTemplate!int? Maybe it was AliasTemplate!string, or 
AliasTemplate!(1,2,3,MyClass) - there's just no way to know.


Of course, that's an extreme example, but the fundamental 
requirement is that ParamsMap needs to be injective - each 
possible output would need to map to exactly one input. Also, 
this mapping must be possible to reverse-engineer.

If we are to support this, a DIP must be written to explain the 
algorithm to reverse the mapping. This is absolutely possible for 
a subset of cases, and would be a benefit in those cases. Of 
course we also run the risk of creating more confusing corner 
cases, and an influx of questions in D.learn of people asking 
'why does X work, but not Y?'.

--
   Simen
Mar 31 2018
prev sibling parent reply Kagamin <spam here.lot> writes:
On Friday, 30 March 2018 at 13:56:45 UTC, Stefan Koch wrote:

 Ah that is an interesting bug which further demonstrates that 
 templates are a tricky thing :)
 Basically you cannot _generally_ proof that one template just 
 forwards to another.
 Therefore you have to create separate types.
 And since you create separate types the alias is not an alias 
 but a separate template.
 Solving this may be possible for special cases but in the 
 general case is infeasible.


If a template is used as a type it should be resolved to a type, 
no? And template resolves to a type in a straightforward way. 
Where does it fail? Judging by the error message "cannot deduce 
function from argument types !()(TestType!int)" it does 
successfully resolve alias to a type.
Mar 31 2018
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Saturday, 31 March 2018 at 13:34:18 UTC, Kagamin wrote:

 On Friday, 30 March 2018 at 13:56:45 UTC, Stefan Koch wrote:

 Ah that is an interesting bug which further demonstrates that 
 templates are a tricky thing :)
 Basically you cannot _generally_ proof that one template just 
 forwards to another.
 Therefore you have to create separate types.
 And since you create separate types the alias is not an alias 
 but a separate template.
 Solving this may be possible for special cases but in the 
 general case is infeasible.


 If a template is used as a type it should be resolved to a 
 type, no? And template resolves to a type in a straightforward 
 way. Where does it fail? Judging by the error message "cannot 
 deduce function from argument types !()(TestType!int)" it does 
 successfully resolve alias to a type.


You're starting in the wrong end - the type cannot yet be 
considered, since the compiler doesn't know the correct arguments 
to TestAlias. Given this code:

struct S(T...) {}
alias SS(T...) = S!(T, int);

void foo(T)(SS!T arg) {}

unittest {
     foo(SS!string());
}

The error message is "template foo cannot deduce function from 
argument types !()(S!(string, int)), candidates are: foo(T)(SS!T 
arg)".

What the compiler needs to do is figure out what T needs to be in 
order for SS to return the type S!(int, int). SS hasn't resolved 
to a type yet at that point, because the compiler has no idea 
which arguments to give it.

These are the steps the compiler does when it evaluates a 
function call (simplified):

1) Figure out the overload set.
2) Weed out non-matching overloads.
3) Check that exactly one overload matches*.
4) Use that overload.

In step 2, the compiler looks at the types when the overload is a 
regular function. When it's a function template, it doesn't know 
the types yet, and IFTI tries to figure it out by a sort of 
pattern matching. In the case above, it doesn't find a 
S!(/*something*/) anywhere, and gives up.

If the compiler were to do something other than give up, we would 
need some algorithm to define what it should try, and in which 
order. As human beings, with impressive collections of 
pattern-matching circuits, we can easily see that it should try 
putting the first template argument into T. Getting to that 
conclusion is a lot harder for the poor, stupid compiler.

--
   Simen


*In the case where multiple overloads are a match, the best fit 
is chosen. If there's more than one best fit, or there's no 
match, you get a compile error.
Mar 31 2018
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 31.03.2018 18:34, Simen Kjærås wrote:

 On Saturday, 31 March 2018 at 13:34:18 UTC, Kagamin wrote:

 On Friday, 30 March 2018 at 13:56:45 UTC, Stefan Koch wrote:

 Ah that is an interesting bug which further demonstrates that 
 templates are a tricky thing :)
 Basically you cannot _generally_ proof that one template just 
 forwards to another.
 Therefore you have to create separate types.
 And since you create separate types the alias is not an alias but a 
 separate template.
 Solving this may be possible for special cases but in the general 
 case is infeasible.


 If a template is used as a type it should be resolved to a type, no? 
 And template resolves to a type in a straightforward way. Where does 
 it fail? Judging by the error message "cannot deduce function from 
 argument types !()(TestType!int)" it does successfully resolve alias 
 to a type.


 
 You're starting in the wrong end - the type cannot yet be considered, 
 since the compiler doesn't know the correct arguments to TestAlias. 
 Given this code:
 
 struct S(T...) {}
 alias SS(T...) = S!(T, int);
 
 void foo(T)(SS!T arg) {}
 
 unittest {
      foo(SS!string());
 }
 
 The error message is "template foo cannot deduce function from argument 
 types !()(S!(string, int)), candidates are: foo(T)(SS!T arg)".
 ...
 
 If the compiler were to do something other than give up, we would need 
 some algorithm to define what it should try, and in which order.


It should simply run a limited semantic analysis on the function 
parameters before matching.

void foo(T)(SS!T arg) -> void foo(T)(S!(T, int) arg)

To support Ilya's use case, it suffices to expand unconstrained alias 
templates.
Mar 31 2018
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 30.03.2018 08:11, 9il wrote:

 Hello,
 
 Bugfix for the Issue 16486 [1] (originally [2]) is required for 
 mir-algorithm types [3], [4].
 
 For example, packed triangular matrix can be represented as
 
 Slice!(Contiguous, [1], StairsIterator!(T*))
 Slice!(Contiguous, [1], 
 RetroIterator!(MapIterator!(StairsIterator!(RetroIterator!(T*)), retro)))
 
 They are used in mir-lapack [5]. The bug fix also required for mir 
 (Sparse, CompressedTensor), and for the future Dlang image library.
 
 Workarounds aren't interesting.
 
 200$  - bounty ( I can pay directly or transfer money to the Dlang 
 Foundation )
 
 Best Regards,
 Ilya Yaroshenko
 
 [1] https://issues.dlang.org/show_bug.cgi?id=16486
 [2] https://issues.dlang.org/show_bug.cgi?id=16465
 [3] http://docs.algorithm.dlang.io/latest/mir_ndslice_slice.html#Slice
 [4] http://docs.algorithm.dlang.io/latest/mir_series.html#Series
 [5] https://github.com/libmir/mir-lapack/blob/master/source/mir/lapack.d


This is supported in https://github.com/tgehr/d-compiler
It has explicit "unknown" types and may instantiate templates using them 
during IFTI. The result is then matched against the argument types.
Mar 30 2018
prev sibling next sibling parent Rubn <where is.this> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 Hello,

 Bugfix for the Issue 16486 [1] (originally [2]) is required for 
 mir-algorithm types [3], [4].

 For example, packed triangular matrix can be represented as

 Slice!(Contiguous, [1], StairsIterator!(T*))
 Slice!(Contiguous, [1], 
 RetroIterator!(MapIterator!(StairsIterator!(RetroIterator!(T*)), retro)))

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.

 Workarounds aren't interesting.

 200$  - bounty ( I can pay directly or transfer money to the 
 Dlang Foundation )

 Best Regards,
 Ilya Yaroshenko

 [1] https://issues.dlang.org/show_bug.cgi?id=16486
 [2] https://issues.dlang.org/show_bug.cgi?id=16465
 [3] 
 http://docs.algorithm.dlang.io/latest/mir_ndslice_slice.html#Slice
 [4] http://docs.algorithm.dlang.io/latest/mir_series.html#Series
 [5] 
 https://github.com/libmir/mir-lapack/blob/master/source/mir/lapack.d


It's a feature request, according to the comments. So before 
anyone goes wasting their time implementing this. Someone might 
want to write the DIP for it.
Mar 30 2018
prev sibling next sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [snip]

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.


I was experimenting with one of the open methods matrix examples 
[1] and trying to replace the virtual methods with templates. My 
example [3] does it statically and with structs so that it could 
be used with mir. However, the moment you try to make it a little 
bit more complicated and allow the type of the underlying matrix 
data to be templated, then it hits up against this issue and you 
can't rely on aliases any more.

I would support a DIP.

[1] 
https://github.com/jll63/openmethods.d/tree/master/examples/matrix/source

[2] 
http://www.di.unipi.it/~nids/docs/templates_vs_inheritance.html

[3] https://run.dlang.io/gist/9da210e321af95e1ce373b5a6621e4f8
Apr 20 2018
prev sibling next sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [snip]

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.


I was experimenting with one of the open methods matrix examples 
[1] and trying to replace the virtual methods with templates. My 
example [3] does it statically and with structs so that it could 
be used with mir. However, the moment you try to make it a little 
bit more complicated and allow the type of the underlying matrix 
data to be templated, then it hits up against this issue and you 
can't rely on aliases any more.

I would support a DIP.

[1] 
https://github.com/jll63/openmethods.d/tree/master/examples/matrix/source

[2] 
http://www.di.unipi.it/~nids/docs/templates_vs_inheritance.html

[3] https://run.dlang.io/gist/9da210e321af95e1ce373b5a6621e4f8
Apr 20 2018
prev sibling next sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [snip]

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.


I was experimenting with one of the open methods matrix examples 
[1] and trying to replace the virtual methods with templates. My 
example [3] does it statically and with structs so that it could 
be used with mir. However, the moment you try to make it a little 
bit more complicated and allow the type of the underlying matrix 
data to be templated, then it hits up against this issue and you 
can't rely on aliases any more.

I would support a DIP.

[1] 
https://github.com/jll63/openmethods.d/tree/master/examples/matrix/source

[2] 
http://www.di.unipi.it/~nids/docs/templates_vs_inheritance.html

[3] https://run.dlang.io/gist/9da210e321af95e1ce373b5a6621e4f8
Apr 20 2018
prev sibling next sibling parent reply jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [snip]

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.


I was experimenting with one of the open methods matrix examples 
[1] and trying to replace the virtual methods with templates. My 
example [3] does it statically and with structs so that it could 
be used with mir. However, the moment you try to make it a little 
bit more complicated and allow the type of the underlying matrix 
data to be templated, then it hits up against this issue and you 
can't rely on aliases any more.

I would support a DIP.

[1] 
https://github.com/jll63/openmethods.d/tree/master/examples/matrix/source

[2] 
http://www.di.unipi.it/~nids/docs/templates_vs_inheritance.html

[3] https://run.dlang.io/gist/9da210e321af95e1ce373b5a6621e4f8
Apr 20 2018
parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 20 April 2018 at 16:03:40 UTC, jmh530 wrote:

 On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [...]


 I was experimenting with one of the open methods matrix 
 examples [1] and trying to replace the virtual methods with 
 templates. My example [3] does it statically and with structs 
 so that it could be used with mir. However, the moment you try 
 to make it a little bit more complicated and allow the type of 
 the underlying matrix data to be templated, then it hits up 
 against this issue and you can't rely on aliases any more.

 I would support a DIP.

 [1] 
 https://github.com/jll63/openmethods.d/tree/master/examples/matrix/source

 [2] 
 http://www.di.unipi.it/~nids/docs/templates_vs_inheritance.html

 [3] https://run.dlang.io/gist/9da210e321af95e1ce373b5a6621e4f8


Sorry, the stupid thing keeps telling me it's down for 
maintenance.
Apr 20 2018
prev sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 30 March 2018 at 06:11:22 UTC, 9il wrote:

 [snip]

 They are used in mir-lapack [5]. The bug fix also required for 
 mir (Sparse, CompressedTensor), and for the future Dlang image 
 library.


I was experimenting with one of the open methods matrix examples 
[1] and trying to replace the virtual methods with templates. My 
example [3] does it statically and with structs so that it could 
be used with mir. However, the moment you try to make it a little 
bit more complicated and allow the type of the underlying matrix 
data to be templated, then it hits up against this issue and you 
can't rely on aliases any more.

I would support a DIP.

[1] 
https://github.com/jll63/openmethods.d/tree/master/examples/matrix/source

[2] 
http://www.di.unipi.it/~nids/docs/templates_vs_inheritance.html

[3] https://run.dlang.io/gist/9da210e321af95e1ce373b5a6621e4f8
Apr 20 2018