Improve quantifiers engine wrt incremental presolve. Add regressions.

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