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