src/theory/theory_engine.cpp

   1 /*********************                                                        */
   2 /*! \file theory_engine.cpp
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Dejan Jovanovic, Morgan Deters, Andrew Reynolds
   6  ** This file is part of the CVC4 project.
   7  ** Copyright (c) 2009-2019 by the authors listed in the file AUTHORS
   8  ** in the top-level source directory) and their institutional affiliations.
   9  ** All rights reserved.  See the file COPYING in the top-level source
  10  ** directory for licensing information.\endverbatim
  11  **
  12  ** \brief The theory engine
  13  **
  14  ** The theory engine.
  15  **/
  16
  17 #include "theory/theory_engine.h"
  18
  19 #include <list>
  20 #include <vector>
  21
  22 #include "base/map_util.h"
  23 #include "decision/decision_engine.h"
  24 #include "expr/attribute.h"
  25 #include "expr/node.h"
  26 #include "expr/node_algorithm.h"
  27 #include "expr/node_builder.h"
  28 #include "options/bv_options.h"
  29 #include "options/options.h"
  30 #include "options/proof_options.h"
  31 #include "options/quantifiers_options.h"
  32 #include "preprocessing/assertion_pipeline.h"
  33 #include "proof/cnf_proof.h"
  34 #include "proof/lemma_proof.h"
  35 #include "proof/proof_manager.h"
  36 #include "proof/theory_proof.h"
  37 #include "smt/logic_exception.h"
  38 #include "smt/term_formula_removal.h"
  39 #include "smt_util/lemma_output_channel.h"
  40 #include "smt_util/node_visitor.h"
  41 #include "theory/arith/arith_ite_utils.h"
  42 #include "theory/bv/theory_bv_utils.h"
  43 #include "theory/care_graph.h"
  44 #include "theory/quantifiers/first_order_model.h"
  45 #include "theory/quantifiers/fmf/model_engine.h"
  46 #include "theory/quantifiers/theory_quantifiers.h"
  47 #include "theory/quantifiers_engine.h"
  48 #include "theory/rewriter.h"
  49 #include "theory/theory.h"
  50 #include "theory/theory_model.h"
  51 #include "theory/theory_traits.h"
  52 #include "theory/uf/equality_engine.h"
  53 #include "util/resource_manager.h"
  54
  55 using namespace std;
  56
  57 using namespace CVC4::preprocessing;
  58 using namespace CVC4::theory;
  59
  60 namespace CVC4 {
  61
  62 /* -------------------------------------------------------------------------- */
  63
  64 namespace theory {
  65
  66 /**
  67  * IMPORTANT: The order of the theories is important. For example, strings
  68  *            depends on arith, quantifiers needs to come as the very last.
  69  *            Do not change this order.
  70  */
  71
  72 #define CVC4_FOR_EACH_THEORY                                     \
  73   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BUILTIN)   \
  74   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BOOL)      \
  75   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_UF)        \
  76   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARITH)     \
  77   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_BV)        \
  78   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_FP)        \
  79   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_ARRAYS)    \
  80   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_DATATYPES) \
  81   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SEP)       \
  82   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_SETS)      \
  83   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_STRINGS)   \
  84   CVC4_FOR_EACH_THEORY_STATEMENT(CVC4::theory::THEORY_QUANTIFIERS)
  85
  86 }  // namespace theory
  87
  88 /* -------------------------------------------------------------------------- */
  89
  90 inline void flattenAnd(Node n, std::vector<TNode>& out){
  91   Assert(n.getKind() == kind::AND);
  92   for(Node::iterator i=n.begin(), i_end=n.end(); i != i_end; ++i){
  93     Node curr = *i;
  94     if(curr.getKind() == kind::AND){
  95       flattenAnd(curr, out);
  96     }else{
  97       out.push_back(curr);
  98     }
  99   }
 100 }
 101
 102 inline Node flattenAnd(Node n){
 103   std::vector<TNode> out;
 104   flattenAnd(n, out);
 105   return NodeManager::currentNM()->mkNode(kind::AND, out);
 106 }
 107
 108 /**
 109  * Compute the string for a given theory id. In this module, we use
 110  * THEORY_SAT_SOLVER as an id, which is not a normal id but maps to
 111  * THEORY_LAST. Thus, we need our own string conversion here.
 112  *
 113  * @param id The theory id
 114  * @return The string corresponding to the theory id
 115  */
 116 std::string getTheoryString(theory::TheoryId id)
 117 {
 118   if (id == theory::THEORY_SAT_SOLVER)
 119   {
 120     return "THEORY_SAT_SOLVER";
 121   }
 122   else
 123   {
 124     std::stringstream ss;
 125     ss << id;
 126     return ss.str();
 127   }
 128 }
 129
 130 theory::LemmaStatus TheoryEngine::EngineOutputChannel::lemma(TNode lemma,
 131                                                              ProofRule rule,
 132                                                              bool removable,
 133                                                              bool preprocess,
 134                                                              bool sendAtoms) {
 135   Debug("theory::lemma") << "EngineOutputChannel<" << d_theory << ">::lemma("
 136                          << lemma << ")"
 137                          << ", preprocess = " << preprocess << std::endl;
 138   ++d_statistics.lemmas;
 139   d_engine->d_outputChannelUsed = true;
 140
 141   PROOF({ registerLemmaRecipe(lemma, lemma, preprocess, d_theory); });
 142
 143   theory::LemmaStatus result =
 144       d_engine->lemma(lemma, rule, false, removable, preprocess,
 145                       sendAtoms ? d_theory : theory::THEORY_LAST);
 146   return result;
 147 }
 148
 149 void TheoryEngine::EngineOutputChannel::registerLemmaRecipe(Node lemma, Node originalLemma, bool preprocess, theory::TheoryId theoryId) {
 150   // During CNF conversion, conjunctions will be broken down into
 151   // multiple lemmas. In order for the recipes to match, we have to do
 152   // the same here.
 153   NodeManager* nm = NodeManager::currentNM();
 154
 155   if (preprocess)
 156     lemma = d_engine->preprocess(lemma);
 157
 158   bool negated = (lemma.getKind() == kind::NOT);
 159   Node nnLemma = negated ? lemma[0] : lemma;
 160
 161   switch (nnLemma.getKind()) {
 162
 163   case kind::AND:
 164     if (!negated) {
 165       for (unsigned i = 0; i < nnLemma.getNumChildren(); ++i)
 166         registerLemmaRecipe(nnLemma[i], originalLemma, false, theoryId);
 167     } else {
 168       NodeBuilder<> builder(kind::OR);
 169       for (unsigned i = 0; i < nnLemma.getNumChildren(); ++i)
 170         builder << nnLemma[i].negate();
 171
 172       Node disjunction = (builder.getNumChildren() == 1) ? builder[0] : builder;
 173       registerLemmaRecipe(disjunction, originalLemma, false, theoryId);
 174     }
 175     break;
 176
 177   case kind::EQUAL:
 178     if( nnLemma[0].getType().isBoolean() ){
 179       if (!negated) {
 180         registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0], nnLemma[1].negate()), originalLemma, false, theoryId);
 181         registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0].negate(), nnLemma[1]), originalLemma, false, theoryId);
 182       } else {
 183         registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0], nnLemma[1]), originalLemma, false, theoryId);
 184         registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0].negate(), nnLemma[1].negate()), originalLemma, false, theoryId);
 185       }
 186     }
 187     break;
 188
 189   case kind::ITE:
 190     if (!negated) {
 191       registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0].negate(), nnLemma[1]), originalLemma, false, theoryId);
 192       registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0], nnLemma[2]), originalLemma, false, theoryId);
 193     } else {
 194       registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0].negate(), nnLemma[1].negate()), originalLemma, false, theoryId);
 195       registerLemmaRecipe(nm->mkNode(kind::OR, nnLemma[0], nnLemma[2].negate()), originalLemma, false, theoryId);
 196     }
 197     break;
 198
 199   default:
 200     break;
 201   }
 202
 203   // Theory lemmas have one step that proves the empty clause
 204   LemmaProofRecipe proofRecipe;
 205   Node emptyNode;
 206   LemmaProofRecipe::ProofStep proofStep(theoryId, emptyNode);
 207
 208   // Remember the original lemma, so we can report this later when asked to
 209   proofRecipe.setOriginalLemma(originalLemma);
 210
 211   // Record the assertions and rewrites
 212   Node rewritten;
 213   if (lemma.getKind() == kind::OR) {
 214     for (unsigned i = 0; i < lemma.getNumChildren(); ++i) {
 215       rewritten = theory::Rewriter::rewrite(lemma[i]);
 216       if (rewritten != lemma[i]) {
 217         proofRecipe.addRewriteRule(lemma[i].negate(), rewritten.negate());
 218       }
 219       proofStep.addAssertion(lemma[i]);
 220       proofRecipe.addBaseAssertion(rewritten);
 221     }
 222   } else {
 223     rewritten = theory::Rewriter::rewrite(lemma);
 224     if (rewritten != lemma) {
 225       proofRecipe.addRewriteRule(lemma.negate(), rewritten.negate());
 226     }
 227     proofStep.addAssertion(lemma);
 228     proofRecipe.addBaseAssertion(rewritten);
 229   }
 230   proofRecipe.addStep(proofStep);
 231   ProofManager::getCnfProof()->setProofRecipe(&proofRecipe);
 232 }
 233
 234 theory::LemmaStatus TheoryEngine::EngineOutputChannel::splitLemma(
 235     TNode lemma, bool removable) {
 236   Debug("theory::lemma") << "EngineOutputChannel<" << d_theory << ">::lemma("
 237                          << lemma << ")" << std::endl;
 238   ++d_statistics.lemmas;
 239   d_engine->d_outputChannelUsed = true;
 240
 241   Debug("pf::explain") << "TheoryEngine::EngineOutputChannel::splitLemma( "
 242                        << lemma << " )" << std::endl;
 243   theory::LemmaStatus result =
 244       d_engine->lemma(lemma, RULE_SPLIT, false, removable, false, d_theory);
 245   return result;
 246 }
 247
 248 bool TheoryEngine::EngineOutputChannel::propagate(TNode literal) {
 249   Debug("theory::propagate") << "EngineOutputChannel<" << d_theory
 250                              << ">::propagate(" << literal << ")" << std::endl;
 251   ++d_statistics.propagations;
 252   d_engine->d_outputChannelUsed = true;
 253   return d_engine->propagate(literal, d_theory);
 254 }
 255
 256 void TheoryEngine::EngineOutputChannel::conflict(TNode conflictNode,
 257                                                  std::unique_ptr<Proof> proof)
 258 {
 259   Trace("theory::conflict")
 260       << "EngineOutputChannel<" << d_theory << ">::conflict(" << conflictNode
 261       << ")" << std::endl;
 262   Assert(!proof);  // Theory shouldn't be producing proofs yet
 263   ++d_statistics.conflicts;
 264   d_engine->d_outputChannelUsed = true;
 265   d_engine->conflict(conflictNode, d_theory);
 266 }
 267
 268 void TheoryEngine::finishInit() {
 269
 270   //initialize the quantifiers engine, master equality engine, model, model builder
 271   if( d_logicInfo.isQuantified() ) {
 272     // initialize the quantifiers engine
 273     d_quantEngine = new QuantifiersEngine(d_context, d_userContext, this);
 274     Assert(d_masterEqualityEngine == 0);
 275     d_masterEqualityEngine = new eq::EqualityEngine(d_masterEENotify,getSatContext(), "theory::master", false);
 276
 277     for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
 278       if (d_theoryTable[theoryId]) {
 279         d_theoryTable[theoryId]->setQuantifiersEngine(d_quantEngine);
 280         d_theoryTable[theoryId]->setMasterEqualityEngine(d_masterEqualityEngine);
 281       }
 282     }
 283
 284     d_curr_model_builder = d_quantEngine->getModelBuilder();
 285     d_curr_model = d_quantEngine->getModel();
 286   } else {
 287     d_curr_model = new theory::TheoryModel(
 288         d_userContext, "DefaultModel", options::assignFunctionValues());
 289     d_aloc_curr_model = true;
 290   }
 291   //make the default builder, e.g. in the case that the quantifiers engine does not have a model builder
 292   if( d_curr_model_builder==NULL ){
 293     d_curr_model_builder = new theory::TheoryEngineModelBuilder(this);
 294     d_aloc_curr_model_builder = true;
 295   }
 296
 297   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
 298     if (d_theoryTable[theoryId]) {
 299       // set the decision manager for the theory
 300       d_theoryTable[theoryId]->setDecisionManager(d_decManager.get());
 301       // finish initializing the theory
 302       d_theoryTable[theoryId]->finishInit();
 303     }
 304   }
 305 }
 306
 307 void TheoryEngine::eqNotifyNewClass(TNode t){
 308   if (d_logicInfo.isQuantified()) {
 309     d_quantEngine->eqNotifyNewClass( t );
 310   }
 311 }
 312
 313 TheoryEngine::TheoryEngine(context::Context* context,
 314                            context::UserContext* userContext,
 315                            RemoveTermFormulas& iteRemover,
 316                            const LogicInfo& logicInfo,
 317                            LemmaChannels* channels)
 318     : d_propEngine(nullptr),
 319       d_decisionEngine(nullptr),
 320       d_context(context),
 321       d_userContext(userContext),
 322       d_logicInfo(logicInfo),
 323       d_sharedTerms(this, context),
 324       d_masterEqualityEngine(nullptr),
 325       d_masterEENotify(*this),
 326       d_quantEngine(nullptr),
 327       d_decManager(new DecisionManager(userContext)),
 328       d_curr_model(nullptr),
 329       d_aloc_curr_model(false),
 330       d_curr_model_builder(nullptr),
 331       d_aloc_curr_model_builder(false),
 332       d_eager_model_building(false),
 333       d_ppCache(),
 334       d_possiblePropagations(context),
 335       d_hasPropagated(context),
 336       d_inConflict(context, false),
 337       d_inSatMode(false),
 338       d_hasShutDown(false),
 339       d_incomplete(context, false),
 340       d_propagationMap(context),
 341       d_propagationMapTimestamp(context, 0),
 342       d_propagatedLiterals(context),
 343       d_propagatedLiteralsIndex(context, 0),
 344       d_atomRequests(context),
 345       d_tform_remover(iteRemover),
 346       d_combineTheoriesTime("TheoryEngine::combineTheoriesTime"),
 347       d_true(),
 348       d_false(),
 349       d_interrupted(false),
 350       d_resourceManager(NodeManager::currentResourceManager()),
 351       d_channels(channels),
 352       d_inPreregister(false),
 353       d_factsAsserted(context, false),
 354       d_preRegistrationVisitor(this, context),
 355       d_sharedTermsVisitor(d_sharedTerms),
 356       d_theoryAlternatives(),
 357       d_attr_handle(),
 358       d_arithSubstitutionsAdded("theory::arith::zzz::arith::substitutions", 0)
 359 {
 360   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST;
 361       ++ theoryId)
 362   {
 363     d_theoryTable[theoryId] = NULL;
 364     d_theoryOut[theoryId] = NULL;
 365   }
 366
 367   smtStatisticsRegistry()->registerStat(&d_combineTheoriesTime);
 368   d_true = NodeManager::currentNM()->mkConst<bool>(true);
 369   d_false = NodeManager::currentNM()->mkConst<bool>(false);
 370
 371 #ifdef CVC4_PROOF
 372   ProofManager::currentPM()->initTheoryProofEngine();
 373 #endif
 374
 375   smtStatisticsRegistry()->registerStat(&d_arithSubstitutionsAdded);
 376 }
 377
 378 TheoryEngine::~TheoryEngine() {
 379   Assert(d_hasShutDown);
 380
 381   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
 382     if(d_theoryTable[theoryId] != NULL) {
 383       delete d_theoryTable[theoryId];
 384       delete d_theoryOut[theoryId];
 385     }
 386   }
 387
 388   if( d_aloc_curr_model_builder ){
 389     delete d_curr_model_builder;
 390   }
 391   if( d_aloc_curr_model ){
 392     delete d_curr_model;
 393   }
 394
 395   delete d_quantEngine;
 396
 397   delete d_masterEqualityEngine;
 398
 399   smtStatisticsRegistry()->unregisterStat(&d_combineTheoriesTime);
 400   smtStatisticsRegistry()->unregisterStat(&d_arithSubstitutionsAdded);
 401 }
 402
 403 void TheoryEngine::interrupt() { d_interrupted = true; }
 404 void TheoryEngine::preRegister(TNode preprocessed) {
 405
 406   Debug("theory") << "TheoryEngine::preRegister( " << preprocessed << ")" << std::endl;
 407   if(Dump.isOn("missed-t-propagations")) {
 408     d_possiblePropagations.push_back(preprocessed);
 409   }
 410   d_preregisterQueue.push(preprocessed);
 411
 412   if (!d_inPreregister) {
 413     // We're in pre-register
 414     d_inPreregister = true;
 415
 416     // Process the pre-registration queue
 417     while (!d_preregisterQueue.empty()) {
 418       // Get the next atom to pre-register
 419       preprocessed = d_preregisterQueue.front();
 420       d_preregisterQueue.pop();
 421
 422       if (d_logicInfo.isSharingEnabled() && preprocessed.getKind() == kind::EQUAL) {
 423         // When sharing is enabled, we propagate from the shared terms manager also
 424         d_sharedTerms.addEqualityToPropagate(preprocessed);
 425       }
 426
 427       // the atom should not have free variables
 428       Debug("theory") << "TheoryEngine::preRegister: " << preprocessed
 429                       << std::endl;
 430       Assert(!expr::hasFreeVar(preprocessed));
 431       // Pre-register the terms in the atom
 432       Theory::Set theories = NodeVisitor<PreRegisterVisitor>::run(d_preRegistrationVisitor, preprocessed);
 433       theories = Theory::setRemove(THEORY_BOOL, theories);
 434       // Remove the top theory, if any more that means multiple theories were involved
 435       bool multipleTheories = Theory::setRemove(Theory::theoryOf(preprocessed), theories);
 436       TheoryId i;
 437       // These checks don't work with finite model finding, because it
 438       // uses Rational constants to represent cardinality constraints,
 439       // even though arithmetic isn't actually involved.
 440       if(!options::finiteModelFind()) {
 441         while((i = Theory::setPop(theories)) != THEORY_LAST) {
 442           if(!d_logicInfo.isTheoryEnabled(i)) {
 443             LogicInfo newLogicInfo = d_logicInfo.getUnlockedCopy();
 444             newLogicInfo.enableTheory(i);
 445             newLogicInfo.lock();
 446             stringstream ss;
 447             ss << "The logic was specified as " << d_logicInfo.getLogicString()
 448                << ", which doesn't include " << i
 449                << ", but found a term in that theory." << endl
 450                << "You might want to extend your logic to "
 451                << newLogicInfo.getLogicString() << endl;
 452             throw LogicException(ss.str());
 453           }
 454         }
 455       }
 456       if (multipleTheories) {
 457         // Collect the shared terms if there are multiple theories
 458         NodeVisitor<SharedTermsVisitor>::run(d_sharedTermsVisitor, preprocessed);
 459       }
 460     }
 461
 462     // Leaving pre-register
 463     d_inPreregister = false;
 464   }
 465 }
 466
 467 void TheoryEngine::printAssertions(const char* tag) {
 468   if (Trace.isOn(tag)) {
 469
 470     for (TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
 471       Theory* theory = d_theoryTable[theoryId];
 472       if (theory && d_logicInfo.isTheoryEnabled(theoryId)) {
 473         Trace(tag) << "--------------------------------------------" << endl;
 474         Trace(tag) << "Assertions of " << theory->getId() << ": " << endl;
 475         context::CDList<Assertion>::const_iterator it = theory->facts_begin(), it_end = theory->facts_end();
 476         for (unsigned i = 0; it != it_end; ++ it, ++i) {
 477             if ((*it).isPreregistered) {
 478               Trace(tag) << "[" << i << "]: ";
 479             } else {
 480               Trace(tag) << "(" << i << "): ";
 481             }
 482             Trace(tag) << (*it).assertion << endl;
 483         }
 484
 485         if (d_logicInfo.isSharingEnabled()) {
 486           Trace(tag) << "Shared terms of " << theory->getId() << ": " << endl;
 487           context::CDList<TNode>::const_iterator it = theory->shared_terms_begin(), it_end = theory->shared_terms_end();
 488           for (unsigned i = 0; it != it_end; ++ it, ++i) {
 489               Trace(tag) << "[" << i << "]: " << (*it) << endl;
 490           }
 491         }
 492       }
 493     }
 494   }
 495 }
 496
 497 void TheoryEngine::dumpAssertions(const char* tag) {
 498   if (Dump.isOn(tag)) {
 499     Dump(tag) << CommentCommand("Starting completeness check");
 500     for (TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
 501       Theory* theory = d_theoryTable[theoryId];
 502       if (theory && d_logicInfo.isTheoryEnabled(theoryId)) {
 503         Dump(tag) << CommentCommand("Completeness check");
 504         Dump(tag) << PushCommand();
 505
 506         // Dump the shared terms
 507         if (d_logicInfo.isSharingEnabled()) {
 508           Dump(tag) << CommentCommand("Shared terms");
 509           context::CDList<TNode>::const_iterator it = theory->shared_terms_begin(), it_end = theory->shared_terms_end();
 510           for (unsigned i = 0; it != it_end; ++ it, ++i) {
 511               stringstream ss;
 512               ss << (*it);
 513               Dump(tag) << CommentCommand(ss.str());
 514           }
 515         }
 516
 517         // Dump the assertions
 518         Dump(tag) << CommentCommand("Assertions");
 519         context::CDList<Assertion>::const_iterator it = theory->facts_begin(), it_end = theory->facts_end();
 520         for (; it != it_end; ++ it) {
 521           // Get the assertion
 522           Node assertionNode = (*it).assertion;
 523           // Purify all the terms
 524
 525           if ((*it).isPreregistered) {
 526             Dump(tag) << CommentCommand("Preregistered");
 527           } else {
 528             Dump(tag) << CommentCommand("Shared assertion");
 529           }
 530           Dump(tag) << AssertCommand(assertionNode.toExpr());
 531         }
 532         Dump(tag) << CheckSatCommand();
 533
 534         Dump(tag) << PopCommand();
 535       }
 536     }
 537   }
 538 }
 539
 540 /**
 541  * Check all (currently-active) theories for conflicts.
 542  * @param effort the effort level to use
 543  */
 544 void TheoryEngine::check(Theory::Effort effort) {
 545   // spendResource();
 546
 547   // Reset the interrupt flag
 548   d_interrupted = false;
 549
 550 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 551 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 552 #endif
 553 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 554     if (theory::TheoryTraits<THEORY>::hasCheck && d_logicInfo.isTheoryEnabled(THEORY)) { \
 555        theoryOf(THEORY)->check(effort); \
 556        if (d_inConflict) { \
 557          Debug("conflict") << THEORY << " in conflict. " << std::endl; \
 558          break; \
 559        } \
 560     }
 561
 562   // Do the checking
 563   try {
 564
 565     // Mark the output channel unused (if this is FULL_EFFORT, and nothing
 566     // is done by the theories, no additional check will be needed)
 567     d_outputChannelUsed = false;
 568
 569     // Mark the lemmas flag (no lemmas added)
 570     d_lemmasAdded = false;
 571
 572     Debug("theory") << "TheoryEngine::check(" << effort << "): d_factsAsserted = " << (d_factsAsserted ? "true" : "false") << endl;
 573
 574     // If in full effort, we have a fake new assertion just to jumpstart the checking
 575     if (Theory::fullEffort(effort)) {
 576       d_factsAsserted = true;
 577     }
 578
 579     // Check until done
 580     while (d_factsAsserted && !d_inConflict && !d_lemmasAdded) {
 581
 582       Debug("theory") << "TheoryEngine::check(" << effort << "): running check" << endl;
 583
 584       Trace("theory::assertions") << endl;
 585       if (Trace.isOn("theory::assertions")) {
 586         printAssertions("theory::assertions");
 587       }
 588
 589       if(Theory::fullEffort(effort)) {
 590         Trace("theory::assertions::fulleffort") << endl;
 591         if (Trace.isOn("theory::assertions::fulleffort")) {
 592           printAssertions("theory::assertions::fulleffort");
 593         }
 594       }
 595
 596       // Note that we've discharged all the facts
 597       d_factsAsserted = false;
 598
 599       // Do the checking
 600       CVC4_FOR_EACH_THEORY;
 601
 602       if(Dump.isOn("missed-t-conflicts")) {
 603         Dump("missed-t-conflicts")
 604             << CommentCommand("Completeness check for T-conflicts; expect sat")
 605             << CheckSatCommand();
 606       }
 607
 608       Debug("theory") << "TheoryEngine::check(" << effort << "): running propagation after the initial check" << endl;
 609
 610       // We are still satisfiable, propagate as much as possible
 611       propagate(effort);
 612
 613       // We do combination if all has been processed and we are in fullcheck
 614       if (Theory::fullEffort(effort) && d_logicInfo.isSharingEnabled() && !d_factsAsserted && !d_lemmasAdded && !d_inConflict) {
 615         // Do the combination
 616         Debug("theory") << "TheoryEngine::check(" << effort << "): running combination" << endl;
 617         combineTheories();
 618         if(d_logicInfo.isQuantified()){
 619           d_quantEngine->notifyCombineTheories();
 620         }
 621       }
 622     }
 623
 624     // Must consult quantifiers theory for last call to ensure sat, or otherwise add a lemma
 625     if( Theory::fullEffort(effort) && ! d_inConflict && ! needCheck() ) {
 626       Trace("theory::assertions-model") << endl;
 627       if (Trace.isOn("theory::assertions-model")) {
 628         printAssertions("theory::assertions-model");
 629       }
 630       //checks for theories requiring the model go at last call
 631       d_curr_model->reset();
 632       for (TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
 633         if( theoryId!=THEORY_QUANTIFIERS ){
 634           Theory* theory = d_theoryTable[theoryId];
 635           if (theory && d_logicInfo.isTheoryEnabled(theoryId)) {
 636             if( theory->needsCheckLastEffort() ){
 637               if( !d_curr_model->isBuilt() ){
 638                 if( !d_curr_model_builder->buildModel(d_curr_model) ){
 639                   break;
 640                 }
 641               }
 642               theory->check(Theory::EFFORT_LAST_CALL);
 643             }
 644           }
 645         }
 646       }
 647       if (!d_inConflict)
 648       {
 649         if(d_logicInfo.isQuantified()) {
 650           // quantifiers engine must check at last call effort
 651           d_quantEngine->check(Theory::EFFORT_LAST_CALL);
 652         }
 653       }
 654       if (!d_inConflict && !needCheck())
 655       {
 656         // If d_eager_model_building is false, then we only mark that we
 657         // are in "SAT mode". We build the model later only if the user asks
 658         // for it via getBuiltModel.
 659         d_inSatMode = true;
 660         if (d_eager_model_building && !d_curr_model->isBuilt())
 661         {
 662           d_curr_model_builder->buildModel(d_curr_model);
 663         }
 664       }
 665     }
 666
 667     Debug("theory") << "TheoryEngine::check(" << effort << "): done, we are " << (d_inConflict ? "unsat" : "sat") << (d_lemmasAdded ? " with new lemmas" : " with no new lemmas");
 668     Debug("theory") << ", need check = " << (needCheck() ? "YES" : "NO") << endl;
 669
 670     if( Theory::fullEffort(effort) && !d_inConflict && !needCheck()) {
 671       // case where we are about to answer SAT
 672       if( d_masterEqualityEngine != NULL ){
 673         AlwaysAssert(d_masterEqualityEngine->consistent());
 674       }
 675       if (d_curr_model->isBuilt())
 676       {
 677         // model construction should always succeed unless lemmas were added
 678         AlwaysAssert(d_curr_model->isBuiltSuccess());
 679         if (options::produceModels())
 680         {
 681           // Do post-processing of model from the theories (used for THEORY_SEP
 682           // to construct heap model)
 683           postProcessModel(d_curr_model);
 684           // also call the model builder's post-process model
 685           d_curr_model_builder->postProcessModel(d_incomplete.get(),
 686                                                  d_curr_model);
 687         }
 688       }
 689     }
 690   } catch(const theory::Interrupted&) {
 691     Trace("theory") << "TheoryEngine::check() => interrupted" << endl;
 692   }
 693   // If fulleffort, check all theories
 694   if(Dump.isOn("theory::fullcheck") && Theory::fullEffort(effort)) {
 695     if (!d_inConflict && !needCheck()) {
 696       dumpAssertions("theory::fullcheck");
 697     }
 698   }
 699 }
 700
 701 void TheoryEngine::combineTheories() {
 702
 703   Trace("combineTheories") << "TheoryEngine::combineTheories()" << endl;
 704
 705   TimerStat::CodeTimer combineTheoriesTimer(d_combineTheoriesTime);
 706
 707   // Care graph we'll be building
 708   CareGraph careGraph;
 709
 710 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 711 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 712 #endif
 713 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 714   if (theory::TheoryTraits<THEORY>::isParametric && d_logicInfo.isTheoryEnabled(THEORY)) { \
 715     theoryOf(THEORY)->getCareGraph(&careGraph); \
 716   }
 717
 718   // Call on each parametric theory to give us its care graph
 719   CVC4_FOR_EACH_THEORY;
 720
 721   Trace("combineTheories") << "TheoryEngine::combineTheories(): care graph size = " << careGraph.size() << endl;
 722
 723   // Now add splitters for the ones we are interested in
 724   CareGraph::const_iterator care_it = careGraph.begin();
 725   CareGraph::const_iterator care_it_end = careGraph.end();
 726
 727   for (; care_it != care_it_end; ++ care_it) {
 728     const CarePair& carePair = *care_it;
 729
 730     Debug("combineTheories") << "TheoryEngine::combineTheories(): checking " << carePair.a << " = " << carePair.b << " from " << carePair.theory << endl;
 731
 732     Assert(d_sharedTerms.isShared(carePair.a) || carePair.a.isConst());
 733     Assert(d_sharedTerms.isShared(carePair.b) || carePair.b.isConst());
 734
 735     // The equality in question (order for no repetition)
 736     Node equality = carePair.a.eqNode(carePair.b);
 737     // EqualityStatus es = getEqualityStatus(carePair.a, carePair.b);
 738     // Debug("combineTheories") << "TheoryEngine::combineTheories(): " <<
 739     //   (es == EQUALITY_TRUE_AND_PROPAGATED ? "EQUALITY_TRUE_AND_PROPAGATED" :
 740     //   es == EQUALITY_FALSE_AND_PROPAGATED ? "EQUALITY_FALSE_AND_PROPAGATED" :
 741     //   es == EQUALITY_TRUE ? "EQUALITY_TRUE" :
 742     //   es == EQUALITY_FALSE ? "EQUALITY_FALSE" :
 743     //   es == EQUALITY_TRUE_IN_MODEL ? "EQUALITY_TRUE_IN_MODEL" :
 744     //   es == EQUALITY_FALSE_IN_MODEL ? "EQUALITY_FALSE_IN_MODEL" :
 745     //   es == EQUALITY_UNKNOWN ? "EQUALITY_UNKNOWN" :
 746     //    "Unexpected case") << endl;
 747
 748     // We need to split on it
 749     Debug("combineTheories") << "TheoryEngine::combineTheories(): requesting a split " << endl;
 750
 751     lemma(equality.orNode(equality.notNode()), RULE_INVALID, false, false, false, carePair.theory);
 752
 753     // This code is supposed to force preference to follow what the theory models already have
 754     // but it doesn't seem to make a big difference - need to explore more -Clark
 755     // if (true) {
 756     //   if (es == EQUALITY_TRUE || es == EQUALITY_TRUE_IN_MODEL) {
 757     Node e = ensureLiteral(equality);
 758     d_propEngine->requirePhase(e, true);
 759     //   }
 760     //   else if (es == EQUALITY_FALSE_IN_MODEL) {
 761     //     Node e = ensureLiteral(equality);
 762     //     d_propEngine->requirePhase(e, false);
 763     //   }
 764     // }
 765   }
 766 }
 767
 768 void TheoryEngine::propagate(Theory::Effort effort) {
 769   // Reset the interrupt flag
 770   d_interrupted = false;
 771
 772   // Definition of the statement that is to be run by every theory
 773 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 774 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 775 #endif
 776 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 777   if (theory::TheoryTraits<THEORY>::hasPropagate && d_logicInfo.isTheoryEnabled(THEORY)) { \
 778     theoryOf(THEORY)->propagate(effort); \
 779   }
 780
 781   // Reset the interrupt flag
 782   d_interrupted = false;
 783
 784   // Propagate for each theory using the statement above
 785   CVC4_FOR_EACH_THEORY;
 786
 787   if(Dump.isOn("missed-t-propagations")) {
 788     for(unsigned i = 0; i < d_possiblePropagations.size(); ++i) {
 789       Node atom = d_possiblePropagations[i];
 790       bool value;
 791       if(d_propEngine->hasValue(atom, value)) {
 792         continue;
 793       }
 794       // Doesn't have a value, check it (and the negation)
 795       if(d_hasPropagated.find(atom) == d_hasPropagated.end()) {
 796         Dump("missed-t-propagations")
 797           << CommentCommand("Completeness check for T-propagations; expect invalid")
 798           << EchoCommand(atom.toString())
 799           << QueryCommand(atom.toExpr())
 800           << EchoCommand(atom.notNode().toString())
 801           << QueryCommand(atom.notNode().toExpr());
 802       }
 803     }
 804   }
 805 }
 806
 807 Node TheoryEngine::getNextDecisionRequest()
 808 {
 809   return d_decManager->getNextDecisionRequest();
 810 }
 811
 812 bool TheoryEngine::properConflict(TNode conflict) const {
 813   bool value;
 814   if (conflict.getKind() == kind::AND) {
 815     for (unsigned i = 0; i < conflict.getNumChildren(); ++ i) {
 816       if (! getPropEngine()->hasValue(conflict[i], value)) {
 817         Debug("properConflict") << "Bad conflict is due to unassigned atom: "
 818                                 << conflict[i] << endl;
 819         return false;
 820       }
 821       if (! value) {
 822         Debug("properConflict") << "Bad conflict is due to false atom: "
 823                                 << conflict[i] << endl;
 824         return false;
 825       }
 826       if (conflict[i] != Rewriter::rewrite(conflict[i])) {
 827         Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
 828                                 << conflict[i] << " vs " << Rewriter::rewrite(conflict[i]) << endl;
 829         return false;
 830       }
 831     }
 832   } else {
 833     if (! getPropEngine()->hasValue(conflict, value)) {
 834       Debug("properConflict") << "Bad conflict is due to unassigned atom: "
 835                               << conflict << endl;
 836       return false;
 837     }
 838     if(! value) {
 839       Debug("properConflict") << "Bad conflict is due to false atom: "
 840                               << conflict << endl;
 841       return false;
 842     }
 843     if (conflict != Rewriter::rewrite(conflict)) {
 844       Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
 845                               << conflict << " vs " << Rewriter::rewrite(conflict) << endl;
 846       return false;
 847     }
 848   }
 849   return true;
 850 }
 851
 852 bool TheoryEngine::properPropagation(TNode lit) const {
 853   if(!getPropEngine()->isSatLiteral(lit)) {
 854     return false;
 855   }
 856   bool b;
 857   return !getPropEngine()->hasValue(lit, b);
 858 }
 859
 860 bool TheoryEngine::properExplanation(TNode node, TNode expl) const {
 861   // Explanation must be either a conjunction of true literals that have true SAT values already
 862   // or a singled literal that has a true SAT value already.
 863   if (expl.getKind() == kind::AND) {
 864     for (unsigned i = 0; i < expl.getNumChildren(); ++ i) {
 865       bool value;
 866       if (!d_propEngine->hasValue(expl[i], value) || !value) {
 867         return false;
 868       }
 869     }
 870   } else {
 871     bool value;
 872     return d_propEngine->hasValue(expl, value) && value;
 873   }
 874   return true;
 875 }
 876
 877 bool TheoryEngine::collectModelInfo(theory::TheoryModel* m)
 878 {
 879   //have shared term engine collectModelInfo
 880   //  d_sharedTerms.collectModelInfo( m );
 881   // Consult each active theory to get all relevant information
 882   // concerning the model.
 883   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST; ++theoryId) {
 884     if(d_logicInfo.isTheoryEnabled(theoryId)) {
 885       Trace("model-builder") << "  CollectModelInfo on theory: " << theoryId << endl;
 886       if (!d_theoryTable[theoryId]->collectModelInfo(m))
 887       {
 888         return false;
 889       }
 890     }
 891   }
 892   Trace("model-builder") << "  CollectModelInfo boolean variables" << std::endl;
 893   // Get the Boolean variables
 894   vector<TNode> boolVars;
 895   d_propEngine->getBooleanVariables(boolVars);
 896   vector<TNode>::iterator it, iend = boolVars.end();
 897   bool hasValue, value;
 898   for (it = boolVars.begin(); it != iend; ++it) {
 899     TNode var = *it;
 900     hasValue = d_propEngine->hasValue(var, value);
 901     // TODO: Assert that hasValue is true?
 902     if (!hasValue) {
 903       Trace("model-builder-assertions")
 904           << "    has no value : " << var << std::endl;
 905       value = false;
 906     }
 907     Trace("model-builder-assertions") << "(assert" << (value ? " " : " (not ") << var << (value ? ");" : "));") << endl;
 908     if (!m->assertPredicate(var, value))
 909     {
 910       return false;
 911     }
 912   }
 913   return true;
 914 }
 915
 916 void TheoryEngine::postProcessModel( theory::TheoryModel* m ){
 917   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST; ++theoryId) {
 918     if(d_logicInfo.isTheoryEnabled(theoryId)) {
 919       Trace("model-builder-debug") << "  PostProcessModel on theory: " << theoryId << endl;
 920       d_theoryTable[theoryId]->postProcessModel( m );
 921     }
 922   }
 923 }
 924
 925 TheoryModel* TheoryEngine::getModel() {
 926   return d_curr_model;
 927 }
 928
 929 TheoryModel* TheoryEngine::getBuiltModel()
 930 {
 931   if (!d_curr_model->isBuilt())
 932   {
 933     // If this method was called, we should be in SAT mode, and produceModels
 934     // should be true.
 935     AlwaysAssert(options::produceModels());
 936     if (!d_inSatMode)
 937     {
 938       // not available, perhaps due to interuption.
 939       return nullptr;
 940     }
 941     // must build model at this point
 942     d_curr_model_builder->buildModel(d_curr_model);
 943   }
 944   return d_curr_model;
 945 }
 946
 947 bool TheoryEngine::getSynthSolutions(
 948     std::map<Node, std::map<Node, Node>>& sol_map)
 949 {
 950   if (d_quantEngine)
 951   {
 952     return d_quantEngine->getSynthSolutions(sol_map);
 953   }
 954   // we are not in a quantified logic, there is no synthesis solution
 955   return false;
 956 }
 957
 958 bool TheoryEngine::presolve() {
 959   // Reset the interrupt flag
 960   d_interrupted = false;
 961
 962   // Reset the decision manager. This clears its decision strategies that are
 963   // no longer valid in this user context.
 964   d_decManager->presolve();
 965
 966   try {
 967     // Definition of the statement that is to be run by every theory
 968 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 969 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 970 #endif
 971 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 972     if (theory::TheoryTraits<THEORY>::hasPresolve) {    \
 973       theoryOf(THEORY)->presolve(); \
 974       if(d_inConflict) { \
 975         return true; \
 976       } \
 977     }
 978
 979     // Presolve for each theory using the statement above
 980     CVC4_FOR_EACH_THEORY;
 981   } catch(const theory::Interrupted&) {
 982     Trace("theory") << "TheoryEngine::presolve() => interrupted" << endl;
 983   }
 984   // return whether we have a conflict
 985   return false;
 986 }/* TheoryEngine::presolve() */
 987
 988 void TheoryEngine::postsolve() {
 989   // no longer in SAT mode
 990   d_inSatMode = false;
 991   // Reset the interrupt flag
 992   d_interrupted = false;
 993   bool CVC4_UNUSED wasInConflict = d_inConflict;
 994
 995   try {
 996     // Definition of the statement that is to be run by every theory
 997 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 998 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 999 #endif
1000 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY)    \
1001   if (theory::TheoryTraits<THEORY>::hasPostsolve) \
1002   {                                               \
1003     theoryOf(THEORY)->postsolve();                \
1004     Assert(!d_inConflict || wasInConflict)        \
1005         << "conflict raised during postsolve()";  \
1006   }
1007
1008     // Postsolve for each theory using the statement above
1009     CVC4_FOR_EACH_THEORY;
1010   } catch(const theory::Interrupted&) {
1011     Trace("theory") << "TheoryEngine::postsolve() => interrupted" << endl;
1012   }
1013 }/* TheoryEngine::postsolve() */
1014
1015
1016 void TheoryEngine::notifyRestart() {
1017   // Reset the interrupt flag
1018   d_interrupted = false;
1019
1020   // Definition of the statement that is to be run by every theory
1021 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
1022 #undef CVC4_FOR_EACH_THEORY_STATEMENT
1023 #endif
1024 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
1025   if (theory::TheoryTraits<THEORY>::hasNotifyRestart && d_logicInfo.isTheoryEnabled(THEORY)) { \
1026     theoryOf(THEORY)->notifyRestart(); \
1027   }
1028
1029   // notify each theory using the statement above
1030   CVC4_FOR_EACH_THEORY;
1031 }
1032
1033 void TheoryEngine::ppStaticLearn(TNode in, NodeBuilder<>& learned) {
1034   // Reset the interrupt flag
1035   d_interrupted = false;
1036
1037   // Definition of the statement that is to be run by every theory
1038 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
1039 #undef CVC4_FOR_EACH_THEORY_STATEMENT
1040 #endif
1041 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
1042   if (theory::TheoryTraits<THEORY>::hasPpStaticLearn) { \
1043     theoryOf(THEORY)->ppStaticLearn(in, learned); \
1044   }
1045
1046   // static learning for each theory using the statement above
1047   CVC4_FOR_EACH_THEORY;
1048 }
1049
1050 void TheoryEngine::shutdown() {
1051   // Set this first; if a Theory shutdown() throws an exception,
1052   // at least the destruction of the TheoryEngine won't confound
1053   // matters.
1054   d_hasShutDown = true;
1055
1056   // Shutdown all the theories
1057   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST; ++theoryId) {
1058     if(d_theoryTable[theoryId]) {
1059       theoryOf(theoryId)->shutdown();
1060     }
1061   }
1062
1063   d_ppCache.clear();
1064 }
1065
1066 theory::Theory::PPAssertStatus TheoryEngine::solve(TNode literal, SubstitutionMap& substitutionOut) {
1067   // Reset the interrupt flag
1068   d_interrupted = false;
1069
1070   TNode atom = literal.getKind() == kind::NOT ? literal[0] : literal;
1071   Trace("theory::solve") << "TheoryEngine::solve(" << literal << "): solving with " << theoryOf(atom)->getId() << endl;
1072
1073   if(! d_logicInfo.isTheoryEnabled(Theory::theoryOf(atom)) &&
1074      Theory::theoryOf(atom) != THEORY_SAT_SOLVER) {
1075     stringstream ss;
1076     ss << "The logic was specified as " << d_logicInfo.getLogicString()
1077        << ", which doesn't include " << Theory::theoryOf(atom)
1078        << ", but got a preprocessing-time fact for that theory." << endl
1079        << "The fact:" << endl
1080        << literal;
1081     throw LogicException(ss.str());
1082   }
1083
1084   Theory::PPAssertStatus solveStatus = theoryOf(atom)->ppAssert(literal, substitutionOut);
1085   Trace("theory::solve") << "TheoryEngine::solve(" << literal << ") => " << solveStatus << endl;
1086   return solveStatus;
1087 }
1088
1089 // Recursively traverse a term and call the theory rewriter on its sub-terms
1090 Node TheoryEngine::ppTheoryRewrite(TNode term) {
1091   NodeMap::iterator find = d_ppCache.find(term);
1092   if (find != d_ppCache.end()) {
1093     return (*find).second;
1094   }
1095   unsigned nc = term.getNumChildren();
1096   if (nc == 0) {
1097     return theoryOf(term)->ppRewrite(term);
1098   }
1099   Trace("theory-pp") << "ppTheoryRewrite { " << term << endl;
1100
1101   Node newTerm;
1102   // do not rewrite inside quantifiers
1103   if (term.isClosure())
1104   {
1105     newTerm = Rewriter::rewrite(term);
1106   }
1107   else
1108   {
1109     NodeBuilder<> newNode(term.getKind());
1110     if (term.getMetaKind() == kind::metakind::PARAMETERIZED) {
1111       newNode << term.getOperator();
1112     }
1113     unsigned i;
1114     for (i = 0; i < nc; ++i) {
1115       newNode << ppTheoryRewrite(term[i]);
1116     }
1117     newTerm = Rewriter::rewrite(Node(newNode));
1118   }
1119   Node newTerm2 = theoryOf(newTerm)->ppRewrite(newTerm);
1120   if (newTerm != newTerm2) {
1121     newTerm = ppTheoryRewrite(Rewriter::rewrite(newTerm2));
1122   }
1123   d_ppCache[term] = newTerm;
1124   Trace("theory-pp")<< "ppTheoryRewrite returning " << newTerm << "}" << endl;
1125   return newTerm;
1126 }
1127
1128
1129 void TheoryEngine::preprocessStart()
1130 {
1131   d_ppCache.clear();
1132 }
1133
1134
1135 struct preprocess_stack_element {
1136   TNode node;
1137   bool children_added;
1138   preprocess_stack_element(TNode node)
1139   : node(node), children_added(false) {}
1140 };/* struct preprocess_stack_element */
1141
1142
1143 Node TheoryEngine::preprocess(TNode assertion) {
1144
1145   Trace("theory::preprocess") << "TheoryEngine::preprocess(" << assertion << ")" << endl;
1146   // spendResource();
1147
1148   // Do a topological sort of the subexpressions and substitute them
1149   vector<preprocess_stack_element> toVisit;
1150   toVisit.push_back(assertion);
1151
1152   while (!toVisit.empty())
1153   {
1154     // The current node we are processing
1155     preprocess_stack_element& stackHead = toVisit.back();
1156     TNode current = stackHead.node;
1157
1158     Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion << "): processing " << current << endl;
1159
1160     // If node already in the cache we're done, pop from the stack
1161     NodeMap::iterator find = d_ppCache.find(current);
1162     if (find != d_ppCache.end()) {
1163       toVisit.pop_back();
1164       continue;
1165     }
1166
1167     if(! d_logicInfo.isTheoryEnabled(Theory::theoryOf(current)) &&
1168        Theory::theoryOf(current) != THEORY_SAT_SOLVER) {
1169       stringstream ss;
1170       ss << "The logic was specified as " << d_logicInfo.getLogicString()
1171          << ", which doesn't include " << Theory::theoryOf(current)
1172          << ", but got a preprocessing-time fact for that theory." << endl
1173          << "The fact:" << endl
1174          << current;
1175       throw LogicException(ss.str());
1176     }
1177
1178     // If this is an atom, we preprocess its terms with the theory ppRewriter
1179     if (Theory::theoryOf(current) != THEORY_BOOL) {
1180       Node ppRewritten = ppTheoryRewrite(current);
1181       d_ppCache[current] = ppRewritten;
1182       Assert(Rewriter::rewrite(d_ppCache[current]) == d_ppCache[current]);
1183       continue;
1184     }
1185
1186     // Not yet substituted, so process
1187     if (stackHead.children_added) {
1188       // Children have been processed, so substitute
1189       NodeBuilder<> builder(current.getKind());
1190       if (current.getMetaKind() == kind::metakind::PARAMETERIZED) {
1191         builder << current.getOperator();
1192       }
1193       for (unsigned i = 0; i < current.getNumChildren(); ++ i) {
1194         Assert(d_ppCache.find(current[i]) != d_ppCache.end());
1195         builder << d_ppCache[current[i]];
1196       }
1197       // Mark the substitution and continue
1198       Node result = builder;
1199       if (result != current) {
1200         result = Rewriter::rewrite(result);
1201       }
1202       Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion << "): setting " << current << " -> " << result << endl;
1203       d_ppCache[current] = result;
1204       toVisit.pop_back();
1205     } else {
1206       // Mark that we have added the children if any
1207       if (current.getNumChildren() > 0) {
1208         stackHead.children_added = true;
1209         // We need to add the children
1210         for(TNode::iterator child_it = current.begin(); child_it != current.end(); ++ child_it) {
1211           TNode childNode = *child_it;
1212           NodeMap::iterator childFind = d_ppCache.find(childNode);
1213           if (childFind == d_ppCache.end()) {
1214             toVisit.push_back(childNode);
1215           }
1216         }
1217       } else {
1218         // No children, so we're done
1219         Debug("substitution::internal") << "SubstitutionMap::internalSubstitute(" << assertion << "): setting " << current << " -> " << current << endl;
1220         d_ppCache[current] = current;
1221         toVisit.pop_back();
1222       }
1223     }
1224   }
1225
1226   // Return the substituted version
1227   return d_ppCache[assertion];
1228 }
1229
1230 void TheoryEngine::notifyPreprocessedAssertions(
1231     const std::vector<Node>& assertions) {
1232   // call all the theories
1233   for (TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST;
1234        ++theoryId) {
1235     if (d_theoryTable[theoryId]) {
1236       theoryOf(theoryId)->ppNotifyAssertions(assertions);
1237     }
1238   }
1239 }
1240
1241 bool TheoryEngine::markPropagation(TNode assertion, TNode originalAssertion, theory::TheoryId toTheoryId, theory::TheoryId fromTheoryId) {
1242
1243   // What and where we are asserting
1244   NodeTheoryPair toAssert(assertion, toTheoryId, d_propagationMapTimestamp);
1245   // What and where it came from
1246   NodeTheoryPair toExplain(originalAssertion, fromTheoryId, d_propagationMapTimestamp);
1247
1248   // See if the theory already got this literal
1249   PropagationMap::const_iterator find = d_propagationMap.find(toAssert);
1250   if (find != d_propagationMap.end()) {
1251     // The theory already knows this
1252     Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): already there" << endl;
1253     return false;
1254   }
1255
1256   Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): marking [" << d_propagationMapTimestamp << "] " << assertion << ", " << toTheoryId << " from " << originalAssertion << ", " << fromTheoryId << endl;
1257
1258   // Mark the propagation
1259   d_propagationMap[toAssert] = toExplain;
1260   d_propagationMapTimestamp = d_propagationMapTimestamp + 1;
1261
1262   return true;
1263 }
1264
1265
1266 void TheoryEngine::assertToTheory(TNode assertion, TNode originalAssertion, theory::TheoryId toTheoryId, theory::TheoryId fromTheoryId) {
1267
1268   Trace("theory::assertToTheory") << "TheoryEngine::assertToTheory(" << assertion << ", " << originalAssertion << "," << toTheoryId << ", " << fromTheoryId << ")" << endl;
1269
1270   Assert(toTheoryId != fromTheoryId);
1271   if(toTheoryId != THEORY_SAT_SOLVER &&
1272      ! d_logicInfo.isTheoryEnabled(toTheoryId)) {
1273     stringstream ss;
1274     ss << "The logic was specified as " << d_logicInfo.getLogicString()
1275        << ", which doesn't include " << toTheoryId
1276        << ", but got an asserted fact to that theory." << endl
1277        << "The fact:" << endl
1278        << assertion;
1279     throw LogicException(ss.str());
1280   }
1281
1282   if (d_inConflict) {
1283     return;
1284   }
1285
1286   // If sharing is disabled, things are easy
1287   if (!d_logicInfo.isSharingEnabled()) {
1288     Assert(assertion == originalAssertion);
1289     if (fromTheoryId == THEORY_SAT_SOLVER) {
1290       // Send to the apropriate theory
1291       theory::Theory* toTheory = theoryOf(toTheoryId);
1292       // We assert it, and we know it's preregistereed
1293       toTheory->assertFact(assertion, true);
1294       // Mark that we have more information
1295       d_factsAsserted = true;
1296     } else {
1297       Assert(toTheoryId == THEORY_SAT_SOLVER);
1298       // Check for propositional conflict
1299       bool value;
1300       if (d_propEngine->hasValue(assertion, value)) {
1301         if (!value) {
1302           Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion << ", " << toTheoryId << ", " << fromTheoryId << "): conflict (no sharing)" << endl;
1303           d_inConflict = true;
1304         } else {
1305           return;
1306         }
1307       }
1308       d_propagatedLiterals.push_back(assertion);
1309     }
1310     return;
1311   }
1312
1313   // Polarity of the assertion
1314   bool polarity = assertion.getKind() != kind::NOT;
1315
1316   // Atom of the assertion
1317   TNode atom = polarity ? assertion : assertion[0];
1318
1319   // If sending to the shared terms database, it's also simple
1320   if (toTheoryId == THEORY_BUILTIN) {
1321     Assert(atom.getKind() == kind::EQUAL)
1322         << "atom should be an EQUALity, not `" << atom << "'";
1323     if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1324       d_sharedTerms.assertEquality(atom, polarity, assertion);
1325     }
1326     return;
1327   }
1328
1329   // Things from the SAT solver are already normalized, so they go
1330   // directly to the apropriate theory
1331   if (fromTheoryId == THEORY_SAT_SOLVER) {
1332     // We know that this is normalized, so just send it off to the theory
1333     if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1334       // Is it preregistered
1335       bool preregistered = d_propEngine->isSatLiteral(assertion) && Theory::theoryOf(assertion) == toTheoryId;
1336       // We assert it
1337       theoryOf(toTheoryId)->assertFact(assertion, preregistered);
1338       // Mark that we have more information
1339       d_factsAsserted = true;
1340     }
1341     return;
1342   }
1343
1344   // Propagations to the SAT solver are just enqueued for pickup by
1345   // the SAT solver later
1346   if (toTheoryId == THEORY_SAT_SOLVER) {
1347     if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1348       // Enqueue for propagation to the SAT solver
1349       d_propagatedLiterals.push_back(assertion);
1350       // Check for propositional conflicts
1351       bool value;
1352       if (d_propEngine->hasValue(assertion, value) && !value) {
1353           Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion << ", " << toTheoryId << ", " << fromTheoryId << "): conflict (sharing)" << endl;
1354         d_inConflict = true;
1355       }
1356     }
1357     return;
1358   }
1359
1360   Assert(atom.getKind() == kind::EQUAL);
1361
1362   // Normalize
1363   Node normalizedLiteral = Rewriter::rewrite(assertion);
1364
1365   // See if it rewrites false directly -> conflict
1366   if (normalizedLiteral.isConst()) {
1367     if (!normalizedLiteral.getConst<bool>()) {
1368       // Mark the propagation for explanations
1369       if (markPropagation(normalizedLiteral, originalAssertion, toTheoryId, fromTheoryId)) {
1370         // Get the explanation (conflict will figure out where it came from)
1371         conflict(normalizedLiteral, toTheoryId);
1372       } else {
1373         Unreachable();
1374       }
1375       return;
1376     }
1377   }
1378
1379   // Try and assert (note that we assert the non-normalized one)
1380   if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1381     // Check if has been pre-registered with the theory
1382     bool preregistered = d_propEngine->isSatLiteral(assertion) && Theory::theoryOf(assertion) == toTheoryId;
1383     // Assert away
1384     theoryOf(toTheoryId)->assertFact(assertion, preregistered);
1385     d_factsAsserted = true;
1386   }
1387
1388   return;
1389 }
1390
1391 void TheoryEngine::assertFact(TNode literal)
1392 {
1393   Trace("theory") << "TheoryEngine::assertFact(" << literal << ")" << endl;
1394
1395   // spendResource();
1396
1397   // If we're in conflict, nothing to do
1398   if (d_inConflict) {
1399     return;
1400   }
1401
1402   // Get the atom
1403   bool polarity = literal.getKind() != kind::NOT;
1404   TNode atom = polarity ? literal : literal[0];
1405
1406   if (d_logicInfo.isSharingEnabled()) {
1407
1408     // If any shared terms, it's time to do sharing work
1409     if (d_sharedTerms.hasSharedTerms(atom)) {
1410       // Notify the theories the shared terms
1411       SharedTermsDatabase::shared_terms_iterator it = d_sharedTerms.begin(atom);
1412       SharedTermsDatabase::shared_terms_iterator it_end = d_sharedTerms.end(atom);
1413       for (; it != it_end; ++ it) {
1414         TNode term = *it;
1415         Theory::Set theories = d_sharedTerms.getTheoriesToNotify(atom, term);
1416         for (TheoryId id = THEORY_FIRST; id != THEORY_LAST; ++ id) {
1417           if (Theory::setContains(id, theories)) {
1418             theoryOf(id)->addSharedTermInternal(term);
1419           }
1420         }
1421         d_sharedTerms.markNotified(term, theories);
1422       }
1423     }
1424
1425     // If it's an equality, assert it to the shared term manager, even though the terms are not
1426     // yet shared. As the terms become shared later, the shared terms manager will then add them
1427     // to the assert the equality to the interested theories
1428     if (atom.getKind() == kind::EQUAL) {
1429       // Assert it to the the owning theory
1430       assertToTheory(literal, literal, /* to */ Theory::theoryOf(atom), /* from */ THEORY_SAT_SOLVER);
1431       // Shared terms manager will assert to interested theories directly, as the terms become shared
1432       assertToTheory(literal, literal, /* to */ THEORY_BUILTIN, /* from */ THEORY_SAT_SOLVER);
1433
1434       // Now, let's check for any atom triggers from lemmas
1435       AtomRequests::atom_iterator it = d_atomRequests.getAtomIterator(atom);
1436       while (!it.done()) {
1437         const AtomRequests::Request& request = it.get();
1438         Node toAssert = polarity ? (Node) request.atom : request.atom.notNode();
1439         Debug("theory::atoms") << "TheoryEngine::assertFact(" << literal << "): sending requested " << toAssert << endl;
1440         assertToTheory(toAssert, literal, request.toTheory, THEORY_SAT_SOLVER);
1441         it.next();
1442       }
1443
1444     } else {
1445       // Not an equality, just assert to the appropriate theory
1446       assertToTheory(literal, literal, /* to */ Theory::theoryOf(atom), /* from */ THEORY_SAT_SOLVER);
1447     }
1448   } else {
1449     // Assert the fact to the appropriate theory directly
1450     assertToTheory(literal, literal, /* to */ Theory::theoryOf(atom), /* from */ THEORY_SAT_SOLVER);
1451   }
1452 }
1453
1454 bool TheoryEngine::propagate(TNode literal, theory::TheoryId theory) {
1455
1456   Debug("theory::propagate") << "TheoryEngine::propagate(" << literal << ", " << theory << ")" << endl;
1457
1458   // spendResource();
1459
1460   if(Dump.isOn("t-propagations")) {
1461     Dump("t-propagations") << CommentCommand("negation of theory propagation: expect valid")
1462                            << QueryCommand(literal.toExpr());
1463   }
1464   if(Dump.isOn("missed-t-propagations")) {
1465     d_hasPropagated.insert(literal);
1466   }
1467
1468   // Get the atom
1469   bool polarity = literal.getKind() != kind::NOT;
1470   TNode atom = polarity ? literal : literal[0];
1471
1472   if (d_logicInfo.isSharingEnabled() && atom.getKind() == kind::EQUAL) {
1473     if (d_propEngine->isSatLiteral(literal)) {
1474       // We propagate SAT literals to SAT
1475       assertToTheory(literal, literal, /* to */ THEORY_SAT_SOLVER, /* from */ theory);
1476     }
1477     if (theory != THEORY_BUILTIN) {
1478       // Assert to the shared terms database
1479       assertToTheory(literal, literal, /* to */ THEORY_BUILTIN, /* from */ theory);
1480     }
1481   } else {
1482     // We could be propagating a unit-clause lemma. In this case, we need to provide a
1483     // recipe.
1484     // TODO: Consider putting this someplace else? This is the only refence to the proof
1485     // manager in this class.
1486
1487     PROOF({
1488         LemmaProofRecipe proofRecipe;
1489         proofRecipe.addBaseAssertion(literal);
1490
1491         Node emptyNode;
1492         LemmaProofRecipe::ProofStep proofStep(theory, emptyNode);
1493         proofStep.addAssertion(literal);
1494         proofRecipe.addStep(proofStep);
1495
1496         ProofManager::getCnfProof()->setProofRecipe(&proofRecipe);
1497       });
1498
1499     // Just send off to the SAT solver
1500     Assert(d_propEngine->isSatLiteral(literal));
1501     assertToTheory(literal, literal, /* to */ THEORY_SAT_SOLVER, /* from */ theory);
1502   }
1503
1504   return !d_inConflict;
1505 }
1506
1507 const LogicInfo& TheoryEngine::getLogicInfo() const { return d_logicInfo; }
1508
1509 theory::EqualityStatus TheoryEngine::getEqualityStatus(TNode a, TNode b) {
1510   Assert(a.getType().isComparableTo(b.getType()));
1511   if (d_sharedTerms.isShared(a) && d_sharedTerms.isShared(b)) {
1512     if (d_sharedTerms.areEqual(a,b)) {
1513       return EQUALITY_TRUE_AND_PROPAGATED;
1514     }
1515     else if (d_sharedTerms.areDisequal(a,b)) {
1516       return EQUALITY_FALSE_AND_PROPAGATED;
1517     }
1518   }
1519   return theoryOf(Theory::theoryOf(a.getType()))->getEqualityStatus(a, b);
1520 }
1521
1522 Node TheoryEngine::getModelValue(TNode var) {
1523   if (var.isConst())
1524   {
1525     // the model value of a constant must be itself
1526     return var;
1527   }
1528   Assert(d_sharedTerms.isShared(var));
1529   return theoryOf(Theory::theoryOf(var.getType()))->getModelValue(var);
1530 }
1531
1532
1533 Node TheoryEngine::ensureLiteral(TNode n) {
1534   Debug("ensureLiteral") << "rewriting: " << n << std::endl;
1535   Node rewritten = Rewriter::rewrite(n);
1536   Debug("ensureLiteral") << "      got: " << rewritten << std::endl;
1537   Node preprocessed = preprocess(rewritten);
1538   Debug("ensureLiteral") << "preprocessed: " << preprocessed << std::endl;
1539   d_propEngine->ensureLiteral(preprocessed);
1540   return preprocessed;
1541 }
1542
1543
1544 void TheoryEngine::printInstantiations( std::ostream& out ) {
1545   if( d_quantEngine ){
1546     d_quantEngine->printInstantiations( out );
1547   }else{
1548     out << "Internal error : instantiations not available when quantifiers are not present." << std::endl;
1549     Assert(false);
1550   }
1551 }
1552
1553 void TheoryEngine::printSynthSolution( std::ostream& out ) {
1554   if( d_quantEngine ){
1555     d_quantEngine->printSynthSolution( out );
1556   }else{
1557     out << "Internal error : synth solution not available when quantifiers are not present." << std::endl;
1558     Assert(false);
1559   }
1560 }
1561
1562 void TheoryEngine::getInstantiatedQuantifiedFormulas( std::vector< Node >& qs ) {
1563   if( d_quantEngine ){
1564     d_quantEngine->getInstantiatedQuantifiedFormulas( qs );
1565   }else{
1566     Assert(false);
1567   }
1568 }
1569
1570 void TheoryEngine::getInstantiations( Node q, std::vector< Node >& insts ) {
1571   if( d_quantEngine ){
1572     d_quantEngine->getInstantiations( q, insts );
1573   }else{
1574     Assert(false);
1575   }
1576 }
1577
1578 void TheoryEngine::getInstantiationTermVectors( Node q, std::vector< std::vector< Node > >& tvecs ) {
1579   if( d_quantEngine ){
1580     d_quantEngine->getInstantiationTermVectors( q, tvecs );
1581   }else{
1582     Assert(false);
1583   }
1584 }
1585
1586 void TheoryEngine::getInstantiations( std::map< Node, std::vector< Node > >& insts ) {
1587   if( d_quantEngine ){
1588     d_quantEngine->getInstantiations( insts );
1589   }else{
1590     Assert(false);
1591   }
1592 }
1593
1594 void TheoryEngine::getInstantiationTermVectors( std::map< Node, std::vector< std::vector< Node > > >& insts ) {
1595   if( d_quantEngine ){
1596     d_quantEngine->getInstantiationTermVectors( insts );
1597   }else{
1598     Assert(false);
1599   }
1600 }
1601
1602 Node TheoryEngine::getInstantiatedConjunction( Node q ) {
1603   if( d_quantEngine ){
1604     return d_quantEngine->getInstantiatedConjunction( q );
1605   }else{
1606     Assert(false);
1607     return Node::null();
1608   }
1609 }
1610
1611
1612 static Node mkExplanation(const std::vector<NodeTheoryPair>& explanation) {
1613
1614   std::set<TNode> all;
1615   for (unsigned i = 0; i < explanation.size(); ++ i) {
1616     Assert(explanation[i].theory == THEORY_SAT_SOLVER);
1617     all.insert(explanation[i].node);
1618   }
1619
1620   if (all.size() == 0) {
1621     // Normalize to true
1622     return NodeManager::currentNM()->mkConst<bool>(true);
1623   }
1624
1625   if (all.size() == 1) {
1626     // All the same, or just one
1627     return explanation[0].node;
1628   }
1629
1630   NodeBuilder<> conjunction(kind::AND);
1631   std::set<TNode>::const_iterator it = all.begin();
1632   std::set<TNode>::const_iterator it_end = all.end();
1633   while (it != it_end) {
1634     conjunction << *it;
1635     ++ it;
1636   }
1637
1638   return conjunction;
1639 }
1640
1641 Node TheoryEngine::getExplanationAndRecipe(TNode node, LemmaProofRecipe* proofRecipe) {
1642   Debug("theory::explain") << "TheoryEngine::getExplanation(" << node << "): current propagation index = " << d_propagationMapTimestamp << endl;
1643
1644   bool polarity = node.getKind() != kind::NOT;
1645   TNode atom = polarity ? node : node[0];
1646
1647   // If we're not in shared mode, explanations are simple
1648   if (!d_logicInfo.isSharingEnabled()) {
1649     Debug("theory::explain") << "TheoryEngine::getExplanation: sharing is NOT enabled. "
1650                              << " Responsible theory is: "
1651                              << theoryOf(atom)->getId() << std::endl;
1652
1653     Node explanation = theoryOf(atom)->explain(node);
1654     Debug("theory::explain") << "TheoryEngine::getExplanation(" << node << ") => " << explanation << endl;
1655     PROOF({
1656         if(proofRecipe) {
1657           Node emptyNode;
1658           LemmaProofRecipe::ProofStep proofStep(theoryOf(atom)->getId(), emptyNode);
1659           proofStep.addAssertion(node);
1660           proofRecipe->addBaseAssertion(node);
1661
1662           if (explanation.getKind() == kind::AND) {
1663             // If the explanation is a conjunction, the recipe for the corresponding lemma is
1664             // the negation of its conjuncts.
1665             Node flat = flattenAnd(explanation);
1666             for (unsigned i = 0; i < flat.getNumChildren(); ++i) {
1667               if (flat[i].isConst() && flat[i].getConst<bool>()) {
1668                 ++ i;
1669                 continue;
1670               }
1671               if (flat[i].getKind() == kind::NOT &&
1672                   flat[i][0].isConst() && !flat[i][0].getConst<bool>()) {
1673                 ++ i;
1674                 continue;
1675               }
1676               Debug("theory::explain") << "TheoryEngine::getExplanationAndRecipe: adding recipe assertion: "
1677                                        << flat[i].negate() << std::endl;
1678               proofStep.addAssertion(flat[i].negate());
1679               proofRecipe->addBaseAssertion(flat[i].negate());
1680             }
1681           } else {
1682             // The recipe for proving it is by negating it. "True" is not an acceptable reason.
1683             if (!((explanation.isConst() && explanation.getConst<bool>()) ||
1684                   (explanation.getKind() == kind::NOT &&
1685                    explanation[0].isConst() && !explanation[0].getConst<bool>()))) {
1686               proofStep.addAssertion(explanation.negate());
1687               proofRecipe->addBaseAssertion(explanation.negate());
1688             }
1689           }
1690
1691           proofRecipe->addStep(proofStep);
1692         }
1693       });
1694
1695     return explanation;
1696   }
1697
1698   Debug("theory::explain") << "TheoryEngine::getExplanation: sharing IS enabled" << std::endl;
1699
1700   // Initial thing to explain
1701   NodeTheoryPair toExplain(node, THEORY_SAT_SOLVER, d_propagationMapTimestamp);
1702   Assert(d_propagationMap.find(toExplain) != d_propagationMap.end());
1703
1704   NodeTheoryPair nodeExplainerPair = d_propagationMap[toExplain];
1705   Debug("theory::explain") << "TheoryEngine::getExplanation: explainer for node "
1706                            << nodeExplainerPair.node
1707                            << " is theory: " << nodeExplainerPair.theory << std::endl;
1708   TheoryId explainer = nodeExplainerPair.theory;
1709
1710   // Create the workplace for explanations
1711   std::vector<NodeTheoryPair> explanationVector;
1712   explanationVector.push_back(d_propagationMap[toExplain]);
1713   // Process the explanation
1714   if (proofRecipe) {
1715     Node emptyNode;
1716     LemmaProofRecipe::ProofStep proofStep(explainer, emptyNode);
1717     proofStep.addAssertion(node);
1718     proofRecipe->addStep(proofStep);
1719     proofRecipe->addBaseAssertion(node);
1720   }
1721
1722   getExplanation(explanationVector, proofRecipe);
1723   Node explanation = mkExplanation(explanationVector);
1724
1725   Debug("theory::explain") << "TheoryEngine::getExplanation(" << node << ") => " << explanation << endl;
1726
1727   return explanation;
1728 }
1729
1730 Node TheoryEngine::getExplanation(TNode node) {
1731   LemmaProofRecipe *dontCareRecipe = NULL;
1732   return getExplanationAndRecipe(node, dontCareRecipe);
1733 }
1734
1735 struct AtomsCollect {
1736
1737   std::vector<TNode> d_atoms;
1738   std::unordered_set<TNode, TNodeHashFunction> d_visited;
1739
1740 public:
1741
1742   typedef void return_type;
1743
1744   bool alreadyVisited(TNode current, TNode parent) {
1745     // Check if already visited
1746     if (d_visited.find(current) != d_visited.end()) return true;
1747     // Don't visit non-boolean
1748     if (!current.getType().isBoolean()) return true;
1749     // New node
1750     return false;
1751   }
1752
1753   void visit(TNode current, TNode parent) {
1754     if (Theory::theoryOf(current) != theory::THEORY_BOOL) {
1755       d_atoms.push_back(current);
1756     }
1757     d_visited.insert(current);
1758   }
1759
1760   void start(TNode node) {}
1761   void done(TNode node) {}
1762
1763   std::vector<TNode> getAtoms() const {
1764     return d_atoms;
1765   }
1766 };
1767
1768 void TheoryEngine::ensureLemmaAtoms(const std::vector<TNode>& atoms, theory::TheoryId atomsTo) {
1769   for (unsigned i = 0; i < atoms.size(); ++ i) {
1770
1771     // Non-equality atoms are either owned by theory or they don't make sense
1772     if (atoms[i].getKind() != kind::EQUAL) {
1773       continue;
1774     }
1775
1776     // The equality
1777     Node eq = atoms[i];
1778     // Simple normalization to not repeat stuff
1779     if (eq[0] > eq[1]) {
1780       eq = eq[1].eqNode(eq[0]);
1781     }
1782
1783     // Rewrite the equality
1784     Node eqNormalized = Rewriter::rewrite(atoms[i]);
1785
1786     Debug("theory::atoms") << "TheoryEngine::ensureLemmaAtoms(): " << eq << " with nf " << eqNormalized << endl;
1787
1788     // If the equality is a boolean constant, we send immediately
1789     if (eqNormalized.isConst()) {
1790       if (eqNormalized.getConst<bool>()) {
1791         assertToTheory(eq, eqNormalized, /** to */ atomsTo, /** Sat solver */ theory::THEORY_SAT_SOLVER);
1792       } else {
1793         assertToTheory(eq.notNode(), eqNormalized.notNode(), /** to */ atomsTo, /** Sat solver */ theory::THEORY_SAT_SOLVER);
1794       }
1795       continue;
1796     }else if( eqNormalized.getKind() != kind::EQUAL){
1797       Assert(eqNormalized.getKind() == kind::BOOLEAN_TERM_VARIABLE
1798              || (eqNormalized.getKind() == kind::NOT
1799                  && eqNormalized[0].getKind() == kind::BOOLEAN_TERM_VARIABLE));
1800       // this happens for Boolean term equalities V = true that are rewritten to V, we should skip
1801       //  TODO : revisit this
1802       continue;
1803     }
1804
1805     // If the normalization did the just flips, keep the flip
1806     if (eqNormalized[0] == eq[1] && eqNormalized[1] == eq[0]) {
1807       eq = eqNormalized;
1808     }
1809
1810     // Check if the equality is already known by the sat solver
1811     if (d_propEngine->isSatLiteral(eqNormalized)) {
1812       bool value;
1813       if (d_propEngine->hasValue(eqNormalized, value)) {
1814         if (value) {
1815           assertToTheory(eq, eqNormalized, atomsTo, theory::THEORY_SAT_SOLVER);
1816           continue;
1817         } else {
1818           assertToTheory(eq.notNode(), eqNormalized.notNode(), atomsTo, theory::THEORY_SAT_SOLVER);
1819           continue;
1820         }
1821       }
1822     }
1823
1824     // If the theory is asking about a different form, or the form is ok but if will go to a different theory
1825     // then we must figure it out
1826     if (eqNormalized != eq || Theory::theoryOf(eq) != atomsTo) {
1827       // If you get eqNormalized, send atoms[i] to atomsTo
1828       d_atomRequests.add(eqNormalized, eq, atomsTo);
1829     }
1830   }
1831 }
1832
1833 theory::LemmaStatus TheoryEngine::lemma(TNode node,
1834                                         ProofRule rule,
1835                                         bool negated,
1836                                         bool removable,
1837                                         bool preprocess,
1838                                         theory::TheoryId atomsTo) {
1839   // For resource-limiting (also does a time check).
1840   // spendResource();
1841
1842   // Do we need to check atoms
1843   if (atomsTo != theory::THEORY_LAST) {
1844     Debug("theory::atoms") << "TheoryEngine::lemma(" << node << ", " << atomsTo << ")" << endl;
1845     AtomsCollect collectAtoms;
1846     NodeVisitor<AtomsCollect>::run(collectAtoms, node);
1847     ensureLemmaAtoms(collectAtoms.getAtoms(), atomsTo);
1848   }
1849
1850   if(Dump.isOn("t-lemmas")) {
1851     Node n = node;
1852     if (negated) {
1853       n = node.negate();
1854     }
1855     Dump("t-lemmas") << CommentCommand("theory lemma: expect valid")
1856                      << QueryCommand(n.toExpr());
1857   }
1858
1859   // Share with other portfolio threads
1860   if(d_channels->getLemmaOutputChannel() != NULL) {
1861     d_channels->getLemmaOutputChannel()->notifyNewLemma(node.toExpr());
1862   }
1863
1864   AssertionPipeline additionalLemmas;
1865
1866   // Run theory preprocessing, maybe
1867   Node ppNode = preprocess ? this->preprocess(node) : Node(node);
1868
1869   // Remove the ITEs
1870   Debug("ite") << "Remove ITE from " << ppNode << std::endl;
1871   additionalLemmas.push_back(ppNode);
1872   additionalLemmas.updateRealAssertionsEnd();
1873   d_tform_remover.run(additionalLemmas.ref(),
1874                       additionalLemmas.getIteSkolemMap());
1875   Debug("ite") << "..done " << additionalLemmas[0] << std::endl;
1876   additionalLemmas.replace(0, theory::Rewriter::rewrite(additionalLemmas[0]));
1877
1878   if(Debug.isOn("lemma-ites")) {
1879     Debug("lemma-ites") << "removed ITEs from lemma: " << ppNode << endl;
1880     Debug("lemma-ites") << " + now have the following "
1881                         << additionalLemmas.size() << " lemma(s):" << endl;
1882     for(std::vector<Node>::const_iterator i = additionalLemmas.begin();
1883         i != additionalLemmas.end();
1884         ++i) {
1885       Debug("lemma-ites") << " + " << *i << endl;
1886     }
1887     Debug("lemma-ites") << endl;
1888   }
1889
1890   // assert to prop engine
1891   d_propEngine->assertLemma(additionalLemmas[0], negated, removable, rule, node);
1892   for (unsigned i = 1; i < additionalLemmas.size(); ++ i) {
1893     additionalLemmas.replace(i, theory::Rewriter::rewrite(additionalLemmas[i]));
1894     d_propEngine->assertLemma(additionalLemmas[i], false, removable, rule, node);
1895   }
1896
1897   // WARNING: Below this point don't assume additionalLemmas[0] to be not negated.
1898   if(negated) {
1899     additionalLemmas.replace(0, additionalLemmas[0].notNode());
1900     negated = false;
1901   }
1902
1903   // assert to decision engine
1904   if(!removable) {
1905     d_decisionEngine->addAssertions(additionalLemmas);
1906   }
1907
1908   // Mark that we added some lemmas
1909   d_lemmasAdded = true;
1910
1911   // Lemma analysis isn't online yet; this lemma may only live for this
1912   // user level.
1913   return theory::LemmaStatus(additionalLemmas[0], d_userContext->getLevel());
1914 }
1915
1916 void TheoryEngine::conflict(TNode conflict, TheoryId theoryId) {
1917
1918   Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict << ", " << theoryId << ")" << endl;
1919
1920   // Mark that we are in conflict
1921   d_inConflict = true;
1922
1923   if(Dump.isOn("t-conflicts")) {
1924     Dump("t-conflicts") << CommentCommand("theory conflict: expect unsat")
1925                         << CheckSatCommand(conflict.toExpr());
1926   }
1927
1928   LemmaProofRecipe* proofRecipe = NULL;
1929   PROOF({
1930       proofRecipe = new LemmaProofRecipe;
1931       Node emptyNode;
1932       LemmaProofRecipe::ProofStep proofStep(theoryId, emptyNode);
1933
1934       if (conflict.getKind() == kind::AND) {
1935         for (unsigned i = 0; i < conflict.getNumChildren(); ++i) {
1936           proofStep.addAssertion(conflict[i].negate());
1937         }
1938       } else {
1939         proofStep.addAssertion(conflict.negate());
1940       }
1941
1942       proofRecipe->addStep(proofStep);
1943     });
1944
1945   // In the multiple-theories case, we need to reconstruct the conflict
1946   if (d_logicInfo.isSharingEnabled()) {
1947     // Create the workplace for explanations
1948     std::vector<NodeTheoryPair> explanationVector;
1949     explanationVector.push_back(NodeTheoryPair(conflict, theoryId, d_propagationMapTimestamp));
1950
1951     // Process the explanation
1952     getExplanation(explanationVector, proofRecipe);
1953     PROOF(ProofManager::getCnfProof()->setProofRecipe(proofRecipe));
1954     Node fullConflict = mkExplanation(explanationVector);
1955     Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict << ", " << theoryId << "): full = " << fullConflict << endl;
1956     Assert(properConflict(fullConflict));
1957     lemma(fullConflict, RULE_CONFLICT, true, true, false, THEORY_LAST);
1958
1959   } else {
1960     // When only one theory, the conflict should need no processing
1961     Assert(properConflict(conflict));
1962     PROOF({
1963         if (conflict.getKind() == kind::AND) {
1964           // If the conflict is a conjunction, the corresponding lemma is derived by negating
1965           // its conjuncts.
1966           for (unsigned i = 0; i < conflict.getNumChildren(); ++i) {
1967             if (conflict[i].isConst() && conflict[i].getConst<bool>()) {
1968               ++ i;
1969               continue;
1970             }
1971             if (conflict[i].getKind() == kind::NOT &&
1972                 conflict[i][0].isConst() && !conflict[i][0].getConst<bool>()) {
1973               ++ i;
1974               continue;
1975             }
1976             proofRecipe->getStep(0)->addAssertion(conflict[i].negate());
1977             proofRecipe->addBaseAssertion(conflict[i].negate());
1978           }
1979         } else {
1980           proofRecipe->getStep(0)->addAssertion(conflict.negate());
1981           proofRecipe->addBaseAssertion(conflict.negate());
1982         }
1983
1984         ProofManager::getCnfProof()->setProofRecipe(proofRecipe);
1985       });
1986
1987     lemma(conflict, RULE_CONFLICT, true, true, false, THEORY_LAST);
1988   }
1989
1990   PROOF({
1991       delete proofRecipe;
1992       proofRecipe = NULL;
1993     });
1994 }
1995
1996 void TheoryEngine::staticInitializeBVOptions(
1997     const std::vector<Node>& assertions)
1998 {
1999   bool useSlicer = true;
2000   if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_ON)
2001   {
2002     if (!d_logicInfo.isPure(theory::THEORY_BV) || d_logicInfo.isQuantified())
2003       throw ModalException(
2004           "Slicer currently only supports pure QF_BV formulas. Use "
2005           "--bv-eq-slicer=off");
2006     if (options::incrementalSolving())
2007       throw ModalException(
2008           "Slicer does not currently support incremental mode. Use "
2009           "--bv-eq-slicer=off");
2010     if (options::produceModels())
2011       throw ModalException(
2012           "Slicer does not currently support model generation. Use "
2013           "--bv-eq-slicer=off");
2014   }
2015   else if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_OFF)
2016   {
2017     return;
2018   }
2019   else if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_AUTO)
2020   {
2021     if ((!d_logicInfo.isPure(theory::THEORY_BV) || d_logicInfo.isQuantified())
2022         || options::incrementalSolving()
2023         || options::produceModels())
2024       return;
2025
2026     bv::utils::TNodeBoolMap cache;
2027     for (unsigned i = 0; i < assertions.size(); ++i)
2028     {
2029       useSlicer = useSlicer && bv::utils::isCoreTerm(assertions[i], cache);
2030     }
2031   }
2032
2033   if (useSlicer)
2034   {
2035     bv::TheoryBV* bv_theory = (bv::TheoryBV*)d_theoryTable[THEORY_BV];
2036     bv_theory->enableCoreTheorySlicer();
2037   }
2038 }
2039
2040 void TheoryEngine::getExplanation(std::vector<NodeTheoryPair>& explanationVector, LemmaProofRecipe* proofRecipe) {
2041   Assert(explanationVector.size() > 0);
2042
2043   unsigned i = 0; // Index of the current literal we are processing
2044   unsigned j = 0; // Index of the last literal we are keeping
2045
2046   std::unique_ptr<std::set<Node>> inputAssertions = nullptr;
2047   PROOF({
2048     if (proofRecipe)
2049     {
2050       inputAssertions.reset(
2051           new std::set<Node>(proofRecipe->getStep(0)->getAssertions()));
2052     }
2053   });
2054
2055   while (i < explanationVector.size()) {
2056     // Get the current literal to explain
2057     NodeTheoryPair toExplain = explanationVector[i];
2058
2059     Debug("theory::explain") << "[i=" << i << "] TheoryEngine::explain(): processing [" << toExplain.timestamp << "] " << toExplain.node << " sent from " << toExplain.theory << endl;
2060
2061
2062     // If a true constant or a negation of a false constant we can ignore it
2063     if (toExplain.node.isConst() && toExplain.node.getConst<bool>()) {
2064       ++ i;
2065       continue;
2066     }
2067     if (toExplain.node.getKind() == kind::NOT && toExplain.node[0].isConst() && !toExplain.node[0].getConst<bool>()) {
2068       ++ i;
2069       continue;
2070     }
2071
2072     // If from the SAT solver, keep it
2073     if (toExplain.theory == THEORY_SAT_SOLVER) {
2074       Debug("theory::explain") << "\tLiteral came from THEORY_SAT_SOLVER. Kepping it." << endl;
2075       explanationVector[j++] = explanationVector[i++];
2076       continue;
2077     }
2078
2079     // If an and, expand it
2080     if (toExplain.node.getKind() == kind::AND) {
2081       Debug("theory::explain") << "TheoryEngine::explain(): expanding " << toExplain.node << " got from " << toExplain.theory << endl;
2082       for (unsigned k = 0; k < toExplain.node.getNumChildren(); ++ k) {
2083         NodeTheoryPair newExplain(toExplain.node[k], toExplain.theory, toExplain.timestamp);
2084         explanationVector.push_back(newExplain);
2085       }
2086       ++ i;
2087       continue;
2088     }
2089
2090     // See if it was sent to the theory by another theory
2091     PropagationMap::const_iterator find = d_propagationMap.find(toExplain);
2092     if (find != d_propagationMap.end()) {
2093       Debug("theory::explain")
2094           << "\tTerm was propagated by another theory (theory = "
2095           << getTheoryString((*find).second.theory) << ")" << std::endl;
2096       // There is some propagation, check if its a timely one
2097       if ((*find).second.timestamp < toExplain.timestamp) {
2098         Debug("theory::explain") << "\tRelevant timetsamp, pushing "
2099                                  << (*find).second.node << "to index = " << explanationVector.size() << std::endl;
2100         explanationVector.push_back((*find).second);
2101         ++i;
2102
2103         PROOF({
2104             if (toExplain.node != (*find).second.node) {
2105               Debug("pf::explain") << "TheoryEngine::getExplanation: Rewrite alert! toAssert = " << toExplain.node
2106                                    << ", toExplain = " << (*find).second.node << std::endl;
2107
2108               if (proofRecipe) {
2109                 proofRecipe->addRewriteRule(toExplain.node, (*find).second.node);
2110               }
2111             }
2112           })
2113
2114         continue;
2115       }
2116     }
2117
2118     // It was produced by the theory, so ask for an explanation
2119     Node explanation;
2120     if (toExplain.theory == THEORY_BUILTIN) {
2121       explanation = d_sharedTerms.explain(toExplain.node);
2122       Debug("theory::explain") << "\tTerm was propagated by THEORY_BUILTIN. Explanation: " << explanation << std::endl;
2123     } else {
2124       explanation = theoryOf(toExplain.theory)->explain(toExplain.node);
2125       Debug("theory::explain") << "\tTerm was propagated by owner theory: "
2126                                << theoryOf(toExplain.theory)->getId()
2127                                << ". Explanation: " << explanation << std::endl;
2128     }
2129
2130     Debug("theory::explain") << "TheoryEngine::explain(): got explanation " << explanation << " got from " << toExplain.theory << endl;
2131     Assert(explanation != toExplain.node)
2132         << "wasn't sent to you, so why are you explaining it trivially";
2133     // Mark the explanation
2134     NodeTheoryPair newExplain(explanation, toExplain.theory, toExplain.timestamp);
2135     explanationVector.push_back(newExplain);
2136
2137     ++ i;
2138
2139     PROOF({
2140       if (proofRecipe && inputAssertions)
2141       {
2142         // If we're expanding the target node of the explanation (this is the
2143         // first expansion...), we don't want to add it as a separate proof
2144         // step. It is already part of the assertions.
2145         if (!ContainsKey(*inputAssertions, toExplain.node))
2146         {
2147           LemmaProofRecipe::ProofStep proofStep(toExplain.theory,
2148                                                 toExplain.node);
2149           if (explanation.getKind() == kind::AND)
2150           {
2151             Node flat = flattenAnd(explanation);
2152             for (unsigned k = 0; k < flat.getNumChildren(); ++k)
2153             {
2154               // If a true constant or a negation of a false constant we can
2155               // ignore it
2156               if (!((flat[k].isConst() && flat[k].getConst<bool>())
2157                     || (flat[k].getKind() == kind::NOT && flat[k][0].isConst()
2158                         && !flat[k][0].getConst<bool>())))
2159               {
2160                 proofStep.addAssertion(flat[k].negate());
2161               }
2162             }
2163           }
2164           else
2165           {
2166             if (!((explanation.isConst() && explanation.getConst<bool>())
2167                   || (explanation.getKind() == kind::NOT
2168                       && explanation[0].isConst()
2169                       && !explanation[0].getConst<bool>())))
2170             {
2171               proofStep.addAssertion(explanation.negate());
2172             }
2173           }
2174           proofRecipe->addStep(proofStep);
2175         }
2176       }
2177     });
2178   }
2179
2180   // Keep only the relevant literals
2181   explanationVector.resize(j);
2182
2183   PROOF({
2184       if (proofRecipe) {
2185         // The remaining literals are the base of the proof
2186         for (unsigned k = 0; k < explanationVector.size(); ++k) {
2187           proofRecipe->addBaseAssertion(explanationVector[k].node.negate());
2188         }
2189       }
2190     });
2191 }
2192
2193 void TheoryEngine::setUserAttribute(const std::string& attr,
2194                                     Node n,
2195                                     const std::vector<Node>& node_values,
2196                                     const std::string& str_value)
2197 {
2198   Trace("te-attr") << "set user attribute " << attr << " " << n << endl;
2199   if( d_attr_handle.find( attr )!=d_attr_handle.end() ){
2200     for( size_t i=0; i<d_attr_handle[attr].size(); i++ ){
2201       d_attr_handle[attr][i]->setUserAttribute(attr, n, node_values, str_value);
2202     }
2203   } else {
2204     //unhandled exception?
2205   }
2206 }
2207
2208 void TheoryEngine::handleUserAttribute(const char* attr, Theory* t) {
2209   Trace("te-attr") << "Handle user attribute " << attr << " " << t << endl;
2210   std::string str( attr );
2211   d_attr_handle[ str ].push_back( t );
2212 }
2213
2214 void TheoryEngine::checkTheoryAssertionsWithModel(bool hardFailure) {
2215   for(TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
2216     Theory* theory = d_theoryTable[theoryId];
2217     if(theory && d_logicInfo.isTheoryEnabled(theoryId)) {
2218       for(context::CDList<Assertion>::const_iterator it = theory->facts_begin(),
2219             it_end = theory->facts_end();
2220           it != it_end;
2221           ++it) {
2222         Node assertion = (*it).assertion;
2223         Node val = getModel()->getValue(assertion);
2224         if (val != d_true)
2225         {
2226           if (hardFailure)
2227           {
2228             InternalError()
2229                 << theoryId
2230                 << " has an asserted fact that the model doesn't satisfy."
2231                 << endl
2232                 << "The fact: " << assertion << endl
2233                 << "Model value: " << val << endl;
2234           }
2235         }
2236       }
2237     }
2238   }
2239 }
2240
2241 std::pair<bool, Node> TheoryEngine::entailmentCheck(theory::TheoryOfMode mode, TNode lit, const EntailmentCheckParameters* params, EntailmentCheckSideEffects* seffects) {
2242   TNode atom = (lit.getKind() == kind::NOT) ? lit[0] : lit;
2243   if( atom.getKind()==kind::AND || atom.getKind()==kind::OR || atom.getKind()==kind::IMPLIES ){
2244     //Boolean connective, recurse
2245     std::vector< Node > children;
2246     bool pol = (lit.getKind()!=kind::NOT);
2247     bool is_conjunction = pol==(lit.getKind()==kind::AND);
2248     for( unsigned i=0; i<atom.getNumChildren(); i++ ){
2249       Node ch = atom[i];
2250       if( pol==( lit.getKind()==kind::IMPLIES && i==0 ) ){
2251         ch = atom[i].negate();
2252       }
2253       std::pair<bool, Node> chres = entailmentCheck( mode, ch, params, seffects );
2254       if( chres.first ){
2255         if( !is_conjunction ){
2256           return chres;
2257         }else{
2258           children.push_back( chres.second );
2259         }
2260       }else if( !chres.first && is_conjunction ){
2261         return std::pair<bool, Node>(false, Node::null());
2262       }
2263     }
2264     if( is_conjunction ){
2265       return std::pair<bool, Node>(true, NodeManager::currentNM()->mkNode(kind::AND, children));
2266     }else{
2267       return std::pair<bool, Node>(false, Node::null());
2268     }
2269   }else if( atom.getKind()==kind::ITE || ( atom.getKind()==kind::EQUAL && atom[0].getType().isBoolean() ) ){
2270     bool pol = (lit.getKind()!=kind::NOT);
2271     for( unsigned r=0; r<2; r++ ){
2272       Node ch = atom[0];
2273       if( r==1 ){
2274         ch = ch.negate();
2275       }
2276       std::pair<bool, Node> chres = entailmentCheck( mode, ch, params, seffects );
2277       if( chres.first ){
2278         Node ch2 = atom[ atom.getKind()==kind::ITE ? r+1 : 1 ];
2279         if( pol==( atom.getKind()==kind::ITE ? true : r==1 ) ){
2280           ch2 = ch2.negate();
2281         }
2282         std::pair<bool, Node> chres2 = entailmentCheck( mode, ch2, params, seffects );
2283         if( chres2.first ){
2284           return std::pair<bool, Node>(true, NodeManager::currentNM()->mkNode(kind::AND, chres.second, chres2.second));
2285         }else{
2286           break;
2287         }
2288       }
2289     }
2290     return std::pair<bool, Node>(false, Node::null());
2291   }else{
2292     //it is a theory atom
2293     theory::TheoryId tid = theory::Theory::theoryOf(mode, atom);
2294     theory::Theory* th = theoryOf(tid);
2295
2296     Assert(th != NULL);
2297     Assert(params == NULL || tid == params->getTheoryId());
2298     Assert(seffects == NULL || tid == seffects->getTheoryId());
2299     Trace("theory-engine-entc") << "Entailment check : " << lit << std::endl;
2300
2301     std::pair<bool, Node> chres = th->entailmentCheck(lit, params, seffects);
2302     return chres;
2303   }
2304 }
2305
2306 void TheoryEngine::spendResource(unsigned amount)
2307 {
2308   d_resourceManager->spendResource(amount);
2309 }
2310
2311 void TheoryEngine::enableTheoryAlternative(const std::string& name){
2312   Debug("TheoryEngine::enableTheoryAlternative")
2313       << "TheoryEngine::enableTheoryAlternative(" << name << ")" << std::endl;
2314
2315   d_theoryAlternatives.insert(name);
2316 }
2317
2318 bool TheoryEngine::useTheoryAlternative(const std::string& name) {
2319   return d_theoryAlternatives.find(name) != d_theoryAlternatives.end();
2320 }
2321
2322
2323 TheoryEngine::Statistics::Statistics(theory::TheoryId theory):
2324     conflicts(getStatsPrefix(theory) + "::conflicts", 0),
2325     propagations(getStatsPrefix(theory) + "::propagations", 0),
2326     lemmas(getStatsPrefix(theory) + "::lemmas", 0),
2327     requirePhase(getStatsPrefix(theory) + "::requirePhase", 0),
2328     restartDemands(getStatsPrefix(theory) + "::restartDemands", 0)
2329 {
2330   smtStatisticsRegistry()->registerStat(&conflicts);
2331   smtStatisticsRegistry()->registerStat(&propagations);
2332   smtStatisticsRegistry()->registerStat(&lemmas);
2333   smtStatisticsRegistry()->registerStat(&requirePhase);
2334   smtStatisticsRegistry()->registerStat(&restartDemands);
2335 }
2336
2337 TheoryEngine::Statistics::~Statistics() {
2338   smtStatisticsRegistry()->unregisterStat(&conflicts);
2339   smtStatisticsRegistry()->unregisterStat(&propagations);
2340   smtStatisticsRegistry()->unregisterStat(&lemmas);
2341   smtStatisticsRegistry()->unregisterStat(&requirePhase);
2342   smtStatisticsRegistry()->unregisterStat(&restartDemands);
2343 }
2344
2345 }/* CVC4 namespace */