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

Soundness issue: Map's range not inferred to require equality for datatype to support equality #5972

Closed
MikaelMayer opened this issue Dec 11, 2024 · 0 comments · Fixed by #5973 · May be fixed by #5948
Closed

Soundness issue: Map's range not inferred to require equality for datatype to support equality #5972

MikaelMayer opened this issue Dec 11, 2024 · 0 comments · Fixed by #5973 · May be fixed by #5948
Labels
during 3: execution of incorrect program An bug in the verifier that allows Dafny to run a program that does not correctly implement its spec kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: resolver Resolution and typechecking

Comments

@MikaelMayer
Copy link
Member

MikaelMayer commented Dec 11, 2024

Dafny version

latest-nightly

Code to produce this issue

datatype M<T, U> = M(m: map<T, U>)

method CompareAnything<A>(f: A, g: A) returns (b: bool) 
   ensures b <==> f == g
{
  var m1 := M(map[0 := f]);
  var m2 := M(map[0 := g]);
  assert m1 == m2 <==> f == g by {
    if f == g {
      assert m1 == m2;
    }
    if m1 == m2 {
      assert m1.m[0] == m2.m[0];
    }
  }
  return m1 == m2;
}

codatatype Stream = Stream(head: int, tail: Stream)
{
  static function From(i: int): Stream {
    Stream(i, From(i + 1))
  }
}

method Main() {
  var s1 := Stream.From(0);
  var s2 := Stream.From(0);
  var b := CompareAnything(s1, s2);
  if !b {
    assert false;
    print 1/0;
  }
}

Command to run and resulting output

dafny run file.dfy

What happened?

It outputs a run-time exception whereas the program verifies.
The problem is that the second argument of the map requires supporting equality for the datatype to support equality but it is not added

What type of operating system are you experiencing the problem on?

Any

@MikaelMayer MikaelMayer added kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: resolver Resolution and typechecking labels Dec 11, 2024
@MikaelMayer MikaelMayer added the during 3: execution of incorrect program An bug in the verifier that allows Dafny to run a program that does not correctly implement its spec label Dec 11, 2024
@MikaelMayer MikaelMayer changed the title Functions can be compared at compile-time, and it's troublesome Soundness issue: Map's range not inferred to require equality for datatype to support equality Dec 11, 2024
MikaelMayer added a commit that referenced this issue Dec 11, 2024
MikaelMayer added a commit that referenced this issue Dec 12, 2024
…ty (#5973)

This PR fixes #5972
I added the corresponding test.

<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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
during 3: execution of incorrect program An bug in the verifier that allows Dafny to run a program that does not correctly implement its spec kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: resolver Resolution and typechecking
Projects
None yet
1 participant