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

Assign-such-that drawing from iset/imap collection is reported as non-compilable #5034

Closed
RustanLeino opened this issue Feb 1, 2024 · 0 comments · Fixed by #5041
Closed
Assignees
Labels
kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: resolver Resolution and typechecking

Comments

@RustanLeino
Copy link
Collaborator

Dafny version

4.4.0

Code to produce this issue

method Test(u: iset<int>, w: imap<int, bool>)
  requires 3 in u && 3 in w.Keys
{
  // BOGUS: these assign-such-that statements are reported as non-compilable
  var y :| y in u && LessThanFour(y); // but an iset is enumerable, so it is compilable
  var z :| z in w && LessThanFour(z); // and an imap is enumerable, so it is compilable

  print y, z;
}

predicate LessThanFour(x: int) {
  x < 4
}

method Main() {
  var s := {3, 3, 3, 5};
  var m := map[3 := true, 5 := false];
  Test(iset x | x in s, imap x | x in m :: true);
}

Command to run and resulting output

% dafny test.dfy

Dafny program verifier finished with 2 verified, 0 errors
test.dfy(22,8): Error: this assign-such-that statement is too advanced for the current compiler; Dafny's heuristics cannot find any bound for variable 'y' (ID: c_assign_such_that_is_too_complex)

To compile an assign-such-that statement, Dafny needs to find some appropriate bounds for each variable.
However, in this case the expression is too complex for Dafny's heuristics.
test.dfy(23,8): Error: this assign-such-that statement is too advanced for the current compiler; Dafny's heuristics cannot find any bound for variable 'z' (ID: c_assign_such_that_is_too_complex)

To compile an assign-such-that statement, Dafny needs to find some appropriate bounds for each variable.
However, in this case the expression is too complex for Dafny's heuristics.

What happened?

The program should be compilable, in the same way as if u and w were a finite set and finite map, respectively. However, Dafny whines that the expressions are too advanced to be compiled.

The problem is that the CollectionBoundedPool reports the Enumerable virtue only for finite collections.

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

Mac

@RustanLeino RustanLeino added kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: resolver Resolution and typechecking labels Feb 1, 2024
@RustanLeino RustanLeino self-assigned this Feb 1, 2024
RustanLeino added a commit to RustanLeino/dafny that referenced this issue Feb 1, 2024
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: resolver Resolution and typechecking
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant