堆上的 Dafny 迭代器无法确保 Valid()

Question

我有一个 class，它在堆上分配一个迭代器并在该迭代器上调用 MoveNext()。我想证明如果 MoveNext() returns true, Valid() 对迭代器成立。

iterator Iter()
{}

class MyClass
{
    var iter : Iter;

    constructor ()
    {
        iter := new Iter();
    }
    method next() returns (more : bool)
    requires iter.Valid();
    modifies iter, iter._new, iter._modifies;
    {
        more := iter.MoveNext();
        // This assertion fails:
        assert more ==> iter.Valid();
    }
}

我看了一下/rprint的输出，方法MoveNext()包含ensures more ==> this.Valid()，这似乎暗示了我想要的断言。如果我将 iter 更改为在方法 next() 中本地分配，那么 Dafny 会验证断言。

Answer 1

问题是 iter._new 和 iter._modifies 中的内容一无所知。如果 this 在其中一个集合中，那么 this.iter 可能在调用 MoveNext() 期间发生了变化。

next() 的正文证实了我刚才所说的：

var i := iter;
more := iter.MoveNext();
assert i == iter;  // this assertion fails
assert more ==> iter.Valid();

因此，在假设 more 下，Valid() 仍然持有迭代器，但迭代器可能不再被 iter 引用：

more := iter.MoveNext();
assert more ==> old(iter).Valid();  // this holds

可能你想解决这个问题的方法是在next()中添加一个前提条件：

method next() returns (more : bool)
  requires iter.Valid()
  requires this !in iter._new + iter._modifies  // add this precondition
  modifies iter, iter._new, iter._modifies
{
  more := iter.MoveNext();
  assert more ==> iter.Valid();  // this now verifies
}

鲁斯坦

堆上的 Dafny 迭代器无法确保 Valid()

Dafny iterator on heap fails to ensure Valid()

dafny