| #include "internal.hpp" | |
| namespace CaDiCaL { | |
| /*------------------------------------------------------------------------*/ | |
| // Covered clause elimination (CCE) is described in our short LPAR-10 paper | |
| // and later in more detail in our JAIR'15 article. Actually implement | |
| // the asymmetric version which adds asymmetric literals too but still call | |
| // it 'CCE' in the following (and not 'ACCE'). This implementation provides | |
| // a simplified and cleaner version of the one implemented before in | |
| // Lingeling. We still follow quite closely the original description in the | |
| // literature, which is based on asymmetric literal addition (ALA) and | |
| // covered literal addition (CLA). Both can be seen as kind of propagation, | |
| // where the literals in the original and then extended clause are assigned | |
| // to false, and the literals on the trail (actually we use our own 'added' | |
| // stack for that) make up the extended clause. The ALA steps can be | |
| // implemented by simple propagation (copied from 'propagate.cpp') using | |
| // watches, while the CLA steps need full occurrence lists to determine the | |
| // resolution candidate clauses. The CCE is successful if a conflict is | |
| // found during ALA steps or if during a CLA step all resolution candidates | |
| // of a literal on the trail are satisfied (the extended clause is blocked). | |
| struct Coveror { | |
| std::vector<int> added; // acts as trail | |
| std::vector<int> extend; // extension stack for witness | |
| std::vector<int> covered; // clause literals or added through CLA | |
| std::vector<int> intersection; // of literals in resolution candidates | |
| size_t alas, clas; // actual number of ALAs and CLAs | |
| struct { | |
| size_t added, covered; | |
| } next; // propagate next ... | |
| Coveror () : alas (0), clas (0) {} | |
| }; | |
| /*------------------------------------------------------------------------*/ | |
| // Push on the extension stack a clause made up of the given literal, the | |
| // original clause (initially copied to 'covered') and all the added covered | |
| // literals so far. The given literal will act as blocking literal for that | |
| // clause, if CCE is successful. Only in this case, this private extension | |
| // stack is copied to the actual extension stack of the solver. Note, that | |
| // even though all 'added' clauses correspond to the extended clause, we | |
| // only need to save the original and added covered literals. | |
| inline void Internal::cover_push_extension (int lit, Coveror &coveror) { | |
| coveror.extend.push_back (0); | |
| coveror.extend.push_back (lit); // blocking literal comes first | |
| bool found = false; | |
| for (const auto &other : coveror.covered) | |
| if (lit == other) | |
| assert (!found), found = true; | |
| else | |
| coveror.extend.push_back (other); | |
| assert (found); | |
| (void) found; | |
| } | |
| // Successful covered literal addition (CLA) step. | |
| inline void Internal::covered_literal_addition (int lit, Coveror &coveror) { | |
| MODE_REQUIRE (COVER); | |
| assert (level == 1); | |
| cover_push_extension (lit, coveror); | |
| for (const auto &other : coveror.intersection) { | |
| LOG ("covered literal addition %d", other); | |
| assert (!vals[other]), assert (!vals[-other]); | |
| set_val (other, -1); | |
| coveror.covered.push_back (other); | |
| coveror.added.push_back (other); | |
| coveror.clas++; | |
| } | |
| coveror.next.covered = 0; | |
| } | |
| // Successful asymmetric literal addition (ALA) step. | |
| inline void Internal::asymmetric_literal_addition (int lit, | |
| Coveror &coveror) { | |
| MODE_REQUIRE (COVER); | |
| assert (level == 1); | |
| LOG ("initial asymmetric literal addition %d", lit); | |
| assert (!vals[lit]), assert (!vals[-lit]); | |
| set_val (lit, -1); | |
| coveror.added.push_back (lit); | |
| coveror.alas++; | |
| coveror.next.covered = 0; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // In essence copied and adapted from 'propagate' in 'propagate.cpp'. Since | |
| // this function is also a hot-spot here in 'cover' we specialize it in the | |
| // same spirit as 'probe_propagate' and 'vivify_propagate'. Please refer to | |
| // the detailed comments for 'propagate' in 'propagate.cpp' for details. | |
| bool Internal::cover_propagate_asymmetric (int lit, Clause *ignore, | |
| Coveror &coveror) { | |
| MODE_REQUIRE (COVER); | |
| stats.propagations_cover++; | |
| stats.propagations++; | |
| assert (val (lit) < 0); | |
| bool subsumed = false; | |
| LOG ("asymmetric literal propagation of %d", lit); | |
| Watches &ws = watches (lit); | |
| const const_watch_iterator eow = ws.end (); | |
| watch_iterator j = ws.begin (); | |
| const_watch_iterator i = j; | |
| while (!subsumed && i != eow) { | |
| const Watch w = *j++ = *i++; | |
| if (w.clause == ignore) | |
| continue; // costly but necessary here ... | |
| const signed char b = val (w.blit); | |
| if (b > 0) | |
| continue; | |
| if (w.clause->garbage) | |
| j--; | |
| else if (w.binary ()) { | |
| if (b < 0) { | |
| LOG (w.clause, "found subsuming"); | |
| subsumed = true; | |
| } else | |
| asymmetric_literal_addition (-w.blit, coveror); | |
| } else { | |
| literal_iterator lits = w.clause->begin (); | |
| const int other = lits[0] ^ lits[1] ^ lit; | |
| lits[0] = other, lits[1] = lit; | |
| const signed char u = val (other); | |
| if (u > 0) | |
| j[-1].blit = other; | |
| else { | |
| const int size = w.clause->size; | |
| const const_literal_iterator end = lits + size; | |
| const literal_iterator middle = lits + w.clause->pos; | |
| literal_iterator k = middle; | |
| signed char v = -1; | |
| int r = 0; | |
| while (k != end && (v = val (r = *k)) < 0) | |
| k++; | |
| if (v < 0) { | |
| k = lits + 2; | |
| assert (w.clause->pos <= size); | |
| while (k != middle && (v = val (r = *k)) < 0) | |
| k++; | |
| } | |
| w.clause->pos = k - lits; | |
| assert (lits + 2 <= k), assert (k <= w.clause->end ()); | |
| if (v > 0) | |
| j[-1].blit = r; | |
| else if (!v) { | |
| LOG (w.clause, "unwatch %d in", lit); | |
| lits[1] = r; | |
| *k = lit; | |
| watch_literal (r, lit, w.clause); | |
| j--; | |
| } else if (!u) { | |
| assert (v < 0); | |
| asymmetric_literal_addition (-other, coveror); | |
| } else { | |
| assert (u < 0), assert (v < 0); | |
| LOG (w.clause, "found subsuming"); | |
| subsumed = true; | |
| break; | |
| } | |
| } | |
| } | |
| } | |
| if (j != i) { | |
| while (i != eow) | |
| *j++ = *i++; | |
| ws.resize (j - ws.begin ()); | |
| } | |
| return subsumed; | |
| } | |
| // Covered literal addition (which needs full occurrence lists). The | |
| // function returns 'true' if the extended clause is blocked on 'lit.' | |
| bool Internal::cover_propagate_covered (int lit, Coveror &coveror) { | |
| MODE_REQUIRE (COVER); | |
| assert (val (lit) < 0); | |
| if (frozen (lit)) { | |
| LOG ("no covered propagation on frozen literal %d", lit); | |
| return false; | |
| } | |
| stats.propagations_cover++; | |
| stats.propagations++; | |
| LOG ("covered propagation of %d", lit); | |
| assert (coveror.intersection.empty ()); | |
| Occs &os = occs (-lit); | |
| const auto end = os.end (); | |
| bool first = true; | |
| // Compute the intersection of the literals in all the clauses with | |
| // '-lit'. If all these clauses are double satisfied then we know that | |
| // the extended clauses (in 'added') is blocked. All literals in the | |
| // intersection can be added as covered literal. As soon the intersection | |
| // becomes empty (during traversal of clauses with '-lit') we abort. | |
| for (auto i = os.begin (); i != end; i++) { | |
| Clause *c = *i; | |
| if (c->garbage) | |
| continue; | |
| // First check whether clause is 'blocked', i.e., is double satisfied. | |
| bool blocked = false; | |
| for (const auto &other : *c) { | |
| if (other == -lit) | |
| continue; | |
| const signed char tmp = val (other); | |
| if (tmp < 0) | |
| continue; | |
| if (tmp > 0) { | |
| blocked = true; | |
| break; | |
| } | |
| } | |
| if (blocked) { // ... if 'c' is double satisfied. | |
| LOG (c, "blocked"); | |
| continue; // with next clause with '-lit'. | |
| } | |
| if (first) { | |
| // Copy and mark literals of first clause. | |
| for (const auto &other : *c) { | |
| if (other == -lit) | |
| continue; | |
| const signed char tmp = val (other); | |
| if (tmp < 0) | |
| continue; | |
| assert (!tmp); | |
| coveror.intersection.push_back (other); | |
| mark (other); | |
| } | |
| first = false; | |
| } else { | |
| // Unmark all literals in current clause. | |
| for (const auto &other : *c) { | |
| if (other == -lit) | |
| continue; | |
| signed char tmp = val (other); | |
| if (tmp < 0) | |
| continue; | |
| assert (!tmp); | |
| tmp = marked (other); | |
| if (tmp > 0) | |
| unmark (other); | |
| } | |
| // Then remove from intersection all marked literals. | |
| const auto end = coveror.intersection.end (); | |
| auto j = coveror.intersection.begin (); | |
| for (auto k = j; k != end; k++) { | |
| const int other = *j++ = *k; | |
| const int tmp = marked (other); | |
| assert (tmp >= 0); | |
| if (tmp) | |
| j--, unmark (other); // remove marked and unmark it | |
| else | |
| mark (other); // keep unmarked and mark it | |
| } | |
| const size_t new_size = j - coveror.intersection.begin (); | |
| coveror.intersection.resize (new_size); | |
| if (!coveror.intersection.empty ()) | |
| continue; | |
| // No covered literal addition candidates in the intersection left! | |
| // Move this clause triggering early abort to the beginning. | |
| // This is a common move to front strategy to minimize effort. | |
| auto begin = os.begin (); | |
| while (i != begin) { | |
| auto prev = i - 1; | |
| *i = *prev; | |
| i = prev; | |
| } | |
| *begin = c; | |
| break; // early abort ... | |
| } | |
| } | |
| bool res = false; | |
| if (first) { | |
| LOG ("all resolution candidates with %d blocked", -lit); | |
| assert (coveror.intersection.empty ()); | |
| cover_push_extension (lit, coveror); | |
| res = true; | |
| } else if (coveror.intersection.empty ()) { | |
| LOG ("empty intersection of resolution candidate literals"); | |
| } else { | |
| LOG (coveror.intersection, | |
| "non-empty intersection of resolution candidate literals"); | |
| covered_literal_addition (lit, coveror); | |
| unmark (coveror.intersection); | |
| coveror.intersection.clear (); | |
| coveror.next.covered = 0; // Restart covering. | |
| } | |
| unmark (coveror.intersection); | |
| coveror.intersection.clear (); | |
| return res; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| bool Internal::cover_clause (Clause *c, Coveror &coveror) { | |
| MODE_REQUIRE (COVER); | |
| assert (!c->garbage); | |
| LOG (c, "trying covered clauses elimination on"); | |
| bool satisfied = false; | |
| for (const auto &lit : *c) | |
| if (val (lit) > 0) | |
| satisfied = true; | |
| if (satisfied) { | |
| LOG (c, "clause already satisfied"); | |
| mark_garbage (c); | |
| return false; | |
| } | |
| assert (coveror.added.empty ()); | |
| assert (coveror.extend.empty ()); | |
| assert (coveror.covered.empty ()); | |
| assert (!level); | |
| level = 1; | |
| LOG ("assuming literals of candidate clause"); | |
| for (const auto &lit : *c) { | |
| if (val (lit)) | |
| continue; | |
| asymmetric_literal_addition (lit, coveror); | |
| coveror.covered.push_back (lit); | |
| } | |
| bool tautological = false; | |
| coveror.next.added = coveror.next.covered = 0; | |
| while (!tautological) { | |
| if (coveror.next.added < coveror.added.size ()) { | |
| const int lit = coveror.added[coveror.next.added++]; | |
| tautological = cover_propagate_asymmetric (lit, c, coveror); | |
| } else if (coveror.next.covered < coveror.covered.size ()) { | |
| const int lit = coveror.covered[coveror.next.covered++]; | |
| tautological = cover_propagate_covered (lit, coveror); | |
| } else | |
| break; | |
| } | |
| if (tautological) { | |
| if (coveror.extend.empty ()) { | |
| stats.cover_asymmetric++; | |
| stats.cover_total++; | |
| LOG (c, "asymmetric tautological"); | |
| } else { | |
| stats.cover_blocked++; | |
| stats.cover_total++; | |
| // Only copy extension stack if successful. | |
| int prev = INT_MIN; | |
| bool already_pushed = false; | |
| int64_t last_id = 0; | |
| LOG (c, "covered tautological"); | |
| assert (clause.empty ()); | |
| LOG (coveror.extend, "extension = "); | |
| std::vector<int> weakened_clause; | |
| int witness = 0; | |
| int64_t weakened_id = 0; | |
| for (const auto &other : coveror.extend) { | |
| if (!prev) { | |
| // are we finishing a clause? | |
| if (already_pushed) { | |
| // add missing literals that are not needed for covering | |
| // but avoid RAT proofs | |
| for (auto i = 0, j = 0; i < c->size; ++i, ++j) { | |
| const int lit = c->literals[i]; | |
| if (j >= (int) coveror.covered.size () || | |
| c->literals[i] != coveror.covered[j]) { | |
| --j; | |
| LOG ("adding lit %d not needed for ATA", lit); | |
| clause.push_back (lit); | |
| weakened_clause.push_back (lit); | |
| } | |
| } | |
| } | |
| if (proof && already_pushed) { | |
| if (lrat) | |
| lrat_chain.push_back (c->id); | |
| LOG ("LEARNING clause with id %" PRId64, last_id); | |
| proof->add_derived_clause (last_id, false, clause, lrat_chain); | |
| proof->weaken_plus (last_id, clause); | |
| lrat_chain.clear (); | |
| } | |
| last_id = ++clause_id; | |
| if (already_pushed) | |
| external->push_clause_on_extension (weakened_id, witness, | |
| weakened_clause); | |
| assert (other); | |
| witness = other; | |
| weakened_clause.clear (); | |
| weakened_id = last_id; | |
| clause.clear (); | |
| already_pushed = true; | |
| } | |
| if (other) { | |
| weakened_clause.push_back (other); | |
| clause.push_back (other); | |
| LOG (clause, "current clause is"); | |
| } | |
| prev = other; | |
| } | |
| if (proof) { | |
| // add missing literals that are not needed for covering | |
| // but avoid RAT proofs | |
| for (auto i = 0, j = 0; i < c->size; ++i, ++j) { | |
| const int lit = c->literals[i]; | |
| if (j >= (int) coveror.covered.size () || | |
| c->literals[i] != coveror.covered[j]) { | |
| --j; | |
| LOG ("adding lit %d not needed for ATA", lit); | |
| clause.push_back (lit); | |
| weakened_clause.push_back (lit); | |
| } | |
| } | |
| if (lrat) | |
| lrat_chain.push_back (c->id); | |
| proof->add_derived_clause (last_id, false, clause, lrat_chain); | |
| proof->weaken_plus (last_id, clause); | |
| lrat_chain.clear (); | |
| } | |
| clause.clear (); | |
| external->push_clause_on_extension (weakened_id, witness, | |
| weakened_clause); | |
| mark_garbage (c); | |
| } | |
| } | |
| // Backtrack and 'unassign' all literals. | |
| assert (level == 1); | |
| for (const auto &lit : coveror.added) | |
| set_val (lit, 0); | |
| level = 0; | |
| coveror.covered.clear (); | |
| coveror.extend.clear (); | |
| coveror.added.clear (); | |
| return tautological; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Not yet tried and larger clauses are tried first. | |
| struct clause_covered_or_smaller { | |
| bool operator() (const Clause *a, const Clause *b) { | |
| if (a->covered && !b->covered) | |
| return true; | |
| if (!a->covered && b->covered) | |
| return false; | |
| return a->size < b->size; | |
| } | |
| }; | |
| int64_t Internal::cover_round () { | |
| if (unsat) | |
| return 0; | |
| init_watches (); | |
| connect_watches (true); // irredundant watches only is enough | |
| int64_t delta = stats.propagations_search; | |
| delta *= 1e-3 * opts.covereffort; | |
| if (delta < opts.covermineff) | |
| delta = opts.covermineff; | |
| if (delta > opts.covermaxeff) | |
| delta = opts.covermaxeff; | |
| delta = max (delta, ((int64_t) 2) * active ()); | |
| PHASE ("cover", stats.coverings, | |
| "covered clause elimination limit of %" PRId64 " propagations", | |
| delta); | |
| int64_t limit = stats.propagations_cover + delta; | |
| init_occs (); | |
| vector<Clause *> schedule; | |
| Coveror coveror; | |
| // First connect all clauses and find all not yet tried clauses. | |
| // | |
| #ifndef QUIET | |
| int64_t untried = 0; | |
| #endif | |
| // | |
| for (auto c : clauses) { | |
| assert (!c->frozen); | |
| if (c->garbage) | |
| continue; | |
| if (c->redundant) | |
| continue; | |
| bool satisfied = false, allfrozen = true; | |
| for (const auto &lit : *c) | |
| if (val (lit) > 0) { | |
| satisfied = true; | |
| break; | |
| } else if (allfrozen && !frozen (lit)) | |
| allfrozen = false; | |
| if (satisfied) { | |
| mark_garbage (c); | |
| continue; | |
| } | |
| if (allfrozen) { | |
| c->frozen = true; | |
| continue; | |
| } | |
| for (const auto &lit : *c) | |
| occs (lit).push_back (c); | |
| if (c->size < opts.coverminclslim) | |
| continue; | |
| if (c->size > opts.covermaxclslim) | |
| continue; | |
| if (c->covered) | |
| continue; | |
| schedule.push_back (c); | |
| #ifndef QUIET | |
| untried++; | |
| #endif | |
| } | |
| if (schedule.empty ()) { | |
| PHASE ("cover", stats.coverings, "no previously untried clause left"); | |
| for (auto c : clauses) { | |
| if (c->garbage) | |
| continue; | |
| if (c->redundant) | |
| continue; | |
| if (c->frozen) { | |
| c->frozen = false; | |
| continue; | |
| } | |
| if (c->size < opts.coverminclslim) | |
| continue; | |
| if (c->size > opts.covermaxclslim) | |
| continue; | |
| assert (c->covered); | |
| c->covered = false; | |
| schedule.push_back (c); | |
| } | |
| } else { // Mix of tried and not tried clauses .... | |
| for (auto c : clauses) { | |
| if (c->garbage) | |
| continue; | |
| if (c->redundant) | |
| continue; | |
| if (c->frozen) { | |
| c->frozen = false; | |
| continue; | |
| } | |
| if (c->size < opts.coverminclslim) | |
| continue; | |
| if (c->size > opts.covermaxclslim) | |
| continue; | |
| if (!c->covered) | |
| continue; | |
| schedule.push_back (c); | |
| } | |
| } | |
| stable_sort (schedule.begin (), schedule.end (), | |
| clause_covered_or_smaller ()); | |
| #ifndef QUIET | |
| const size_t scheduled = schedule.size (); | |
| PHASE ("cover", stats.coverings, | |
| "scheduled %zd clauses %.0f%% with %" PRId64 " untried %.0f%%", | |
| scheduled, percent (scheduled, stats.clauses_now_irr), untried, | |
| percent (untried, scheduled)); | |
| #endif | |
| // Heuristically it should be beneficial to intersect with smaller clauses | |
| // first, since then the chances are higher that the intersection of | |
| // resolution candidates becomes emptier earlier. | |
| for (auto lit : lits) { | |
| if (!active (lit)) | |
| continue; | |
| Occs &os = occs (lit); | |
| stable_sort (os.begin (), os.end (), clause_smaller_size ()); | |
| } | |
| // This is the main loop of trying to do CCE of candidate clauses. | |
| // | |
| int64_t covered = 0; | |
| // | |
| while (!terminated_asynchronously () && !schedule.empty () && | |
| stats.propagations_cover < limit) { | |
| Clause *c = schedule.back (); | |
| schedule.pop_back (); | |
| c->covered = true; | |
| if (cover_clause (c, coveror)) | |
| covered++; | |
| } | |
| #ifndef QUIET | |
| const size_t remain = schedule.size (); | |
| const size_t tried = scheduled - remain; | |
| PHASE ("cover", stats.coverings, | |
| "eliminated %" PRId64 " covered clauses out of %zd tried %.0f%%", | |
| covered, tried, percent (covered, tried)); | |
| if (remain) | |
| PHASE ("cover", stats.coverings, "remaining %zu clauses %.0f%% untried", | |
| remain, percent (remain, scheduled)); | |
| else | |
| PHASE ("cover", stats.coverings, "all scheduled clauses tried"); | |
| #endif | |
| reset_occs (); | |
| reset_watches (); | |
| return covered; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| bool Internal::cover () { | |
| if (!opts.cover) | |
| return false; | |
| if (unsat) | |
| return false; | |
| if (terminated_asynchronously ()) | |
| return false; | |
| if (!stats.clauses_now_irr) | |
| return false; | |
| // TODO: Our current algorithm for producing the necessary clauses on the | |
| // reconstruction stack for extending the witness requires a covered | |
| // literal addition step which (empirically) conflicts with flushing | |
| // during restoring clauses (see 'regr00{48,51}.trace') even though | |
| // flushing during restore is disabled by default (as is covered clause | |
| // elimination). The consequence of combining these two options | |
| // ('opts.cover' and 'opts.restoreflush') can thus produce incorrect | |
| // witness reconstruction and thus invalid witnesses. This is quite | |
| // infrequent (one out of half billion mobical test cases) but as the two | |
| // regression traces show, does happen. Thus we disable the combination. | |
| // | |
| // if (opts.restoreflush) | |
| // return false; | |
| MODE_SCOPE_SIMPLIFY (COVER); | |
| PROFILE_SCOPE_SIMPLIFY (cover); | |
| stats.coverings++; | |
| // During variable elimination unit clauses can be generated which need to | |
| // be propagated properly over redundant clauses too. Since variable | |
| // elimination avoids to have occurrence lists and watches at the same | |
| // time this propagation is delayed until the end of variable elimination. | |
| // Since we want to interleave CCE with it, we have to propagate here. | |
| // Otherwise this triggers inconsistencies. | |
| // | |
| if (propagated < trail.size ()) { | |
| init_watches (); | |
| connect_watches (); // need to propagated over all clauses! | |
| LOG ("elimination produced %zd units", | |
| (size_t) (trail.size () - propagated)); | |
| if (!propagate ()) { | |
| LOG ("propagating units before covered clause elimination " | |
| "results in empty clause"); | |
| learn_empty_clause (); | |
| assert (unsat); | |
| } | |
| reset_watches (); | |
| } | |
| assert (unsat || propagated == trail.size ()); | |
| int64_t covered = cover_round (); | |
| report ('K', !opts.reportall && !covered); | |
| return covered; | |
| } | |
| } // namespace CaDiCaL |