src/theory/bv/bv_subtheory_core.cpp

   1 /*********************                                                        */
   2 /*! \file bv_subtheory_core.cpp
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Liana Hadarean, Aina Niemetz, Andrew Reynolds
   6  ** This file is part of the CVC4 project.
   7  ** Copyright (c) 2009-2019 by the authors listed in the file AUTHORS
   8  ** in the top-level source directory) and their institutional affiliations.
   9  ** All rights reserved.  See the file COPYING in the top-level source
  10  ** directory for licensing information.\endverbatim
  11  **
  12  ** \brief Algebraic solver.
  13  **
  14  ** Algebraic solver.
  15  **/
  16
  17 #include "theory/bv/bv_subtheory_core.h"
  18
  19 #include "options/bv_options.h"
  20 #include "options/smt_options.h"
  21 #include "smt/smt_statistics_registry.h"
  22 #include "theory/bv/slicer.h"
  23 #include "theory/bv/theory_bv.h"
  24 #include "theory/bv/theory_bv_utils.h"
  25 #include "theory/ext_theory.h"
  26 #include "theory/theory_model.h"
  27
  28 using namespace std;
  29 using namespace CVC4;
  30 using namespace CVC4::context;
  31 using namespace CVC4::theory;
  32 using namespace CVC4::theory::bv;
  33 using namespace CVC4::theory::bv::utils;
  34
  35 CoreSolver::CoreSolver(context::Context* c, TheoryBV* bv)
  36   : SubtheorySolver(c, bv),
  37     d_notify(*this),
  38     d_equalityEngine(d_notify, c, "theory::bv::ee", true),
  39     d_slicer(new Slicer()),
  40     d_isComplete(c, true),
  41     d_lemmaThreshold(16),
  42     d_useSlicer(false),
  43     d_preregisterCalled(false),
  44     d_checkCalled(false),
  45     d_reasons(c)
  46 {
  47   // The kinds we are treating as function application in congruence
  48   d_equalityEngine.addFunctionKind(kind::BITVECTOR_CONCAT, true);
  49   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_AND);
  50   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_OR);
  51   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_XOR);
  52   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_NOT);
  53   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_NAND);
  54   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_NOR);
  55   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_XNOR);
  56   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_COMP);
  57   d_equalityEngine.addFunctionKind(kind::BITVECTOR_MULT, true);
  58   d_equalityEngine.addFunctionKind(kind::BITVECTOR_PLUS, true);
  59   d_equalityEngine.addFunctionKind(kind::BITVECTOR_EXTRACT, true);
  60   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SUB);
  61   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_NEG);
  62   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_UDIV);
  63   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_UREM);
  64   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SDIV);
  65   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SREM);
  66   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SMOD);
  67   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SHL);
  68   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_LSHR);
  69   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_ASHR);
  70   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_ULT);
  71   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_ULE);
  72   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_UGT);
  73   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_UGE);
  74   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SLT);
  75   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SLE);
  76   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SGT);
  77   //    d_equalityEngine.addFunctionKind(kind::BITVECTOR_SGE);
  78   d_equalityEngine.addFunctionKind(kind::BITVECTOR_TO_NAT);
  79   d_equalityEngine.addFunctionKind(kind::INT_TO_BITVECTOR);
  80 }
  81
  82 CoreSolver::~CoreSolver() {}
  83
  84 void CoreSolver::setMasterEqualityEngine(eq::EqualityEngine* eq) {
  85   d_equalityEngine.setMasterEqualityEngine(eq);
  86 }
  87
  88 void CoreSolver::enableSlicer() {
  89   AlwaysAssert (!d_preregisterCalled);
  90   d_useSlicer = true;
  91   d_statistics.d_slicerEnabled.setData(true);
  92 }
  93
  94 void CoreSolver::preRegister(TNode node) {
  95   d_preregisterCalled = true;
  96   if (node.getKind() == kind::EQUAL) {
  97       d_equalityEngine.addTriggerEquality(node);
  98       if (d_useSlicer) {
  99         d_slicer->processEquality(node);
 100         AlwaysAssert(!d_checkCalled);
 101       }
 102   } else {
 103     d_equalityEngine.addTerm(node);
 104   }
 105 }
 106
 107
 108 void CoreSolver::explain(TNode literal, std::vector<TNode>& assumptions) {
 109   bool polarity = literal.getKind() != kind::NOT;
 110   TNode atom = polarity ? literal : literal[0];
 111   if (atom.getKind() == kind::EQUAL) {
 112     d_equalityEngine.explainEquality(atom[0], atom[1], polarity, assumptions);
 113   } else {
 114     d_equalityEngine.explainPredicate(atom, polarity, assumptions);
 115   }
 116 }
 117
 118 Node CoreSolver::getBaseDecomposition(TNode a) {
 119   std::vector<Node> a_decomp;
 120   d_slicer->getBaseDecomposition(a, a_decomp);
 121   Node new_a = utils::mkConcat(a_decomp);
 122   Debug("bv-slicer") << "CoreSolver::getBaseDecomposition " << a <<" => " << new_a << "\n";
 123   return new_a;
 124 }
 125
 126 bool CoreSolver::decomposeFact(TNode fact) {
 127   Debug("bv-slicer") << "CoreSolver::decomposeFact fact=" << fact << endl;
 128   // FIXME: are this the right things to assert?
 129   // assert decompositions since the equality engine does not know the semantics of
 130   // concat:
 131   //   a == a_1 concat ... concat a_k
 132   //   b == b_1 concat ... concat b_k
 133   TNode eq = fact.getKind() == kind::NOT? fact[0] : fact;
 134
 135   TNode a = eq[0];
 136   TNode b = eq[1];
 137   Node new_a = getBaseDecomposition(a);
 138   Node new_b = getBaseDecomposition(b);
 139
 140   Assert (utils::getSize(new_a) == utils::getSize(new_b) &&
 141           utils::getSize(new_a) == utils::getSize(a));
 142
 143   NodeManager* nm = NodeManager::currentNM();
 144   Node a_eq_new_a = nm->mkNode(kind::EQUAL, a, new_a);
 145   Node b_eq_new_b = nm->mkNode(kind::EQUAL, b, new_b);
 146
 147   bool ok = true;
 148   ok = assertFactToEqualityEngine(a_eq_new_a, utils::mkTrue());
 149   if (!ok) return false;
 150   ok = assertFactToEqualityEngine(b_eq_new_b, utils::mkTrue());
 151   if (!ok) return false;
 152   ok = assertFactToEqualityEngine(fact, fact);
 153   if (!ok) return false;
 154
 155   if (fact.getKind() == kind::EQUAL) {
 156     // assert the individual equalities as well
 157     //    a_i == b_i
 158     if (new_a.getKind() == kind::BITVECTOR_CONCAT &&
 159         new_b.getKind() == kind::BITVECTOR_CONCAT) {
 160
 161       Assert (new_a.getNumChildren() == new_b.getNumChildren());
 162       for (unsigned i = 0; i < new_a.getNumChildren(); ++i) {
 163         Node eq_i = nm->mkNode(kind::EQUAL, new_a[i], new_b[i]);
 164         ok = assertFactToEqualityEngine(eq_i, fact);
 165         if (!ok) return false;
 166       }
 167     }
 168   }
 169   return true;
 170 }
 171
 172 bool CoreSolver::check(Theory::Effort e) {
 173   Trace("bitvector::core") << "CoreSolver::check \n";
 174
 175   d_bv->spendResource(options::theoryCheckStep());
 176
 177   d_checkCalled = true;
 178   Assert (!d_bv->inConflict());
 179   ++(d_statistics.d_numCallstoCheck);
 180   bool ok = true;
 181   std::vector<Node> core_eqs;
 182   TNodeBoolMap seen;
 183   // slicer does not deal with cardinality constraints yet
 184   if (d_useSlicer) {
 185     d_isComplete = false;
 186   }
 187   while (! done()) {
 188     TNode fact = get();
 189     if (d_isComplete && !isCompleteForTerm(fact, seen)) {
 190       d_isComplete = false;
 191     }
 192
 193     // only reason about equalities
 194     if (fact.getKind() == kind::EQUAL || (fact.getKind() == kind::NOT && fact[0].getKind() == kind::EQUAL)) {
 195       if (d_useSlicer) {
 196         ok = decomposeFact(fact);
 197       } else {
 198         ok = assertFactToEqualityEngine(fact, fact);
 199       }
 200     } else {
 201       ok = assertFactToEqualityEngine(fact, fact);
 202     }
 203     if (!ok)
 204       return false;
 205   }
 206
 207   if (Theory::fullEffort(e) && isComplete()) {
 208     buildModel();
 209   }
 210
 211   return true;
 212 }
 213
 214 void CoreSolver::buildModel()
 215 {
 216   Debug("bv-core") << "CoreSolver::buildModel() \n";
 217   NodeManager* nm = NodeManager::currentNM();
 218   d_modelValues.clear();
 219   TNodeSet constants;
 220   TNodeSet constants_in_eq_engine;
 221   // collect constants in equality engine
 222   eq::EqClassesIterator eqcs_i = eq::EqClassesIterator(&d_equalityEngine);
 223   while (!eqcs_i.isFinished())
 224   {
 225     TNode repr = *eqcs_i;
 226     if (repr.getKind() == kind::CONST_BITVECTOR)
 227     {
 228       // must check if it's just the constant
 229       eq::EqClassIterator it(repr, &d_equalityEngine);
 230       if (!(++it).isFinished() || true)
 231       {
 232         constants.insert(repr);
 233         constants_in_eq_engine.insert(repr);
 234       }
 235     }
 236     ++eqcs_i;
 237   }
 238
 239   // build repr to value map
 240
 241   eqcs_i = eq::EqClassesIterator(&d_equalityEngine);
 242   while (!eqcs_i.isFinished())
 243   {
 244     TNode repr = *eqcs_i;
 245     ++eqcs_i;
 246
 247     if (!repr.isVar() && repr.getKind() != kind::CONST_BITVECTOR
 248         && !d_bv->isSharedTerm(repr))
 249     {
 250       continue;
 251     }
 252
 253     TypeNode type = repr.getType();
 254     if (type.isBitVector() && repr.getKind() != kind::CONST_BITVECTOR)
 255     {
 256       Debug("bv-core-model") << "   processing " << repr << "\n";
 257       // we need to assign a value for it
 258       TypeEnumerator te(type);
 259       Node val;
 260       do
 261       {
 262         val = *te;
 263         ++te;
 264         // Debug("bv-core-model") << "  trying value " << val << "\n";
 265         // Debug("bv-core-model") << "  is in set? " << constants.count(val) <<
 266         // "\n"; Debug("bv-core-model") << "  enumerator done? " <<
 267         // te.isFinished() << "\n";
 268       } while (constants.count(val) != 0 && !(te.isFinished()));
 269
 270       if (te.isFinished() && constants.count(val) != 0)
 271       {
 272         // if we cannot enumerate anymore values we just return the lemma
 273         // stating that at least two of the representatives are equal.
 274         std::vector<TNode> representatives;
 275         representatives.push_back(repr);
 276
 277         for (TNodeSet::const_iterator it = constants_in_eq_engine.begin();
 278              it != constants_in_eq_engine.end();
 279              ++it)
 280         {
 281           TNode constant = *it;
 282           if (utils::getSize(constant) == utils::getSize(repr))
 283           {
 284             representatives.push_back(constant);
 285           }
 286         }
 287         for (ModelValue::const_iterator it = d_modelValues.begin();
 288              it != d_modelValues.end();
 289              ++it)
 290         {
 291           representatives.push_back(it->first);
 292         }
 293         std::vector<Node> equalities;
 294         for (unsigned i = 0; i < representatives.size(); ++i)
 295         {
 296           for (unsigned j = i + 1; j < representatives.size(); ++j)
 297           {
 298             TNode a = representatives[i];
 299             TNode b = representatives[j];
 300             if (a.getKind() == kind::CONST_BITVECTOR
 301                 && b.getKind() == kind::CONST_BITVECTOR)
 302             {
 303               Assert(a != b);
 304               continue;
 305             }
 306             if (utils::getSize(a) == utils::getSize(b))
 307             {
 308               equalities.push_back(nm->mkNode(kind::EQUAL, a, b));
 309             }
 310           }
 311         }
 312         // better off letting the SAT solver split on values
 313         if (equalities.size() > d_lemmaThreshold)
 314         {
 315           d_isComplete = false;
 316           return;
 317         }
 318
 319         if (equalities.size() == 0)
 320         {
 321           Debug("bv-core") << "  lemma: true (no equalities)" << std::endl;
 322         }
 323         else
 324         {
 325           Node lemma = utils::mkOr(equalities);
 326           d_bv->lemma(lemma);
 327           Debug("bv-core") << "  lemma: " << lemma << std::endl;
 328         }
 329         return;
 330       }
 331
 332       Debug("bv-core-model") << "   " << repr << " => " << val << "\n";
 333       constants.insert(val);
 334       d_modelValues[repr] = val;
 335     }
 336   }
 337 }
 338
 339 bool CoreSolver::assertFactToEqualityEngine(TNode fact, TNode reason) {
 340   // Notify the equality engine
 341   if (!d_bv->inConflict() && (!d_bv->wasPropagatedBySubtheory(fact) || d_bv->getPropagatingSubtheory(fact) != SUB_CORE)) {
 342     Debug("bv-slicer-eq") << "CoreSolver::assertFactToEqualityEngine fact=" << fact << endl;
 343     // Debug("bv-slicer-eq") << "                     reason=" << reason << endl;
 344     bool negated = fact.getKind() == kind::NOT;
 345     TNode predicate = negated ? fact[0] : fact;
 346     if (predicate.getKind() == kind::EQUAL) {
 347       if (negated) {
 348         // dis-equality
 349         d_equalityEngine.assertEquality(predicate, false, reason);
 350       } else {
 351         // equality
 352         d_equalityEngine.assertEquality(predicate, true, reason);
 353       }
 354     } else {
 355       // Adding predicate if the congruence over it is turned on
 356       if (d_equalityEngine.isFunctionKind(predicate.getKind())) {
 357         d_equalityEngine.assertPredicate(predicate, !negated, reason);
 358       }
 359     }
 360   }
 361
 362   // checking for a conflict
 363   if (d_bv->inConflict()) {
 364     return false;
 365   }
 366   return true;
 367 }
 368
 369 bool CoreSolver::NotifyClass::eqNotifyTriggerEquality(TNode equality, bool value) {
 370   Debug("bitvector::core") << "NotifyClass::eqNotifyTriggerEquality(" << equality << ", " << (value ? "true" : "false" )<< ")" << std::endl;
 371   if (value) {
 372     return d_solver.storePropagation(equality);
 373   } else {
 374     return d_solver.storePropagation(equality.notNode());
 375   }
 376 }
 377
 378 bool CoreSolver::NotifyClass::eqNotifyTriggerPredicate(TNode predicate, bool value) {
 379   Debug("bitvector::core") << "NotifyClass::eqNotifyTriggerPredicate(" << predicate << ", " << (value ? "true" : "false" ) << ")" << std::endl;
 380   if (value) {
 381     return d_solver.storePropagation(predicate);
 382   } else {
 383     return d_solver.storePropagation(predicate.notNode());
 384   }
 385 }
 386
 387 bool CoreSolver::NotifyClass::eqNotifyTriggerTermEquality(TheoryId tag, TNode t1, TNode t2, bool value) {
 388   Debug("bitvector::core") << "NotifyClass::eqNotifyTriggerTermMerge(" << t1 << ", " << t2 << ")" << std::endl;
 389   if (value) {
 390     return d_solver.storePropagation(t1.eqNode(t2));
 391   } else {
 392     return d_solver.storePropagation(t1.eqNode(t2).notNode());
 393   }
 394 }
 395
 396 void CoreSolver::NotifyClass::eqNotifyConstantTermMerge(TNode t1, TNode t2) {
 397   d_solver.conflict(t1, t2);
 398 }
 399
 400 void CoreSolver::NotifyClass::eqNotifyNewClass(TNode t) {
 401   d_solver.eqNotifyNewClass( t );
 402 }
 403
 404 bool CoreSolver::storePropagation(TNode literal) {
 405   return d_bv->storePropagation(literal, SUB_CORE);
 406 }
 407
 408 void CoreSolver::conflict(TNode a, TNode b) {
 409   std::vector<TNode> assumptions;
 410   d_equalityEngine.explainEquality(a, b, true, assumptions);
 411   Node conflict = flattenAnd(assumptions);
 412   d_bv->setConflict(conflict);
 413 }
 414
 415 void CoreSolver::eqNotifyNewClass(TNode t) {
 416   Assert( d_bv->getExtTheory()!=NULL );
 417   d_bv->getExtTheory()->registerTerm( t );
 418 }
 419
 420 bool CoreSolver::isCompleteForTerm(TNode term, TNodeBoolMap& seen) {
 421   if (d_useSlicer)
 422     return utils::isCoreTerm(term, seen);
 423
 424   return utils::isEqualityTerm(term, seen);
 425 }
 426
 427 bool CoreSolver::collectModelInfo(TheoryModel* m, bool fullModel)
 428 {
 429   if (d_useSlicer) {
 430     Unreachable();
 431   }
 432   if (Debug.isOn("bitvector-model")) {
 433     context::CDQueue<Node>::const_iterator it = d_assertionQueue.begin();
 434     for (; it!= d_assertionQueue.end(); ++it) {
 435       Debug("bitvector-model") << "CoreSolver::collectModelInfo (assert "
 436                                << *it << ")\n";
 437     }
 438   }
 439   set<Node> termSet;
 440   d_bv->computeRelevantTerms(termSet);
 441   if (!m->assertEqualityEngine(&d_equalityEngine, &termSet))
 442   {
 443     return false;
 444   }
 445   if (isComplete()) {
 446     Debug("bitvector-model") << "CoreSolver::collectModelInfo complete.";
 447     for (ModelValue::const_iterator it = d_modelValues.begin(); it != d_modelValues.end(); ++it) {
 448       Node a = it->first;
 449       Node b = it->second;
 450       Debug("bitvector-model") << "CoreSolver::collectModelInfo modelValues "
 451                                << a << " => " << b <<")\n";
 452       if (!m->assertEquality(a, b, true))
 453       {
 454         return false;
 455       }
 456     }
 457   }
 458   return true;
 459 }
 460
 461 Node CoreSolver::getModelValue(TNode var) {
 462   Debug("bitvector-model") << "CoreSolver::getModelValue (" << var <<")";
 463   Assert (isComplete());
 464   TNode repr = d_equalityEngine.getRepresentative(var);
 465   Node result = Node();
 466   if (repr.getKind() == kind::CONST_BITVECTOR) {
 467     result = repr;
 468   } else if (d_modelValues.find(repr) == d_modelValues.end()) {
 469     // it may be a shared term that never gets asserted
 470     // result is just Null
 471     Assert(d_bv->isSharedTerm(var));
 472   } else {
 473     result = d_modelValues[repr];
 474   }
 475   Debug("bitvector-model") << " => " << result <<"\n";
 476   return result;
 477 }
 478
 479 CoreSolver::Statistics::Statistics()
 480   : d_numCallstoCheck("theory::bv::CoreSolver::NumCallsToCheck", 0)
 481   , d_slicerEnabled("theory::bv::CoreSolver::SlicerEnabled", false)
 482 {
 483   smtStatisticsRegistry()->registerStat(&d_numCallstoCheck);
 484   smtStatisticsRegistry()->registerStat(&d_slicerEnabled);
 485 }
 486 CoreSolver::Statistics::~Statistics() {
 487   smtStatisticsRegistry()->unregisterStat(&d_numCallstoCheck);
 488   smtStatisticsRegistry()->unregisterStat(&d_slicerEnabled);
 489 }