src/theory/theory_engine.cpp

   1 /*********************                                                        */
   2 /*! \file theory_engine.cpp
   3  ** \verbatim
   4  ** Original author: Morgan Deters
   5  ** Major contributors: Dejan Jovanovic
   6  ** Minor contributors (to current version): Christopher L. Conway, Tianyi Liang, Kshitij Bansal, Clark Barrett, Liana Hadarean, Andrew Reynolds, Tim King
   7  ** This file is part of the CVC4 project.
   8  ** Copyright (c) 2009-2014  New York University and The University of Iowa
   9  ** See the file COPYING in the top-level source directory for licensing
  10  ** information.\endverbatim
  11  **
  12  ** \brief The theory engine
  13  **
  14  ** The theory engine.
  15  **/
  16
  17 #include <vector>
  18 #include <list>
  19
  20 #include "theory/arith/arith_ite_utils.h"
  21
  22 #include "decision/decision_engine.h"
  23
  24 #include "expr/attribute.h"
  25 #include "expr/node.h"
  26 #include "expr/node_builder.h"
  27 #include "options/options.h"
  28 #include "util/lemma_output_channel.h"
  29 #include "util/resource_manager.h"
  30
  31 #include "theory/theory.h"
  32 #include "theory/theory_engine.h"
  33 #include "theory/rewriter.h"
  34 #include "theory/theory_traits.h"
  35
  36 #include "smt/logic_exception.h"
  37
  38 #include "proof/proof_manager.h"
  39
  40 #include "util/node_visitor.h"
  41 #include "util/ite_removal.h"
  42
  43 //#include "theory/ite_simplifier.h"
  44 //#include "theory/ite_compressor.h"
  45 #include "theory/ite_utilities.h"
  46 #include "theory/unconstrained_simplifier.h"
  47
  48 #include "theory/theory_model.h"
  49
  50 #include "theory/quantifiers_engine.h"
  51 #include "theory/quantifiers/theory_quantifiers.h"
  52 #include "theory/quantifiers/options.h"
  53 #include "theory/quantifiers/model_engine.h"
  54 #include "theory/quantifiers/first_order_model.h"
  55
  56 #include "theory/uf/equality_engine.h"
  57 //#include "theory/rewriterules/efficient_e_matching.h"
  58 #include "theory/bv/theory_bv_utils.h"
  59 #include "theory/bv/options.h"
  60
  61 #include "proof/proof_manager.h"
  62
  63 using namespace std;
  64
  65 using namespace CVC4;
  66 using namespace CVC4::theory;
  67
  68 void TheoryEngine::finishInit() {
  69   PROOF (ProofManager::initTheoryProof(); );
  70
  71   // initialize the quantifiers engine
  72   d_quantEngine = new QuantifiersEngine(d_context, d_userContext, this);
  73
  74   if (d_logicInfo.isQuantified()) {
  75     d_quantEngine->finishInit();
  76     Assert(d_masterEqualityEngine == 0);
  77     d_masterEqualityEngine = new eq::EqualityEngine(d_masterEENotify,getSatContext(), "theory::master");
  78
  79     for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
  80       if (d_theoryTable[theoryId]) {
  81         d_theoryTable[theoryId]->setQuantifiersEngine(d_quantEngine);
  82         d_theoryTable[theoryId]->setMasterEqualityEngine(d_masterEqualityEngine);
  83       }
  84     }
  85   }
  86
  87   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
  88     if (d_theoryTable[theoryId]) {
  89       d_theoryTable[theoryId]->finishInit();
  90     }
  91   }
  92 }
  93
  94 void TheoryEngine::eqNotifyNewClass(TNode t){
  95   d_quantEngine->addTermToDatabase( t );
  96 }
  97
  98 void TheoryEngine::eqNotifyPreMerge(TNode t1, TNode t2){
  99
 100 }
 101
 102 void TheoryEngine::eqNotifyPostMerge(TNode t1, TNode t2){
 103
 104 }
 105
 106 void TheoryEngine::eqNotifyDisequal(TNode t1, TNode t2, TNode reason){
 107   if( d_logicInfo.isQuantified() ){
 108     if( options::quantConflictFind() ){
 109       d_quantEngine->getConflictFind()->assertDisequal( t1, t2 );
 110     }
 111   }
 112 }
 113
 114
 115 TheoryEngine::TheoryEngine(context::Context* context,
 116                            context::UserContext* userContext,
 117                            RemoveITE& iteRemover,
 118                            const LogicInfo& logicInfo)
 119 : d_propEngine(NULL),
 120   d_decisionEngine(NULL),
 121   d_context(context),
 122   d_userContext(userContext),
 123   d_logicInfo(logicInfo),
 124   d_sharedTerms(this, context),
 125   d_masterEqualityEngine(NULL),
 126   d_masterEENotify(*this),
 127   d_quantEngine(NULL),
 128   d_curr_model(NULL),
 129   d_curr_model_builder(NULL),
 130   d_ppCache(),
 131   d_possiblePropagations(context),
 132   d_hasPropagated(context),
 133   d_inConflict(context, false),
 134   d_hasShutDown(false),
 135   d_incomplete(context, false),
 136   d_propagationMap(context),
 137   d_propagationMapTimestamp(context, 0),
 138   d_propagatedLiterals(context),
 139   d_propagatedLiteralsIndex(context, 0),
 140   d_atomRequests(context),
 141   d_iteRemover(iteRemover),
 142   d_combineTheoriesTime("TheoryEngine::combineTheoriesTime"),
 143   d_true(),
 144   d_false(),
 145   d_interrupted(false),
 146   d_resourceManager(NodeManager::currentResourceManager()),
 147   d_inPreregister(false),
 148   d_factsAsserted(context, false),
 149   d_preRegistrationVisitor(this, context),
 150   d_sharedTermsVisitor(d_sharedTerms),
 151   d_unconstrainedSimp(new UnconstrainedSimplifier(context, logicInfo)),
 152   d_bvToBoolPreprocessor(),
 153   d_arithSubstitutionsAdded("theory::arith::zzz::arith::substitutions", 0)
 154 {
 155   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
 156     d_theoryTable[theoryId] = NULL;
 157     d_theoryOut[theoryId] = NULL;
 158   }
 159
 160   // build model information if applicable
 161   d_curr_model = new theory::TheoryModel(userContext, "DefaultModel", true);
 162   d_curr_model_builder = new theory::TheoryEngineModelBuilder(this);
 163
 164   StatisticsRegistry::registerStat(&d_combineTheoriesTime);
 165   d_true = NodeManager::currentNM()->mkConst<bool>(true);
 166   d_false = NodeManager::currentNM()->mkConst<bool>(false);
 167
 168   d_iteUtilities = new ITEUtilities(d_iteRemover.getContainsVisitor());
 169
 170   StatisticsRegistry::registerStat(&d_arithSubstitutionsAdded);
 171 }
 172
 173 TheoryEngine::~TheoryEngine() {
 174   Assert(d_hasShutDown);
 175
 176   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId != theory::THEORY_LAST; ++ theoryId) {
 177     if(d_theoryTable[theoryId] != NULL) {
 178       delete d_theoryTable[theoryId];
 179       delete d_theoryOut[theoryId];
 180     }
 181   }
 182
 183   delete d_curr_model_builder;
 184   delete d_curr_model;
 185
 186   delete d_quantEngine;
 187
 188   delete d_masterEqualityEngine;
 189
 190   StatisticsRegistry::unregisterStat(&d_combineTheoriesTime);
 191
 192   delete d_unconstrainedSimp;
 193
 194   delete d_iteUtilities;
 195
 196   StatisticsRegistry::unregisterStat(&d_arithSubstitutionsAdded);
 197 }
 198
 199 void TheoryEngine::interrupt() throw(ModalException) {
 200   d_interrupted = true;
 201 }
 202
 203 void TheoryEngine::preRegister(TNode preprocessed) {
 204
 205   if(Dump.isOn("missed-t-propagations")) {
 206     d_possiblePropagations.push_back(preprocessed);
 207   }
 208   d_preregisterQueue.push(preprocessed);
 209
 210   if (!d_inPreregister) {
 211     // We're in pre-register
 212     d_inPreregister = true;
 213
 214     // Process the pre-registration queue
 215     while (!d_preregisterQueue.empty()) {
 216       // Get the next atom to pre-register
 217       preprocessed = d_preregisterQueue.front();
 218       d_preregisterQueue.pop();
 219
 220       if (d_logicInfo.isSharingEnabled() && preprocessed.getKind() == kind::EQUAL) {
 221         // When sharing is enabled, we propagate from the shared terms manager also
 222         d_sharedTerms.addEqualityToPropagate(preprocessed);
 223       }
 224
 225       // Pre-register the terms in the atom
 226       Theory::Set theories = NodeVisitor<PreRegisterVisitor>::run(d_preRegistrationVisitor, preprocessed);
 227       theories = Theory::setRemove(THEORY_BOOL, theories);
 228       // Remove the top theory, if any more that means multiple theories were involved
 229       bool multipleTheories = Theory::setRemove(Theory::theoryOf(preprocessed), theories);
 230       TheoryId i;
 231       // These checks don't work with finite model finding, because it
 232       // uses Rational constants to represent cardinality constraints,
 233       // even though arithmetic isn't actually involved.
 234       if(!options::finiteModelFind()) {
 235         while((i = Theory::setPop(theories)) != THEORY_LAST) {
 236           if(!d_logicInfo.isTheoryEnabled(i)) {
 237             LogicInfo newLogicInfo = d_logicInfo.getUnlockedCopy();
 238             newLogicInfo.enableTheory(i);
 239             newLogicInfo.lock();
 240             stringstream ss;
 241             ss << "The logic was specified as " << d_logicInfo.getLogicString()
 242                << ", which doesn't include " << i
 243                << ", but found a term in that theory." << endl
 244                << "You might want to extend your logic to "
 245                << newLogicInfo.getLogicString() << endl;
 246             throw LogicException(ss.str());
 247           }
 248         }
 249       }
 250       if (multipleTheories) {
 251         // Collect the shared terms if there are multiple theories
 252         NodeVisitor<SharedTermsVisitor>::run(d_sharedTermsVisitor, preprocessed);
 253       }
 254     }
 255
 256     // Leaving pre-register
 257     d_inPreregister = false;
 258   }
 259 }
 260
 261 void TheoryEngine::printAssertions(const char* tag) {
 262   if (Trace.isOn(tag)) {
 263
 264     for (TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
 265       Theory* theory = d_theoryTable[theoryId];
 266       if (theory && d_logicInfo.isTheoryEnabled(theoryId)) {
 267         Trace(tag) << "--------------------------------------------" << endl;
 268         Trace(tag) << "Assertions of " << theory->getId() << ": " << endl;
 269         context::CDList<Assertion>::const_iterator it = theory->facts_begin(), it_end = theory->facts_end();
 270         for (unsigned i = 0; it != it_end; ++ it, ++i) {
 271             if ((*it).isPreregistered) {
 272               Trace(tag) << "[" << i << "]: ";
 273             } else {
 274               Trace(tag) << "(" << i << "): ";
 275             }
 276             Trace(tag) << (*it).assertion << endl;
 277         }
 278
 279         if (d_logicInfo.isSharingEnabled()) {
 280           Trace(tag) << "Shared terms of " << theory->getId() << ": " << endl;
 281           context::CDList<TNode>::const_iterator it = theory->shared_terms_begin(), it_end = theory->shared_terms_end();
 282           for (unsigned i = 0; it != it_end; ++ it, ++i) {
 283               Trace(tag) << "[" << i << "]: " << (*it) << endl;
 284           }
 285         }
 286       }
 287     }
 288   }
 289 }
 290
 291 void TheoryEngine::dumpAssertions(const char* tag) {
 292   if (Dump.isOn(tag)) {
 293     Dump(tag) << CommentCommand("Starting completeness check");
 294     for (TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
 295       Theory* theory = d_theoryTable[theoryId];
 296       if (theory && d_logicInfo.isTheoryEnabled(theoryId)) {
 297         Dump(tag) << CommentCommand("Completeness check");
 298         Dump(tag) << PushCommand();
 299
 300         // Dump the shared terms
 301         if (d_logicInfo.isSharingEnabled()) {
 302           Dump(tag) << CommentCommand("Shared terms");
 303           context::CDList<TNode>::const_iterator it = theory->shared_terms_begin(), it_end = theory->shared_terms_end();
 304           for (unsigned i = 0; it != it_end; ++ it, ++i) {
 305               stringstream ss;
 306               ss << (*it);
 307               Dump(tag) << CommentCommand(ss.str());
 308           }
 309         }
 310
 311         // Dump the assertions
 312         Dump(tag) << CommentCommand("Assertions");
 313         context::CDList<Assertion>::const_iterator it = theory->facts_begin(), it_end = theory->facts_end();
 314         for (; it != it_end; ++ it) {
 315           // Get the assertion
 316           Node assertionNode = (*it).assertion;
 317           // Purify all the terms
 318
 319           if ((*it).isPreregistered) {
 320             Dump(tag) << CommentCommand("Preregistered");
 321           } else {
 322             Dump(tag) << CommentCommand("Shared assertion");
 323           }
 324           Dump(tag) << AssertCommand(assertionNode.toExpr());
 325         }
 326         Dump(tag) << CheckSatCommand();
 327
 328         Dump(tag) << PopCommand();
 329       }
 330     }
 331   }
 332 }
 333
 334 /**
 335  * Check all (currently-active) theories for conflicts.
 336  * @param effort the effort level to use
 337  */
 338 void TheoryEngine::check(Theory::Effort effort) {
 339   // spendResource();
 340
 341   // Reset the interrupt flag
 342   d_interrupted = false;
 343
 344 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 345 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 346 #endif
 347 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 348     if (theory::TheoryTraits<THEORY>::hasCheck && d_logicInfo.isTheoryEnabled(THEORY)) { \
 349        theoryOf(THEORY)->check(effort); \
 350        if (d_inConflict) { \
 351          break; \
 352        } \
 353     }
 354
 355   // Do the checking
 356   try {
 357
 358     // Mark the output channel unused (if this is FULL_EFFORT, and nothing
 359     // is done by the theories, no additional check will be needed)
 360     d_outputChannelUsed = false;
 361
 362     // Mark the lemmas flag (no lemmas added)
 363     d_lemmasAdded = false;
 364
 365     Debug("theory") << "TheoryEngine::check(" << effort << "): d_factsAsserted = " << (d_factsAsserted ? "true" : "false") << endl;
 366
 367     // If in full effort, we have a fake new assertion just to jumpstart the checking
 368     if (Theory::fullEffort(effort)) {
 369       d_factsAsserted = true;
 370     }
 371
 372     // Check until done
 373     while (d_factsAsserted && !d_inConflict && !d_lemmasAdded) {
 374
 375       Debug("theory") << "TheoryEngine::check(" << effort << "): running check" << endl;
 376
 377       Trace("theory::assertions") << endl;
 378       if (Trace.isOn("theory::assertions")) {
 379         printAssertions("theory::assertions");
 380       }
 381
 382       // Note that we've discharged all the facts
 383       d_factsAsserted = false;
 384
 385       // Do the checking
 386       CVC4_FOR_EACH_THEORY;
 387
 388       if(Dump.isOn("missed-t-conflicts")) {
 389         Dump("missed-t-conflicts")
 390             << CommentCommand("Completeness check for T-conflicts; expect sat")
 391             << CheckSatCommand();
 392       }
 393
 394       Debug("theory") << "TheoryEngine::check(" << effort << "): running propagation after the initial check" << endl;
 395
 396       // We are still satisfiable, propagate as much as possible
 397       propagate(effort);
 398
 399       // We do combination if all has been processed and we are in fullcheck
 400       if (Theory::fullEffort(effort) && d_logicInfo.isSharingEnabled() && !d_factsAsserted && !d_lemmasAdded && !d_inConflict) {
 401         // Do the combination
 402         Debug("theory") << "TheoryEngine::check(" << effort << "): running combination" << endl;
 403         combineTheories();
 404       }
 405     }
 406
 407     // Must consult quantifiers theory for last call to ensure sat, or otherwise add a lemma
 408     if( effort == Theory::EFFORT_FULL && ! d_inConflict && ! needCheck() ) {
 409       //d_theoryTable[THEORY_STRINGS]->check(Theory::EFFORT_LAST_CALL);
 410       if(d_logicInfo.isQuantified()) {
 411         // quantifiers engine must pass effort last call check
 412         d_quantEngine->check(Theory::EFFORT_LAST_CALL);
 413         // if we have given up, then possibly flip decision
 414         if(options::flipDecision()) {
 415           if(d_incomplete && !d_inConflict && !needCheck()) {
 416             ((theory::quantifiers::TheoryQuantifiers*) d_theoryTable[THEORY_QUANTIFIERS])->flipDecision();
 417           }
 418         }
 419         // if returning incomplete or SAT, we have ensured that the model in the quantifiers engine has been built
 420       } else if(options::produceModels()) {
 421         // must build model at this point
 422         d_curr_model_builder->buildModel(d_curr_model, true);
 423       }
 424           Trace("theory::assertions-model") << endl;
 425       if (Trace.isOn("theory::assertions-model")) {
 426         printAssertions("theory::assertions-model");
 427       }
 428     }
 429
 430     Debug("theory") << "TheoryEngine::check(" << effort << "): done, we are " << (d_inConflict ? "unsat" : "sat") << (d_lemmasAdded ? " with new lemmas" : " with no new lemmas") << endl;
 431
 432     if(!d_inConflict && Theory::fullEffort(effort) && d_masterEqualityEngine != NULL && !d_lemmasAdded) {
 433       AlwaysAssert(d_masterEqualityEngine->consistent());
 434     }
 435   } catch(const theory::Interrupted&) {
 436     Trace("theory") << "TheoryEngine::check() => interrupted" << endl;
 437   }
 438   // If fulleffort, check all theories
 439   if(Dump.isOn("theory::fullcheck") && Theory::fullEffort(effort)) {
 440     if (!d_inConflict && !needCheck()) {
 441       dumpAssertions("theory::fullcheck");
 442     }
 443   }
 444 }
 445
 446 void TheoryEngine::combineTheories() {
 447
 448   Trace("combineTheories") << "TheoryEngine::combineTheories()" << endl;
 449
 450   TimerStat::CodeTimer combineTheoriesTimer(d_combineTheoriesTime);
 451
 452   // Care graph we'll be building
 453   CareGraph careGraph;
 454
 455 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 456 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 457 #endif
 458 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 459   if (theory::TheoryTraits<THEORY>::isParametric && d_logicInfo.isTheoryEnabled(THEORY)) { \
 460     theoryOf(THEORY)->getCareGraph(careGraph); \
 461   }
 462
 463   // Call on each parametric theory to give us its care graph
 464   CVC4_FOR_EACH_THEORY;
 465
 466   Trace("combineTheories") << "TheoryEngine::combineTheories(): care graph size = " << careGraph.size() << endl;
 467
 468   // Now add splitters for the ones we are interested in
 469   CareGraph::const_iterator care_it = careGraph.begin();
 470   CareGraph::const_iterator care_it_end = careGraph.end();
 471
 472   for (; care_it != care_it_end; ++ care_it) {
 473     const CarePair& carePair = *care_it;
 474
 475     Debug("combineTheories") << "TheoryEngine::combineTheories(): checking " << carePair.a << " = " << carePair.b << " from " << carePair.theory << endl;
 476
 477     Assert(d_sharedTerms.isShared(carePair.a) || carePair.a.isConst());
 478     Assert(d_sharedTerms.isShared(carePair.b) || carePair.b.isConst());
 479
 480     // The equality in question (order for no repetition)
 481     Node equality = carePair.a.eqNode(carePair.b);
 482     // EqualityStatus es = getEqualityStatus(carePair.a, carePair.b);
 483     // Debug("combineTheories") << "TheoryEngine::combineTheories(): " <<
 484     //   (es == EQUALITY_TRUE_AND_PROPAGATED ? "EQUALITY_TRUE_AND_PROPAGATED" :
 485     //   es == EQUALITY_FALSE_AND_PROPAGATED ? "EQUALITY_FALSE_AND_PROPAGATED" :
 486     //   es == EQUALITY_TRUE ? "EQUALITY_TRUE" :
 487     //   es == EQUALITY_FALSE ? "EQUALITY_FALSE" :
 488     //   es == EQUALITY_TRUE_IN_MODEL ? "EQUALITY_TRUE_IN_MODEL" :
 489     //   es == EQUALITY_FALSE_IN_MODEL ? "EQUALITY_FALSE_IN_MODEL" :
 490     //   es == EQUALITY_UNKNOWN ? "EQUALITY_UNKNOWN" :
 491     //    "Unexpected case") << endl;
 492
 493     // We need to split on it
 494     Debug("combineTheories") << "TheoryEngine::combineTheories(): requesting a split " << endl;
 495     lemma(equality.orNode(equality.notNode()), false, false, false, carePair.theory);
 496     // This code is supposed to force preference to follow what the theory models already have
 497     // but it doesn't seem to make a big difference - need to explore more -Clark
 498     // if (true) {
 499     //   if (es == EQUALITY_TRUE || es == EQUALITY_TRUE_IN_MODEL) {
 500     Node e = ensureLiteral(equality);
 501     d_propEngine->requirePhase(e, true);
 502     //   }
 503     //   else if (es == EQUALITY_FALSE_IN_MODEL) {
 504     //     Node e = ensureLiteral(equality);
 505     //     d_propEngine->requirePhase(e, false);
 506     //   }
 507     // }
 508   }
 509 }
 510
 511 void TheoryEngine::propagate(Theory::Effort effort) {
 512   // Reset the interrupt flag
 513   d_interrupted = false;
 514
 515   // Definition of the statement that is to be run by every theory
 516 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 517 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 518 #endif
 519 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 520   if (theory::TheoryTraits<THEORY>::hasPropagate && d_logicInfo.isTheoryEnabled(THEORY)) { \
 521     theoryOf(THEORY)->propagate(effort); \
 522   }
 523
 524   // Reset the interrupt flag
 525   d_interrupted = false;
 526
 527   // Propagate for each theory using the statement above
 528   CVC4_FOR_EACH_THEORY;
 529
 530   if(Dump.isOn("missed-t-propagations")) {
 531     for(unsigned i = 0; i < d_possiblePropagations.size(); ++i) {
 532       Node atom = d_possiblePropagations[i];
 533       bool value;
 534       if(d_propEngine->hasValue(atom, value)) {
 535         continue;
 536       }
 537       // Doesn't have a value, check it (and the negation)
 538       if(d_hasPropagated.find(atom) == d_hasPropagated.end()) {
 539         Dump("missed-t-propagations")
 540           << CommentCommand("Completeness check for T-propagations; expect invalid")
 541           << EchoCommand(atom.toString())
 542           << QueryCommand(atom.toExpr())
 543           << EchoCommand(atom.notNode().toString())
 544           << QueryCommand(atom.notNode().toExpr());
 545       }
 546     }
 547   }
 548 }
 549
 550 Node TheoryEngine::getNextDecisionRequest() {
 551   // Definition of the statement that is to be run by every theory
 552 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 553 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 554 #endif
 555 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 556   if (theory::TheoryTraits<THEORY>::hasGetNextDecisionRequest && d_logicInfo.isTheoryEnabled(THEORY)) { \
 557     Node n = theoryOf(THEORY)->getNextDecisionRequest(); \
 558     if(! n.isNull()) { \
 559       return n; \
 560     } \
 561   }
 562
 563   // Request decision from each theory using the statement above
 564   CVC4_FOR_EACH_THEORY;
 565
 566   return TNode();
 567 }
 568
 569 bool TheoryEngine::properConflict(TNode conflict) const {
 570   bool value;
 571   if (conflict.getKind() == kind::AND) {
 572     for (unsigned i = 0; i < conflict.getNumChildren(); ++ i) {
 573       if (! getPropEngine()->hasValue(conflict[i], value)) {
 574         Debug("properConflict") << "Bad conflict is due to unassigned atom: "
 575                                 << conflict[i] << endl;
 576         return false;
 577       }
 578       if (! value) {
 579         Debug("properConflict") << "Bad conflict is due to false atom: "
 580                                 << conflict[i] << endl;
 581         return false;
 582       }
 583       if (conflict[i] != Rewriter::rewrite(conflict[i])) {
 584         Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
 585                                 << conflict[i] << " vs " << Rewriter::rewrite(conflict[i]) << endl;
 586         return false;
 587       }
 588     }
 589   } else {
 590     if (! getPropEngine()->hasValue(conflict, value)) {
 591       Debug("properConflict") << "Bad conflict is due to unassigned atom: "
 592                               << conflict << endl;
 593       return false;
 594     }
 595     if(! value) {
 596       Debug("properConflict") << "Bad conflict is due to false atom: "
 597                               << conflict << endl;
 598       return false;
 599     }
 600     if (conflict != Rewriter::rewrite(conflict)) {
 601       Debug("properConflict") << "Bad conflict is due to atom not in normal form: "
 602                               << conflict << " vs " << Rewriter::rewrite(conflict) << endl;
 603       return false;
 604     }
 605   }
 606   return true;
 607 }
 608
 609 bool TheoryEngine::properPropagation(TNode lit) const {
 610   if(!getPropEngine()->isSatLiteral(lit)) {
 611     return false;
 612   }
 613   bool b;
 614   return !getPropEngine()->hasValue(lit, b);
 615 }
 616
 617 bool TheoryEngine::properExplanation(TNode node, TNode expl) const {
 618   // Explanation must be either a conjunction of true literals that have true SAT values already
 619   // or a singled literal that has a true SAT value already.
 620   if (expl.getKind() == kind::AND) {
 621     for (unsigned i = 0; i < expl.getNumChildren(); ++ i) {
 622       bool value;
 623       if (!d_propEngine->hasValue(expl[i], value) || !value) {
 624         return false;
 625       }
 626     }
 627   } else {
 628     bool value;
 629     return d_propEngine->hasValue(expl, value) && value;
 630   }
 631   return true;
 632 }
 633
 634 void TheoryEngine::collectModelInfo( theory::TheoryModel* m, bool fullModel ){
 635   //have shared term engine collectModelInfo
 636   //  d_sharedTerms.collectModelInfo( m, fullModel );
 637   // Consult each active theory to get all relevant information
 638   // concerning the model.
 639   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST; ++theoryId) {
 640     if(d_logicInfo.isTheoryEnabled(theoryId)) {
 641       Trace("model-builder") << "  CollectModelInfo on theory: " << theoryId << endl;
 642       d_theoryTable[theoryId]->collectModelInfo( m, fullModel );
 643     }
 644   }
 645   // Get the Boolean variables
 646   vector<TNode> boolVars;
 647   d_propEngine->getBooleanVariables(boolVars);
 648   vector<TNode>::iterator it, iend = boolVars.end();
 649   bool hasValue, value;
 650   for (it = boolVars.begin(); it != iend; ++it) {
 651     TNode var = *it;
 652     hasValue = d_propEngine->hasValue(var, value);
 653     // TODO: Assert that hasValue is true?
 654     if (!hasValue) {
 655       value = false;
 656     }
 657     Trace("model-builder-assertions") << "(assert" << (value ? " " : " (not ") << var << (value ? ");" : "));") << endl;
 658     m->assertPredicate(var, value);
 659   }
 660 }
 661
 662 /* get model */
 663 TheoryModel* TheoryEngine::getModel() {
 664   Debug("model") << "TheoryEngine::getModel()" << endl;
 665   if( d_logicInfo.isQuantified() ) {
 666     Debug("model") << "Get model from quantifiers engine." << endl;
 667     return d_quantEngine->getModel();
 668   } else {
 669     Debug("model") << "Get default model." << endl;
 670     return d_curr_model;
 671   }
 672 }
 673
 674 bool TheoryEngine::presolve() {
 675   // Reset the interrupt flag
 676   d_interrupted = false;
 677
 678   try {
 679     // Definition of the statement that is to be run by every theory
 680 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 681 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 682 #endif
 683 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 684     if (theory::TheoryTraits<THEORY>::hasPresolve) {    \
 685       theoryOf(THEORY)->presolve(); \
 686       if(d_inConflict) { \
 687         return true; \
 688       } \
 689     }
 690
 691     // Presolve for each theory using the statement above
 692     CVC4_FOR_EACH_THEORY;
 693   } catch(const theory::Interrupted&) {
 694     Trace("theory") << "TheoryEngine::presolve() => interrupted" << endl;
 695   }
 696   // return whether we have a conflict
 697   return false;
 698 }/* TheoryEngine::presolve() */
 699
 700 void TheoryEngine::postsolve() {
 701   // Reset the interrupt flag
 702   d_interrupted = false;
 703   bool CVC4_UNUSED wasInConflict = d_inConflict;
 704
 705   try {
 706     // Definition of the statement that is to be run by every theory
 707 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 708 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 709 #endif
 710 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 711     if (theory::TheoryTraits<THEORY>::hasPostsolve) { \
 712       theoryOf(THEORY)->postsolve(); \
 713       Assert(! d_inConflict || wasInConflict, "conflict raised during postsolve()"); \
 714     }
 715
 716     // Postsolve for each theory using the statement above
 717     CVC4_FOR_EACH_THEORY;
 718   } catch(const theory::Interrupted&) {
 719     Trace("theory") << "TheoryEngine::postsolve() => interrupted" << endl;
 720   }
 721 }/* TheoryEngine::postsolve() */
 722
 723
 724 void TheoryEngine::notifyRestart() {
 725   // Reset the interrupt flag
 726   d_interrupted = false;
 727
 728   // Definition of the statement that is to be run by every theory
 729 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 730 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 731 #endif
 732 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 733   if (theory::TheoryTraits<THEORY>::hasNotifyRestart && d_logicInfo.isTheoryEnabled(THEORY)) { \
 734     theoryOf(THEORY)->notifyRestart(); \
 735   }
 736
 737   // notify each theory using the statement above
 738   CVC4_FOR_EACH_THEORY;
 739 }
 740
 741 void TheoryEngine::ppStaticLearn(TNode in, NodeBuilder<>& learned) {
 742   // Reset the interrupt flag
 743   d_interrupted = false;
 744
 745   // Definition of the statement that is to be run by every theory
 746 #ifdef CVC4_FOR_EACH_THEORY_STATEMENT
 747 #undef CVC4_FOR_EACH_THEORY_STATEMENT
 748 #endif
 749 #define CVC4_FOR_EACH_THEORY_STATEMENT(THEORY) \
 750   if (theory::TheoryTraits<THEORY>::hasPpStaticLearn) { \
 751     theoryOf(THEORY)->ppStaticLearn(in, learned); \
 752   }
 753
 754   // static learning for each theory using the statement above
 755   CVC4_FOR_EACH_THEORY;
 756 }
 757
 758 void TheoryEngine::shutdown() {
 759   // Set this first; if a Theory shutdown() throws an exception,
 760   // at least the destruction of the TheoryEngine won't confound
 761   // matters.
 762   d_hasShutDown = true;
 763
 764   // Shutdown all the theories
 765   for(TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST; ++theoryId) {
 766     if(d_theoryTable[theoryId]) {
 767       theoryOf(theoryId)->shutdown();
 768     }
 769   }
 770
 771   d_ppCache.clear();
 772 }
 773
 774 theory::Theory::PPAssertStatus TheoryEngine::solve(TNode literal, SubstitutionMap& substitutionOut) {
 775   // Reset the interrupt flag
 776   d_interrupted = false;
 777
 778   TNode atom = literal.getKind() == kind::NOT ? literal[0] : literal;
 779   Trace("theory::solve") << "TheoryEngine::solve(" << literal << "): solving with " << theoryOf(atom)->getId() << endl;
 780
 781   if(! d_logicInfo.isTheoryEnabled(Theory::theoryOf(atom)) &&
 782      Theory::theoryOf(atom) != THEORY_SAT_SOLVER) {
 783     stringstream ss;
 784     ss << "The logic was specified as " << d_logicInfo.getLogicString()
 785        << ", which doesn't include " << Theory::theoryOf(atom)
 786        << ", but got a preprocessing-time fact for that theory." << endl
 787        << "The fact:" << endl
 788        << literal;
 789     throw LogicException(ss.str());
 790   }
 791
 792   Theory::PPAssertStatus solveStatus = theoryOf(atom)->ppAssert(literal, substitutionOut);
 793   Trace("theory::solve") << "TheoryEngine::solve(" << literal << ") => " << solveStatus << endl;
 794   return solveStatus;
 795 }
 796
 797 // Recursively traverse a term and call the theory rewriter on its sub-terms
 798 Node TheoryEngine::ppTheoryRewrite(TNode term) {
 799   NodeMap::iterator find = d_ppCache.find(term);
 800   if (find != d_ppCache.end()) {
 801     return (*find).second;
 802   }
 803   unsigned nc = term.getNumChildren();
 804   if (nc == 0) {
 805     return theoryOf(term)->ppRewrite(term);
 806   }
 807   Trace("theory-pp") << "ppTheoryRewrite { " << term << endl;
 808
 809   Node newTerm;
 810   if (theoryOf(term)->ppDontRewriteSubterm(term)) {
 811     newTerm = Rewriter::rewrite(term);
 812   } else {
 813     NodeBuilder<> newNode(term.getKind());
 814     if (term.getMetaKind() == kind::metakind::PARAMETERIZED) {
 815       newNode << term.getOperator();
 816     }
 817     unsigned i;
 818     for (i = 0; i < nc; ++i) {
 819       newNode << ppTheoryRewrite(term[i]);
 820     }
 821     newTerm = Rewriter::rewrite(Node(newNode));
 822   }
 823   Node newTerm2 = theoryOf(newTerm)->ppRewrite(newTerm);
 824   if (newTerm != newTerm2) {
 825     newTerm = ppTheoryRewrite(Rewriter::rewrite(newTerm2));
 826   }
 827   d_ppCache[term] = newTerm;
 828   Trace("theory-pp")<< "ppTheoryRewrite returning " << newTerm << "}" << endl;
 829   return newTerm;
 830 }
 831
 832
 833 void TheoryEngine::preprocessStart()
 834 {
 835   d_ppCache.clear();
 836 }
 837
 838
 839 struct preprocess_stack_element {
 840   TNode node;
 841   bool children_added;
 842   preprocess_stack_element(TNode node)
 843   : node(node), children_added(false) {}
 844 };/* struct preprocess_stack_element */
 845
 846
 847 Node TheoryEngine::preprocess(TNode assertion) {
 848
 849   Trace("theory::preprocess") << "TheoryEngine::preprocess(" << assertion << ")" << endl;
 850   // spendResource();
 851
 852   // Do a topological sort of the subexpressions and substitute them
 853   vector<preprocess_stack_element> toVisit;
 854   toVisit.push_back(assertion);
 855
 856   while (!toVisit.empty())
 857   {
 858     // The current node we are processing
 859     preprocess_stack_element& stackHead = toVisit.back();
 860     TNode current = stackHead.node;
 861
 862     Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion << "): processing " << current << endl;
 863
 864     // If node already in the cache we're done, pop from the stack
 865     NodeMap::iterator find = d_ppCache.find(current);
 866     if (find != d_ppCache.end()) {
 867       toVisit.pop_back();
 868       continue;
 869     }
 870
 871     if(! d_logicInfo.isTheoryEnabled(Theory::theoryOf(current)) &&
 872        Theory::theoryOf(current) != THEORY_SAT_SOLVER) {
 873       stringstream ss;
 874       ss << "The logic was specified as " << d_logicInfo.getLogicString()
 875          << ", which doesn't include " << Theory::theoryOf(current)
 876          << ", but got a preprocessing-time fact for that theory." << endl
 877          << "The fact:" << endl
 878          << current;
 879       throw LogicException(ss.str());
 880     }
 881
 882     // If this is an atom, we preprocess its terms with the theory ppRewriter
 883     if (Theory::theoryOf(current) != THEORY_BOOL) {
 884       Node ppRewritten = ppTheoryRewrite(current);
 885       d_ppCache[current] = ppRewritten;
 886       Assert(Rewriter::rewrite(d_ppCache[current]) == d_ppCache[current]);
 887       continue;
 888     }
 889
 890     // Not yet substituted, so process
 891     if (stackHead.children_added) {
 892       // Children have been processed, so substitute
 893       NodeBuilder<> builder(current.getKind());
 894       if (current.getMetaKind() == kind::metakind::PARAMETERIZED) {
 895         builder << current.getOperator();
 896       }
 897       for (unsigned i = 0; i < current.getNumChildren(); ++ i) {
 898         Assert(d_ppCache.find(current[i]) != d_ppCache.end());
 899         builder << d_ppCache[current[i]];
 900       }
 901       // Mark the substitution and continue
 902       Node result = builder;
 903       if (result != current) {
 904         result = Rewriter::rewrite(result);
 905       }
 906       Debug("theory::internal") << "TheoryEngine::preprocess(" << assertion << "): setting " << current << " -> " << result << endl;
 907       d_ppCache[current] = result;
 908       toVisit.pop_back();
 909     } else {
 910       // Mark that we have added the children if any
 911       if (current.getNumChildren() > 0) {
 912         stackHead.children_added = true;
 913         // We need to add the children
 914         for(TNode::iterator child_it = current.begin(); child_it != current.end(); ++ child_it) {
 915           TNode childNode = *child_it;
 916           NodeMap::iterator childFind = d_ppCache.find(childNode);
 917           if (childFind == d_ppCache.end()) {
 918             toVisit.push_back(childNode);
 919           }
 920         }
 921       } else {
 922         // No children, so we're done
 923         Debug("substitution::internal") << "SubstitutionMap::internalSubstitute(" << assertion << "): setting " << current << " -> " << current << endl;
 924         d_ppCache[current] = current;
 925         toVisit.pop_back();
 926       }
 927     }
 928   }
 929
 930   // Return the substituted version
 931   return d_ppCache[assertion];
 932 }
 933
 934 bool TheoryEngine::markPropagation(TNode assertion, TNode originalAssertion, theory::TheoryId toTheoryId, theory::TheoryId fromTheoryId) {
 935
 936   // What and where we are asserting
 937   NodeTheoryPair toAssert(assertion, toTheoryId, d_propagationMapTimestamp);
 938   // What and where it came from
 939   NodeTheoryPair toExplain(originalAssertion, fromTheoryId, d_propagationMapTimestamp);
 940
 941   // See if the theory already got this literal
 942   PropagationMap::const_iterator find = d_propagationMap.find(toAssert);
 943   if (find != d_propagationMap.end()) {
 944     // The theory already knows this
 945     Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): already there" << endl;
 946     return false;
 947   }
 948
 949   Trace("theory::assertToTheory") << "TheoryEngine::markPropagation(): marking [" << d_propagationMapTimestamp << "] " << assertion << ", " << toTheoryId << " from " << originalAssertion << ", " << fromTheoryId << endl;
 950
 951   // Mark the propagation
 952   d_propagationMap[toAssert] = toExplain;
 953   d_propagationMapTimestamp = d_propagationMapTimestamp + 1;
 954
 955   return true;
 956 }
 957
 958
 959 void TheoryEngine::assertToTheory(TNode assertion, TNode originalAssertion, theory::TheoryId toTheoryId, theory::TheoryId fromTheoryId) {
 960
 961   Trace("theory::assertToTheory") << "TheoryEngine::assertToTheory(" << assertion << ", " << toTheoryId << ", " << fromTheoryId << ")" << endl;
 962
 963   Assert(toTheoryId != fromTheoryId);
 964   if(! d_logicInfo.isTheoryEnabled(toTheoryId) &&
 965      toTheoryId != THEORY_SAT_SOLVER) {
 966     stringstream ss;
 967     ss << "The logic was specified as " << d_logicInfo.getLogicString()
 968        << ", which doesn't include " << toTheoryId
 969        << ", but got an asserted fact to that theory." << endl
 970        << "The fact:" << endl
 971        << assertion;
 972     throw LogicException(ss.str());
 973   }
 974
 975   if (d_inConflict) {
 976     return;
 977   }
 978
 979   // If sharing is disabled, things are easy
 980   if (!d_logicInfo.isSharingEnabled()) {
 981     Assert(assertion == originalAssertion);
 982     if (fromTheoryId == THEORY_SAT_SOLVER) {
 983       // Send to the apropriate theory
 984       theory::Theory* toTheory = theoryOf(toTheoryId);
 985       // We assert it, and we know it's preregistereed
 986       toTheory->assertFact(assertion, true);
 987       // Mark that we have more information
 988       d_factsAsserted = true;
 989     } else {
 990       Assert(toTheoryId == THEORY_SAT_SOLVER);
 991       // Check for propositional conflict
 992       bool value;
 993       if (d_propEngine->hasValue(assertion, value)) {
 994         if (!value) {
 995           Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion << ", " << toTheoryId << ", " << fromTheoryId << "): conflict (no sharing)" << endl;
 996           d_inConflict = true;
 997         } else {
 998           return;
 999         }
1000       }
1001       d_propagatedLiterals.push_back(assertion);
1002     }
1003     return;
1004   }
1005
1006   // Polarity of the assertion
1007   bool polarity = assertion.getKind() != kind::NOT;
1008
1009   // Atom of the assertion
1010   TNode atom = polarity ? assertion : assertion[0];
1011
1012   // If sending to the shared terms database, it's also simple
1013   if (toTheoryId == THEORY_BUILTIN) {
1014     Assert(atom.getKind() == kind::EQUAL, "atom should be an EQUALity, not `%s'", atom.toString().c_str());
1015     if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1016       d_sharedTerms.assertEquality(atom, polarity, assertion);
1017     }
1018     return;
1019   }
1020
1021   // Things from the SAT solver are already normalized, so they go
1022   // directly to the apropriate theory
1023   if (fromTheoryId == THEORY_SAT_SOLVER) {
1024     // We know that this is normalized, so just send it off to the theory
1025     if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1026       // Is it preregistered
1027       bool preregistered = d_propEngine->isSatLiteral(assertion) && Theory::theoryOf(assertion) == toTheoryId;
1028       // We assert it
1029       theoryOf(toTheoryId)->assertFact(assertion, preregistered);
1030       // Mark that we have more information
1031       d_factsAsserted = true;
1032     }
1033     return;
1034   }
1035
1036   // Propagations to the SAT solver are just enqueued for pickup by
1037   // the SAT solver later
1038   if (toTheoryId == THEORY_SAT_SOLVER) {
1039     if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1040       // Enqueue for propagation to the SAT solver
1041       d_propagatedLiterals.push_back(assertion);
1042       // Check for propositional conflicts
1043       bool value;
1044       if (d_propEngine->hasValue(assertion, value) && !value) {
1045           Trace("theory::propagate") << "TheoryEngine::assertToTheory(" << assertion << ", " << toTheoryId << ", " << fromTheoryId << "): conflict (sharing)" << endl;
1046         d_inConflict = true;
1047       }
1048     }
1049     return;
1050   }
1051
1052   Assert(atom.getKind() == kind::EQUAL);
1053
1054   // Normalize
1055   Node normalizedLiteral = Rewriter::rewrite(assertion);
1056
1057   // See if it rewrites false directly -> conflict
1058   if (normalizedLiteral.isConst()) {
1059     if (!normalizedLiteral.getConst<bool>()) {
1060       // Mark the propagation for explanations
1061       if (markPropagation(normalizedLiteral, originalAssertion, toTheoryId, fromTheoryId)) {
1062         // Get the explanation (conflict will figure out where it came from)
1063         conflict(normalizedLiteral, toTheoryId);
1064       } else {
1065         Unreachable();
1066       }
1067       return;
1068     }
1069   }
1070
1071   // Try and assert (note that we assert the non-normalized one)
1072   if (markPropagation(assertion, originalAssertion, toTheoryId, fromTheoryId)) {
1073     // Check if has been pre-registered with the theory
1074     bool preregistered = d_propEngine->isSatLiteral(assertion) && Theory::theoryOf(assertion) == toTheoryId;
1075     // Assert away
1076     theoryOf(toTheoryId)->assertFact(assertion, preregistered);
1077     d_factsAsserted = true;
1078   }
1079
1080   return;
1081 }
1082
1083 void TheoryEngine::assertFact(TNode literal)
1084 {
1085   Trace("theory") << "TheoryEngine::assertFact(" << literal << ")" << endl;
1086
1087   // spendResource();
1088
1089   // If we're in conflict, nothing to do
1090   if (d_inConflict) {
1091     return;
1092   }
1093
1094   // Get the atom
1095   bool polarity = literal.getKind() != kind::NOT;
1096   TNode atom = polarity ? literal : literal[0];
1097
1098   if (d_logicInfo.isSharingEnabled()) {
1099
1100     // If any shared terms, it's time to do sharing work
1101     if (d_sharedTerms.hasSharedTerms(atom)) {
1102       // Notify the theories the shared terms
1103       SharedTermsDatabase::shared_terms_iterator it = d_sharedTerms.begin(atom);
1104       SharedTermsDatabase::shared_terms_iterator it_end = d_sharedTerms.end(atom);
1105       for (; it != it_end; ++ it) {
1106         TNode term = *it;
1107         Theory::Set theories = d_sharedTerms.getTheoriesToNotify(atom, term);
1108         for (TheoryId id = THEORY_FIRST; id != THEORY_LAST; ++ id) {
1109           if (Theory::setContains(id, theories)) {
1110             theoryOf(id)->addSharedTermInternal(term);
1111           }
1112         }
1113         d_sharedTerms.markNotified(term, theories);
1114       }
1115     }
1116
1117     // If it's an equality, assert it to the shared term manager, even though the terms are not
1118     // yet shared. As the terms become shared later, the shared terms manager will then add them
1119     // to the assert the equality to the interested theories
1120     if (atom.getKind() == kind::EQUAL) {
1121       // Assert it to the the owning theory
1122       assertToTheory(literal, literal, /* to */ Theory::theoryOf(atom), /* from */ THEORY_SAT_SOLVER);
1123       // Shared terms manager will assert to interested theories directly, as the terms become shared
1124       assertToTheory(literal, literal, /* to */ THEORY_BUILTIN, /* from */ THEORY_SAT_SOLVER);
1125
1126       // Now, let's check for any atom triggers from lemmas
1127       AtomRequests::atom_iterator it = d_atomRequests.getAtomIterator(atom);
1128       while (!it.done()) {
1129         const AtomRequests::Request& request = it.get();
1130         Node toAssert = polarity ? (Node) request.atom : request.atom.notNode();
1131         Debug("theory::atoms") << "TheoryEngine::assertFact(" << literal << "): sending requested " << toAssert << endl;
1132         assertToTheory(toAssert, literal, request.toTheory, THEORY_SAT_SOLVER);
1133         it.next();
1134       }
1135
1136     } else {
1137       // Not an equality, just assert to the appropriate theory
1138       assertToTheory(literal, literal, /* to */ Theory::theoryOf(atom), /* from */ THEORY_SAT_SOLVER);
1139     }
1140   } else {
1141     // Assert the fact to the appropriate theory directly
1142     assertToTheory(literal, literal, /* to */ Theory::theoryOf(atom), /* from */ THEORY_SAT_SOLVER);
1143   }
1144 }
1145
1146 bool TheoryEngine::propagate(TNode literal, theory::TheoryId theory) {
1147
1148   Debug("theory::propagate") << "TheoryEngine::propagate(" << literal << ", " << theory << ")" << endl;
1149
1150   // spendResource();
1151
1152   if(Dump.isOn("t-propagations")) {
1153     Dump("t-propagations") << CommentCommand("negation of theory propagation: expect valid")
1154                            << QueryCommand(literal.toExpr());
1155   }
1156   if(Dump.isOn("missed-t-propagations")) {
1157     d_hasPropagated.insert(literal);
1158   }
1159
1160   // Get the atom
1161   bool polarity = literal.getKind() != kind::NOT;
1162   TNode atom = polarity ? literal : literal[0];
1163
1164   if (d_logicInfo.isSharingEnabled() && atom.getKind() == kind::EQUAL) {
1165     if (d_propEngine->isSatLiteral(literal)) {
1166       // We propagate SAT literals to SAT
1167       assertToTheory(literal, literal, /* to */ THEORY_SAT_SOLVER, /* from */ theory);
1168     }
1169     if (theory != THEORY_BUILTIN) {
1170       // Assert to the shared terms database
1171       assertToTheory(literal, literal, /* to */ THEORY_BUILTIN, /* from */ theory);
1172     }
1173   } else {
1174     // Just send off to the SAT solver
1175     Assert(d_propEngine->isSatLiteral(literal));
1176     assertToTheory(literal, literal, /* to */ THEORY_SAT_SOLVER, /* from */ theory);
1177   }
1178
1179   return !d_inConflict;
1180 }
1181
1182
1183 theory::EqualityStatus TheoryEngine::getEqualityStatus(TNode a, TNode b) {
1184   Assert(a.getType().isComparableTo(b.getType()));
1185   if (d_sharedTerms.isShared(a) && d_sharedTerms.isShared(b)) {
1186     if (d_sharedTerms.areEqual(a,b)) {
1187       return EQUALITY_TRUE_AND_PROPAGATED;
1188     }
1189     else if (d_sharedTerms.areDisequal(a,b)) {
1190       return EQUALITY_FALSE_AND_PROPAGATED;
1191     }
1192   }
1193   return theoryOf(Theory::theoryOf(a.getType()))->getEqualityStatus(a, b);
1194 }
1195
1196 Node TheoryEngine::getModelValue(TNode var) {
1197   Assert(d_sharedTerms.isShared(var));
1198   return theoryOf(Theory::theoryOf(var.getType()))->getModelValue(var);
1199 }
1200
1201
1202 Node TheoryEngine::ensureLiteral(TNode n) {
1203   Debug("ensureLiteral") << "rewriting: " << n << std::endl;
1204   Node rewritten = Rewriter::rewrite(n);
1205   Debug("ensureLiteral") << "      got: " << rewritten << std::endl;
1206   Node preprocessed = preprocess(rewritten);
1207   Debug("ensureLiteral") << "preprocessed: " << preprocessed << std::endl;
1208   d_propEngine->ensureLiteral(preprocessed);
1209   return preprocessed;
1210 }
1211
1212
1213 void TheoryEngine::printInstantiations( std::ostream& out ) {
1214   if( d_quantEngine ){
1215     d_quantEngine->printInstantiations( out );
1216   }
1217 }
1218
1219 static Node mkExplanation(const std::vector<NodeTheoryPair>& explanation) {
1220
1221   std::set<TNode> all;
1222   for (unsigned i = 0; i < explanation.size(); ++ i) {
1223     Assert(explanation[i].theory == THEORY_SAT_SOLVER);
1224     all.insert(explanation[i].node);
1225   }
1226
1227   if (all.size() == 0) {
1228     // Normalize to true
1229     return NodeManager::currentNM()->mkConst<bool>(true);
1230   }
1231
1232   if (all.size() == 1) {
1233     // All the same, or just one
1234     return explanation[0].node;
1235   }
1236
1237   NodeBuilder<> conjunction(kind::AND);
1238   std::set<TNode>::const_iterator it = all.begin();
1239   std::set<TNode>::const_iterator it_end = all.end();
1240   while (it != it_end) {
1241     conjunction << *it;
1242     ++ it;
1243   }
1244
1245   return conjunction;
1246 }
1247
1248
1249 Node TheoryEngine::getExplanation(TNode node) {
1250   Debug("theory::explain") << "TheoryEngine::getExplanation(" << node << "): current propagation index = " << d_propagationMapTimestamp << endl;
1251
1252   bool polarity = node.getKind() != kind::NOT;
1253   TNode atom = polarity ? node : node[0];
1254
1255   // If we're not in shared mode, explanations are simple
1256   if (!d_logicInfo.isSharingEnabled()) {
1257     Node explanation = theoryOf(atom)->explain(node);
1258     Debug("theory::explain") << "TheoryEngine::getExplanation(" << node << ") => " << explanation << endl;
1259     return explanation;
1260   }
1261
1262   // Initial thing to explain
1263   NodeTheoryPair toExplain(node, THEORY_SAT_SOLVER, d_propagationMapTimestamp);
1264   Assert(d_propagationMap.find(toExplain) != d_propagationMap.end());
1265   // Create the workplace for explanations
1266   std::vector<NodeTheoryPair> explanationVector;
1267   explanationVector.push_back(d_propagationMap[toExplain]);
1268   // Process the explanation
1269   getExplanation(explanationVector);
1270   Node explanation = mkExplanation(explanationVector);
1271
1272   Debug("theory::explain") << "TheoryEngine::getExplanation(" << node << ") => " << explanation << endl;
1273
1274   return explanation;
1275 }
1276
1277 struct AtomsCollect {
1278
1279   std::vector<TNode> d_atoms;
1280   std::hash_set<TNode, TNodeHashFunction> d_visited;
1281
1282 public:
1283
1284   typedef void return_type;
1285
1286   bool alreadyVisited(TNode current, TNode parent) {
1287     // Check if already visited
1288     if (d_visited.find(current) != d_visited.end()) return true;
1289     // Don't visit non-boolean
1290     if (!current.getType().isBoolean()) return true;
1291     // New node
1292     return false;
1293   }
1294
1295   void visit(TNode current, TNode parent) {
1296     if (Theory::theoryOf(current) != theory::THEORY_BOOL) {
1297       d_atoms.push_back(current);
1298     }
1299     d_visited.insert(current);
1300   }
1301
1302   void start(TNode node) {}
1303   void done(TNode node) {}
1304
1305   std::vector<TNode> getAtoms() const {
1306     return d_atoms;
1307   }
1308 };
1309
1310 void TheoryEngine::ensureLemmaAtoms(const std::vector<TNode>& atoms, theory::TheoryId atomsTo) {
1311   for (unsigned i = 0; i < atoms.size(); ++ i) {
1312
1313     // Non-equality atoms are either owned by theory or they don't make sense
1314     if (atoms[i].getKind() != kind::EQUAL) {
1315       continue;
1316     }
1317
1318     // The equality
1319     Node eq = atoms[i];
1320     // Simple normalization to not repeat stuff
1321     if (eq[0] > eq[1]) {
1322       eq = eq[1].eqNode(eq[0]);
1323     }
1324
1325     // Rewrite the equality
1326     Node eqNormalized = Rewriter::rewrite(atoms[i]);
1327
1328     Debug("theory::atoms") << "TheoryEngine::ensureLemmaAtoms(): " << eq << " with nf " << eqNormalized << endl;
1329
1330     // If the equality is a boolean constant, we send immediately
1331     if (eqNormalized.isConst()) {
1332       if (eqNormalized.getConst<bool>()) {
1333         assertToTheory(eq, eqNormalized, /** to */ atomsTo, /** Sat solver */ theory::THEORY_SAT_SOLVER);
1334       } else {
1335         assertToTheory(eq.notNode(), eqNormalized.notNode(), /** to */ atomsTo, /** Sat solver */ theory::THEORY_SAT_SOLVER);
1336       }
1337       continue;
1338     }
1339
1340     Assert(eqNormalized.getKind() == kind::EQUAL);
1341
1342
1343     // If the normalization did the just flips, keep the flip
1344     if (eqNormalized[0] == eq[1] && eqNormalized[1] == eq[0]) {
1345       eq = eqNormalized;
1346     }
1347
1348     // Check if the equality is already known by the sat solver
1349     if (d_propEngine->isSatLiteral(eqNormalized)) {
1350       bool value;
1351       if (d_propEngine->hasValue(eqNormalized, value)) {
1352         if (value) {
1353           assertToTheory(eq, eqNormalized, atomsTo, theory::THEORY_SAT_SOLVER);
1354           continue;
1355         } else {
1356           assertToTheory(eq.notNode(), eqNormalized.notNode(), atomsTo, theory::THEORY_SAT_SOLVER);
1357           continue;
1358         }
1359       }
1360     }
1361
1362     // If the theory is asking about a different form, or the form is ok but if will go to a different theory
1363     // then we must figure it out
1364     if (eqNormalized != eq || Theory::theoryOf(eq) != atomsTo) {
1365       // If you get eqNormalized, send atoms[i] to atomsTo
1366       d_atomRequests.add(eqNormalized, eq, atomsTo);
1367     }
1368   }
1369 }
1370
1371 theory::LemmaStatus TheoryEngine::lemma(TNode node, bool negated, bool removable, bool preprocess, theory::TheoryId atomsTo) {
1372   // For resource-limiting (also does a time check).
1373   // spendResource();
1374
1375   // Do we need to check atoms
1376   if (atomsTo != theory::THEORY_LAST) {
1377     Debug("theory::atoms") << "TheoryEngine::lemma(" << node << ", " << atomsTo << ")" << endl;
1378     AtomsCollect collectAtoms;
1379     NodeVisitor<AtomsCollect>::run(collectAtoms, node);
1380     ensureLemmaAtoms(collectAtoms.getAtoms(), atomsTo);
1381   }
1382
1383   if(Dump.isOn("t-lemmas")) {
1384     Node n = node;
1385     if (negated) {
1386       n = node.negate();
1387     }
1388     Dump("t-lemmas") << CommentCommand("theory lemma: expect valid")
1389                      << QueryCommand(n.toExpr());
1390   }
1391
1392   // Share with other portfolio threads
1393   if(options::lemmaOutputChannel() != NULL) {
1394     options::lemmaOutputChannel()->notifyNewLemma(node.toExpr());
1395   }
1396
1397   // Run theory preprocessing, maybe
1398   Node ppNode = preprocess ? this->preprocess(node) : Node(node);
1399
1400   // Remove the ITEs
1401   std::vector<Node> additionalLemmas;
1402   IteSkolemMap iteSkolemMap;
1403   additionalLemmas.push_back(ppNode);
1404   d_iteRemover.run(additionalLemmas, iteSkolemMap);
1405   additionalLemmas[0] = theory::Rewriter::rewrite(additionalLemmas[0]);
1406
1407   if(Debug.isOn("lemma-ites")) {
1408     Debug("lemma-ites") << "removed ITEs from lemma: " << ppNode << endl;
1409     Debug("lemma-ites") << " + now have the following "
1410                         << additionalLemmas.size() << " lemma(s):" << endl;
1411     for(std::vector<Node>::const_iterator i = additionalLemmas.begin();
1412         i != additionalLemmas.end();
1413         ++i) {
1414       Debug("lemma-ites") << " + " << *i << endl;
1415     }
1416     Debug("lemma-ites") << endl;
1417   }
1418
1419   // assert to prop engine
1420   d_propEngine->assertLemma(additionalLemmas[0], negated, removable, RULE_INVALID, node);
1421   for (unsigned i = 1; i < additionalLemmas.size(); ++ i) {
1422     additionalLemmas[i] = theory::Rewriter::rewrite(additionalLemmas[i]);
1423     d_propEngine->assertLemma(additionalLemmas[i], false, removable, RULE_INVALID, node);
1424   }
1425
1426   // WARNING: Below this point don't assume additionalLemmas[0] to be not negated.
1427   if(negated) {
1428     additionalLemmas[0] = additionalLemmas[0].notNode();
1429     negated = false;
1430   }
1431
1432   // assert to decision engine
1433   if(!removable) {
1434     d_decisionEngine->addAssertions(additionalLemmas, 1, iteSkolemMap);
1435   }
1436
1437   // Mark that we added some lemmas
1438   d_lemmasAdded = true;
1439
1440   // Lemma analysis isn't online yet; this lemma may only live for this
1441   // user level.
1442   return theory::LemmaStatus(additionalLemmas[0], d_userContext->getLevel());
1443 }
1444
1445 void TheoryEngine::conflict(TNode conflict, TheoryId theoryId) {
1446
1447   Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict << ", " << theoryId << ")" << endl;
1448
1449   // Mark that we are in conflict
1450   d_inConflict = true;
1451
1452   if(Dump.isOn("t-conflicts")) {
1453     Dump("t-conflicts") << CommentCommand("theory conflict: expect unsat")
1454                         << CheckSatCommand(conflict.toExpr());
1455   }
1456
1457   // In the multiple-theories case, we need to reconstruct the conflict
1458   if (d_logicInfo.isSharingEnabled()) {
1459     // Create the workplace for explanations
1460     std::vector<NodeTheoryPair> explanationVector;
1461     explanationVector.push_back(NodeTheoryPair(conflict, theoryId, d_propagationMapTimestamp));
1462     // Process the explanation
1463     getExplanation(explanationVector);
1464     Node fullConflict = mkExplanation(explanationVector);
1465     Debug("theory::conflict") << "TheoryEngine::conflict(" << conflict << ", " << theoryId << "): full = " << fullConflict << endl;
1466     Assert(properConflict(fullConflict));
1467     lemma(fullConflict, true, true, false, THEORY_LAST);
1468   } else {
1469     // When only one theory, the conflict should need no processing
1470     Assert(properConflict(conflict));
1471     lemma(conflict, true, true, false, THEORY_LAST);
1472   }
1473 }
1474
1475 void TheoryEngine::staticInitializeBVOptions(const std::vector<Node>& assertions) {
1476   bool useSlicer = true;
1477   if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_ON) {
1478     if (options::incrementalSolving())
1479       throw ModalException("Slicer does not currently support incremental mode. Use --bv-eq-slicer=off");
1480     if (options::produceModels())
1481       throw ModalException("Slicer does not currently support model generation. Use --bv-eq-slicer=off");
1482     useSlicer = true;
1483
1484   } else if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_OFF) {
1485     return;
1486
1487   } else if (options::bitvectorEqualitySlicer() == bv::BITVECTOR_SLICER_AUTO) {
1488     if (options::incrementalSolving() ||
1489         options::produceModels())
1490       return;
1491
1492     useSlicer = true;
1493     bv::utils::TNodeBoolMap cache;
1494     for (unsigned i = 0; i < assertions.size(); ++i) {
1495       useSlicer = useSlicer && bv::utils::isCoreTerm(assertions[i], cache);
1496     }
1497   }
1498
1499   if (useSlicer) {
1500     bv::TheoryBV* bv_theory = (bv::TheoryBV*)d_theoryTable[THEORY_BV];
1501     bv_theory->enableCoreTheorySlicer();
1502   }
1503
1504 }
1505
1506 void TheoryEngine::ppBvToBool(const std::vector<Node>& assertions, std::vector<Node>& new_assertions) {
1507   d_bvToBoolPreprocessor.liftBvToBool(assertions, new_assertions);
1508 }
1509
1510 bool  TheoryEngine::ppBvAbstraction(const std::vector<Node>& assertions, std::vector<Node>& new_assertions) {
1511   bv::TheoryBV* bv_theory = (bv::TheoryBV*)d_theoryTable[THEORY_BV];
1512   return bv_theory->applyAbstraction(assertions, new_assertions);
1513 }
1514
1515 void TheoryEngine::mkAckermanizationAsssertions(std::vector<Node>& assertions) {
1516   bv::TheoryBV* bv_theory = (bv::TheoryBV*)d_theoryTable[THEORY_BV];
1517   bv_theory->mkAckermanizationAsssertions(assertions);
1518 }
1519
1520 Node TheoryEngine::ppSimpITE(TNode assertion)
1521 {
1522   if(!d_iteRemover.containsTermITE(assertion)){
1523     return assertion;
1524   }else{
1525
1526     Node result = d_iteUtilities->simpITE(assertion);
1527     Node res_rewritten = Rewriter::rewrite(result);
1528
1529     if(options::simplifyWithCareEnabled()){
1530       Chat() << "starting simplifyWithCare()" << endl;
1531       Node postSimpWithCare = d_iteUtilities->simplifyWithCare(res_rewritten);
1532       Chat() << "ending simplifyWithCare()"
1533              << " post simplifyWithCare()" << postSimpWithCare.getId() << endl;
1534       result = Rewriter::rewrite(postSimpWithCare);
1535     }else{
1536       result = res_rewritten;
1537     }
1538
1539     return result;
1540   }
1541 }
1542
1543 bool TheoryEngine::donePPSimpITE(std::vector<Node>& assertions){
1544   bool result = true;
1545   bool simpDidALotOfWork = d_iteUtilities->simpIteDidALotOfWorkHeuristic();
1546   if(simpDidALotOfWork){
1547     if(options::compressItes()){
1548       result = d_iteUtilities->compress(assertions);
1549     }
1550
1551     if(result){
1552       // if false, don't bother to reclaim memory here.
1553       NodeManager* nm = NodeManager::currentNM();
1554       if(nm->poolSize() >= options::zombieHuntThreshold()){
1555         Chat() << "..ite simplifier did quite a bit of work.. " << nm->poolSize() << endl;
1556         Chat() << "....node manager contains " << nm->poolSize() << " nodes before cleanup" << endl;
1557         d_iteUtilities->clear();
1558         Rewriter::clearCaches();
1559         d_iteRemover.garbageCollect();
1560         nm->reclaimZombiesUntil(options::zombieHuntThreshold());
1561         Chat() << "....node manager contains " << nm->poolSize() << " nodes after cleanup" << endl;
1562       }
1563     }
1564   }
1565
1566   // Do theory specific preprocessing passes
1567   if(d_logicInfo.isTheoryEnabled(theory::THEORY_ARITH)){
1568     if(!simpDidALotOfWork){
1569       ContainsTermITEVisitor& contains = *d_iteRemover.getContainsVisitor();
1570       arith::ArithIteUtils aiteu(contains, d_userContext, getModel());
1571       bool anyItes = false;
1572       for(size_t i = 0;  i < assertions.size(); ++i){
1573         Node curr = assertions[i];
1574         if(contains.containsTermITE(curr)){
1575           anyItes = true;
1576           Node res = aiteu.reduceVariablesInItes(curr);
1577           Debug("arith::ite::red") << "@ " << i << " ... " << curr << endl << "   ->" << res << endl;
1578           if(curr != res){
1579             Node more = aiteu.reduceConstantIteByGCD(res);
1580             Debug("arith::ite::red") << "  gcd->" << more << endl;
1581             assertions[i] = more;
1582           }
1583         }
1584       }
1585       if(!anyItes){
1586         unsigned prevSubCount = aiteu.getSubCount();
1587         aiteu.learnSubstitutions(assertions);
1588         if(prevSubCount < aiteu.getSubCount()){
1589           d_arithSubstitutionsAdded += aiteu.getSubCount() - prevSubCount;
1590           bool anySuccess = false;
1591           for(size_t i = 0, N =  assertions.size();  i < N; ++i){
1592             Node curr = assertions[i];
1593             Node next = Rewriter::rewrite(aiteu.applySubstitutions(curr));
1594             Node res = aiteu.reduceVariablesInItes(next);
1595             Debug("arith::ite::red") << "@ " << i << " ... " << next << endl << "   ->" << res << endl;
1596             Node more = aiteu.reduceConstantIteByGCD(res);
1597             Debug("arith::ite::red") << "  gcd->" << more << endl;
1598             if(more != next){
1599               anySuccess = true;
1600               break;
1601             }
1602           }
1603           for(size_t i = 0, N =  assertions.size();  anySuccess && i < N; ++i){
1604             Node curr = assertions[i];
1605             Node next = Rewriter::rewrite(aiteu.applySubstitutions(curr));
1606             Node res = aiteu.reduceVariablesInItes(next);
1607             Debug("arith::ite::red") << "@ " << i << " ... " << next << endl << "   ->" << res << endl;
1608             Node more = aiteu.reduceConstantIteByGCD(res);
1609             Debug("arith::ite::red") << "  gcd->" << more << endl;
1610             assertions[i] = Rewriter::rewrite(more);
1611           }
1612         }
1613       }
1614     }
1615   }
1616   return result;
1617 }
1618
1619 void TheoryEngine::getExplanation(std::vector<NodeTheoryPair>& explanationVector)
1620 {
1621   Assert(explanationVector.size() > 0);
1622
1623   unsigned i = 0; // Index of the current literal we are processing
1624   unsigned j = 0; // Index of the last literal we are keeping
1625
1626   while (i < explanationVector.size()) {
1627
1628     // Get the current literal to explain
1629     NodeTheoryPair toExplain = explanationVector[i];
1630
1631     Debug("theory::explain") << "TheoryEngine::explain(): processing [" << toExplain.timestamp << "] " << toExplain.node << " sent from " << toExplain.theory << endl;
1632
1633     // If a true constant or a negation of a false constant we can ignore it
1634     if (toExplain.node.isConst() && toExplain.node.getConst<bool>()) {
1635       ++ i;
1636       continue;
1637     }
1638     if (toExplain.node.getKind() == kind::NOT && toExplain.node[0].isConst() && !toExplain.node[0].getConst<bool>()) {
1639       ++ i;
1640       continue;
1641     }
1642
1643     // If from the SAT solver, keep it
1644     if (toExplain.theory == THEORY_SAT_SOLVER) {
1645       explanationVector[j++] = explanationVector[i++];
1646       continue;
1647     }
1648
1649     // If an and, expand it
1650     if (toExplain.node.getKind() == kind::AND) {
1651       Debug("theory::explain") << "TheoryEngine::explain(): expanding " << toExplain.node << " got from " << toExplain.theory << endl;
1652       for (unsigned k = 0; k < toExplain.node.getNumChildren(); ++ k) {
1653         NodeTheoryPair newExplain(toExplain.node[k], toExplain.theory, toExplain.timestamp);
1654         explanationVector.push_back(newExplain);
1655       }
1656       ++ i;
1657       continue;
1658     }
1659
1660     // See if it was sent to the theory by another theory
1661     PropagationMap::const_iterator find = d_propagationMap.find(toExplain);
1662     if (find != d_propagationMap.end()) {
1663       // There is some propagation, check if its a timely one
1664       if ((*find).second.timestamp < toExplain.timestamp) {
1665         explanationVector.push_back((*find).second);
1666         ++ i;
1667         continue;
1668       }
1669     }
1670
1671     // It was produced by the theory, so ask for an explanation
1672     Node explanation;
1673     if (toExplain.theory == THEORY_BUILTIN) {
1674       explanation = d_sharedTerms.explain(toExplain.node);
1675     } else {
1676       explanation = theoryOf(toExplain.theory)->explain(toExplain.node);
1677     }
1678     Debug("theory::explain") << "TheoryEngine::explain(): got explanation " << explanation << " got from " << toExplain.theory << endl;
1679     Assert(explanation != toExplain.node, "wasn't sent to you, so why are you explaining it trivially");
1680     // Mark the explanation
1681     NodeTheoryPair newExplain(explanation, toExplain.theory, toExplain.timestamp);
1682     explanationVector.push_back(newExplain);
1683     ++ i;
1684   }
1685
1686   // Keep only the relevant literals
1687   explanationVector.resize(j);
1688 }
1689
1690
1691 void TheoryEngine::ppUnconstrainedSimp(vector<Node>& assertions)
1692 {
1693   d_unconstrainedSimp->processAssertions(assertions);
1694 }
1695
1696
1697 void TheoryEngine::setUserAttribute(const std::string& attr, Node n, std::vector<Node> node_values, std::string str_value) {
1698   Trace("te-attr") << "set user attribute " << attr << " " << n << endl;
1699   if( d_attr_handle.find( attr )!=d_attr_handle.end() ){
1700     for( size_t i=0; i<d_attr_handle[attr].size(); i++ ){
1701       d_attr_handle[attr][i]->setUserAttribute(attr, n, node_values, str_value);
1702     }
1703   } else {
1704     //unhandled exception?
1705   }
1706 }
1707
1708 void TheoryEngine::handleUserAttribute(const char* attr, Theory* t) {
1709   Trace("te-attr") << "Handle user attribute " << attr << " " << t << endl;
1710   std::string str( attr );
1711   d_attr_handle[ str ].push_back( t );
1712 }
1713
1714 void TheoryEngine::checkTheoryAssertionsWithModel() {
1715   for(TheoryId theoryId = THEORY_FIRST; theoryId < THEORY_LAST; ++theoryId) {
1716     Theory* theory = d_theoryTable[theoryId];
1717     if(theory && d_logicInfo.isTheoryEnabled(theoryId)) {
1718       for(context::CDList<Assertion>::const_iterator it = theory->facts_begin(),
1719             it_end = theory->facts_end();
1720           it != it_end;
1721           ++it) {
1722         Node assertion = (*it).assertion;
1723         Node val = getModel()->getValue(assertion);
1724         if(val != d_true) {
1725           stringstream ss;
1726           ss << theoryId << " has an asserted fact that the model doesn't satisfy." << endl
1727              << "The fact: " << assertion << endl
1728              << "Model value: " << val << endl;
1729           InternalError(ss.str());
1730         }
1731       }
1732     }
1733   }
1734 }
1735
1736 std::pair<bool, Node> TheoryEngine::entailmentCheck(theory::TheoryOfMode mode, TNode lit, const EntailmentCheckParameters* params, EntailmentCheckSideEffects* seffects) {
1737   TNode atom = (lit.getKind() == kind::NOT) ? lit[0] : lit;
1738   theory::TheoryId tid = theory::Theory::theoryOf(mode, atom);
1739   theory::Theory* th = theoryOf(tid);
1740
1741   Assert(th != NULL);
1742   Assert(params == NULL || tid == params->getTheoryId());
1743   Assert(seffects == NULL || tid == seffects->getTheoryId());
1744
1745   return th->entailmentCheck(lit, params, seffects);
1746 }
1747
1748 void TheoryEngine::spendResource() {
1749   d_resourceManager->spendResource();
1750 }