-
Notifications
You must be signed in to change notification settings - Fork 254
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
Stuck in verification #5160
Comments
@MikaelMayer could you be more verbose in your problem description? It's not clear to me what the issue is. |
Updated description. |
It seems like Dafny is telling you that you don't have sufficient reads clauses to invoke The following program is accepted: // Encoding of Boogie references in Dafny
datatype World<!A(==), !FieldValue> = World(
a_to_object: A -> object,
fields: A ~> set<FieldValue>,
reachable: FieldValue -> set<A>,
all_a: set<A>) {
ghost function AllObjects(): set<object> {
set a <- all_a :: a_to_object(a)
}
ghost predicate closed()
reads AllObjects()
requires forall a: A <- all_a :: fields.requires(a) && fields.reads(a) == {}
{
forall a: A <- all_a :: forall f <- fields(a) :: reachable(f) <= all_a
}
} |
That works indeed, but I wanted closed() to be like a Valid() predicate, and I can't refactor your requires into another predicate, do you know why? |
I see, sorry I only now understand your intent, and now I also understand why it's surprising your program didn't verify to begin with. What's the reads clause of a reads function? I'm guessing you need to define it at some level in the requires clause. You can do: // Encoding of Boogie references in Dafny
datatype World<!A(==,!new), !FieldValue> = World(
a_to_object: A -> object,
fields: A ~> set<FieldValue>,
reachable: FieldValue -> set<A>,
all_a: set<A>) {
ghost function AllObjects(): set<object> {
set a <- all_a :: a_to_object(a)
}
ghost predicate closed()
reads AllObjects()
requires forall a: A <- all_a :: && fields.reads.requires(a) && fields.reads.reads(a) == {}
{
forall a: A <- all_a ::
&& fields.reads(a) <= AllObjects()
&& fields.requires(a)
&& forall f <- fields(a) :: reachable(f) <= all_a
}
} I'm confused why moving things to the requires clause even works though. I would have thought that the WF check of the contract fails in the above case because it doesn't know anything about |
SummaryGeneral functions (that is, DetailsSecond exampleHere is a shorter version of the second example from above: ghost predicate Closed'<A>(f: A ~> int, a: A, S: set<object>)
reads S
{
&& f.reads(a) <= S // precondition violation, and insufficient reads clause to invoke function
&& f.requires(a)
&& f(a) == 5
} This function body is in error. To be allowed to even ask the question "what does First exampleHere is a shorter version of the first example from above: ghost predicate Closed<A>(f: A ~> int, a: A, S: set<object>)
reads S
{
&& f.requires(a) // insufficient reads clause to invoke function
&& f.reads(a) <= S
&& f(a) == 5
} By preceding
(The rules I applied here are described in section 5.12 Arrow types of the reference manual.) Adding a preconditionWe could add requires f.requires.reads(a) == {} to function We could try to fix this. However, such a precondition would be hard for anyone to establish. A caller would need to prove that (Section 5.12 Arrow types of the reference manual uses " The difference between the specification and bodyThe examples above put ghost predicate ClosedWithSpec<A>(f: A ~> int, a: A, S: set<object>)
requires f.requires(a) && f.reads(a) <= S
reads S
{
f(a) == 5
}
ghost predicate ClosedWithSpec'<A>(f: A ~> int, a: A)
requires f.requires(a)
reads f.reads(a)
{
f(a) == 5
} The reason for this is that these preconditions will only ever be evaluated to |
is exactly something that I had envisioned before. It gives the ability of writing heap-reading functions that do not have preconditions (if the requires is true, then the reads is empty)
Of course I'd love to add |
Dafny version
latest-nightly
Code to produce this issue
and If I reverse the reads and requires
Command to run and resulting output
What happened?
I can no longer specify anything about general function that read the heap but don't have preconditions I have to bring a tower of reads and no foundation.
What should work here is to be able to stop at
But I don't know if it's sound.
What type of operating system are you experiencing the problem on?
Windows
The text was updated successfully, but these errors were encountered: