www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Trying to do alias template deduction myself.

reply Elfstone <elfstone yeah.net> writes:
Related thread: 
https://forum.dlang.org/thread/wgvtwckvjyhnbpcuyyqy forum.dlang.org

It seems `dtemplate.deduceType` does all the deduction for both 
`is` and IFTI. I can already add a better error message, right 
before "goto Lnomatch":
`cannot deduce the instantiation of an alias template` (is that 
the right term?)
This will better explain to new users why it really fails:
`NOT because no callable candidate exists, but because D never 
tried to do anything about an alias template to find the match. 
So try instantiating the function explicitly then it will work.`

But my goal is:
```D
struct Matrix(U, size_t M, size_t N)
{
     U[M * N] data;
}

alias Vector3(U) = Matrix!(U, 3, 1);
alias Vec3(U) = Vector3!U;
alias Vec3Alt = Vector3;
alias Vec3Var(U...) = Vector3!(U);
alias V3(U) = Vector3!U;

alias Identity(U) = int;

void foo1(U)(in Vector3!U a)
{
}

void foo2(U)(in Vec3!U v)
{
}

void foo2Alt(U)(in Vec3Alt!U v)
{
}

void foo3Var(U...)(Vec3Var!(U))
{
}

void foo3(U)(in V3!U)
{
}

void foo4(U)(Identity!U u)
{
}

void main()
{
     auto instVar = Vector3!float();
     // The current behaviour is: deduction for alias template 
will always fail.
     // foo1(instVar); // expect OK
     // foo2(instVar); // expect OK
     // foo2Alt(instVar); // expect OK
     // foo3Var(instVar); // expect OK
     // foo3(instVar); // expect OK

     // foo4(Identity!int()); // let it fail

     // import std.regex;
     // import std.traits;
     // static assert(isInstanceOf!(Regex, Regex!char)); // now 
fails, not sure it can be fixed along
}
```

How I like it to behave is based on what C++ offers.

```C++
template <typename T, size_t M, size_t N>
struct Matrix {
	T data[M * N];
};

template<typename T, size_t M, size_t N>
using Mat = Matrix<T, M, N>;

template <typename T>
using Vector3 = Matrix<T, 3, 1>;

template <typename T>
using Vec3 = Vector3<T>;

template <typename T>
using Identity = int;

template <typename T>
void foo1(const Vector3<T>& v) {

}

template <typename T>
void foo2(const Vec3<T>& v) {

}

template <typename T, size_t M, size_t N>
void foo3(const Mat<T, M, N>& v) {

}

template <typename T>
void foo4(const Identity<T> id) {

}

int main() {
	foo1(Vector3<float>()); // OK
	foo2(Vector3<float>()); // OK
	foo3(Vector3<float>()); // OK

	// Let it fail
	// foo4(Identity<int>()); // no matching overloaded function 
found.
}
```


My current idea is to "expand" the alias with its to-be-matched 
parameter(s) to the fullest form if possible (for example, V3!U > 
Vec3!U > Matrix!(U, 3, 1)), then go to the parameter matching 
routine.

It seems possible, if I just follow 
`TemplateDeclaration.onemember` and expand the expression level 
by level, give up when running into overloads, conditions, or 
anything too complicate (I'm not sure if `onemember` ensures no 
conditions). I could be wrong, but based on my few hours of 
reading the code and really helpful comments in the forum, I 
believe people who are more familiar with the compiler code can 
implement it instantantly.

I'm making this post not to promise to fix it (I'll try), but to 
gather opinions:
Do you think such behaviour in D is desirable (regardless of how 
I imagine it can be implemented)?
What do I miss?
Mar 30 2023
next sibling parent reply Petar Kirov [ZombineDev] <petar.p.kirov gmail.com> writes:
On Friday, 31 March 2023 at 05:19:48 UTC, Elfstone wrote:

 [..]
 Do you think such behaviour in D is desirable (regardless of 
 how I imagine it can be implemented)?


YES! Thank you for driving this initiative!
Mar 31 2023
parent jmh530 <john.michael.hall gmail.com> writes:
On Friday, 31 March 2023 at 07:50:58 UTC, Petar Kirov 
[ZombineDev] wrote:

 On Friday, 31 March 2023 at 05:19:48 UTC, Elfstone wrote:

 [..]
 Do you think such behaviour in D is desirable (regardless of 
 how I imagine it can be implemented)?


 YES! Thank you for driving this initiative!


