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