Trace tags for dumping the decision tree in org-mode format (#2871)

This would add tracing options to print the decision tree in [org-mode](https://orgmode.org/) format which can be viewed with emacs or [vim-orgmode](https://github.com/jceb/vim-orgmode). 

In the raw format, the number of asterisks denote the decision level of a decision, and within a propagation node, the number of spaces denote the level. Most viewers render the asterisks as indented bullets.

There are some options for controlling verbosity:
`dtview` - prints the decisions (basic option)
`dtview::command` - also prints smt-lib commands as they're issued
`dtview::conflict` - also prints conflicts
`dtview::prop` - also prints propagations 

Example usage:
`cvc4 -t dtview -t dtview::command -t dtview::conflict -t dtview::prop <example smt2 file> &> example-trace.org`

The resulting file when opened with an org-mode viewer has collapsible nodes, where "..." marks a node with children.

2 files changed, 75 insertions, 6 deletions

diff --git a/src/prop/minisat/core/Solver.cc b/src/prop/minisat/core/Solver.cc
index 5b097dc39..6126983fa 100644
--- a/src/prop/minisat/core/Solver.cc
+++ b/src/prop/minisat/core/Solver.cc
@@ -56,6 +56,27 @@ bool assertionLevelOnly()
 {
   return options::unsatCores() && options::incrementalSolving();
 }
+
+//=================================================================================================
+// Helper functions for decision tree tracing
+
+// Writes to Trace macro for decision tree tracing
+static inline void dtviewDecisionHelper(size_t level,
+                                        const Node& node,
+                                        const char* decisiontype)
+{
+  Trace("dtview") << std::string(level - (options::incrementalSolving() ? 1 : 0), '*')
+                  << " " << node << " :" << decisiontype << "-DECISION:" << std::endl;
+}
+
+// Writes to Trace macro for propagation tracing
+static inline void dtviewPropagationHeaderHelper(size_t level)
+{
+  Trace("dtview::prop") << std::string(level + 1 - (options::incrementalSolving() ? 1 : 0),
+                                       '*')
+                        << " /Propagations/" << std::endl;
+}
+
 }  // namespace
 
 //=================================================================================================
@@ -607,6 +628,20 @@ Lit Solver::pickBranchLit()
             << "getNextTheoryDecisionRequest(): now deciding on " << nextLit
             << std::endl;
         decisions++;
+
+        // org-mode tracing -- theory decision
+        if (Trace.isOn("dtview"))
+        {
+          dtviewDecisionHelper(context->getLevel(),
+                               proxy->getNode(MinisatSatSolver::toSatLiteral(nextLit)),
+                               "THEORY");
+        }
+
+        if (Trace.isOn("dtview::prop"))
+        {
+          dtviewPropagationHeaderHelper(context->getLevel());
+        }
+
         return nextLit;
       } else {
         Debug("theoryDecision")
@@ -631,10 +666,23 @@ Lit Solver::pickBranchLit()
       decisions++;
       Var next = var(nextLit);
       if(polarity[next] & 0x2) {
-        return mkLit(next, polarity[next] & 0x1);
-      } else {
-        return nextLit;
+        nextLit = mkLit(next, polarity[next] & 0x1);
       }
+
+      // org-mode tracing -- decision engine decision
+      if (Trace.isOn("dtview"))
+      {
+        dtviewDecisionHelper(context->getLevel(),
+                             proxy->getNode(MinisatSatSolver::toSatLiteral(nextLit)),
+                             "DE");
+      }
+
+      if (Trace.isOn("dtview::prop"))
+      {
+        dtviewPropagationHeaderHelper(context->getLevel());
+      }
+
+      return nextLit;
     }
 
     Var next = var_Undef;
@@ -668,12 +716,32 @@ Lit Solver::pickBranchLit()
       // Check with decision engine if it can tell polarity
       lbool dec_pol = MinisatSatSolver::toMinisatlbool
         (proxy->getDecisionPolarity(MinisatSatSolver::toSatVariable(next)));
+      Lit decisionLit;
       if(dec_pol != l_Undef) {
         Assert(dec_pol == l_True || dec_pol == l_False);
-        return mkLit(next, (dec_pol == l_True) );
+        decisionLit = mkLit(next, (dec_pol == l_True));
       }
-      // If it can't use internal heuristic to do that
-      return mkLit(next, rnd_pol ? drand(random_seed) < 0.5 : (polarity[next] & 0x1));
+      else
+      {
+        // If it can't use internal heuristic to do that
+        decisionLit = mkLit(
+            next, rnd_pol ? drand(random_seed) < 0.5 : (polarity[next] & 0x1));
+      }
+
+      // org-mode tracing -- decision engine decision
+      if (Trace.isOn("dtview"))
+      {
+        dtviewDecisionHelper(context->getLevel(),
+                             proxy->getNode(MinisatSatSolver::toSatLiteral(decisionLit)),
+                             "DE");
+      }
+
+      if (Trace.isOn("dtview::prop"))
+      {
+        dtviewPropagationHeaderHelper(context->getLevel());
+      }
+
+      return decisionLit;
     }
 }
 
diff --git a/src/prop/minisat/core/Solver.h b/src/prop/minisat/core/Solver.h
index b6da9b9c8..aa3b96c57 100644
--- a/src/prop/minisat/core/Solver.h
+++ b/src/prop/minisat/core/Solver.h
@@ -455,6 +455,7 @@ protected:
     // Returns a random integer 0 <= x < size. Seed must never be 0.
     static inline int irand(double& seed, int size) {
         return (int)(drand(seed) * size); }
+
 };