Chalice/examples/cell.chalice


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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

class Cell module Library {
  var x: int;

  method init(v: int)
    requires acc(this.x) && 0<=v;
    ensures valid && this.get() == v;
  {
    x := v;
    fold valid;
  }

  method set(v: int)
    requires valid && 0<=v;
    ensures valid && get()==v;
  {
    unfold valid;
    x := v;
    fold valid;
  }
  
  method increment()
    requires valid;
    ensures valid && get() == old(get()) + 1;
  {
    unfold valid;
    x := x + 1;
    fold valid;
  }

  method dispose()
    requires valid && acc(mu);
    ensures true;
  {
    unfold valid;
    free this;
  }

  function get(): int
    requires valid;
    ensures 0<=result;
  {
    unfolding valid in x
  }

  predicate valid {
    acc(this.x) && 0<=x
  }

  invariant valid;
}

class Interval module Library2 {
  var left: Cell;
  var right: Cell;

  method init(l: int, r: int)
    requires 0<=l && l <= r;
    requires acc(left) && acc(right);
    ensures valid;
    ensures getLeft()==l
    ensures getRight()==r;
  {
    left := new Cell;
    call left.init(l);
    right := new Cell;
    call right.init(r);
    fold valid;
  }

  method setLeft(l: int)
    requires valid;
    requires 0<=l && l<=getRight();
    ensures valid;
    ensures getLeft()==l && getRight()==old(getRight());
  {
    unfold valid;
    call left.set(l);
    fold valid;
  }

  method setRight(r: int)
    requires valid;
    requires 0<=r && getLeft()<=r;
    ensures valid;
    ensures getLeft()==old(getLeft()) && getRight()==r;
  {
    unfold valid;
    call right.set(r);
    fold valid;
  }

  method shift(v: int)
    requires valid;
    requires 0<=v;
    ensures valid;
    ensures getLeft()==old(getLeft())+v && getRight()==old(getRight())+v;
  {
    unfold valid;
    call left.set(left.get()+v);
    call right.set(right.get()+v);
    fold valid;
  }

  function getLeft() : int
    requires valid;
  {
    unfolding valid in left.get()
  }

  function getRight() : int
    requires valid;
  {
    unfolding valid in right.get()
  }
  
  predicate valid
  {
    acc(left) && acc(right) && left!=null && right!=null && left.valid && right.valid && left.get() <= right.get()
  }
}

class Program module Main {
  method main(){
    var c1 := new Cell;
    call c1.init(5);
    call c1.set(6);

    var c2 := new Cell;
    call c2.init(10);
    call c2.set(11);

    assert c1.get() == 6;
  }

  method main2(){
    var c: Cell;

    c := new Cell;
    call c.init(0);
    call c.dispose();

    assert c.valid; // should fail
  }

  method main3() returns (rt: Cell)
    ensures rt!=null && rt.valid && rt.get() == 0
  {
    rt := new Cell;
    call rt.init(0)
  }

  method main4() {
    var c: Cell;

    c := new Cell;
    call c.init(0);
    share c;

    acquire c;
    call c.set(1);
    release c;
  }
}