Dafny 前提条件 0 <= size < capacity 可能不成立

Question

我是 Dafny 的新手，我想弄清楚为什么这不起作用。我想要做的是在我的数组中分别插入 2 个值，priorities，values。我有以下代码：

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);
}

但是当我尝试在 Main 中测试我的方法 insertValues 时，它说

call may violate context's modifies clause
A precondition for this call might not hold.

前提是0 <= size < capacity。提前谢谢你。

Answer 1

问题在于 Dafny 单独分析每个方法，仅使用其他方法的规范。有关详细信息，请参阅 Dafny FAQ。

您需要添加更多后置条件以保证某些内容不会被 insertValues 更改，您还需要向构造函数添加更多后置条件以便调用者了解初始状态。下面是验证的版本：

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);
}

Dafny 前提条件 0 <= size < capacity 可能不成立

Dafny precondition 0 <= size < capacity might not hold

arrays

insert

preconditions

dafny