blob: 6255ee9684536b3d8e365a3c597651fb784e71a9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
// RUN: %dafny /compile:0 /dprint:"%t.dprint" "%s" > "%t"
// RUN: %diff "%s.expect" "%t"
abstract module A {
import L = Library;
class {:autocontracts} StoreAndRetrieve<Thing(==)> {
ghost var Contents: set<Thing>;
predicate Valid
{
true
}
constructor Init()
{
Contents := {};
}
method Store(t: Thing)
{
Contents := Contents + {t};
}
method Retrieve(matchCriterion: L.Function) returns (thing: Thing)
requires exists t :: t in Contents && L.Function.Apply(matchCriterion, t);
ensures Contents == old(Contents);
ensures thing in Contents && L.Function.Apply(matchCriterion, thing);
{
var k :| assume k in Contents && L.Function.Apply(matchCriterion, k);
thing := k;
}
}
}
module B refines A {
class StoreAndRetrieve<Thing(==)> {
var arr: seq<Thing>;
predicate Valid
{
Contents == set x | x in arr
}
constructor Init()
{
arr := [];
}
method Store...
{
arr := arr + [t];
}
method Retrieve...
{
var i := 0;
while (i < |arr|)
invariant i < |arr|;
invariant forall j :: 0 <= j < i ==> !L.Function.Apply(matchCriterion, arr[j]);
{
if (L.Function.Apply(matchCriterion, arr[i])) { break; }
i := i + 1;
}
var k := arr[i];
...;
var a: seq<Thing> :| assume Contents == set x | x in a;
arr := a;
}
}
}
module C refines B {
class StoreAndRetrieve<Thing(==)> {
method Retrieve...
{
...;
var a := [thing] + arr[..i] + arr[i+1..]; // LRU behavior
}
}
}
module Library {
// This class simulates function parameters
class Function {
static function method Apply<T>(f: Function, t: T): bool
}
}
|
