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
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
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
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
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
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
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
parent 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