Verifying a Dafny method that shifts a region of an array

Question

I'm using Dafny to make a delete method where you receive:

char array line
the length of the array l
a position at
the number of characters to delete p

First you delete the characters of line from at to at + p, and then you must move all the characters on the right of at + p to at.

For example, if you have [e][s][p][e][r][m][a], and at = 3, and p = 3, then the final result should be [e][s][p][a]

I'm trying to prove a postcondition that makes sense like:

ensures forall j :: (at<=j<l) ==> line[j] == old(line[j+p]);

To ensure that all chars from the right of at + p are in the new positions.

But Dafny outputs two errors:

index out of range 7 53

postcondition might not hold on this return path. 19 2

method delete(line:array<char>, l:int, at:int, p:int)
  requires line!=null;
  requires 0 <= l <= line.Length && p >= 0 && at >= 0;
  requires 0 <= at+p <= l;
  modifies line;
  ensures forall j :: (at<=j<l) ==> line[j] == old(line[j+p]) ; 
{
  var tempAt:int := at;
  var tempAt2:int := at;
  var tempPos:int := at+p;
  while(tempAt < at + p)
    invariant at<=tempAt<=at + p;
  { 
    line[tempAt] := ' ';
    tempAt := tempAt + 1;
  }

  while(tempPos < line.Length && tempAt2 < at + p)
    invariant at + p<=tempPos<=line.Length;
    invariant at<=tempAt2<=at+p;
  {
    line[tempAt2] := line[tempPos];
    tempAt2 := tempAt2 + 1; 
    line[tempPos] := ' ';
    tempPos := tempPos + 1;
  }
}

Here is the program on rise4fun

lexicalscope lexicalscope · Accepted Answer · 2016-04-14T14:04:37

I don't think it is necessary to use quantifiers to express such postconditions. They are usually better expressed by slicing the array into sequences.

When you are trying to verify a loop you need to provide a loop invariant which is strong enough to imply the postcondition when combined with the negation of the loop condition.

A good strategy for picking a loop invariant is to use the method postcondition, but with the loop index substituted for the array length.

Your loop invariant also needs to be strong enough for the induction to work. In this case, you need to say not only how the loop modifies line, but also which parts of line remain the same in each iteration.

Solution on rise4fun.

// line contains string of length l
// delete p chars starting from position at
method delete(line:array<char>, l:nat, at:nat, p:nat)
  requires line!=null
  requires l <= line.Length
  requires at+p <= l
  modifies line
  ensures line[..at] == old(line[..at])
  ensures line[at..l-p] == old(line[at+p..l])
{
  var i:nat := 0;
  while(i < l-(at+p))
    invariant i <= l-(at+p)
    invariant at+p+i >= at+i 
    invariant line[..at] == old(line[..at])
    invariant line[at..at+i] == old(line[at+p..at+p+i])
    invariant line[at+i..l] == old(line[at+i..l]) // future is untouched
  { 
    line[at+i] := line[at+p+i];
    i := i+1;
  }
}

Overwriting with spaces

If you want to overwrite the trailing part of the old string with spaces you can do this:

method delete(line:array<char>, l:nat, at:nat, p:nat)
  requires line!=null
  requires l <= line.Length
  requires at+p <= l
  modifies line
  ensures line[..at] == old(line[..at])
  ensures line[at..l-p] == old(line[at+p..l])
  ensures forall i :: l-p <= i < l ==> line[i] == ' '  
{
  var i:nat := 0;
  while(i < l-(at+p))
    invariant i <= l-(at+p)
    invariant at+p+i >= at+i 
    invariant line[..at] == old(line[..at])
    invariant line[at..at+i] == old(line[at+p..at+p+i])
    invariant line[at+i..l] == old(line[at+i..l]) // future is untouched
  { 
    line[at+i] := line[at+p+i];
    i := i+1;
  }

  var j:nat := l-p;
  while(j < l)
    invariant l-p <= j <= l
    invariant line[..at] == old(line[..at])
    invariant line[at..l-p] == old(line[at+p..l])
    invariant forall i :: l-p <= i < j ==> line[i] == ' '
  {
    line[j] := ' ';
    j := j+1;
  }
}

Extended solution on rise4fun.

Verifying a Dafny method that shifts a region of an array

1 Answers