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

Dafny reports verification error twice #2703

Closed
keyboardDrummer opened this issue Sep 7, 2022 · 3 comments · Fixed by #2972
Closed

Dafny reports verification error twice #2703

keyboardDrummer opened this issue Sep 7, 2022 · 3 comments · Fixed by #2972
Assignees
Labels
kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: verifier Translation from Dafny to Boogie (translator)

Comments

@keyboardDrummer
Copy link
Member

keyboardDrummer commented Sep 7, 2022

abstract module StillAsby {
  import A : Absy

}

abstract module Absy {
  method Foo() 
    ensures 2 / 0 == 1 {
    var x := 1;
  }
}

Reports:

abstractModuleImport.dfy(10,14): Error: possible division by zero
abstractModuleImport.dfy(10,23): Error: A postcondition might not hold on this return path.
abstractModuleImport.dfy(10,18): Related location: This is the postcondition that might not hold.
abstractModuleImport.dfy(10,14): Error: possible division by zero

Note the double "possible division by zero"

Also note that this program causes an exception in the Dafny language server:

[Trace - 3:40:41 PM] Received notification 'telemetry/event'.
Params: {
    "kind": "UnhandledException",
    "payload": "System.ArgumentException: An item with the same key has already been added. Key: ImplementationId { NamedVerificationTask = (line: 9, char: 9), Name = CheckWellFormed }\n   at System.Collections.Generic.Dictionary`2.TryInsert(TKey key, TValue value, InsertionBehavior behavior)\n   at Microsoft.Dafny.LanguageServer.Workspace.Compilation.PrepareVerificationTasksAsync(DocumentAfterResolution loaded, CancellationToken cancellationToken)\n   at Microsoft.Dafny.LanguageServer.Workspace.Compilation.TranslateAsync()"
}
@keyboardDrummer keyboardDrummer added kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: verifier Translation from Dafny to Boogie (translator) labels Sep 7, 2022
@keyboardDrummer
Copy link
Member Author

I see the verification of the wellformedness of Absy.Foo is done twice. Is that required for soundness? I have trouble overseeing the implication of the import A : Absy and whether that could effect the wellformedness of Absy.Foo. In any case, suppose import A : Absy would cause a verification issue, then the error should be shown at the import, not at the original method definition.

@cpitclaudel
Copy link
Member

Here is a variant of this same issue, which shows that it's not restricted to imports:

abstract module Absy {
  function f(): int { 0 / 0 }
}

abstract module StillAsby refines Absy {
}

This produces the following output:

test.dfy(2,22): Error: possible division by zero
  |
2 |   function f(): int { 0 / 0 }
  |                       ^^^^^

test.dfy[StillAsby](2,22): Error: possible division by zero
  |
2 | <nonexistent line>
  |                       ^


Dafny program verifier finished with 0 verified, 2 errors

For this variant, however, we did not use to print two errors until very recently; that bug was introduced in 3.7.2.

The problem in the original post:

abstract module Absy {
  function f(): int { 0 / 0 }
}

abstract module StillAsby {
  import A: Absy
}

reports two errors in every version of Dafny that can parse it.

I don't think it should: module verification is supposed to be modular, so I don't see why we're re-checking well-formedness :/

keyboardDrummer added a commit that referenced this issue Sep 9, 2022
Defensive programming. Reduces the impact of
#2703 while we work on fixing
it.

<small>By submitting this pull request, I confirm that my contribution
is made under the terms of the [MIT
license](https://github.com/dafny-lang/dafny/blob/master/LICENSE.txt).</small>
@RustanLeino
Copy link
Collaborator

I agree that there should be no need to verify this twice. I don't know how come we do.

This is how these things are generally performed: There are two cases when we make a refinement clone of a module--when you say module B refines A and when you say import X: SomeModule. The refinement cloner wraps each IToken in a RefinementToken. This signals to the verifier that the AST node was created during refinement, which implies that the original AST node is verified elsewhere.

So, perhaps what's going wrong in the report bug is that the RefinementToken is either not created or not detected. It should have been created using a call to the virtually dispatched Tok method in Cloner. Maybe the detection doesn't handle multiply-wrapped tokens correctly--perhaps it only checks tok is RefinementToken, whereas it should keep unwrapping WrappedTokens to see if any of the wrappers is a RefinementToken.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: verifier Translation from Dafny to Boogie (translator)
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants