summaryrefslogtreecommitdiff
path: root/Test/dafny2
diff options
context:
space:
mode:
authorGravatar Rustan Leino <leino@microsoft.com>2011-12-12 13:53:32 -0800
committerGravatar Rustan Leino <leino@microsoft.com>2011-12-12 13:53:32 -0800
commit7e1c3ea0c3d54153c0a698226754686958ceb5f8 (patch)
treef9f5c811d3a4adc316b715c290416b69ebe247c4 /Test/dafny2
parent933057e27e9310cd88e4a41ba3cf51bfeb74a226 (diff)
Dafny: implemented thresholds for the new interval domain (/infer:j)
Diffstat (limited to 'Test/dafny2')
-rw-r--r--Test/dafny2/Answer4
-rw-r--r--Test/dafny2/Intervals.dfy63
-rw-r--r--Test/dafny2/runtest.bat1
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 --------------------