| #include "internal.hpp" | |
| #include "flags.hpp" | |
| #include "profile.hpp" | |
| namespace CaDiCaL { | |
| /*------------------------------------------------------------------------*/ | |
| static Clause external_reason_clause; | |
| Internal::Internal () | |
| : mode (SEARCH), unsat (false), iterating (false), | |
| localsearching (false), lookingahead (false), preprocessing (false), | |
| protected_reasons (false), force_saved_phase (false), | |
| searching_lucky_phases (false), stable (false), reported (false), | |
| external_prop (false), did_external_prop (false), | |
| external_prop_is_lazy (true), forced_backt_allowed (false), | |
| private_steps (false), out_of_order_level (-1), | |
| out_of_order_trail (-1), rephased (0), vsize (0), max_var (0), | |
| clause_id (0), original_id (0), reserved_ids (0), conflict_id (0), | |
| saved_decisions (0), concluded (false), lrat (false), frat (false), | |
| new_binary_since_dedup (true), level (0), vals (0), score_inc (1.0), | |
| scores (this), conflict (0), ignore (0), | |
| external_reason (&external_reason_clause), newest_clause (0), | |
| force_no_backtrack (false), from_propagator (false), | |
| ext_clause_forgettable (false), unsat_constraint (false), | |
| marked_failed (true), sweep_incomplete (false), | |
| earliest_changed_val (0), notified (0), notified_level (0), | |
| probe_reason (0), propagated (0), propagated2 (0), propergated (0), | |
| best_assigned (0), target_assigned (0), no_conflict_until (0), | |
| randomized_deciding (false), citten (nullptr), num_assigned (0), | |
| proof (0), opts (this), | |
| #ifndef QUIET | |
| profiles (this), force_phase_messages (false), | |
| #endif | |
| arena (this), prefix ("c "), internal (this), external (0), | |
| termination_forced (false), vars (this->max_var), | |
| lits (this->max_var) { | |
| control.emplace_back (0, 0); | |
| // The 'dummy_binary' is used in 'try_to_subsume_clause' to fake a real | |
| // clause (which then can be used to subsume or strengthen the given | |
| // clause in one routine for both binary and non binary clauses) and | |
| // in walk (which is only used as a placeholder in the watch lists | |
| // when logging is off, since the clause is not accessed). This | |
| // fake binary clause is always kept non-redundant (and not-moved etc.) | |
| // due to the following 'memset'. Only literals will be changed. | |
| // In a previous version we used local automatic allocated 'Clause' on | |
| // the stack, which became incompatible with several compilers (see the | |
| // discussion on flexible array member in 'Clause.cpp'). | |
| size_t bytes = Clause::bytes (2); | |
| dummy_binary = (Clause *) new char[bytes]; | |
| memset (dummy_binary, 0, bytes); | |
| dummy_binary->size = 2; | |
| /*with C++17: static_*/ assert (max_used == (1 << USED_SIZE) - 1); | |
| } | |
| Internal::~Internal () { | |
| delete[] (char *) dummy_binary; | |
| for (const auto &c : clauses) | |
| delete_clause (c); | |
| if (proof) | |
| delete proof; | |
| for (auto &tracer : tracers) | |
| delete tracer; | |
| for (auto &filetracer : file_tracers) | |
| delete filetracer; | |
| for (auto &stattracer : stat_tracers) | |
| delete stattracer; | |
| if (vals) { | |
| vals -= vsize; | |
| delete[] vals; | |
| } | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Values in 'vals' can be accessed in the range '[-max_var,max_var]' that | |
| // is directly by a literal. This is crucial for performance. By shifting | |
| // the start of 'vals' appropriately, we achieve that negative offsets from | |
| // the start of 'vals' can be used. We also need to set both values at | |
| // 'lit' and '-lit' during assignments. In MiniSAT integer literals are | |
| // encoded, using the least significant bit as negation. This avoids taking | |
| // the 'abs ()' (as in our solution) and thus also avoids a branch in the | |
| // hot-spot of the solver (clause traversal in propagation). That solution | |
| // requires another (branch less) negation of the values though and | |
| // debugging is harder since literals occur only encoded in clauses. | |
| // The main draw-back of our solution is that we have to shift the memory | |
| // and access it through negative indices, which looks less clean (but still | |
| // as far I can tell is properly defined C / C++). | |
| void Internal::enlarge_vals (size_t new_vsize) { | |
| signed char *new_vals; | |
| const size_t bytes = 2u * new_vsize; | |
| new_vals = new signed char[bytes]; // g++-4.8 does not like ... { 0 }; | |
| memset (new_vals, 0, bytes); | |
| new_vals += new_vsize; | |
| if (vals) { | |
| memcpy (new_vals - max_var, vals - max_var, 2u * max_var + 1u); | |
| vals -= vsize; | |
| delete[] vals; | |
| } else | |
| assert (!vsize); | |
| vals = new_vals; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // This function enlarges all data structures. You should use it only if you | |
| // add many literals at once. Otherwise, use `reserve_vars` followed by | |
| // importing all variables. | |
| // | |
| // Remark: for the first literal we cannot distinguish between not watching | |
| // and watching. Therefore, we resize the watch lists, because we are | |
| // watching anyway. | |
| void Internal::enlarge (int new_max_var) { | |
| // New variables can be created that can invoke enlarge anytime (via calls | |
| // during ipasir-up call-backs), thus assuming (!level) is not correct | |
| size_t new_vsize = vsize ? vsize : 1 + (size_t) new_max_var; | |
| while (new_vsize <= (size_t) new_max_var) | |
| new_vsize *= 2; | |
| LOG ("enlarge internal size from %zd to new size %zd", vsize, new_vsize); | |
| // Ordered in the size of allocated memory (larger block first). | |
| if (lrat || frat) | |
| enlarge_zero (unit_clause_idx, 2 * new_vsize); | |
| if (!vsize || watching ()) | |
| enlarge_init (wtab, 2 * new_vsize, {}); | |
| if (!otab.empty ()) | |
| enlarge_init (otab, 2 * new_vsize, Occs ()); | |
| if (!ntab.empty ()) | |
| enlarge_zero (ntab, 2 * new_vsize); | |
| enlarge_only (vtab, new_vsize); | |
| enlarge_zero (parents, new_vsize); | |
| enlarge_only (links, new_vsize); | |
| enlarge_zero (btab, new_vsize); | |
| enlarge_zero (gtab, new_vsize); | |
| enlarge_zero (stab, new_vsize); | |
| enlarge_init (ptab, 2 * new_vsize, -1); | |
| enlarge_only (ftab, new_vsize); | |
| if (external->propagator) | |
| enlarge_zero (relevanttab, new_vsize); | |
| const signed char val = opts.phase ? 1 : -1; | |
| enlarge_init (phases.saved, new_vsize, val); | |
| enlarge_zero (phases.forced, new_vsize); | |
| enlarge_zero (phases.target, new_vsize); | |
| enlarge_zero (phases.best, new_vsize); | |
| enlarge_zero (phases.prev, new_vsize); | |
| enlarge_zero (marks, new_vsize); | |
| // keep this last to avoid memory issues on deallocation. | |
| enlarge_vals (new_vsize); | |
| vsize = new_vsize; | |
| } | |
| // This function enlarges enough to do backtracking (without updating the | |
| // phases only!) and (if needed) watched and occurrence table, but it does | |
| // not enlarge everything. This is done later when importing all variables. | |
| // It does enlarge watch lists (only if you watching) and occurrence lists | |
| // (only if you are having occs). | |
| // | |
| // Remark: for the first literal we cannot distinguish between not watching | |
| // and watching. Therefore, we resize the watch lists, because we are | |
| // watching anyway. | |
| void Internal::reserve_vars (int new_min_vsize) { | |
| if ((size_t) new_min_vsize < vsize) | |
| return; | |
| size_t new_vsize = vsize ? 2 * vsize : 1 + (size_t) max_var; | |
| while (new_vsize <= (size_t) new_min_vsize) | |
| new_vsize *= 2; | |
| LOG ("reserving %d new internal variables, reserved so far: %d", | |
| (int) new_vsize - max_var, max_var); | |
| if (lrat || frat) | |
| enlarge_zero (unit_clause_idx, 2 * new_vsize); | |
| // keep this before enlarge_vals | |
| if (!vsize || watching ()) { | |
| enlarge_only (wtab, 2 * new_vsize); | |
| } | |
| if (!otab.empty ()) | |
| enlarge_init (otab, 2 * new_vsize, Occs ()); | |
| if (!ntab.empty ()) | |
| enlarge_zero (ntab, 2 * new_vsize); | |
| enlarge_only (vtab, new_vsize); | |
| enlarge_zero (btab, new_vsize); | |
| enlarge_zero (stab, new_vsize); | |
| enlarge_only (ftab, new_vsize); | |
| if (external) | |
| enlarge_zero (relevanttab, new_vsize); | |
| enlarge_only (phases.saved, new_vsize); | |
| enlarge_zero (marks, new_vsize); | |
| // keep this last to avoid memory issues on deallocation. | |
| enlarge_vals (new_vsize); | |
| vsize = new_vsize; | |
| } | |
| void Internal::add_original_lit (int lit) { | |
| assert (abs (lit) <= max_var); | |
| if (lit) { | |
| original.push_back (lit); | |
| } else { | |
| const int64_t id = | |
| original_id < reserved_ids ? ++original_id : ++clause_id; | |
| if (proof) { | |
| // Use the external form of the clause for printing in proof | |
| // Externalize(internalized literal) != external literal | |
| assert (!original.size () || !external->eclause.empty ()); | |
| proof->add_external_original_clause (id, false, external->eclause); | |
| } | |
| if (internal->opts.check && | |
| (internal->opts.checkwitness || internal->opts.checkfailed)) { | |
| bool forgettable = from_propagator && ext_clause_forgettable; | |
| if (forgettable && opts.check) { | |
| assert (!original.size () || !external->eclause.empty ()); | |
| // initialize the vector to the correct size directly | |
| external->forgettable_original[id].reserve ( | |
| 1 + external->eclause.size ()); | |
| // First integer is the presence-flag (even if the clause is | |
| // empty) | |
| external->forgettable_original[id].push_back (1); | |
| for (auto const &elit : external->eclause) | |
| external->forgettable_original[id].push_back (elit); | |
| LOG (external->eclause, | |
| "clause added to external forgettable map:"); | |
| } | |
| } | |
| add_new_original_clause (id); | |
| original.clear (); | |
| } | |
| } | |
| void Internal::finish_added_clause_with_id (int64_t id, bool restore) { | |
| if (proof) { | |
| // Use the external form of the clause for printing in proof | |
| // Externalize(internalized literal) != external literal | |
| assert (!original.size () || !external->eclause.empty ()); | |
| proof->add_external_original_clause (id, false, external->eclause, | |
| restore); | |
| } | |
| add_new_original_clause (id); | |
| original.clear (); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::reserve_ids (int64_t number) { | |
| // return; | |
| LOG ("reserving %" PRId64 " ids", number); | |
| assert (number >= 0); | |
| assert (!clause_id && !reserved_ids && !original_id); | |
| clause_id = reserved_ids = number; | |
| if (proof) | |
| proof->begin_proof (reserved_ids); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| #ifdef PROFILE_MODE | |
| // Separating these makes it easier to profile stable and unstable search. | |
| bool Internal::propagate_wrapper () { | |
| if (stable) | |
| return propagate_stable (); | |
| else | |
| return propagate_unstable (); | |
| } | |
| void Internal::analyze_wrapper () { | |
| if (stable) | |
| analyze_stable (); | |
| else | |
| analyze_unstable (); | |
| } | |
| int Internal::decide_wrapper () { | |
| if (stable) | |
| return decide_stable (); | |
| else | |
| return decide_unstable (); | |
| } | |
| #endif | |
| /*------------------------------------------------------------------------*/ | |
| // This is the main CDCL loop with interleaved inprocessing. | |
| int Internal::cdcl_loop_with_inprocessing () { | |
| int res = 0; | |
| PROFILE_SCOPE_SEARCH (search, stable); | |
| if (stable) { | |
| report ('['); | |
| } else { | |
| report ('{'); | |
| } | |
| while (!res) { | |
| if (unsat) | |
| res = 20; | |
| else if (unsat_constraint) | |
| res = 20; | |
| else if (!propagate_wrapper ()) | |
| analyze_wrapper (); // propagate and analyze | |
| else if (iterating) | |
| iterate (); // report learned unit | |
| else if (terminated_asynchronously ()) // externally terminated | |
| break; | |
| else if (!external_propagate () || unsat) { // external propagation | |
| if (unsat) | |
| continue; | |
| else | |
| analyze (); | |
| } else if (satisfied ()) { // found model | |
| if (!external_check_solution () || unsat) { | |
| if (unsat) | |
| continue; | |
| else | |
| analyze (); | |
| } else if (satisfied ()) | |
| res = 10; | |
| } else if (search_limits_hit ()) | |
| break; // decision or conflict limit | |
| else if (terminated_asynchronously ()) // externally terminated | |
| break; | |
| else if (restarting ()) | |
| restart (); // restart by backtracking | |
| else if (rephasing ()) | |
| rephase (); // reset variable phases | |
| else if (reducing ()) | |
| reduce (); // collect useless clauses | |
| else if (inprobing ()) | |
| inprobe (); // schedule of inprocessing | |
| else if (ineliminating ()) | |
| elim (); // variable elimination | |
| else if (compacting ()) | |
| compact (); // collect variables | |
| else if (conditioning ()) | |
| condition (); // globally blocked clauses | |
| else | |
| res = decide (); // next decision | |
| } | |
| if (stable) { | |
| report (']'); | |
| } else { | |
| report ('}'); | |
| } | |
| return res; | |
| } | |
| int Internal::propagate_assumptions () { | |
| activating_all_new_imported_literals (); | |
| if (proof) | |
| proof->solve_query (); | |
| if (opts.ilb) { | |
| sort_and_reuse_assumptions (); | |
| assert (opts.ilb == 2 || (size_t) level <= assumptions.size ()); | |
| stats.ilb_triggers++; | |
| stats.ilb_success += (level > 0); | |
| stats.ilb_reuse_levels += level; | |
| if (level) { | |
| assert (control.size () > 1); | |
| stats.ilb_reuse_literals += num_assigned - control[1].trail; | |
| } | |
| } | |
| init_search_limits (); | |
| init_report_limits (); | |
| int res = already_solved (); // root-level propagation is done here | |
| int last_assumption_level = assumptions.size (); | |
| if (constraint.size ()) | |
| last_assumption_level++; | |
| if (!res) { | |
| restore_clauses (); | |
| while (!res) { | |
| if (unsat) | |
| res = 20; | |
| else if (unsat_constraint) | |
| res = 20; | |
| else if (!propagate ()) { | |
| // let analyze run to get failed assumptions | |
| analyze (); | |
| } else if (!external_propagate () || unsat) { // external propagation | |
| if (unsat) | |
| continue; | |
| else | |
| analyze (); | |
| } else if (satisfied ()) { // found model | |
| if (!external_check_solution () || unsat) { | |
| if (unsat) | |
| continue; | |
| else | |
| analyze (); | |
| } else if (satisfied ()) | |
| res = 10; | |
| } else if (search_limits_hit ()) | |
| break; // decision or conflict limit | |
| else if (terminated_asynchronously ()) // externally terminated | |
| break; | |
| else { | |
| if (level >= last_assumption_level) | |
| break; | |
| res = decide (); | |
| } | |
| } | |
| } | |
| if (unsat || unsat_constraint) | |
| res = 20; | |
| if (!res && satisfied ()) | |
| res = 10; | |
| finalize (res); | |
| reset_solving (); | |
| report_solving (res); | |
| return res; | |
| } | |
| void Internal::implied (std::vector<int> &entrailed) { | |
| int last_assumption_level = assumptions.size (); | |
| size_t trail_limit = trail.size (); | |
| if (level > last_assumption_level) | |
| trail_limit = control[last_assumption_level + 1].trail; | |
| for (size_t i = 0; i < trail_limit; i++) | |
| entrailed.push_back (trail[i]); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Most of the limits are only initialized in the first 'solve' call and | |
| // increased as in a stand-alone non-incremental SAT call except for those | |
| // explicitly marked as being reset below. | |
| void Internal::init_report_limits () { | |
| reported = false; | |
| lim.report = 0; | |
| lim.recompute_tier = 5000; | |
| } | |
| void Internal::init_preprocessing_limits () { | |
| const bool incremental = lim.initialized; | |
| if (incremental) | |
| LOG ("reinitializing preprocessing limits incrementally"); | |
| else | |
| LOG ("initializing preprocessing limits and increments"); | |
| const char *mode = 0; | |
| /*----------------------------------------------------------------------*/ | |
| if (incremental) | |
| mode = "keeping"; | |
| else { | |
| last.elim.marked = -1; | |
| lim.elim = stats.conflicts + scale (opts.elimint); | |
| mode = "initial"; | |
| } | |
| (void) mode; | |
| LOG ("%s elim limit %" PRId64 " after %" PRId64 " conflicts", mode, | |
| lim.elim, lim.elim - stats.conflicts); | |
| // Initialize and reset elimination bounds in any case. | |
| lim.elimbound = opts.elimboundmin; | |
| LOG ("elimination bound %" PRId64 "", lim.elimbound); | |
| /*----------------------------------------------------------------------*/ | |
| if (!incremental) { | |
| last.ternary.marked = -1; // TODO this should not be necessary... | |
| lim.compact = stats.conflicts + opts.compactint; | |
| LOG ("initial compact limit %" PRId64 " increment %" PRId64 "", | |
| lim.compact, lim.compact - stats.conflicts); | |
| } | |
| /*----------------------------------------------------------------------*/ | |
| if (incremental) | |
| mode = "keeping"; | |
| else { | |
| double delta = | |
| stats.clauses_irredundant ? log10 (stats.clauses_irredundant) : 100; | |
| delta = delta * delta; | |
| lim.inprobe = stats.conflicts + opts.inprobeint * delta; | |
| mode = "initial"; | |
| } | |
| (void) mode; | |
| LOG ("%s probe limit %" PRId64 " after %" PRId64 " conflicts", mode, | |
| lim.inprobe, lim.inprobe - stats.conflicts); | |
| /*----------------------------------------------------------------------*/ | |
| if (incremental) | |
| mode = "keeping"; | |
| else { | |
| lim.condition = stats.conflicts + opts.conditionint; | |
| mode = "initial"; | |
| } | |
| LOG ("%s condition limit %" PRId64 " increment %" PRId64, mode, | |
| lim.condition, lim.condition - stats.conflicts); | |
| /*----------------------------------------------------------------------*/ | |
| // Initial preprocessing rounds. | |
| if (inc.preprocessing <= 0) { | |
| lim.preprocessing = 0; | |
| LOG ("no preprocessing"); | |
| } else { | |
| lim.preprocessing = inc.preprocessing; | |
| LOG ("limiting to %" PRId64 " preprocessing rounds", lim.preprocessing); | |
| } | |
| #ifndef LOGGING | |
| (void) mode; | |
| #endif | |
| } | |
| void Internal::init_search_limits () { | |
| const bool incremental = lim.initialized; | |
| if (incremental) | |
| LOG ("reinitializing search limits incrementally"); | |
| else | |
| LOG ("initializing search limits and increments"); | |
| const char *mode = 0; | |
| /*----------------------------------------------------------------------*/ | |
| if (incremental) | |
| mode = "keeping"; | |
| else { | |
| last.reduce.conflicts = -1; | |
| lim.reduce = stats.conflicts + opts.reduceinit; | |
| mode = "initial"; | |
| } | |
| (void) mode; | |
| LOG ("%s reduce limit %" PRId64 " after %" PRId64 " conflicts", mode, | |
| lim.reduce, lim.reduce - stats.conflicts); | |
| /*----------------------------------------------------------------------*/ | |
| if (incremental) | |
| mode = "keeping"; | |
| else { | |
| lim.flush = opts.flushint; | |
| inc.flush = opts.flushint; | |
| mode = "initial"; | |
| } | |
| (void) mode; | |
| LOG ("%s flush limit %" PRId64 " interval %" PRId64 "", mode, lim.flush, | |
| inc.flush); | |
| /*----------------------------------------------------------------------*/ | |
| // Initialize or reset 'rephase' limits in any case. | |
| lim.rephase = stats.conflicts + opts.rephaseint; | |
| lim.rephased[0] = lim.rephased[1] = 0; | |
| last.stabilize.rephased = 0; | |
| LOG ("new rephase limit %" PRId64 " after %" PRId64 " conflicts", | |
| lim.rephase, lim.rephase - stats.conflicts); | |
| /*----------------------------------------------------------------------*/ | |
| // Initialize or reset 'restart' limits in any case. | |
| lim.restart = stats.conflicts + opts.restartint; | |
| LOG ("new restart limit %" PRId64 " increment %" PRId64 "", lim.restart, | |
| lim.restart - stats.conflicts); | |
| /*----------------------------------------------------------------------*/ | |
| if (!incremental) { | |
| stable = opts.stabilize && opts.stabilizeonly; | |
| if (stable) | |
| LOG ("starting in always forced stable phase"); | |
| else | |
| LOG ("starting in default non-stable phase"); | |
| init_averages (); | |
| } else if (opts.stabilize && opts.stabilizeonly) { | |
| LOG ("keeping always forced stable phase"); | |
| assert (stable); | |
| } else if (stable) { | |
| LOG ("switching back to default non-stable phase"); | |
| stable = false; | |
| swap_averages (); | |
| } else | |
| LOG ("keeping non-stable phase"); | |
| inc.stabilize = 0; | |
| last.stabilize.conflicts = stats.conflicts; | |
| lim.stabilize = stats.conflicts + opts.stabilizeinit; | |
| last.stabilize.ticks = stats.ticks_search_unstable; | |
| stats.stable_phases_current = 0; | |
| LOG ("new ticks-based stabilize limit %" PRId64 " after %d conflicts", | |
| lim.stabilize, (int) opts.stabilizeinit); | |
| if (opts.stabilize && opts.reluctant && opts.reluctantint) { | |
| LOG ("new restart reluctant doubling sequence period %d", | |
| opts.reluctant); | |
| reluctant.enable (opts.reluctantint, opts.reluctantmax); | |
| } else | |
| reluctant.disable (); | |
| /*----------------------------------------------------------------------*/ | |
| // Conflict and decision limits. | |
| if (inc.conflicts < 0) { | |
| lim.conflicts = -1; | |
| LOG ("no limit on conflicts"); | |
| } else { | |
| lim.conflicts = stats.conflicts + inc.conflicts; | |
| LOG ("conflict limit after %" PRId64 " conflicts at %" PRId64 | |
| " conflicts", | |
| inc.conflicts, lim.conflicts); | |
| } | |
| if (inc.decisions < 0) { | |
| lim.decisions = -1; | |
| LOG ("no limit on decisions"); | |
| } else { | |
| lim.decisions = stats.decisions + inc.decisions; | |
| LOG ("decision limit after %" PRId64 " decisions at %" PRId64 | |
| " decisions", | |
| inc.decisions, lim.decisions); | |
| } | |
| if (inc.ticks < 0) { | |
| lim.ticks = -1; | |
| LOG ("no limit on ticks"); | |
| } else { | |
| lim.ticks = | |
| stats.ticks_search_unstable + stats.ticks_search_stable + inc.ticks; | |
| LOG ("ticks limit after %" PRId64 " ticks at %" PRId64 " ticks", | |
| inc.ticks, lim.ticks); | |
| } | |
| /*----------------------------------------------------------------------*/ | |
| // Initial preprocessing rounds. | |
| if (inc.localsearch <= 0) { | |
| lim.localsearch = 0; | |
| LOG ("no local search"); | |
| } else { | |
| lim.localsearch = inc.localsearch; | |
| LOG ("limiting to %" PRId64 " local search rounds", lim.localsearch); | |
| } | |
| /*----------------------------------------------------------------------*/ | |
| // tier 1 and tier 2 limits | |
| if (incremental && opts.recomputetier) { | |
| for (auto m : {true, false}) | |
| for (auto &u : stats.used[m]) | |
| u = 0; | |
| stats.bump_used[0] = 0; | |
| stats.bump_used[1] = 0; | |
| for (auto u : {true, false}) { | |
| tier1[u] = max (tier1[u], opts.tier1minglue ? opts.tier1minglue : 2); | |
| tier2[u] = max (tier2[u], opts.tier2minglue ? opts.tier2minglue : 6); | |
| } | |
| stats.recomputed_tiers = 0; | |
| } | |
| /*----------------------------------------------------------------------*/ | |
| // clause decaying | |
| if (incremental) | |
| last.incremental_decay.last_id = 0; | |
| else { | |
| lim.incremental_decay = opts.incdecayint; | |
| } | |
| /*----------------------------------------------------------------------*/ | |
| if (incremental) | |
| mode = "keeping"; | |
| else { | |
| lim.random_decision = stats.conflicts + opts.randecinit; | |
| mode = "initial"; | |
| } | |
| (void) mode; | |
| LOG ("%s randomize decision limit %" PRId64 " after %" PRId64 | |
| " conflicts", | |
| mode, lim.random_decision, lim.random_decision - stats.conflicts); | |
| /*----------------------------------------------------------------------*/ | |
| lim.initialized = true; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| bool Internal::preprocess_round (int round, bool &triggered) { | |
| (void) round; | |
| if (unsat) | |
| return false; | |
| if (!max_var) | |
| return false; | |
| if (terminated_asynchronously ()) | |
| return false; | |
| PROFILE_SCOPE (preprocess); | |
| if (!triggered) | |
| report ('('), triggered = true; | |
| struct { | |
| int64_t vars, clauses; | |
| } before, after; | |
| before.vars = active (); | |
| before.clauses = stats.clauses_now_irr; | |
| stats.preprocessings++; | |
| assert (!preprocessing); | |
| preprocessing = true; | |
| PHASE ("preprocessing", stats.preprocessings, | |
| "starting round %d with %" PRId64 " variables and %" PRId64 | |
| " clauses", | |
| round, before.vars, before.clauses); | |
| int old_elimbound = lim.elimbound; | |
| int old_eliminated = stats.vars_all_elim; | |
| if (opts.inprobing) | |
| inprobe (false); | |
| if (opts.elim) | |
| elim (false); | |
| if (opts.condition) | |
| condition (false); | |
| after.vars = active (); | |
| after.clauses = stats.clauses_now_irr; | |
| assert (preprocessing); | |
| preprocessing = false; | |
| PHASE ("preprocessing", stats.preprocessings, | |
| "finished round %d with %" PRId64 " variables and %" PRId64 | |
| " clauses", | |
| round, after.vars, after.clauses); | |
| report ('P'); | |
| if (unsat) | |
| return false; | |
| if (after.vars != before.vars) | |
| return true; | |
| if (old_elimbound < lim.elimbound) | |
| return true; | |
| if (old_eliminated < stats.vars_all_elim) | |
| return true; | |
| return false; | |
| } | |
| // for now counts as one of the preprocessing rounds TODO: change this? | |
| void Internal::preprocess_quickly (bool always, bool &triggered) { | |
| if (unsat) | |
| return; | |
| if (!max_var) | |
| return; | |
| if (terminated_asynchronously ()) | |
| return; | |
| if (!opts.preprocesslight) | |
| return; | |
| if (!always && stats.searches > 1) | |
| return; | |
| PROFILE_SCOPE (preprocess); | |
| #ifndef QUIET | |
| struct { | |
| int64_t vars, clauses; | |
| } before, after; | |
| before.vars = active (); | |
| before.clauses = stats.clauses_now_irr; | |
| #endif | |
| // stats.preprocessings++; | |
| assert (!preprocessing); | |
| preprocessing = true; | |
| triggered = true; | |
| report ('('); | |
| PHASE ("preprocessing", stats.preprocessings, | |
| "starting with %" PRId64 " variables and %" PRId64 " clauses", | |
| before.vars, before.clauses); | |
| if (extract_gates (true)) | |
| decompose (); | |
| binary_clauses_backbone (); | |
| if (sweep ()) | |
| decompose (); | |
| mark_duplicated_binary_clauses_as_garbage (); | |
| factor (); | |
| if (opts.fastelim) | |
| elimfast (); | |
| #ifndef QUIET | |
| after.vars = active (); | |
| after.clauses = stats.clauses_now_irr; | |
| #endif | |
| assert (preprocessing); | |
| preprocessing = false; | |
| PHASE ("preprocessing", stats.preprocessings, | |
| "finished with %" PRId64 " variables and %" PRId64 " clauses", | |
| after.vars, after.clauses); | |
| report ('P'); | |
| } | |
| int Internal::preprocess (bool always) { | |
| int res = 0; | |
| if (res) | |
| return res; | |
| bool preprecessing_triggered = false; | |
| if (opts.deduplicateallinit && !stats.deduplicate_rounds) | |
| deduplicate_all_clauses (); | |
| preprocess_quickly (always, preprecessing_triggered); | |
| for (int i = 0; i < lim.preprocessing; i++) | |
| if (!preprocess_round (i, preprecessing_triggered)) | |
| break; | |
| if (preprecessing_triggered) | |
| report (')'); | |
| if (unsat) | |
| return 20; | |
| return 0; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| int Internal::try_to_satisfy_formula_by_saved_phases () { | |
| LOG ("satisfying formula by saved phases"); | |
| assert (!level); | |
| assert (!force_saved_phase); | |
| assert (propagated == trail.size ()); | |
| force_saved_phase = true; | |
| if (external_prop) { | |
| assert (!level); | |
| LOG ("external notifications are turned off during preprocessing."); | |
| private_steps = true; | |
| } | |
| int res = 0; | |
| while (!res) { | |
| if (satisfied ()) { | |
| LOG ("formula indeed satisfied by saved phases"); | |
| res = 10; | |
| } else if (decide ()) { | |
| LOG ("inconsistent assumptions with redundant clauses and phases"); | |
| res = 20; | |
| } else if (!propagate ()) { | |
| LOG ("saved phases do not satisfy redundant clauses"); | |
| assert (level > 0); | |
| backtrack (); | |
| conflict = 0; // ignore conflict | |
| assert (!res); | |
| break; | |
| } | |
| } | |
| assert (force_saved_phase); | |
| force_saved_phase = false; | |
| if (external_prop) { | |
| private_steps = false; | |
| LOG ("external notifications are turned back on."); | |
| if (!level) | |
| notify_assignments (); // In case fixed assignments were found. | |
| else { | |
| renotify_trail_after_local_search (); | |
| } | |
| } | |
| return res; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::produce_failed_assumptions () { | |
| LOG ("producing failed assumptions"); | |
| assert (!level); | |
| assert (!assumptions.empty ()); | |
| while (!unsat) { | |
| assert (!satisfied ()); | |
| notify_assignments (); | |
| if (decide ()) | |
| break; | |
| while (!unsat && !propagate ()) | |
| analyze (); | |
| } | |
| notify_assignments (); | |
| if (unsat) | |
| LOG ("formula is actually unsatisfiable unconditionally"); | |
| else | |
| LOG ("assumptions indeed failing"); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| int Internal::local_search_round (int round) { | |
| assert (round > 0); | |
| if (unsat) | |
| return false; | |
| if (!max_var) | |
| return false; | |
| if (terminated_asynchronously ()) | |
| return false; | |
| MODE_SCOPE_WALK (WALK); | |
| PROFILE_SCOPE_WALK (walk); | |
| assert (!localsearching); | |
| localsearching = true; | |
| // Determine propagation limit quadratically scaled with rounds. | |
| // | |
| int64_t limit = opts.walkmineffinit; | |
| limit *= round; | |
| if (LONG_MAX / round > limit) | |
| limit *= round; | |
| else | |
| limit = LONG_MAX; | |
| int res; | |
| if (opts.walkalgo == 1) | |
| res = walk_ddfw_round (limit, true); | |
| else | |
| res = walk_round (limit, true); | |
| assert (localsearching); | |
| localsearching = false; | |
| report ('L'); | |
| return res; | |
| } | |
| int Internal::local_search () { | |
| if (unsat) | |
| return 0; | |
| if (!max_var) | |
| return 0; | |
| if (!opts.walk) | |
| return 0; | |
| if (constraint.size ()) | |
| return 0; | |
| if (!lim.localsearch) | |
| return 0; | |
| int res = 0; | |
| assert (imports.empty ()); | |
| assert (!level); | |
| for (int i = 1; !res && i <= lim.localsearch; i++) | |
| res = local_search_round (i); | |
| if (res == 10) { | |
| LOG ("local search determined formula to be satisfiable"); | |
| assert (!stats.walk_minimum); | |
| res = try_to_satisfy_formula_by_saved_phases (); | |
| } else if (res == 20) { | |
| LOG ("local search determined assumptions to be inconsistent"); | |
| assert (!assumptions.empty ()); | |
| } | |
| return res; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // if preprocess_only is false and opts.ilb is true we do not preprocess | |
| // such that we do not have to backtrack to level 0. | |
| // | |
| int Internal::solve (bool preprocess_only) { | |
| assert (clause.empty ()); | |
| stats.searches++; | |
| PROFILE_SCOPE (solve); | |
| activating_all_new_imported_literals (); | |
| if (proof) | |
| proof->solve_query (); | |
| if (opts.ilb) { | |
| sort_and_reuse_assumptions (); | |
| assert (opts.ilb || (size_t) level <= assumptions.size ()); | |
| stats.ilb_triggers++; | |
| stats.ilb_success += (level > 0); | |
| stats.ilb_reuse_levels += level; | |
| if (level) { | |
| assert (control.size () > 1); | |
| stats.ilb_reuse_literals += num_assigned - control[1].trail; | |
| } | |
| if (external->propagator) | |
| renotify_trail_after_ilb (); | |
| } | |
| if (preprocess_only) | |
| LOG ("internal solving in preprocessing only mode"); | |
| else | |
| LOG ("internal solving in full mode"); | |
| init_report_limits (); | |
| int res = already_solved (); | |
| if (!res && preprocess_only && level) | |
| backtrack (); | |
| if (!res) | |
| res = restore_clauses (); | |
| if (!res || (res == 10 && external_prop)) { | |
| init_preprocessing_limits (); | |
| if (!preprocess_only) | |
| init_search_limits (); | |
| } | |
| if (!preprocess_only) { | |
| if (!res && !level) | |
| res = local_search (); | |
| } | |
| bool run_lucky = | |
| (stats.conflicts >= | |
| lim.lucky); // cannot be in lucky, because we run it twice | |
| bool update_lucky_limits = !opts.luckylate; // update in the second | |
| // run if there is any only run lucky late if some preprocessing was | |
| // done, which corresponds to preprocesslight (only done during the | |
| // first search), or if the user forced preprocessing, or there are | |
| // full preprocessing round. | |
| bool will_do_any_preprocessing = | |
| ((opts.preprocesslight && stats.searches <= 1) || preprocess_only || | |
| lim.preprocessing); | |
| if (!preprocess_only && !res && !level && opts.luckyearly && run_lucky) | |
| res = lucky_phases (update_lucky_limits); | |
| if (!res && !level) | |
| res = preprocess (preprocess_only); | |
| if (!preprocess_only) { | |
| if (!res && !level && will_do_any_preprocessing && opts.luckylate && | |
| run_lucky) | |
| res = lucky_phases (true); | |
| if (!res && !level) | |
| res = local_search (); | |
| if (!res) | |
| decay_clauses_upon_incremental_clauses (); | |
| if (!res || (res == 10 && external_prop)) { | |
| if (res == 10 && external_prop && level) | |
| backtrack (); | |
| res = cdcl_loop_with_inprocessing (); | |
| } | |
| } | |
| finalize (res); | |
| reset_solving (); | |
| report_solving (res); | |
| return res; | |
| } | |
| int Internal::already_solved () { | |
| int res = 0; | |
| if (unsat || unsat_constraint) { | |
| LOG ("already inconsistent"); | |
| res = 20; | |
| } else { | |
| if (level && !opts.ilb) | |
| backtrack (); | |
| if (!level && !propagate ()) { | |
| LOG ("root level propagation produces conflict"); | |
| learn_empty_clause (); | |
| res = 20; | |
| } | |
| if (max_var == 0 && res == 0) | |
| res = 10; | |
| } | |
| return res; | |
| } | |
| void Internal::report_solving (int res) { | |
| if (res == 10) | |
| report ('1'); | |
| else if (res == 20) | |
| report ('0'); | |
| else | |
| report ('?'); | |
| } | |
| void Internal::reset_solving () { | |
| if (termination_forced) { | |
| // TODO this leads potentially to a data race if the external | |
| // user is calling 'terminate' twice within one 'solve' call. | |
| // A proper solution would be to guard / protect setting the | |
| // 'termination_forced' flag and only allow it during solving and | |
| // ignore it otherwise thus also the second time it is called during a | |
| // 'solve' call. We could move resetting it also the start of | |
| // 'solve'. | |
| // | |
| termination_forced = false; | |
| LOG ("reset forced termination"); | |
| } | |
| } | |
| int Internal::restore_clauses () { | |
| int res = 0; | |
| if (!opts.restoreall && external->tainted.empty ()) { | |
| LOG ("no tainted literals and nothing to restore"); | |
| report ('*'); | |
| } else { | |
| report ('+'); | |
| // remove_garbage_binaries (); | |
| external->restore (); | |
| internal->report ('r'); | |
| if (!unsat && !level && !propagate ()) { | |
| LOG ("root level propagation after restore produces conflict"); | |
| learn_empty_clause (); | |
| res = 20; | |
| } | |
| } | |
| return res; | |
| } | |
| CubesWithStatus Internal::solve_and_generate_cubes (int depth, | |
| int min_depth) { | |
| assert (clause.empty ()); | |
| PROFILE_SCOPE (lookahead); | |
| assert (!lookingahead); | |
| lookingahead = true; | |
| if (proof) | |
| proof->solve_query (); | |
| activating_all_new_imported_literals (); | |
| if (external_prop) { | |
| if (level) { | |
| // Combining lookahead with external propagator is limited | |
| // Note that lookahead_probing (); would also force backtrack anyway | |
| backtrack (); | |
| } | |
| LOG ("external notifications are turned off during preprocessing."); | |
| private_steps = true; | |
| } | |
| CubesWithStatus cubes; | |
| int res = already_solved (); | |
| if (res == 0) | |
| res = restore_clauses (); | |
| if (unsat) | |
| res = 20; | |
| if (res != 0) | |
| res = solve (true); | |
| cubes.status = res; | |
| if (!res) | |
| cubes = generate_cubes (depth, min_depth); | |
| lookingahead = false; | |
| res = cubes.status; | |
| finalize (res); | |
| reset_solving (); | |
| report_solving (res); | |
| PROFILE_SCOPE_EARLY_EXIT (lookahead); | |
| if (external_prop) { | |
| private_steps = false; | |
| LOG ("external notifications are turned back on."); | |
| notify_assignments (); // In case fixed assignments were found. | |
| } | |
| return cubes; | |
| } | |
| int Internal::lookahead (int &lit) { | |
| assert (clause.empty ()); | |
| PROFILE_SCOPE (lookahead); | |
| assert (!lookingahead); | |
| lookingahead = true; | |
| if (proof) | |
| proof->solve_query (); | |
| activating_all_new_imported_literals (); | |
| if (external_prop) { | |
| if (level) { | |
| // Combining lookahead with external propagator is limited | |
| // Note that lookahead_probing (); would also force backtrack anyway | |
| backtrack (); | |
| } | |
| LOG ("external notifications are turned off during preprocessing."); | |
| private_steps = true; | |
| } | |
| int res = already_solved (); | |
| if (!res) | |
| res = restore_clauses (); | |
| if (unsat) // restore_clauses only returns 20 if the propagation returns | |
| // unsat | |
| res = 20; | |
| if (!res) | |
| lit = lookahead_probing (); | |
| else if (res == 20) | |
| lit = INT_MIN; | |
| if (lit == INT_MIN) { | |
| assert (unsat || unsat_constraint); | |
| res = 20; | |
| lit = 0; | |
| } else | |
| assert (!unsat && !unsat_constraint); | |
| finalize (res); | |
| reset_solving (); | |
| report_solving (res); | |
| assert (lookingahead); | |
| lookingahead = false; | |
| PROFILE_SCOPE_EARLY_EXIT (lookahead); | |
| if (external_prop) { | |
| private_steps = false; | |
| LOG ("external notifications are turned back on."); | |
| notify_assignments (); // In case fixed assignments were found. | |
| } | |
| return res; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::finalize (int res) { | |
| if (!proof) | |
| return; | |
| LOG ("finalizing"); | |
| // finalize external units | |
| if (frat) { | |
| for (const auto &evar : external->vars) { | |
| assert (evar > 0); | |
| const auto eidx = 2 * evar; | |
| int sign = 1; | |
| int64_t id = external->ext_units[eidx]; | |
| if (!id) { | |
| sign = -1; | |
| id = external->ext_units[eidx + 1]; | |
| } | |
| if (id) { | |
| proof->finalize_external_unit (id, evar * sign); | |
| } | |
| } | |
| // finalize internal units | |
| for (const auto &lit : lits) { | |
| const auto elit = externalize (lit); | |
| if (elit) { | |
| const unsigned eidx = (elit < 0) + 2u * (unsigned) abs (elit); | |
| const int64_t id = external->ext_units[eidx]; | |
| if (id) { | |
| assert (unit_clauses (vlit (lit)) == id); | |
| continue; | |
| } | |
| } | |
| const int64_t id = unit_clauses (vlit (lit)); | |
| if (!id) | |
| continue; | |
| proof->finalize_unit (id, lit); | |
| } | |
| // See the discussion in 'propagate' on why garbage binary clauses | |
| // stick around. | |
| for (const auto &c : clauses) | |
| if (!c->garbage || (c->size == 2 && !c->flushed)) | |
| proof->finalize_clause (c); | |
| // finalize conflict and proof | |
| if (conflict_id) { | |
| proof->finalize_clause (conflict_id, {}); | |
| } | |
| } | |
| proof->report_status (res, conflict_id); | |
| if (res == 10) | |
| external->conclude_sat (); | |
| else if (res == 20) | |
| conclude_unsat (); | |
| else if (!res) | |
| external->conclude_unknown (); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::print_statistics () { | |
| stats.print (this); | |
| for (auto &st : stat_tracers) | |
| st->print_stats (); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Only useful for debugging purposes. | |
| void Internal::dump (Clause *c) { | |
| for (const auto &lit : *c) | |
| printf ("%d ", lit); | |
| printf ("0\n"); | |
| } | |
| void Internal::dump () { | |
| int64_t m = assumptions.size (); | |
| for (auto idx : vars) | |
| if (fixed (idx)) | |
| m++; | |
| for (const auto &c : clauses) | |
| if (!c->garbage) | |
| m++; | |
| printf ("p cnf %d %" PRId64 "\n", max_var, m); | |
| for (auto idx : vars) { | |
| const int tmp = fixed (idx); | |
| if (tmp) | |
| printf ("%d 0\n", tmp < 0 ? -idx : idx); | |
| } | |
| for (const auto &c : clauses) | |
| if (!c->garbage) | |
| dump (c); | |
| for (const auto &lit : assumptions) | |
| printf ("%d 0\n", lit); | |
| fflush (stdout); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| bool Internal::traverse_constraint (ClauseIterator &it) { | |
| if (constraint.empty () && !unsat_constraint) | |
| return true; | |
| vector<int> eclause; | |
| if (unsat) | |
| return it.clause (eclause); | |
| LOG (constraint, "traversing constraint"); | |
| bool satisfied = false; | |
| for (auto ilit : constraint) { | |
| const int tmp = fixed (ilit); | |
| if (tmp > 0) { | |
| satisfied = true; | |
| break; | |
| } | |
| if (tmp < 0) | |
| continue; | |
| const int elit = externalize (ilit); | |
| eclause.push_back (elit); | |
| } | |
| if (!satisfied && !it.clause (eclause)) | |
| return false; | |
| return true; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| bool Internal::traverse_clauses (ClauseIterator &it) { | |
| vector<int> eclause; | |
| if (unsat) | |
| return it.clause (eclause); | |
| for (const auto &c : clauses) { | |
| if (c->garbage) | |
| continue; | |
| if (c->redundant) | |
| continue; | |
| bool satisfied = false; | |
| for (const auto &ilit : *c) { | |
| const int tmp = fixed (ilit); | |
| if (tmp > 0) { | |
| satisfied = true; | |
| break; | |
| } | |
| if (tmp < 0) | |
| continue; | |
| const int elit = externalize (ilit); | |
| eclause.push_back (elit); | |
| } | |
| if (!satisfied && !it.clause (eclause)) | |
| return false; | |
| eclause.clear (); | |
| } | |
| return true; | |
| } | |
| void Internal::declare_variable (int ilit) { | |
| int iidx = abs (ilit); | |
| reserve_vars (iidx); | |
| assert ((size_t) iidx < vsize); | |
| if (iidx >= max_var) { | |
| stats.vars_unused += (iidx - max_var); | |
| stats.vars_inactive += (iidx - max_var); | |
| max_var = iidx; | |
| } | |
| Flags &f = internal->flags (ilit); | |
| if (f.declared ()) | |
| return; | |
| LOG ("declaring %s", LOGLIT (ilit)); | |
| mark_declared (ilit); | |
| imports.push_back (vidx (ilit)); | |
| } | |
| // Now we come to the part where we import literals. We either import | |
| // them in order of appearance, in order of numbering, or the reversed | |
| // versions of that. The sorting is based on the external ordering not | |
| // the internal ordering. | |
| void Internal::activating_all_new_imported_literals () { | |
| LOG (imports, "activating all new variables"); | |
| if (imports.empty ()) | |
| return; | |
| int new_max_var = 0; | |
| if (opts.varindexorder) { | |
| // I experimented with MSORT, but this was slower on | |
| // lru_10.sanitized (14 vs 16s) | |
| std::sort (begin (imports), end (imports), [&] (int l, int o) { | |
| assert (l > 0 && o > 0); | |
| return i2e[vidx (l)] < i2e[vidx (o)]; | |
| }); | |
| new_max_var = imports.back (); | |
| } else { | |
| auto max_it = | |
| std::max_element (imports.begin (), imports.end (), | |
| [] (int a, int b) { return (a) < (b); }); | |
| assert (max_it != imports.end ()); | |
| new_max_var = *max_it; | |
| } | |
| enlarge (new_max_var); | |
| if (!opts.varprioritizefirst) | |
| std::reverse (begin (imports), end (imports)); | |
| for (auto idx : imports) { | |
| assert (idx > 0); | |
| auto &f = flags (idx); | |
| // the user asked for it but did not put the literal in any | |
| // clause, we still should declare it (for future use by the user) | |
| if (f.unused ()) | |
| mark_declared (idx); | |
| // for units, we do have to enqueue (in case we backtracked and already | |
| // added it) | |
| if (f.fixed ()) { | |
| continue; | |
| } | |
| if (f.declared ()) | |
| mark_active (idx); | |
| // otherwise, reactivating literal | |
| init_enqueue (idx); | |
| // due to propagation and backtracking, the literal might have already | |
| // been added | |
| if (!scores.contains (idx)) { | |
| LOG ("pushing %s to the scores", LOGLIT (idx)); | |
| scores.push_back (idx); | |
| } | |
| assert (scores.contains (idx)); | |
| assert (f.active () || f.fixed ()); | |
| } | |
| stats.vars += imports.size (); | |
| imports.clear (); | |
| check_var_stats (); | |
| #ifndef NDEBUG | |
| for (auto c : clauses) { | |
| if (c->garbage) | |
| continue; | |
| for (auto lit : *c) { | |
| assert (flags (lit).active () || flags (lit).fixed () || | |
| flags (lit).eliminated ()); | |
| } | |
| } | |
| for (auto v : vars) { | |
| assert (flags (v).unused () || internal->val (v) || | |
| scores.contains (v)); | |
| if (flags (v).unused ()) | |
| assert (!scores.contains (v)); | |
| } | |
| check_queue (); | |
| #endif | |
| } | |
| } // namespace CaDiCaL |