diff options
author | ajreynol <andrew.j.reynolds@gmail.com> | 2017-07-10 14:06:52 -0500 |
---|---|---|
committer | ajreynol <andrew.j.reynolds@gmail.com> | 2017-07-10 14:07:11 -0500 |
commit | f3590092818d9eab9d961ea602093029ff472a85 (patch) | |
tree | 1401f00df0d9659ba2321ea2088fe0c3f4de9f52 /test/regress/regress1 | |
parent | d598a9644862d176632071bca8448765d9cc3cc1 (diff) |
Merge datatype shared selectors/sygus comp 2017 branch. Modify the datatypes decision procedure to share selectors of the same type across multiple constructors. Major rewrite of the SyGuS solver. Adds several new strategies for I/O example problems (PBE) and invariant synthesis. Major simplifications to sygus parsing and synthesis conjecture representation. Do not support check-synth in portfolio. Add sygus regressions.
Diffstat (limited to 'test/regress/regress1')
-rw-r--r-- | test/regress/regress1/sygus/Makefile.am | 9 | ||||
-rw-r--r-- | test/regress/regress1/sygus/VC22_a.sy | 60 | ||||
-rw-r--r-- | test/regress/regress1/sygus/array_sum_dd.sy | 11 | ||||
-rw-r--r-- | test/regress/regress1/sygus/icfp_easy_mt_ite.sy | 32 | ||||
-rw-r--r-- | test/regress/regress1/sygus/inv_gen_fig8.sy | 46 | ||||
-rw-r--r-- | test/regress/regress1/sygus/inv_gen_n_c11.sy | 36 | ||||
-rw-r--r-- | test/regress/regress1/sygus/mpg_guard1-dd.sy | 27 | ||||
-rw-r--r-- | test/regress/regress1/sygus/three.sy | 30 | ||||
-rw-r--r-- | test/regress/regress1/sygus/unbdd_inv_gen_ex7.sy | 40 |
9 files changed, 290 insertions, 1 deletions
diff --git a/test/regress/regress1/sygus/Makefile.am b/test/regress/regress1/sygus/Makefile.am index 2dff1f1da..f1f1c1342 100644 --- a/test/regress/regress1/sygus/Makefile.am +++ b/test/regress/regress1/sygus/Makefile.am @@ -18,7 +18,14 @@ endif # put it below in "TESTS +=" TESTS = \ hd-sdiv.sy \ - stopwatch-bt.sy + stopwatch-bt.sy \ + array_sum_dd.sy \ + mpg_guard1-dd.sy \ + VC22_a.sy \ + inv_gen_n_c11.sy \ + unbdd_inv_gen_ex7.sy \ + icfp_easy_mt_ite.sy \ + three.sy EXTRA_DIST = $(TESTS) diff --git a/test/regress/regress1/sygus/VC22_a.sy b/test/regress/regress1/sygus/VC22_a.sy new file mode 100644 index 000000000..75bed6a28 --- /dev/null +++ b/test/regress/regress1/sygus/VC22_a.sy @@ -0,0 +1,60 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic LIA) + +(synth-fun f ((x1 Int) (x2 Int)) Int + ((Start Int (0 1 x1 x2 + (ite StartBool Start Start))) + (StartBool Bool ((= Start Start))))) + +(define-fun vmin () Int 1) +(define-fun vmax () Int 2) + +(define-fun Zero ((v Int)) Bool + (= v 0)) + +(define-fun InV1 ((v Int)) Bool + (and (>= v vmin) (<= v vmax))) + +(define-fun InV2 ((v1 Int) (v2 Int)) Bool + (and (and (and (>= v1 vmin) (<= v1 vmax)) + (>= v2 vmin)) (<= v2 vmax))) + +(define-fun InVorZero ((v Int)) Bool + (or (InV1 v) (Zero v))) + + +(define-fun UnsafeSame ((x1 Int) (x2 Int) (v1 Int) (v2 Int)) Bool + (or (and (>= x1 x2) (>= (+ x2 v2) (+ x1 v1))) + (and (>= x2 x1) (>= (+ x1 v1) (+ x2 v2))))) + +(define-fun Unsafe ((x1 Int) (x2 Int) (v1 Int) (v2 Int)) Bool + (UnsafeSame x1 x2 v1 v2)) + +(define-fun BadSame ((x1 Int) (x2 Int)) Bool + (= x1 x2)) + +(define-fun Bad ((x1 Int) (x2 Int)) Bool + (BadSame x1 x2)) + +(declare-var x1 Int) +(declare-var x2 Int) +(declare-var v1 Int) +(declare-var v2 Int) + +(constraint (InVorZero (f x1 x2))) + +(constraint (or (or (not (InV2 v1 v2)) + (Zero (f x1 x2))) + (and (not (Unsafe x1 x2 (f x1 x2) (f x1 x2))) + (not (Zero (f (+ x1 (f x1 x2)) (+ x2 (f x1 x2)))))))) + +(constraint (or (or (not (InV2 v1 v2)) + (or (Unsafe x1 x2 v1 v2) + (Zero (f (+ x1 v1) (+ x2 v2))))) + (not (Zero (f x1 x2))))) + +(constraint (or (Bad x1 x2) (not (Zero (f x1 x2))))) + +(check-synth) + diff --git a/test/regress/regress1/sygus/array_sum_dd.sy b/test/regress/regress1/sygus/array_sum_dd.sy new file mode 100644 index 000000000..dacd7347d --- /dev/null +++ b/test/regress/regress1/sygus/array_sum_dd.sy @@ -0,0 +1,11 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic LIA) +(synth-fun findSum ( (y1 Int) (y2 Int) )Int ( +(Start Int ( 0 1 y1 y2 (+ Start Start) (ite BoolExpr Start Start))) +(BoolExpr Bool ((< Start Start) (<= Start Start))))) +(declare-var x1 Int) +(declare-var x2 Int) +(constraint (=> (> (+ x1 x2) 0) (= (findSum x1 x2 ) x1))) +(constraint (=> (<= (+ x1 x2) 0) (= (findSum x1 x2 ) x2))) +(check-synth) diff --git a/test/regress/regress1/sygus/icfp_easy_mt_ite.sy b/test/regress/regress1/sygus/icfp_easy_mt_ite.sy new file mode 100644 index 000000000..b7428fd51 --- /dev/null +++ b/test/regress/regress1/sygus/icfp_easy_mt_ite.sy @@ -0,0 +1,32 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic BV) + +(define-fun shr1 ((x (BitVec 64))) (BitVec 64) (bvlshr x #x0000000000000001)) +(define-fun shr4 ((x (BitVec 64))) (BitVec 64) (bvlshr x #x0000000000000004)) +(define-fun shr16 ((x (BitVec 64))) (BitVec 64) (bvlshr x #x0000000000000010)) +(define-fun shl1 ((x (BitVec 64))) (BitVec 64) (bvshl x #x0000000000000001)) +(define-fun if0 ((x (BitVec 64)) (y (BitVec 64)) (z (BitVec 64))) (BitVec 64) (ite (= x #x0000000000000001) y z)) + +(synth-fun f ( (x (BitVec 64))) (BitVec 64) +( + +(Start (BitVec 64) (#x0000000000000000 #x0000000000000001 x (bvnot Start) + (shl1 Start) + (shr1 Start) + (shr4 Start) + (shr16 Start) + (bvand Start Start) + (bvor Start Start) + (bvxor Start Start) + (bvadd Start Start) + (ite StartBool Start Start) + )) +(StartBool Bool ((= Start #x0000000000000001))) +) +) +(constraint (= (f #x6E393354DFFAAB51) #xC8E366559002AA57)) + +(constraint (= (f #xE5D371D100002E8A) #x0000000000000000)) + +(check-synth) diff --git a/test/regress/regress1/sygus/inv_gen_fig8.sy b/test/regress/regress1/sygus/inv_gen_fig8.sy new file mode 100644 index 000000000..5496f3c0a --- /dev/null +++ b/test/regress/regress1/sygus/inv_gen_fig8.sy @@ -0,0 +1,46 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic LIA) +(synth-fun inv ((l Int)) Bool + ( + (Start Bool ((and AtomicFormula AtomicFormula) + (or AtomicFormula AtomicFormula))) + (AtomicFormula Bool ((<= Sum Const) (= Sum Const))) + (Sum Int ((+ Term Term))) + (Term Int ((* Sign Var))) + (Sign Int (0 1 -1)) + (Var Int (l)) + (Const Int (-3 -2 -1 0 1 2 3)) + ) +) + +(define-fun implies ((b1 Bool) (b2 Bool)) Bool (or (not b1) b2)) +(define-fun and3 ((b1 Bool) (b2 Bool) (b3 Bool)) Bool (and (and b1 b2) b3)) +(define-fun and4 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool)) Bool (and (and3 b1 b2 b3) b4)) +(define-fun and5 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool)) Bool (and (and4 b1 b2 b3 b4) b5)) +(define-fun and6 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool) (b6 Bool)) Bool (and (and5 b1 b2 b3 b4 b5) b6)) +(define-fun or3 ((b1 Bool) (b2 Bool) (b3 Bool)) Bool (or (or b1 b2) b3)) +(define-fun or4 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool)) Bool (or (or3 b1 b2 b3) b4)) +(define-fun or5 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool)) Bool (or (or4 b1 b2 b3 b4) b5)) + +(declare-var x0 Int) +(declare-var x1 Int) +(declare-var x2 Int) +(declare-var x3 Int) +(declare-var x4 Int) +(declare-var l Int) +(declare-var x0p Int) +(declare-var x1p Int) +(declare-var x2p Int) +(declare-var x3p Int) +(declare-var x4p Int) + +(constraint (implies (and6 (= l 0) (or (= x0p (+ x0 1)) (= x0p (- x0 1))) + (or (= x1p (+ x1 1)) (= x1p (- x1 1))) + (or (= x2p (+ x2 1)) (= x2p (- x2 1))) + (or (= x3p (+ x3 1)) (= x3p (- x3 1))) + (or (= x4p (+ x4 1)) (= x4p (- x4 1)))) + (inv l))) +(constraint (implies (and (inv l) (not (= l 0))) false)) + +(check-synth) diff --git a/test/regress/regress1/sygus/inv_gen_n_c11.sy b/test/regress/regress1/sygus/inv_gen_n_c11.sy new file mode 100644 index 000000000..946f284cb --- /dev/null +++ b/test/regress/regress1/sygus/inv_gen_n_c11.sy @@ -0,0 +1,36 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic LIA) +(synth-fun inv ((i Int) (l Int)) Bool + ( + (Start Bool ((and AtomicFormula AtomicFormula) + (or AtomicFormula AtomicFormula))) + (AtomicFormula Bool ((<= Sum Const) (= Sum Const))) + (Sum Int ((+ Term Term))) + (Term Int ((* Sign Var))) + (Sign Int (0 1 -1)) + (Var Int (i l)) + (Const Int (-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7)) + ) +) + +(define-fun implies ((b1 Bool) (b2 Bool)) Bool (or (not b1) b2)) +(define-fun and3 ((b1 Bool) (b2 Bool) (b3 Bool)) Bool (and (and b1 b2) b3)) +(define-fun and4 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool)) Bool (and (and3 b1 b2 b3) b4)) +(define-fun and5 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool)) Bool (and (and4 b1 b2 b3 b4) b5)) +(define-fun and6 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool) (b6 Bool)) Bool (and (and5 b1 b2 b3 b4 b5) b6)) +(define-fun or3 ((b1 Bool) (b2 Bool) (b3 Bool)) Bool (or (or b1 b2) b3)) +(define-fun or4 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool)) Bool (or (or3 b1 b2 b3) b4)) +(define-fun or5 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool)) Bool (or (or4 b1 b2 b3 b4) b5)) + +(declare-var i Int) +(declare-var l Int) +(declare-var i1 Int) +(declare-var l1 Int) +(declare-var l2 Int) + +(constraint (implies (= l 0) (inv i l))) +(constraint (implies (and5 (inv i l) (implies (= l 4) (= l1 0)) (implies (not (= l 4)) (= l1 l)) (not (or (< l1 0) (>= l1 5))) (= l2 (+ l1 1))) (inv i l2))) +(constraint (implies (and4 (inv i l) (implies (= l 4) (= l1 0)) (implies (not (= l 4)) (= l1 l)) (or (< l1 0) (>= l1 5))) false)) + +(check-synth) diff --git a/test/regress/regress1/sygus/mpg_guard1-dd.sy b/test/regress/regress1/sygus/mpg_guard1-dd.sy new file mode 100644 index 000000000..e574f7eb6 --- /dev/null +++ b/test/regress/regress1/sygus/mpg_guard1-dd.sy @@ -0,0 +1,27 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic LIA) + +(synth-fun eq1 ( (x Int) (y Int) ) Int + ((Start Int (x + y + 0 + (+ Start Start) + (- Start Start) + (ite StartBool Start Start))) + (StartBool Bool ((and StartBool StartBool) + (<= Start Start) + (= Start Start))))) + +(define-fun iteB (( b1 Bool ) (b2 Bool ) (b3 Bool )) Bool (or (and b1 b2) (and (not b1) b3))) + +(declare-var x Int) +(declare-var y Int) + +(constraint (iteB (>= x 0) + (= (eq1 x y) (+ x x)) + (= (eq1 x y) x) +)) + +(check-synth) + diff --git a/test/regress/regress1/sygus/three.sy b/test/regress/regress1/sygus/three.sy new file mode 100644 index 000000000..6e2ce3a2c --- /dev/null +++ b/test/regress/regress1/sygus/three.sy @@ -0,0 +1,30 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth + +(set-logic LIA) + +(synth-fun f ((x Int)) Int + ((Start Int ( + x + 3 + 7 + 10 + (* Start Start) + (mod Start Start))))) + +(declare-var x Int) + +(constraint (= (f x) (f (+ x 10)))) +(constraint (= (f 1) 3)) +(constraint (= (f 2) 6)) +(constraint (= (f 3) 9)) +(constraint (= (f 4) 2)) +(constraint (= (f 5) 5)) +(constraint (= (f 6) 8)) +(constraint (= (f 7) 1)) +(constraint (= (f 8) 4)) +(constraint (= (f 9) 7)) +(constraint (= (f 0) 0)) + +(check-synth) + diff --git a/test/regress/regress1/sygus/unbdd_inv_gen_ex7.sy b/test/regress/regress1/sygus/unbdd_inv_gen_ex7.sy new file mode 100644 index 000000000..f840fa519 --- /dev/null +++ b/test/regress/regress1/sygus/unbdd_inv_gen_ex7.sy @@ -0,0 +1,40 @@ +; EXPECT: unsat +; COMMAND-LINE: --no-dump-synth +(set-logic LIA) +(synth-fun inv ((i Int) (y Int) (l Int)) Bool + ( + (Start Bool ((and AtomicFormula AtomicFormula) + (or AtomicFormula AtomicFormula))) + (AtomicFormula Bool ((<= Sum Const) (= Sum Const))) + (Sum Int ((+ Term Term))) + (Term Int ((* Sign Var))) + (Sign Int (0 1 -1)) + (Var Int (i y l)) + (Const Int ((+ Const Const) (- Const Const) 0 1)) + ) +) + +(define-fun implies ((b1 Bool) (b2 Bool)) Bool (or (not b1) b2)) +(define-fun and3 ((b1 Bool) (b2 Bool) (b3 Bool)) Bool (and (and b1 b2) b3)) +(define-fun and4 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool)) Bool (and (and3 b1 b2 b3) b4)) +(define-fun and5 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool)) Bool (and (and4 b1 b2 b3 b4) b5)) +(define-fun and6 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool) (b6 Bool)) Bool (and (and5 b1 b2 b3 b4 b5) b6)) +(define-fun or3 ((b1 Bool) (b2 Bool) (b3 Bool)) Bool (or (or b1 b2) b3)) +(define-fun or4 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool)) Bool (or (or3 b1 b2 b3) b4)) +(define-fun or5 ((b1 Bool) (b2 Bool) (b3 Bool) (b4 Bool) (b5 Bool)) Bool (or (or4 b1 b2 b3 b4) b5)) + +(declare-var i Int) +(declare-var x Int) +(declare-var y Int) +(declare-var l Int) +(declare-var i1 Int) +(declare-var x1 Int) +(declare-var y1 Int) +(declare-var l1 Int) + +(constraint (implies (or3 (< x 0) (< y 0) (> y x)) true)) +(constraint (implies (and3 (not (or3 (< x 0) (< y 0) (> y x))) (= l x) (= i 0)) (inv i y l))) +(constraint (implies (and4 (inv i y l) (< i y) (not (or (< i 0) (>= i l))) (= i1 (+ i 1))) (inv i1 y l))) +(constraint (implies (and3 (inv i y l) (< i y) (or (< i 0) (>= i l))) false)) + +(check-synth) |