You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Dafny链表指定位置插入节点验证报错,求排查方案

链表队列指定位置插入的验证困境

我参考Rustan Leino的论文完成了链表队列的验证工作,现尝试实现更通用的队列插入功能——在指定位置插入节点而非仅追加。参考资料编写代码后,最终断言报错,无法证明next in footprint与next.valid()。我怀疑valid谓词定义存在问题,同时也不清楚如何合理推导contents的更新逻辑,恳请提供帮助。

class Node {
    var data: int
    var next: Node?
    
    ghost var footprint: set<object>
    ghost var contents: seq<int>
    
    ghost predicate valid()
        reads this, footprint
    {
        this in footprint &&
        (next != null ==> next in footprint &&
            next.footprint <= footprint &&
            this !in next.footprint &&
            next.valid()) &&
        (next == null ==> |contents| == 0 &&
            next != null ==> next.contents == contents[1..])
    }
    
    constructor()
        modifies this
        ensures valid() && fresh(footprint - {this})
        ensures next == null
        ensures |contents| == 0
    {
        next := null;
        contents := [];
        footprint := {this}
    }
    
    method enqueueMid(d: int, pos: int)
        requires valid()
        requires 0 <= pos <= |contents|
        modifies footprint
        ensures valid() && fresh(footprint - old(footprint))
    {
        var i: int := 0;
        var curr := this;
        
        while(i < pos && curr.next != null)
            invariant curr != null
            invariant curr != null ==> curr.valid()
            decreases if curr != null then curr.footprint else {}
        {
            i := i + 1;
            curr := curr.next;
        }
        
        var n := new Node();
        n.data := d;
        
        if(curr == null) {
            curr := n;
            contents := contents + [d]; // if current is null then we have reached the end of the list!
        } else {
            n.next := curr.next;
            n.footprint := curr.footprint - {curr}; // acyclicity!
            curr.footprint := curr.footprint + n.footprint;
            curr.next := n;
            contents := contents[ .. pos] + [d] + contents[pos ..];
        }
        
        footprint := footprint + n.footprint;
        assert(valid()); // error: could not prove: next in footprint. could not prove: next.valid()
    }
}

内容的提问来源于stack exchange,提问作者Drona Nagarajan

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.07.01 08:32:13