blob: 187c0457dbe2474170c122ea262497e70ed77688 [file] [edit]
#include "internal.hpp"
namespace CaDiCaL {
// The global assignment stack can only be (partially) reset through
// 'backtrack' which is the only function using 'unassign' (inlined and thus
// local to this file). It turns out that 'unassign' does not need a
// specialization for 'probe' nor 'vivify' and thus it is shared.
inline void Internal::unassign (int lit) {
assert (val (lit) > 0);
set_val (lit, 0);
int idx = vidx (lit);
LOG ("unassign %d @ %d", lit, var (idx).level);
num_assigned--;
if (flags (idx).declared ())
return;
// In the standard EVSIDS variable decision heuristic of MiniSAT, we need
// to push variables which become unassigned back to the heap.
//
if (!scores.contains (idx))
scores.push_back (idx);
// For VMTF we need to update the 'queue.unassigned' pointer in case this
// variable sits after the variable to which 'queue.unassigned' currently
// points. See our SAT'15 paper for more details on this aspect.
//
if (queue.bumped < btab[idx])
update_queue_unassigned (idx);
}
/*------------------------------------------------------------------------*/
// Update the current target maximum assignment and also the very best
// assignment. Whether a trail produces a conflict is determined during
// propagation. Thus that all functions in the 'search' loop after
// propagation can assume that 'no_conflict_until' is valid. If a conflict
// is found then the trail before the last decision is used (see the end of
// 'propagate'). During backtracking we can then save this largest
// propagation conflict free assignment. It is saved as both 'target'
// assignment for picking decisions in 'stable' mode and if it is the
// largest ever such assignment also as 'best' assignment. This 'best'
// assignment can then be used in future stable decisions after the next
// 'rephase_best' overwrites saved phases with it.
void Internal::update_target_and_best () {
if (opts.rephase == 2 && !stable)
return;
bool reset = (rephased && stats.conflicts > last.rephase.conflicts);
if (reset) {
target_assigned = 0;
if (rephased == 'B')
best_assigned = 0; // update it again
}
if (no_conflict_until > target_assigned) {
save_assigned_phases (phases.target);
target_assigned = no_conflict_until;
LOG ("new target trail level %zu", target_assigned);
}
if (no_conflict_until > best_assigned) {
save_assigned_phases (phases.best);
best_assigned = no_conflict_until;
LOG ("new best trail level %zu", best_assigned);
}
if (reset) {
report (rephased);
rephased = 0;
}
}
/*------------------------------------------------------------------------*/
// backtrack to the given level (by default 0), updating the target and the
// best level if required. The function also handles out-of-order literals
// correcty by reassigning them (but you do have to repropagate afterwards!)
//
// For inprocessing use the version that does not update the phases.
void Internal::backtrack (int new_level) {
assert (new_level <= level);
if (new_level == level)
return;
update_target_and_best ();
backtrack_without_updating_phases (new_level);
}
// backtrack to the given level (by default 0), withour updating the target
// and the best level if required. The function also handles out-of-order
// literals correcty by reassigning them (but you do have to repropagate
// afterwards!) if you did out-of-order.
//
// Use `backtrack` to also save the phases. This one is mostly for
// inprocessing.
void Internal::backtrack_without_updating_phases (int new_level) {
assert (new_level <= level);
if (new_level == level)
return;
stats.backtracked++;
assert (num_assigned == trail.size ());
const size_t assigned = control[new_level + 1].trail;
LOG ("backtracking to decision level %d with decision %d and trail %zd",
new_level, control[new_level].decision, assigned);
const size_t end_of_trail = trail.size ();
size_t i = assigned, j = i;
#ifdef LOGGING
int unassigned = 0;
#endif
int reassigned = 0;
if (external_prop && !external_prop_is_lazy && !private_steps &&
notified > assigned) {
LOG ("external propagator is notified about some unassignments (trail: "
"%zd, notified: %zd).",
trail.size (), notified);
notified = assigned;
}
while (i < end_of_trail) {
int lit = trail[i++];
Var &v = var (lit);
if (v.level > new_level) {
unassign (lit);
#ifdef LOGGING
unassigned++;
#endif
} else {
// This is the essence of the SAT'18 paper on chronological
// backtracking. It is possible to just keep out-of-order assigned
// literals on the trail without breaking the solver (after some
// modifications to 'analyze' - see 'opts.chrono' guarded code there).
#ifdef LOGGING
if (!v.level) {
LOG ("reassign %d @ 0 unit clause %d", lit, lit);
assert (!lrat || unit_id (lit));
} else
LOG (v.reason, "reassign %d @ %d", lit, v.level);
#endif
trail[j] = lit;
v.trail = j++;
reassigned++;
}
}
trail.resize (j);
LOG ("unassigned %d literals %.0f%%", unassigned,
percent (unassigned, unassigned + reassigned));
LOG ("reassigned %d literals %.0f%%", reassigned,
percent (reassigned, unassigned + reassigned));
if (propagated > assigned)
propagated = assigned;
if (propagated2 > assigned)
propagated2 = assigned;
if (no_conflict_until > assigned)
no_conflict_until = assigned;
propergated = 0; // Always go back to root-level.
assert (notified <= assigned + reassigned);
control.resize (new_level + 1);
if (earliest_changed_val) {
assert (opts.ilb);
if (!val (earliest_changed_val)) {
earliest_changed_val = 0;
}
}
assert (num_assigned == trail.size ());
notify_backtrack (new_level);
if (reassigned) {
notify_assignments ();
}
level = new_level;
}
} // namespace CaDiCaL