blob: c1d14a57ee10e91e9659fb3a9665a29c52658bf1 [file] [edit]
#include "flags.hpp"
#include "internal.hpp"
#include "message.hpp"
#include "util.hpp"
#include <cstdint>
namespace CaDiCaL {
External::External (Internal *i)
: internal (i), max_var (0), vsize (0), extended (false),
concluded (false), terminator (0), learner (0), fixed_listener (0),
propagator (0), trace_api_file (0), solution (0), vars (max_var) {
assert (internal);
assert (!internal->external);
internal->external = this;
e2i.limit_to_check = internal->opts.varinitswitch;
e2i.internal = internal;
e2i.incremental_scaling = internal->opts.varswitchscale;
checkfrozen = internal->opts.checkfrozen;
}
External::~External () {
if (solution)
delete[] solution;
}
void External::enlarge (int new_max_var) {
assert (!extended);
size_t new_vsize = vsize ? 2 * vsize : 1 + (size_t) new_max_var;
while (new_vsize <= (size_t) new_max_var)
new_vsize *= 2;
LOG ("enlarge external size from %zd to new size %zd", vsize, new_vsize);
vsize = new_vsize;
}
int External::declare_var (int new_var, bool extension) {
int ilit = internal_lit (new_var);
if (!ilit) {
if (!internal->opts.varkeepname)
ilit = internal->max_var + 1;
else {
ilit = new_var;
if (internal->i2e.size () > (size_t) ilit && internal->i2e[ilit]) {
LOG ("the slot is already used by %d, giving the next available "
"name",
internal->i2e[ilit]);
ilit = internal->max_var + 1;
}
}
if (internal->i2e.size () <= (size_t) ilit) {
reserve_at_least (internal->i2e, ilit + 1);
internal->i2e.resize (ilit + 1);
}
LOG ("new mapping external %d to internal %d", new_var, ilit);
e2i.insert (new_var, ilit);
assert (e2i[new_var] == ilit);
LOG ("%d -> %d =?= %d", new_var, ilit, e2i[new_var]);
internal->i2e[ilit] = new_var;
internal->declare_variable (ilit);
assert (internal->max_var >= ilit);
}
if (extension)
internal->stats.variables_extension++;
else
internal->stats.variables_original++;
return e2i[new_var];
}
void External::reserve (int new_max_var) {
assert (max_var < new_max_var);
internal->reserve_vars (new_max_var);
if (internal->lrat || internal->frat)
reserve_at_least (ext_units, 2 * new_max_var + 2);
if (internal->lrat)
reserve_at_least (ext_flags, new_max_var + 1);
reserve_at_least (ervars, new_max_var + 1);
reserve_at_least (internal->i2e, new_max_var + 1);
if (!max_var) {
assert (e2i.empty ());
if (internal->lrat || internal->frat) {
ext_units.push_back (0);
ext_units.push_back (0);
}
if (internal->lrat)
ext_flags.push_back (0);
ervars.push_back (0);
assert (internal->i2e.empty ());
internal->i2e.push_back (0);
}
unsigned eidx;
for (eidx = max_var + 1u; eidx <= (unsigned) new_max_var; eidx++) {
if (internal->lrat || internal->frat) {
ext_units.push_back (0);
ext_units.push_back (0);
}
if (internal->lrat)
ext_flags.push_back (0);
ervars.push_back (0);
}
if (checkfrozen)
if (new_max_var >= (int64_t) moltentab.size ())
moltentab.resize (1 + (size_t) new_max_var, false);
assert (internal->i2e.size () == (size_t) internal->max_var + 1);
assert (eidx == (size_t) new_max_var + 1);
max_var = new_max_var;
}
void External::init (int new_max_var, bool extension) {
assert (extension || !extended);
LOG ("%d external variables from %d", new_max_var, max_var);
assert (!max_var ||
internal->i2e.size () == (size_t) internal->max_var + 1);
if (new_max_var <= max_var) {
declare_var (new_max_var, extension);
return;
}
LOG ("initialized %d external variables", new_max_var - max_var);
reserve (new_max_var);
declare_var (new_max_var, extension);
assert ((!internal->lrat && !internal->frat) ||
ext_units.size () == (size_t) new_max_var * 2 + 2);
}
/*------------------------------------------------------------------------*/
void External::reset_assumptions () {
assumptions.clear ();
internal->reset_assumptions ();
}
void External::reset_concluded () {
concluded = false;
internal->reset_concluded ();
}
void External::reset_constraint () {
if (constraint.empty ()) {
// nothing do to
} else if (constraint.back ()) {
LOG ("the constraint was not finished");
// the constraint was not imported yet and thus not finalized, so
// just dropping it
constraint.clear ();
internal->constraint.clear ();
} else {
constraint.clear ();
internal->reset_constraint ();
}
}
void External::reset_extended () {
if (!extended)
return;
LOG ("reset extended");
extended = false;
}
void External::reset_limits () { internal->reset_limits (); }
/*------------------------------------------------------------------------*/
// when extension is true, elit should be a fresh variable and
// we can set a flag that it is an extension variable.
// This is then used in the API contracts, that extension variables are
// never part of the input
int External::internalize (int elit, bool extension) {
int ilit;
if (elit) {
assert (elit != INT_MIN);
const int eidx = abs (elit);
if (extension && eidx <= max_var)
FATAL ("can not add a definition for an already used variable %d",
eidx);
if (eidx > max_var) {
init (eidx, extension);
}
if (extension) {
assert (ervars.size () > (size_t) eidx);
ervars[eidx] = true;
}
ilit = e2i.find (eidx).second;
if (!ilit)
ilit = declare_var (eidx, false);
if (elit < 0)
ilit = -ilit;
if (!ilit) {
assert (internal->max_var < INT_MAX);
ilit = internal->max_var + 1u;
internal->reserve_vars (ilit);
LOG ("mapping external %d to internal %d", eidx, ilit);
e2i.insert (eidx, ilit);
internal->i2e.push_back (eidx);
assert (internal->i2e[ilit] == eidx);
assert (e2i[eidx] == ilit);
if (elit < 0)
ilit = -ilit;
}
if (checkfrozen) {
assert (eidx < (int64_t) moltentab.size ());
if (moltentab[eidx])
FATAL ("can not reuse molten literal %d", eidx);
}
Flags &f = internal->flags (ilit);
if (f.status == Flags::UNUSED)
internal->declare_variable (ilit);
else if (f.status != Flags::DECLARED && f.status != Flags::ACTIVE &&
f.status != Flags::FIXED) {
internal->reactivate (ilit);
}
f.factored = extension;
assert (!extension || f.elim);
if (extension)
f.elim = false;
if (!marked (tainted, elit) && marked (witness, -elit)) {
assert (!checkfrozen);
LOG ("marking tainted %d", elit);
mark (tainted, elit);
}
} else
ilit = 0;
return ilit;
}
void External::add (int elit) {
assert (elit != INT_MIN);
reset_extended ();
bool forgettable = false;
if (internal->opts.check &&
(internal->opts.checkwitness || internal->opts.checkfailed)) {
forgettable =
internal->from_propagator && internal->ext_clause_forgettable;
// Forgettable clauses (coming from the external propagator) are not
// saved into the external 'original' stack. They are stored separately
// in external 'forgettable_original', from where they are deleted when
// the corresponding clause is deleted (actually deleted, not just
// marked as garbage).
if (!forgettable)
original.push_back (elit);
}
const int ilit = internalize (elit);
assert (!elit == !ilit);
// The external literals of the new clause must be saved for later
// when the proof is printed during add_original_lit (0)
if (elit && (internal->proof || forgettable)) {
eclause.push_back (elit);
if (internal->lrat) {
// actually find unit of -elit (flips elit < 0)
unsigned eidx = (elit > 0) + 2u * (unsigned) abs (elit);
assert ((size_t) eidx < ext_units.size ());
const int64_t id = ext_units[eidx];
bool added = ext_flags[abs (elit)];
if (id && !added) {
ext_flags[abs (elit)] = true;
internal->lrat_chain.push_back (id);
}
}
}
if (!elit && internal->proof && internal->lrat) {
for (const auto &elit : eclause) {
ext_flags[abs (elit)] = false;
}
}
if (elit)
LOG ("adding external %d as internal %d", elit, ilit);
if (internal->external_prop)
internal->activating_all_new_imported_literals ();
internal->add_original_lit (ilit);
// Clean-up saved external literals once proof line is printed
if (!elit && (internal->proof || forgettable))
eclause.clear ();
}
void External::assume (int elit) {
assert (elit);
reset_extended ();
if (internal->proof)
internal->proof->add_assumption (elit);
assumptions.push_back (elit);
const int ilit = internalize (elit);
assert (ilit);
LOG ("assuming external %d as internal %d", elit, ilit);
internal->assume (ilit);
}
bool External::flip (int elit) {
assert (elit);
assert (elit != INT_MIN);
assert (!propagator);
int eidx = abs (elit);
if (eidx > max_var)
return false;
if (marked (witness, elit))
return false;
int ilit = e2i.find_or_default (eidx, 0);
if (!ilit)
return false;
bool res = internal->flip (ilit);
if (res && extended)
reset_extended ();
return res;
}
bool External::flippable (int elit) {
assert (elit);
assert (elit != INT_MIN);
assert (!propagator);
int eidx = abs (elit);
if (eidx > max_var)
return false;
if (marked (witness, elit))
return false;
int ilit = e2i.find_or_default (eidx, 0);
if (!ilit)
return false;
return internal->flippable (ilit);
}
bool External::failed (int elit) {
assert (elit);
assert (elit != INT_MIN);
int eidx = abs (elit);
if (eidx > max_var)
return 0;
int ilit = e2i.find_or_default (eidx, 0);
if (!ilit)
return 0;
if (elit < 0)
ilit = -ilit;
return internal->failed (ilit);
}
void External::constrain (int elit) {
if (constraint.size () && !constraint.back ()) {
LOG (constraint, "replacing previous constraint");
reset_constraint ();
}
assert (elit != INT_MIN);
reset_extended ();
const int ilit = internalize (elit);
assert (!elit == !ilit);
if (elit)
LOG ("adding external %d as internal %d to constraint", elit, ilit);
else if (!elit && internal->proof) {
internal->proof->add_constraint (constraint);
}
constraint.push_back (elit);
internal->constrain (ilit);
}
bool External::failed_constraint () {
return internal->failed_constraint ();
}
void External::phase (int elit) {
assert (elit);
assert (elit != INT_MIN);
// this test is a bit stupid,
// it is triggering an assertion, but we
// could simply add those to the other if...
if (std::abs (elit) > max_var) {
reset_extended ();
}
const int ilit = internalize (elit);
if (!internal->imports.empty ()) {
if (extended)
reset_extended ();
internal->activating_all_new_imported_literals ();
}
internal->phase (ilit);
}
void External::unphase (int elit) {
assert (elit);
assert (elit != INT_MIN);
int eidx = abs (elit);
if (eidx > max_var) {
UNUSED:
LOG ("resetting forced phase of unused external %d ignored", elit);
return;
}
int ilit = e2i.find (eidx).second;
if (!ilit)
goto UNUSED;
if (elit < 0)
ilit = -ilit;
if (!internal->imports.empty ()) {
if (extended)
reset_extended ();
internal->activating_all_new_imported_literals ();
}
internal->unphase (ilit);
}
/*------------------------------------------------------------------------*/
// External propagation related functions
//
// Note that when an already assigned variable is added as observed, the
// solver will backtrack to undo this assignment.
//
void External::add_observed_var (int elit) {
assert (propagator); // REQ is in Solver::add_observed_var
assert (elit);
assert (elit != INT_MIN);
int eidx = abs (elit);
// if (eidx <= max_var &&
// (marked (witness, elit) || marked (witness, -elit))) {
// LOG ("Error, only clean variables are allowed to become observed.");
// assert (false);
// // TODO: here needs to come the taint and restore of the newly
// // observed variable. Restore_clauses must be called before continue.
// // LOG ("marking tainted %d", elit);
// // mark (tainted, elit);
// // mark (tainted, -elit);
// // restore_clauses ...
// }
if (eidx >= (int64_t) is_observed.size ())
is_observed.resize (1 + (size_t) eidx, false);
else if (is_observed[eidx])
return;
reset_extended (); // tainting!
// internalize and in particular declares the variables
int ilit = internalize (elit);
// taint and restore of the newly observed variable.
// Restore_clauses must be called before continue.
// alternative to above
/*
if (marked (witness, elit)) {
mark (tainted, -elit);
}
if (marked (witness, -elit)) {
mark (tainted, elit);
}
if (!tainted.empty ()) {
const bool was_from_propagator = internal->from_propagator;
assert (!internal->force_no_backtrack);
internal->from_propagator = 0;
if (internal->force_no_backtrack)
FATAL ("can not add ");
restore_clauses ();
internal->from_propagator = was_from_propagator;
}
*/
LOG ("marking %d as externally watched", eidx);
// Will do the necessary internalization
freeze (elit);
is_observed[eidx] = true;
// internal add-observed-var backtracks to a lower decision level to
// unassign the variable in case it was already assigned previously (but
// not on the current level)
internal->add_observed_var (ilit);
if (propagator->is_lazy)
return;
// In case this variable was already assigned (e.g. via unit clause) and
// got compacted to map to another (not observed) variable, it can not be
// unnasigned so it must be notified explicitly now. (-> Can lead to
// repeated fixed assignment notifications, in case it was unobserved and
// observed again. But a repeated notification is less error-prone than
// never notifying an assignment.)
const int tmp = fixed (elit);
if (!tmp)
return;
int unit = tmp < 0 ? -elit : elit;
LOG ("notify propagator about fixed assignment upon observe for %d",
unit);
// internal add-observed-var had to backtrack to root-level already
assert (!internal->level);
std::vector<int> assigned;
assigned.push_back (unit);
propagator->notify_assignment (assigned);
}
void External::remove_observed_var (int elit) {
assert (propagator); // REQ is in Solver::remove_observed_var
int eidx = abs (elit);
if (eidx > max_var) // Ignore call if variable does not exist
return;
// Ignore call if variable is not observed
if ((size_t) eidx >= is_observed.size ())
return;
if (is_observed[eidx]) {
// Follow opposite order of add_observed_var, first remove internal
// is_observed
int ilit = e2i[eidx]; // internalize (elit);
internal->remove_observed_var (ilit);
is_observed[eidx] = false;
melt (elit);
LOG ("unmarking %d as externally watched", eidx);
}
}
void External::reset_observed_vars () {
// Shouldn't be called if there is no connected propagator
assert (propagator); // REQ is in Solver::reset_observed_vars
reset_extended ();
internal->notified = 0;
LOG ("reset notified counter to 0");
if (!is_observed.size ())
return;
for (auto elit : vars) {
int eidx = abs (elit);
assert (eidx <= max_var);
if ((size_t) eidx >= is_observed.size ())
break;
if (is_observed[eidx]) {
int ilit = internalize (elit);
internal->remove_observed_var (ilit);
LOG ("unmarking %d as externally watched", eidx);
is_observed[eidx] = false;
melt (elit);
}
}
}
bool External::observed (int elit) {
assert (elit);
assert (elit != INT_MIN);
int eidx = abs (elit);
if (eidx > max_var)
return false;
if (eidx >= (int) is_observed.size ())
return false;
return is_observed[eidx];
}
bool External::is_decision (int elit) {
assert (elit);
assert (elit != INT_MIN);
int eidx = abs (elit);
if (eidx > max_var)
return false;
int ilit = internal_lit (elit);
if (!ilit)
return false;
return internal->is_decision (ilit);
}
signed char External::current_val (int elit) {
assert (observed (elit));
int ilit = internalize (elit);
assert (ilit);
signed char res = internal->val (ilit);
return res;
}
bool External::force_unassign (int elit) {
assert (observed (elit));
const int iidx = internalize (elit);
assert (iidx);
if (!internal->val (iidx))
return true;
while (internal->val (iidx)) {
const int level = internal->var (iidx).level;
if (!level)
return false;
force_backtrack (level - 1);
internal->propagate ();
assert (!internal->conflict);
}
assert (!internal->val (iidx));
internal->notify_assignments ();
return false;
}
void External::force_backtrack (int new_level) {
assert (propagator); // REQ is is in Solver::force_backtrack
LOG ("force backtrack to level %d", new_level);
internal->force_backtrack (new_level);
}
/*------------------------------------------------------------------------*/
int External::propagate_assumptions () {
int res = internal->propagate_assumptions ();
if (res == 10 && !extended)
extend (); // Call solution reconstruction
check_solve_result (res);
reset_limits ();
return res;
}
void External::implied (std::vector<int> &trailed) {
std::vector<int> ilit_implicants;
internal->implied (ilit_implicants);
// Those implied literals must be filtered out that are witnesses
// on the reconstruction stack -> no inplace externalize is possible.
// (Internal does not see these marks, so no earlier filter is
// possible.)
trailed.clear ();
for (const auto &ilit : ilit_implicants) {
assert (ilit);
const int elit = internal->externalize (ilit);
const int eidx = abs (elit);
const bool is_extension_var = ervars[eidx];
if (!marked (tainted, elit) && !is_extension_var) {
trailed.push_back (elit);
}
}
}
void External::conclude_unknown () {
if (!internal->proof || concluded)
return;
concluded = true;
vector<int> trail;
implied (trail);
internal->proof->conclude_unknown (trail);
}
/*------------------------------------------------------------------------*/
// Internal checker if 'solve' claims the formula to be satisfiable.
void External::check_satisfiable () {
LOG ("checking satisfiable");
if (!extended)
extend ();
if (internal->opts.checkwitness)
check_assignment (&External::ival);
if (internal->opts.checkassumptions && !assumptions.empty ())
check_assumptions_satisfied ();
if (internal->opts.checkconstraint && !constraint.empty ())
check_constraint_satisfied ();
}
// Internal checker if 'solve' claims formula to be unsatisfiable.
void External::check_unsatisfiable () {
LOG ("checking unsatisfiable");
if (!internal->opts.checkfailed)
return;
if (!assumptions.empty () || !constraint.empty ())
check_failing ();
}
// Check result of 'solve' to be correct.
void External::check_solve_result (int res) {
if (!internal->opts.check)
return;
if (res == 10)
check_satisfiable ();
if (res == 20)
check_unsatisfiable ();
}
// Prepare checking that completely molten literals are not used as argument
// of 'add' or 'assume', which is invalid under freezing semantics. This
// case would be caught by our 'restore' implementation so is only needed
// for checking the deprecated 'freeze' semantics.
void External::update_molten_literals () {
if (!checkfrozen)
return;
assert (!max_var || (size_t) max_var + 1 == moltentab.size ());
#ifdef LOGGING
int registered = 0, molten = 0;
#endif
for (auto lit : vars) {
if (moltentab[lit]) {
LOG ("skipping already molten literal %d", lit);
#ifdef LOGGING
molten++;
#endif
} else if (frozen (lit))
LOG ("skipping currently frozen literal %d", lit);
else {
LOG ("new molten literal %d", lit);
moltentab[lit] = true;
#ifdef LOGGING
registered++;
molten++;
#endif
}
}
LOG ("registered %d new molten literals", registered);
LOG ("reached in total %d molten literals", molten);
}
int External::solve (bool preprocess_only) {
reset_extended ();
update_molten_literals ();
int res = internal->solve (preprocess_only);
check_solve_result (res);
reset_limits ();
return res;
}
void External::terminate () { internal->terminate (); }
int External::lookahead (int &lit) {
reset_extended ();
update_molten_literals ();
int ilit = 0;
int res = internal->lookahead (ilit);
check_solve_result (res);
const int elit =
(ilit && ilit != INT_MIN) ? internal->externalize (ilit) : 0;
LOG ("lookahead internal %d external %d", ilit, elit);
lit = elit;
return res;
}
CaDiCaL::CubesWithStatus External::generate_cubes (int depth,
int min_depth = 0) {
reset_extended ();
update_molten_literals ();
auto cubes = internal->solve_and_generate_cubes (depth, min_depth);
reset_limits ();
check_solve_result (cubes.status);
auto externalize = [this] (int ilit) {
const int elit = ilit ? internal->externalize (ilit) : 0;
MSG ("lookahead internal %d external %d", ilit, elit);
return elit;
};
auto externalize_map = [this, externalize] (std::vector<int> &cube) {
(void) this;
MSG ("Cube : ");
std::for_each (begin (cube), end (cube), externalize);
};
std::for_each (begin (cubes.cubes), end (cubes.cubes), externalize_map);
return cubes;
}
/*------------------------------------------------------------------------*/
bool External::is_witness (int elit) {
assert (elit);
assert (elit != INT_MIN);
int eidx = abs (elit);
if (eidx > max_var)
return false;
return (marked (witness, elit) || marked (witness, -elit));
}
/*------------------------------------------------------------------------*/
void External::freeze (int elit) {
reset_extended ();
int ilit = internalize (elit);
unsigned eidx = vidx (elit);
if (eidx >= frozentab.size ())
frozentab.resize (eidx + 1, 0);
unsigned &ref = frozentab[eidx];
if (ref < UINT_MAX) {
ref++;
LOG ("external variable %d frozen once and now frozen %u times", eidx,
ref);
} else
LOG ("external variable %d frozen but remains frozen forever", eidx);
internal->freeze (ilit);
}
void External::melt (int elit) {
reset_extended ();
int ilit = internalize (elit);
unsigned eidx = vidx (elit);
assert (eidx < frozentab.size ());
unsigned &ref = frozentab[eidx];
assert (ref > 0);
if (ref < UINT_MAX) {
if (!--ref) {
if (observed (elit)) {
ref++;
LOG ("external variable %d is observed, can not be completely "
"molten",
eidx);
} else
LOG ("external variable %d melted once and now completely melted",
eidx);
} else
LOG ("external variable %d melted once but remains frozen %u times",
eidx, ref);
} else
LOG ("external variable %d melted but remains frozen forever", eidx);
internal->melt (ilit);
}
/*------------------------------------------------------------------------*/
void External::check_assignment (int (External::*a) (int) const) {
// First check all assigned and consistent.
//
for (auto idx : vars) {
if (!(this->*a) (idx))
FATAL ("unassigned variable: %d", idx);
int value_idx = (this->*a) (idx);
int value_neg_idx = (this->*a) (-idx);
if (value_idx == idx)
assert (value_neg_idx == idx);
else {
assert (value_idx == -idx);
assert (value_neg_idx == -idx);
}
if (value_idx != value_neg_idx)
FATAL ("inconsistently assigned literals %d and %d", idx, -idx);
}
// Then check that all (saved) original clauses are satisfied.
//
bool satisfied = false;
const auto end = original.end ();
auto start = original.begin (), i = start;
#ifndef QUIET
int64_t count = 0;
#endif
for (; i != end; i++) {
int lit = *i;
if (!lit) {
if (!satisfied) {
fatal_message_start ();
fputs ("unsatisfied clause:\n", stderr);
for (auto j = start; j != i; j++)
fprintf (stderr, "%d ", *j);
fputc ('0', stderr);
fatal_message_end ();
}
satisfied = false;
start = i + 1;
#ifndef QUIET
count++;
#endif
} else if (!satisfied && (this->*a) (lit) == lit)
satisfied = true;
}
bool presence_flag;
// Check those forgettable external clauses that are still present, but
// only if the external propagator is still connected (otherwise solution
// reconstruction is allowed to touch the previously observed variables so
// there is no guarantee that the final model will satisfy these clauses.)
for (const auto &forgettables : forgettable_original) {
if (!propagator)
break;
presence_flag = true;
satisfied = false;
#ifndef QUIET
count++;
#endif
std::vector<int> literals;
for (const auto lit : forgettables.second) {
if (presence_flag) {
// First integer is a Boolean flag, not a literal
if (!lit) {
// Deleted clauses can be ignored, they count as satisfied
satisfied = true;
break;
}
presence_flag = false;
continue;
}
if ((this->*a) (lit) == lit) {
satisfied = true;
break;
} else if (!observed (lit)) {
// unobserved variables do not need to be satisfied
satisfied = true;
break;
}
}
if (!satisfied) {
fatal_message_start ();
fputs ("unsatisfied external forgettable clause:\n", stderr);
for (size_t j = 1; j < forgettables.second.size (); j++)
fprintf (stderr, "%d ", forgettables.second[j]);
fputc ('0', stderr);
fatal_message_end ();
}
}
#ifndef QUIET
VERBOSE (1, "satisfying assignment checked on %" PRId64 " clauses",
count);
#endif
}
/*------------------------------------------------------------------------*/
void External::check_assumptions_satisfied () {
for (const auto &lit : assumptions) {
// Not 'signed char' !!!!
const int tmp = ival (lit);
if (tmp != lit)
FATAL ("assumption %d falsified", lit);
if (!tmp)
FATAL ("assumption %d unassigned", lit);
}
VERBOSE (1, "checked that %zd assumptions are satisfied",
assumptions.size ());
}
void External::check_constraint_satisfied () {
for (const auto lit : constraint) {
if (ival (lit) == lit) {
VERBOSE (1, "checked that constraint is satisfied");
return;
}
}
FATAL ("constraint not satisfied");
}
void External::check_failing () {
Solver *checker = new Solver ();
if (terminator)
checker->connect_terminator (terminator);
DeferDeletePtr<Solver> delete_checker (checker);
checker->prefix ("checker ");
#ifdef LOGGING
if (internal->opts.log)
checker->set ("log", true);
#endif
checker->set ("factorcheck", false);
for (const auto lit : assumptions) {
if (!failed (lit))
continue;
LOG ("checking failed literal %d in core", lit);
checker->add (lit);
checker->add (0);
}
if (failed_constraint ()) {
LOG (constraint, "checking failed constraint");
for (const auto lit : constraint)
checker->add (lit);
} else if (constraint.size ())
LOG (constraint, "constraint satisfied and ignored");
// Add original clauses as last step, failing () and failed_constraint ()
// might add more external clauses (due to lazy explanation)
for (const auto lit : original)
checker->add (lit);
// Add every forgettable external clauses
for (const auto &forgettables : forgettable_original) {
bool presence_flag = true;
for (const auto lit : forgettables.second) {
if (presence_flag) {
// First integer is a Boolean flag, not a literal, ignore it here
presence_flag = false;
continue;
}
checker->add (lit);
}
checker->add (0);
}
int res = checker->solve ();
if (res == 10)
FATAL ("failed assumptions do not form a core");
delete_checker.free ();
if (res == 0)
VERBOSE (1, "checking of failed assumptions interrupted");
else
VERBOSE (1, "checked that %zd failing assumptions form a core",
assumptions.size ());
}
/*------------------------------------------------------------------------*/
// Traversal of unit clauses is implemented here.
// In principle we want to traverse the clauses of the simplified formula
// only, particularly eliminated variables should be completely removed.
// This poses the question what to do with unit clauses. Should they be
// considered part of the simplified formula or of the witness to construct
// solutions for the original formula? Ideally they should be considered
// to be part of the witness only, i.e., as they have been simplified away.
// Therefore we distinguish frozen and non-frozen units during clause
// traversal. Frozen units are treated as unit clauses while non-frozen
// units are treated as if they were already eliminated and put on the
// extension stack as witness clauses.
// Furthermore, eliminating units during 'compact' could be interpreted as
// variable elimination, i.e., just add the resolvents (remove falsified
// literals), then drop the clauses with the unit, and push the unit on the
// extension stack. This is of course only OK if the user did not freeze
// that variable (even implicitly during assumptions).
// Thanks go to Fahiem Bacchus for asking why there is a necessity to
// distinguish these two cases (frozen and non-frozen units). The answer is
// that it is not strictly necessary, and this distinction could be avoided
// by always treating units as remaining unit clauses, thus only using the
// first of the two following functions and dropping the 'if (!frozen (idx))
// continue;' check in it. This has however the down-side that those units
// are still in the simplified formula and only as units. I would not
// consider such a formula as really being 'simplified'. On the other hand
// if the user explicitly freezes a literal, then it should continue to be
// in the simplified formula during traversal. So also only using the
// second function is not ideal.
// There is however a catch where this solution breaks down (in the sense of
// producing less optimal results - that is keeping units in the formula
// which better would be witness clauses). The problem is with compact
// preprocessing which removes eliminated but also fixed internal variables.
// One internal unit (fixed) variable is kept and all the other external
// literals which became unit are mapped to that internal literal (negated
// or positively). Compact is called non-deterministically from the point
// of the user and thus there is no control on when this happens. If
// compact happens those external units are mapped to a single internal
// literal now and then all share the same 'frozen' counter. So if the
// user freezes one of them all in essence get frozen, which in turn then
// makes a difference in terms of traversing such a unit as unit clause or
// as unit witness.
bool External::traverse_all_frozen_units_as_clauses (ClauseIterator &it) {
if (internal->unsat)
return true;
vector<int> clause;
for (auto idx : vars) {
if (!frozen (idx))
continue;
const int tmp = fixed (idx);
if (!tmp)
continue;
int unit = tmp < 0 ? -idx : idx;
clause.push_back (unit);
if (!it.clause (clause))
return false;
clause.clear ();
}
return true;
}
bool External::traverse_all_non_frozen_units_as_witnesses (
WitnessIterator &it) {
if (internal->unsat)
return true;
vector<int> clause_and_witness;
for (auto idx : vars) {
if (frozen (idx))
continue;
const int tmp = fixed (idx);
if (!tmp)
continue;
int unit = tmp < 0 ? -idx : idx;
const int ilit = e2i[idx] * (tmp < 0 ? -1 : 1);
// heurstically add + max_var to the id to avoid reusing ids
const int64_t id = internal->lrat ? internal->unit_id (ilit) : 1;
assert (id);
clause_and_witness.push_back (unit);
if (!it.witness (clause_and_witness, clause_and_witness, id + max_var))
return false;
clause_and_witness.clear ();
}
return true;
}
/*------------------------------------------------------------------------*/
void External::copy_flags (External &other) const {
const vector<Flags> &this_ftab = internal->ftab;
vector<Flags> &other_ftab = other.internal->ftab;
const unsigned limit = min (max_var, other.max_var);
for (unsigned eidx = 1; eidx <= limit; eidx++) {
const int this_ilit = internal_lit (eidx);
if (!this_ilit)
continue;
const int other_ilit = other.internal_lit (eidx);
if (!other_ilit)
continue;
if (!internal->active (this_ilit))
continue;
if (!other.internal->active (other_ilit))
continue;
assert (this_ilit != INT_MIN);
assert (other_ilit != INT_MIN);
const Flags &this_flags = this_ftab[abs (this_ilit)];
Flags &other_flags = other_ftab[abs (other_ilit)];
this_flags.copy (other_flags);
}
internal->external->ervars = other.ervars;
}
/*------------------------------------------------------------------------*/
void External::export_learned_empty_clause () {
assert (learner);
if (learner->learning (0)) {
LOG ("exporting learned empty clause");
learner->learn (0);
} else
LOG ("not exporting learned empty clause");
}
void External::export_learned_unit_clause (int ilit) {
assert (learner);
if (learner->learning (1)) {
LOG ("exporting learned unit clause");
const int elit = internal->externalize (ilit);
assert (elit);
learner->learn (elit);
learner->learn (0);
} else
LOG ("not exporting learned unit clause");
}
void External::export_learned_large_clause (const vector<int> &clause) {
assert (learner);
size_t size = clause.size ();
assert (size <= (unsigned) INT_MAX);
if (learner->learning ((int) size)) {
LOG ("exporting learned clause of size %zu", size);
for (auto ilit : clause) {
const int elit = internal->externalize (ilit);
assert (elit);
learner->learn (elit);
}
learner->learn (0);
} else
LOG ("not exporting learned clause of size %zu", size);
}
} // namespace CaDiCaL