Ditto.
Mar 31 2023
prev sibling next sibling parent reply Elfstone <elfstone yeah.net> writes:
On Friday, 31 March 2023 at 05:19:48 UTC, Elfstone wrote:

 [..]


Some updates and thoughts.

The good new is, I have all the above cases working (except the 
one with tuple)! And even more complicated cases, such as:

```D
private struct SomeTemp(T, U, size_t N)
{
}

alias SomeAlias(X, Y, size_t C) = SomeTemp!(Y, X, C);

alias SomeOtherAlias(X, Y) = SomeAlias!(X, Y, 1);

void someOtherFoo(P, Q)(SomeOtherAlias!(Q, P) v)
{
     static assert(is(P == int));
     static assert(is(Q == float));
}

void main()
{
	someOtherFoo(SomeTemp!(float, int 1)()); // ok
	someOtherFoo(SomeTemp!(float, int, 3)()); // fails.
}
```

As I dig more into the compiler code, it's getting more obvious 
that this task is much tougher than I previously imagined. I 
cannot just "expand" the alias expression. It seems the 
"expansion" happens only during `templateInstanceSemantic` and I 
cannot reuse any of that with to-be-deduced arguments.

Now I take another approach: while matching `[U_, N_], Vec!(U_, 
N_)` to `Matrix!(float, 3, 1)`, I find the `AliasDeclaration` 
(alias Vec(U, N) = Matrix!(U, N, 1)) and call `deduceType` on 
`[U, N], Matrix!(U, N, 1)` - now it can produce [float, 3]. All I 
need to do is match [float, 3] to [U_, N_]. This also works 
recursively on a chain of aliases as long as it ends with a 
template declaration.

The potentional is likely the capability of original IFTI for 
alias template, but unfortunately I cannot reuse the existing 
matching code either (before I fully understand it, if ever). 
Still I figure it's better to write some simplistic matching with 
limit capability than writing a separate "expansion". It only 
takes several lines to do the basic matching anyway - the 
compiler will make sure the arguments really match later.

I'm almost sure my code works with bare type identifiers and 
values. I can probably support tuple soon. I'll figure out what I 
can do with fancy U:U*, U: A!U, etc.

I'll upload my code, when I feel more ... secure about the 
implementation, and because I coded during lunch break, I can't 
just upload it from work, maybe on weekends.
Apr 03 2023
next sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 4/3/23 8:56 AM, Elfstone wrote:

 On Friday, 31 March 2023 at 05:19:48 UTC, Elfstone wrote:

 [..]


 
 Some updates and thoughts.
 
 The good new is, I have all the above cases working (except the one with 
 tuple)!


Just want to say, I'm super excited to see this possibly getting solved!

Thanks for the attempt, and I hope you succeed.

-Steve
Apr 03 2023
prev sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
On Monday, 3 April 2023 at 12:56:10 UTC, Elfstone wrote:

 
 I'm almost sure my code works with bare type identifiers and 
 values. I can probably support tuple soon. I'll figure out what 
 I can do with fancy U:U*, U: A!U, etc.


Why don't you try using AliasSeq?  I think it would be very 
elegant with a triple staticMap.  For example:

```d
import std.meta;

struct Matrix(U, size_t M, size_t N)
{
     U[M * N] data;
}

alias P = AliasSeq!(byte, short, int);
alias X = AliasSeq!(3, 3, 4);
alias Y = AliasSeq!(1, 3, 2);

void main()
{
   alias Vec3(U) = Matrix!(U, 3, 3);
   alias T = float;

   Vec3!T cube;
   void singleMatrix(U)(Vec3!U v){}

   singleMatrix!T(cube); // ok
   assert(is(typeof(cube) == Vec3!T));

   // ...

   alias Vec3Var(U...) = staticMapTrio!(Matrix, U);
   alias S = AliasSeq!(P, X, Y);

   Vec3Var!S trio;
   void triMatrix(U...)(in Vec3Var!(U) v){}

   triMatrix!S(trio); // ok
   assert(is(typeof(trio) == Vec3Var!S));
}

template staticMapTrio(alias fun, args...) {
   alias staticMapTrio = AliasSeq!();
   static foreach (i; 0..args.length / 3) {
     staticMapTrio = AliasSeq!(staticMapTrio,
       fun!(args[0..$/3][i],
            args[$/3..($/3) * 2][i],
            args[($/3) * 2..($/3) * 3][i]
       )
     );
   }
}
```
Apr 03 2023
next sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
On Monday, 3 April 2023 at 19:50:14 UTC, Salih Dincer wrote:

 ... very elegant ...


