| #include "contract.hpp" | |
| #include "internal.hpp" | |
| #include <algorithm> | |
| namespace CaDiCaL { | |
| #ifndef NTRACING | |
| #define LOG_INTERACTION_START(NAME) LOG (#NAME " on level %d START", level); | |
| #define LOG_INTERACTION_FOR(NAME, VAL) \ | |
| LOG (#NAME "(%d) on level %d START", VAL, level) | |
| static void trace_api_call (FILE *trace_api_file, Internal *internal, | |
| const char *s0, int i1) { | |
| assert (trace_api_file); | |
| LOG ("TRACE %s %d", s0, i1); | |
| (void) internal; | |
| fprintf (trace_api_file, "%s %d\n", s0, i1); | |
| fflush (trace_api_file); | |
| } | |
| static void trace_api_call (FILE *trace_api_file, Internal *internal, | |
| const char *s0, int i1, int i2) { | |
| assert (trace_api_file); | |
| LOG ("TRACE %s %d", s0, i1); | |
| (void) internal; | |
| fprintf (trace_api_file, "%s %d %d\n", s0, i1, i2); | |
| fflush (trace_api_file); | |
| } | |
| #define LOG_INTERACTION_RETURN_FOR(NAME, VAL, RET) \ | |
| do { \ | |
| LOG (#NAME "(%d) returns %d on level %d END", VAL, RET, level); \ | |
| if (!opts.exttracecalls) \ | |
| break; \ | |
| if (!external->trace_api_file) \ | |
| break; \ | |
| trace_api_call (external->trace_api_file, this, #NAME, VAL, RET); \ | |
| } while (0) | |
| #define LOG_INTERACTION_RETURN_TWO(NAME, RET1, RET2) \ | |
| do { \ | |
| LOG (#NAME " returns %d (%d) on level %d END", RET1, RET2, level); \ | |
| if (!opts.exttracecalls) \ | |
| break; \ | |
| if (!external->trace_api_file) \ | |
| break; \ | |
| trace_api_call (external->trace_api_file, this, #NAME, RET1, RET2); \ | |
| } while (0) | |
| #define LOG_INTERACTION_END_FOR(NAME, VAL) \ | |
| do { \ | |
| LOG (#NAME "(%d) on level %d END", VAL, level); \ | |
| if (!opts.exttracecalls) \ | |
| break; \ | |
| if (!external->trace_api_file) \ | |
| break; \ | |
| trace_api_call (external->trace_api_file, this, #NAME, VAL); \ | |
| } while (0) | |
| #define LOG_INTERACTION_RETURN(NAME, VAL) \ | |
| do { \ | |
| LOG (#NAME " returns %d on level %d END", VAL, level); \ | |
| if (!opts.exttracecalls) \ | |
| break; \ | |
| if (!external->trace_api_file) \ | |
| break; \ | |
| trace_api_call (external->trace_api_file, this, #NAME, VAL); \ | |
| } while (0) | |
| #else | |
| #define LOG_INTERACTION_START(NAME) LOG (#NAME " on level %d START", level) | |
| #define LOG_INTERACTION_FOR(NAME, VAL) \ | |
| LOG (#NAME "(%d) on level %d START", VAL, level) | |
| #define LOG_INTERACTION_RETURN(NAME, VAL) \ | |
| LOG (#NAME " returns %d on level %d END", VAL, level) | |
| #define LOG_INTERACTION_RETURN_TWO(NAME, RET1, RET2) \ | |
| LOG (#NAME " returns %d (%d) on level %d END", RET1, RET2, level) | |
| #define LOG_INTERACTION_END_FOR(NAME, VAL) \ | |
| LOG (#NAME "(%d) on level %d END", VAL, level) | |
| #define LOG_INTERACTION_RETURN_FOR(NAME, VAL, RET) \ | |
| LOG (#NAME "(%d) returns %d on level %d END", VAL, RET, level) | |
| #endif | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Mark a variable as an observed one. It can be a new variable. It is | |
| // assumed to be clean (not eliminated by previous simplifications). | |
| // | |
| void Internal::add_observed_var (int ilit) { | |
| int idx = vidx (ilit); | |
| if (idx >= (int64_t) relevanttab.size ()) | |
| relevanttab.resize (1 + (size_t) idx, 0); | |
| unsigned &ref = relevanttab[idx]; | |
| if (flags (idx).unused ()) | |
| declare_variable (idx); | |
| if (ref < UINT_MAX) { | |
| ref++; | |
| LOG ("variable %d is observed %u times", idx, ref); | |
| } else | |
| LOG ("variable %d remains observed forever", idx); | |
| // TODO: instead of actually backtracking, it would be enough to notify | |
| // backtrack and re-play again every levels' notification to the | |
| // propagator | |
| if (val (ilit) && level && !fixed (ilit)) { | |
| REQUIRE (!force_no_backtrack, | |
| "can not observe assigned variable during conflict analysis"); | |
| // The variable is already assigned, but we can not send a notification | |
| // about it because it happened on an earlier decision level. | |
| // To not break the stack-like view of the trail, we simply backtrack to | |
| // undo this unnotifiable assignment. | |
| const int assignment_level = var (ilit).level; | |
| backtrack_without_updating_phases (assignment_level - 1); | |
| } else if (level && fixed (ilit)) { | |
| REQUIRE (!conflict, | |
| "can not observe fixed variable during conflict analysis"); | |
| backtrack_without_updating_phases (0); | |
| } | |
| activating_all_new_imported_literals (); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Removing an observed variable should happen only once it is ensured | |
| // that there is no unexplained propagation in the implication | |
| // graph involving this variable. To ensure that, the solver might | |
| // need to backtrack so that the variable becomes unassigned. | |
| // | |
| void Internal::remove_observed_var (int ilit) { | |
| if (!fixed (ilit) && level && val (ilit)) { | |
| REQUIRE (!force_no_backtrack, | |
| "can not remove observed assigned variable during conflict " | |
| "analysis"); | |
| const int assignment_level = var (ilit).level; | |
| backtrack_without_updating_phases (assignment_level - 1); | |
| } | |
| assert (fixed (ilit) || !val (ilit)); | |
| const int idx = vidx (ilit); | |
| assert ((size_t) idx < relevanttab.size ()); | |
| unsigned &ref = relevanttab[idx]; | |
| assert (fixed (ilit) || ref > 0); | |
| if (fixed (ilit)) | |
| ref = 0; | |
| else if (ref < UINT_MAX) { | |
| if (!--ref) { | |
| LOG ("variable %d is not observed anymore", idx); | |
| } else | |
| LOG ("variable %d is unobserved once but remains observed %u times", | |
| ilit, ref); | |
| } else | |
| LOG ("variable %d remains observed forever", idx); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Supposed to be used only by mobical. | |
| // | |
| bool Internal::observed (int ilit) const { | |
| assert ((size_t) vidx (ilit) < relevanttab.size ()); | |
| return relevanttab[vidx (ilit)] > 0; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Check for unexplained propagations upon disconnecting external propagator | |
| // | |
| void Internal::set_changed_val () { | |
| if (!opts.ilb) { | |
| return; | |
| } | |
| for (auto idx : vars) { | |
| if (!val (idx)) | |
| continue; | |
| if (var (idx).reason != external_reason) | |
| continue; | |
| if (!earliest_changed_val) { | |
| earliest_changed_val = idx; | |
| continue; | |
| } | |
| assert (val (earliest_changed_val)); | |
| if (var (idx).level < var (earliest_changed_val).level) { | |
| earliest_changed_val = idx; | |
| } | |
| } | |
| } | |
| void Internal::renotify_trail_after_ilb () { | |
| assert (opts.ilb); | |
| if (!external_prop || external_prop_is_lazy || !trail.size () || | |
| !opts.ilb) { | |
| return; | |
| } | |
| LOG ("notify external propagator about new assignments (after ilb)"); | |
| #ifndef NDEBUG | |
| LOG ("(decision level: %d, trail size: %zd, notified %zd)", level, | |
| trail.size (), notified); | |
| #endif | |
| renotify_full_trail (); | |
| } | |
| void Internal::renotify_trail_after_local_search () { | |
| if (!external_prop || external_prop_is_lazy || !trail.size ()) { | |
| return; | |
| } | |
| LOG ("notify external propagator about new assignments (after local " | |
| "search)"); | |
| #ifndef NDEBUG | |
| LOG ("(decision level: %d, trail size: %zd, notified %zd)", level, | |
| trail.size (), notified); | |
| #endif | |
| renotify_full_trail (); | |
| } | |
| void Internal::renotify_full_trail_between_trail_pos ( | |
| int start_level, int end_level, int up_level, | |
| std::vector<int> &assigned, bool start_new_level) { | |
| assert (assigned.empty ()); | |
| int j = start_level; | |
| #ifdef LOGGING | |
| LOG ("starting notification of level %d from trail %d .. %d", up_level, | |
| start_level, end_level); | |
| #else | |
| (void) up_level; | |
| #endif | |
| if (start_new_level) { | |
| if (assigned.size ()) { | |
| LOG_INTERACTION_FOR (notify_assignment_batch, (int) assigned.size ()); | |
| external->propagator->notify_assignment (assigned); | |
| LOG_INTERACTION_END_FOR (notify_assignment_batch, | |
| (int) assigned.size ()); | |
| } | |
| assigned.clear (); | |
| notified_level++; | |
| LOG_INTERACTION_FOR (notify_new_decision_level, notified_level); | |
| external->propagator->notify_new_decision_level (); | |
| LOG_INTERACTION_END_FOR (notify_new_decision_level, notified_level); | |
| } | |
| for (; j < end_level; ++j) { | |
| int ilit = trail[j]; | |
| // In theory, 0 ilit can happen due to pseudo-decision levels | |
| if (!ilit) | |
| continue; | |
| if (!observed (ilit)) | |
| continue; | |
| int elit = externalize (ilit); // TODO: double-check tainting | |
| LOG ("notifying elit %d @ %d aka %s", up_level, elit, LOGLIT (ilit)); | |
| assert (elit); | |
| // Fixed variables might get mapped (during compact) to another | |
| // non-observed but fixed variable. | |
| // This happens on root level, so notification about their assignment | |
| // is already done. | |
| assert (external->observed (elit) || fixed (ilit)); | |
| if (external->observed (elit) && !external->ervars[abs (elit)]) | |
| assigned.push_back (elit); | |
| } | |
| if (assigned.size ()) { | |
| LOG_INTERACTION_FOR (notify_assignment_batch, (int) assigned.size ()); | |
| external->propagator->notify_assignment (assigned); | |
| LOG_INTERACTION_END_FOR (notify_assignment_batch, | |
| (int) assigned.size ()); | |
| } | |
| assigned.clear (); | |
| } | |
| // It repeats ALL assignments of the trail, so the already notified | |
| // root-level assignments will be notified multiple times. | |
| // | |
| // As CaDiCaL is missing some '0' seperators, it is important to go | |
| // over slices from the control stack instead of going over the trail | |
| // directly. | |
| void Internal::renotify_full_trail () { | |
| const size_t end_of_trail = trail.size (); | |
| if (level) { | |
| notified = 0; // TODO: save the last notified root-level position | |
| // somewhere and use it here | |
| if (notified_level) | |
| notify_backtrack (0); | |
| } | |
| std::vector<int> assigned; | |
| int up_level = 0; | |
| const int c_size = control.size (); | |
| { // first all root-level literals | |
| const int start_level = 0; | |
| const int end_level = | |
| (control.size () > 1 ? control[1].trail : end_of_trail); | |
| renotify_full_trail_between_trail_pos (start_level, end_level, up_level, | |
| assigned, false); | |
| } | |
| // notify all intermediate levels | |
| for (int i = 2; i < c_size; ++i) { | |
| const int start_level = control[i - 1].trail; | |
| const int end_level = control[i].trail; | |
| up_level++; | |
| LOG ("notification of %d", up_level); | |
| renotify_full_trail_between_trail_pos (start_level, end_level, up_level, | |
| assigned, true); | |
| } | |
| // and the current level if there is non-root level one | |
| if (level) { | |
| const int start_level = control.back ().trail; | |
| up_level++; | |
| renotify_full_trail_between_trail_pos (start_level, end_of_trail, | |
| up_level, assigned, true); | |
| } | |
| assert (up_level == level); | |
| notified = trail.size (); | |
| return; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Check if the variable is assigned by decision. | |
| // | |
| bool Internal::is_decision (int ilit) { | |
| if (!level || fixed (ilit) || !val (ilit)) | |
| return false; | |
| const int idx = vidx (ilit); | |
| Var &v = var (idx); | |
| #ifndef NDEBUG | |
| LOG (v.reason, | |
| "is_decision: i%d (current level: %d, is_fixed: %d, v.level: %d, " | |
| "is_external_reason: %d, v.reason: )", | |
| ilit, level, fixed (ilit), v.level, v.reason == external_reason); | |
| #endif | |
| if (!v.level || v.reason) | |
| return false; | |
| assert (!v.reason); | |
| return true; | |
| } | |
| void Internal::force_backtrack (int new_level) { | |
| #ifndef NDEBUG | |
| LOG ("external propagator forces backtrack to decision level" | |
| "%d (from level %d)", | |
| new_level, level); | |
| #endif | |
| backtrack (new_level); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Call external propagator to check if there is a literal to be propagated. | |
| // The reason of the propagation is not necessarily asked at that point. | |
| // | |
| // In case the externally propagated literal is already falsified, the | |
| // reason is asked and conflict analysis starts. In case the externally | |
| // propagated literal is already satisfied, nothing happens. | |
| // | |
| bool Internal::external_propagate () { | |
| if (level) | |
| MODE_REQUIRE (SEARCH); | |
| assert (!unsat); | |
| size_t before = num_assigned; | |
| bool cb_repropagate_needed = true; | |
| while (cb_repropagate_needed && !conflict && external_prop && | |
| !external_prop_is_lazy && !private_steps) { | |
| #ifndef NDEBUG | |
| LOG ("external propagation starts (decision level: %d, trail size: " | |
| "%zd, notified %zd)", | |
| level, trail.size (), notified); | |
| #endif | |
| cb_repropagate_needed = false; | |
| // external->reset_extended (); //TODO for inprocessing | |
| notify_assignments (); | |
| LOG_INTERACTION_START (cb_propagate); | |
| int elit = external->propagator->cb_propagate (); | |
| LOG_INTERACTION_RETURN (cb_propagate, elit); | |
| CB_REQUIRE (!elit || external->observed (elit), "cb_propagate", elit, | |
| "external propagations are only allowed over observed " | |
| "variables."); | |
| stats.up_cb++; | |
| stats.up_cb_prop++; | |
| while (elit) { | |
| assert (external->is_observed[abs (elit)]); | |
| int ilit = external->e2i[abs (elit)]; | |
| if (elit < 0) | |
| ilit = -ilit; | |
| int tmp = val (ilit); | |
| #ifndef NDEBUG | |
| assert (fixed (ilit) || observed (ilit)); | |
| LOG ("External propagation of e%d (i%d val: %d)", elit, ilit, tmp); | |
| #endif | |
| if (!tmp) { | |
| // variable is not assigned, it can be propagated | |
| if (!level) { | |
| Clause *res = learn_external_reason_clause (ilit, elit); | |
| #ifndef LOGGING | |
| LOG (res, "reason clause of external propagation of %d:", elit); | |
| #endif | |
| (void) res; | |
| } else | |
| search_assign_external (ilit); | |
| stats.up_cb_prop_assign++; | |
| if (unsat || conflict) | |
| break; | |
| propagate (); | |
| if (unsat || conflict) | |
| break; | |
| notify_assignments (); | |
| } else if (tmp < 0) { | |
| LOG ("External propgation of %d is falsified under current trail", | |
| ilit); | |
| stats.up_cb_prop_clash++; | |
| int level_before = level; | |
| size_t assigned = num_assigned; | |
| Clause *res = learn_external_reason_clause (ilit, elit); | |
| #ifndef LOGGING | |
| LOG (res, "reason clause of external propagation of %d:", elit); | |
| #endif | |
| (void) res; | |
| bool trail_changed = | |
| (num_assigned != assigned || level != level_before || | |
| propagated < trail.size ()); | |
| if (unsat || conflict) | |
| break; | |
| if (trail_changed) { | |
| propagate (); | |
| if (unsat || conflict) | |
| break; | |
| notify_assignments (); | |
| } | |
| } // else (tmp > 0) -> the case of a satisfied literal is ignored | |
| LOG_INTERACTION_START (cb_propagate); | |
| elit = external->propagator->cb_propagate (); | |
| LOG_INTERACTION_RETURN (cb_propagate, elit); | |
| stats.up_cb++; | |
| stats.up_cb_prop++; | |
| } | |
| #ifndef NDEBUG | |
| LOG ("External propagation ends (decision level: %d, trail size: %zd, " | |
| "notified %zd)", | |
| level, trail.size (), notified); | |
| #endif | |
| if (!unsat && !conflict) { | |
| int level_before = level; | |
| size_t assigned = num_assigned; | |
| bool has_external_clause = ask_external_clause (); | |
| // New observed variable might have triggered a backtrack during this | |
| // ask_external_clause call, so we need to propagate before continuing | |
| stats.up_cb++; | |
| stats.up_cb_add++; | |
| bool trail_changed = | |
| (num_assigned != assigned || level != level_before || | |
| propagated < trail.size ()); | |
| if (trail_changed) { | |
| propagate (); // unsat or conflict will be caught later | |
| if (!unsat || !conflict) | |
| notify_assignments (); | |
| } | |
| #ifndef NDEBUG | |
| if (has_external_clause) | |
| LOG ("New external clauses are to be added."); | |
| else | |
| LOG ("No external clauses to be added."); | |
| #endif | |
| while (has_external_clause) { | |
| level_before = level; | |
| assigned = num_assigned; | |
| add_external_clause (0); | |
| trail_changed = | |
| (num_assigned != assigned || level != level_before || | |
| propagated < trail.size ()); | |
| cb_repropagate_needed = true; | |
| if (unsat || conflict) { | |
| cb_repropagate_needed = false; | |
| break; | |
| } | |
| if (trail_changed) { | |
| propagate (); | |
| if (unsat || conflict) { | |
| cb_repropagate_needed = false; | |
| break; | |
| } | |
| notify_assignments (); | |
| } | |
| has_external_clause = ask_external_clause (); | |
| stats.up_cb++; | |
| stats.up_cb_add++; | |
| } | |
| } | |
| #ifndef NDEBUG | |
| LOG ("External clause addition ends on decision level %d at trail " | |
| "size " | |
| "%zd (notified %zd)", | |
| level, trail.size (), notified); | |
| #endif | |
| } | |
| if (before < num_assigned) | |
| did_external_prop = true; | |
| return !conflict; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Helper function, calls 'cb_has_external_clause', while maintains the | |
| // related redundancy type of the clause. | |
| // | |
| bool Internal::ask_external_clause () { | |
| ext_clause_forgettable = false; | |
| LOG_INTERACTION_START (cb_has_external_clause); | |
| bool res = | |
| external->propagator->cb_has_external_clause (ext_clause_forgettable); | |
| LOG_INTERACTION_RETURN_TWO (cb_has_external_clause, res, | |
| ext_clause_forgettable); | |
| return res; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Literals of the externally learned clause must be reordered based on the | |
| // assignment levels of the literals. | |
| // Returns the best clause idx (except ignore) | |
| size_t Internal::best_literal_to_watch (int ignore, bool trail_over_level) { | |
| size_t lit_position = 0; | |
| int lit = 0; | |
| int lit_level = 0; | |
| signed char lit_value = 0; | |
| int lit_trail = 0; | |
| for (size_t i = 0; i < clause.size (); i++) { | |
| const int other = clause[i]; | |
| if (other == ignore) | |
| continue; | |
| assert (other); | |
| const int other_level = var (other).level; | |
| const signed char other_value = val (other); | |
| const int other_trail = var (other).trail; | |
| if (!lit || // no candidate yet. | |
| lit_value < other_value || // -1 < 0 < 1 | |
| (lit_value == other_value && // Tie breaker: | |
| ((lit_value < 0 && // -1: | |
| ((!trail_over_level && // level over trail: | |
| (lit_level < other_level || // higher level, or | |
| (lit_level == other_level && // equal level: | |
| lit_trail < other_trail))) || // higher trail | |
| (trail_over_level && // trail over level: | |
| lit_trail < other_trail))) || // higher trail | |
| (lit_value > 0 && lit_level > other_level)))) // 1: lower level | |
| { | |
| lit = other; | |
| lit_position = i; | |
| lit_value = other_value; | |
| lit_level = other_level; | |
| lit_trail = other_trail; | |
| } | |
| } | |
| assert (lit); | |
| return lit_position; | |
| } | |
| void Internal::move_literals_to_watch () { | |
| if (clause.size () < 2) | |
| return; | |
| if (!level) | |
| return; | |
| size_t best1 = best_literal_to_watch (0, false); | |
| const int lit = clause[best1]; | |
| if (best1 != 0) | |
| std::swap (clause[0], clause[best1]); | |
| size_t best2 = best_literal_to_watch (lit, false); | |
| // const int other = clause[best2]; | |
| assert (best2 && clause[best2] != lit); | |
| if (best2 != 1) | |
| std::swap (clause[1], clause[best2]); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Reads out from the external propagator the lemma/proapgation reason | |
| // clause literal by literal. In case propagated_elit is 0, it is about an | |
| // external clause via 'cb_add_external_clause_lit'. Otherwise, it is about | |
| // learning the reason of 'propagated_elit' via 'cb_add_reason_clause_lit'. | |
| // The learned clause is simplified by the current root-level assignment | |
| // (i.e. root-level falsified literals are removed, root satisfied clauses | |
| // are skipped). Duplicate literals are removed, tauotologies are detected | |
| // and skipped. It always adds the original (un-simplified) external clause | |
| // to the proof as an input clause and | |
| // the simplified version of it (except exceptions below) as a derived | |
| // clause. | |
| // | |
| // In case the external clause, after simplifications, is satisfied, no | |
| // clause is constructed, and the function returns 0. In case the external | |
| // clause, after simplifications, is empty, no clause is constructed, unsat | |
| // is set true and the function returns 0. In case the external clause, | |
| // after simplifications, is unit, no clause is constructed, | |
| // 'Internal::clause' has the unit literal (without 0) and the function | |
| // returns 0. | |
| // | |
| // In every other cases a new clause is constructed and the pointer is in | |
| // newest_clause | |
| // | |
| void Internal::add_external_clause (int propagated_elit, | |
| bool no_backtrack) { | |
| assert (!force_no_backtrack); | |
| assert (!from_propagator); | |
| force_no_backtrack = no_backtrack; | |
| from_propagator = true; | |
| int elit = 0; | |
| #ifndef NCONTRACTS | |
| bool propagated_lit_found = false; | |
| #endif | |
| assert (tmp_elits.empty ()); | |
| while (true) { | |
| if (propagated_elit) { | |
| LOG_INTERACTION_FOR (cb_add_reason_clause_lit, propagated_elit); | |
| elit = | |
| external->propagator->cb_add_reason_clause_lit (propagated_elit); | |
| LOG_INTERACTION_RETURN_FOR (cb_add_reason_clause_lit, propagated_elit, | |
| elit); | |
| CB_REQUIRE (!elit || external->observed (elit), | |
| "cb_add_reason_clause_lit", elit, | |
| "reason clause must contain only observed variables."); | |
| } else { | |
| LOG_INTERACTION_START (cb_add_external_clause_lit); | |
| elit = external->propagator->cb_add_external_clause_lit (); | |
| LOG_INTERACTION_RETURN (cb_add_external_clause_lit, elit); | |
| CB_REQUIRE (!elit || external->observed (elit), | |
| "cb_add_external_clause_lit", elit, | |
| "external clause must contain only observed variables."); | |
| } | |
| LOG ("cb_add %d", elit); | |
| tmp_elits.push_back (elit); | |
| if (!elit) | |
| break; | |
| #ifndef NCONTRACTS | |
| if (elit == propagated_elit) | |
| propagated_lit_found = true; | |
| #endif | |
| CB_REQUIRE ( | |
| !propagated_elit || elit == propagated_elit || | |
| external->current_val (elit) < 0, | |
| "cb_add_reason_clause_lit", elit, | |
| "external reason clause must only contain falsified literals"); | |
| CB_REQUIRE (!propagated_elit || elit == propagated_elit || | |
| external->current_val (propagated_elit) < 0 || !level || | |
| var (external->internalize (elit)).trail < | |
| var (external->internalize (propagated_elit)).trail, | |
| "cb_add_reason_clause_lit", elit, | |
| "external reason clause must respect the trail order (%d " | |
| "was assigned after %d)", | |
| elit, propagated_elit); | |
| } | |
| CB_REQUIRE ( | |
| !propagated_elit || propagated_lit_found, "cb_add_reason_clause_lit", | |
| elit, "external reason clause must contain the propagated literal."); | |
| // copy the state from adding clauses to enable adding external clauses | |
| // everywhere. | |
| tmp_lrat_chain = std::move (lrat_chain); | |
| lrat_chain.clear (); | |
| tmp_clause = std::move (clause); | |
| clause.clear (); | |
| tmp_original = std::move (original); | |
| original.clear (); | |
| tmp_eclause = std::move (external->eclause); | |
| external->eclause.clear (); | |
| for (auto &tmp : tmp_elits) | |
| external->add (tmp); | |
| tmp_elits.clear (); | |
| // copy the old state back. | |
| assert (lrat_chain.empty ()); | |
| assert (clause.empty ()); | |
| assert (original.empty ()); | |
| assert (external->eclause.empty ()); | |
| lrat_chain = std::move (tmp_lrat_chain); | |
| clause = std::move (tmp_clause); | |
| original = std::move (tmp_original); | |
| external->eclause = std::move (tmp_eclause); | |
| force_no_backtrack = false; | |
| from_propagator = false; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Recursively calls 'learn_external_reason_clause' to explain every | |
| // backward reachable externally propagated literal starting from 'ilit'. | |
| // | |
| void Internal::explain_reason (int ilit, Clause *reason, int &open) { | |
| if (!opts.exteagerreasons) | |
| return; | |
| #ifndef NDEBUG | |
| LOG (reason, "explain_reason of %d (open: %d)", ilit, open); | |
| #endif | |
| assert (reason); | |
| assert (reason != external_reason); | |
| for (const auto &other : *reason) { | |
| if (other == ilit) | |
| continue; | |
| Flags &f = flags (other); | |
| if (f.seen) | |
| continue; | |
| Var &v = var (other); | |
| if (!v.level) | |
| continue; | |
| assert (val (other) < 0); | |
| assert (v.level <= level); | |
| if (v.reason == external_reason) { | |
| v.reason = learn_external_reason_clause (-other, 0, true); | |
| } | |
| if (v.level && v.reason) { | |
| f.seen = true; | |
| open++; | |
| } | |
| } | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // In case external propagation was used, the reason clauses of the relevant | |
| // propagations must be learned lazily before/during conflict analysis. | |
| // While conflict analysis needs to analyze only the current level, lazy | |
| // clause learning must check every clause on every level that is backward | |
| // reachable from the conflicting clause to guarantee that the assignment | |
| // levels of the variables are accurate. So this explanation round is | |
| // separated from the conflict analysis, thereby guranteeing that the flags | |
| // and datastructures can be properly used later. | |
| // | |
| // This function must be called before the conflict analysis, in order to | |
| // guarantee that every relevant reason clause is indeed learned already and | |
| // to be sure that the levels of assignments are set correctly. | |
| // | |
| // Later TODO: experiment with bounded explanation (explain only those | |
| // literals that are directly used during conflict analysis + | |
| // minimizing/shrinking). The assignment levels are then only | |
| // over-approximated. | |
| // | |
| void Internal::explain_external_propagations () { | |
| assert (conflict); | |
| assert (clause.empty ()); | |
| Clause *reason = conflict; | |
| std::vector<int> seen_lits; | |
| int open = 0; // Seen but not explained literal | |
| explain_reason (0, reason, open); // marks conflict clause lits as seen | |
| int i = trail.size (); // Start at end-of-trail | |
| while (i > 0) { | |
| const int lit = trail[--i]; | |
| if (!flags (lit).seen) | |
| continue; | |
| seen_lits.push_back (lit); | |
| Var &v = var (lit); | |
| if (!v.level) | |
| continue; | |
| if (v.reason) { | |
| open--; | |
| explain_reason (lit, v.reason, open); | |
| } | |
| if (!open) | |
| break; | |
| } | |
| assert (!open); | |
| if (!opts.exteagerrecalc) { | |
| for (auto lit : seen_lits) { | |
| Flags &f = flags (lit); | |
| f.seen = false; | |
| } | |
| seen_lits.clear (); | |
| #ifndef NDEBUG | |
| for (auto idx : vars) { | |
| assert (!flags (idx).seen); | |
| } | |
| #endif | |
| } else { | |
| assert (external_prop && !external_prop_is_lazy && | |
| opts.exteagerreasons && opts.exteagerrecalc); | |
| // Traverse now in the opposite direction (from lower to higher levels) | |
| // and calculate the actual assignment level for the seen assignments. | |
| for (auto it = seen_lits.rbegin (); it != seen_lits.rend (); ++it) { | |
| const int lit = *it; | |
| Flags &f = flags (lit); | |
| Var &v = var (lit); | |
| if (v.reason) { | |
| int real_level = 0; | |
| for (const auto &other : *v.reason) { | |
| if (other == lit) | |
| continue; | |
| int tmp = var (other).level; | |
| if (tmp > real_level) | |
| real_level = tmp; | |
| } | |
| if (v.level && !real_level) { | |
| build_chain_for_units (lit, v.reason, 1); | |
| learn_unit_clause (lit); | |
| lrat_chain.clear (); | |
| v.reason = 0; | |
| } | |
| assert (v.level >= real_level); | |
| if (v.level > real_level) { | |
| v.level = real_level; | |
| } | |
| } | |
| f.seen = false; | |
| } | |
| } | |
| #if 0 // has been fuzzed extensively | |
| for (auto idx : vars) { | |
| assert (!flags (idx).seen); | |
| } | |
| #endif | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Learns the reason clause of the propagation of ilit from the | |
| // external propagator via 'add_external_clause'. | |
| // In case of falsified propagation steps, if the propagated literal is | |
| // already fixed to the opposite value, externalize will not necessarily | |
| // give back the original elit (but an equivalent one). To avoid that, in | |
| // falsified propagation cases the propagated elit is added as a second | |
| // argument. | |
| // | |
| Clause *Internal::learn_external_reason_clause (int ilit, | |
| int falsified_elit, | |
| bool no_backtrack) { | |
| assert (external->propagator); // REQ is defined by not allowing | |
| // unobserving during conflict | |
| stats.up_cb_prop_explain++; | |
| int elit = 0; | |
| if (!falsified_elit) { | |
| assert (!fixed (ilit)); | |
| elit = externalize (ilit); | |
| } else | |
| elit = falsified_elit; | |
| // Propagation reason clauses are by default assumed to be forgettable | |
| // irredundant. In case they would be unforgettably important, the | |
| // propagator can add them as an explicit unforgettable external | |
| // clause or set 'are_reasons_forgettable' to false. | |
| ext_clause_forgettable = external->propagator->are_reasons_forgettable; | |
| LOG ("ilit: %d, elit: %d", ilit, elit); | |
| add_external_clause (elit, no_backtrack); | |
| #ifndef NDEBUG | |
| if (!falsified_elit && newest_clause) { | |
| // Check if external propagation is correct wrt to the topological order | |
| // defined by the trail. In case it is a falsified external propagation | |
| // step, the order does not matter, the reason simply supposed to be a | |
| // falsified clause. | |
| const int propagated_ilit = ilit; | |
| for (auto const reason_ilit : *newest_clause) { | |
| assert (var (reason_ilit).trail <= var (propagated_ilit).trail); | |
| } | |
| } | |
| #endif | |
| return newest_clause; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Checks if the new clause forces backtracking, new assignments or conflict | |
| // analysis | |
| // | |
| void Internal::handle_external_clause (Clause *res, int64_t new_id) { | |
| if (from_propagator) | |
| stats.up_learn++; | |
| if (from_propagator && !res) | |
| stats.up_learn_unit++; | |
| // new unit clause. For now just backtrack. | |
| if (!res && (force_no_backtrack || | |
| (val (clause[0]) > 0 && opts.elevate > 0 && | |
| (opts.elevate > 1 || var (clause[0]).reason)))) { | |
| if (force_no_backtrack) | |
| did_external_prop = true; | |
| assert (level); | |
| assert (new_id); | |
| const int idx = vidx (clause[0]); | |
| assert (val (clause[0]) >= 0); | |
| assert (!flags (idx).eliminated ()); | |
| Var &v = var (idx); | |
| assert (val (clause[0])); | |
| v.level = 0; | |
| v.reason = 0; | |
| LOG ("elevate %s to level 0", LOGLIT (idx)); | |
| const unsigned uidx = vlit (clause[0]); | |
| if (lrat || frat) | |
| unit_clauses (uidx) = new_id; | |
| mark_fixed (clause[0]); | |
| return; | |
| } | |
| if (!res) { | |
| if (from_propagator) | |
| stats.up_learn_propagating++; | |
| const int lit = clause[0]; | |
| assert (!val (lit) || var (lit).level); | |
| if (val (lit)) | |
| backtrack_without_updating_phases (var (lit).level - 1); | |
| if (opts.elevate == -1 && val (lit)) | |
| backtrack_without_updating_phases (); | |
| assert (!val (lit)); | |
| assign_original_unit (new_id, lit); | |
| return; | |
| } | |
| // at level 0 we have to do nothing... | |
| if (!level) | |
| return; | |
| assert (res); | |
| assert (res->size >= 2); | |
| const int pos0 = res->literals[0]; | |
| const int pos1 = res->literals[1]; | |
| const int l1 = var (pos1).level; | |
| const int l0 = var (pos0).level; | |
| if (force_no_backtrack) { | |
| assert (from_propagator); | |
| assert (val (pos1) < 0); | |
| assert (val (pos0) >= 0); | |
| Var &v = var (pos0); | |
| if (v.level != l1) { | |
| stats.up_learn_lazy_elevate++; | |
| LOG (res, | |
| "elevate assignment of %s from level %d to level %d with lazy " | |
| "reason clause", | |
| LOGLIT (pos0), l0, l1); | |
| LOG ("elevate %s to level %d", LOGLIT (pos0), l1); | |
| } else | |
| LOG (res, "add assignment %s lazy reason clause", LOGLIT (pos0)); | |
| v.level = l1; | |
| return; | |
| } | |
| assert (!force_no_backtrack); | |
| if (val (pos1) >= 0) // do nothing | |
| return; | |
| if (val (pos0) < 0) { // conflicting | |
| assert (val (pos1) < 0); | |
| assert (0 < l1 && l1 <= var (pos0).level); | |
| if (opts.elevate == -1) | |
| backtrack_without_updating_phases (l1); | |
| // its better to backtrack instead of analyze without propagator | |
| // but analyze with propagaor | |
| if (val (pos0) && !from_propagator) | |
| backtrack_without_updating_phases (l0 - 1); | |
| else if (val (pos0) && from_propagator) { | |
| conflict = res; | |
| stats.up_learn_conflict++; | |
| } | |
| if (val (pos1) < 0 && !val (pos0)) | |
| search_assign_driving (pos0, res); | |
| return; | |
| } | |
| if (!val (pos0)) { // propagating | |
| assert (val (pos1) < 0); | |
| if (opts.elevate == -1) | |
| backtrack_without_updating_phases (l1); | |
| if (val (pos1) < 0 && !val (pos0)) | |
| search_assign_driving (pos0, res); | |
| return; | |
| } | |
| if (l0 <= l1) // no alternative reason | |
| return; | |
| assert (val (pos0) > 0); // elevating | |
| assert (val (pos1) < 0); | |
| // It would have propagated pos0 on an earlier level than it is | |
| // assigned | |
| // Find the highest literal based on trail-position of the clause | |
| size_t highest_idx = best_literal_to_watch (pos0, true); | |
| assert (highest_idx != 0); | |
| const int highest_literal = clause[highest_idx]; | |
| // highest trail level variable | |
| const Var &m = var (highest_literal); | |
| assert (l0 >= m.level); | |
| // best watch variable | |
| Var &v = var (pos0); | |
| // out-of-order if best watch smaller highest. | |
| if (v.trail < m.trail && opts.elevate > 0) { | |
| assert (highest_idx); | |
| int *lits = res->literals; | |
| if (highest_idx != 1) { | |
| lits[1] = highest_literal; | |
| lits[highest_idx] = pos1; | |
| } | |
| if (from_propagator) | |
| stats.up_learn_out_of_order++; | |
| LOG (res, | |
| "ignore out-of-order missed assignment of %s from level %d to " | |
| "level %d with new " | |
| "reason clause", | |
| LOGLIT (pos0), var (pos0).level, var (pos1).level); | |
| return; | |
| } | |
| // in order | |
| if (v.trail > m.trail && opts.elevate > 0 && | |
| (opts.elevate > 1 || v.reason)) { | |
| // If v.trail == m.trail, then the propagated literal is the | |
| // maximum as well, so no need to backtrack we simply reassign the | |
| // reason and level of the propagation | |
| LOG (res, | |
| "elevate assignment of %s from level %d to level %d with new " | |
| "reason clause", | |
| LOGLIT (pos0), var (pos0).level, var (pos1).level); | |
| assert (l1 < l0); | |
| assert (var (pos1).trail < var (pos0).trail); | |
| assert (var (highest_literal).trail < var (pos0).trail); | |
| v.level = l1; | |
| v.reason = res; | |
| LOG ("elevate %s to level %d", LOGLIT (pos0), l1); | |
| if (from_propagator) | |
| stats.up_learn_elevating++; | |
| if (out_of_order_level == -1 || l1 < out_of_order_level) | |
| out_of_order_level = l1; | |
| if (v.trail > out_of_order_trail) | |
| out_of_order_trail = v.trail; | |
| return; | |
| } | |
| // backtrack instead | |
| LOG (res, | |
| "backtrack due to missed assignment of %d from level %d to " | |
| "level %d with new reason clause", | |
| pos0, l0, l1); | |
| assert (!force_no_backtrack); | |
| if (opts.elevate == -1) | |
| backtrack_without_updating_phases (l1); | |
| else | |
| backtrack_without_updating_phases (l0 - 1); | |
| assert (!val (pos0) && val (pos1) < 0); | |
| search_assign_driving (pos0, res); | |
| assert (v.trail >= m.trail); | |
| assert (v.level == l1); | |
| assert (val (pos0) > 0 && val (pos1) < 0); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Asks the external propagator if the current solution is OK | |
| // by calling 'cb_check_found_model (model)'. | |
| // | |
| // The checked model is built up after everything is restored | |
| // from the reconstruction stack and every variable is reactivated | |
| // and so it is not just simply the trail (i.e. it can be expensive). | |
| // | |
| // If the external propagator approves the model, the function | |
| // returns true. | |
| // | |
| // If the propagator does not approve the model, the solver asks | |
| // the propagator to add an external clause. | |
| // This external clause, however, does NOT have to be falsified by | |
| // the current model. The possible cases and reactions are described | |
| // below in the function. The possible states after that function: | |
| // - A solution was found and accepted by the external propagator | |
| // - A conflicting clause was learned from the external propagator | |
| // - The empty clause was learned due to something new learned from | |
| // the external propagator. | |
| // | |
| // In case only new variables were introduced, but no new clauses were | |
| // added, the function will return without a conflict to the outer CDCL | |
| // loop, where the new (not yet satisfied) variables are recognized and | |
| // the search continues. | |
| bool Internal::external_check_solution () { | |
| if (!external_prop) | |
| return true; | |
| bool trail_changed = true; | |
| bool added_new_clauses = false; | |
| while (trail_changed || added_new_clauses) { | |
| notify_assignments (); | |
| if (!satisfied ()) | |
| break; | |
| LOG ("Final check by external propagator is invoked."); | |
| stats.up_cb_check_model++; | |
| external->reset_extended (); | |
| external->extend (); | |
| assert (notify_model_trail.empty ()); | |
| // Here the variables must be filtered by external->is_observed, | |
| // because fixed variables are internally not necessarily observed | |
| // anymore. | |
| if (trail_changed) { | |
| external->reset_extended (); | |
| external->extend (); | |
| // printf ("trail changed %b\n", trail_changed); | |
| for (int idx = 1; | |
| idx <= std::min ((int) external->is_observed.size () - 1, | |
| external->max_var); | |
| idx++) { | |
| if (!external->is_observed[idx]) | |
| continue; | |
| const int lit = external->ival (idx); | |
| notify_model_trail.push_back (lit); | |
| #ifndef NDEBUG | |
| #ifdef LOGGING | |
| bool p = external->vals[idx]; | |
| LOG ("evals[%d]: %d ival(%d): %d", idx, p, idx, lit); | |
| #endif | |
| #endif | |
| } | |
| } | |
| trail_changed = false; // to be on the safe side | |
| added_new_clauses = false; | |
| forced_backt_allowed = true; | |
| size_t assigned = num_assigned; | |
| int level_before = level; | |
| LOG_INTERACTION_START (cb_check_found_model); | |
| bool is_consistent = | |
| external->propagator->cb_check_found_model (notify_model_trail); | |
| LOG_INTERACTION_RETURN (cb_check_found_model, is_consistent); | |
| notify_model_trail.clear (); | |
| stats.up_cb++; | |
| forced_backt_allowed = false; | |
| if (num_assigned != assigned || level != level_before || | |
| propagated < trail.size ()) { | |
| // In case an external forced backtracking was performed, the CDCL | |
| // loop needs to continue withouth further checks of the model. | |
| trail_changed = true; | |
| return !conflict; | |
| } | |
| if (is_consistent) { | |
| LOG ("Found solution is approved by external propagator."); | |
| return true; | |
| } | |
| bool has_external_clause = ask_external_clause (); | |
| stats.up_cb++; | |
| stats.up_cb_add++; | |
| if (has_external_clause) | |
| LOG ("Found solution triggered new clauses from external " | |
| "propagator."); | |
| while (has_external_clause) { | |
| level_before = level; | |
| assigned = num_assigned; | |
| add_external_clause (0); | |
| bool trail_changed = | |
| (num_assigned != assigned || level != level_before || | |
| propagated < trail.size ()); | |
| added_new_clauses = true; | |
| // printf ("trail changed %b\n", trail_changed); | |
| // | |
| // There are many possible scenarios here: | |
| // - Learned conflicting clause: return to CDCL loop (conflict true) | |
| // - Learned conflicting unit clause that after backtrack+BCP leads | |
| // to | |
| // a new complete solution: force the outer loop to check the new | |
| // model (trail_changed is true, but (conflict & unsat) is false) | |
| // - Learned empty clause: return to CDCL loop (unsat true) | |
| // - Learned a non-conflicting unit clause: | |
| // Though it does not invalidate the current solution, the solver | |
| // will backtrack to the root level and will repropagate it. The | |
| // search will start again (saved phases hopefully make it quick), | |
| // but it is needed in order to guarantee that every fixed | |
| // variable is properly handled+notified (important for | |
| // incremental use cases). | |
| // - Otherwise: the solution is considered approved and the | |
| // CDCL-loop | |
| // can return with res = 10. | |
| // | |
| if (unsat || conflict || trail_changed) | |
| break; | |
| has_external_clause = ask_external_clause (); | |
| stats.up_cb++; | |
| stats.up_cb_add++; | |
| } | |
| LOG ("No more external clause to add."); | |
| if (unsat || conflict) | |
| break; | |
| } | |
| if (!unsat && conflict) { | |
| const int conflict_level = var (conflict->literals[0]).level; | |
| if (conflict_level != level) { | |
| backtrack_without_updating_phases (conflict_level); | |
| } | |
| } | |
| return !conflict; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Notify the external propagator that an observed variable got assigned. | |
| // | |
| void Internal::notify_assignments () { | |
| if (!external_prop || external_prop_is_lazy || private_steps) | |
| return; | |
| const size_t end_of_trail = trail.size (); | |
| if (notified >= end_of_trail) | |
| return; | |
| LOG ("notify external propagator about new assignments"); | |
| assert (notification_trail.empty ()); | |
| while (notified < end_of_trail) { | |
| int ilit = trail[notified++]; | |
| if (!observed (ilit)) | |
| continue; | |
| int elit = externalize (ilit); // TODO: double-check tainting | |
| assert (elit); | |
| if (external->ervars[abs (elit)]) | |
| continue; | |
| // Fixed variables might get mapped (during compact) to another | |
| // non-observed but fixed variable. | |
| // This happens on root level, so notification about their assignment | |
| // is already done. | |
| assert (external->observed (elit) || | |
| (fixed (ilit) && !external->ervars[abs (elit)])); | |
| if (!external->observed (elit)) | |
| continue; | |
| notification_trail.push_back (elit); | |
| } | |
| if (!notification_trail.empty ()) { | |
| LOG_INTERACTION_FOR (notify_assignment_batch, | |
| (int) notification_trail.size ()); | |
| external->propagator->notify_assignment (notification_trail); | |
| LOG_INTERACTION_END_FOR (notify_assignment_batch, | |
| (int) notification_trail.size ()); | |
| notification_trail.clear (); | |
| } | |
| return; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| void Internal::connect_propagator () { | |
| if (level) | |
| backtrack_without_updating_phases (); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Notify the external propagator that a new decision level is started. | |
| // | |
| void Internal::notify_decision () { | |
| if (!external_prop || external_prop_is_lazy || private_steps) | |
| return; | |
| notify_assignments (); | |
| notified_level = level; | |
| LOG_INTERACTION_FOR (notify_new_decision_level, level); | |
| external->propagator->notify_new_decision_level (); | |
| LOG_INTERACTION_END_FOR (notify_new_decision_level, level); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Notify the external propagator that backtrack to new_level. | |
| // | |
| void Internal::notify_backtrack (size_t new_level) { | |
| if (!external_prop || external_prop_is_lazy || private_steps) | |
| return; | |
| assert ((size_t) notified_level > new_level); | |
| LOG_INTERACTION_FOR (notify_backtrack, (int) new_level); | |
| external->propagator->notify_backtrack (new_level); | |
| LOG_INTERACTION_END_FOR (notify_backtrack, (int) new_level); | |
| notified_level = new_level; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Ask the external propagator if there is a suggested literal as next | |
| // decision. | |
| // | |
| int Internal::ask_decision () { | |
| if (!external_prop || external_prop_is_lazy || private_steps) | |
| return 0; | |
| assert (!unsat); | |
| assert (!conflict); | |
| notify_assignments (); | |
| int level_before = level; | |
| forced_backt_allowed = true; | |
| LOG_INTERACTION_START (cb_decide); | |
| int elit = external->propagator->cb_decide (); | |
| LOG_INTERACTION_RETURN (cb_decide, elit); | |
| forced_backt_allowed = false; | |
| stats.up_cb++; | |
| stats.up_cb_decide++; | |
| if (elit) | |
| stats.up_cb_decided++; | |
| if (level_before != level) { | |
| stats.up_cb_decide_force_bt++; | |
| propagate (); | |
| assert (!unsat); | |
| assert (!conflict); | |
| notify_assignments (); | |
| // In case the external propagator forced to backtrack below the | |
| // pseduo decision levels, we must go back to the CDCL loop instead of | |
| // making a decision. | |
| if ((size_t) level < assumptions.size () || | |
| ((size_t) level == assumptions.size () && constraint.size ())) { | |
| return 0; | |
| } | |
| return ask_decision (); | |
| } | |
| if (!elit) | |
| return 0; | |
| LOG ("external propagator proposes decision: %d", elit); | |
| CB_REQUIRE ( | |
| (size_t) abs (elit) < external->is_observed.size () && | |
| external->is_observed[abs (elit)], | |
| "cb_decide", elit, | |
| "external decisions are only allowed over observed variables."); | |
| assert (external->is_observed[abs (elit)]); | |
| int ilit = external->e2i[abs (elit)]; | |
| if (elit < 0) | |
| ilit = -ilit; | |
| assert (observed (ilit)); | |
| LOG ("Asking external propagator for decision returned: %d (internal: " | |
| "%d, fixed: %d, val: %d)", | |
| elit, ilit, fixed (ilit), val (ilit)); | |
| CB_REQUIRE ( | |
| !fixed (ilit) && !val (ilit), "cb_decide", elit, | |
| "external decisions are only allowed over unassigned variables."); | |
| return ilit; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Check if the clause is a forgettable clause coming from the external | |
| // propagator. | |
| // | |
| bool Internal::is_external_forgettable (int64_t id) { | |
| assert (opts.check); | |
| return (external->forgettable_original.find (id) != | |
| external->forgettable_original.end ()); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // When an external forgettable clause is deleted, it is marked in the | |
| // 'forgettable_original' hash, so that the internal model checking can | |
| // ignore it. | |
| // | |
| void Internal::mark_garbage_external_forgettable (int64_t id) { | |
| assert (opts.check); | |
| assert (is_external_forgettable (id)); | |
| LOG (external->forgettable_original[id], | |
| "forgettable external lemma is deleted:"); | |
| if (opts.checkfailed) { | |
| // Mark as removed by flipping the first flag to false. | |
| external->forgettable_original[id][0] = 0; | |
| } else | |
| external->forgettable_original.erase (id); | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Check that the literals in the clause are properly ordered. Used only | |
| // internally for debug purposes. | |
| // | |
| void Internal::check_watched_literal_invariants () { | |
| #ifndef NDEBUG | |
| int v0 = 0; | |
| int v1 = 0; | |
| if (val (clause[0]) > 0) | |
| v0 = 1; | |
| else if (val (clause[0]) < 0) | |
| v0 = -1; | |
| if (val (clause[1]) > 0) | |
| v1 = 1; | |
| else if (val (clause[1]) < 0) | |
| v1 = -1; | |
| assert (v0 >= v1); | |
| #endif | |
| if (val (clause[0]) > 0) { | |
| if (val (clause[1]) > 0) { // Case 1: Both literals are satisfied | |
| // They are ordered by lower to higher decision level | |
| assert (var (clause[0]).level <= var (clause[1]).level); | |
| // Every other literal of the clause is either | |
| // - satisfied at higher level | |
| // - unassigned | |
| // - falsified | |
| for (size_t i = 2; i < clause.size (); i++) | |
| assert (val (clause[i]) <= 0 || | |
| (var (clause[1]).level <= var (clause[i]).level)); | |
| } else if (val (clause[1]) == | |
| 0) { // Case 2: First satisfied, next unassigned | |
| // Every other literal of the clause is either | |
| // - unassigned | |
| // - falsified | |
| for (size_t i = 2; i < clause.size (); i++) | |
| assert (val (clause[i]) <= 0); | |
| } else { // Case 3: First satisfied, next falsified -> could have been | |
| // a reason of a previous propagation | |
| // Every other literal of the clause is falsified but at a lower | |
| // decision level | |
| for (size_t i = 2; i < clause.size (); i++) | |
| assert (val (clause[i]) < 0 && | |
| (var (clause[1]).level >= var (clause[i]).level)); | |
| } | |
| } else if (val (clause[0]) == 0) { | |
| if (val (clause[1]) == 0) { // Case 4: Both literals are unassigned | |
| // Every other literal of the clause is either | |
| // - unassigned | |
| // - falsified | |
| for (size_t i = 2; i < clause.size (); i++) | |
| assert (val (clause[i]) <= 0); | |
| } else { // Case 5: First unassigned, next falsified -> PROPAGATE | |
| // Every other literal of the clause is falsified but at a lower | |
| // decision level | |
| for (size_t i = 2; i < clause.size (); i++) | |
| assert (val (clause[i]) < 0 && | |
| (var (clause[1]).level >= var (clause[i]).level)); | |
| } | |
| } else { | |
| assert (val (clause[0]) < 0 && | |
| val (clause[1]) < 0); // Case 6: Both literals are falsified | |
| // They are ordered by higher to lower decision level | |
| assert (var (clause[0]).level >= var (clause[1]).level); | |
| // Every other literal of the clause is falsified, but at a lower | |
| // level | |
| for (size_t i = 2; i < clause.size (); i++) | |
| assert (val (clause[i]) < 0 && | |
| (var (clause[1]).level >= var (clause[i]).level)); | |
| } | |
| } | |
| #ifndef NDEBUG | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // An expensive function that can be used for deep-debug trail-related | |
| // issues in mobical. Do not use it unless it is really unavoidable. | |
| // | |
| // eq_class contains all the merged external literals that are currently | |
| // compacted to the internal literal of trail[0] and return true. | |
| // | |
| // In case trail[0] does not exists or is not on the root level, the | |
| // function returns false (indicating that there was no merger literal | |
| // found). | |
| // | |
| bool Internal::get_merged_literals (std::vector<int> &eq_class) { | |
| eq_class.clear (); | |
| if (!trail.size ()) | |
| return false; | |
| int ilit = trail[0]; | |
| size_t lit_level = var (ilit).level; | |
| if (!lit_level) { | |
| // Collect all the variables that are merged and mapped to that ilit | |
| int ivar = abs (ilit); | |
| if (external->e2i.use_hash_map) { | |
| for (auto id : external->e2i.h_e2i) { | |
| int o_elit = id.second; | |
| int o_ilit = id.first; | |
| int other = abs (o_elit); | |
| if (other == ivar) { | |
| if (o_elit == ilit) | |
| eq_class.push_back (o_ilit); | |
| else | |
| eq_class.push_back (-o_ilit); | |
| } | |
| } | |
| } else { | |
| for (size_t i = 1; i < external->e2i.vec_e2i.table.size (); ++i) { | |
| auto id = std::pair<int, int> (i, external->e2i[i]); | |
| int o_elit = id.second; | |
| int o_ilit = id.first; | |
| int other = abs (o_elit); | |
| if (other == ivar) { | |
| if (o_elit == ilit) | |
| eq_class.push_back (o_ilit); | |
| else | |
| eq_class.push_back (-o_ilit); | |
| } | |
| } | |
| } | |
| return true; | |
| } | |
| return false; | |
| } | |
| /*----------------------------------------------------------------------------*/ | |
| // | |
| // Collect all external variables that are FIXED internally. Again an | |
| // expensive function that should be called only for debugging in mobical. | |
| // | |
| // Do not use it unless it is really unavoidable. | |
| // | |
| void Internal::get_all_fixed_literals (std::vector<int> &fixed_lits) { | |
| fixed_lits.clear (); | |
| if (!trail.size ()) | |
| return; | |
| if (external->e2i.use_hash_map) | |
| for (auto id : external->e2i.h_e2i) { | |
| int ilit = id.second; | |
| int eidx = id.first; | |
| if (ilit && !external->ervars[eidx]) { | |
| Flags &f = flags (ilit); | |
| if (f.status == Flags::FIXED) { | |
| fixed_lits.push_back (vals[abs (ilit)] * eidx); | |
| } | |
| } | |
| } | |
| else | |
| for (size_t i = 1; i < external->e2i.vec_e2i.table.size (); ++i) { | |
| auto id = std::pair<int, int> (i, external->e2i[i]); | |
| int ilit = id.second; | |
| int eidx = id.first; | |
| if (ilit && !external->ervars[eidx]) { | |
| Flags &f = flags (ilit); | |
| if (f.status == Flags::FIXED) { | |
| fixed_lits.push_back (vals[abs (ilit)] * eidx); | |
| } | |
| } | |
| } | |
| } | |
| #endif | |
| } // namespace CaDiCaL |