Support ackermannization on uninterpreted sorts in BV (#3372)

Support ackermannization on uninterpreted sorts in BV. For uninterpreted sorts, we create a bit-vector sort to replace it. For an uninterpreted sort `S`, if the number of variables within sort `S` is `n`, the replacing bit-vector will have size (log n)+1.

5 files changed, 118 insertions, 0 deletions

diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt
index c4dfd2593..f4937f8f3 100644
--- a/test/regress/CMakeLists.txt
+++ b/test/regress/CMakeLists.txt
@@ -170,6 +170,10 @@ set(regress_0_tests
   regress0/bv/ackermann2.smt2
   regress0/bv/ackermann3.smt2
   regress0/bv/ackermann4.smt2
+  regress0/bv/ackermann5.smt2
+  regress0/bv/ackermann6.smt2
+  regress0/bv/ackermann7.smt2
+  regress0/bv/ackermann8.smt2
   regress0/bv/bool-model.smt2
   regress0/bv/bool-to-bv-all.smt2
   regress0/bv/bool-to-bv-ite.smt2
diff --git a/test/regress/regress0/bv/ackermann5.smt2 b/test/regress/regress0/bv/ackermann5.smt2
new file mode 100644
index 000000000..d29311109
--- /dev/null
+++ b/test/regress/regress0/bv/ackermann5.smt2
@@ -0,0 +1,31 @@
+; COMMAND-LINE: --ackermann --no-check-models --no-check-proofs --no-check-unsat-cores
+; EXPECT: sat
+(set-logic QF_UFBV)
+
+(declare-sort S 0)
+(declare-sort T 0)
+
+(declare-fun s1 () S)
+(declare-fun s2 () S)
+(declare-fun t1 () T)
+(declare-fun t2 () T)
+
+(declare-fun a () (_ BitVec 4))
+(declare-fun b () (_ BitVec 4))
+
+(declare-fun f (S) (_ BitVec 4))
+(declare-fun g (S) S)
+(declare-fun h (T) S)
+(declare-fun i (T) T)
+
+(assert (= (f s1) (bvand a b)))
+(assert (= (f s2) (bvand a b)))
+
+(assert (= (f (g s1)) (f (h (i t1)))))
+(assert (= (f (g (h (i t2)))) (f (h (i t2)))))
+(assert (= t1 t2))
+(assert (= s1 (h (i t2))))
+
+(check-sat)
+(exit)
+
diff --git a/test/regress/regress0/bv/ackermann6.smt2 b/test/regress/regress0/bv/ackermann6.smt2
new file mode 100644
index 000000000..846339f52
--- /dev/null
+++ b/test/regress/regress0/bv/ackermann6.smt2
@@ -0,0 +1,31 @@
+; COMMAND-LINE: --ackermann --no-check-models --no-check-proofs --no-check-unsat-cores
+; EXPECT: unsat
+(set-logic QF_UFBV)
+
+(declare-sort S 0)
+(declare-sort T 0)
+
+(declare-fun s1 () S)
+(declare-fun s2 () S)
+(declare-fun t1 () T)
+(declare-fun t2 () T)
+
+(declare-fun a () (_ BitVec 4))
+(declare-fun b () (_ BitVec 4))
+
+(declare-fun f (S) (_ BitVec 4))
+(declare-fun g (S) S)
+(declare-fun h (T) S)
+(declare-fun i (T) T)
+
+(assert (= (f s1) (bvand a b)))
+(assert (= (f s2) (bvand a b)))
+
+(assert (= (f (g s1)) (f (h (i t1)))))
+(assert (not (= (f (g (h (i t2)))) (f (h (i t2))))))
+(assert (= t1 t2))
+(assert (= s1 (h (i t2))))
+
+(check-sat)
+(exit)
+
diff --git a/test/regress/regress0/bv/ackermann7.smt2 b/test/regress/regress0/bv/ackermann7.smt2
new file mode 100644
index 000000000..174ad747a
--- /dev/null
+++ b/test/regress/regress0/bv/ackermann7.smt2
@@ -0,0 +1,26 @@
+; COMMAND-LINE: --ackermann --no-check-models --no-check-proofs --no-check-unsat-cores
+; EXPECT: sat
+(set-logic QF_UFBV)
+
+(declare-sort S 0)
+(declare-sort T 0)
+
+(declare-fun s1 () S)
+(declare-fun s2 () S)
+(declare-fun s3 () S)
+
+(declare-fun t1 () T)
+(declare-fun t2 () T)
+(declare-fun t3 () T)
+
+(assert (not (= s1 s2)))
+(assert (not (= s2 s3)))
+(assert (not (= s3 s1)))
+
+(assert (not (= t1 t2)))
+(assert (not (= t2 t3)))
+(assert (not (= t3 t1)))
+
+(check-sat)
+(exit)
+
diff --git a/test/regress/regress0/bv/ackermann8.smt2 b/test/regress/regress0/bv/ackermann8.smt2
new file mode 100644
index 000000000..2a424e085
--- /dev/null
+++ b/test/regress/regress0/bv/ackermann8.smt2
@@ -0,0 +1,26 @@
+; COMMAND-LINE: --ackermann --no-check-models --no-check-proofs --no-check-unsat-cores
+; EXPECT: unsat
+(set-logic QF_UFBV)
+
+(declare-sort S 0)
+(declare-sort T 0)
+
+(declare-fun s1 () S)
+(declare-fun s2 () S)
+(declare-fun s3 () S)
+
+(declare-fun a () (_ BitVec 1))
+(declare-fun b () (_ BitVec 1))
+(declare-fun c () (_ BitVec 1))
+
+(assert (not (= s1 s2)))
+(assert (not (= s2 s3)))
+(assert (not (= s3 s1)))
+
+(assert (not (= a b)))
+(assert (not (= b c)))
+(assert (not (= c a)))
+
+(check-sat)
+(exit)
+