From 93fd4aed186c3dfa1b0fa7bec102f5b94edca322 Mon Sep 17 00:00:00 2001 From: Andrew Reynolds Date: Mon, 22 Mar 2021 09:51:05 -0500 Subject: [PATCH] Guard for non-unique skolems in term formula removal (#6179) In rare cases, we may reuse skolems for different terms (those that are the same up to purification) due to recent changes in how skolem are generated. This guards for this case in the term formula remover, which avoids assertion failures in cd insert hash map. Fixes #6132. --- src/expr/skolem_manager.h | 9 +++++++++ src/smt/term_formula_removal.cpp | 13 +++++++++++-- test/regress/CMakeLists.txt | 1 + .../strings/issue6132-non-unique-skolem.smt2 | 7 +++++++ 4 files changed, 28 insertions(+), 2 deletions(-) create mode 100644 test/regress/regress1/strings/issue6132-non-unique-skolem.smt2 diff --git a/src/expr/skolem_manager.h b/src/expr/skolem_manager.h index 1cb048cf2..44a8f87c2 100644 --- a/src/expr/skolem_manager.h +++ b/src/expr/skolem_manager.h @@ -161,6 +161,15 @@ class SkolemManager * * Notice that a purification skolem is trivial to justify, and hence it * does not require a proof generator. + * + * Notice that in very rare cases, two different terms may have the + * same purification skolem. For example, let k be the skolem introduced to + * eliminate (ite A B C). Then, the pair of terms: + * (ite (ite A B C) D E) and (ite k D E) + * have the same purification skolem. In the implementation, this is a result + * of the fact that the above terms have the same original form. It is sound + * to use the same skolem to purify these two terms, since they are + * definitionally equivalent. */ Node mkPurifySkolem(Node t, const std::string& prefix, diff --git a/src/smt/term_formula_removal.cpp b/src/smt/term_formula_removal.cpp index d1bb4f5b8..6f2f77a14 100644 --- a/src/smt/term_formula_removal.cpp +++ b/src/smt/term_formula_removal.cpp @@ -292,6 +292,12 @@ Node RemoveTermFormulas::runCurrent(std::pair& curr, "a variable introduced due to term-level ITE removal"); d_skolem_cache.insert(node, skolem); + // Notice that in very rare cases, two different terms may have the + // same purification skolem (see SkolemManager::mkPurifySkolem) For such + // cases, for simplicity, we repeat the work of constructing the + // assertion and proofs below. This is so that the proof for the new form + // of the lemma is used. + // The new assertion newAssertion = nodeManager->mkNode( kind::ITE, node[0], skolem.eqNode(node[1]), skolem.eqNode(node[2])); @@ -497,8 +503,11 @@ Node RemoveTermFormulas::runCurrent(std::pair& curr, newLem = theory::TrustNode::mkTrustLemma(newAssertion, d_lp.get()); - // store in the lemma cache - d_lemmaCache.insert(skolem, newLem); + // store in the lemma cache, if it is not already there. + if (d_lemmaCache.find(skolem) == d_lemmaCache.end()) + { + d_lemmaCache.insert(skolem, newLem); + } Trace("rtf-proof-debug") << "Checking closed..." << std::endl; newLem.debugCheckClosed("rtf-proof-debug", diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt index a98ea84bb..6ae77b38b 100644 --- a/test/regress/CMakeLists.txt +++ b/test/regress/CMakeLists.txt @@ -2038,6 +2038,7 @@ set(regress_1_tests regress1/strings/issue5940-2-skc-len-conc.smt2 regress1/strings/issue6072-inc-no-const-reg.smt2 regress1/strings/issue6075-repl-len-one-rr.smt2 + regress1/strings/issue6132-non-unique-skolem.smt2 regress1/strings/issue6142-repl-inv-rew.smt2 regress1/strings/kaluza-fl.smt2 regress1/strings/loop002.smt2 diff --git a/test/regress/regress1/strings/issue6132-non-unique-skolem.smt2 b/test/regress/regress1/strings/issue6132-non-unique-skolem.smt2 new file mode 100644 index 000000000..29d0e9469 --- /dev/null +++ b/test/regress/regress1/strings/issue6132-non-unique-skolem.smt2 @@ -0,0 +1,7 @@ +; COMMAND-LINE: --strings-exp +; EXPECT: sat +(set-logic ALL) +(declare-fun str () String) +(assert (= 0 (ite (= str (str.from_code + (ite (= 0 (ite (> (str.len (str.from_int (str.len str))) 1) 1 0)) 1 0))) 1 0))) +(check-sat) -- 2.30.2