diff options
Diffstat (limited to 'Test/hofs')
30 files changed, 349 insertions, 223 deletions
diff --git a/Test/hofs/Apply.dfy.expect b/Test/hofs/Apply.dfy.expect index 77d34c4c..0a923143 100644 --- a/Test/hofs/Apply.dfy.expect +++ b/Test/hofs/Apply.dfy.expect @@ -1,4 +1,4 @@ -Apply.dfy(27,16): Error: assertion violation
+Apply.dfy(27,15): Error: assertion violation
Execution trace:
(0,0): anon0
Apply.dfy(26,27): anon15_Else
diff --git a/Test/hofs/Classes.dfy b/Test/hofs/Classes.dfy index 2b892b35..9d8044db 100644 --- a/Test/hofs/Classes.dfy +++ b/Test/hofs/Classes.dfy @@ -30,15 +30,14 @@ function B(t : T) : int -> int } function J(t : T) : int - requires t != null; - requires t.h.reads(0) == {}; - reads t; - reads if t != null then t.h.reads(0) else {}; + requires t != null + reads t + reads t.h.reads(0) { if t.h.requires(0) then B(t)(0) else - B(t)(0) // fail + B(t)(0) // error: precondition violation } method U(t : T) @@ -48,3 +47,20 @@ method U(t : T) t.h := x => x; assert J(t) == 0; // ok } + +class MyClass { + var data: int + function method F(): int + reads this + { + data + } + method M(that: MyClass) + requires that != null + { + var fn := that.F; // "that" is captured into the closure + var d := fn(); + assert d == that.data; // yes + assert d == this.data; // error: no reason to believe that this would hold + } +} diff --git a/Test/hofs/Classes.dfy.expect b/Test/hofs/Classes.dfy.expect index 3c933bae..a5b33522 100644 --- a/Test/hofs/Classes.dfy.expect +++ b/Test/hofs/Classes.dfy.expect @@ -1,10 +1,10 @@ -Classes.dfy(41,6): Error: possible violation of function precondition
+Classes.dfy(64,11): Error: assertion violation
Execution trace:
(0,0): anon0
- (0,0): anon11_Then
- (0,0): anon3
- (0,0): anon12_Then
- (0,0): anon13_Else
- (0,0): anon14_Else
+Classes.dfy(40,5): Error: possible violation of function precondition
+Execution trace:
+ (0,0): anon0
+ (0,0): anon7_Else
+ (0,0): anon8_Else
-Dafny program verifier finished with 6 verified, 1 error
+Dafny program verifier finished with 8 verified, 2 errors
diff --git a/Test/hofs/Examples.dfy b/Test/hofs/Examples.dfy index be2672f5..306d278d 100644 --- a/Test/hofs/Examples.dfy +++ b/Test/hofs/Examples.dfy @@ -1,14 +1,14 @@ // RUN: %dafny /print:"%t.print" "%s" > "%t" // RUN: %diff "%s.expect" "%t" -function Apply(f: A -> B, x: A): B +function Apply<A,B>(f: A -> B, x: A): B reads f.reads(x); requires f.requires(x); { f(x) } -function Apply'(f: A -> B) : A -> B +function Apply'<A,B>(f: A -> B) : A -> B { x reads f.reads(x) requires f.requires(x) @@ -16,7 +16,7 @@ function Apply'(f: A -> B) : A -> B } -function Compose(f: B -> C, g:A -> B): A -> C +function Compose<A,B,C>(f: B -> C, g:A -> B): A -> C { x reads g.reads(x) reads if g.requires(x) then f.reads(g(x)) else {} @@ -25,21 +25,21 @@ function Compose(f: B -> C, g:A -> B): A -> C => f(g(x)) } -function W(f : (A,A) -> A): A -> A +function W<A>(f : (A,A) -> A): A -> A { x requires f.requires(x,x) reads f.reads(x,x) => f(x,x) } -function Curry(f : (A,B) -> C) : A -> B -> C +function Curry<A,B,C>(f : (A,B) -> C) : A -> B -> C { x => y requires f.requires(x,y) reads f.reads(x,y) => f(x,y) } -function Uncurry(f : A -> B -> C) : (A,B) -> C +function Uncurry<A,B,C>(f : A -> B -> C) : (A,B) -> C { (x,y) requires f.requires(x) requires f(x).requires(y) @@ -48,7 +48,7 @@ function Uncurry(f : A -> B -> C) : (A,B) -> C => f(x)(y) } -function S(f : (A,B) -> C, g : A -> B): A -> C +function S<A,B,C>(f : (A,B) -> C, g : A -> B): A -> C { x requires g.requires(x) requires f.requires(x,g(x)) diff --git a/Test/hofs/Field.dfy.expect b/Test/hofs/Field.dfy.expect index 9f6998f5..0859d83c 100644 --- a/Test/hofs/Field.dfy.expect +++ b/Test/hofs/Field.dfy.expect @@ -1,13 +1,13 @@ -Field.dfy(12,12): Error: possible violation of function precondition
+Field.dfy(12,11): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
-Field.dfy(12,15): Error: assertion violation
+Field.dfy(12,14): Error: assertion violation
Execution trace:
(0,0): anon0
-Field.dfy(21,12): Error: possible violation of function precondition
+Field.dfy(21,11): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
-Field.dfy(21,14): Error: assertion violation
+Field.dfy(21,13): Error: assertion violation
Execution trace:
(0,0): anon0
diff --git a/Test/hofs/FnRef.dfy.expect b/Test/hofs/FnRef.dfy.expect index 0f6f2aa9..e665c830 100644 --- a/Test/hofs/FnRef.dfy.expect +++ b/Test/hofs/FnRef.dfy.expect @@ -1,19 +1,19 @@ -FnRef.dfy(17,45): Error: possible violation of function precondition
+FnRef.dfy(17,44): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
FnRef.dfy(15,12): anon5_Else
(0,0): anon6_Then
-FnRef.dfy(32,8): Error: possible violation of function precondition
+FnRef.dfy(32,7): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
FnRef.dfy(26,12): anon9_Else
FnRef.dfy(28,8): anon10_Else
-FnRef.dfy(46,12): Error: assertion violation
+FnRef.dfy(46,11): Error: assertion violation
Execution trace:
(0,0): anon0
FnRef.dfy(43,12): anon7_Else
(0,0): anon9_Then
-FnRef.dfy(65,14): Error: assertion violation
+FnRef.dfy(65,13): Error: assertion violation
Execution trace:
(0,0): anon0
FnRef.dfy(56,12): anon8_Else
diff --git a/Test/hofs/Fold.dfy b/Test/hofs/Fold.dfy index 6ca2d3b1..9bcd9e02 100644 --- a/Test/hofs/Fold.dfy +++ b/Test/hofs/Fold.dfy @@ -13,7 +13,7 @@ function method Eval(e : Expr): int case Lit(i) => i } -function method Fold(xs : List<A>, unit : B, f : (A,B) -> B): B +function method Fold<A,B>(xs : List<A>, unit : B, f : (A,B) -> B): B reads f.reads; requires forall x, y :: x < xs ==> f.requires(x,y); { diff --git a/Test/hofs/Frame.dfy.expect b/Test/hofs/Frame.dfy.expect index 0ee2eadb..9964deb4 100644 --- a/Test/hofs/Frame.dfy.expect +++ b/Test/hofs/Frame.dfy.expect @@ -1,35 +1,35 @@ -Frame.dfy(23,16): Error: assertion violation
+Frame.dfy(23,15): Error: assertion violation
Execution trace:
(0,0): anon0
Frame.dfy(19,12): anon5_Else
(0,0): anon6_Then
-Frame.dfy(37,14): Error: assertion violation
+Frame.dfy(37,13): Error: assertion violation
Execution trace:
(0,0): anon0
Frame.dfy(33,12): anon3_Else
-Frame.dfy(63,23): Error: assertion violation
+Frame.dfy(63,22): Error: assertion violation
Execution trace:
(0,0): anon0
(0,0): anon13_Then
Frame.dfy(55,12): anon14_Else
(0,0): anon15_Then
(0,0): anon5
-Frame.dfy(66,19): Error: insufficient reads clause to read array element
+Frame.dfy(66,18): Error: insufficient reads clause to read array element
Execution trace:
(0,0): anon0
(0,0): anon16_Then
(0,0): anon17_Then
-Frame.dfy(68,28): Error: insufficient reads clause to read array element
+Frame.dfy(68,27): Error: insufficient reads clause to read array element
Execution trace:
(0,0): anon0
(0,0): anon16_Else
(0,0): anon18_Then
-Frame.dfy(123,14): Error: possible violation of function precondition
+Frame.dfy(123,13): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
(0,0): anon5_Then
(0,0): anon6_Else
-Frame.dfy(123,19): Error: assertion violation
+Frame.dfy(123,18): Error: assertion violation
Execution trace:
(0,0): anon0
(0,0): anon5_Then
diff --git a/Test/hofs/Lambda.dfy.expect b/Test/hofs/Lambda.dfy.expect index 4fe8275f..ab57fbe0 100644 --- a/Test/hofs/Lambda.dfy.expect +++ b/Test/hofs/Lambda.dfy.expect @@ -1,4 +1,4 @@ -Lambda.dfy(24,12): Error: assertion violation
+Lambda.dfy(24,11): Error: assertion violation
Execution trace:
(0,0): anon0
Lambda.dfy(6,24): anon31_Else
diff --git a/Test/hofs/LambdaParsefail.dfy.expect b/Test/hofs/LambdaParsefail.dfy.expect index 11deb9b0..a72fc978 100644 --- a/Test/hofs/LambdaParsefail.dfy.expect +++ b/Test/hofs/LambdaParsefail.dfy.expect @@ -1,6 +1,6 @@ -LambdaParsefail.dfy(5,19): error: this symbol not expected in VarDeclStatement
-LambdaParsefail.dfy(6,19): error: this symbol not expected in VarDeclStatement
-LambdaParsefail.dfy(7,21): error: this symbol not expected in VarDeclStatement
-LambdaParsefail.dfy(8,15): error: cannot declare identifier beginning with underscore
-LambdaParsefail.dfy(9,17): error: this symbol not expected in VarDeclStatement
+LambdaParsefail.dfy(5,18): Error: this symbol not expected in VarDeclStatement
+LambdaParsefail.dfy(6,18): Error: this symbol not expected in VarDeclStatement
+LambdaParsefail.dfy(7,20): Error: this symbol not expected in VarDeclStatement
+LambdaParsefail.dfy(8,14): Error: cannot declare identifier beginning with underscore
+LambdaParsefail.dfy(9,16): Error: this symbol not expected in VarDeclStatement
5 parse errors detected in LambdaParsefail.dfy
diff --git a/Test/hofs/LambdaParsefail2.dfy.expect b/Test/hofs/LambdaParsefail2.dfy.expect index 0c9ecb83..1a6a65dc 100644 --- a/Test/hofs/LambdaParsefail2.dfy.expect +++ b/Test/hofs/LambdaParsefail2.dfy.expect @@ -1,2 +1,2 @@ -LambdaParsefail2.dfy(6,39): error: invalid LambdaArrow
+LambdaParsefail2.dfy(6,38): Error: invalid LambdaArrow
1 parse errors detected in LambdaParsefail2.dfy
diff --git a/Test/hofs/Monads.dfy b/Test/hofs/Monads.dfy index 3598d2b3..633dd339 100644 --- a/Test/hofs/Monads.dfy +++ b/Test/hofs/Monads.dfy @@ -4,29 +4,29 @@ abstract module Monad { type M<A> - function method Return(x: A): M<A> - function method Bind(m: M<A>, f:A -> M<B>):M<B> - reads f.reads; - requires forall a :: f.requires(a); + function method Return<A>(x: A): M<A> + function method Bind<A,B>(m: M<A>, f:A -> M<B>):M<B> + reads f.reads + requires forall a :: f.requires(a) // return x >>= f = f x - lemma LeftIdentity(x : A, f : A -> M<B>) - requires forall a :: f.requires(a); - ensures Bind(Return(x),f) == f(x); + lemma LeftIdentity<A,B>(x : A, f : A -> M<B>) + requires forall a :: f.requires(a) + ensures Bind(Return(x),f) == f(x) // m >>= return = m - lemma RightIdentity(m : M<A>) - ensures Bind(m,Return) == m; + lemma RightIdentity<A>(m : M<A>) + ensures Bind(m,Return) == m // (m >>= f) >>= g = m >>= (x => f(x) >>= g) - lemma Associativity(m : M<A>, f:A -> M<B>, g: B -> M<C>) - requires forall a :: f.requires(a); - requires forall b :: g.requires(b); + lemma Associativity<A,B,C>(m : M<A>, f:A -> M<B>, g: B -> M<C>) + requires forall a :: f.requires(a) + requires forall b :: g.requires(b) ensures Bind(Bind(m,f),g) == Bind(m,x reads f.reads(x) reads g.reads requires f.requires(x) - requires forall b :: g.requires(b) => Bind(f(x),g)); + requires forall b :: g.requires(b) => Bind(f(x),g)) } module Identity refines Monad { @@ -101,21 +101,21 @@ module List refines Monad { function method Return<A>(x: A): M<A> { Cons(x,Nil) } - function method Concat(xs: M<A>, ys: M<A>): M<A> + function method Concat<A>(xs: M<A>, ys: M<A>): M<A> { match xs case Nil => ys case Cons(x,xs) => Cons(x,Concat(xs,ys)) } - function method Join(xss: M<M<A>>) : M<A> + function method Join<A>(xss: M<M<A>>) : M<A> { match xss case Nil => Nil case Cons(xs,xss) => Concat(xs,Join(xss)) } - function method Map(xs: M<A>, f: A -> B):M<B> + function method Map<A,B>(xs: M<A>, f: A -> B):M<B> reads f.reads; requires forall a :: f.requires(a); { @@ -170,7 +170,7 @@ module List refines Monad { ensures Concat(Concat(xs,ys),zs) == Concat(xs,Concat(ys,zs)); {} - lemma BindMorphism(xs : M<A>, ys: M<A>, f : A -> M<B>) + lemma BindMorphism<A,B>(xs : M<A>, ys: M<A>, f : A -> M<B>) requires forall a :: f.requires(a); ensures Bind(Concat(xs,ys),f) == Concat(Bind(xs,f),Bind(ys,f)); { diff --git a/Test/hofs/Naked.dfy b/Test/hofs/Naked.dfy index fa99377f..d23eb507 100644 --- a/Test/hofs/Naked.dfy +++ b/Test/hofs/Naked.dfy @@ -19,17 +19,17 @@ module Functions { module Requires { function t(x: nat): nat - requires !t.requires(x); + requires !t.requires(x); // error: use of naked function in its own SCC { x } function g(x: nat): nat - requires !(g).requires(x); + requires !(g).requires(x); // error: use of naked function in its own SCC { x } - function g2(x: int): int { h(x) } - + function D(x: int): int // used so termination errors don't mask other errors + function g2(x: int): int decreases D(x) { h(x) } // error: precondition violation function h(x: int): int - requires !g2.requires(x); + requires !g2.requires(x); // error: use of naked function in its own SCC { x } } diff --git a/Test/hofs/Naked.dfy.expect b/Test/hofs/Naked.dfy.expect index 62c035b2..9794478d 100644 --- a/Test/hofs/Naked.dfy.expect +++ b/Test/hofs/Naked.dfy.expect @@ -1,50 +1,46 @@ -Naked.dfy(9,16): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+Naked.dfy(9,15): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
- (0,0): anon7_Else
- (0,0): anon8_Else
- (0,0): anon9_Then
-Naked.dfy(12,8): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
-Execution trace:
- (0,0): anon0
- (0,0): anon7_Else
- (0,0): anon8_Else
(0,0): anon9_Else
-Naked.dfy(17,53): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+ (0,0): anon10_Else
+ (0,0): anon11_Then
+Naked.dfy(12,7): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
- (0,0): anon5_Else
- (0,0): anon6_Else
-Naked.dfy(22,13): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+ (0,0): anon9_Else
+ (0,0): anon10_Else
+ (0,0): anon11_Else
+Naked.dfy(17,52): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
-Naked.dfy(26,14): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+ (0,0): anon7_Else
+ (0,0): anon8_Else
+Naked.dfy(22,12): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
-Naked.dfy(29,30): Error: cannot prove termination; try supplying a decreases clause
+Naked.dfy(26,13): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-Naked.dfy(29,30): Error: possible violation of function precondition
-Naked.dfy(32,14): Related location
+Naked.dfy(30,44): Error: possible violation of function precondition
+Naked.dfy(32,13): Related location
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-Naked.dfy(32,15): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+ (0,0): anon4_Else
+Naked.dfy(32,14): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
-Naked.dfy(38,9): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+Naked.dfy(38,8): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
-Naked.dfy(42,10): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+Naked.dfy(42,9): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
-Naked.dfy(45,30): Error: cannot prove termination; try supplying a decreases clause
+Naked.dfy(45,29): Error: cannot prove termination; try supplying a decreases clause
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-Naked.dfy(48,11): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
+ (0,0): anon4_Else
+Naked.dfy(48,10): Error: cannot use naked function in recursive setting. Possible solution: eta expansion.
Execution trace:
(0,0): anon0
-Dafny program verifier finished with 1 verified, 12 errors
+Dafny program verifier finished with 2 verified, 11 errors
diff --git a/Test/hofs/OneShot.dfy b/Test/hofs/OneShot.dfy index 286be898..e920530a 100644 --- a/Test/hofs/OneShot.dfy +++ b/Test/hofs/OneShot.dfy @@ -10,16 +10,15 @@ method OneShot() { var i : Ref<int>; i := new Ref; - g := () -> true; - + g := () reads i -> true; // using a (deprecated) one-shot arrow here means "g" acquires + // a precondition that says it can only be applied in this heap assert g(); i.val := i.val + 1; // heap changes if * { - assert g(); // should fail + assert g(); // error: precondition violation } else { - assert !g(); // should fail + assert !g(); // error: precondition violation } } - diff --git a/Test/hofs/OneShot.dfy.expect b/Test/hofs/OneShot.dfy.expect index 91b931b8..0b4a2bb8 100644 --- a/Test/hofs/OneShot.dfy.expect +++ b/Test/hofs/OneShot.dfy.expect @@ -1,16 +1,16 @@ -OneShot.dfy(20,12): Error: possible violation of function precondition
+OneShot.dfy(20,11): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
(0,0): anon5_Then
OneShot.dfy(13,8): anon5_Else
(0,0): anon6_Then
-OneShot.dfy(22,12): Error: assertion violation
+OneShot.dfy(22,11): Error: assertion violation
Execution trace:
(0,0): anon0
(0,0): anon5_Then
OneShot.dfy(13,8): anon5_Else
(0,0): anon6_Else
-OneShot.dfy(22,13): Error: possible violation of function precondition
+OneShot.dfy(22,12): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
(0,0): anon5_Then
diff --git a/Test/hofs/ReadsReads.dfy b/Test/hofs/ReadsReads.dfy index e11473bd..60ac35f5 100644 --- a/Test/hofs/ReadsReads.dfy +++ b/Test/hofs/ReadsReads.dfy @@ -2,58 +2,58 @@ // RUN: %diff "%s.expect" "%t" module ReadsRequiresReads { - function MyReadsOk(f : A -> B, a : A) : set<object> - reads f.reads(a); + function MyReadsOk<A,B>(f : A -> B, a : A) : set<object> + reads f.reads(a) { f.reads(a) } - function MyReadsOk2(f : A -> B, a : A) : set<object> - reads f.reads(a); + function MyReadsOk2<A,B>(f : A -> B, a : A) : set<object> + reads f.reads(a) { (f.reads)(a) } - function MyReadsOk3(f : A -> B, a : A) : set<object> - reads (f.reads)(a); + function MyReadsOk3<A,B>(f : A -> B, a : A) : set<object> + reads (f.reads)(a) { f.reads(a) } - function MyReadsOk4(f : A -> B, a : A) : set<object> - reads (f.reads)(a); + function MyReadsOk4<A,B>(f : A -> B, a : A) : set<object> + reads (f.reads)(a) { (f.reads)(a) } - function MyReadsBad(f : A -> B, a : A) : set<object> + function MyReadsBad<A,B>(f : A -> B, a : A) : set<object> { f.reads(a) // error: MyReadsBad does not have permission to read what f.reads(a) reads } - function MyReadsBad2(f : A -> B, a : A) : set<object> + function MyReadsBad2<A,B>(f : A -> B, a : A) : set<object> { (f.reads)(a) // error: MyReadsBad2 does not have permission to read what f.reads(a) reads } - function MyReadsOk'(f : A -> B, a : A, o : object) : bool - reads f.reads(a); + function MyReadsOk'<A,B>(f : A -> B, a : A, o : object) : bool + reads f.reads(a) { o in f.reads(a) } - function MyReadsBad'(f : A -> B, a : A, o : object) : bool + function MyReadsBad'<A,B>(f : A -> B, a : A, o : object) : bool { o in f.reads(a) // error: MyReadsBad' does not have permission to read what f.reads(a) reads } - function MyRequiresOk(f : A -> B, a : A) : bool - reads f.reads(a); + function MyRequiresOk<A,B>(f : A -> B, a : A) : bool + reads f.reads(a) { f.requires(a) } - function MyRequiresBad(f : A -> B, a : A) : bool + function MyRequiresBad<A,B>(f : A -> B, a : A) : bool { f.requires(a) // error: MyRequiresBad does not have permission to read what f.requires(a) reads } @@ -72,11 +72,11 @@ module WhatWeKnowAboutReads { } class S { - var s : S; + var s : S } function ReadsSomething(s : S):() - reads s; + reads s {()} method MaybeSomething() { @@ -105,29 +105,29 @@ module WhatWeKnowAboutReads { module ReadsAll { function A(f: int -> int) : int - reads set o,x | o in f.reads(x) :: o; - requires forall x :: f.requires(x); + reads set x,o | o in f.reads(x) :: o // note, with "set o,x ..." instead, Dafny complains (this is perhaps less than ideal) + requires forall x :: f.requires(x) { f(0) + f(1) + f(2) } function method B(f: int -> int) : int - reads set o,x | o in f.reads(x) :: o; - requires forall x :: f.requires(x); + reads set x,o | o in f.reads(x) :: o // note, with "set o,x ..." instead, Dafny complains (this is perhaps less than ideal) + requires forall x :: f.requires(x) { f(0) + f(1) + f(2) } function C(f: int -> int) : int - reads f.reads; - requires forall x :: f.requires(x); + reads f.reads + requires forall x :: f.requires(x) { f(0) + f(1) + f(2) } function method D(f: int -> int) : int - reads f.reads; - requires forall x :: f.requires(x); + reads f.reads + requires forall x :: f.requires(x) { f(0) + f(1) + f(2) } diff --git a/Test/hofs/ReadsReads.dfy.expect b/Test/hofs/ReadsReads.dfy.expect index 73002b73..0a374c44 100644 --- a/Test/hofs/ReadsReads.dfy.expect +++ b/Test/hofs/ReadsReads.dfy.expect @@ -1,33 +1,33 @@ -ReadsReads.dfy(31,7): Error: insufficient reads clause to invoke function
+ReadsReads.dfy(31,6): Error: insufficient reads clause to invoke function
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-ReadsReads.dfy(36,5): Error: insufficient reads clause to invoke function
+ (0,0): anon4_Else
+ReadsReads.dfy(36,4): Error: insufficient reads clause to invoke function
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-ReadsReads.dfy(47,12): Error: insufficient reads clause to invoke function
+ (0,0): anon4_Else
+ReadsReads.dfy(47,11): Error: insufficient reads clause to invoke function
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-ReadsReads.dfy(58,7): Error: insufficient reads clause to invoke function
+ (0,0): anon4_Else
+ReadsReads.dfy(58,6): Error: insufficient reads clause to invoke function
Execution trace:
(0,0): anon0
- (0,0): anon3_Else
-ReadsReads.dfy(87,50): Error: assertion violation
+ (0,0): anon4_Else
+ReadsReads.dfy(87,49): Error: assertion violation
Execution trace:
(0,0): anon0
(0,0): anon16_Then
-ReadsReads.dfy(89,29): Error: assertion violation
+ReadsReads.dfy(89,28): Error: assertion violation
Execution trace:
(0,0): anon0
(0,0): anon18_Then
-ReadsReads.dfy(99,37): Error: assertion violation
+ReadsReads.dfy(99,36): Error: assertion violation
Execution trace:
(0,0): anon0
ReadsReads.dfy(96,14): anon15_Else
(0,0): anon19_Then
-ReadsReads.dfy(101,29): Error: assertion violation
+ReadsReads.dfy(101,28): Error: assertion violation
Execution trace:
(0,0): anon0
ReadsReads.dfy(96,14): anon15_Else
diff --git a/Test/hofs/Requires.dfy b/Test/hofs/Requires.dfy new file mode 100644 index 00000000..68677b3e --- /dev/null +++ b/Test/hofs/Requires.dfy @@ -0,0 +1,82 @@ +// RUN: %dafny /compile:3 /print:"%t.print" /dprint:"%t.dprint" "%s" > "%t"
+// RUN: %diff "%s.expect" "%t"
+
+method Main()
+{
+ test0(10);
+ test5(11);
+ test6(12);
+ test1();
+ test2();
+}
+
+predicate valid(x:int)
+{
+ x > 0
+}
+
+function ref1(y:int) : int
+ requires valid(y);
+{
+ y - 1
+}
+
+lemma assumption1()
+ ensures forall a, b :: valid(a) && valid(b) && ref1(a) == ref1(b) ==> a == b;
+{
+}
+
+method test0(a: int)
+{
+ if ref1.requires(a) {
+ // the precondition should suffice to let us call the method
+ ghost var b := ref1(a);
+ }
+}
+method test5(a: int)
+{
+ if valid(a) {
+ // valid(a) is the precondition of ref1
+ assert ref1.requires(a);
+ }
+}
+method test6(a: int)
+{
+ if ref1.requires(a) {
+ // the precondition of ref1 is valid(a)
+ assert valid(a);
+ }
+}
+
+method test1()
+{
+ if * {
+ assert forall a, b :: valid(a) && valid(b) && ref1(a) == ref1(b) ==> a == b;
+ } else {
+ assert forall a, b :: ref1.requires(a) && ref1.requires(b) && ref1(a) == ref1(b)
+ ==> a == b;
+ }
+}
+
+function {:opaque} ref2(y:int) : int // Now with an opaque attribute
+ requires valid(y);
+{
+ y - 1
+}
+
+lemma assumption2()
+ ensures forall a, b :: valid(a) && valid(b) && ref2(a) == ref2(b) ==> a == b;
+{
+ reveal_ref2();
+}
+
+method test2()
+{
+ assumption2();
+ if * {
+ assert forall a, b :: valid(a) && valid(b) && ref2(a) == ref2(b) ==> a == b;
+ } else {
+ assert forall a, b :: ref2.requires(a) && ref2.requires(b) && ref2(a) == ref2(b)
+ ==> a == b;
+ }
+}
diff --git a/Test/hofs/Requires.dfy.expect b/Test/hofs/Requires.dfy.expect new file mode 100644 index 00000000..b9a40d66 --- /dev/null +++ b/Test/hofs/Requires.dfy.expect @@ -0,0 +1,5 @@ +
+Dafny program verifier finished with 20 verified, 0 errors
+Program compiled successfully
+Running...
+
diff --git a/Test/hofs/ResolveError.dfy b/Test/hofs/ResolveError.dfy index 3c0d7cd9..ae838eb3 100644 --- a/Test/hofs/ResolveError.dfy +++ b/Test/hofs/ResolveError.dfy @@ -3,9 +3,9 @@ method ResolutionErrors() { - var x; - var g5 := x, y => (y, x); // fail at resolution - var g6 := x, (y => (y, x)); // fail at resolution + var x; + var g5 := x, y => (y, x); // fail at resolution + var g6 := x, (y => (y, x)); // fail at resolution } // cannot assign functions @@ -23,20 +23,20 @@ method Nope3() { method RequiresFail(f : int -> int) // ok - requires f(0) == 0; - requires f.requires(0); - requires f.reads(0) == {}; + requires f(0) == 0 + requires f.requires(0) + requires f.reads(0) == {} // fail - requires f(0) == true; - requires f(1,2) == 0; - requires f(true) == 0; - requires f.requires(true); - requires f.requires(1) == 0; - requires f.requires(1,2); - requires f.reads(true) == {}; - requires f.reads(1) == 0; - requires f.reads(1,2) == {}; + requires f(0) == true + requires f(1,2) == 0 + requires f(true) == 0 + requires f.requires(true) + requires f.requires(1) == 0 + requires f.requires(1,2) + requires f.reads(true) == {} + requires f.reads(1) == 0 + requires f.reads(1,2) == {} { } @@ -56,7 +56,7 @@ method Bla() { assert Bool; } -method Pli(f : A -> B) requires f != null; +method Pli<A,B>(f : A -> B) requires f != null { var o : object; assert f != o; @@ -102,7 +102,7 @@ module AritySituations { w := V; // error } - method P(r: T -> U, x: T) returns (u: U) + method P<T,U>(r: T -> U, x: T) returns (u: U) requires r.requires(x); { u := r(x); diff --git a/Test/hofs/ResolveError.dfy.expect b/Test/hofs/ResolveError.dfy.expect index c3e0c242..11471ffd 100644 --- a/Test/hofs/ResolveError.dfy.expect +++ b/Test/hofs/ResolveError.dfy.expect @@ -2,8 +2,8 @@ ResolveError.dfy(86,6): Error: RHS (of type ((int,bool)) -> real) not assignable ResolveError.dfy(91,15): Error: incorrect type of method in-parameter 0 (expected ? -> ?, got (int,bool) -> real)
ResolveError.dfy(101,6): Error: RHS (of type (()) -> real) not assignable to LHS (of type () -> real)
ResolveError.dfy(102,6): Error: RHS (of type () -> real) not assignable to LHS (of type (()) -> real)
-ResolveError.dfy(7,11): Error: the number of left-hand sides (1) and right-hand sides (2) must match for a multi-assignment
-ResolveError.dfy(8,11): Error: the number of left-hand sides (1) and right-hand sides (2) must match for a multi-assignment
+ResolveError.dfy(7,9): Error: the number of left-hand sides (1) and right-hand sides (2) must match for a multi-assignment
+ResolveError.dfy(8,9): Error: the number of left-hand sides (1) and right-hand sides (2) must match for a multi-assignment
ResolveError.dfy(21,6): Error: LHS of assignment must denote a mutable field
ResolveError.dfy(31,16): Error: arguments must have the same type (got int and bool)
ResolveError.dfy(32,12): Error: wrong number of arguments to function application (function type 'int -> int' expects 1, got 2)
@@ -17,7 +17,7 @@ ResolveError.dfy(39,18): Error: wrong number of arguments to function applicatio ResolveError.dfy(46,15): Error: a reads-clause expression must denote an object or a collection of objects (instead got int)
ResolveError.dfy(47,7): Error: Precondition must be boolean (got int)
ResolveError.dfy(56,9): Error: condition is expected to be of type bool, but is () -> bool
-ResolveError.dfy(59,34): Error: arguments must have the same type (got A -> B and ?)
+ResolveError.dfy(59,39): Error: arguments must have the same type (got A -> B and ?)
ResolveError.dfy(62,11): Error: arguments must have the same type (got A -> B and object)
ResolveError.dfy(68,24): Error: unresolved identifier: _
22 resolution/type errors detected in ResolveError.dfy
diff --git a/Test/hofs/Simple.dfy b/Test/hofs/Simple.dfy index c27fa82c..6d98531e 100644 --- a/Test/hofs/Simple.dfy +++ b/Test/hofs/Simple.dfy @@ -50,7 +50,7 @@ method Main() { } function method succ(x : int) : int - requires x > 0; + requires x > 0 { x + 1 } @@ -74,24 +74,24 @@ method Main3() { } -function P(f: A -> B, x : A): B - reads (f.reads)(x); - requires (f.requires)(x); +function P<A,B>(f: A -> B, x : A): B + reads (f.reads)(x) + requires (f.requires)(x) { f(x) } -function Q(f: U -> V, x : U): V - reads P.reads(f,x); - requires f.requires(x); // would be nice to be able to write P.requires(f,x) +function Q<U,V>(f: U -> V, x : U): V + reads P.reads(f,x) + requires f.requires(x) // would be nice to be able to write P.requires(f,x) { P(f,x) } -function QQ(f: U -> V, x : U): V - reads ((() => ((()=>f)()).reads)())((()=>x)()); - requires ((() => ((()=>f)()).requires)())((()=>x)()); +function QQ<U,V>(f: U -> V, x : U): V + reads ((() => ((()=>f)()).reads)())((()=>x)()) + requires ((() => ((()=>f)()).requires)())((()=>x)()) { ((() => P)())((()=>f)(),(()=>x)()) } diff --git a/Test/hofs/Simple.dfy.expect b/Test/hofs/Simple.dfy.expect index b3c126d5..c0123c80 100644 --- a/Test/hofs/Simple.dfy.expect +++ b/Test/hofs/Simple.dfy.expect @@ -1,32 +1,29 @@ -Simple.dfy(14,10): Error: possible division by zero
+Simple.dfy(14,9): Error: possible division by zero
Execution trace:
(0,0): anon0
- (0,0): anon5_Else
- (0,0): anon6_Then
-Simple.dfy(27,10): Error: possible division by zero
+ (0,0): anon6_Else
+ (0,0): anon7_Then
+Simple.dfy(27,9): Error: possible division by zero
Execution trace:
(0,0): anon0
- (0,0): anon5_Else
- (0,0): anon6_Then
-Simple.dfy(37,9): Error: possible violation of function precondition
+ (0,0): anon6_Else
+ (0,0): anon7_Then
+Simple.dfy(37,8): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
Simple.dfy(35,13): anon5_Else
-Simple.dfy(49,9): Error: possible violation of function precondition
+Simple.dfy(49,8): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
(0,0): anon3_Then
(0,0): anon2
-Simple.dfy(61,10): Error: possible violation of function precondition
+Simple.dfy(61,9): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
-Simple.dfy(61,18): Error: assertion violation
-Execution trace:
- (0,0): anon0
-Simple.dfy(73,10): Error: assertion violation
+Simple.dfy(73,9): Error: assertion violation
Execution trace:
(0,0): anon0
Simple.dfy(72,38): anon5_Else
Simple.dfy(73,38): anon6_Else
-Dafny program verifier finished with 14 verified, 7 errors
+Dafny program verifier finished with 14 verified, 6 errors
diff --git a/Test/hofs/TreeMapSimple.dfy b/Test/hofs/TreeMapSimple.dfy index a853b82c..6b8f1377 100644 --- a/Test/hofs/TreeMapSimple.dfy +++ b/Test/hofs/TreeMapSimple.dfy @@ -6,7 +6,7 @@ datatype List<A> = Nil | Cons(head: A,tail: List<A>) datatype Tree<A> = Branch(val: A,trees: List<Tree<A>>) function ListData(xs : List) : set - ensures forall x :: x in ListData(xs) ==> x < xs; + ensures forall x :: x in ListData(xs) ==> x < xs { match xs case Nil => {} @@ -14,32 +14,32 @@ function ListData(xs : List) : set } function TreeData(t0 : Tree) : set - ensures forall t :: t in TreeData(t0) ==> t < t0; + ensures forall t :: t in TreeData(t0) ==> t < t0 { var Branch(x,ts) := t0; {x} + set t, y | t in ListData(ts) && y in TreeData(t) :: y } -function Pre(f : A -> B, s : set<A>) : bool - reads (set x, y | x in s && y in f.reads(x) :: y); +function Pre<A,B>(f : A -> B, s : set<A>) : bool + reads (set x, y | x in s && y in f.reads(x) :: y) { forall x :: x in s ==> f.reads(x) == {} && f.requires(x) } -function method Map(xs : List<A>, f : A -> B): List<B> - reads Pre.reads(f, ListData(xs)); - requires Pre(f, ListData(xs)); - decreases xs; +function method Map<A,B>(xs : List<A>, f : A -> B): List<B> + reads Pre.reads(f, ListData(xs)) + requires Pre(f, ListData(xs)) + decreases xs { match xs case Nil => Nil case Cons(x,xs) => Cons(f(x),Map(xs,f)) } -function method TMap(t0 : Tree<A>, f : A -> B) : Tree<B> - reads Pre.reads(f, TreeData(t0)); - requires Pre(f, TreeData(t0)); - decreases t0; +function method TMap<A,B>(t0 : Tree<A>, f : A -> B) : Tree<B> + reads Pre.reads(f, TreeData(t0)) + requires Pre(f, TreeData(t0)) + decreases t0 { var Branch(x,ts) := t0; Branch(f(x),Map(ts, t requires t in ListData(ts) diff --git a/Test/hofs/Twice.dfy b/Test/hofs/Twice.dfy index add7e83c..5d948a58 100644 --- a/Test/hofs/Twice.dfy +++ b/Test/hofs/Twice.dfy @@ -1,7 +1,7 @@ // RUN: %dafny /print:"%t.print" "%s" > "%t" // RUN: %diff "%s.expect" "%t" -function method Twice(f : A -> A): A -> A +function method Twice<A>(f : A -> A): A -> A { x requires f.requires(x) && f.requires(f(x)) reads f.reads(x) reads if f.requires(x) then f.reads(f(x)) else {} @@ -29,7 +29,7 @@ method WithReads() { } -function method Twice_bad(f : A -> A): A -> A +function method Twice_bad<A>(f : A -> A): A -> A { x requires f.requires(x) && f.requires(f(x)) reads f.reads(x) + f.reads(f(x)) diff --git a/Test/hofs/Twice.dfy.expect b/Test/hofs/Twice.dfy.expect index 5ba4b47b..0ce2450c 100644 --- a/Test/hofs/Twice.dfy.expect +++ b/Test/hofs/Twice.dfy.expect @@ -1,11 +1,11 @@ -Twice.dfy(27,22): Error: assertion violation
+Twice.dfy(27,21): Error: assertion violation
Execution trace:
(0,0): anon0
Twice.dfy(23,12): anon3_Else
-Twice.dfy(35,32): Error: possible violation of function precondition
+Twice.dfy(35,31): Error: possible violation of function precondition
Execution trace:
(0,0): anon0
- (0,0): anon9_Else
- (0,0): anon10_Then
+ (0,0): anon10_Else
+ (0,0): anon11_Then
Dafny program verifier finished with 4 verified, 2 errors
diff --git a/Test/hofs/VectorUpdate.dfy b/Test/hofs/VectorUpdate.dfy index 96edbe77..6fb25a87 100644 --- a/Test/hofs/VectorUpdate.dfy +++ b/Test/hofs/VectorUpdate.dfy @@ -1,28 +1,59 @@ -// RUN: %dafny /compile:3 "%s" > "%t" +// RUN: %dafny /compile:3 /autoTriggers:1 "%s" > "%t" // RUN: %diff "%s.expect" "%t" -method VectorUpdate(N: int, a : array<A>, f : (int,A) -> A) - requires a != null; - requires N == a.Length; - requires forall j :: 0 <= j < N ==> f.requires(j,a[j]); - requires forall j :: 0 <= j < N ==> a !in f.reads(j,a[j]); - modifies a; - ensures forall j :: 0 <= j < N ==> a[j] == f(j,old(a[j])); +// this is a rather verbose version of the VectorUpdate method +method VectorUpdate<A>(N: int, a : array<A>, f : (int,A) -> A) + requires a != null + requires N == a.Length + requires forall j :: 0 <= j < N ==> f.requires(j,a[j]) + requires forall j :: 0 <= j < N ==> a !in f.reads(j,a[j]) + modifies a + ensures forall j :: 0 <= j < N ==> a[j] == f(j,old(a[j])) { var i := 0; - while (i < N) - invariant 0 <= i <= N; - invariant forall j :: i <= j < N ==> f.requires(j,a[j]); - invariant forall j :: 0 <= j < N ==> f.requires(j,old(a[j])); - invariant forall j :: i <= j < N ==> a !in f.reads(j,a[j]); - invariant forall j :: i <= j < N ==> a[j] == old(a[j]); - invariant forall j :: 0 <= j < i ==> a[j] == f(j,old(a[j])); + while i < N + invariant 0 <= i <= N + invariant forall j :: i <= j < N ==> f.requires(j,a[j]) + invariant forall j :: 0 <= j < N ==> f.requires(j,old(a[j])) + invariant forall j :: i <= j < N ==> a !in f.reads(j,a[j]) + invariant forall j :: i <= j < N ==> a[j] == old(a[j]) + invariant forall j :: 0 <= j < i ==> a[j] == f(j,old(a[j])) { a[i] := f(i,a[i]); i := i + 1; } } +// here's a shorter version of the method above +method VectorUpdate'<A>(a : array<A>, f : (int,A) -> A) + requires a != null + requires forall j :: 0 <= j < a.Length ==> a !in f.reads(j,a[j]) && f.requires(j,a[j]) + modifies a + ensures forall j :: 0 <= j < a.Length ==> a[j] == f(j,old(a[j])) +{ + var i := 0; + while i < a.Length + invariant 0 <= i <= a.Length + invariant forall j :: i <= j < a.Length ==> a[j] == old(a[j]) + invariant forall j :: 0 <= j < i ==> a[j] == f(j,old(a[j])) + { + a[i] := f(i,a[i]); + i := i + 1; + } +} + +// here's yet another version +method VectorUpdate''<A>(a : array<A>, f : (int,A) -> A) + requires a != null + requires forall j :: 0 <= j < a.Length ==> a !in f.reads(j,a[j]) && f.requires(j,a[j]) + modifies a + ensures forall j :: 0 <= j < a.Length ==> a[j] == f(j,old(a[j])) +{ + forall i | 0 <= i < a.Length { + a[i] := f(i,a[i]); + } +} + method Main() { var v := new int[10]; @@ -46,11 +77,11 @@ method Main() } method PrintArray(a : array<int>) - requires a != null; + requires a != null { var i := 0; - while (i < a.Length) { - if (i != 0) { + while i < a.Length { + if i != 0 { print ", "; } print a[i]; diff --git a/Test/hofs/VectorUpdate.dfy.expect b/Test/hofs/VectorUpdate.dfy.expect index b01ace00..18a7b110 100644 --- a/Test/hofs/VectorUpdate.dfy.expect +++ b/Test/hofs/VectorUpdate.dfy.expect @@ -1,5 +1,5 @@ -Dafny program verifier finished with 6 verified, 0 errors
+Dafny program verifier finished with 10 verified, 0 errors
Program compiled successfully
Running...
diff --git a/Test/hofs/WhileLoop.dfy b/Test/hofs/WhileLoop.dfy index f79562e9..2c91a8cc 100644 --- a/Test/hofs/WhileLoop.dfy +++ b/Test/hofs/WhileLoop.dfy @@ -34,14 +34,14 @@ method OneShot(n: int) { method HeapQuant(n: int) { var f : int -> int := x => x; - var i := new Ref<int>; + var i := new Ref; ghost var r := 0; i.val := 0; - while (i.val < n) - invariant forall u {:heapQuantifier} :: f.requires(u); - invariant forall u {:heapQuantifier} :: f.reads(u) == {}; + while i.val < n + invariant forall u :: f.requires(u); + invariant forall u :: f.reads(u) == {}; invariant r == i.val; - invariant forall u {:heapQuantifier} :: f(u) == u + r; + invariant forall u :: f(u) == u + r; { i.val, r := i.val + 1, r + 1; f := x => f(x) + 1; |