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