Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Missing checks for refinement of !new and 00 #2064

Closed
cpitclaudel opened this issue Apr 25, 2022 · 1 comment · Fixed by #5146
Closed

Missing checks for refinement of !new and 00 #2064

cpitclaudel opened this issue Apr 25, 2022 · 1 comment · Fixed by #5146
Assignees
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 introduced: pre-2012 kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label priority: next Will consider working on this after in progress work is done

Comments

@cpitclaudel
Copy link
Member

Dafny accepts the following program:

abstract module Parent {
  type T(!new)

  twostate lemma L(new t: T)
    ensures old(allocated(t)) // Uses the !new annotation on T
  {}
}

module Child refines Parent {
  class T {
    var a: int
    constructor(a: int) ensures this.a == a { this.a := a; }
  }

  method boom() {
    var c := new T(0);
    assert !old(allocated(c));
    L(c);
    assert old(allocated(c));
    assert false;
  }
}

The problem is that the resolver does not check that !new annotations are preserved by refinement. (At first I thought it was a special case of #1419, but in fact it's a separate issue.)

@cpitclaudel cpitclaudel added kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label logic An inconsistency in Dafny's logic (e.g. in the Boogie prelude) labels Apr 25, 2022
@cpitclaudel cpitclaudel self-assigned this Apr 25, 2022
@cpitclaudel
Copy link
Member Author

The following is another example, this time with 00:

abstract module Parent {
  type U(00)

  lemma Mk() returns (u: U) {
    u :| true;
  }
}

module Child refines Parent {
  type False = x: int | false witness *

  // datatype U = U(f: False) // Correctly rejected

  class U { // Accepted
    var f: False
    constructor(f: False) { this.f := f; }
  }
}

method Main() ensures false {
  ghost var u: Child.U := Child.Mk();
  ghost var f: Child.False := u.f;
}

@cpitclaudel cpitclaudel changed the title Missing checks for refinement of !new Missing checks for refinement of !new and 00 Apr 26, 2022
@cpitclaudel cpitclaudel removed their assignment Jul 11, 2022
@cpitclaudel cpitclaudel added 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 and removed logic An inconsistency in Dafny's logic (e.g. in the Boogie prelude) labels Sep 2, 2022
@keyboardDrummer keyboardDrummer added the priority: next Will consider working on this after in progress work is done label Feb 21, 2024
@RustanLeino RustanLeino self-assigned this Mar 5, 2024
RustanLeino added a commit to RustanLeino/dafny that referenced this issue Mar 5, 2024
RustanLeino added a commit that referenced this issue Mar 26, 2024
…es (#5146)

If a module `M` declares an abstract type `T` with specific type
characteristics, then any module that refines `M` and replaces `T` must
make sure that the new `T` lives up to those type characteristics. Some
of those checks were missing. This PR adds them for all replacements of
`T`.

Also, previously, some of the checks that were performed were stronger
than necessary. For example, they did not allow `M.T(00)` to be refined
by a type that satisfies `(0)`. This PR makes those checks less
forceful.

Fixes #2064


<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>
# for free to join this conversation on GitHub. Already have an account? # 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 introduced: pre-2012 kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label priority: next Will consider working on this after in progress work is done
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants