From ef7b7bba7bc9b207d5a2198518f21b13490caa32 Mon Sep 17 00:00:00 2001 From: ajreynol Date: Mon, 28 Sep 2015 16:18:32 +0200 Subject: [PATCH] Improve quantifiers engine wrt incremental presolve. Add regressions. --- src/theory/quantifiers/term_database.cpp | 12 ++++--- src/theory/quantifiers_engine.cpp | 32 ++++++++++++------- src/theory/quantifiers_engine.h | 14 +++++--- test/regress/regress0/push-pop/Makefile.am | 3 +- .../regress0/push-pop/inc-double-u.smt2 | 16 ++++++++++ test/regress/regress0/strings/Makefile.am | 3 +- test/regress/regress0/strings/norn-360.smt2 | 25 +++++++++++++++ 7 files changed, 82 insertions(+), 23 deletions(-) create mode 100644 test/regress/regress0/push-pop/inc-double-u.smt2 create mode 100644 test/regress/regress0/strings/norn-360.smt2 diff --git a/src/theory/quantifiers/term_database.cpp b/src/theory/quantifiers/term_database.cpp index d6f8b3af7..366c7ce07 100644 --- a/src/theory/quantifiers/term_database.cpp +++ b/src/theory/quantifiers/term_database.cpp @@ -420,11 +420,13 @@ void TermDb::setHasTerm( Node n ) { } void TermDb::presolve() { - //reset the caches that are SAT context-independent - d_op_map.clear(); - d_type_map.clear(); - d_processed.clear(); - d_iclosure_processed.clear(); + if( options::incrementalSolving() ){ + //reset the caches that are SAT context-independent + d_op_map.clear(); + d_type_map.clear(); + d_processed.clear(); + d_iclosure_processed.clear(); + } } void TermDb::reset( Theory::Effort effort ){ diff --git a/src/theory/quantifiers_engine.cpp b/src/theory/quantifiers_engine.cpp index e5b5c4080..f1c47a21a 100644 --- a/src/theory/quantifiers_engine.cpp +++ b/src/theory/quantifiers_engine.cpp @@ -83,7 +83,11 @@ QuantifiersEngine::QuantifiersEngine(context::Context* c, context::UserContext* d_te( te ), d_lemmas_produced_c(u), d_skolemized(u), -d_presolve(u, true){ +d_presolve(u, true), +d_presolve_in(u), +d_presolve_cache(u), +d_presolve_cache_wq(u), +d_presolve_cache_wic(u){ d_eq_query = new EqualityQueryQuantifiersEngine( this ); d_term_db = new quantifiers::TermDb( c, u, this ); d_tr_trie = new inst::TriggerTrie; @@ -300,13 +304,12 @@ void QuantifiersEngine::presolve() { } d_term_db->presolve(); d_presolve = false; - //clear presolve cache - for( unsigned i=0; i added; getTermDatabase()->addTerm( n, added, withinQuant, withinInstClosure ); //maybe have triggered instantiations if we are doing eager instantiation diff --git a/src/theory/quantifiers_engine.h b/src/theory/quantifiers_engine.h index 4e3bba501..30c4dabdf 100644 --- a/src/theory/quantifiers_engine.h +++ b/src/theory/quantifiers_engine.h @@ -29,6 +29,8 @@ #include #include #include +#include "context/cdchunk_list.h" +#include "context/cdhashset.h" namespace CVC4 { @@ -113,8 +115,11 @@ class QuantifiersEngine { friend class quantifiers::RewriteEngine; friend class quantifiers::QuantConflictFind; friend class inst::InstMatch; -private: typedef context::CDHashMap< Node, bool, NodeHashFunction > BoolMap; + typedef context::CDChunkList NodeList; + typedef context::CDChunkList BoolList; + typedef context::CDHashSet NodeSet; +private: /** reference to theory engine object */ TheoryEngine* d_te; /** vector of modules for quantifiers */ @@ -197,9 +202,10 @@ private: /** has presolve been called */ context::CDO< bool > d_presolve; /** presolve cache */ - std::vector< Node > d_presolve_cache; - std::vector< bool > d_presolve_cache_wq; - std::vector< bool > d_presolve_cache_wic; + NodeSet d_presolve_in; + NodeList d_presolve_cache; + BoolList d_presolve_cache_wq; + BoolList d_presolve_cache_wic; private: KEEP_STATISTIC(TimerStat, d_time, "theory::QuantifiersEngine::time"); public: diff --git a/test/regress/regress0/push-pop/Makefile.am b/test/regress/regress0/push-pop/Makefile.am index 649cbee90..6d50cc39f 100644 --- a/test/regress/regress0/push-pop/Makefile.am +++ b/test/regress/regress0/push-pop/Makefile.am @@ -42,7 +42,8 @@ BUG_TESTS = \ quant-fun-proc-unfd.smt2 \ bug654-dd.smt2 \ bug-fmf-fun-skolem.smt2 \ - bug674.smt2 + bug674.smt2 \ + inc-double-u.smt2 TESTS = $(SMT_TESTS) $(SMT2_TESTS) $(CVC_TESTS) $(BUG_TESTS) diff --git a/test/regress/regress0/push-pop/inc-double-u.smt2 b/test/regress/regress0/push-pop/inc-double-u.smt2 new file mode 100644 index 000000000..a01643df3 --- /dev/null +++ b/test/regress/regress0/push-pop/inc-double-u.smt2 @@ -0,0 +1,16 @@ +; COMMAND-LINE: --incremental +(set-logic UFLIA) +(declare-fun P (Int) Bool) +(declare-fun R (Int) Bool) +(assert (forall ((x Int)) (=> (R x) (not (P x))))) +; EXPECT: unknown +(check-sat) +(assert (R 0)) +; EXPECT: unknown +(check-sat) +(assert (forall ((x Int)) (P x))) +; EXPECT: unsat +(check-sat) +(push 1) +; EXPECT: unsat +(check-sat) diff --git a/test/regress/regress0/strings/Makefile.am b/test/regress/regress0/strings/Makefile.am index 716d41365..09dbdf08f 100644 --- a/test/regress/regress0/strings/Makefile.am +++ b/test/regress/regress0/strings/Makefile.am @@ -58,7 +58,8 @@ TESTS = \ bug613.smt2 \ idof-triv.smt2 \ chapman150408.smt2 \ - pierre150331.smt2 + pierre150331.smt2 \ + norn-360.smt2 FAILING_TESTS = diff --git a/test/regress/regress0/strings/norn-360.smt2 b/test/regress/regress0/strings/norn-360.smt2 new file mode 100644 index 000000000..573dcbe01 --- /dev/null +++ b/test/regress/regress0/strings/norn-360.smt2 @@ -0,0 +1,25 @@ +(set-logic QF_SLIA) +(set-option :strings-exp true) +(set-info :status sat) + +(declare-fun var_0 () String) +(declare-fun var_1 () String) +(declare-fun var_2 () String) +(declare-fun var_3 () String) +(declare-fun var_4 () String) +(declare-fun var_5 () String) +(declare-fun var_6 () String) +(declare-fun var_7 () String) +(declare-fun var_8 () String) +(declare-fun var_9 () String) +(declare-fun var_10 () String) +(declare-fun var_11 () String) +(declare-fun var_12 () String) + +(assert (str.in.re (str.++ var_3 "z" var_4 ) (re.++ (re.* (re.union (re.union (str.to.re "z") (str.to.re "b")) (re.++ (str.to.re "a") (re.union (re.union (str.to.re "z") (str.to.re "b")) (str.to.re "a"))))) (str.to.re "a")))) +(assert (str.in.re (str.++ var_3 "z" var_4 ) (re.++ (re.* (re.union (re.union (str.to.re "z") (str.to.re "b")) (re.++ (str.to.re "a") (re.union (str.to.re "z") (str.to.re "a"))))) (str.to.re "a")))) +(assert (str.in.re (str.++ var_3 "z" var_4 ) (re.++ (re.* (re.union (str.to.re "z") (re.++ (re.union (str.to.re "b") (str.to.re "a")) (re.union (str.to.re "z") (str.to.re "b"))))) (re.union (str.to.re "b") (str.to.re "a"))))) +(assert (str.in.re var_4 (re.* (re.range "a" "u")))) +(assert (str.in.re var_3 (re.* (re.range "a" "u")))) +(assert (<= 0 (str.len var_4))) +(check-sat) \ No newline at end of file -- 2.30.2