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 | |
| parent | 933057e27e9310cd88e4a41ba3cf51bfeb74a226 (diff) | |
Dafny: implemented thresholds for the new interval domain (/infer:j)
Diffstat (limited to 'Test/dafny2')
| -rw-r--r-- | Test/dafny2/Answer | 4 | ||||
| -rw-r--r-- | Test/dafny2/Intervals.dfy | 63 | ||||
| -rw-r--r-- | Test/dafny2/runtest.bat | 1 |
3 files changed, 68 insertions, 0 deletions
diff --git a/Test/dafny2/Answer b/Test/dafny2/Answer index 9cb94f69..ea481dae 100644 --- a/Test/dafny2/Answer +++ b/Test/dafny2/Answer @@ -26,3 +26,7 @@ Dafny program verifier finished with 4 verified, 0 errors -------------------- COST-verif-comp-2011-4-FloydCycleDetect.dfy --------------------
Dafny program verifier finished with 23 verified, 0 errors
+
+-------------------- Intervals.dfy --------------------
+
+Dafny program verifier finished with 5 verified, 0 errors
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;
+}
diff --git a/Test/dafny2/runtest.bat b/Test/dafny2/runtest.bat index d7c0dc79..79ee0f89 100644 --- a/Test/dafny2/runtest.bat +++ b/Test/dafny2/runtest.bat @@ -14,6 +14,7 @@ for %%f in ( COST-verif-comp-2011-2-MaxTree-datatype.dfy
COST-verif-comp-2011-3-TwoDuplicates.dfy
COST-verif-comp-2011-4-FloydCycleDetect.dfy
+ Intervals.dfy
) do (
echo.
echo -------------------- %%f --------------------
|