Make lambda rewriter more robust (#3806)

The lambda rewriter was not robust to the case where the lambda of the
array representation contained a disequality, e.g. `not(x = 1))`. It
would process it as `ite(not(x = 1), true, false)` instead of `ite(x =
1, false, true)`, which meant that it wasn't able to turn it into an
array representation when checking const-ness. Additionally, the
rewriter had issues when the lambda was of the form `ite((= x c1), true,
(= y c2))` (after turning it into an array and then into a lambda)
because it is expecting the false branch of the `ite` to not contain `y`
variables, making it non-constant despite the array being constant. This
commit solves that issue by normalizing `ite(not(c), x, y) ---> ite(c,
y, x)`.

4 files changed, 38 insertions, 3 deletions

diff --git a/src/theory/booleans/theory_bool_rewriter.cpp b/src/theory/booleans/theory_bool_rewriter.cpp
index c53610efa..1c5eab364 100644
--- a/src/theory/booleans/theory_bool_rewriter.cpp
+++ b/src/theory/booleans/theory_bool_rewriter.cpp
@@ -316,6 +316,14 @@ RewriteResponse TheoryBoolRewriter::preRewrite(TNode n) {
       //   return RewriteResponse(REWRITE_AGAIN, resp);
       // }
     }
+
+    if (n[0].getKind() == kind::NOT)
+    {
+      // ite(not(c), x, y) ---> ite(c, y, x)
+      return RewriteResponse(
+          REWRITE_AGAIN, nodeManager->mkNode(kind::ITE, n[0][0], n[2], n[1]));
+    }
+
     // else if (n[2].isConst()) {
     //   if(n[2] == ff){
     //     Node resp = (n[0]).andNode(n[1]);
diff --git a/src/theory/builtin/theory_builtin_rewriter.cpp b/src/theory/builtin/theory_builtin_rewriter.cpp
index 15c312080..82952f9fd 100644
--- a/src/theory/builtin/theory_builtin_rewriter.cpp
+++ b/src/theory/builtin/theory_builtin_rewriter.cpp
@@ -224,9 +224,10 @@ Node TheoryBuiltinRewriter::getArrayRepresentationForLambdaRec(TNode n,
           << "  process base : " << curr << std::endl;
       // Boolean return case, e.g. lambda x. (= x v) becomes
       // lambda x. (ite (= x v) true false)
-      index_eq = curr;
-      curr_val = nm->mkConst(true);
-      next = nm->mkConst(false);
+      bool pol = curr.getKind() != kind::NOT;
+      index_eq = pol ? curr : curr[0];
+      curr_val = nm->mkConst(pol);
+      next = nm->mkConst(!pol);
     }
 
     // [2] We ensure that "index_eq" is an equality, if possible.
diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt
index 9469e7d61..92a6200ee 100644
--- a/test/regress/CMakeLists.txt
+++ b/test/regress/CMakeLists.txt
@@ -109,6 +109,7 @@ set(regress_0_tests
   regress0/aufbv/fuzz13.smtv1.smt2
   regress0/aufbv/fuzz14.smtv1.smt2
   regress0/aufbv/fuzz15.smtv1.smt2
+  regress0/aufbv/issue3737.smt2
   regress0/aufbv/rewrite_bug.smtv1.smt2
   regress0/aufbv/try3_sameret_functions_fse-bfs_tac.calc_next.il.fse-bfs.delta01.smtv1.smt2
   regress0/aufbv/try5_small_difret_functions_wp_su.set_char_quoting.il.wp.delta01.smtv1.smt2
diff --git a/test/regress/regress0/aufbv/issue3737.smt2 b/test/regress/regress0/aufbv/issue3737.smt2
new file mode 100644
index 000000000..630e7f3b5
--- /dev/null
+++ b/test/regress/regress0/aufbv/issue3737.smt2
@@ -0,0 +1,25 @@
+(set-logic QF_UFBV)
+(declare-fun b ((_ BitVec 12) (_ BitVec 6)) Bool)
+(declare-fun a ((_ BitVec 11) (_ BitVec 9) (_ BitVec 15)) (_ BitVec 10))
+(declare-fun d () (_ BitVec 7))
+(declare-fun c ((_ BitVec 15) (_ BitVec 15) (_ BitVec 1)) Bool)
+(assert (let ((a!1 (a ((_ zero_extend 2) #b001010001)
+              ((_ sign_extend 8) (ite (bvsle #b001010001 #b001010001) #b1 #b0))
+              ((_ sign_extend 14) (ite (bvsle #b001010001 #b001010001) #b1 #b0))))
+      (a!6 (b ((_ zero_extend 11) (ite (bvsle #b001010001 #b001010001) #b1 #b0))
+              ((_ sign_extend 5) (ite (bvsle #b001010001 #b001010001) #b1 #b0)))))
+(let ((a!2 (c ((_ zero_extend 14) (ite (bvsle #b001010001 #b001010001) #b1 #b0))
+              ((_ zero_extend 6) #b001010001)
+              ((_ extract 3 3) a!1)))
+      (a!3 (bvule (ite (bvsle #b001010001 #b001010001) #b1 #b0)
+                  (ite (b ((_ sign_extend 5) d) ((_ extract 7 2) a!1)) #b1 #b0)))
+      (a!4 (ite (c ((_ sign_extend 5) (bvsrem a!1 a!1))
+                   ((_ zero_extend 6) #b001010001)
+                   ((_ extract 8 8) (bvsrem a!1 a!1)))
+                #b1
+                #b0)))
+(let ((a!5 (bvslt a!4
+                  (ite (b ((_ sign_extend 5) d) ((_ extract 7 2) a!1)) #b1 #b0))))
+  (ite (= a!2 a!3) (xor a!5 a!6) (= a!2 a!3))))))
+(set-info :status sat)
+(check-sat)