diff options
author | makaimann <makaim@stanford.edu> | 2019-12-16 01:58:24 -0800 |
---|---|---|
committer | Andres Noetzli <andres.noetzli@gmail.com> | 2019-12-16 01:58:24 -0800 |
commit | c1c8b61a03732cb485e358bc0f78e654242d58de (patch) | |
tree | c7943638645ed74976c1e5aa0fe7ddad59d57c0f /src/prop | |
parent | 0e5efa8c4ff22925d3fc011a3588a3e67c107d0e (diff) |
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.
Diffstat (limited to 'src/prop')
-rw-r--r-- | src/prop/minisat/core/Solver.cc | 80 | ||||
-rw-r--r-- | src/prop/minisat/core/Solver.h | 1 |
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); } + }; |