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
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>
RustanLeino added a commit that referenced this issue Dec 17, 2024
…ypes (#5980)

This PR extends fix #5973 of issue #5972 to also handle newtypes, subset
types, and type synonyms wrapped around map and sequence types.

Fixes #5978 

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

---------

Co-authored-by: Mikael Mayer <mimayere@amazon.com>
Co-authored-by: Mikaël Mayer <MikaelMayer@users.noreply.github.com>
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
Development

Successfully merging a pull request may close this issue.

1 participant