From a431edc5eba8b04812768b475b240725fb07d8c6 Mon Sep 17 00:00:00 2001 From: Andres Noetzli Date: Mon, 24 Feb 2020 07:46:47 -0800 Subject: [PATCH] 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)`. --- src/theory/booleans/theory_bool_rewriter.cpp | 8 ++++++ .../builtin/theory_builtin_rewriter.cpp | 7 +++--- test/regress/CMakeLists.txt | 1 + test/regress/regress0/aufbv/issue3737.smt2 | 25 +++++++++++++++++++ 4 files changed, 38 insertions(+), 3 deletions(-) create mode 100644 test/regress/regress0/aufbv/issue3737.smt2 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) -- 2.30.2