I like it better when program prints:

```d

 import std.stdio;


import std.meta;

struct Matrix(U, size_t M, size_t N)
{
     U[M * N] data;
}

alias P = AliasSeq!(byte, short, int);
alias X = AliasSeq!(3, 3, 4);
alias Y = AliasSeq!(1, 3, 2);

void main()
{
   alias Vec3(U) = Matrix!(U, 3, 3);
   alias T = float;

   Vec3!T cube;
   void singleMatrix(U)(in Vec3!U v)
   {
     typeid(aTypeOf!(v.data)).write(": ");
     v.data.writeln;
   }

   singleMatrix!T(cube); // ok
   assert(is(typeof(cube) == Vec3!T));

   // ...

   alias Vec3Var(U...) = staticMapTrio!(Matrix, U);
   alias S = AliasSeq!(P, X, Y);

   Vec3Var!S trio;
   void triMatrix(U...)(in Vec3Var!(U) vps)
   {
     foreach(ref v; vps)
     {
       typeid(aTypeOf!(v.data)).write(": ");
       v.data.writeln;
     }
   }

   triMatrix!S(trio); // ok
   assert(is(typeof(trio) == Vec3Var!S));
}

template staticMapTrio(alias fun, args...) {
   alias staticMapTrio = AliasSeq!();
   static foreach (i; 0..args.length / 3) {
     staticMapTrio = AliasSeq!(staticMapTrio,
       fun!(args[0..$/3][i],
            args[$/3..($/3) * 2][i],
            args[($/3) * 2..($/3) * 3][i]
       )
     );
   }
}

template aTypeOf(alias A) {
   alias Type(T : T[]) = T;
   alias aTypeOf = Type!(typeof(A));
}

/* PRINTS:
float: [nan, nan, nan, nan, nan, nan, nan, nan, nan]
byte: [0, 0, 0]
short: [0, 0, 0, 0, 0, 0, 0, 0, 0]
int: [0, 0, 0, 0, 0, 0, 0, 0]
*/
```

SDB 79
Apr 03 2023
parent Elfstone <elfstone yeah.net> writes:
On Monday, 3 April 2023 at 20:17:00 UTC, Salih Dincer wrote:

 [..]


Oh, I think I get it. `Vec3Var` in my original post is just a 
poor choice of name. It's is meant for correct type deduction 
with `U...`, not that I want a tuple of types.
Apr 03 2023
prev sibling parent Elfstone <elfstone yeah.net> writes:
On Monday, 3 April 2023 at 19:50:14 UTC, Salih Dincer wrote:

 On Monday, 3 April 2023 at 12:56:10 UTC, Elfstone wrote:

 [...]


 Why don't you try using AliasSeq?  I think it would be very 
 elegant with a triple staticMap.  For example:

 [...]


Hm, I don't understand what your code does. So Vec3Var!S yields 
the tuple `(Matrix!(byte, 3, 1), Matrix!(short, 3, 3), 
Matrix!(int, 4, 2))`, but what do I do with the tuple?
Apr 03 2023
prev sibling parent reply Elfstone <elfstone yeah.net> writes:
On Friday, 31 March 2023 at 05:19:48 UTC, Elfstone wrote:

 [..]


Hi all! I've pushed my code:
https://github.com/Lucipetus/dmd/tree/fix_alias_template_deduction
And here's my test code:
https://github.com/Lucipetus/dmd_test - Run `dmd atifti.d`

I'll have a look on `static assert(isInstance!(Regex, 
Regex!char))`, it still fails, but `static 
assert(is(Vector3!float == Vector3!U, U))` now compiles!

The fix is really, really simple, as I've explained in my last 
reply: recursively call `deduceType`, match the output with 
largely the same code as the original matching routine `L2:` - as 
you can see, my matching is simply an abridged version of the 
original. I think ideally we can share the same code, which 
requires modifying the original - I don't think I'm qualified to 
do that. But I think it's a proof of idea. We can do IFTI for 
alias template!

Another thing. I was thinking of `alias AliasT(U:U*) = TempT(U)`, 
but found out IFTI couldn't resolve this: 
https://github.com/Lucipetus/dmd_test/blob/master/iftilim.d `void 
foo(U : U*)(TempT!U v)`, so why bother?
Apr 04 2023
parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
Please open a PR on to dmd's upstream repo so the testsuite can run and 
you can start getting feedback from compiler devs.

This would be nice to be resolved.
Apr 04 2023
parent reply Elfstone <elfstone yeah.net> writes:
On Wednesday, 5 April 2023 at 04:15:53 UTC, Richard (Rikki) 
Andrew Cattermole wrote:

 Please open a PR on to dmd's upstream repo so the testsuite can 
 run and you can start getting feedback from compiler devs.

 This would be nice to be resolved.


I think I will eventually.

The matching part is still a problem - it's a copy of `L2:`.

Help is needed. I'm not confident enough to make changes to `L2:` 
so it can be shared. Do you think it's a better idea to get more 
help by opening a PR? It'd be great if a seasoned D dev would 
take it over and finish it.

---

Update:

I just solved `static assert(isInstanceOf!(Regex, Regex!char))`, 
but also noticed there could be much more complicated alias 
declarations. I wouldn't want to handle them all. For example:

```D
alias SomeAlias(T, U) = somemodule.SomeTemp!T.SomeInnerTemp!U;
void foo(X, Y)(SomeAlias!(T, U) v) {} // IFTI will fail
void foo(X, Y)(SomeTemp!T.SomeInnerTemp!U v) {} // also fails
```
Apr 05 2023
parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
On 06/04/2023 5:44 PM, Elfstone wrote:

 Help is needed. I'm not confident enough to make changes to `L2:` so it 
 can be shared. Do you think it's a better idea to get more help by 
 opening a PR? It'd be great if a seasoned D dev would take it over and 
 finish it.


Yeah, it can always be done in multiple PR's; partial implementations 
are not a bad thing!
Apr 05 2023
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 4/6/23 1:46 AM, Richard (Rikki) Andrew Cattermole wrote:

 On 06/04/2023 5:44 PM, Elfstone wrote:

 Help is needed. I'm not confident enough to make changes to `L2:` so 
 it can be shared. Do you think it's a better idea to get more help by 
 opening a PR? It'd be great if a seasoned D dev would take it over and 
 finish it.


 
 Yeah, it can always be done in multiple PR's; partial implementations 
 are not a bad thing!


Yeah, please push what you can. It's OK if IFTI isn't perfect.

The best way to get it looked at and have the experts take over is to 
make a PR!

-Steve
Apr 06 2023
parent reply Elfstone <elfstone yeah.net> writes:
On Thursday, 6 April 2023 at 14:58:59 UTC, Steven Schveighoffer 
wrote:

 On 4/6/23 1:46 AM, Richard (Rikki) Andrew Cattermole wrote:

 On 06/04/2023 5:44 PM, Elfstone wrote:

 Help is needed. I'm not confident enough to make changes to 
 `L2:` so it can be shared. Do you think it's a better idea to 
 get more help by opening a PR? It'd be great if a seasoned D 
 dev would take it over and finish it.


 
 Yeah, it can always be done in multiple PR's; partial 
 implementations are not a bad thing!


 Yeah, please push what you can. It's OK if IFTI isn't perfect.

 The best way to get it looked at and have the experts take over 
 is to make a PR!

 -Steve


I need help with this problem, friends!

PR requires spec change: 
https://github.com/dlang/dmd/discussions/15086
Apr 06 2023
parent reply Salih Dincer <salihdb hotmail.com> writes:
On Friday, 7 April 2023 at 04:55:16 UTC, Elfstone wrote:

 I need help with this problem, friends!

 PR requires spec change: 
 https://github.com/dlang/dmd/discussions/15086


I tried the test code in 2 different versions (one of them old) 
and didn't run into any issues. It compiled for me with no errors.

SDB 79
Apr 06 2023
parent reply Elfstone <elfstone yeah.net> writes:
On Friday, 7 April 2023 at 05:39:52 UTC, Salih Dincer wrote:

 On Friday, 7 April 2023 at 04:55:16 UTC, Elfstone wrote:

 I need help with this problem, friends!

 PR requires spec change: 
 https://github.com/dlang/dmd/discussions/15086


 I tried the test code in 2 different versions (one of them old) 
 and didn't run into any issues. It compiled for me with no 
 errors.

 SDB 79


This shouldn't happen. What test code did you run?

D master should be able to compile this code, as it's part of D's 
autotest.

```D
    struct S(T) {}
    alias A(T) = S!T;

    static assert(is(A!int : S!T, T));
    static assert(!is(A!int : A!T, T));
```

But with my PR this will not compile, because my PR is exactly 
about resolving `is(A!int : A!T, T)` to be true, therefore it 
can't pass the autotest.

I'm stuck in a circle: I need to get my PR to be reviewed, before 
I can convince others to change the spec. But the spec is 
preventing my PR from passing the autotest.
Apr 06 2023
parent reply jmh530 <john.michael.hall gmail.com> writes:
On Friday, 7 April 2023 at 05:59:30 UTC, Elfstone wrote:

 [snip]


Has there been any update on this?
May 18 2023
parent reply Elfstone <elfstone yeah.net> writes:
On Thursday, 18 May 2023 at 12:30:49 UTC, jmh530 wrote:

 On Friday, 7 April 2023 at 05:59:30 UTC, Elfstone wrote:

 [snip]


 Has there been any update on this?


The PR had a few failed tests for some reason. After a recent 
rebase, it passed all tests but two awaiting for approval.

No more response from the maintainers than what you can see in 
the conversation there:
https://github.com/dlang/dmd/pull/15085 :(
May 21 2023
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Monday, 22 May 2023 at 02:53:08 UTC, Elfstone wrote:

 On Thursday, 18 May 2023 at 12:30:49 UTC, jmh530 wrote:

 On Friday, 7 April 2023 at 05:59:30 UTC, Elfstone wrote:

 [snip]


 Has there been any update on this?


 The PR had a few failed tests for some reason. After a recent 
 rebase, it passed all tests but two awaiting for approval.

 No more response from the maintainers than what you can see in 
 the conversation there:
 https://github.com/dlang/dmd/pull/15085 :(


I generally follow a schedule of two weeks between pings on my 
PRs. IMO, don't be afraid of being more annoying than you feel is 
permissible. This sort of abandonment for huge heaps of volunteer 
work is unacceptable and frankly insulting.
May 21 2023
parent reply Elfstone <elfstone yeah.net> writes:
On Monday, 22 May 2023 at 06:25:15 UTC, FeepingCreature wrote:

 On Monday, 22 May 2023 at 02:53:08 UTC, Elfstone wrote:

 On Thursday, 18 May 2023 at 12:30:49 UTC, jmh530 wrote:

 On Friday, 7 April 2023 at 05:59:30 UTC, Elfstone wrote:

 [snip]


 Has there been any update on this?


 The PR had a few failed tests for some reason. After a recent 
 rebase, it passed all tests but two awaiting for approval.

 No more response from the maintainers than what you can see in 
 the conversation there:
 https://github.com/dlang/dmd/pull/15085 :(


 I generally follow a schedule of two weeks between pings on my 
 PRs. IMO, don't be afraid of being more annoying than you feel 
 is permissible. This sort of abandonment for huge heaps of 
 volunteer work is unacceptable and frankly insulting.


In this case I think it was the failed tests.
I'm glad to find out that all checks are now successful after 
rebasing and Walter has left reasonable inputs. I'll see what I 
can do when I have the time.
May 22 2023
parent jmh530 <john.michael.hall gmail.com> writes:
On Tuesday, 23 May 2023 at 04:20:23 UTC, Elfstone wrote:

 [snip]

 In this case I think it was the failed tests.
 I'm glad to find out that all checks are now successful after 
 rebasing and Walter has left reasonable inputs. I'll see what I 
 can do when I have the time.


Glad to see there's some movement.
May 24 2023