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