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