| #include "internal.hpp" | |
| #include "options.hpp" | |
| namespace CaDiCaL { | |
| // Failed literal handling as pioneered by MiniSAT. This first function | |
| // adds an assumption literal onto the assumption stack. | |
| void Internal::assume (int lit) { | |
| if (level && !opts.ilb) | |
| backtrack (); | |
| else if (val (lit) < 0) | |
| backtrack_without_updating_phases (max (0, var (lit).level - 1)); | |
| Flags &f = flags (lit); | |
| const unsigned char bit = bign (lit); | |
| if (f.assumed & bit) { | |
| LOG ("ignoring already assumed %d", lit); | |
| return; | |
| } | |
| LOG ("assume %d", lit); | |
| f.assumed |= bit; | |
| assumptions.push_back (lit); | |
| freeze (lit); | |
| } | |
| // for LRAT we actually need to implement recursive DFS | |
| // for non-lrat use BFS. The DFS uses an explicit stack, since implication | |
| // chains can be long enough to overflow the call stack. | |
| // | |
| void Internal::assume_analyze_literal (int lit) { | |
| // Visits a literal before the literals of its reason and returns the | |
| // reason if it still has to be analyzed. | |
| const auto visit = [this] (int lit) -> Clause * { | |
| assert (lit); | |
| Flags &f = flags (lit); | |
| if (f.seen) | |
| return 0; | |
| f.seen = true; | |
| analyzed.push_back (lit); | |
| Var &v = var (lit); | |
| assert (val (lit) < 0); | |
| if (v.reason == external_reason) { | |
| v.reason = learn_external_reason_clause (-lit, 0, true); | |
| assert (v.reason || !v.level); | |
| } | |
| assert (v.reason != external_reason); | |
| if (!v.level) { | |
| int64_t id = unit_id (-lit); | |
| lrat_chain.push_back (id); | |
| return 0; | |
| } | |
| if (v.reason) { | |
| assert (v.level); | |
| LOG (v.reason, "analyze reason"); | |
| return v.reason; | |
| } | |
| assert (assumed (-lit)); | |
| LOG ("failed assumption %d", -lit); | |
| clause.push_back (lit); | |
| return 0; | |
| }; | |
| Clause *reason = visit (lit); | |
| if (!reason) | |
| return; | |
| // The reasons on the DFS path with the position of their next literal. | |
| vector<pair<Clause *, int>> stack; | |
| stack.push_back ({reason, 0}); | |
| while (!stack.empty ()) { | |
| Clause *c = stack.back ().first; | |
| const int i = stack.back ().second; | |
| if (i < c->size) { | |
| stack.back ().second = i + 1; | |
| if (Clause *r = visit (c->literals[i])) | |
| stack.push_back ({r, 0}); | |
| } else { | |
| lrat_chain.push_back (c->id); | |
| stack.pop_back (); | |
| } | |
| } | |
| } | |
| void Internal::assume_analyze_reason (int lit, Clause *reason) { | |
| assert (reason); | |
| assert (lrat_chain.empty ()); | |
| assert (reason != external_reason); | |
| assert (lrat); | |
| for (const auto &other : *reason) | |
| if (other != lit) | |
| assume_analyze_literal (other); | |
| lrat_chain.push_back (reason->id); | |
| } | |
| // Find all failing assumptions starting from the one on the assumption | |
| // stack with the lowest decision level. This goes back to MiniSAT and is | |
| // called 'analyze_final' there. | |
| void Internal::failing () { | |
| PROFILE_SCOPE (analyze); | |
| LOG ("analyzing failing assumptions"); | |
| assert (analyzed.empty ()); | |
| assert (clause.empty ()); | |
| assert (lrat_chain.empty ()); | |
| assert (!marked_failed); | |
| assert (!conflict_id); | |
| if (!unsat_constraint) { | |
| // Search for failing assumptions in the (internal) assumption stack. | |
| // There are in essence three cases: (1) An assumption is falsified on | |
| // the root-level and then 'failed_unit' is set to that assumption, (2) | |
| // two clashing assumptions are assumed and then 'failed_clashing' is | |
| // set to the second assumed one, or otherwise (3) there is a failing | |
| // assumption 'first_failed' with minimum (non-zero) decision level | |
| // 'failed_level'. | |
| int failed_unit = 0; | |
| int failed_clashing = 0; | |
| int first_failed = 0; | |
| int failed_level = INT_MAX; | |
| int efailed = 0; | |
| for (auto &elit : external->assumptions) { | |
| int lit = external->e2i[abs (elit)]; | |
| if (elit < 0) | |
| lit = -lit; | |
| if (val (lit) >= 0) | |
| continue; | |
| const Var &v = var (lit); | |
| if (!v.level) { | |
| failed_unit = lit; | |
| efailed = elit; | |
| break; | |
| } | |
| if (failed_clashing) | |
| continue; | |
| if (v.reason == external_reason) { | |
| Var &ev = var (lit); | |
| ev.reason = learn_external_reason_clause (-lit); | |
| if (!ev.reason) { | |
| ev.level = 0; | |
| failed_unit = lit; | |
| efailed = elit; | |
| break; | |
| } | |
| ev.level = 0; | |
| // Recalculate assignment level | |
| for (const auto &other : *ev.reason) { | |
| if (other == -lit) | |
| continue; | |
| assert (val (other)); | |
| int tmp = var (other).level; | |
| if (tmp > ev.level) | |
| ev.level = tmp; | |
| } | |
| if (!ev.level) { | |
| failed_unit = lit; | |
| efailed = elit; | |
| break; | |
| } | |
| } | |
| assert (v.reason != external_reason); | |
| if (!v.reason) { | |
| failed_clashing = lit; | |
| efailed = elit; | |
| } else if (!first_failed || v.level < failed_level) { | |
| first_failed = lit; | |
| efailed = elit; | |
| failed_level = v.level; | |
| } | |
| } | |
| assert (clause.empty ()); | |
| // Get the 'failed' assumption from one of the three cases. | |
| int failed; | |
| if (failed_unit) | |
| failed = failed_unit; | |
| else if (failed_clashing) | |
| failed = failed_clashing; | |
| else | |
| failed = first_failed; | |
| assert (failed); | |
| assert (efailed); | |
| // In any case mark literal 'failed' as failed assumption. | |
| { | |
| Flags &f = flags (failed); | |
| const unsigned bit = bign (failed); | |
| assert (!(f.failed & bit)); | |
| f.failed |= bit; | |
| } | |
| // First case (1). | |
| if (failed_unit) { | |
| assert (failed == failed_unit); | |
| LOG ("root-level falsified assumption %d", failed); | |
| if (proof) { | |
| if (lrat) { | |
| unsigned eidx = (efailed > 0) + 2u * (unsigned) abs (efailed); | |
| assert ((size_t) eidx < external->ext_units.size ()); | |
| const int64_t id = external->ext_units[eidx]; | |
| if (id) { | |
| lrat_chain.push_back (id); | |
| } else { | |
| int64_t id = unit_id (-failed_unit); | |
| lrat_chain.push_back (id); | |
| } | |
| } | |
| proof->add_assumption_clause (++clause_id, -efailed, lrat_chain); | |
| conclusion.push_back (clause_id); | |
| lrat_chain.clear (); | |
| } | |
| return; | |
| } | |
| // Second case (2). | |
| if (failed_clashing) { | |
| assert (failed == failed_clashing); | |
| LOG ("clashing assumptions %d and %d", failed, -failed); | |
| Flags &f = flags (-failed); | |
| const unsigned bit = bign (-failed); | |
| assert (!(f.failed & bit)); | |
| f.failed |= bit; | |
| if (proof) { | |
| vector<int> clash = {externalize (failed), externalize (-failed)}; | |
| proof->add_assumption_clause (++clause_id, clash, lrat_chain); | |
| conclusion.push_back (clause_id); | |
| } | |
| return; | |
| } | |
| // Fall through to third case (3). | |
| LOG ("starting with assumption %d falsified on minimum decision level " | |
| "%d", | |
| first_failed, failed_level); | |
| assert (first_failed); | |
| assert (failed_level > 0); | |
| // The 'analyzed' stack serves as working stack for a BFS through the | |
| // implication graph until decisions, which are all assumptions, or | |
| // units are reached. This is simpler than corresponding code in | |
| // 'analyze'. | |
| { | |
| LOG ("failed assumption %d", first_failed); | |
| Flags &f = flags (first_failed); | |
| assert (!f.seen); | |
| f.seen = true; | |
| assert (f.failed & bign (first_failed)); | |
| analyzed.push_back (-first_failed); | |
| clause.push_back (-first_failed); | |
| } | |
| } else { | |
| // unsat_constraint | |
| // The assumptions necessary to fail each literal in the constraint are | |
| // collected. | |
| for (auto lit : constraint) { | |
| lit *= -1; | |
| assert (lit != INT_MIN); | |
| flags (lit).seen = true; | |
| analyzed.push_back (lit); | |
| } | |
| } | |
| { | |
| // used for unsat_constraint lrat | |
| vector<vector<int64_t>> constraint_chains; | |
| vector<vector<int>> constraint_clauses; | |
| vector<int> sum_constraints; | |
| vector<int> econstraints; | |
| for (auto &elit : external->constraint) { | |
| int lit = external->e2i.find_or_default (abs (elit), 0); | |
| if (elit < 0) | |
| lit = -lit; | |
| if (!lit) | |
| continue; | |
| Flags &f = flags (lit); | |
| if (f.seen) | |
| continue; | |
| if (std::find (econstraints.begin (), econstraints.end (), elit) != | |
| econstraints.end ()) | |
| continue; | |
| econstraints.push_back (elit); | |
| } | |
| // no LRAT do bfs as it was before | |
| if (!lrat) { | |
| size_t next = 0; | |
| while (next < analyzed.size ()) { | |
| const int lit = analyzed[next++]; | |
| assert (val (lit) > 0); | |
| Var &v = var (lit); | |
| if (!v.level) | |
| continue; | |
| if (v.reason == external_reason) { | |
| v.reason = learn_external_reason_clause (lit, 0, true); | |
| if (!v.reason) { | |
| v.level = 0; | |
| continue; | |
| } | |
| } | |
| assert (v.reason != external_reason); | |
| if (v.reason) { | |
| assert (v.level); | |
| LOG (v.reason, "analyze reason"); | |
| for (const auto &other : *v.reason) { | |
| Flags &f = flags (other); | |
| if (f.seen) | |
| continue; | |
| f.seen = true; | |
| assert (val (other) < 0); | |
| analyzed.push_back (-other); | |
| } | |
| } else { | |
| assert (assumed (lit)); | |
| LOG ("failed assumption %d", lit); | |
| clause.push_back (-lit); | |
| Flags &f = flags (lit); | |
| const unsigned bit = bign (lit); | |
| assert (!(f.failed & bit)); | |
| f.failed |= bit; | |
| } | |
| } | |
| clear_analyzed_literals (); | |
| } else if (!unsat_constraint) { // LRAT for case (3) | |
| assert (clause.size () == 1); | |
| const int lit = clause[0]; | |
| Var &v = var (lit); | |
| assert (v.reason); | |
| if (v.reason == external_reason) { // does this even happen? | |
| v.reason = learn_external_reason_clause (lit, 0, true); | |
| } | |
| assert (v.reason != external_reason); | |
| if (v.reason) | |
| assume_analyze_reason (lit, v.reason); | |
| else { | |
| int64_t id = unit_id (lit); | |
| lrat_chain.push_back (id); | |
| } | |
| for (auto &lit : clause) { | |
| Flags &f = flags (lit); | |
| const unsigned bit = bign (-lit); | |
| if (!(f.failed & bit)) | |
| f.failed |= bit; | |
| } | |
| clear_analyzed_literals (); | |
| } else { // LRAT for unsat_constraint | |
| assert (clause.empty ()); | |
| clear_analyzed_literals (); | |
| for (auto lit : constraint) { | |
| // make sure nothing gets marked failed twice | |
| // also might shortcut the case where | |
| // lrat_chain is empty because clause is tautological | |
| assert (lit != INT_MIN); | |
| assume_analyze_literal (lit); | |
| vector<int64_t> empty; | |
| vector<int> empty2; | |
| constraint_chains.push_back (empty); | |
| constraint_clauses.push_back (empty2); | |
| for (auto ign : clause) { | |
| constraint_clauses.back ().push_back (ign); | |
| Flags &f = flags (ign); | |
| const unsigned bit = bign (-ign); | |
| if (!(f.failed & bit)) { | |
| sum_constraints.push_back (ign); | |
| assert (!(f.failed & bit)); | |
| f.failed |= bit; | |
| } | |
| } | |
| clause.clear (); | |
| clear_analyzed_literals (); | |
| for (auto p : lrat_chain) { | |
| constraint_chains.back ().push_back (p); | |
| } | |
| lrat_chain.clear (); | |
| } | |
| for (auto &lit : sum_constraints) | |
| clause.push_back (lit); | |
| } | |
| clear_analyzed_literals (); | |
| // Doing clause minimization here does not do anything because | |
| // the clause already contains only one literal of each level | |
| // and minimization can never reduce the number of levels | |
| VERBOSE (1, "found %zd failed assumptions %.0f%%", clause.size (), | |
| percent (clause.size (), assumptions.size ())); | |
| // We do not actually need to learn this clause, since the conflict is | |
| // forced already by some other clauses. There is also no bumping | |
| // of variables nor clauses necessary. But we still want to check | |
| // correctness of the claim that the determined subset of failing | |
| // assumptions are a high-level core or equivalently their negations | |
| // form a unit-implied clause. | |
| // | |
| if (!unsat_constraint) { | |
| external->check_learned_clause (); | |
| if (proof) { | |
| vector<int> eclause; | |
| for (auto &lit : clause) | |
| eclause.push_back (externalize (lit)); | |
| proof->add_assumption_clause (++clause_id, eclause, lrat_chain); | |
| conclusion.push_back (clause_id); | |
| } | |
| } else { | |
| assert (!lrat || (constraint.size () == constraint_clauses.size () && | |
| constraint.size () == constraint_chains.size ())); | |
| for (auto p = constraint.rbegin (); p != constraint.rend (); p++) { | |
| const auto &lit = *p; | |
| if (lrat) { | |
| clause.clear (); | |
| for (auto &ign : constraint_clauses.back ()) | |
| clause.push_back (ign); | |
| constraint_clauses.pop_back (); | |
| } | |
| clause.push_back (-lit); | |
| external->check_learned_clause (); | |
| if (proof) { | |
| if (lrat) { | |
| for (auto p : constraint_chains.back ()) { | |
| lrat_chain.push_back (p); | |
| } | |
| constraint_chains.pop_back (); | |
| LOG (lrat_chain, "assume proof chain with constraints"); | |
| } | |
| vector<int> eclause; | |
| for (auto &lit : clause) | |
| eclause.push_back (externalize (lit)); | |
| proof->add_assumption_clause (++clause_id, eclause, lrat_chain); | |
| conclusion.push_back (clause_id); | |
| lrat_chain.clear (); | |
| } | |
| clause.pop_back (); | |
| } | |
| if (proof) { | |
| for (auto &elit : econstraints) { | |
| if (lrat) { | |
| unsigned eidx = (elit > 0) + 2u * (unsigned) abs (elit); | |
| assert ((size_t) eidx < external->ext_units.size ()); | |
| const int64_t id = external->ext_units[eidx]; | |
| if (id) { | |
| lrat_chain.push_back (id); | |
| } else { | |
| int lit = external->e2i[abs (elit)]; | |
| if (elit < 0) | |
| lit = -lit; | |
| int64_t id = unit_id (-lit); | |
| lrat_chain.push_back (id); | |
| } | |
| } | |
| proof->add_assumption_clause (++clause_id, -elit, lrat_chain); | |
| conclusion.push_back (clause_id); | |
| lrat_chain.clear (); | |
| } | |
| } | |
| } | |
| lrat_chain.clear (); | |
| clause.clear (); | |
| } | |
| } | |
| bool Internal::failed (int lit) { | |
| if (!marked_failed) { | |
| if (!conflict_id) | |
| failing (); | |
| marked_failed = true; | |
| } | |
| conclude_unsat (); | |
| Flags &f = flags (lit); | |
| const unsigned bit = bign (lit); | |
| return (f.failed & bit) != 0; | |
| } | |
| void Internal::conclude_unsat () { | |
| if (!proof || concluded) | |
| return; | |
| concluded = true; | |
| if (!marked_failed) { | |
| assert (conclusion.empty ()); | |
| if (!conflict_id) | |
| failing (); | |
| marked_failed = true; | |
| } | |
| ConclusionType con; | |
| if (conflict_id) | |
| con = CONFLICT; | |
| else if (unsat_constraint) | |
| con = CONSTRAINT; | |
| else | |
| con = ASSUMPTIONS; | |
| proof->conclude_unsat (con, conclusion); | |
| } | |
| void Internal::reset_concluded () { | |
| // this is preemptive fix: if you reset the constrain without | |
| // resetting the assumptions, you should not reset the assumptions in | |
| // the proofs. This is not possible anymore since reset_constrain | |
| // () is not part part of the API anymore, but this was possible in | |
| // 3.0.1. Therefore, for defensive programming, we decided to | |
| // implement the code just in case we ever readd the call. | |
| if (proof && external->assumptions.empty ()) | |
| proof->reset_assumptions (); | |
| if (concluded) { | |
| LOG ("reset concluded"); | |
| concluded = false; | |
| } | |
| if (conflict_id) { | |
| assert (conclusion.size () == 1); | |
| return; | |
| } | |
| conclusion.clear (); | |
| } | |
| // Add the start of each incremental phase (leaving the state | |
| // 'UNSATISFIABLE' actually) we reset all assumptions. | |
| void Internal::reset_assumptions () { | |
| for (const auto &lit : assumptions) { | |
| Flags &f = flags (lit); | |
| const unsigned char bit = bign (lit); | |
| f.assumed &= ~bit; | |
| f.failed &= ~bit; | |
| melt (lit); | |
| } | |
| LOG ("cleared %zd assumptions", assumptions.size ()); | |
| assumptions.clear (); | |
| marked_failed = true; | |
| } | |
| struct sort_assumptions_positive_rank { | |
| Internal *internal; | |
| // Decision level could be 'INT_MAX' and thus 'level + 1' could overflow. | |
| // Therefore we carefully have to use 'unsigned' for levels below. | |
| const unsigned max_level; | |
| sort_assumptions_positive_rank (Internal *s) | |
| : internal (s), max_level (s->level + 1u) {} | |
| typedef uint64_t Type; | |
| // Set assumptions first, then sorted by position on the trail | |
| // unset literals are sorted by literal value. | |
| Type operator() (const int &a) const { | |
| const int val = internal->val (a); | |
| const bool assigned = (val != 0); | |
| const Var &v = internal->var (a); | |
| uint64_t res = (assigned ? (unsigned) v.level : max_level); | |
| res <<= 32; | |
| res |= (assigned ? v.trail : abs (a)); | |
| return res; | |
| } | |
| }; | |
| struct sort_assumptions_smaller { | |
| Internal *internal; | |
| sort_assumptions_smaller (Internal *s) : internal (s) {} | |
| bool operator() (const int &a, const int &b) const { | |
| return sort_assumptions_positive_rank (internal) (a) < | |
| sort_assumptions_positive_rank (internal) (b); | |
| } | |
| }; | |
| // Sort the assumptions by the current position on the trail and backtrack | |
| // to the first place where the assumptions and the current trail differ. | |
| void Internal::sort_and_reuse_assumptions () { | |
| assert (opts.ilb >= 1); | |
| if (assumptions.empty ()) { | |
| if (opts.ilb == 1) { | |
| LOG ("no assumptions, reusing nothing (ilb == 1)"); | |
| backtrack (0); | |
| } else { // reuse full trail | |
| LOG ("no assumptions, reusing everything (ilb == 2)"); | |
| return; | |
| } | |
| } | |
| MSORT (opts.radixsortlim, assumptions.begin (), assumptions.end (), | |
| sort_assumptions_positive_rank (this), | |
| sort_assumptions_smaller (this)); | |
| unsigned max_level = 0; | |
| // assumptions are sorted by level, with unset at the end | |
| for (auto lit : assumptions) { | |
| if (val (lit)) | |
| max_level = var (lit).level; | |
| else | |
| break; | |
| } | |
| const unsigned size = min (level + 1u, max_level + 1); | |
| assert ((size_t) level == control.size () - 1); | |
| LOG (assumptions, "sorted assumptions"); | |
| int target = 0; | |
| for (unsigned i = 1, j = 0; i < size;) { | |
| const Level &l = control[i]; | |
| const int lit = l.decision; | |
| const int alit = assumptions[j]; | |
| const int lev = i; | |
| target = lev; | |
| if (val (alit) > 0 && | |
| var (alit).level < lev) { // we can ignore propagated assumptions | |
| LOG ("ILB skipping propagation %d", alit); | |
| ++j; | |
| continue; | |
| } | |
| if (!lit) { // skip fake decisions | |
| target = lev - 1; | |
| break; | |
| } | |
| ++i, ++j; | |
| assert (var (lit).level == lev || !var (lit).level || var (lit).reason); | |
| if (l.decision == alit) { | |
| continue; | |
| } | |
| target = lev - 1; | |
| LOG ("first different literal %d on the trail and %d from the " | |
| "assumptions", | |
| lit, alit); | |
| break; | |
| } | |
| if (opts.ilb == 1 && | |
| (size_t) target > assumptions.size ()) // reusing only assumptions | |
| target = assumptions.size (); | |
| if (target < level) | |
| backtrack_without_updating_phases (target); | |
| LOG ("assumptions allow for reuse of trail up to level %d", level); | |
| if ((size_t) level > assumptions.size ()) | |
| stats.ilb_reuse_assumptions += assumptions.size (); | |
| else | |
| stats.ilb_reuse_assumptions += level; | |
| } | |
| } // namespace CaDiCaL |