Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Is it safe to use reads this to say "depends on unspecified external state"? #322

Open
samuelgruetter opened this issue Jul 17, 2019 · 3 comments
Labels
area: ffi The {:extern} attribute and otherwise interfacing with code in other languages kind: enhancement Enhancements, feature requests, etc. These are NOT bugs, but ways we can improve Dafny

Comments

@samuelgruetter
Copy link
Collaborator

class Foo {
    function Property(): int reads this
    method Modify() modifies this {}
    constructor() {}
}

method Main() {
    var f := new Foo();
    ghost var before := f.Property();
    f.Modify();
    ghost var after := f.Property();
    assert before == after; // assertion violation
}

In this example, Dafny fails to prove that before == after (and I think that's good).
However, in the future, someone might come and suggest the following reasoning:

Class Foo has no fields, so the function Property cannot read any state, so in this case, reads this should have no effect, and since Property also takes no arguments, it must be a constant value, therefore before == after holds.

They will implement this by doing something like "if class has no fields, then remove all reads this clauses from its functions", make a PR, which passes all existing tests, it will get merged, and everyone will be happy about this Dafny improvement.

However, in our project we're currently using extern classes which look very similar to the above pattern:

class {:extern} MetadataCollection {
    function {:extern} Content(): map<string, string> reads this
    method {:extern} Add(key: string, value: string) 
        modifies this
        ensures Content() == old(Content())[key := value]
    constructor {:extern} () ensures Content() == map[]
}

Assuming the person didn't think too hard about externs, the patch I described above will have the same effect as commenting out the reads this clause:

class {:extern} MetadataCollection {
    function {:extern} Content(): map<string, string> //reads this
    method {:extern} Add(key: string, value: string) 
        modifies this
        ensures Content() == old(Content())[key := value]
    constructor {:extern} () ensures Content() == map[]
}

But that's bad, because now we can prove false:

method Main() {
    var m := new MetadataCollection();
    ghost var before := m.Content();
    m.Add("testkey", "testvalue");
    ghost var after := m.Content();
    assert before == after;

    assert before["testkey" := "testvalue"] == after;
    assert before == map[];
    assert after == map[];
    assert "testkey" in after;

    assert false;
}

So my question is: Is it safe and future proof to specify extern classes like I did above?

@parno
Copy link
Collaborator

parno commented Jul 19, 2019

Perhaps you could add a test case that would fail if such an optimization were added?

@samuelgruetter
Copy link
Collaborator Author

Good idea! Will do so as soon as @RustanLeino confirms that this optimization should never be added.

@robin-aws
Copy link
Member

See #461 and #463 - I assert that the compiler should "think too hard about externs" so you don't have to. :)

@robin-aws robin-aws added kind: enhancement Enhancements, feature requests, etc. These are NOT bugs, but ways we can improve Dafny area: ffi The {:extern} attribute and otherwise interfacing with code in other languages labels Jun 23, 2020
@acioc acioc added this to the Post 3.0 milestone Aug 5, 2020
@robin-aws robin-aws removed this from the Post 3.1 milestone Sep 22, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area: ffi The {:extern} attribute and otherwise interfacing with code in other languages kind: enhancement Enhancements, feature requests, etc. These are NOT bugs, but ways we can improve Dafny
Projects
None yet
Development

No branches or pull requests

4 participants