diff options
| author |  Rustan Leino <leino@microsoft.com> | 2011-12-12 13:53:32 -0800 |
|---|---|---|
| committer | Rustan Leino <leino@microsoft.com> | 2011-12-12 13:53:32 -0800 |
| commit | 7e1c3ea0c3d54153c0a698226754686958ceb5f8 (patch) | |
| tree | f9f5c811d3a4adc316b715c290416b69ebe247c4 /Test/dafny2/Intervals.dfy | |
| parent | 933057e27e9310cd88e4a41ba3cf51bfeb74a226 (diff) | |
Dafny: implemented thresholds for the new interval domain (/infer:j)
Diffstat (limited to 'Test/dafny2/Intervals.dfy')
| -rw-r--r-- | Test/dafny2/Intervals.dfy | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/Test/dafny2/Intervals.dfy b/Test/dafny2/Intervals.dfy new file mode 100644 index 00000000..f04f6411 --- /dev/null +++ b/Test/dafny2/Intervals.dfy @@ -0,0 +1,63 @@ +// The RoundDown and RoundUp methods in this file are the ones in the Boogie
+// implementation Source/AbsInt/IntervalDomain.cs.
+
+var thresholds: array<int>;
+
+function Valid(): bool
+ reads this, thresholds;
+{
+ thresholds != null &&
+ forall m,n :: 0 <= m < n < thresholds.Length ==> thresholds[m] <= thresholds[n]
+}
+
+method RoundDown(k: int) returns (r: int)
+ requires Valid();
+ ensures -1 <= r < thresholds.Length;
+ ensures forall m :: r < m < thresholds.Length ==> k < thresholds[m];
+ ensures 0 <= r ==> thresholds[r] <= k;
+{
+ if (thresholds.Length == 0 || k < thresholds[0]) {
+ return -1;
+ }
+ var i, j := 0, thresholds.Length - 1;
+ while (i < j)
+ invariant 0 <= i <= j < thresholds.Length;
+ invariant thresholds[i] <= k;
+ invariant forall m :: j < m < thresholds.Length ==> k < thresholds[m];
+ {
+ var mid := i + (j - i + 1) / 2;
+ assert i < mid <= j;
+ if (thresholds[mid] <= k) {
+ i := mid;
+ } else {
+ j := mid - 1;
+ }
+ }
+ return i;
+}
+
+method RoundUp(k: int) returns (r: int)
+ requires Valid();
+ ensures 0 <= r <= thresholds.Length;
+ ensures forall m :: 0 <= m < r ==> thresholds[m] < k;
+ ensures r < thresholds.Length ==> k <= thresholds[r];
+{
+ if (thresholds.Length == 0 || thresholds[thresholds.Length-1] < k) {
+ return thresholds.Length;
+ }
+ var i, j := 0, thresholds.Length - 1;
+ while (i < j)
+ invariant 0 <= i <= j < thresholds.Length;
+ invariant k <= thresholds[j];
+ invariant forall m :: 0 <= m < i ==> thresholds[m] < k;
+ {
+ var mid := i + (j - i) / 2;
+ assert i <= mid < j;
+ if (thresholds[mid] < k) {
+ i := mid + 1;
+ } else {
+ j := mid;
+ }
+ }
+ return i;
+}
|