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.

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

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?

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.

On 10.01.20 22:25, Timon Gehr wrote:
> and C'' for const(C)

(For const(C'), actually.)

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.

On 1/9/2020 6:50 PM, Timon Gehr wrote:
> Some test cases:

Please turn this into a bugzilla report.

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

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

Should this report obsolete #20437 and pull request #10544?
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