dafny сбой предварительного условия

  • Я пытаюсь запустить проверенную версию BFS (от здесь)
  • Мой входной график в полном порядке, но по какой-то причине он не проходит предварительную проверку.
  • Вот постоянная ссылка
  • И для полноты вот определение графика + условия достоверности
class Graph
{
    var adjList : seq<seq<int>>;
    constructor (adjListInput : seq<seq<int>>)
    {
        adjList := adjListInput;
    }
}
function ValidGraph(G : Graph) : bool
    reads G
{
    (forall u :: 0 <= u < |G.adjList| ==> forall v   :: 0 <= v <     |G.adjList[u]| ==> 0 <= G.adjList[u][v] < |G.adjList|) &&
    (forall u :: 0 <= u < |G.adjList| ==> forall v,w :: 0 <= v < w < |G.adjList[u]| ==> G.adjList[u][v] != G.adjList[u][w])
}
method main()
{
    var G : Graph := new Graph([[1,2],[0,2],[0,1]]);
    assert (ValidGraph(G));
}
  • Дафни отвечает Error: assertion violation

person OrenIshShalom    schedule 05.08.2020    source источник


Ответы (1)


Вам просто нужно добавить ensures adjList == adjListInput в конструктор. Поскольку Dafny рассматривает конструктор в основном как метод и поскольку Dafny анализирует каждый метод отдельно, когда Dafny анализирует main, он использует только спецификацию конструктора, а не тело конструктора. Таким образом, причина неудачи утверждения заключалась в том, что с точки зрения main конструктор устанавливал поле adjList в произвольное значение, которое не обязательно соответствовало его аргументу.

person James Wilcox    schedule 05.08.2020