www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - inout template parameter, or a solution to the templated container

reply "deadalnix" <deadalnix gmail.com> writes:
We currently have a problem with containers : it is very 
difficult to implement them in a way that is compliant type 
qualifiers. To restate the problem shortly, let's imagine we want 
to implement array's as a library type.

struct Array(T) {
     size_t length;
     T* ptr;
     // Methods
}

Now we have several problems with type qualifiers. For instance, 
Array!T won't implicitly cast to Array!const(T), and 
const(Array!T) now become a completely useless type, as ptr will 
become const by transitivity which will create internal 
inconsistencies.

This problem is known and makes it hard to provide a nice 
container library for D. This also imply a lot of circuitry in 
the compiler that can (and should) be provided as library.

So I propose to introduce the inout template parameter type. We 
declare as follow :

Array(inout T) {
     size_t length;
     T* ptr
}

The inout template parameter is a type parameter, and so don't 
overload on them (if both Array(T) and Array(inout T) the 
instantiation is ambiguous).

Within the template, T is always seen as inout, and only one 
instantiation occur for all top type qualifiers. Array!T and 
Array!const(T) refers to the same instance of Array. As a result, 
this makes it impossible to specialize Array on T's type 
qualifier.

The real type qualifier is determined from the outside. A user of 
Array!T consider inout as meaning mutable, when a user of 
Array!const(T) consider it as meaning const, for anything related 
to Array.

Implicit cast is allowed for instances of Array with different 
inout parameter's type qualifier, as long as implicit conversion 
between such qualifier is allowed. Array!T implicitly convert to 
Array!const(T) but not the other way around.

Finally, Array's type qualifier turtle down to inout parameters's 
type qualifier. alias A = Array!T; static assert(is(const(A)) == 
const(Array!const(T))); alias B = Array!immutable(T); static 
assert(is(const(A)) == const(Array!immutable(T)));

The idea popped in my mind yesterday, so it is not really super 
fleshed out, and I'm not sure if some horrible dark corner case 
makes it completely worthless. But it seems super promising to 
me, so I want to share. The current situation isn't satisfying 
and we desperately need a solution.
Jun 11 2013
next sibling parent reply Timothee Cour <thelastmammoth gmail.com> writes:
On Tue, Jun 11, 2013 at 11:08 PM, deadalnix <deadalnix gmail.com> wrote:


 We currently have a problem with containers : it is very difficult to
 implement them in a way that is compliant type qualifiers. To restate the
 problem shortly, let's imagine we want to implement array's as a library
 type.

 struct Array(T) {
     size_t length;
     T* ptr;
     // Methods
 }

 Now we have several problems with type qualifiers. For instance, Array!T
 won't implicitly cast to Array!const(T), and const(Array!T) now become a
 completely useless type, as ptr will become const by transitivity which
 will create internal inconsistencies.

 This problem is known and makes it hard to provide a nice container
 library for D. This also imply a lot of circuitry in the compiler that can
 (and should) be provided as library.

 So I propose to introduce the inout template parameter type. We declare as
 follow :

 Array(inout T) {
     size_t length;
     T* ptr
 }

 The inout template parameter is a type parameter, and so don't overload on
 them (if both Array(T) and Array(inout T) the instantiation is ambiguous).

 Within the template, T is always seen as inout, and only one instantiation
 occur for all top type qualifiers. Array!T and Array!const(T) refers to the
 same instance of Array. As a result, this makes it impossible to specialize
 Array on T's type qualifier.

 The real type qualifier is determined from the outside. A user of Array!T
 consider inout as meaning mutable, when a user of Array!const(T) consider
 it as meaning const, for anything related to Array.

 Implicit cast is allowed for instances of Array with different inout
 parameter's type qualifier, as long as implicit conversion between such
 qualifier is allowed. Array!T implicitly convert to Array!const(T) but not
 the other way around.

 Finally, Array's type qualifier turtle down to inout parameters's type
 qualifier. alias A = Array!T; static assert(is(const(A)) ==
 const(Array!const(T))); alias B = Array!immutable(T); static
 assert(is(const(A)) == const(Array!immutable(T)));

 The idea popped in my mind yesterday, so it is not really super fleshed
 out, and I'm not sure if some horrible dark corner case makes it completely
 worthless. But it seems super promising to me, so I want to share. The
 current situation isn't satisfying and we desperately need a solution.



