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 unable to produce arbitrary witness element from set of nats in custom datatype #4188

Closed
efl9013 opened this issue Jun 15, 2023 · 1 comment · Fixed by #4190
Closed
Labels
kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label

Comments

@efl9013
Copy link

efl9013 commented Jun 15, 2023

Dafny version

4.1.0.0

Code to produce this issue

newtype Int = nat
datatype IntWrapper = Wrap(s: set<Int>)

method m(x: IntWrapper) {
  var iter := x.s;
  while iter != {}
    decreases |iter|
  {
    var i: Int :| i in iter;
    iter := iter - {i};
  }
}

Command to run and resulting output

VSCode verifier shows the following error message: 
cannot establish the existence of LHS values that satisfy the such-that predicate

What happened?

The current code fails at the line var i: Int :| i in iter; -- Dafny cannot find an arbitrary witness from the set iter of type set<nat>. However, if I change the newtype definition from newtype Int = nat to newtype Int = int, verification succeeds.

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

Mac

@efl9013 efl9013 added the kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label label Jun 15, 2023
@fabiomadge
Copy link
Collaborator

The bug is in the generation of the axioms for newtypes. Until we can fix it, consider using newtype Int = n: nat | true
, or type Int = nat.

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
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants