Reset decisions at SAT level after solving (#2059)

Some quick background: CVC4 has two primary contexts: the assertion
context (which corresponds to the push/pops issued by the user) and the
decision/SAT context (which corresponds to the push/pops done by the
user and each decision made by MiniSat.

Before 2cc0e2c6a691fb6d30ed8879832b49bc1f277d77, we had an additonal
push/pop when doing the actual solving. With these removed, it could
happen that we get a wrong result when doing incremental solving:

```
...
; check-sat call returns sat, the decision level in the SAT solver is
; non-zero at this point
(check-sat)
; Solver::addClause_() determines that we cannot add the clause to the
; SAT solver directly because the decision level is non-zero (i.e. the
; clause is treated like a theory lemma), thus it is added to the lemmas
; list.
(assert false)
; The solver stores some information about the current state, including
; the value of the "ok" flag in Solver, which indicates whether the
; current constraints are unsatisfiable. Note that "ok" is true at this
; point.
(push)
; Now, in Solver::updateLemmas(), we add clauses from the lemmas list.
; The problem is that empty clauses (which "false" is after removing "false"
; literals) and unit clauses are not added like normal clauses. Instead,
; the empty clause, essentially just results in the "ok" flag being set to
; false (unit clauses are added to the decision trail).
(check-sat)
; Here, the solver restores the information stored during
; (push), including the "ok" flag, which is now true again.
(pop)
; At this point, the solver has "forgotten" about (assert false) since
; the "ok" flag is back to true and it answers sat.
(check-sat)
```

There are multiple ways to look at the problem and to fix it:

- One could argue that an input assertion should always be added
directly to the clauses in the SAT solver, i.e. the solver should
always be at decision level 0 when we are adding input clauses. The
advantage of this is that it is relatively easy to implement,
corresponds to what the original MiniSat code does (it calls
Solver::cancelUntil(0) after solving), and is no worse than what we had
before commit 2cc0e2c6a691fb6d30ed8879832b49bc1f277d77 (push/pop do a
strict superset of what resetting the decision at the current assertion
level does). The disadvantage is that we might throw away some useful work.

- One could argue that is fine that (assert false) is treated like a
theory lemma. The advantage being that it might result in more efficient
solving and the disadvantage being that it is much trickier to
implement.

Unfortunately, it is not quite clear from the code what the original
intention was but we decided to implement the first solution. This
commit exposes a method in MiniSat to reset the decisions at the current
assertion level. We call this method from SmtEngine after solving.
Resetting the decisions directly after solving while we are still in
MiniSat does not work because it causes issues with datastructures in
the SMT solver that use the decision context (e.g.
TheoryEngine::d_incomplete seems to be reset too early, resulting in us
answering sat instead of unknown).

9 files changed, 38 insertions, 11 deletions

diff --git a/src/prop/minisat/core/Solver.cc b/src/prop/minisat/core/Solver.cc
index 2136f22df..aa59f18e1 100644
--- a/src/prop/minisat/core/Solver.cc
+++ b/src/prop/minisat/core/Solver.cc
@@ -344,8 +344,9 @@ bool Solver::addClause_(vec<Lit>& ps, bool removable, ClauseId& id)
     // Fit to size
     ps.shrink(i - j);
 
-    // If we are in solve or decision level > 0
-    if (minisat_busy || decisionLevel() > 0) {
+    // If we are in solve_ or propagate
+    if (minisat_busy)
+    {
       Debug("pf::sat") << "Add clause adding a new lemma: ";
       for (int k = 0; k < ps.size(); ++k) {
         Debug("pf::sat") << ps[k] << " ";
@@ -369,6 +370,8 @@ bool Solver::addClause_(vec<Lit>& ps, bool removable, ClauseId& id)
       // Debug("cores") << "lemma push " << proof_id << " " << (proof_id & 0xffffffff) << std::endl;
       // lemmas_proof_id.push(proof_id);
     } else {
+      assert(decisionLevel() == 0);
+
       // If all false, we're in conflict
       if (ps.size() == falseLiteralsCount) {
         if(PROOF_ON()) {
@@ -534,9 +537,7 @@ void Solver::cancelUntil(int level) {
     }
 }
 
-void Solver::popTrail() {
-  cancelUntil(0);
-}
+void Solver::resetTrail() { cancelUntil(0); }
 
 //=================================================================================================
 // Major methods:
@@ -1391,7 +1392,7 @@ lbool Solver::solve_()
 
     ScopedBool scoped_bool(minisat_busy, true);
 
-    popTrail();
+    assert(decisionLevel() == 0);
 
     model.clear();
     conflict.clear();
@@ -1580,8 +1581,8 @@ void Solver::garbageCollect()
 void Solver::push()
 {
   assert(enable_incremental);
+  assert(decisionLevel() == 0);
 
-  popTrail();
   ++assertionLevel;
   Debug("minisat") << "in user push, increasing assertion level to " << assertionLevel << std::endl;
   trail_ok.push(ok);
@@ -1596,8 +1597,6 @@ void Solver::pop()
 {
   assert(enable_incremental);
 
-  // Pop the trail to 0 level
-  popTrail();
   assert(decisionLevel() == 0);
 
   // Pop the trail below the user level
diff --git a/src/prop/minisat/core/Solver.h b/src/prop/minisat/core/Solver.h
index 99c47e045..c27d8a18b 100644
--- a/src/prop/minisat/core/Solver.h
+++ b/src/prop/minisat/core/Solver.h
@@ -169,6 +169,11 @@ public:
     void          push                     ();
     void          pop                      ();
 
+    /*
+     * Reset the decisions in the DPLL(T) SAT solver at the current assertion
+     * level.
+     */
+    void resetTrail();
     // addClause returns the ClauseId corresponding to the clause added in the
     // reference parameter id.
     bool    addClause (const vec<Lit>& ps, bool removable, ClauseId& id);  // Add a clause to the solver.
@@ -393,7 +398,6 @@ protected:
     void     theoryCheck      (CVC4::theory::Theory::Effort effort);                   // Perform a theory satisfiability check. Adds lemmas.
     CRef     updateLemmas     ();                                                      // Add the lemmas, backtraking if necessary and return a conflict if there is one
     void     cancelUntil      (int level);                                             // Backtrack until a certain level.
-    void     popTrail         ();                                                      // Backtrack the trail to the previous push position
     int      analyze          (CRef confl, vec<Lit>& out_learnt, int& out_btlevel);    // (bt = backtrack)
     void     analyzeFinal     (Lit p, vec<Lit>& out_conflict);                         // COULD THIS BE IMPLEMENTED BY THE ORDINARIY "analyze" BY SOME REASONABLE GENERALIZATION?
     bool     litRedundant     (Lit p, uint32_t abstract_levels);                       // (helper method for 'analyze()') - true if p is redundant
diff --git a/src/prop/minisat/minisat.cpp b/src/prop/minisat/minisat.cpp
index 514338fd9..73a6f0d5e 100644
--- a/src/prop/minisat/minisat.cpp
+++ b/src/prop/minisat/minisat.cpp
@@ -232,6 +232,8 @@ void MinisatSatSolver::pop() {
   d_minisat->pop();
 }
 
+void MinisatSatSolver::resetTrail() { d_minisat->resetTrail(); }
+
 /// Statistics for MinisatSatSolver
 
 MinisatSatSolver::Statistics::Statistics(StatisticsRegistry* registry) :
diff --git a/src/prop/minisat/minisat.h b/src/prop/minisat/minisat.h
index 58e02179c..ea673a15d 100644
--- a/src/prop/minisat/minisat.h
+++ b/src/prop/minisat/minisat.h
@@ -74,6 +74,8 @@ public:
 
   void pop() override;
 
+  void resetTrail() override;
+
   void requirePhase(SatLiteral lit) override;
 
   bool flipDecision() override;
diff --git a/src/prop/minisat/simp/SimpSolver.cc b/src/prop/minisat/simp/SimpSolver.cc
index 9b551fa70..96fea2147 100644
--- a/src/prop/minisat/simp/SimpSolver.cc
+++ b/src/prop/minisat/simp/SimpSolver.cc
@@ -120,7 +120,7 @@ lbool SimpSolver::solve_(bool do_simp, bool turn_off_simp)
       toDimacs(); 
       return l_Undef; 
     }
-    popTrail();
+    assert(decisionLevel() == 0);
 
     vec<Var> extra_frozen;
     lbool    result = l_True;
diff --git a/src/prop/prop_engine.cpp b/src/prop/prop_engine.cpp
index 23f7ea6b5..b09e7a088 100644
--- a/src/prop/prop_engine.cpp
+++ b/src/prop/prop_engine.cpp
@@ -281,6 +281,12 @@ void PropEngine::pop() {
   Debug("prop") << "pop()" << endl;
 }
 
+void PropEngine::resetTrail()
+{
+  d_satSolver->resetTrail();
+  Debug("prop") << "resetTrail()" << endl;
+}
+
 unsigned PropEngine::getAssertionLevel() const {
   return d_satSolver->getAssertionLevel();
 }
diff --git a/src/prop/prop_engine.h b/src/prop/prop_engine.h
index f3a69be96..edc828418 100644
--- a/src/prop/prop_engine.h
+++ b/src/prop/prop_engine.h
@@ -213,6 +213,12 @@ public:
    */
   void pop();
 
+  /*
+   * Reset the decisions in the DPLL(T) SAT solver at the current assertion
+   * level.
+   */
+  void resetTrail();
+
   /**
    * Get the assertion level of the SAT solver.
    */
diff --git a/src/prop/sat_solver.h b/src/prop/sat_solver.h
index 4dc95e060..86e0f1577 100644
--- a/src/prop/sat_solver.h
+++ b/src/prop/sat_solver.h
@@ -148,6 +148,12 @@ public:
 
   virtual void pop() = 0;
 
+  /*
+   * Reset the decisions in the DPLL(T) SAT solver at the current assertion
+   * level.
+   */
+  virtual void resetTrail() = 0;
+
   virtual bool properExplanation(SatLiteral lit, SatLiteral expl) const = 0;
 
   virtual void requirePhase(SatLiteral lit) = 0;
diff --git a/src/smt/smt_engine.cpp b/src/smt/smt_engine.cpp
index 2836f73b4..69cea8b06 100644
--- a/src/smt/smt_engine.cpp
+++ b/src/smt/smt_engine.cpp
@@ -4709,6 +4709,8 @@ Result SmtEngine::checkSatisfiability(const vector<Expr>& assumptions,
       }
     }
 
+    d_propEngine->resetTrail();
+
     // Pop the context
     if (didInternalPush)
     {