From 19c70cd0d7a65c46bcaafa66b13bde43316bc081 Mon Sep 17 00:00:00 2001 From: Clément Pit--Claudel Date: Wed, 19 Aug 2015 22:16:02 -0700 Subject: Add tests for quantifier splitting and trigger generation --- Test/triggers/loop-detection-is-not-too-strict.dfy | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 Test/triggers/loop-detection-is-not-too-strict.dfy (limited to 'Test/triggers/loop-detection-is-not-too-strict.dfy') diff --git a/Test/triggers/loop-detection-is-not-too-strict.dfy b/Test/triggers/loop-detection-is-not-too-strict.dfy new file mode 100644 index 00000000..c6722399 --- /dev/null +++ b/Test/triggers/loop-detection-is-not-too-strict.dfy @@ -0,0 +1,21 @@ +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %diff "%s.expect" "%t" + +// This test shows that the loop detection engine makes compromises when looking +// for subexpressions matching a trigger; in particular, it allows a +// subexpression to match a trigger without reporting a loop and without being +// equal to that trigger, as long as the only differences are variable + +predicate P(x: int, y: int) + +method Test() { + // P(x, y) and P(y, x) might look like they would cause a loop. Since they + // only differ by their variables, though, they won't raise flags. + assume forall x: int, y: int :: P(x, y) == P(y, x); + + // This works independent of extra parentheses: + assume forall x: int, y: int :: P(x, y) == (P(y, x)); + + // Contrast with the following: + assume forall x: int, y: int :: P(x, y) == P(x, y+1); +} -- cgit v1.2.3 From af6f23ba1869c0450c44e917becc48263b565327 Mon Sep 17 00:00:00 2001 From: Clément Pit--Claudel Date: Fri, 21 Aug 2015 09:39:49 -0700 Subject: Add /printTooltips to trigger tests --- .../function-applications-are-triggers.dfy | 2 +- .../function-applications-are-triggers.dfy.expect | 11 ++++++++ .../large-quantifiers-dont-break-dafny.dfy | 2 +- .../large-quantifiers-dont-break-dafny.dfy.expect | 2 ++ Test/triggers/loop-detection-is-not-too-strict.dfy | 2 +- .../loop-detection-is-not-too-strict.dfy.expect | 4 +++ .../loop-detection-messages--unit-tests.dfy | 2 +- .../loop-detection-messages--unit-tests.dfy.expect | 24 ++++++++++++++++++ .../nested-quantifiers-all-get-triggers.dfy | 2 +- .../nested-quantifiers-all-get-triggers.dfy.expect | 2 ++ ...ms-do-not-look-like-the-triggers-they-match.dfy | 2 +- .../splitting-triggers-recovers-expressivity.dfy | 2 +- ...tting-triggers-recovers-expressivity.dfy.expect | 29 ++++++++++++++++++++++ ...s-yields-better-precondition-related-errors.dfy | 2 +- Test/triggers/triggers-prevent-some-inlining.dfy | 2 +- .../triggers-prevent-some-inlining.dfy.expect | 5 ++++ Test/triggers/useless-triggers-are-removed.dfy | 2 +- 17 files changed, 87 insertions(+), 10 deletions(-) (limited to 'Test/triggers/loop-detection-is-not-too-strict.dfy') diff --git a/Test/triggers/function-applications-are-triggers.dfy b/Test/triggers/function-applications-are-triggers.dfy index 67ffe4e4..0aad9018 100644 --- a/Test/triggers/function-applications-are-triggers.dfy +++ b/Test/triggers/function-applications-are-triggers.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This file checks that function applications yield trigger candidates diff --git a/Test/triggers/function-applications-are-triggers.dfy.expect b/Test/triggers/function-applications-are-triggers.dfy.expect index 069e7767..7922e88d 100644 --- a/Test/triggers/function-applications-are-triggers.dfy.expect +++ b/Test/triggers/function-applications-are-triggers.dfy.expect @@ -1,2 +1,13 @@ +function-applications-are-triggers.dfy(9,9): Info: Selected triggers: {P.requires(f)} +function-applications-are-triggers.dfy(10,9): Info: For expression {P(f) ==> f.requires(10)}: + Selected triggers: + {f(10)}, {f.requires(10)}, {P(f)} +function-applications-are-triggers.dfy(10,9): Info: For expression {P(f) ==> f(10) == 0}: + Selected triggers: + {f(10)}, {f.requires(10)}, {P(f)} +function-applications-are-triggers.dfy(11,9): Info: Selected triggers: + {f(10)}, {f.requires(10)} +function-applications-are-triggers.dfy(12,5): Info: Selected triggers: + {g(x), f(x)}, {g(x), f.requires(x)}, {g(x)}, {f(x)}, {g.requires(x), f.requires(x)}, {g.requires(x)}, {f.requires(x)} Dafny program verifier finished with 2 verified, 0 errors diff --git a/Test/triggers/large-quantifiers-dont-break-dafny.dfy b/Test/triggers/large-quantifiers-dont-break-dafny.dfy index 8becae97..58eb56e1 100644 --- a/Test/triggers/large-quantifiers-dont-break-dafny.dfy +++ b/Test/triggers/large-quantifiers-dont-break-dafny.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This test ensures that the trigger collector (the routine that picks trigger diff --git a/Test/triggers/large-quantifiers-dont-break-dafny.dfy.expect b/Test/triggers/large-quantifiers-dont-break-dafny.dfy.expect index c90560b0..5e7c14b9 100644 --- a/Test/triggers/large-quantifiers-dont-break-dafny.dfy.expect +++ b/Test/triggers/large-quantifiers-dont-break-dafny.dfy.expect @@ -1,2 +1,4 @@ +large-quantifiers-dont-break-dafny.dfy(60,9): Info: Selected triggers: + {P49(x)}, {P48(x)}, {P47(x)}, {P46(x)}, {P45(x)}, {P44(x)}, {P43(x)}, {P42(x)}, {P41(x)}, {P40(x)}, {P39(x)}, {P38(x)}, {P37(x)}, {P36(x)}, {P35(x)}, {P34(x)}, {P33(x)}, {P32(x)}, {P31(x)}, {P30(x)}, {P29(x)}, {P28(x)}, {P27(x)}, {P26(x)}, {P25(x)}, {P24(x)}, {P23(x)}, {P22(x)}, {P21(x)}, {P20(x)}, {P19(x)}, {P18(x)}, {P17(x)}, {P16(x)}, {P15(x)}, {P14(x)}, {P13(x)}, {P12(x)}, {P11(x)}, {P10(x)}, {P9(x)}, {P8(x)}, {P7(x)}, {P6(x)}, {P5(x)}, {P4(x)}, {P3(x)}, {P2(x)}, {P1(x)}, {P0(x)} Dafny program verifier finished with 52 verified, 0 errors diff --git a/Test/triggers/loop-detection-is-not-too-strict.dfy b/Test/triggers/loop-detection-is-not-too-strict.dfy index c6722399..a5a30c81 100644 --- a/Test/triggers/loop-detection-is-not-too-strict.dfy +++ b/Test/triggers/loop-detection-is-not-too-strict.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This test shows that the loop detection engine makes compromises when looking diff --git a/Test/triggers/loop-detection-is-not-too-strict.dfy.expect b/Test/triggers/loop-detection-is-not-too-strict.dfy.expect index 29882da7..270f7e57 100644 --- a/Test/triggers/loop-detection-is-not-too-strict.dfy.expect +++ b/Test/triggers/loop-detection-is-not-too-strict.dfy.expect @@ -1,3 +1,7 @@ +loop-detection-is-not-too-strict.dfy(14,9): Info: Selected triggers: + {P(y, x)}, {P(x, y)} +loop-detection-is-not-too-strict.dfy(17,9): Info: Selected triggers: + {P(y, x)}, {P(x, y)} loop-detection-is-not-too-strict.dfy(20,9): Warning: Selected triggers: {P(x, y)} (loops with {P(x, y + 1)}) (!) Suppressing loops would leave this expression without triggers. diff --git a/Test/triggers/loop-detection-messages--unit-tests.dfy b/Test/triggers/loop-detection-messages--unit-tests.dfy index d5439e09..c1560317 100644 --- a/Test/triggers/loop-detection-messages--unit-tests.dfy +++ b/Test/triggers/loop-detection-messages--unit-tests.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This file is a series of basic tests for loop detection, focusing on the diff --git a/Test/triggers/loop-detection-messages--unit-tests.dfy.expect b/Test/triggers/loop-detection-messages--unit-tests.dfy.expect index 1ebc0bce..89d7265c 100644 --- a/Test/triggers/loop-detection-messages--unit-tests.dfy.expect +++ b/Test/triggers/loop-detection-messages--unit-tests.dfy.expect @@ -1,13 +1,37 @@ +loop-detection-messages--unit-tests.dfy(11,9): Info: Selected triggers: {f(f(i))} + Rejected triggers: {f(i)} (loops with {f(f(i))}) loop-detection-messages--unit-tests.dfy(12,9): Warning: Selected triggers: {f(i)} (loops with {f(i + 1)}) (!) Suppressing loops would leave this expression without triggers. +loop-detection-messages--unit-tests.dfy(13,9): Info: Selected triggers: {f(i)} (loops with {f(i + 1)}) +loop-detection-messages--unit-tests.dfy(15,9): Info: For expression {false ==> f(i) == f(i + 1)}: + Selected triggers: {g(i)} + Rejected triggers: {f(i)} (loops with {f(i + 1)}) +loop-detection-messages--unit-tests.dfy(15,9): Info: For expression {false ==> f(i) == g(i)}: + Selected triggers: + {g(i)}, {f(i)} loop-detection-messages--unit-tests.dfy(16,9): Warning: For expression {false ==> f(i) == f(i + 1)}: Selected triggers: {f(i)} (loops with {f(i + 1)}) (!) Suppressing loops would leave this expression without triggers. +loop-detection-messages--unit-tests.dfy(16,9): Info: For expression {false ==> f(i) == f(i)}: + Selected triggers: {f(i)} +loop-detection-messages--unit-tests.dfy(17,9): Info: For expression {false ==> f(i) == f(i + 1)}: + Selected triggers: {f(i)} (loops with {f(i + 1)}) +loop-detection-messages--unit-tests.dfy(17,9): Info: For expression {false ==> f(i) == f(i)}: + Selected triggers: {f(i)} +loop-detection-messages--unit-tests.dfy(19,9): Info: Selected triggers: {f(i)} loop-detection-messages--unit-tests.dfy(20,9): Warning: (!) No terms found to trigger on. +loop-detection-messages--unit-tests.dfy(21,9): Info: Not generating triggers for {false ==> f(i + 1) == 0}. +loop-detection-messages--unit-tests.dfy(23,9): Info: Selected triggers: {f(j), f(i)} loop-detection-messages--unit-tests.dfy(24,9): Warning: (!) No trigger covering all quantified variables found. +loop-detection-messages--unit-tests.dfy(25,9): Info: For expression {false ==> f(i) == f(i)}: + Selected triggers: {g(j), f(i)} +loop-detection-messages--unit-tests.dfy(25,9): Info: For expression {false ==> g(j) == 0}: + Selected triggers: {g(j), f(i)} loop-detection-messages--unit-tests.dfy(26,9): Warning: For expression {false ==> f(i) == f(i)}: (!) No trigger covering all quantified variables found. loop-detection-messages--unit-tests.dfy(26,9): Warning: For expression {false ==> g(j + 1) == 0}: (!) No trigger covering all quantified variables found. +loop-detection-messages--unit-tests.dfy(27,9): Info: Not generating triggers for {false ==> f(i) == f(i)}. +loop-detection-messages--unit-tests.dfy(28,9): Info: Not generating triggers for {false ==> f(i) == f(i)}. Dafny program verifier finished with 4 verified, 0 errors diff --git a/Test/triggers/nested-quantifiers-all-get-triggers.dfy b/Test/triggers/nested-quantifiers-all-get-triggers.dfy index c75cfab9..a55019db 100644 --- a/Test/triggers/nested-quantifiers-all-get-triggers.dfy +++ b/Test/triggers/nested-quantifiers-all-get-triggers.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This checks that nested quantifiers do get triggers, and that the parent diff --git a/Test/triggers/nested-quantifiers-all-get-triggers.dfy.expect b/Test/triggers/nested-quantifiers-all-get-triggers.dfy.expect index 069e7767..172f5607 100644 --- a/Test/triggers/nested-quantifiers-all-get-triggers.dfy.expect +++ b/Test/triggers/nested-quantifiers-all-get-triggers.dfy.expect @@ -1,2 +1,4 @@ +nested-quantifiers-all-get-triggers.dfy(8,17): Info: Selected triggers: {x in s} +nested-quantifiers-all-get-triggers.dfy(8,59): Info: Selected triggers: {y in s} Dafny program verifier finished with 2 verified, 0 errors diff --git a/Test/triggers/some-terms-do-not-look-like-the-triggers-they-match.dfy b/Test/triggers/some-terms-do-not-look-like-the-triggers-they-match.dfy index 7423e086..d7636ea2 100644 --- a/Test/triggers/some-terms-do-not-look-like-the-triggers-they-match.dfy +++ b/Test/triggers/some-terms-do-not-look-like-the-triggers-they-match.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This file shows how Dafny detects loops even for terms that are not literal diff --git a/Test/triggers/splitting-triggers-recovers-expressivity.dfy b/Test/triggers/splitting-triggers-recovers-expressivity.dfy index 79a0dc72..dd1bd81d 100644 --- a/Test/triggers/splitting-triggers-recovers-expressivity.dfy +++ b/Test/triggers/splitting-triggers-recovers-expressivity.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" predicate P(i: int) diff --git a/Test/triggers/splitting-triggers-recovers-expressivity.dfy.expect b/Test/triggers/splitting-triggers-recovers-expressivity.dfy.expect index 8d7ff4ef..63cbc476 100644 --- a/Test/triggers/splitting-triggers-recovers-expressivity.dfy.expect +++ b/Test/triggers/splitting-triggers-recovers-expressivity.dfy.expect @@ -1,3 +1,32 @@ +splitting-triggers-recovers-expressivity.dfy(12,10): Info: Selected triggers: {Q(i)} + Rejected triggers: {P(i)} (loops with {P(i + 1)}) +splitting-triggers-recovers-expressivity.dfy(17,11): Info: Selected triggers: {Q(j)} + Rejected triggers: {P(j)} (loops with {P(j + 1)}) +splitting-triggers-recovers-expressivity.dfy(26,10): Info: Selected triggers: {Q(i)} + Rejected triggers: {P(i)} (loops with {P(i + 1)}) +splitting-triggers-recovers-expressivity.dfy(33,11): Info: Selected triggers: {Q(j)} + Rejected triggers: {P(j)} (loops with {P(j + 1)}) +splitting-triggers-recovers-expressivity.dfy(44,10): Info: For expression {P(i)}: + Selected triggers: + {Q(i)}, {P(i)} +splitting-triggers-recovers-expressivity.dfy(44,10): Info: For expression {!Q(i)}: + Selected triggers: + {Q(i)}, {P(i)} +splitting-triggers-recovers-expressivity.dfy(44,10): Info: For expression {P(i + 1)}: + Selected triggers: {Q(i)} + Rejected triggers: {P(i)} (loops with {P(i + 1)}) +splitting-triggers-recovers-expressivity.dfy(49,11): Info: For expression {j >= 0 ==> P(j)}: + Selected triggers: + {Q(j)}, {P(j)} +splitting-triggers-recovers-expressivity.dfy(49,11): Info: For expression {j >= 0 ==> Q(j) ==> P(j + 1)}: + Selected triggers: {Q(j)} + Rejected triggers: {P(j)} (loops with {P(j + 1)}) +splitting-triggers-recovers-expressivity.dfy(58,11): Info: For expression {i >= 0 ==> Q(i)}: + Selected triggers: + {P(i)}, {Q(i)} +splitting-triggers-recovers-expressivity.dfy(58,11): Info: For expression {i >= 0 ==> P(i) ==> P(i + 1)}: + Selected triggers: + {P(i)} (loops with {P(i + 1)}), {Q(i)} splitting-triggers-recovers-expressivity.dfy(12,63): Error BP5003: A postcondition might not hold on this return path. splitting-triggers-recovers-expressivity.dfy(12,10): Related location: This is the postcondition that might not hold. Execution trace: diff --git a/Test/triggers/splitting-triggers-yields-better-precondition-related-errors.dfy b/Test/triggers/splitting-triggers-yields-better-precondition-related-errors.dfy index f25a624e..20e90843 100644 --- a/Test/triggers/splitting-triggers-yields-better-precondition-related-errors.dfy +++ b/Test/triggers/splitting-triggers-yields-better-precondition-related-errors.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This tests shows that, since quantifiers are split, it becomes possible to know more precisely what part of a precondition did not hold at the call site. diff --git a/Test/triggers/triggers-prevent-some-inlining.dfy b/Test/triggers/triggers-prevent-some-inlining.dfy index 04b8051c..90af62a3 100644 --- a/Test/triggers/triggers-prevent-some-inlining.dfy +++ b/Test/triggers/triggers-prevent-some-inlining.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This file looks at the interactions between inlining and triggers. The diff --git a/Test/triggers/triggers-prevent-some-inlining.dfy.expect b/Test/triggers/triggers-prevent-some-inlining.dfy.expect index 73ba063c..4c24893e 100644 --- a/Test/triggers/triggers-prevent-some-inlining.dfy.expect +++ b/Test/triggers/triggers-prevent-some-inlining.dfy.expect @@ -1,2 +1,7 @@ +triggers-prevent-some-inlining.dfy(17,2): Info: Selected triggers: {sum(a, b)} +triggers-prevent-some-inlining.dfy(24,10): Info: Some instances of this call cannot safely be inlined. +triggers-prevent-some-inlining.dfy(25,10): Info: Some instances of this call cannot safely be inlined. +triggers-prevent-some-inlining.dfy(24,10): Info: Some instances of this call cannot safely be inlined. +triggers-prevent-some-inlining.dfy(25,10): Info: Some instances of this call cannot safely be inlined. Dafny program verifier finished with 4 verified, 0 errors diff --git a/Test/triggers/useless-triggers-are-removed.dfy b/Test/triggers/useless-triggers-are-removed.dfy index 16458e41..658890f2 100644 --- a/Test/triggers/useless-triggers-are-removed.dfy +++ b/Test/triggers/useless-triggers-are-removed.dfy @@ -1,4 +1,4 @@ -// RUN: %dafny /printTooltips /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 "%s" > "%t" +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" // RUN: %diff "%s.expect" "%t" // This file ensures that Dafny does get rid of redundant triggers before -- cgit v1.2.3 From 1e725f0c9382a3dd8be109d160581868c9567f61 Mon Sep 17 00:00:00 2001 From: Clément Pit--Claudel Date: Thu, 27 Aug 2015 21:25:06 -0700 Subject: Further relax the loop detection conditions Mismatches are now allowed up to expressions not involving any of the bound variables of the quantifier under inspection. --- Source/Dafny/Triggers/QuantifiersCollection.cs | 7 +++++-- Source/Dafny/Triggers/TriggerExtensions.cs | 23 +++++++++++++++++----- Source/Dafny/Triggers/TriggersCollector.cs | 3 ++- Test/triggers/loop-detection-is-not-too-strict.dfy | 21 +++++++++++++++++++- .../loop-detection-is-not-too-strict.dfy.expect | 17 ++++++++++++---- 5 files changed, 58 insertions(+), 13 deletions(-) (limited to 'Test/triggers/loop-detection-is-not-too-strict.dfy') diff --git a/Source/Dafny/Triggers/QuantifiersCollection.cs b/Source/Dafny/Triggers/QuantifiersCollection.cs index b77afccb..50458ab7 100644 --- a/Source/Dafny/Triggers/QuantifiersCollection.cs +++ b/Source/Dafny/Triggers/QuantifiersCollection.cs @@ -101,8 +101,11 @@ namespace Microsoft.Dafny.Triggers { // [∀ x {f(x), f(f(x))} ⋅ f(x) = f(f(x))] is not a loop). And we even // ignore terms that almost match a trigger term, modulo a single variable // (this ensures that [∀ x y {a(x, y)} ⋅ a(x, y) == a(y, x)] is not a loop). - // The last thing that we ignore is matching variables against constants, - // to ensure that P(x) is not flagged as looping with P(0). + // In addition, we ignore cases where the only differences between a trigger + // and a trigger match are places where a variable is replaced with an + // expression whose free variables do not intersect that of the quantifier + // in which that expression is found. For examples of this behavious, see + // triggers/literals-do-not-cause-loops. // This ignoring logic is implemented by the CouldCauseLoops method. foreach (var q in quantifiers) { diff --git a/Source/Dafny/Triggers/TriggerExtensions.cs b/Source/Dafny/Triggers/TriggerExtensions.cs index dccd996d..d4a822a8 100644 --- a/Source/Dafny/Triggers/TriggerExtensions.cs +++ b/Source/Dafny/Triggers/TriggerExtensions.cs @@ -31,9 +31,15 @@ namespace Microsoft.Dafny.Triggers { return ExprExtensions.ExpressionEq(t1.Expr, t2.Expr); } - internal bool CouldCauseLoops(List terms) { + /// + /// This method checks whether this match could actually cause a loop, given a set of terms participating in a trigger; + /// to compute an answer, we match the Expr of this match against the Exprs of each of these term, allowing for harmless + /// variations. If any of these tests does match, this term likely won't cause a loop. + /// The boundVars list is useful to determine that forall x :: P(x) == P(y+z) does not loop. + /// + internal bool CouldCauseLoops(List terms, ISet boundVars) { var expr = Expr; - return !terms.Any(term => term.Expr.ExpressionEqModuloVariableNamesAndConstants(expr)); + return !terms.Any(term => term.Expr.ExpressionEqModuloExpressionsNotInvolvingBoundVariables(expr, boundVars)); } } @@ -79,15 +85,22 @@ namespace Microsoft.Dafny.Triggers { return ShallowEq_Top(expr1, expr2) && TriggerUtils.SameLists(expr1.SubExpressions, expr2.SubExpressions, (e1, e2) => ExpressionEq(e1, e2)); } - internal static bool ExpressionEqModuloVariableNamesAndConstants(this Expression expr1, Expression expr2) { + internal static bool ExpressionEqModuloExpressionsNotInvolvingBoundVariables(this Expression expr1, Expression expr2, ISet boundVars) { expr1 = expr1.Resolved; expr2 = expr2.Resolved; if (expr1 is IdentifierExpr) { - return expr2 is IdentifierExpr || expr2 is LiteralExpr; + if (expr2 is IdentifierExpr) { + return true; + } else { + var freeInE2 = Translator.ComputeFreeVariables(expr2); + freeInE2.IntersectWith(boundVars); + return !freeInE2.Any(); + } } - return ShallowEq_Top(expr1, expr2) && TriggerUtils.SameLists(expr1.SubExpressions, expr2.SubExpressions, (e1, e2) => ExpressionEqModuloVariableNamesAndConstants(e1, e2)); + return ShallowEq_Top(expr1, expr2) && TriggerUtils.SameLists(expr1.SubExpressions, + expr2.SubExpressions, (e1, e2) => ExpressionEqModuloExpressionsNotInvolvingBoundVariables(e1, e2, boundVars)); } internal static bool MatchesTrigger(this Expression expr, Expression trigger, ISet holes, Dictionary bindings) { diff --git a/Source/Dafny/Triggers/TriggersCollector.cs b/Source/Dafny/Triggers/TriggersCollector.cs index d78bcb9e..cc3b1978 100644 --- a/Source/Dafny/Triggers/TriggersCollector.cs +++ b/Source/Dafny/Triggers/TriggersCollector.cs @@ -69,7 +69,8 @@ namespace Microsoft.Dafny.Triggers { internal IEnumerable LoopingSubterms(QuantifierExpr quantifier) { Contract.Requires(quantifier.SplitQuantifier == null); // Don't call this on a quantifier with a Split clause: it's not a real quantifier var matchingSubterms = this.MatchingSubterms(quantifier); - return matchingSubterms.Where(tm => tm.CouldCauseLoops(Terms)); + var boundVars = new HashSet(quantifier.BoundVars); + return matchingSubterms.Where(tm => tm.CouldCauseLoops(Terms, boundVars)); } internal List MatchingSubterms(QuantifierExpr quantifier) { diff --git a/Test/triggers/loop-detection-is-not-too-strict.dfy b/Test/triggers/loop-detection-is-not-too-strict.dfy index a5a30c81..81f764ad 100644 --- a/Test/triggers/loop-detection-is-not-too-strict.dfy +++ b/Test/triggers/loop-detection-is-not-too-strict.dfy @@ -7,8 +7,9 @@ // equal to that trigger, as long as the only differences are variable predicate P(x: int, y: int) +predicate Q(x: int) -method Test() { +method Test(z: int) { // P(x, y) and P(y, x) might look like they would cause a loop. Since they // only differ by their variables, though, they won't raise flags. assume forall x: int, y: int :: P(x, y) == P(y, x); @@ -18,4 +19,22 @@ method Test() { // Contrast with the following: assume forall x: int, y: int :: P(x, y) == P(x, y+1); + + // The following examples were made legal after an exchange where Chris + // pointed examples in the IronClad sources where things like this were + // incorrectly flagged. + assert forall x :: true || Q(x) || Q(0); + assert forall x :: true || Q(x) || Q(z); + assert forall x :: true || P(x, 1) || P(x, z); + + // Support for the following was added following a discussion with Rustan; in + // the second one the expression `if z > 1 then z else 3 * z + 1` is not + // directly a constant expression, but it does not involve x, so it's ok: + assert forall x :: true || Q(x) || Q(0+1); + assert forall x :: true || Q(x) || Q(if z > 1 then z else 3 * z + 1); + // Sanity check: + assert forall x :: true || Q(x) || Q(if z > 1 then x else 3 * z + 1); + + // WISH: It might also be good to zeta-reduce before loop detection. + assert forall x :: true || Q(x) || (var xx := x+1; Q(xx)); } diff --git a/Test/triggers/loop-detection-is-not-too-strict.dfy.expect b/Test/triggers/loop-detection-is-not-too-strict.dfy.expect index 6f5ed3d7..705c2a8c 100644 --- a/Test/triggers/loop-detection-is-not-too-strict.dfy.expect +++ b/Test/triggers/loop-detection-is-not-too-strict.dfy.expect @@ -1,8 +1,17 @@ -loop-detection-is-not-too-strict.dfy(14,9): Info: Selected triggers: +loop-detection-is-not-too-strict.dfy(15,9): Info: Selected triggers: {P(y, x)}, {P(x, y)} -loop-detection-is-not-too-strict.dfy(17,9): Info: Selected triggers: +loop-detection-is-not-too-strict.dfy(18,9): Info: Selected triggers: {P(y, x)}, {P(x, y)} -loop-detection-is-not-too-strict.dfy(20,9): Warning: Selected triggers: {P(x, y)} (may loop with {P(x, y + 1)}) +loop-detection-is-not-too-strict.dfy(21,9): Warning: Selected triggers: {P(x, y)} (may loop with {P(x, y + 1)}) (!) Suppressing loops would leave this expression without triggers. +loop-detection-is-not-too-strict.dfy(26,9): Info: Selected triggers: {Q(x)} +loop-detection-is-not-too-strict.dfy(27,9): Info: Selected triggers: {Q(x)} +loop-detection-is-not-too-strict.dfy(28,9): Info: Selected triggers: + {P(x, z)}, {P(x, 1)} +loop-detection-is-not-too-strict.dfy(33,9): Info: Selected triggers: {Q(x)} +loop-detection-is-not-too-strict.dfy(34,9): Info: Selected triggers: {Q(x)} +loop-detection-is-not-too-strict.dfy(36,9): Warning: Selected triggers: {Q(x)} (may loop with {Q(if z > 1 then x else 3 * z + 1)}) + (!) Suppressing loops would leave this expression without triggers. +loop-detection-is-not-too-strict.dfy(39,9): Info: Selected triggers: {Q(x)} -Dafny program verifier finished with 3 verified, 0 errors +Dafny program verifier finished with 4 verified, 0 errors -- cgit v1.2.3