www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Constness and delegates

reply Mafi <mafi example.org> writes:
Regarding the work and comments on a pull request about delegate 
constness (https://github.com/dlang/dmd/pull/10644) I think there 
is some things we need to discuss.

I think the only sane way to analyze the soundness of delegates 
is to equate:

R delegate(P) qualifier f;

with:

interface I { R f(P) qualifier; }
I f;

Therefore given some class:

class C { R f(P) const; }
C c;

The delegate &c.f is of type 'R f(P) const'! The const qualifier 
does *not* apply to the this-Pointer of the delegate but to the 
contract of the invocation. Therefore the qualifier should be 
handled in a contravariant manner (and not covariant) because it 
describes the implicit this-Parameter of the referenced method 
and not the stored this-Pointer. The const-ness of the 
this-Pointer is the one "outside" the delegate.

qualifer1( R delegate(P) qualifier2 ) f;

Is always a well-formed type / variable. But f can only be called 
iff qualifier1 is implicitly convertible to qualifier2. This 
solves the soundness of delegates in const classes  and structs:

auto s = S(3);

struct S {
   int x = 0;
   void delegate() f;

   this(int x) { this.x = x; this.f = &this.incX; }
   void incX() { x++; }
   void const_method() const { f(); } // HERE
}

The line marked HERE compiles currently but f (in this const 
context) is of type 'const void delegate()' and therefore cannot 
be invoked (because const does not convert to mutable). If you 
change the type of f to "void delegate() const" it can be invoked 
but "incX" cannot be assigned to it! Soundness recovered. Const 
references cannot change any (implicit) state and immutable 
objects cannot observably change at all.

So in general:

struct S { void f() qualifier2; }
qualifier1 S s;
auto f = &s.f;

Is of type qualifier1(void delegate() qualifier2). Note the 
additional qualifier1 around the type. It (and not qualifier2) 
makes sure we respect the constness of the instance.

So what about implicit conversions? Well as always T -> const(T) 
<- immutable(T). Additionally qualifer(R delegate(P) const) -> 
qualifier(R delegate(P)), that is, we drop the const! This is 
because we loose power, the delegate cannot be invoked in const 
contexts anymore. This makes simple 'R delegate(P)' the goto-type 
for callbacks, as is probably the case anyways in most D code. Of 
course the inverse cannot be allowed, otherwise we lose the 
soundness again.

Additionally qualifier(R delegate(P) const) -> qualifier(R 
delegate(P) immtuble). This way immutable R delegate(P) immutable 
can be initialized from a delegate to const method on an 
immutable object.

Inline delegates that want to be const (either explicitely or 
maybe implicitely(?)) have to treat every referenced stack 
variable as const, like going through a const this-Pointer, which 
is actually what happens anyways.

I am not sure exactly how to treat inout. And I don't know in 
what state shared is in general. So what do you think? Does this 
sound reasonable? Please discuss.
Jan 09 2020
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10.01.20 00:11, Mafi wrote:

 Regarding the work and comments on a pull request about delegate 
 constness (https://github.com/dlang/dmd/pull/10644) I think there is 
 some things we need to discuss.
 
 I think the only sane way to analyze the soundness of delegates is to 
 equate:
 
 R delegate(P) qualifier f;
 
 with:
 
 interface I { R f(P) qualifier; }
 I f;
 ...


No, this is not exactly the right way to think about this. A delegate is 
not an interface, because it *includes* an _opaque_ context pointer. The 
qualifier on a delegate qualifies _both_ the function and the context 
pointer and the reason why qualifiers can be dropped anyway is that 
`qualified(void*)` can implicitly convert to `void*` (even though DMD 
does not know it yet) and the delegate maintains an invariant that says 
that the function pointer and the context pointer are compatible.


 Therefore given some class:
 
 class C { R f(P) const; }
 C c;
 
 The delegate &c.f is of type 'R f(P) const'! The const qualifier does 
 *not* apply to the this-Pointer of the delegate but to the contract of 
 the invocation.


This conclusion is however correct.


 Therefore the qualifier should be handled in a 
 contravariant manner (and not covariant) because it describes the 
 implicit this-Parameter of the referenced method and not the stored 
 this-Pointer. The const-ness of the this-Pointer is the one "outside" 
 the delegate.
 ...


Yes, exactly.


 qualifer1( R delegate(P) qualifier2 ) f;
 
 Is always a well-formed type / variable. But f can only be called iff 
 qualifier1 is implicitly convertible to qualifier2. This solves the 
 soundness of delegates in const classes  and structs:
 
 auto s = S(3);
 
 struct S {
    int x = 0;
    void delegate() f;
 
    this(int x) { this.x = x; this.f = &this.incX; }
    void incX() { x++; }
    void const_method() const { f(); } // HERE
 }
 
 The line marked HERE compiles currently but f (in this const context) is 
 of type 'const void delegate()' and therefore cannot be invoked (because 
 const does not convert to mutable). If you change the type of f to "void 
 delegate() const" it can be invoked but "incX" cannot be assigned to it! 
 Soundness recovered. Const references cannot change any (implicit) state 
 and immutable objects cannot observably change at all.
 ...


Yes. Also see: https://issues.dlang.org/show_bug.cgi?id=9149#c11
(Where I reached the same conclusion.)


 So in general:
 
 struct S { void f() qualifier2; }
 qualifier1 S s;
 auto f = &s.f;
 
 Is of type qualifier1(void delegate() qualifier2). Note the additional 
 qualifier1 around the type. It (and not qualifier2) makes sure we 
 respect the constness of the instance.
 ...


No. The type should be `void delegate() qualifier1 qualifier2`, given 
that `f` can actually be called on `s`. (And otherwise the expression 
should not compile, there is no reason to allow constructing a delegate 
that will never be able to be called.)


 So what about implicit conversions? Well as always T -> const(T) <- 
 immutable(T). Additionally qualifer(R delegate(P) const) -> qualifier(R 
 delegate(P)), that is, we drop the const! This is because we loose 
 power, the delegate cannot be invoked in const contexts anymore. This 
 makes simple 'R delegate(P)' the goto-type for callbacks, as is probably 
 the case anyways in most D code. Of course the inverse cannot be 
 allowed, otherwise we lose the soundness again.
 ...


Yes. And it's not only `const`. You can lose *all* qualifiers.


 Additionally qualifier(R delegate(P) const) -> qualifier(R delegate(P) 
 immutable). This way immutable R delegate(P) immutable can be initialized 
 from a delegate to const method on an immutable object.
 ...


No, this would break the type system. An `R delegate(immutable(P))pure 
immutable` can be implicitly memoized, but the same is not true for `R 
delegate(immutable(P))pure const`, so there is no such subtyping 
relationship.

It is however true that `&c.f` should have an immutable delegate type if 
`c` is immutable and `f` is a `const` method, consistent with what I 
stated above.


 Inline delegates that want to be const (either explicitely or maybe 
 implicitely(?)) have to treat every referenced stack variable as const, 
 like going through a const this-Pointer, which is actually what happens 
 anyways.
 
 I am not sure exactly how to treat inout. And I don't know in what state 
 shared is in general. So what do you think? Does this sound reasonable? 
 Please discuss.


Some test cases:

This should compile:

void main(){
     immutable(void*) a;
     void* b=a; // this is rejected incorrectly
     // TODO: add other qualifier combinations
}

This should compile too:

void main(){
     int delegate()const dgc;
     int delegate() dgc2=dgc; // this is correctly accepted
     int delegate()immutable dgi;
     int delegate() dgi2=dgi; // this is rejected incorrectly
     int delegate() dgi3=()=>dgi(); // ugly workaround
     int delegate()shared dgs;
     int delegate() dgs2=dgs; // this is rejected incorrectly
     int delegate() dgs3=()=>dgs(); // ugly workaround
     // TODO: add all other qualifier combinations
}


Exhaustive tests for checks on nested function contexts:

void fun(inout(int)*){
     int* x;
     const(int*) cx;
     immutable(int*) ix;
     shared(int*) sx;
     shared(const(int*)) scx;
     inout(int*) wx;
     shared(inout(int*)) swx;
     const(inout(int*)) cwx;
     shared(const(inout(int*))) scwx;
     void foo(){
         int* x=x;
         const(int)* cx=cx; // ok
         immutable(int)* ix=ix; // ok
         shared(int)* sx=sx; // ok
         shared(const(int*)) scx=scx; // ok
         inout(int)* wx=wx; // ok
         shared(inout(int))* swx=swx; // ok
         const(inout(int))* cwx=cwx; // ok
         shared(const(inout(int)))* scwx=scwx; // ok
     }
     void fooc()const{
         int* x=x; // currently ok, shouldn't compile
         const(int)* x2=x; // ok
         const(int)* cx=cx; // ok
         immutable(int)* ix=ix; // ok
         shared(int)* sx=sx; // currently ok, shouldn't compile
         const(shared(int))* sx2=sx; // ok
         shared(const(int*)) scx=scx; // ok
         inout(int)* wx=wx; // currently ok, shouldn't compile
         const(inout(int))* wx2=wx; // ok
         shared(inout(int))* swx=swx; // currently ok, shouldn't compile
         shared(const(inout(int)))* swx2=swx; // ok
         const(inout(int))* cwx=cwx; // ok
         shared(const(inout(int)))* scwx=scwx; // ok
     }
     void fooi()immutable{
         //int* x=x; // error, correct
         //const(int)* cx=cx; // error, correct
         immutable(int)* ix=ix; // ok
         //shared(int)* sx=sx; // error, correct
         //shared(const(int*)) scx=scx; // error, correct
         //inout(int)* wx=wx; // error, correct
         //shared(inout(int))* swx=swx; // error, correct
         //const(inout(int))* cwx=cwx; // error, correct
         //shared(const(inout(int)))* scwx=scwx; // error, correct
     }
     void foos()shared{
         //int* x=x; // error, correct
         //const(int)* cx=cx; // error, correct
         immutable(int)* ix=ix; // ok
         shared(int)* sx=sx; // ok
         shared(const(int*)) scx=scx; // ok
         //inout(int)* wx=wx; // error, correct
         //shared(inout(int))* swx=swx; // currently error, should work
         //const(inout(int))* cwx=cwx; // error, correct
         //shared(const(inout(int)))* scwx=scwx; // currently error, 
should work
     }
     void foosc()shared const{
         //int* x=x; // error, correct
         //const(int)* cx=cx; // error, correct
         immutable(int)* ix=ix; // ok
         //shared(int)* sx=sx; // error, correct
         //const(shared(int))* sx2=sx; // currently error, should work
         shared(const(int*)) scx=scx; // ok
         //inout(int)* wx=wx; // error, correct
         //const(inout(int))* wx2=wx; // currently error, should work
         //shared(inout(int))* swx=swx; // error, correct
         //const(shared(inout(int)))* swx2=swx; // currently error, 
should work
         //const(inout(int))* cwx=cwx; // error, correct
         //shared(const(inout(int)))* scwx=scwx; // currently error, 
should work
     }
     void foow()inout{
         int* x=x; // currently ok, shouldn't compile
         immutable(int)* ix=ix; // ok
         shared(int)* sx=sx; // currently ok, shouldn't compile
         inout(int)* wx=wx; // ok
         shared(inout(int))* swx=swx; // ok
         const(inout(int))* cwx=cwx; // ok
         shared(const(inout(int)))* scwx=scwx; // ok
     }
     void foosw()shared inout{
         //int* x=x; // error, correct
         immutable(int)* ix=ix; // ok
         //shared(int)* sx=sx; // error, correct
         //inout(int)* wx=wx; // error, correct
         shared(inout(int))* swx=swx; // ok
         //const(inout(int))* cwx=cwx; // error, correct
         shared(const(inout(int)))* scwx=scwx; // ok
     }
     void fooscw()shared const inout{
         //int* x=x; // error, correct
         immutable(int)* ix=ix; // ok
         //shared(int)* sx=sx; // error, correct
         //inout(int)* wx=wx; // error, correct
         //shared(inout(int))* swx=swx; // error, correct
         //const(shared(inout(int)))* swx2=swx; // currently error, 
should compile
         //const(inout(int))* cwx=cwx; // error, correct
         shared(const(inout(int)))* scwx=scwx; // ok
     }
}

void fun(inout(int)*){
     void bar(){}
     void barc()const{}
     void bari()immutable{}
     void bars()shared{}
     void barsc()shared const{}
     void barw()inout{}
     void barsw()shared inout{}
     void barcw()const inout{}
     void barscw()shared const inout{}
     void foo(){
         bar(); // ok
         barc(); // ok
         bari(); // ok
         bars(); // ok
         barsc(); // ok
         barsw(); // ok
         barcw(); // ok
         barscw(); // ok
     }
     void fooc()const{
         bar(); // currently ok, shouldn't compile
         barc(); // ok
         bari(); // ok
         bars(); // currently ok, shouldn't compile
         barsc(); // ok
         barsw(); // currently ok, shouldn't compile
         barcw(); // ok
         barscw(); // ok
     }
     void fooi()immutable{
         bar(); // currently ok, shouldn't compile
         barc(); // currently ok, shouldn't compile
         bari(); // ok
         bars(); // currently ok, shouldn't compile
         barsc(); // currently ok, shouldn't compile
         barsw(); // currently ok, shouldn't compile
         barcw(); // currently ok, shouldn't compile
         barscw(); // currently ok, shouldn't compile
     }
     void foos()shared{
         bar(); // currently ok, shouldn't compile
         barc(); // currently ok, shouldn't compile
         bari(); // ok
         bars(); // ok
         barsc(); // ok
         barsw(); // ok
         barcw(); // currently ok, shouldn't compile
         barscw(); // ok
     }
     void foosc()shared const{
         bar(); // currently ok, shouldn't compile
         barc(); // currently ok, shouldn't compile
         bari(); // ok
         bars(); // currently ok, shouldn't compile
         barsc(); // ok
         barsw(); // currently ok, shouldn't compile
         barcw(); // currently ok, shouldn't compile
         barscw(); // ok
     }
     void foow()inout{
         bar(); // currently ok, shouldn't compile
         barc(); // currently ok, shouldn't compile
         bari(); // ok
         bars(); // currently ok, shouldn't compile
         barsc(); // currently ok, shouldn't compile
         barsw(); // ok
         barcw(); // ok
         barscw(); // ok
     }
     void foosw()shared inout{
         bar(); // currently ok, shouldn't compile
         barc(); // currently ok, shouldn't compile
         bari(); // ok
         bars(); // currently ok, shouldn't compile
         barsc(); // currently ok, shouldn't compile
         barsw(); // ok
         barcw(); // currently ok, shouldn't compile
         barscw(); // ok
     }
     void fooscw()shared const inout{
         bar(); // currently ok, shouldn't compile
         barc(); // currently ok, shouldn't compile
         bari(); // ok
         bars(); // currently ok, shouldn't compile
         barsc(); // currently ok, shouldn't compile
         barsw(); // currently ok, shouldn't compile
         barcw(); // currently ok, shouldn't compile
         barscw(); // ok
     }
}
Jan 09 2020
next sibling parent reply Mafi <mafi example.org> writes:
On Friday, 10 January 2020 at 02:50:16 UTC, Timon Gehr wrote:

 On 10.01.20 00:11, Mafi wrote:

 Regarding the work and comments on a pull request about 
 delegate constness (https://github.com/dlang/dmd/pull/10644) I 
 think there is some things we need to discuss.
 
 I think the only sane way to analyze the soundness of 
 delegates is to equate:
 
 R delegate(P) qualifier f;
 
 with:
 
 interface I { R f(P) qualifier; }
 I f;
 ...


 No, this is not exactly the right way to think about this. A 
 delegate is not an interface, because it *includes* an _opaque_ 
 context pointer. The qualifier on a delegate qualifies _both_ 
 the function and the context pointer and the reason why 
 qualifiers can be dropped anyway is that `qualified(void*)` can 
 implicitly convert to `void*` (even though DMD does not know it 
 yet) and the delegate maintains an invariant that says that the 
 function pointer and the context pointer are compatible.


I see. So the additional opacity is that an interface type I, 
that is qualified mutable, could be upcast to some class C and 
you would expect C to mutable as well. Therefore you may not 
convert an interface consisting of only const methods from const 
to mutable. But a delegate is different, it can never be 
inspected. Correct? That's interesting!


 ...

 Therefore the qualifier should be handled in a contravariant 
 manner (and not covariant) because it describes the implicit 
 this-Parameter of the referenced method and not the stored 
 this-Pointer. The const-ness of the this-Pointer is the one 
 "outside" the delegate.
 ...


 Yes, exactly.

 ...

 Yes. And it's not only `const`. You can lose *all* qualifiers.


So the qualifier on the right of the delegate is not actually 
contravariant in the type-way but rather the inside-out direction 
of transitive constness (mutable data can reference const data 
can reference immutable data). Thus delegate() immutable -> 
delegate() const -> delegate(). This is also a nice symmetry 
between constness and other qualifiers.

Additionally because of the simple opaque nature of delegates 
'qualifierA R delegate(P) qualifer1' should be implicitely 
convertible to 'qualifierB R delegate(P) qualifier1' as long as 
qualifierA and qualifierB are "weaker" than qualifier1. That is 
mutable/const/immtutable R delegate() immutable all convert to 
one another. And mutable/const R delegate(P) const convert 
between each other.

Which I think gives this graph (qualifier1/2 => qualifier1 R 
delegate(P) qualifier2:

m/m <- m/c <- m/i
  |      ^      ^
  v      v      v
c/m <- c/c <- c/i
  ^      ^      ^
  |      |      v
i/m <- i/c <- i/i

Where a delegate is callable iff 'qualifier1 qualifier2' is 
convertible to 'qualifier2'. Therefore only i/m and c/m are not 
callable (and they don't convert to a callable one). Is this 
correct?
Jan 10 2020
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10.01.20 14:54, Mafi wrote:

 On Friday, 10 January 2020 at 02:50:16 UTC, Timon Gehr wrote:

 On 10.01.20 00:11, Mafi wrote:

 Regarding the work and comments on a pull request about delegate 
 constness (https://github.com/dlang/dmd/pull/10644) I think there is 
 some things we need to discuss.

 I think the only sane way to analyze the soundness of delegates is to 
 equate:

 R delegate(P) qualifier f;

 with:

 interface I { R f(P) qualifier; }
 I f;
 ...


 No, this is not exactly the right way to think about this. A delegate 
 is not an interface, because it *includes* an _opaque_ context 
 pointer. The qualifier on a delegate qualifies _both_ the function and 
 the context pointer and the reason why qualifiers can be dropped 
 anyway is that `qualified(void*)` can implicitly convert to `void*` 
 (even though DMD does not know it yet) and the delegate maintains an 
 invariant that says that the function pointer and the context pointer 
 are compatible.


 
 I see. So the additional opacity is that an interface type I, that is 
 qualified mutable, could be upcast to some class C and you would expect 
 C to mutable as well. Therefore you may not convert an interface 
 consisting of only const methods from const to mutable. But a delegate 
 is different, it can never be inspected. Correct? That's interesting!
 ...


Yes. :)


 ...

 Therefore the qualifier should be handled in a contravariant manner 
 (and not covariant) because it describes the implicit this-Parameter 
 of the referenced method and not the stored this-Pointer. The 
 const-ness of the this-Pointer is the one "outside" the delegate.
 ...


 Yes, exactly.

 ...

 Yes. And it's not only `const`. You can lose *all* qualifiers.


 
 So the qualifier on the right of the delegate is not actually 
 contravariant in the type-way but rather the inside-out direction of 
 transitive constness (mutable data can reference const data can 
 reference immutable data). Thus delegate() immutable -> delegate() const 
 -> delegate(). This is also a nice symmetry between constness and other 
 qualifiers.
 
 Additionally because of the simple opaque nature of delegates 
 'qualifierA R delegate(P) qualifer1' should be implicitely convertible 
 to 'qualifierB R delegate(P) qualifier1' as long as qualifierA and 
 qualifierB are "weaker" than qualifier1. That is 
 mutable/const/immtutable R delegate() immutable all convert to one 
 another. And mutable/const R delegate(P) const convert between each other.
 
 Which I think gives this graph (qualifier1/2 => qualifier1 R delegate(P) 
 qualifier2:
 
 m/m <- m/c <- m/i
   |      ^      ^
   v      v      v
 c/m <- c/c <- c/i
   ^      ^      ^
   |      |      v
 i/m <- i/c <- i/i
 ...


Yes.


 Where a delegate is callable iff 'qualifier1 qualifier2' is convertible 
 to 'qualifier2'. Therefore only i/m and c/m are not callable (and they 
 don't convert to a callable one). Is this correct?
 
 


Yes. I think the best way to think about it is that qualifier1 applies 
to the context pointer and the function pointer, while qualifier2 
applies to the context pointer and the implicit context parameter that 
the function pointer takes as an argument. The qualifier on the context 
(qualifier1 qualifier2) always has to be at least as strong as what the 
function pointer accepts (qualifier2) if the delegate is to be callable, 
while the qualifier on the function pointer itself does not matter (as 
the code it points to is immutable).

Conceptually, the type of a closure mapping A to B can be described as 
an existential type ∃C. C×(A×C→B). All type checking rules basically 
follow from this, for example:

∃C. immutable(C)×(A×immutable(C)→B)
=
∃C. const(immutable(C))×(A×const(immutable(C))→B)
⊆
∃C'. const(C')×(A×const(C')→B)
⊆
∃C''. C''×(A×C''→B)

(Where C' is substituted for immutable(C), and C'' for const(C).)

The implementation using void* is an unsafe approximation made necessary 
by D's type system not being powerful enough, but any code that respects 
this typing of delegates can be  trusted.
Jan 10 2020
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10.01.20 22:25, Timon Gehr wrote:

 and C'' for const(C)


(For const(C'), actually.)
Jan 10 2020
prev sibling parent Mafi <mafi example.org> writes:
On Friday, 10 January 2020 at 21:25:50 UTC, Timon Gehr wrote:

...

 Conceptually, the type of a closure mapping A to B can be 
 described as an existential type ∃C. C×(A×C→B). All type 
 checking rules basically follow from this, for example:

 ∃C. immutable(C)×(A×immutable(C)→B)
 =
 ∃C. const(immutable(C))×(A×const(immutable(C))→B)
 ⊆
 ∃C'. const(C')×(A×const(C')→B)
 ⊆
 ∃C''. C''×(A×C''→B)

 (Where C' is substituted for immutable(C), and C'' for 
 const(C).)

 The implementation using void* is an unsafe approximation made 
 necessary by D's type system not being powerful enough, but any 
 code that respects this typing of delegates can be  trusted.


Thank very much for this explanation in particular! It's great to 
know that delegates can have maxmimum flexibility (especially 
'mutable delegate mutable' being the go-to type) while preserving 
soundness.
Jan 11 2020
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 1/9/2020 6:50 PM, Timon Gehr wrote:

 Some test cases:


Please turn this into a bugzilla report.
Jan 17 2020
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 1/17/2020 1:27 AM, Walter Bright wrote:

 Please turn this into a bugzilla report.


https://issues.dlang.org/show_bug.cgi?id=20517
Jan 17 2020
parent =?UTF-8?B?Q2hsb8Op?= Kekoa <rightfold+ck gmail.com> writes:
On Saturday, 18 January 2020 at 04:26:36 UTC, Walter Bright wrote:

 On 1/17/2020 1:27 AM, Walter Bright wrote:

 Please turn this into a bugzilla report.


 https://issues.dlang.org/show_bug.cgi?id=20517



The proposed solution is more thought-out and ergonomic.

https://issues.dlang.org/show_bug.cgi?id=20437
https://github.com/dlang/dmd/pull/10644
Aug 26 2020