diff options
author | ajreynol <andrew.j.reynolds@gmail.com> | 2015-09-28 16:18:32 +0200 |
---|---|---|
committer | ajreynol <andrew.j.reynolds@gmail.com> | 2015-09-28 16:18:32 +0200 |
commit | ef7b7bba7bc9b207d5a2198518f21b13490caa32 (patch) | |
tree | 43867e7dcab54bd77bc07167e096cc518b0be035 | |
parent | 187e5d57adeda59c8899321c882db1d5b9a6f2ba (diff) |
Improve quantifiers engine wrt incremental presolve. Add regressions.
-rw-r--r-- | src/theory/quantifiers/term_database.cpp | 12 | ||||
-rw-r--r-- | src/theory/quantifiers_engine.cpp | 32 | ||||
-rw-r--r-- | src/theory/quantifiers_engine.h | 14 | ||||
-rw-r--r-- | test/regress/regress0/push-pop/Makefile.am | 3 | ||||
-rw-r--r-- | test/regress/regress0/push-pop/inc-double-u.smt2 | 16 | ||||
-rw-r--r-- | test/regress/regress0/strings/Makefile.am | 3 | ||||
-rw-r--r-- | test/regress/regress0/strings/norn-360.smt2 | 25 |
7 files changed, 82 insertions, 23 deletions
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<d_presolve_cache.size(); i++ ){ - addTermToDatabase( d_presolve_cache[i], d_presolve_cache_wq[i], d_presolve_cache_wic[i] ); + //add all terms to database + if( options::incrementalSolving() ){ + for( unsigned i=0; i<d_presolve_cache.size(); i++ ){ + addTermToDatabase( d_presolve_cache[i], d_presolve_cache_wq[i], d_presolve_cache_wic[i] ); + } } - d_presolve_cache.clear(); - d_presolve_cache_wq.clear(); - d_presolve_cache_wic.clear(); } void QuantifiersEngine::check( Theory::Effort e ){ @@ -627,11 +630,16 @@ quantifiers::TermDbSygus* QuantifiersEngine::getTermDatabaseSygus() { } void QuantifiersEngine::addTermToDatabase( Node n, bool withinQuant, bool withinInstClosure ){ - if( d_presolve ){ - d_presolve_cache.push_back( n ); - d_presolve_cache_wq.push_back( withinQuant ); - d_presolve_cache_wic.push_back( withinInstClosure ); - }else{ + if( options::incrementalSolving() ){ + if( d_presolve_in.find( n )==d_presolve_in.end() ){ + d_presolve_in.insert( n ); + d_presolve_cache.push_back( n ); + d_presolve_cache_wq.push_back( withinQuant ); + d_presolve_cache_wic.push_back( withinInstClosure ); + } + } + //only wait if we are doing incremental solving + if( !d_presolve || !options::incrementalSolving() ){ std::set< Node > 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 <ext/hash_set> #include <iostream> #include <map> +#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<Node> NodeList; + typedef context::CDChunkList<bool> BoolList; + typedef context::CDHashSet<Node, NodeHashFunction> 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 |