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.

12 files changed, 241 insertions, 1 deletions

diff --git a/test/regress/regress0/sygus/General_plus10.sy b/test/regress/regress0/sygus/General_plus10.sy
new file mode 100755
index 000000000..ee26fac79
--- /dev/null
+++ b/test/regress/regress0/sygus/General_plus10.sy
@@ -0,0 +1,11 @@
+; EXPECT: unsat
+; COMMAND-LINE: --cegqi-si=all --no-dump-synth
+(set-logic LIA)
+
+(synth-fun fb () Int ((Start Int ((Constant Int)))))
+(synth-fun fc () Int ((Start Int ((Constant Int)))))
+
+(constraint (= fc (+ fb 10))) 
+
+(check-synth)
+
diff --git a/test/regress/regress0/sygus/Makefile.am b/test/regress/regress0/sygus/Makefile.am
index 0764b5d77..0786c3f31 100644
--- a/test/regress/regress0/sygus/Makefile.am
+++ b/test/regress/regress0/sygus/Makefile.am
@@ -50,7 +50,19 @@ TESTS = commutative.sy \
         no-mention.sy \
         max2-univ.sy \
         strings-small.sy \
-        strings-unconstrained.sy
+        strings-unconstrained.sy \
+        tl-type-4x.sy \
+        tl-type-0.sy \
+        fg_polynomial3.sy \
+        icfp_14.12.sy \
+        strings-trivial-simp.sy \
+        icfp_easy-ite.sy \
+        strings-template-infer.sy \
+        strings-trivial.sy \
+        General_plus10.sy \
+        qe.sy \
+        cggmp.sy
+
 
 # sygus tests currently taking too long for make regress
 EXTRA_DIST = $(TESTS) \
diff --git a/test/regress/regress0/sygus/cggmp.sy b/test/regress/regress0/sygus/cggmp.sy
new file mode 100644
index 000000000..1ae1f53c0
--- /dev/null
+++ b/test/regress/regress0/sygus/cggmp.sy
@@ -0,0 +1,23 @@
+; EXPECT: unsat
+; COMMAND-LINE: --sygus-inv-templ=pre --no-dump-synth
+
+(set-logic LIA)
+
+(synth-inv inv-f ((i Int) (j Int)))
+
+(declare-primed-var i Int)
+(declare-primed-var j Int)
+
+(define-fun pre-f ((i Int) (j Int)) Bool
+(and (= i 1)  
+(= j 10)))
+
+(define-fun trans-f ((i Int) (j Int) (i! Int) (j! Int)) Bool
+(and (and (>= j i) (= i! (+ i 2))) (= j! (- j 1))))
+
+(define-fun post-f ((i Int) (j Int)) Bool
+(not (and (< j i) (not (= j 6)))))
+
+(inv-constraint inv-f pre-f trans-f post-f)
+
+(check-synth)
diff --git a/test/regress/regress0/sygus/fg_polynomial3.sy b/test/regress/regress0/sygus/fg_polynomial3.sy
new file mode 100644
index 000000000..dab92bb88
--- /dev/null
+++ b/test/regress/regress0/sygus/fg_polynomial3.sy
@@ -0,0 +1,18 @@
+; EXPECT: unsat
+; COMMAND-LINE: --no-dump-synth
+
+(set-logic LIA)
+
+(synth-fun addExpr1 ((x Int) (y Int)) Int
+)
+
+(synth-fun addExpr2 ((x Int) (y Int)) Int
+)
+
+(declare-var x Int)
+(declare-var y Int)
+
+(constraint (= (+ (addExpr1 x y) (addExpr2 y x)) (- x (+ x y))))
+
+(check-synth)
+
diff --git a/test/regress/regress0/sygus/icfp_14.12.sy b/test/regress/regress0/sygus/icfp_14.12.sy
new file mode 100644
index 000000000..d9c19f8c1
--- /dev/null
+++ b/test/regress/regress0/sygus/icfp_14.12.sy
@@ -0,0 +1,63 @@
+; 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)
+		    (if0 Start Start Start)
+ ))
+)
+)
+(constraint (= (f #x6E393354DFFAAB51) #xC8E366559002AA57))
+(constraint (= (f #xFDA75AD598A27135) #x812C529533AEC765))
+(constraint (= (f #x58682C0FA4F8DB6D) #xD3CBE9F82D839249))
+(constraint (= (f #x58FDC0941A7E079F) #xD3811FB5F2C0FC30))
+(constraint (= (f #xBDC9B88103ECB0C9) #xA11B23BF7E09A79B))
+(constraint (= (f #x000000000001502F) #xFFFFFFFFFFFF57E8))
+(constraint (= (f #x0000000000010999) #xFFFFFFFFFFFF7B33))
+(constraint (= (f #x0000000000013169) #xFFFFFFFFFFFF674B))
+(constraint (= (f #x000000000001B1A9) #xFFFFFFFFFFFF272B))
+(constraint (= (f #x0000000000016D77) #xFFFFFFFFFFFF4944))
+(constraint (= (f #x0000000000000001) #xFFFFFFFFFFFFFFFF))
+(constraint (= (f #x1ED2E25068744C80) #x0000000000000000))
+(constraint (= (f #x2D2144F9D8CDCBD6) #x0000000000000000))
+(constraint (= (f #xE5D371D100002E8A) #x0000000000000000))
+(constraint (= (f #xADFF6BA34EBDAD72) #x0000000000000000))
+(constraint (= (f #xDA9299B546AAB59A) #x0000000000000000))
+(constraint (= (f #x0000000000015C8A) #x0000000000000000))
+(constraint (= (f #x0000000000017066) #x0000000000000000))
+(constraint (= (f #x000000000001D9D8) #x0000000000000000))
+(constraint (= (f #x00000000000151AE) #x0000000000000000))
+(constraint (= (f #x0000000000017A14) #x0000000000000000))
+(constraint (= (f #xF0F0F0F0F0F0F0F2) #x0000000000000000))
+(constraint (= (f #x83163CFD5DDCCCFB) #xBE74E18151119982))
+(constraint (= (f #xEA31B6A50EF4E399) #x8AE724AD78858E33))
+(constraint (= (f #xE0B1EF549BB6D4B9) #x8FA70855B22495A3))
+(constraint (= (f #x086F9E13A16C363D) #xFBC830F62F49E4E1))
+(constraint (= (f #x2426824D3E67E342) #x0000000000000000))
+(constraint (= (f #xDD518DEFFF18308A) #x0000000000000000))
+(constraint (= (f #x21ECDADB06B3CB03) #xEF0992927CA61A7E))
+(constraint (= (f #x72B1976FBB63A82B) #xC6A73448224E2BEA))
+(constraint (= (f #x16CB47AE0281B27F) #xF49A5C28FEBF26C0))
+(constraint (= (f #x82DE7A1FCA0C0B8F) #xBE90C2F01AF9FA38))
+(constraint (= (f #x0000000000000001) #xFFFFFFFFFFFFFFFF))
+(constraint (= (f #xF0F0F0F0F0F0F0F2) #x0000000000000000))
+(constraint (= (f #x000000000001F0D4) #x0000000000000000))
+(constraint (= (f #x0000000000010067) #xFFFFFFFFFFFF7FCC))
+(check-synth)
diff --git a/test/regress/regress0/sygus/icfp_easy-ite.sy b/test/regress/regress0/sygus/icfp_easy-ite.sy
new file mode 100644
index 000000000..248264698
--- /dev/null
+++ b/test/regress/regress0/sygus/icfp_easy-ite.sy
@@ -0,0 +1,34 @@
+; 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 #x0000000000000001) #x0000000000000001))
+
+(constraint (= (f #x0000000000100001) #x0000000000100001))
+
+(constraint (= (f #xE5D371D100002E8A) #x0000000000000000))
+
+(check-synth)
diff --git a/test/regress/regress0/sygus/qe.sy b/test/regress/regress0/sygus/qe.sy
new file mode 100644
index 000000000..eaff0fd9a
--- /dev/null
+++ b/test/regress/regress0/sygus/qe.sy
@@ -0,0 +1,12 @@
+; EXPECT: unsat
+; COMMAND-LINE: --cegqi-si=all --no-dump-synth
+(set-logic LIA)
+
+(synth-fun f ((x Int)) Int)
+
+(declare-var x Int)
+(declare-var y Int)
+
+(constraint (=> (or (= y 2) (= y 3)) (> (f x) y)))
+
+(check-synth)
diff --git a/test/regress/regress0/sygus/strings-template-infer.sy b/test/regress/regress0/sygus/strings-template-infer.sy
new file mode 100644
index 000000000..498e713e8
--- /dev/null
+++ b/test/regress/regress0/sygus/strings-template-infer.sy
@@ -0,0 +1,16 @@
+; EXPECT: unsat
+; COMMAND-LINE: --no-dump-synth
+(set-logic SLIA)
+ 
+(define-fun cA ((x String) (y String)) String (str.++ (str.++ x "A") y))
+ 
+(synth-fun f ((name String)) String
+    ((Start String (name "A" "B" ""
+                       (cA Start Start)))))
+
+
+(declare-var name String)
+ 
+(constraint (= (f "BB") "AAAAAAAAAAAA"))
+ 
+(check-synth)
diff --git a/test/regress/regress0/sygus/strings-trivial-simp.sy b/test/regress/regress0/sygus/strings-trivial-simp.sy
new file mode 100644
index 000000000..d37ac8bf4
--- /dev/null
+++ b/test/regress/regress0/sygus/strings-trivial-simp.sy
@@ -0,0 +1,14 @@
+; EXPECT: unsat
+; COMMAND-LINE: --no-dump-synth
+(set-logic SLIA)
+ 
+(synth-fun f ((name String)) String
+    ((Start String (name "A" "B"
+                       (str.++ Start Start)))))
+
+
+(declare-var name String)
+ 
+(constraint (= (f "BB") "AAAAAAAAAAAABAAAAAAAABAAA"))
+ 
+(check-synth)
diff --git a/test/regress/regress0/sygus/strings-trivial.sy b/test/regress/regress0/sygus/strings-trivial.sy
new file mode 100644
index 000000000..f4847922d
--- /dev/null
+++ b/test/regress/regress0/sygus/strings-trivial.sy
@@ -0,0 +1,15 @@
+; EXPECT: unsat
+; COMMAND-LINE: --no-dump-synth
+(set-logic SLIA)
+ 
+(synth-fun f ((name String)) String
+    ((Start String (ntString))
+     (ntString String (name "A" "B"
+                       (str.++ ntString ntString)))))
+
+
+(declare-var name String)
+ 
+(constraint (= (f "B") "AAAAAAAAAAAAAAAAAAAAAAAAA"))
+ 
+(check-synth)
diff --git a/test/regress/regress0/sygus/tl-type-0.sy b/test/regress/regress0/sygus/tl-type-0.sy
new file mode 100644
index 000000000..ef046c8e0
--- /dev/null
+++ b/test/regress/regress0/sygus/tl-type-0.sy
@@ -0,0 +1,11 @@
+; EXPECT: unsat
+; COMMAND-LINE: --cegqi-si=none --no-dump-synth
+(set-logic LIA)
+(synth-fun f ((x Int)) Int
+    ((Start Int ((+ Term Term)))
+     (Term Int (x 0))))
+
+(declare-var x Int)
+(constraint (= (f x) 0))
+(check-synth)
+
diff --git a/test/regress/regress0/sygus/tl-type-4x.sy b/test/regress/regress0/sygus/tl-type-4x.sy
new file mode 100644
index 000000000..a18d13052
--- /dev/null
+++ b/test/regress/regress0/sygus/tl-type-4x.sy
@@ -0,0 +1,11 @@
+; EXPECT: unsat
+; COMMAND-LINE: --cegqi-si=none --no-dump-synth
+(set-logic LIA)
+(synth-fun f ((x Int)) Int
+    ((Start Int (Term (+ Start Start)))
+     (Term Int (x 0))))
+
+(declare-var x Int)
+(constraint (= (f x) (* 4 x)))
+(check-synth)
+