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

Incorrect handling of split quantifier expressions in substitution of binding guards #2748

Closed
jtristan opened this issue Sep 15, 2022 · 1 comment · Fixed by #2968
Closed
Labels
kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: verifier Translation from Dafny to Boogie (translator)

Comments

@jtristan
Copy link
Contributor

Reproduction:

function method f(x: int): int { 10 - x * x }

function method BindingGuardTest(): int {
  var x: nat := 1;
  assert true by {
    if i :| 0 <= i < 10 && (f(i) == f(i+1) || f(i) == f(i+2)) {
    }
  }
  2
}

Error:
Unhandled exception. System.AggregateException: One or more errors occurred. (Unable to cast object of type 'Microsoft.Dafny.BinaryExpr' to type 'Microsoft.Dafny.ComprehensionExpr'.) ---> System.InvalidCastException: Unable to cast object of type 'Microsoft.Dafny.BinaryExpr' to type 'Microsoft.Dafny.ComprehensionExpr'. at Microsoft.Dafny.Substituter.SubstituteComprehensionExpr(ComprehensionExpr expr, Boolean forceSubstituteOfBoundVars) in /Users/trjohnb/Code/dafny/Source/Dafny/Substituter.cs:line 920 at Microsoft.Dafny.Substituter.SubstStmt(Statement stmt) in /Users/trjohnb/Code/dafny/Source/Dafny/Substituter.cs:line 683

@jtristan jtristan added kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label part: verifier Translation from Dafny to Boogie (translator) labels Sep 15, 2022
@cpitclaudel
Copy link
Member

Adding a copy of the comment I wrote accompanying the report of this issue in #2745 in relation to the implementation of Substitute:

Substitute(q.SplitQuantifierExpression); was always wrong: it takes a quantifier and returns a conjunction or disjunction of quantifiers, so when applied to the BindingGuard of an If it replaces an ExistsExpr with a BinaryExpr, which confuses later parts of the code.

@robin-aws robin-aws changed the title Incorrect handling of slit quantifier expressions in substitution of binding guards Incorrect handling of split quantifier expressions in substitution of binding guards Sep 15, 2022
MikaelMayer added a commit that referenced this issue Nov 1, 2022
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.

2 participants