Why not use a castConstSafe function that'll transform A!T into A!(const
T), generically:

auto ref castSafe(T,S)(auto ref S a){...}
S a; T b=castSafe!T(a); //same as T b=cast(T)(a) except that it only
compiles if S=>T only involves nonconst=>const conversions (works
recursively):
example: A!(double) => A!(const double) is allowed but not other direction.

More specifically:
auto ref castConstSafe(S)(auto ref S a){...} //transforms A!T into A!(const
T), generically

then:
void foo(B a) if (is(ElementType!B == const)){...}
A!(const double) a1;
A!(double) a2;
foo(a1.castConstSafe); //works
foo(a2.castConstSafe); //works

All it requires is to pass a.castConstSafe instead of a.
Jun 12 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 12 June 2013 at 09:16:30 UTC, Timothee Cour wrote:

 Why not use a castConstSafe function that'll transform A!T into 
 A!(const
 T), generically:

 auto ref castSafe(T,S)(auto ref S a){...}
 S a; T b=castSafe!T(a); //same as T b=cast(T)(a) except that it 
 only
 compiles if S=>T only involves nonconst=>const conversions 
 (works
 recursively):
 example: A!(double) => A!(const double) is allowed but not 
 other direction.

 More specifically:
 auto ref castConstSafe(S)(auto ref S a){...} //transforms A!T 
 into A!(const
 T), generically

 then:
 void foo(B a) if (is(ElementType!B == const)){...}
 A!(const double) a1;
 A!(double) a2;
 foo(a1.castConstSafe); //works
 foo(a2.castConstSafe); //works

 All it requires is to pass a.castConstSafe instead of a.


Because Foo!T and Foo!(const T) are completely unrelated types. 
Casting from one to the other gives 0 guarantees it actually 
works. For example:

//----
struct Foo(T)
{
     static if (is(T == const int))
     {
         void do_it()const{writeln("this");}
     }
     else
     {
         void do_it()const{writeln("that");}
     }
}

void main()
{
     Foo!int a;
     const(Foo!int)*  pa = &a;
     Foo!(const int)* pb = cast(Foo!(const int)*) &a;
     pa.do_it(); //prints "that"
     pb.do_it(); //prints "this"
}
//----

Of course, I could have also changed the members, making memory 
mapping incompatible, amongst others...
Jun 12 2013
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Wednesday, 12 June 2013 at 06:08:58 UTC, deadalnix wrote:

 Within the template, T is always seen as inout, and only one 
 instantiation occur for all top type qualifiers.


So are you adding inout as a type qualifier? Currently it is only 
a storage class usable in functions.
Jun 12 2013
parent "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 June 2013 at 10:38:20 UTC, Peter Alexander wrote:

 On Wednesday, 12 June 2013 at 06:08:58 UTC, deadalnix wrote:

 Within the template, T is always seen as inout, and only one 
 instantiation occur for all top type qualifiers.


 So are you adding inout as a type qualifier? Currently it is 
 only a storage class usable in functions.


I choose inout as the idea is really the same as it is for 
function : a wildcard type qualifier for the callee, a known one 
for the caller. Here it is a type qualifier know by the 
instancier, not the instanciee.

If you consider template argument as compile time argument, as 
opposed to runtime arguments, this make sense.
Jun 12 2013
prev sibling next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 12 June 2013 at 06:08:58 UTC, deadalnix wrote:

 ...


I like it!


 The idea popped in my mind yesterday, so it is not really super 
 fleshed out, and I'm not sure if some horrible dark corner case 
 makes it completely worthless. But it seems super promising to 
 me, so I want to share. The current situation isn't satisfying 
 and we desperately need a solution.


Maybe...


 Within the template, T is always seen as inout, and only one 
 instantiation occur for all top type qualifiers. Array!T and 
 Array!const(T) refers to the same instance of Array. As a 
 result, this makes it impossible to specialize Array on T's 
 type qualifier.


OK, but how do you handle methods that rely on T being 
(potentially) mutable? For example:

//----
struct Foo(inout T)
{
     T a;
     static if (isAssignable!T) //So here, "T" is actually "inout 
T", correct?
     {
         void opAssign(T other)
         {a = other.a;}
     }
}
//----

Or is the idea that when instantiated with a "const T", non const 
methods are not compiled in for that instantiation...?

What about:

//----
struct Foo(inout T)
{
     T[10] buffer;
     size_t i = 0;
     ref T get() const {return buffer[i];}
     void setIndex(size_t i){this.i = i;}
}
//----

This time, the mutable method works, even when T is not mutable :/

I haven't thought through the implications, but it looks like 
there is a little something missing to make it work.

I DO like your proposition a lot. Being able to have templates 
that are all instanciated based on the Unqualed type is definitly 
a plus.
Jun 12 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 June 2013 at 12:37:13 UTC, monarch_dodra wrote:

 OK, but how do you handle methods that rely on T being 
 (potentially) mutable? For example:

 //----
 struct Foo(inout T)
 {
     T a;
     static if (isAssignable!T) //So here, "T" is actually 
 "inout T", correct?
     {
         void opAssign(T other)
         {a = other.a;}
     }
 }
 //----


T is not assignable. If it were, you couldn't cast implicitly to 
Foo!const(T) . You can still return a T by reference, the caller 
know if it is mutable or not.


 Or is the idea that when instantiated with a "const T", non 
 const methods are not compiled in for that instantiation...?

 What about:

 //----
 struct Foo(inout T)
 {
     T[10] buffer;
     size_t i = 0;
     ref T get() const {return buffer[i];}
     void setIndex(size_t i){this.i = i;}
 }
 //----


Foo's type qualifier turtle down to inout parameter type 
qualifier. You are returning a ref to a const(T) not a ref T. 
This is a compile time error.

If you don't put const, then T's type is known by the caller, and 
the code is correct.


 I haven't thought through the implications, but it looks like 
 there is a little something missing to make it work.


Yes, details may need to be sorted out.


 I DO like your proposition a lot. Being able to have templates 
 that are all instanciated based on the Unqualed type is 
 definitly a plus.
Jun 12 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 12 June 2013 at 13:04:28 UTC, deadalnix wrote:

 On Wednesday, 12 June 2013 at 12:37:13 UTC, monarch_dodra wrote:

 OK, but how do you handle methods that rely on T being 
 (potentially) mutable? For example:

 //----
 struct Foo(inout T)
 {
    T a;
    static if (isAssignable!T) //So here, "T" is actually 
 "inout T", correct?
    {
        void opAssign(T other)
        {a = other.a;}
    }
 }
 //----


 T is not assignable. If it were, you couldn't cast implicitly 
 to Foo!const(T) . You can still return a T by reference, the 
 caller know if it is mutable or not.


I'm not sure I understand the answer. If a parameter is marked as 
inout, then you are saying it must be considered as const in the 
entire struct?

*But*, when the user handles the struct, user may "interfere" 
with his own knowledge of the object's mutability?

This seems too restrictive to be useful, no? propery setters go 
out the window for non-escaping refs, amongst others. 
Implementation wise, I also don't see many usecases for useful 
structs that can't do mutating operations on T.

I think being able to mark which functions will operate only when 
T has (or lacks) specific qualifiers (because there is the same 
problem for functions that could only exist when T is immutable)? 
The problem is that the mutable->const<-immutable hierarchy is 
flipped on its head.

Not to mention that a template could have multiple parameters. 
Something like this?

struct Foo(inout T, inout U)
{
     //Function body. T and U are not qualified. User may qualify 
as wanted.

     void foo(); //normal function. T and U are "const" in here.
     void bar() const; //normal const function. T and U are also 
"const" in here.

     void foo1() inout(T); //This function requires T to be 
mutable. It will not appear in const
     void foo2() immutable(U); //This function requires (U) to be 
immutable. It will not appear in const.
     void foo3() inout(T) inout(U); //Both T and U need to be 
mutable.
     void foo4() inout(T) immutable(U); //Mix and match.
}

Or something along these lines. I couldn't really see it working 
any other way. I mean, as presented, it feels that "Foo!T" is 
simply an alias for what you'd get with "Foo!(const T)", but you 
preserve qualification information on the outside.
Jun 13 2013
prev sibling next sibling parent "Jason House" <jason.james.house gmail.com> writes:
On Wednesday, 12 June 2013 at 06:08:58 UTC, deadalnix wrote:

 We currently have a problem with containers : it is very 
 difficult to implement them in a way that is compliant type 
 qualifiers. To restate the problem shortly, let's imagine we 
 want to implement array's as a library type.

 struct Array(T) {
     size_t length;
     T* ptr;
     // Methods
 }

 Now we have several problems with type qualifiers. For 
 instance, Array!T won't implicitly cast to Array!const(T), and 
 const(Array!T) now become a completely useless type, as ptr 
 will become const by transitivity which will create internal 
 inconsistencies.

 This problem is known and makes it hard to provide a nice 
 container library for D. This also imply a lot of circuitry in 
 the compiler that can (and should) be provided as library.

 So I propose to introduce the inout template parameter type. We 
 declare as follow :

 Array(inout T) {
     size_t length;
     T* ptr
 }

 The inout template parameter is a type parameter, and so don't 
 overload on them (if both Array(T) and Array(inout T) the 
 instantiation is ambiguous).

 Within the template, T is always seen as inout, and only one 
 instantiation occur for all top type qualifiers. Array!T and 
 Array!const(T) refers to the same instance of Array. As a 
 result, this makes it impossible to specialize Array on T's 
 type qualifier.

 The real type qualifier is determined from the outside. A user 
 of Array!T consider inout as meaning mutable, when a user of 
 Array!const(T) consider it as meaning const, for anything 
 related to Array.

 Implicit cast is allowed for instances of Array with different 
 inout parameter's type qualifier, as long as implicit 
 conversion between such qualifier is allowed. Array!T 
 implicitly convert to Array!const(T) but not the other way 
 around.

 Finally, Array's type qualifier turtle down to inout 
 parameters's type qualifier. alias A = Array!T; static 
 assert(is(const(A)) == const(Array!const(T))); alias B = 
 Array!immutable(T); static assert(is(const(A)) == 
 const(Array!immutable(T)));

 The idea popped in my mind yesterday, so it is not really super 
 fleshed out, and I'm not sure if some horrible dark corner case 
 makes it completely worthless. But it seems super promising to 
 me, so I want to share. The current situation isn't satisfying 
 and we desperately need a solution.


I think it needs to be fleshed out better...  Try to add the 
methods to your array class and think through the required 
validation. For example, an insert of const(T) would only work if 
implemented as a copy on write. It would also be good to think 
through how to handle class hierarchies.

I believe the correct handling requires awareness of covariant 
and contravariant types. I first heard about them in scala, but I 

you'll need two type arguments: array(in I, out O), where I is 
implicitly castable to O. If C derives from B which derives from 
A, then array!(B,B) is implicitly castable to array!(C,B), 
array!(B,A), and array!(C,A)
Jun 12 2013
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 12 Jun 2013 02:08:48 -0400, deadalnix <deadalnix gmail.com> wrote:


 We currently have a problem with containers : it is very difficult to  
 implement them in a way that is compliant type qualifiers. To restate  
 the problem shortly, let's imagine we want to implement array's as a  
 library type.

 struct Array(T) {
      size_t length;
      T* ptr;
      // Methods
 }

 Now we have several problems with type qualifiers. For instance, Array!T  
 won't implicitly cast to Array!const(T), and const(Array!T) now become a  
 completely useless type, as ptr will become const by transitivity which  
 will create internal inconsistencies.

 This problem is known and makes it hard to provide a nice container  
 library for D. This also imply a lot of circuitry in the compiler that  
 can (and should) be provided as library.

 So I propose to introduce the inout template parameter type. We declare  
 as follow :

 Array(inout T) {
      size_t length;
      T* ptr
 }

 The inout template parameter is a type parameter, and so don't overload  
 on them (if both Array(T) and Array(inout T) the instantiation is  
 ambiguous).

 Within the template, T is always seen as inout, and only one  
 instantiation occur for all top type qualifiers. Array!T and  
 Array!const(T) refers to the same instance of Array. As a result, this  
 makes it impossible to specialize Array on T's type qualifier.


The one problem I see here is the case where you want to have Array mutate  
its data.

For example, let's say Array makes ptr and length private overloads  
opIndex AND opIndexAssign to prevent taking the the address of its data.

How do you do opIndexAssign with your mechanism?  There is no "mutable"  
type qualifier, so there isn't a way to say, "only allow calling this  
function if T is mutable," like we have with const and immutable member  
functions.

Another issue here is, what if you don't want Array to be a template?   
That is, you want:

struct IntArray {
     size_t length;
     int *ptr;
}

How do you make this tail-const-able?


 The real type qualifier is determined from the outside. A user of  
 Array!T consider inout as meaning mutable, when a user of Array!const(T)  
 consider it as meaning const, for anything related to Array.

 Implicit cast is allowed for instances of Array with different inout  
 parameter's type qualifier, as long as implicit conversion between such  
 qualifier is allowed. Array!T implicitly convert to Array!const(T) but  
 not the other way around.

 Finally, Array's type qualifier turtle down to inout parameters's type  
 qualifier. alias A = Array!T; static assert(is(const(A)) ==  
 const(Array!const(T))); alias B = Array!immutable(T); static  
 assert(is(const(A)) == const(Array!immutable(T)));

 The idea popped in my mind yesterday, so it is not really super fleshed  
 out, and I'm not sure if some horrible dark corner case makes it  
 completely worthless. But it seems super promising to me, so I want to  
 share. The current situation isn't satisfying and we desperately need a  
 solution.


It's a very good start, and very close to the solution I have.  I'm going  
to finish my article and post it hopefully next week.

-Steve
Jun 12 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
I knew you'll have interesting feddback.

On Wednesday, 12 June 2013 at 15:33:13 UTC, Steven Schveighoffer 
wrote:

 The one problem I see here is the case where you want to have 
 Array mutate its data.


I admit that this won't solve the issue. But I don't know if this 
is an issue to be fair.


 For example, let's say Array makes ptr and length private 
 overloads opIndex AND opIndexAssign to prevent taking the the 
 address of its data.


I'm not sure what is the use case. But that is clearly impossible 
with the solution I proposed.


 Another issue here is, what if you don't want Array to be a 
 template?  That is, you want:

 struct IntArray {
     size_t length;
     int *ptr;
 }

 How do you make this tail-const-able?


By making it a template. I'm also not sure what is the use case 
here, but still this is a limitation.


 It's a very good start, and very close to the solution I have.  
 I'm going to finish my article and post it hopefully next week.


Could you give a quick executive summary ?
Jun 12 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 12 Jun 2013 12:18:50 -0400, deadalnix <deadalnix gmail.com> wrote:


 I knew you'll have interesting feddback.

 On Wednesday, 12 June 2013 at 15:33:13 UTC, Steven Schveighoffer wrote:

 The one problem I see here is the case where you want to have Array  
 mutate its data.


 I admit that this won't solve the issue. But I don't know if this is an  
 issue to be fair.


To avoid escaping pointers to your elements.  This is especially important  
if you have total control over allocation of your elements.

I would have to think about it more, but I think there is another  
fundamental problem with this.  It feels like you could be converting  
const two levels deep, which is not allowed.


 For example, let's say Array makes ptr and length private overloads  
 opIndex AND opIndexAssign to prevent taking the the address of its data.


 I'm not sure what is the use case. But that is clearly impossible with  
 the solution I proposed.


 Another issue here is, what if you don't want Array to be a template?   
 That is, you want:

 struct IntArray {
     size_t length;
     int *ptr;
 }

 How do you make this tail-const-able?


 By making it a template. I'm also not sure what is the use case here,  
 but still this is a limitation.


The use case:

class Container(T)
{

    struct range
    {
       size_t length;
       T* ptr;
    }
}

Which I use for all dcollections containers.

Yes, I could introduce it like this:

struct range(inout U) if(is(U == T))
{
    size_t length;
    U *ptr;
}

but it feels unnecessary.  I also find the usage for this solution clumsy.


 It's a very good start, and very close to the solution I have.  I'm  
 going to finish my article and post it hopefully next week.


 Could you give a quick executive summary ?


I am hesitant to publicly announce it before releasing the article :)  I  
don't want preconceptions for when people read it.  I will send you an  
email.

-Steve
Jun 12 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 June 2013 at 19:00:28 UTC, Steven Schveighoffer 
wrote:

 To avoid escaping pointers to your elements.  This is 
 especially important if you have total control over allocation 
 of your elements.


Yes, that is definitively a point.


 The use case:

 class Container(T)
 {

    struct range
    {
       size_t length;
       T* ptr;
    }
 }

 Which I use for all dcollections containers.

 Yes, I could introduce it like this:

 struct range(inout U) if(is(U == T))
 {
    size_t length;
    U *ptr;
 }

 but it feels unnecessary.  I also find the usage for this 
 solution clumsy.


Why would you need to do it ? Why not simply do :

class Container(T) {
     struct range {
         size_t length;
         T* ptr;
     }
}
Jun 12 2013
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 12 Jun 2013 22:54:19 -0400, deadalnix <deadalnix gmail.com> wrote:


 On Wednesday, 12 June 2013 at 19:00:28 UTC, Steven Schveighoffer wrote:

 Yes, I could introduce it like this:

 struct range(inout U) if(is(U == T))
 {
    size_t length;
    U *ptr;
 }

 but it feels unnecessary.  I also find the usage for this solution  
 clumsy.


 Why would you need to do it ? Why not simply do :

 class Container(T) {
      struct range {
          size_t length;
          T* ptr;
      }
 }


if, for instance, I want to accept a container and promise not to modify  
the elements, I would have:

void foo(const Container!int cont);

OK, so, in order to access a range of elements from the container, the  
container would have some kind of function, like:

range findAll(T elem);

How to mark up this function so it's callable on a const Container?

For C++, their solution (at least for C++03, I haven't checked how this  
works for C++11) is to simply define iterator and const_iterator  
separately, and then each function is duplicated, one that returns  
iterator and one that is const and returns const_iterator.

But I don't like that :)  I want to use inout to avoid duplication.  I  
*also* want to have a function like this:

void processRange(R)(R r) if(isInputRange!R)

And mark up processRange so *it* states that it won't modify the data.   
Then I can do:

processRange(cont.findAll(1));

on a mutable C named cont.

Basically, I'm spoiled by how well D slices work :)  I want the same power.

-Steve
Jun 13 2013