I am new in Dafny and I try to figure out why this doesn't work. What I want to do is to insert 2 values in my arrays, priorities
, respectively values
.
I have the following code:
class Queue<V> {
var size: int;
ghost var capacity: int;
var priorities: array<int>;
var values: array<V>;
predicate Valid()
reads this
{
0 <= size <= capacity &&
capacity == priorities.Length &&
capacity == values.Length
}
constructor(aCapacity: int, defaultValue: V)
requires aCapacity >= 0
ensures Valid()
{
size := 0;
values := new V[aCapacity](i => defaultValue);
priorities := new int[aCapacity];
capacity := aCapacity;
}
method insertValues(priority: int, value: V)
modifies this.values, this.priorities, this
requires Valid()
requires 0 <= size < capacity // here is the problem
ensures Valid()
ensures capacity == values.Length && capacity == priorities.Length
{
this.values[size] := value;
this.priorities[size] := priority;
size := size + 1;
}
}
method Main() {
var queue := new Queue<int>(10, 0);
queue.insertValues(1, 10);
queue.insertValues(2, 11);
}
But when I try to tests my method insertValues
in Main it says that
call may violate context's modifies clause
A precondition for this call might not hold.
and the precondition is 0 <= size < capacity
. Thank you in advance.
The issue is that Dafny analyzes each method in isolation, using only the specifications of the other methods. See the Dafny FAQ for more information.
You need to add more postconditions to guarantee that certain things aren't changed by insertValues
, and you need to also add more postconditions to the constructor so that callers know the initial state. Here is a version that verifies:
class Queue<V> {
var size: int;
ghost var capacity: int;
var priorities: array<int>;
var values: array<V>;
predicate Valid()
reads this
{
0 <= size <= capacity &&
capacity == priorities.Length &&
capacity == values.Length
}
constructor(aCapacity: int, defaultValue: V)
requires aCapacity >= 0
ensures Valid()
ensures fresh(priorities) && fresh(values)
ensures size == 0 && capacity == aCapacity
{
size := 0;
values := new V[aCapacity](i => defaultValue);
priorities := new int[aCapacity];
capacity := aCapacity;
}
method insertValues(priority: int, value: V)
modifies this.values, this.priorities, this
requires Valid()
requires 0 <= size < capacity // here is the problem
ensures Valid()
ensures capacity == old(capacity) && size == old(size) + 1 && values == old(values) && priorities == old(priorities)
{
this.values[size] := value;
this.priorities[size] := priority;
size := size + 1;
}
}
method Main() {
var queue := new Queue<int>(10, 0);
queue.insertValues(1, 10);
queue.insertValues(2, 11);
}