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