diff options
Diffstat (limited to 'src/prop/bvminisat')
25 files changed, 0 insertions, 5974 deletions
diff --git a/src/prop/bvminisat/LICENSE b/src/prop/bvminisat/LICENSE deleted file mode 100644 index 22816ff39..000000000 --- a/src/prop/bvminisat/LICENSE +++ /dev/null @@ -1,21 +0,0 @@ -MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson - Copyright (c) 2007-2010 Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a -copy of this software and associated documentation files (the -"Software"), to deal in the Software without restriction, including -without limitation the rights to use, copy, modify, merge, publish, -distribute, sublicense, and/or sell copies of the Software, and to -permit persons to whom the Software is furnished to do so, subject to -the following conditions: - -The above copyright notice and this permission notice shall be included -in all copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS -OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE -LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION -OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION -WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/src/prop/bvminisat/README b/src/prop/bvminisat/README deleted file mode 100644 index e5e5617d8..000000000 --- a/src/prop/bvminisat/README +++ /dev/null @@ -1,24 +0,0 @@ -================================================================================ -DIRECTORY OVERVIEW: - -mtl/ Mini Template Library -utils/ Generic helper code (I/O, Parsing, CPU-time, etc) -core/ A core version of the solver -simp/ An extended solver with simplification capabilities -README -LICENSE - -================================================================================ -BUILDING: (release version: without assertions, statically linked, etc) - -export MROOT=<minisat-dir> (or setenv in cshell) -cd { core | simp } -gmake rs -cp minisat_static <install-dir>/minisat - -================================================================================ -EXAMPLES: - -Run minisat with same heuristics as version 2.0: - -> minisat <cnf-file> -no-luby -rinc=1.5 -phase-saving=0 -rnd-freq=0.02 diff --git a/src/prop/bvminisat/bvminisat.cpp b/src/prop/bvminisat/bvminisat.cpp deleted file mode 100644 index 77b8c68e0..000000000 --- a/src/prop/bvminisat/bvminisat.cpp +++ /dev/null @@ -1,299 +0,0 @@ -/****************************************************************************** - * Top contributors (to current version): - * Liana Hadarean, Dejan Jovanovic, Tim King - * - * This file is part of the cvc5 project. - * - * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS - * in the top-level source directory and their institutional affiliations. - * All rights reserved. See the file COPYING in the top-level source - * directory for licensing information. - * **************************************************************************** - * - * SAT Solver. - * - * Implementation of the minisat for cvc5 (bit-vectors). - */ - -#include "prop/bvminisat/bvminisat.h" - -#include "prop/bvminisat/simp/SimpSolver.h" -#include "proof/clause_id.h" -#include "util/statistics_registry.h" - -namespace cvc5 { -namespace prop { - -BVMinisatSatSolver::BVMinisatSatSolver(StatisticsRegistry& registry, - context::Context* mainSatContext, - const std::string& name) - : context::ContextNotifyObj(mainSatContext, false), - d_minisat(new BVMinisat::SimpSolver(mainSatContext)), - d_minisatNotify(nullptr), - d_assertionsCount(0), - d_assertionsRealCount(mainSatContext, 0), - d_lastPropagation(mainSatContext, 0), - d_statistics(registry, name) -{ - d_statistics.init(d_minisat.get()); -} - -BVMinisatSatSolver::~BVMinisatSatSolver() { d_statistics.deinit(); } - -void BVMinisatSatSolver::MinisatNotify::notify( - BVMinisat::vec<BVMinisat::Lit>& clause) -{ - SatClause satClause; - for (unsigned i = 0, n = clause.size(); i < n; ++i) - { - satClause.push_back(toSatLiteral(clause[i])); - } - d_notify->notify(satClause); -} - -void BVMinisatSatSolver::setNotify(BVSatSolverNotify* notify) { - d_minisatNotify.reset(new MinisatNotify(notify)); - d_minisat->setNotify(d_minisatNotify.get()); -} - -ClauseId BVMinisatSatSolver::addClause(SatClause& clause, - bool removable) { - Debug("sat::minisat") << "Add clause " << clause <<"\n"; - BVMinisat::vec<BVMinisat::Lit> minisat_clause; - toMinisatClause(clause, minisat_clause); - // for(unsigned i = 0; i < minisat_clause.size(); ++i) { - // d_minisat->setFrozen(BVMinisat::var(minisat_clause[i]), true); - // } - ClauseId clause_id = ClauseIdError; - d_minisat->addClause(minisat_clause, clause_id); - return clause_id; -} - -SatValue BVMinisatSatSolver::propagate() { - return toSatLiteralValue(d_minisat->propagateAssumptions()); -} - -void BVMinisatSatSolver::addMarkerLiteral(SatLiteral lit) { - d_minisat->addMarkerLiteral(BVMinisat::var(toMinisatLit(lit))); - markUnremovable(lit); -} - -void BVMinisatSatSolver::explain(SatLiteral lit, std::vector<SatLiteral>& explanation) { - std::vector<BVMinisat::Lit> minisat_explanation; - d_minisat->explain(toMinisatLit(lit), minisat_explanation); - for (unsigned i = 0; i < minisat_explanation.size(); ++i) { - explanation.push_back(toSatLiteral(minisat_explanation[i])); - } -} - -SatValue BVMinisatSatSolver::assertAssumption(SatLiteral lit, bool propagate) { - d_assertionsCount ++; - d_assertionsRealCount = d_assertionsRealCount + 1; - return toSatLiteralValue(d_minisat->assertAssumption(toMinisatLit(lit), propagate)); -} - -void BVMinisatSatSolver::contextNotifyPop() { - while (d_assertionsCount > d_assertionsRealCount) { - popAssumption(); - d_assertionsCount --; - } -} - -void BVMinisatSatSolver::popAssumption() { - d_minisat->popAssumption(); -} - -SatVariable BVMinisatSatSolver::newVar(bool isTheoryAtom, bool preRegister, bool canErase){ - return d_minisat->newVar(true, true, !canErase); -} - -void BVMinisatSatSolver::markUnremovable(SatLiteral lit){ - d_minisat->setFrozen(BVMinisat::var(toMinisatLit(lit)), true); -} - - -void BVMinisatSatSolver::interrupt(){ - d_minisat->interrupt(); -} - -SatValue BVMinisatSatSolver::solve() -{ - TimerStat::CodeTimer solveTimer(d_statistics.d_statSolveTime); - ++d_statistics.d_statCallsToSolve; - return toSatLiteralValue(d_minisat->solve()); -} - -SatValue BVMinisatSatSolver::solve(long unsigned int& resource){ - Trace("limit") << "MinisatSatSolver::solve(): have limit of " << resource << " conflicts" << std::endl; - TimerStat::CodeTimer solveTimer(d_statistics.d_statSolveTime); - ++d_statistics.d_statCallsToSolve; - if(resource == 0) { - d_minisat->budgetOff(); - } else { - d_minisat->setConfBudget(resource); - } - // BVMinisat::vec<BVMinisat::Lit> empty; - unsigned long conflictsBefore = d_minisat->conflicts; - SatValue result = toSatLiteralValue(d_minisat->solveLimited()); - d_minisat->clearInterrupt(); - resource = d_minisat->conflicts - conflictsBefore; - Trace("limit") << "<MinisatSatSolver::solve(): it took " << resource << " conflicts" << std::endl; - return result; -} - -bool BVMinisatSatSolver::ok() const { return d_minisat->okay(); } - -void BVMinisatSatSolver::getUnsatCore(SatClause& unsatCore) { - // TODO add assertion to check the call was after an unsat call - for (int i = 0; i < d_minisat->conflict.size(); ++i) { - unsatCore.push_back(toSatLiteral(d_minisat->conflict[i])); - } -} - -SatValue BVMinisatSatSolver::value(SatLiteral l){ - return toSatLiteralValue(d_minisat->value(toMinisatLit(l))); -} - -SatValue BVMinisatSatSolver::modelValue(SatLiteral l){ - return toSatLiteralValue(d_minisat->modelValue(toMinisatLit(l))); -} - -void BVMinisatSatSolver::unregisterVar(SatLiteral lit) { - // this should only be called when user context is implemented - // in the BVSatSolver - Unreachable(); -} - -void BVMinisatSatSolver::renewVar(SatLiteral lit, int level) { - // this should only be called when user context is implemented - // in the BVSatSolver - - Unreachable(); -} - -unsigned BVMinisatSatSolver::getAssertionLevel() const { - // we have no user context implemented so far - return 0; -} - -// converting from internal Minisat representation - -SatVariable BVMinisatSatSolver::toSatVariable(BVMinisat::Var var) { - if (var == var_Undef) { - return undefSatVariable; - } - return SatVariable(var); -} - -BVMinisat::Lit BVMinisatSatSolver::toMinisatLit(SatLiteral lit) { - if (lit == undefSatLiteral) { - return BVMinisat::lit_Undef; - } - return BVMinisat::mkLit(lit.getSatVariable(), lit.isNegated()); -} - -SatLiteral BVMinisatSatSolver::toSatLiteral(BVMinisat::Lit lit) { - if (lit == BVMinisat::lit_Undef) { - return undefSatLiteral; - } - - return SatLiteral(SatVariable(BVMinisat::var(lit)), - BVMinisat::sign(lit)); -} - -SatValue BVMinisatSatSolver::toSatLiteralValue(BVMinisat::lbool res) { - if(res == (BVMinisat::lbool((uint8_t)0))) return SAT_VALUE_TRUE; - if(res == (BVMinisat::lbool((uint8_t)2))) return SAT_VALUE_UNKNOWN; - Assert(res == (BVMinisat::lbool((uint8_t)1))); - return SAT_VALUE_FALSE; -} - -void BVMinisatSatSolver::toMinisatClause(SatClause& clause, - BVMinisat::vec<BVMinisat::Lit>& minisat_clause) { - for (unsigned i = 0; i < clause.size(); ++i) { - minisat_clause.push(toMinisatLit(clause[i])); - } - Assert(clause.size() == (unsigned)minisat_clause.size()); -} - -void BVMinisatSatSolver::toSatClause(const BVMinisat::Clause& clause, - SatClause& sat_clause) { - for (int i = 0; i < clause.size(); ++i) { - sat_clause.push_back(toSatLiteral(clause[i])); - } - Assert((unsigned)clause.size() == sat_clause.size()); -} - - -// Satistics for BVMinisatSatSolver - -BVMinisatSatSolver::Statistics::Statistics(StatisticsRegistry& registry, - const std::string& prefix) - : d_statStarts( - registry.registerReference<int64_t>(prefix + "bvminisat::starts")), - d_statDecisions( - registry.registerReference<int64_t>(prefix + "bvminisat::decisions")), - d_statRndDecisions(registry.registerReference<int64_t>( - prefix + "bvminisat::rnd_decisions")), - d_statPropagations(registry.registerReference<int64_t>( - prefix + "bvminisat::propagations")), - d_statConflicts( - registry.registerReference<int64_t>(prefix + "bvminisat::conflicts")), - d_statClausesLiterals(registry.registerReference<int64_t>( - prefix + "bvminisat::clauses_literals")), - d_statLearntsLiterals(registry.registerReference<int64_t>( - prefix + "bvminisat::learnts_literals")), - d_statMaxLiterals(registry.registerReference<int64_t>( - prefix + "bvminisat::max_literals")), - d_statTotLiterals(registry.registerReference<int64_t>( - prefix + "bvminisat::tot_literals")), - d_statEliminatedVars(registry.registerReference<int64_t>( - prefix + "bvminisat::eliminated_vars")), - d_statCallsToSolve( - registry.registerInt(prefix + "bvminisat::calls_to_solve")), - d_statSolveTime(registry.registerTimer(prefix + "bvminisat::solve_time")) -{ - if (!d_registerStats) - { - return; - } -} - -void BVMinisatSatSolver::Statistics::init(BVMinisat::SimpSolver* minisat){ - if (!d_registerStats){ - return; - } - - d_statStarts.set(minisat->starts); - d_statDecisions.set(minisat->decisions); - d_statRndDecisions.set(minisat->rnd_decisions); - d_statPropagations.set(minisat->propagations); - d_statConflicts.set(minisat->conflicts); - d_statClausesLiterals.set(minisat->clauses_literals); - d_statLearntsLiterals.set(minisat->learnts_literals); - d_statMaxLiterals.set(minisat->max_literals); - d_statTotLiterals.set(minisat->tot_literals); - d_statEliminatedVars.set(minisat->eliminated_vars); -} - -void BVMinisatSatSolver::Statistics::deinit() -{ - if (!d_registerStats) - { - return; - } - - d_statStarts.reset(); - d_statDecisions.reset(); - d_statRndDecisions.reset(); - d_statPropagations.reset(); - d_statConflicts.reset(); - d_statClausesLiterals.reset(); - d_statLearntsLiterals.reset(); - d_statMaxLiterals.reset(); - d_statTotLiterals.reset(); - d_statEliminatedVars.reset(); -} - -} // namespace prop -} // namespace cvc5 diff --git a/src/prop/bvminisat/bvminisat.h b/src/prop/bvminisat/bvminisat.h deleted file mode 100644 index 3bfb2d93c..000000000 --- a/src/prop/bvminisat/bvminisat.h +++ /dev/null @@ -1,151 +0,0 @@ -/****************************************************************************** - * Top contributors (to current version): - * Mathias Preiner, Liana Hadarean, Tim King - * - * This file is part of the cvc5 project. - * - * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS - * in the top-level source directory and their institutional affiliations. - * All rights reserved. See the file COPYING in the top-level source - * directory for licensing information. - * **************************************************************************** - * - * SAT Solver. - * - * Implementation of the minisat for cvc5 (bit-vectors). - */ - -#include "cvc5_private.h" - -#pragma once - -#include <memory> - -#include "context/cdo.h" -#include "prop/bv_sat_solver_notify.h" -#include "prop/bvminisat/simp/SimpSolver.h" -#include "prop/sat_solver.h" -#include "util/resource_manager.h" -#include "util/statistics_stats.h" - -namespace cvc5 { -namespace prop { - -class BVMinisatSatSolver : public BVSatSolverInterface, - public context::ContextNotifyObj -{ - private: - class MinisatNotify : public BVMinisat::Notify - { - BVSatSolverNotify* d_notify; - - public: - MinisatNotify(BVSatSolverNotify* notify) : d_notify(notify) {} - bool notify(BVMinisat::Lit lit) override - { - return d_notify->notify(toSatLiteral(lit)); - } - void notify(BVMinisat::vec<BVMinisat::Lit>& clause) override; - void spendResource(Resource r) override - { - d_notify->spendResource(r); - } - void safePoint(Resource r) override - { - d_notify->safePoint(r); - } - }; - - std::unique_ptr<BVMinisat::SimpSolver> d_minisat; - std::unique_ptr<MinisatNotify> d_minisatNotify; - - unsigned d_assertionsCount; - context::CDO<unsigned> d_assertionsRealCount; - context::CDO<unsigned> d_lastPropagation; - -protected: - void contextNotifyPop() override; - -public: - BVMinisatSatSolver(StatisticsRegistry& registry, - context::Context* mainSatContext, - const std::string& name = ""); - virtual ~BVMinisatSatSolver(); - - void setNotify(BVSatSolverNotify* notify) override; - - ClauseId addClause(SatClause& clause, bool removable) override; - - ClauseId addXorClause(SatClause& clause, bool rhs, bool removable) override - { - Unreachable() << "Minisat does not support native XOR reasoning"; - return ClauseIdError; - } - - SatValue propagate() override; - - SatVariable newVar(bool isTheoryAtom = false, - bool preRegister = false, - bool canErase = true) override; - - SatVariable trueVar() override { return d_minisat->trueVar(); } - SatVariable falseVar() override { return d_minisat->falseVar(); } - - void markUnremovable(SatLiteral lit) override; - - void interrupt() override; - - SatValue solve() override; - SatValue solve(long unsigned int&) override; - bool ok() const override; - void getUnsatCore(SatClause& unsatCore) override; - - SatValue value(SatLiteral l) override; - SatValue modelValue(SatLiteral l) override; - - void unregisterVar(SatLiteral lit); - void renewVar(SatLiteral lit, int level = -1); - unsigned getAssertionLevel() const override; - - // helper methods for converting from the internal Minisat representation - - static SatVariable toSatVariable(BVMinisat::Var var); - static BVMinisat::Lit toMinisatLit(SatLiteral lit); - static SatLiteral toSatLiteral(BVMinisat::Lit lit); - static SatValue toSatLiteralValue(BVMinisat::lbool res); - - static void toMinisatClause(SatClause& clause, BVMinisat::vec<BVMinisat::Lit>& minisat_clause); - static void toSatClause (const BVMinisat::Clause& clause, SatClause& sat_clause); - void addMarkerLiteral(SatLiteral lit) override; - - void explain(SatLiteral lit, std::vector<SatLiteral>& explanation) override; - - SatValue assertAssumption(SatLiteral lit, bool propagate) override; - - void popAssumption() override; - - private: - /* Disable the default constructor. */ - BVMinisatSatSolver() = delete; - - class Statistics { - public: - ReferenceStat<int64_t> d_statStarts, d_statDecisions; - ReferenceStat<int64_t> d_statRndDecisions, d_statPropagations; - ReferenceStat<int64_t> d_statConflicts, d_statClausesLiterals; - ReferenceStat<int64_t> d_statLearntsLiterals, d_statMaxLiterals; - ReferenceStat<int64_t> d_statTotLiterals; - ReferenceStat<int64_t> d_statEliminatedVars; - IntStat d_statCallsToSolve; - TimerStat d_statSolveTime; - bool d_registerStats = true; - Statistics(StatisticsRegistry& registry, const std::string& prefix); - void init(BVMinisat::SimpSolver* minisat); - void deinit(); - }; - - Statistics d_statistics; -}; - -} // namespace prop -} // namespace cvc5 diff --git a/src/prop/bvminisat/core/Dimacs.h b/src/prop/bvminisat/core/Dimacs.h deleted file mode 100644 index a660391f7..000000000 --- a/src/prop/bvminisat/core/Dimacs.h +++ /dev/null @@ -1,91 +0,0 @@ -/****************************************************************************************[Dimacs.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Dimacs_h -#define BVMinisat_Dimacs_h - -#include <stdio.h> - -#include "prop/bvminisat/core/SolverTypes.h" -#include "prop/bvminisat/utils/ParseUtils.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// DIMACS Parser: - -template<class B, class Solver> -static void readClause(B& in, Solver& S, vec<Lit>& lits) { - int parsed_lit, var; - lits.clear(); - for (;;){ - parsed_lit = parseInt(in); - if (parsed_lit == 0) break; - var = abs(parsed_lit)-1; - while (var >= S.nVars()) S.newVar(); - lits.push( (parsed_lit > 0) ? mkLit(var) : ~mkLit(var) ); - } -} - -template<class B, class Solver> -static void parse_DIMACS_main(B& in, Solver& S) { - vec<Lit> lits; - int vars = 0; - int clauses = 0; - int cnt = 0; - for (;;){ - skipWhitespace(in); - if (*in == EOF) break; - else if (*in == 'p'){ - if (eagerMatch(in, "p cnf")){ - vars = parseInt(in); - clauses = parseInt(in); - // SATRACE'06 hack - // if (clauses > 4000000) - // S.eliminate(true); - }else{ - printf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3); - } - } else if (*in == 'c' || *in == 'p') - skipLine(in); - else{ - cnt++; - readClause(in, S, lits); - S.addClause_(lits); } - } - if (vars != S.nVars()) - fprintf(stderr, "WARNING! DIMACS header mismatch: wrong number of variables.\n"); - if (cnt != clauses) - fprintf(stderr, "WARNING! DIMACS header mismatch: wrong number of clauses.\n"); -} - -// Inserts problem into solver. -// -template<class Solver> -static void parse_DIMACS(gzFile input_stream, Solver& S) { - StreamBuffer in(input_stream); - parse_DIMACS_main(in, S); } - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/core/Solver.cc b/src/prop/bvminisat/core/Solver.cc deleted file mode 100644 index e7d9086bc..000000000 --- a/src/prop/bvminisat/core/Solver.cc +++ /dev/null @@ -1,1421 +0,0 @@ -/***************************************************************************************[Solver.cc] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#include "prop/bvminisat/core/Solver.h" - -#include <math.h> - -#include <iostream> -#include <vector> - -#include "base/check.h" -#include "base/exception.h" -#include "base/output.h" -#include "options/bv_options.h" -#include "options/smt_options.h" -#include "prop/bvminisat/mtl/Sort.h" -#include "theory/interrupted.h" -#include "util/utility.h" - -namespace cvc5 { -namespace BVMinisat { - -#define OUTPUT_TAG "bvminisat: [a=" << assumptions.size() << ",l=" << decisionLevel() << "] " - -std::ostream& operator << (std::ostream& out, const BVMinisat::Lit& l) { - out << (sign(l) ? "-" : "") << var(l) + 1; - return out; -} - -std::ostream& operator << (std::ostream& out, const BVMinisat::Clause& c) { - for (int i = 0; i < c.size(); i++) { - if (i > 0) { - out << " "; - } - out << c[i]; - } - return out; -} - - -//================================================================================================= -// Options: - - -static const char* _cat = "CORE"; - -static DoubleOption opt_var_decay (_cat, "var-decay", "The variable activity decay factor", 0.95, DoubleRange(0, false, 1, false)); -static DoubleOption opt_clause_decay (_cat, "cla-decay", "The clause activity decay factor", 0.999, DoubleRange(0, false, 1, false)); -static DoubleOption opt_random_var_freq (_cat, "rnd-freq", "The frequency with which the decision heuristic tries to choose a random variable", 0, DoubleRange(0, true, 1, true)); -static DoubleOption opt_random_seed (_cat, "rnd-seed", "Used by the random variable selection", 91648253, DoubleRange(0, false, HUGE_VAL, false)); -static IntOption opt_ccmin_mode (_cat, "ccmin-mode", "Controls conflict clause minimization (0=none, 1=basic, 2=deep)", 2, IntRange(0, 2)); -static IntOption opt_phase_saving (_cat, "phase-saving", "Controls the level of phase saving (0=none, 1=limited, 2=full)", 2, IntRange(0, 2)); -static BoolOption opt_rnd_init_act (_cat, "rnd-init", "Randomize the initial activity", false); -static BoolOption opt_luby_restart (_cat, "luby", "Use the Luby restart sequence", true); -static IntOption opt_restart_first (_cat, "rfirst", "The base restart interval", 25, IntRange(1, INT32_MAX)); -static DoubleOption opt_restart_inc (_cat, "rinc", "Restart interval increase factor", 3, DoubleRange(1, false, HUGE_VAL, false)); -static DoubleOption opt_garbage_frac (_cat, "gc-frac", "The fraction of wasted memory allowed before a garbage collection is triggered", 0.20, DoubleRange(0, false, HUGE_VAL, false)); - -//================================================================================================= -// Proof declarations -CRef Solver::TCRef_Undef = CRef_Undef; -CRef Solver::TCRef_Lazy = CRef_Undef - 1; // no real lazy ref here - - -//================================================================================================= -// Constructor/Destructor: - -Solver::Solver(cvc5::context::Context* context) - : - - // Parameters (user settable): - // - d_notify(nullptr), - c(context), - verbosity(0), - var_decay(opt_var_decay), - clause_decay(opt_clause_decay), - random_var_freq(opt_random_var_freq), - random_seed(opt_random_seed), - luby_restart(opt_luby_restart), - ccmin_mode(opt_ccmin_mode), - phase_saving(opt_phase_saving), - rnd_pol(false), - rnd_init_act(opt_rnd_init_act), - garbage_frac(opt_garbage_frac), - restart_first(opt_restart_first), - restart_inc(opt_restart_inc) - - // Parameters (the rest): - // - , - learntsize_factor((double)1 / (double)3), - learntsize_inc(1.5) - - // Parameters (experimental): - // - , - learntsize_adjust_start_confl(100), - learntsize_adjust_inc(1.5) - - // Statistics: (formerly in 'SolverStats') - // - , - solves(0), - starts(0), - decisions(0), - rnd_decisions(0), - propagations(0), - conflicts(0), - dec_vars(0), - clauses_literals(0), - learnts_literals(0), - max_literals(0), - tot_literals(0) - - , - need_to_propagate(false), - only_bcp(false), - clause_added(false), - ok(true), - cla_inc(1), - var_inc(1), - watches(WatcherDeleted(ca)), - qhead(0), - simpDB_assigns(-1), - simpDB_props(0), - order_heap(VarOrderLt(activity)), - progress_estimate(0), - remove_satisfied(true) - - , - ca() - - // even though these are temporaries and technically should be set - // before calling, lets initialize them. this will reduces chances of - // non-determinism in portfolio (parallel) solver if variables are - // being (incorrectly) used without initialization. - , - seen(), - analyze_stack(), - analyze_toclear(), - add_tmp(), - max_learnts(0.0), - learntsize_adjust_confl(0.0), - learntsize_adjust_cnt(0) - - // Resource constraints: - // - , - conflict_budget(-1), - propagation_budget(-1), - asynch_interrupt(false) -{ - // Create the constant variables - varTrue = newVar(true, false); - varFalse = newVar(false, false); - - // Assert the constants - uncheckedEnqueue(mkLit(varTrue, false)); - uncheckedEnqueue(mkLit(varFalse, true)); -} - - -Solver::~Solver() -{ -} - - -//================================================================================================= -// Minor methods: - - -// Creates a new SAT variable in the solver. If 'decision' is cleared, variable will not be -// used as a decision variable (NOTE! This has effects on the meaning of a SATISFIABLE result). -// -Var Solver::newVar(bool sign, bool dvar) -{ - int v = nVars(); - watches .init(mkLit(v, false)); - watches .init(mkLit(v, true )); - assigns .push(l_Undef); - vardata .push(mkVarData(CRef_Undef, 0)); - marker .push(0); - //activity .push(0); - activity .push(rnd_init_act ? drand(random_seed) * 0.00001 : 0); - seen .push(0); - polarity .push(sign); - decision .push(); - trail .capacity(v+1); - setDecisionVar(v, dvar); - - return v; -} - - -bool Solver::addClause_(vec<Lit>& ps, ClauseId& id) -{ - if (decisionLevel() > 0) { - cancelUntil(0); - } - - if (!ok) { - id = ClauseIdUndef; - return false; - } - - // Check if clause is satisfied and remove false/duplicate literals: - // TODO proof for duplicate literals removal? - sort(ps); - Lit p; int i, j; - int falseLiteralsCount = 0; - - for (i = j = 0, p = lit_Undef; i < ps.size(); i++) { - // tautologies are ignored - if (value(ps[i]) == l_True || ps[i] == ~p) { - id = ClauseIdUndef; - return true; - } - - // Ignore repeated literals - if (ps[i] == p) { - continue; - } - - if (value(ps[i]) == l_False) { - continue; - } - ps[j++] = p = ps[i]; - } - - ps.shrink(i - j); - - clause_added = true; - - if(falseLiteralsCount == 0) { - if (ps.size() == 0) { - return ok = false; - } - else if (ps.size() == 1){ - uncheckedEnqueue(ps[0]); - CRef confl_ref = propagate(); - ok = (confl_ref == CRef_Undef); - return ok; - } else { - CRef cr = ca.alloc(ps, false); - clauses.push(cr); - attachClause(cr); - } - return ok; - } - return ok; -} - -void Solver::attachClause(CRef cr) { - const Clause& clause = ca[cr]; - Assert(clause.size() > 1); - watches[~clause[0]].push(Watcher(cr, clause[1])); - watches[~clause[1]].push(Watcher(cr, clause[0])); - if (clause.learnt()) - learnts_literals += clause.size(); - else - clauses_literals += clause.size(); -} - -void Solver::detachClause(CRef cr, bool strict) { - const Clause& clause = ca[cr]; - - Assert(clause.size() > 1); - - if (strict) - { - remove(watches[~clause[0]], Watcher(cr, clause[1])); - remove(watches[~clause[1]], Watcher(cr, clause[0])); - }else{ - // Lazy detaching: (NOTE! Must clean all watcher lists before garbage collecting this clause) - watches.smudge(~clause[0]); - watches.smudge(~clause[1]); - } - - if (clause.learnt()) - learnts_literals -= clause.size(); - else - clauses_literals -= clause.size(); -} - -void Solver::removeClause(CRef cr) { - Clause& clause = ca[cr]; - detachClause(cr); - // Don't leave pointers to free'd memory! - if (locked(clause)) vardata[var(clause[0])].reason = CRef_Undef; - clause.mark(1); - ca.free(cr); -} - -bool Solver::satisfied(const Clause& clause) const -{ - for (int i = 0; i < clause.size(); i++) - if (value(clause[i]) == l_True) return true; - return false; -} - -// Revert to the state at given level (keeping all assignment at 'level' but not beyond). -// -void Solver::cancelUntil(int level) { - if (decisionLevel() > level){ - Debug("bvminisat::explain") << OUTPUT_TAG << " backtracking to " << level << std::endl; - for (int clause = trail.size() - 1; clause >= trail_lim[level]; clause--) - { - Var x = var(trail[clause]); - assigns[x] = l_Undef; - if (marker[x] == 2) marker[x] = 1; - if (phase_saving > 1 - || ((phase_saving == 1) && clause > trail_lim.last())) - { - polarity[x] = sign(trail[clause]); - } - insertVarOrder(x); - } - qhead = trail_lim[level]; - trail.shrink(trail.size() - trail_lim[level]); - trail_lim.shrink(trail_lim.size() - level); - } -} - - -//================================================================================================= -// Major methods: - - -Lit Solver::pickBranchLit() -{ - Var next = var_Undef; - - // Random decision: - if (drand(random_seed) < random_var_freq && !order_heap.empty()){ - next = order_heap[irand(random_seed,order_heap.size())]; - if (value(next) == l_Undef && decision[next]) - rnd_decisions++; } - - // Activity based decision: - while (next == var_Undef || value(next) != l_Undef || !decision[next]) - if (order_heap.empty()){ - next = var_Undef; - break; - }else - next = order_heap.removeMin(); - - return next == var_Undef ? lit_Undef : mkLit(next, rnd_pol ? drand(random_seed) < 0.5 : polarity[next]); -} - -/*_________________________________________________________________________________________________ -| -| analyze : (confl : Clause*) (out_learnt : vec<Lit>&) (out_btlevel : int&) -> -[void] -| -| Description: -| Analyze conflict and produce a reason clause. -| -| Pre-conditions: -| * 'out_learnt' is assumed to be cleared. -| * Current decision level must be greater than root level. -| -| Post-conditions: -| * 'out_learnt[0]' is the asserting literal at level 'out_btlevel'. -| * If out_learnt.size() > 1 then 'out_learnt[1]' has the greatest decision -level of the | rest of literals. There may be others from the same level -though. -| -|________________________________________________________________________________________________@*/ -void Solver::analyze(CRef confl, vec<Lit>& out_learnt, int& out_btlevel, UIP uip) -{ - int pathC = 0; - Lit p = lit_Undef; - - // Generate conflict clause: - // - out_learnt.push(); // (leave room for the asserting literal) - int index = trail.size() - 1; - - bool done = false; - - do{ - Assert(confl != CRef_Undef); // (otherwise should be UIP) - Clause& clause = ca[confl]; - - if (clause.learnt()) claBumpActivity(clause); - - for (int j = (p == lit_Undef) ? 0 : 1; j < clause.size(); j++) - { - Lit q = clause[j]; - - if (!seen[var(q)] && level(var(q)) > 0) - { - varBumpActivity(var(q)); - seen[var(q)] = 1; - if (level(var(q)) >= decisionLevel()) - pathC++; - else - out_learnt.push(q); - } - } - - // Select next clause to look at: - while (!seen[var(trail[index--])]); - p = trail[index+1]; - confl = reason(var(p)); - seen[var(p)] = 0; - pathC--; - - switch (uip) { - case UIP_FIRST: - done = pathC == 0; - break; - case UIP_LAST: - done = confl == CRef_Undef || (pathC == 0 && marker[var(p)] == 2); - break; - default: - Unreachable(); - break; - } - } while (!done); - out_learnt[0] = ~p; - - // Simplify conflict clause: - // - int i1, j; - out_learnt.copyTo(analyze_toclear); - if (ccmin_mode == 2){ - uint32_t abstract_level = 0; - for (i1 = 1; i1 < out_learnt.size(); i1++) - abstract_level |= abstractLevel( - var(out_learnt[i1])); // (maintain an abstraction of levels - // involved in conflict) - - for (i1 = j = 1; i1 < out_learnt.size(); i1++) - { - if (reason(var(out_learnt[i1])) == CRef_Undef) - { - out_learnt[j++] = out_learnt[i1]; - } - else - { - // Check if the literal is redundant - if (!litRedundant(out_learnt[i1], abstract_level)) - { - // Literal is not redundant - out_learnt[j++] = out_learnt[i1]; - } - } - } - }else if (ccmin_mode == 1){ - Unreachable(); - for (i1 = j = 1; i1 < out_learnt.size(); i1++) - { - Var x = var(out_learnt[i1]); - - if (reason(x) == CRef_Undef) - out_learnt[j++] = out_learnt[i1]; - else - { - Clause& clause = ca[reason(var(out_learnt[i1]))]; - for (int k = 1; k < clause.size(); k++) - if (!seen[var(clause[k])] && level(var(clause[k])) > 0) - { - out_learnt[j++] = out_learnt[i1]; - break; - } - } - } - }else - i1 = j = out_learnt.size(); - - max_literals += out_learnt.size(); - out_learnt.shrink(i1 - j); - tot_literals += out_learnt.size(); - - for (int i2 = 0; i2 < out_learnt.size(); ++i2) - { - if (marker[var(out_learnt[i2])] == 0) - { - break; - } - } - - // Find correct backtrack level: - // - if (out_learnt.size() == 1) { - out_btlevel = 0; - } - else{ - int max_i = 1; - // Find the first literal assigned at the next-highest level: - for (int i3 = 2; i3 < out_learnt.size(); i3++) - if (level(var(out_learnt[i3])) > level(var(out_learnt[max_i]))) - max_i = i3; - // Swap-in this literal at i1 1: - Lit p2 = out_learnt[max_i]; - out_learnt[max_i] = out_learnt[1]; - out_learnt[1] = p2; - out_btlevel = level(var(p2)); - } - - for (int j2 = 0; j2 < analyze_toclear.size(); j2++) - seen[var(analyze_toclear[j2])] = 0; // ('seen[]' is now cleared) -} - - -// Check if 'p' can be removed. 'abstract_levels' is used to abort early if the algorithm is -// visiting literals at levels that cannot be removed later. -bool Solver::litRedundant(Lit p, uint32_t abstract_levels) -{ - analyze_stack.clear(); analyze_stack.push(p); - int top = analyze_toclear.size(); - while (analyze_stack.size() > 0){ - CRef c_reason = reason(var(analyze_stack.last())); - Assert(c_reason != CRef_Undef); - Clause& clause = ca[c_reason]; - int c_size = clause.size(); - analyze_stack.pop(); - - for (int i = 1; i < c_size; i++){ - Lit p2 = clause[i]; - if (!seen[var(p2)] && level(var(p2)) > 0) - { - if (reason(var(p2)) != CRef_Undef - && (abstractLevel(var(p2)) & abstract_levels) != 0) - { - seen[var(p2)] = 1; - analyze_stack.push(p2); - analyze_toclear.push(p2); - } - else - { - for (int j = top; j < analyze_toclear.size(); j++) - seen[var(analyze_toclear[j])] = 0; - analyze_toclear.shrink(analyze_toclear.size() - top); - return false; - } - } - } - } - - return true; -} - -/** - * Specialized analyzeFinal procedure where we test the consistency - * of the assumptions before backtracking bellow the assumption level. - * - * @param p the original uip (may be unit) - * @param confl_clause the conflict clause - * @param out_conflict the conflict in terms of assumptions we are building - */ -void Solver::analyzeFinal2(Lit p, CRef confl_clause, vec<Lit>& out_conflict) { - Assert(confl_clause != CRef_Undef); - Assert(decisionLevel() == assumptions.size()); - Assert(level(var(p)) == assumptions.size()); - - out_conflict.clear(); - - Clause& cl = ca[confl_clause]; - for (int i = 0; i < cl.size(); ++i) { - seen[var(cl[i])] = 1; - } - - int end = trail_lim[0]; - for (int i = trail.size() - 1; i >= end; i--) { - Var x = var(trail[i]); - if (seen[x]) { - if (reason(x) == CRef_Undef) { - // we skip p if was a learnt unit - if (x != var(p)) { - if (marker[x] == 2) { - Assert(level(x) > 0); - out_conflict.push(~trail[i]); - } - } - } else { - Clause& clause = ca[reason(x)]; - - for (int j = 1; j < clause.size(); j++) - { - if (level(var(clause[j])) > 0) seen[var(clause[j])] = 1; - } - } - seen[x] = 0; - } - Assert(seen[x] == 0); - } - Assert(out_conflict.size()); -} - -/*_________________________________________________________________________________________________ -| -| analyzeFinal : (p : Lit) -> [void] -| -| Description: -| Specialized analysis procedure to express the final conflict in terms of -assumptions. | Calculates the (possibly empty) set of assumptions that led to -the assignment of 'p', and | stores the result in 'out_conflict'. -|________________________________________________________________________________________________@*/ -void Solver::analyzeFinal(Lit p, vec<Lit>& out_conflict) -{ - out_conflict.clear(); - if (marker[var(p)] == 2) { - out_conflict.push(p); - } - - if (decisionLevel() == 0) - { - return; - } - - seen[var(p)] = 1; - int end = trail_lim[0]; - - for (int i = trail.size()-1; i >= end; i--){ - Var x = var(trail[i]); - if (seen[x]) { - if (reason(x) == CRef_Undef) { - Assert(marker[x] == 2); - Assert(level(x) > 0); - if (~trail[i] != p) - { - out_conflict.push(~trail[i]); - } - } else { - Clause& clause = ca[reason(x)]; - for (int j = 1; j < clause.size(); j++) - { - if (level(var(clause[j])) > 0) - { - seen[var(clause[j])] = 1; - } - } - } - seen[x] = 0; - } - } - - seen[var(p)] = 0; - Assert(out_conflict.size()); -} - - -void Solver::uncheckedEnqueue(Lit p, CRef from) -{ - Assert(value(p) == l_Undef); - assigns[var(p)] = lbool(!sign(p)); - vardata[var(p)] = mkVarData(from, decisionLevel()); - trail.push_(p); - if (decisionLevel() <= assumptions.size() && marker[var(p)] == 1) - { - if (d_notify) - { - Debug("bvminisat::explain") - << OUTPUT_TAG << "propagating " << p << std::endl; - d_notify->notify(p); - } - } -} - -void Solver::popAssumption() { - assumptions.pop(); - conflict.clear(); - cancelUntil(assumptions.size()); -} - -lbool Solver::propagateAssumptions() { - only_bcp = true; - ccmin_mode = 0; - return search(-1); -} - -lbool Solver::assertAssumption(Lit p, bool propagate) { - // TODO need to somehow mark the assumption as unit in the current context? - // it's not always unit though, but this would be useful for debugging - - // Assert(marker[var(p)] == 1); - - if (decisionLevel() > assumptions.size()) { - cancelUntil(assumptions.size()); - } - - conflict.clear(); - - // add to the assumptions - if (c->getLevel() > 0) { - assumptions.push(p); - } else { - ClauseId id; - if (!addClause(p, id)) { - conflict.push(~p); - return l_False; - } - } - - // run the propagation - if (propagate) { - only_bcp = true; - ccmin_mode = 0; - lbool result = search(-1); - return result; - } else { - return l_True; - } -} - -void Solver::addMarkerLiteral(Var var) { - // make sure it wasn't already marked - Assert(marker[var] == 0); - marker[var] = 1; -} - -/*_________________________________________________________________________________________________ -| -| propagate : [void] -> [Clause*] -| -| Description: -| Propagates all enqueued facts. If a conflict arises, the conflicting clause -is returned, | otherwise CRef_Undef. -| -| Post-conditions: -| * the propagation queue is empty, even if there was a conflict. -|________________________________________________________________________________________________@*/ -CRef Solver::propagate() -{ - CRef confl = CRef_Undef; - int num_props = 0; - watches.cleanAll(); - - while (qhead < trail.size()){ - Lit p = trail[qhead++]; // 'p' is enqueued fact to propagate. - vec<Watcher>& ws = watches[p]; - Watcher *i, *j, *end; - num_props++; - - for (i = j = (Watcher*)ws, end = i + ws.size(); i != end;){ - // Try to avoid inspecting the clause: - Lit blocker = i->blocker; - if (value(blocker) == l_True){ - *j++ = *i++; continue; } - - // Make sure the false literal is data[1]: - CRef cr = i->cref; - Clause& clause = ca[cr]; - Lit false_lit = ~p; - if (clause[0] == false_lit) - clause[0] = clause[1], clause[1] = false_lit; - Assert(clause[1] == false_lit); - i++; - - // If 0th watch is true, then clause is already satisfied. - Lit first = clause[0]; - Watcher w = Watcher(cr, first); - if (first != blocker && value(first) == l_True){ - *j++ = w; continue; } - - // Look for new watch: - for (int k = 2; k < clause.size(); k++) - if (value(clause[k]) != l_False) - { - clause[1] = clause[k]; - clause[k] = false_lit; - watches[~clause[1]].push(w); - goto NextClause; - } - - // Did not find watch -- clause is unit under assignment: - *j++ = w; - if (value(first) == l_False){ - confl = cr; - qhead = trail.size(); - // Copy the remaining watches: - while (i < end) - *j++ = *i++; - }else - uncheckedEnqueue(first, cr); - - NextClause:; - } - ws.shrink(i - j); - } - propagations += num_props; - simpDB_props -= num_props; - - return confl; -} - -/*_________________________________________________________________________________________________ -| -| reduceDB : () -> [void] -| -| Description: -| Remove half of the learnt clauses, minus the clauses locked by the current -assignment. Locked | clauses are clauses that are reason to some assignment. -Binary clauses are never removed. -|________________________________________________________________________________________________@*/ -struct reduceDB_lt -{ - ClauseAllocator& ca; - reduceDB_lt(ClauseAllocator& ca_) : ca(ca_) {} - bool operator()(CRef x, CRef y) - { - return ca[x].size() > 2 - && (ca[y].size() == 2 || ca[x].activity() < ca[y].activity()); - } -}; -void Solver::reduceDB() -{ - int i, j; - double extra_lim = cla_inc / learnts.size(); // Remove any clause below this activity - - sort(learnts, reduceDB_lt(ca)); - // Don't delete binary or locked clauses. From the rest, delete clauses from the first half - // and clauses with activity smaller than 'extra_lim': - for (i = j = 0; i < learnts.size(); i++){ - Clause& clause = ca[learnts[i]]; - if (clause.size() > 2 && !locked(clause) - && (i < learnts.size() / 2 || clause.activity() < extra_lim)) - removeClause(learnts[i]); - else - learnts[j++] = learnts[i]; - } - learnts.shrink(i - j); - checkGarbage(); -} - - -void Solver::removeSatisfied(vec<CRef>& cs) -{ - int i, j; - for (i = j = 0; i < cs.size(); i++){ - Clause& clause = ca[cs[i]]; - if (satisfied(clause)) - { - removeClause(cs[i]); - } - else - cs[j++] = cs[i]; - } - cs.shrink(i - j); -} - - -void Solver::rebuildOrderHeap() -{ - vec<Var> vs; - for (Var v = 0; v < nVars(); v++) - if (decision[v] && value(v) == l_Undef) - vs.push(v); - order_heap.build(vs); -} - -/*_________________________________________________________________________________________________ -| -| simplify : [void] -> [bool] -| -| Description: -| Simplify the clause database according to the current top-level assigment. -Currently, the only | thing done here is the removal of satisfied clauses, -but more things can be put here. -|________________________________________________________________________________________________@*/ -bool Solver::simplify() -{ - Assert(decisionLevel() == 0); - - if (!ok || propagate() != CRef_Undef) return ok = false; - - if (nAssigns() == simpDB_assigns || (simpDB_props > 0)) return true; - - d_notify->spendResource(Resource::BvSatSimplifyStep); - - // Remove satisfied clauses: - removeSatisfied(learnts); - if (remove_satisfied) // Can be turned off. - removeSatisfied(clauses); - checkGarbage(); - rebuildOrderHeap(); - - simpDB_assigns = nAssigns(); - simpDB_props = - clauses_literals + learnts_literals; // (shouldn't depend on stats - // really, but it will do for now) - - return true; -} - -/*_________________________________________________________________________________________________ -| -| search : (nof_conflicts : int) (params : const SearchParams&) -> [lbool] -| -| Description: -| Search for a model the specified number of conflicts. -| NOTE! Use negative value for 'nof_conflicts' indicate infinity. -| -| Output: -| 'l_True' if a partial assigment that is consistent with respect to the -clauseset is found. If | all variables are decision variables, this means -that the clause set is satisfiable. 'l_False' | if the clause set is -unsatisfiable. 'l_Undef' if the bound on number of conflicts is reached. -|________________________________________________________________________________________________@*/ -lbool Solver::search(int nof_conflicts, UIP uip) -{ - Assert(ok); - int backtrack_level; - int conflictC = 0; - vec<Lit> learnt_clause; - starts++; - - for (;;) - { - d_notify->safePoint(Resource::BvSatPropagateStep); - CRef confl = propagate(); - if (confl != CRef_Undef) - { - // CONFLICT - conflicts++; - conflictC++; - - if (decisionLevel() == 0) - { - // can this happen for bv? - return l_False; - } - - learnt_clause.clear(); - analyze(confl, learnt_clause, backtrack_level, uip); - - Lit p = learnt_clause[0]; - // bool assumption = marker[var(p)] == 2; - - CRef cr = CRef_Undef; - if (learnt_clause.size() > 1) - { - cr = ca.alloc(learnt_clause, true); - learnts.push(cr); - attachClause(cr); - claBumpActivity(ca[cr]); - } - - if (learnt_clause.size() == 1) - { - // learning a unit clause - } - - // if the uip was an assumption we are unsat - if (level(var(p)) <= assumptions.size()) - { - for (int i = 0; i < learnt_clause.size(); ++i) - { - Assert(level(var(learnt_clause[i])) <= decisionLevel()); - seen[var(learnt_clause[i])] = 1; - } - - analyzeFinal(p, conflict); - Debug("bvminisat::search") - << OUTPUT_TAG << " conflict on assumptions " << std::endl; - return l_False; - } - - if (!cvc5::options::bvEagerExplanations()) - { - // check if uip leads to a conflict - if (backtrack_level < assumptions.size()) - { - cancelUntil(assumptions.size()); - uncheckedEnqueue(p, cr); - - CRef new_confl = propagate(); - if (new_confl != CRef_Undef) - { - // we have a conflict we now need to explain it - analyzeFinal2(p, new_confl, conflict); - return l_False; - } - } - } - - cancelUntil(backtrack_level); - uncheckedEnqueue(p, cr); - - varDecayActivity(); - claDecayActivity(); - - if (--learntsize_adjust_cnt == 0) - { - learntsize_adjust_confl *= learntsize_adjust_inc; - learntsize_adjust_cnt = (int)learntsize_adjust_confl; - max_learnts *= learntsize_inc; - - if (verbosity >= 1) - printf("| %9d | %7d %8d %8d | %8d %8d %6.0f | %6.3f %% |\n", - (int)conflicts, - (int)dec_vars - - (trail_lim.size() == 0 ? trail.size() : trail_lim[0]), - nClauses(), - (int)clauses_literals, - (int)max_learnts, - nLearnts(), - (double)learnts_literals / nLearnts(), - progressEstimate() * 100); - } - } - else - { - // NO CONFLICT - bool isWithinBudget; - try - { - isWithinBudget = - withinBudget(Resource::BvSatConflictsStep); - } - catch (const cvc5::theory::Interrupted& e) - { - // do some clean-up and rethrow - cancelUntil(assumptions.size()); - throw e; - } - - if ((decisionLevel() > assumptions.size() && nof_conflicts >= 0 - && conflictC >= nof_conflicts) - || !isWithinBudget) - { - // Reached bound on number of conflicts: - Debug("bvminisat::search") << OUTPUT_TAG << " restarting " << std::endl; - progress_estimate = progressEstimate(); - cancelUntil(assumptions.size()); - return l_Undef; - } - - // Simplify the set of problem clauses: - if (decisionLevel() == 0 && !simplify()) - { - Debug("bvminisat::search") - << OUTPUT_TAG << " base level conflict, we're unsat" << std::endl; - return l_False; - } - - // We can't erase clauses if there is unprocessed assumptions, there might - // be some propagationg we need to redu - if (decisionLevel() >= assumptions.size() - && learnts.size() - nAssigns() >= max_learnts) - { - // Reduce the set of learnt clauses: - Debug("bvminisat::search") - << OUTPUT_TAG << " cleaning up database" << std::endl; - reduceDB(); - } - - Lit next = lit_Undef; - while (decisionLevel() < assumptions.size()) - { - // Perform user provided assumption: - Lit p = assumptions[decisionLevel()]; - if (value(p) == l_True) - { - // Dummy decision level: - newDecisionLevel(); - } - else if (value(p) == l_False) - { - marker[var(p)] = 2; - - analyzeFinal(~p, conflict); - Debug("bvminisat::search") - << OUTPUT_TAG << " assumption false, we're unsat" << std::endl; - return l_False; - } - else - { - marker[var(p)] = 2; - next = p; - break; - } - } - - if (next == lit_Undef) - { - if (only_bcp) - { - Debug("bvminisat::search") - << OUTPUT_TAG << " only bcp, skipping rest of the problem" - << std::endl; - return l_True; - } - - // New variable decision: - decisions++; - next = pickBranchLit(); - - if (next == lit_Undef) - { - Debug("bvminisat::search") - << OUTPUT_TAG << " satisfiable" << std::endl; - // Model found: - return l_True; - } - } - - // Increase decision level and enqueue 'next' - newDecisionLevel(); - uncheckedEnqueue(next); - } - } -} - - -double Solver::progressEstimate() const -{ - double progress = 0; - double F = 1.0 / nVars(); - - for (int i = 0; i <= decisionLevel(); i++){ - int beg = i == 0 ? 0 : trail_lim[i - 1]; - int end = i == decisionLevel() ? trail.size() : trail_lim[i]; - progress += pow(F, i) * (end - beg); - } - - return progress / nVars(); -} - -/* - Finite subsequences of the Luby-sequence: - - 0: 1 - 1: 1 1 2 - 2: 1 1 2 1 1 2 4 - 3: 1 1 2 1 1 2 4 1 1 2 1 1 2 4 8 - ... - - - */ - -static double luby(double y, int x){ - - // Find the finite subsequence that contains index 'x', and the - // size of that subsequence: - int size, seq; - for (size = 1, seq = 0; size < x+1; seq++, size = 2*size+1); - - while (size-1 != x){ - size = (size-1)>>1; - seq--; - x = x % size; - } - - return pow(y, seq); -} - -// NOTE: assumptions passed in member-variable 'assumptions'. -lbool Solver::solve_() -{ - Debug("bvminisat") <<"BVMinisat::Solving learned clauses " << learnts.size() <<"\n"; - Debug("bvminisat") <<"BVMinisat::Solving assumptions " << assumptions.size() <<"\n"; - - model.clear(); - conflict.clear(); - - ccmin_mode = 0; - - if (!ok) return l_False; - - solves++; - - max_learnts = nClauses() * learntsize_factor; - learntsize_adjust_confl = learntsize_adjust_start_confl; - learntsize_adjust_cnt = (int)learntsize_adjust_confl; - lbool status = l_Undef; - - if (verbosity >= 1){ - printf("============================[ Search Statistics ]==============================\n"); - printf("| Conflicts | ORIGINAL | LEARNT | Progress |\n"); - printf("| | Vars Clauses Literals | Limit Clauses Lit/Cl | |\n"); - printf("===============================================================================\n"); - } - - // Search: - int curr_restarts = 0; - while (status == l_Undef){ - double rest_base = luby_restart ? luby(restart_inc, curr_restarts) : pow(restart_inc, curr_restarts); - status = search(rest_base * restart_first); - if (!withinBudget(Resource::BvSatConflictsStep)) break; - curr_restarts++; - } - - if (verbosity >= 1) - printf("===============================================================================\n"); - - if (status == l_True){ - // Extend & copy model: - // model.growTo(nVars()); - // for (int i = 0; i < nVars(); i++) model[i] = value(i); - }else if (status == l_False && conflict.size() == 0) - ok = false; - - return status; -} - -//================================================================================================= -// Bitvector propagations -// - -void Solver::explain(Lit p, std::vector<Lit>& explanation) { - Debug("bvminisat::explain") << OUTPUT_TAG << "starting explain of " << p << std::endl; - - // top level fact, no explanation necessary - if (level(var(p)) == 0) { - return; - } - - seen[var(p)] = 1; - - // if we are called at decisionLevel = 0 trail_lim is empty - int bottom = trail_lim[0]; - for (int i = trail.size()-1; i >= bottom; i--){ - Var x = var(trail[i]); - if (seen[x]) { - if (reason(x) == CRef_Undef) { - if (marker[x] == 2) { - Assert(level(x) > 0); - explanation.push_back(trail[i]); - } else { - Assert(level(x) == 0); - } - } else { - Clause& clause = ca[reason(x)]; - for (int j = 1; j < clause.size(); j++) - { - if (level(var(clause[j])) > 0) - { - seen[var(clause[j])] = 1; - } - } - } - seen[x] = 0; - } - } - seen[var(p)] = 0; -} - -//================================================================================================= -// Writing CNF to DIMACS: -// -// FIXME: this needs to be rewritten completely. - -static Var mapVar(Var x, vec<Var>& map, Var& max) -{ - if (map.size() <= x || map[x] == -1){ - map.growTo(x+1, -1); - map[x] = max++; - } - return map[x]; -} - -void Solver::toDimacs(FILE* f, Clause& clause, vec<Var>& map, Var& max) -{ - if (satisfied(clause)) return; - - for (int i = 0; i < clause.size(); i++) - if (value(clause[i]) != l_False) - fprintf(f, - "%s%d ", - sign(clause[i]) ? "-" : "", - mapVar(var(clause[i]), map, max) + 1); - fprintf(f, "0\n"); -} - - -void Solver::toDimacs(const char *file, const vec<Lit>& assumps) -{ - FILE* f = fopen(file, "wr"); - if (f == NULL) - fprintf(stderr, "could not open file %s\n", file), exit(1); - toDimacs(f, assumps); - fclose(f); -} - - -void Solver::toDimacs(FILE* f, const vec<Lit>& assumps) -{ - // Handle case when solver is in contradictory state: - if (!ok){ - fprintf(f, "p cnf 1 2\n1 0\n-1 0\n"); - return; } - - vec<Var> map; Var max = 0; - - // Cannot use removeClauses here because it is not safe - // to deallocate them at this point. Could be improved. - int cnt = 0; - for (int i = 0; i < clauses.size(); i++) - if (!satisfied(ca[clauses[i]])) - cnt++; - - for (int i = 0; i < clauses.size(); i++) - if (!satisfied(ca[clauses[i]])){ - Clause& clause = ca[clauses[i]]; - for (int j = 0; j < clause.size(); j++) - if (value(clause[j]) != l_False) mapVar(var(clause[j]), map, max); - } - - // Assumptions are added as unit clauses: - cnt += assumps.size(); - - fprintf(f, "p cnf %d %d\n", max, cnt); - - for (int i = 0; i < assumps.size(); i++){ - Assert(value(assumps[i]) != l_False); - fprintf(f, - "%s%d 0\n", - sign(assumps[i]) ? "-" : "", - mapVar(var(assumps[i]), map, max) + 1); - } - - for (int i = 0; i < clauses.size(); i++) - toDimacs(f, ca[clauses[i]], map, max); - - if (verbosity > 0) - printf("Wrote %d clauses with %d variables.\n", cnt, max); -} - - -//================================================================================================= -// Garbage Collection methods: - -void Solver::relocAll(ClauseAllocator& to) -{ - // All watchers: - // - // for (int i = 0; i < watches.size(); i++) - watches.cleanAll(); - for (int v = 0; v < nVars(); v++) - for (int s = 0; s < 2; s++){ - Lit p = mkLit(v, s); - // printf(" >>> RELOCING: %s%d\n", sign(p)?"-":"", var(p)+1); - vec<Watcher>& ws = watches[p]; - for (int j = 0; j < ws.size(); j++) ca.reloc(ws[j].cref, to); - } - - // All reasons: - // - for (int i = 0; i < trail.size(); i++){ - Var v = var(trail[i]); - - if (reason(v) != CRef_Undef && (ca[reason(v)].reloced() || locked(ca[reason(v)]))) - ca.reloc(vardata[v].reason, to); - } - - // All learnt: - // - for (int i = 0; i < learnts.size(); i++) ca.reloc(learnts[i], to); - - // All original: - // - for (int i = 0; i < clauses.size(); i++) ca.reloc(clauses[i], to); -} - - -void Solver::garbageCollect() -{ - // Initialize the next region to a size corresponding to the estimated utilization degree. This - // is not precise but should avoid some unnecessary reallocations for the new region: - ClauseAllocator to(ca.size() - ca.wasted()); - Debug("bvminisat") << " BVMinisat::Garbage collection \n"; - relocAll(to); - if (verbosity >= 2) - printf( - "| Garbage collection: %12d bytes => %12d bytes |\n", - ca.size() * ClauseAllocator::Unit_Size, - to.size() * ClauseAllocator::Unit_Size); - to.moveTo(ca); -} - -void ClauseAllocator::reloc(CRef& cr, ClauseAllocator& to) -{ - Clause& c = operator[](cr); - if (c.reloced()) { cr = c.relocation(); return; } - - cr = to.alloc(c, c.learnt()); - c.relocate(cr); - - // Copy extra data-fields: - // (This could be cleaned-up. Generalize Clause-constructor to be applicable - // here instead?) - to[cr].mark(c.mark()); - if (to[cr].learnt()) to[cr].activity() = c.activity(); - else if (to[cr].has_extra()) to[cr].calcAbstraction(); -} - -void Solver::setNotify(Notify* toNotify) { d_notify = toNotify; } -bool Solver::withinBudget(Resource r) const -{ - AlwaysAssert(d_notify); - d_notify->safePoint(r); - - return !asynch_interrupt && - (conflict_budget < 0 || conflicts < conflict_budget) && - (propagation_budget < 0 || - propagations < propagation_budget); -} - -} // namespace BVMinisat -} // namespace cvc5 diff --git a/src/prop/bvminisat/core/Solver.h b/src/prop/bvminisat/core/Solver.h deleted file mode 100644 index 7c08c3bcf..000000000 --- a/src/prop/bvminisat/core/Solver.h +++ /dev/null @@ -1,539 +0,0 @@ -/****************************************************************************************[Solver.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Solver_h -#define BVMinisat_Solver_h - -#include <vector> - -#include "base/check.h" -#include "context/context.h" -#include "proof/clause_id.h" -#include "prop/bvminisat/core/SolverTypes.h" -#include "prop/bvminisat/mtl/Alg.h" -#include "prop/bvminisat/mtl/Heap.h" -#include "prop/bvminisat/mtl/Vec.h" -#include "prop/bvminisat/utils/Options.h" -#include "util/resource_manager.h" - -namespace cvc5 { - -namespace BVMinisat { -class Solver; -} - -namespace BVMinisat { - -/** Interface for minisat callbacks */ -class Notify { - -public: - - virtual ~Notify() {} - - /** - * If the notify returns false, the solver will break out of whatever it's currently doing - * with an "unknown" answer. - */ - virtual bool notify(Lit lit) = 0; - - /** - * Notify about a new learnt clause with marked literals only. - */ - virtual void notify(vec<Lit>& learnt) = 0; - - virtual void spendResource(Resource r) = 0; - virtual void safePoint(Resource r) = 0; -}; - -//================================================================================================= -// Solver -- the main class: -class Solver { -public: - typedef Var TVar; - typedef Lit TLit; - typedef Clause TClause; - typedef CRef TCRef; - typedef vec<Lit> TLitVec; - - static CRef TCRef_Undef; - static CRef TCRef_Lazy; -private: - /** To notify */ - Notify* d_notify; - - /** cvc5 context */ - cvc5::context::Context* c; - - /** True constant */ - Var varTrue; - - /** False constant */ - Var varFalse; - -public: - - // Constructor/Destructor: - // - Solver(cvc5::context::Context* c); - virtual ~Solver(); - - void setNotify(Notify* toNotify); - - // Problem specification: - // - Var newVar(bool polarity = true, - bool dvar = true); // Add a new variable with parameters specifying - // variable mode. - Var trueVar() const { return varTrue; } - Var falseVar() const { return varFalse; } - - bool addClause(const vec<Lit>& ps, - ClauseId& id); // Add a clause to the solver. - bool addEmptyClause(); // Add the empty clause, making the solver - // contradictory. - bool addClause(Lit p, ClauseId& id); // Add a unit clause to the solver. - bool addClause(Lit p, - Lit q, - ClauseId& id); // Add a binary clause to the solver. - bool addClause(Lit p, - Lit q, - Lit r, - ClauseId& id); // Add a ternary clause to the solver. - bool addClause_( - vec<Lit>& ps, - ClauseId& id); // Add a clause to the solver without making superflous - // internal copy. Will change the passed vector 'ps'. - - // Solving: - // - bool simplify(); // Removes already satisfied clauses. - lbool solve(const vec<Lit>& assumps); // Search for a model that respects a - // given set of assumptions. - lbool solveLimited( - const vec<Lit>& assumps); // Search for a model that respects a given set - // of assumptions (With resource constraints). - lbool solve(); // Search without assumptions. - lbool solve(Lit p); // Search for a model that respects a single assumption. - lbool solve(Lit p, - Lit q); // Search for a model that respects two assumptions. - lbool solve(Lit p, - Lit q, - Lit r); // Search for a model that respects three assumptions. - bool okay() const; // FALSE means solver is in a conflicting state - lbool assertAssumption( - Lit p, - bool propagate); // Assert a new assumption, start BCP if propagate = true - lbool propagateAssumptions(); // Do BCP over asserted assumptions - void popAssumption(); // Pop an assumption - - void toDimacs(FILE* f, - const vec<Lit>& assumps); // Write CNF to file in DIMACS-format. - void toDimacs(const char* file, const vec<Lit>& assumps); - void toDimacs(FILE* f, Clause& c, vec<Var>& map, Var& max); - - // Convenience versions of 'toDimacs()': - void toDimacs(const char* file); - void toDimacs(const char* file, Lit p); - void toDimacs(const char* file, Lit p, Lit q); - void toDimacs(const char* file, Lit p, Lit q, Lit r); - - // Variable mode: - // - void setPolarity( - Var v, bool b); // Declare which polarity the decision heuristic should - // use for a variable. Requires mode 'polarity_user'. - void setDecisionVar(Var v, - bool b); // Declare if a variable should be eligible for - // selection in the decision heuristic. - - // Read state: - // - lbool value(Var x) const; // The current value of a variable. - lbool value(Lit p) const; // The current value of a literal. - lbool modelValue( - Var x) const; // The value of a variable in the last model. The last call - // to solve must have been satisfiable. - lbool modelValue( - Lit p) const; // The value of a literal in the last model. The last call - // to solve must have been satisfiable. - int nAssigns() const; // The current number of assigned literals. - int nClauses() const; // The current number of original clauses. - int nLearnts() const; // The current number of learnt clauses. - int nVars() const; // The current number of variables. - int nFreeVars() const; - - // Resource contraints: - // - void setConfBudget(int64_t x); - void setPropBudget(int64_t x); - void budgetOff(); - void interrupt(); // Trigger a (potentially asynchronous) interruption of the - // solver. - void clearInterrupt(); // Clear interrupt indicator flag. - - // Memory managment: - // - virtual void garbageCollect(); - void checkGarbage(double gf); - void checkGarbage(); - - // Extra results: (read-only member variable) - // - vec<lbool> model; // If problem is satisfiable, this vector contains the model - // (if any). - vec<Lit> conflict; // If problem is unsatisfiable (possibly under - // assumptions), this vector represent the final conflict - // clause expressed in the assumptions. - - // Mode of operation: - // - int verbosity; - double var_decay; - double clause_decay; - double random_var_freq; - double random_seed; - bool luby_restart; - int ccmin_mode; // Controls conflict clause minimization (0=none, 1=basic, - // 2=deep). - int phase_saving; // Controls the level of phase saving (0=none, 1=limited, - // 2=full). - bool rnd_pol; // Use random polarities for branching heuristics. - bool - rnd_init_act; // Initialize variable activities with a small random value. - double garbage_frac; // The fraction of wasted memory allowed before a garbage - // collection is triggered. - - int restart_first; // The initial restart limit. (default 100) - double restart_inc; // The factor with which the restart limit is multiplied - // in each restart. (default 1.5) - double - learntsize_factor; // The intitial limit for learnt clauses is a factor of - // the original clauses. (default 1 / 3) - double learntsize_inc; // The limit for learnt clauses is multiplied with this - // factor each restart. (default 1.1) - - int learntsize_adjust_start_confl; - double learntsize_adjust_inc; - - // Statistics: (read-only member variable) - // - int64_t solves, starts, decisions, rnd_decisions, propagations, conflicts; - int64_t dec_vars, clauses_literals, learnts_literals, max_literals, - tot_literals; - - // Bitvector Propagations - // - - void addMarkerLiteral(Var var); - - bool need_to_propagate; // true if we added new clauses, set to true in - // propagation - bool only_bcp; // solving mode in which only boolean constraint propagation is - // done - void setOnlyBCP(bool val) { only_bcp = val; } - void explain(Lit l, std::vector<Lit>& explanation); - -protected: - // has a clause been added - bool clause_added; - - // Helper structures: - // - struct VarData - { - CRef reason; - int level; }; - static inline VarData mkVarData(CRef cr, int l){ VarData d = {cr, l}; return d; } - - struct Watcher { - CRef cref; - Lit blocker; - Watcher(CRef cr, Lit p) : cref(cr), blocker(p) {} - bool operator==(const Watcher& w) const { return cref == w.cref; } - bool operator!=(const Watcher& w) const { return cref != w.cref; } - }; - - struct WatcherDeleted - { - const ClauseAllocator& ca; - WatcherDeleted(const ClauseAllocator& _ca) : ca(_ca) {} - bool operator()(const Watcher& w) const { return ca[w.cref].mark() == 1; } - }; - - struct VarOrderLt { - const vec<double>& activity; - bool operator () (Var x, Var y) const { return activity[x] > activity[y]; } - VarOrderLt(const vec<double>& act) : activity(act) { } - }; - - // Solver state: - // - bool ok; // If FALSE, the constraints are already unsatisfiable. No part of the solver state may be used! - vec<CRef> clauses; // List of problem clauses. - vec<CRef> learnts; // List of learnt clauses. - double cla_inc; // Amount to bump next clause with. - vec<double> activity; // A heuristic measurement of the activity of a variable. - double var_inc; // Amount to bump next variable with. - OccLists<Lit, vec<Watcher>, WatcherDeleted> - watches; // 'watches[lit]' is a list of constraints watching 'lit' (will go there if literal becomes true). - vec<lbool> assigns; // The current assignments. - vec<char> polarity; // The preferred polarity of each variable. - vec<char> marker; // Is the variable a marker literal - vec<char> decision; // Declares if a variable is eligible for selection in the decision heuristic. - vec<Lit> trail; // Assignment stack; stores all assigments made in the order they were made. - vec<int> trail_lim; // Separator indices for different decision levels in 'trail'. - vec<VarData> vardata; // Stores reason and level for each variable. - int qhead; // Head of queue (as index into the trail -- no more explicit propagation queue in MiniSat). - int simpDB_assigns; // Number of top-level assignments since last execution of 'simplify()'. - int64_t simpDB_props; // Remaining number of propagations that must be made before next execution of 'simplify()'. - vec<Lit> assumptions; // Current set of assumptions provided to solve by the user. - Heap<VarOrderLt> order_heap; // A priority queue of variables ordered with respect to the variable activity. - double progress_estimate;// Set by 'search()'. - bool remove_satisfied; // Indicates whether possibly inefficient linear scan for satisfied clauses should be performed in 'simplify'. - - ClauseAllocator ca; - - // Temporaries (to reduce allocation overhead). Each variable is prefixed by the method in which it is - // used, exept 'seen' wich is used in several places. - // - vec<char> seen; - vec<Lit> analyze_stack; - vec<Lit> analyze_toclear; - vec<Lit> add_tmp; - - double max_learnts; - double learntsize_adjust_confl; - int learntsize_adjust_cnt; - - // Resource contraints: - // - int64_t conflict_budget; // -1 means no budget. - int64_t propagation_budget; // -1 means no budget. - bool asynch_interrupt; - - // Main internal methods: - // - void insertVarOrder (Var x); // Insert a variable in the decision order priority queue. - Lit pickBranchLit (); // Return the next decision variable. - void newDecisionLevel (); // Begins a new decision level. - void uncheckedEnqueue (Lit p, CRef from = CRef_Undef); // Enqueue a literal. Assumes value of literal is undefined. - bool enqueue (Lit p, CRef from = CRef_Undef); // Test if fact 'p' contradicts current state, enqueue otherwise. - CRef propagate (); // Perform unit propagation. Returns possibly conflicting clause. - void cancelUntil (int level); // Backtrack until a certain level. - - enum UIP { - UIP_FIRST, - UIP_LAST - }; - - void analyze (CRef confl, vec<Lit>& out_learnt, int& out_btlevel, UIP uip = UIP_FIRST); // (bt = backtrack) - void analyzeFinal (Lit p, vec<Lit>& out_conflict); // COULD THIS BE IMPLEMENTED BY THE ORDINARIY "analyze" BY SOME REASONABLE GENERALIZATION? - void analyzeFinal2(Lit p, CRef confl_clause, vec<Lit>& out_conflict); - bool litRedundant (Lit p, uint32_t abstract_levels); // (helper method for 'analyze()') - lbool search (int nof_conflicts, UIP uip = UIP_FIRST); // Search for a given number of conflicts. - lbool solve_ (); // Main solve method (assumptions given in 'assumptions'). - void reduceDB (); // Reduce the set of learnt clauses. - void removeSatisfied (vec<CRef>& cs); // Shrink 'cs' to contain only non-satisfied clauses. - void rebuildOrderHeap (); - - // Maintaining Variable/Clause activity: - // - void varDecayActivity (); // Decay all variables with the specified factor. Implemented by increasing the 'bump' value instead. - void varBumpActivity (Var v, double inc); // Increase a variable with the current 'bump' value. - void varBumpActivity (Var v); // Increase a variable with the current 'bump' value. - void claDecayActivity (); // Decay all clauses with the specified factor. Implemented by increasing the 'bump' value instead. - void claBumpActivity (Clause& c); // Increase a clause with the current 'bump' value. - - // Operations on clauses: - // - void attachClause (CRef cr); // Attach a clause to watcher lists. - void detachClause (CRef cr, bool strict = false); // Detach a clause to watcher lists. - void removeClause (CRef cr); // Detach and free a clause. - bool locked (const Clause& c) const; // Returns TRUE if a clause is a reason for some implication in the current state. - bool satisfied (const Clause& c) const; // Returns TRUE if a clause is satisfied in the current state. - - void relocAll (ClauseAllocator& to); - - // Misc: - // - int decisionLevel () const; // Gives the current decisionlevel. - uint32_t abstractLevel (Var x) const; // Used to represent an abstraction of sets of decision levels. - CRef reason (Var x) const; - int level (Var x) const; - double progressEstimate () const; // DELETE THIS ?? IT'S NOT VERY USEFUL ... - bool withinBudget(Resource r) const; - - // Static helpers: - // - - // Returns a random float 0 <= x < 1. Seed must never be 0. - static inline double drand(double& seed) { - seed *= 1389796; - int q = (int)(seed / 2147483647); - seed -= (double)q * 2147483647; - return seed / 2147483647; } - - // Returns a random integer 0 <= x < size. Seed must never be 0. - static inline int irand(double& seed, int size) { - return (int)(drand(seed) * size); } - - // Less than for literals in an added clause when proofs are on. - struct assign_lt { - Solver& d_solver; - assign_lt(Solver& solver) : d_solver(solver) {} - bool operator () (Lit x, Lit y) { - lbool x_value = d_solver.value(x); - lbool y_value = d_solver.value(y); - // Two unassigned literals are sorted arbitrarily - if (x_value == l_Undef && y_value == l_Undef) { - return x < y; - } - // Unassigned literals are put to front - if (x_value == l_Undef) return true; - if (y_value == l_Undef) return false; - // Literals of the same value are sorted by decreasing levels - if (x_value == y_value) { - return d_solver.level(var(x)) > d_solver.level(var(y)); - } else { - // True literals go up front - if (x_value == l_True) { - return true; - } else { - return false; - } - } - } - }; - -}; - - -//================================================================================================= -// Implementation of inline methods: - -inline CRef Solver::reason(Var x) const -{ - Assert(x < vardata.size()); - return vardata[x].reason; -} -inline int Solver::level(Var x) const -{ - Assert(x < vardata.size()); - return vardata[x].level; -} - -inline void Solver::insertVarOrder(Var x) { - if (!order_heap.inHeap(x) && decision[x]) order_heap.insert(x); } - -inline void Solver::varDecayActivity() { var_inc *= (1 / var_decay); } -inline void Solver::varBumpActivity(Var v) { varBumpActivity(v, var_inc); } -inline void Solver::varBumpActivity(Var v, double inc) { - if ( (activity[v] += inc) > 1e100 ) { - // Rescale: - for (int i = 0; i < nVars(); i++) - activity[i] *= 1e-100; - var_inc *= 1e-100; } - - // Update order_heap with respect to new activity: - if (order_heap.inHeap(v)) - order_heap.decrease(v); } - -inline void Solver::claDecayActivity() { cla_inc *= (1 / clause_decay); } -inline void Solver::claBumpActivity(Clause& clause) -{ - if ((clause.activity() += cla_inc) > 1e20) - { - // Rescale: - for (int i = 0; i < learnts.size(); i++) ca[learnts[i]].activity() *= 1e-20; - cla_inc *= 1e-20; - } -} - -inline void Solver::checkGarbage(void){ return checkGarbage(garbage_frac); } -inline void Solver::checkGarbage(double gf){ - if (ca.wasted() > ca.size() * gf) - garbageCollect(); } - -// NOTE: enqueue does not set the ok flag! (only public methods do) -inline bool Solver::enqueue (Lit p, CRef from) { return value(p) != l_Undef ? value(p) != l_False : (uncheckedEnqueue(p, from), true); } -inline bool Solver::addClause (const vec<Lit>& ps, ClauseId& id) { ps.copyTo(add_tmp); return addClause_(add_tmp, id); } -inline bool Solver::addEmptyClause () { add_tmp.clear(); ClauseId tmp; return addClause_(add_tmp, tmp); } -inline bool Solver::addClause (Lit p, ClauseId& id) { add_tmp.clear(); add_tmp.push(p); return addClause_(add_tmp, id); } -inline bool Solver::addClause (Lit p, Lit q, ClauseId& id) { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); return addClause_(add_tmp, id); } -inline bool Solver::addClause (Lit p, Lit q, Lit r, ClauseId& id) { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); add_tmp.push(r); return addClause_(add_tmp, id); } -inline bool Solver::locked(const Clause& clause) const -{ - return value(clause[0]) == l_True && reason(var(clause[0])) != CRef_Undef - && ca.lea(reason(var(clause[0]))) == &clause; -} -inline void Solver::newDecisionLevel() { trail_lim.push(trail.size()); } - -inline int Solver::decisionLevel () const { return trail_lim.size(); } -inline uint32_t Solver::abstractLevel (Var x) const { return 1 << (level(x) & 31); } -inline lbool Solver::value (Var x) const { return assigns[x]; } -inline lbool Solver::value (Lit p) const { return assigns[var(p)] ^ sign(p); } -inline lbool Solver::modelValue (Var x) const { return model[x]; } -inline lbool Solver::modelValue (Lit p) const { return model[var(p)] ^ sign(p); } -inline int Solver::nAssigns () const { return trail.size(); } -inline int Solver::nClauses () const { return clauses.size(); } -inline int Solver::nLearnts () const { return learnts.size(); } -inline int Solver::nVars () const { return vardata.size(); } -inline int Solver::nFreeVars () const { return (int)dec_vars - (trail_lim.size() == 0 ? trail.size() : trail_lim[0]); } -inline void Solver::setPolarity (Var v, bool b) { polarity[v] = b; } -inline void Solver::setDecisionVar(Var v, bool b) -{ - if (b && !decision[v]) - dec_vars++; - else if (!b && decision[v]) - dec_vars--; - - decision[v] = b; - insertVarOrder(v); -} -inline void Solver::setConfBudget(int64_t x){ conflict_budget = conflicts + x; } -inline void Solver::setPropBudget(int64_t x){ propagation_budget = propagations + x; } -inline void Solver::interrupt(){ asynch_interrupt = true; } -inline void Solver::clearInterrupt(){ asynch_interrupt = false; } -inline void Solver::budgetOff(){ conflict_budget = propagation_budget = -1; } - -inline lbool Solver::solve () { budgetOff(); return solve_(); } -inline lbool Solver::solve (Lit p) { budgetOff(); assumptions.push(p); return solve_(); } -inline lbool Solver::solve (Lit p, Lit q) { budgetOff(); assumptions.push(p); assumptions.push(q); return solve_(); } -inline lbool Solver::solve (Lit p, Lit q, Lit r) { budgetOff(); assumptions.push(p); assumptions.push(q); assumptions.push(r); return solve_(); } -inline lbool Solver::solve (const vec<Lit>& assumps){ budgetOff(); assumps.copyTo(assumptions); return solve_(); } -inline lbool Solver::solveLimited (const vec<Lit>& assumps){ assumps.copyTo(assumptions); return solve_(); } -inline bool Solver::okay () const { return ok; } - -inline void Solver::toDimacs (const char* file){ vec<Lit> as; toDimacs(file, as); } -inline void Solver::toDimacs (const char* file, Lit p){ vec<Lit> as; as.push(p); toDimacs(file, as); } -inline void Solver::toDimacs (const char* file, Lit p, Lit q){ vec<Lit> as; as.push(p); as.push(q); toDimacs(file, as); } -inline void Solver::toDimacs (const char* file, Lit p, Lit q, Lit r){ vec<Lit> as; as.push(p); as.push(q); as.push(r); toDimacs(file, as); } - - -//================================================================================================= -// Debug etc: - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/core/SolverTypes.h b/src/prop/bvminisat/core/SolverTypes.h deleted file mode 100644 index fd0e86116..000000000 --- a/src/prop/bvminisat/core/SolverTypes.h +++ /dev/null @@ -1,435 +0,0 @@ -/***********************************************************************************[SolverTypes.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_SolverTypes_h -#define BVMinisat_SolverTypes_h - -#include "base/check.h" -#include "prop/bvminisat/mtl/Alg.h" -#include "prop/bvminisat/mtl/Alloc.h" -#include "prop/bvminisat/mtl/IntTypes.h" -#include "prop/bvminisat/mtl/Map.h" -#include "prop/bvminisat/mtl/Vec.h" - -namespace cvc5 { -namespace BVMinisat { -class Solver; -} -template <class Solver> -class TSatProof; -} // namespace cvc5 - -namespace cvc5 { - -namespace BVMinisat { - -//================================================================================================= -// Variables, literals, lifted booleans, clauses: - - -// NOTE! Variables are just integers. No abstraction here. They should be chosen from 0..N, -// so that they can be used as array indices. - -typedef int Var; -#define var_Undef (-1) - - -struct Lit { - int x; - - // Use this as a constructor: - friend Lit mkLit(Var var, bool sign); - - bool operator == (Lit p) const { return x == p.x; } - bool operator != (Lit p) const { return x != p.x; } - bool operator < (Lit p) const { return x < p.x; } // '<' makes p, ~p adjacent in the ordering. -}; - -inline Lit mkLit (Var var, bool sign = false) { Lit p; p.x = var + var + (int)sign; return p; } -inline Lit operator ~(Lit p) { Lit q; q.x = p.x ^ 1; return q; } -inline Lit operator ^(Lit p, bool b) { Lit q; q.x = p.x ^ (unsigned int)b; return q; } -inline bool sign (Lit p) { return p.x & 1; } -inline int var (Lit p) { return p.x >> 1; } - -// Mapping Literals to and from compact integers suitable for array indexing: -inline int toInt (Var v) { return v; } -inline int toInt (Lit p) { return p.x; } -inline Lit toLit (int i) { Lit p; p.x = i; return p; } - -struct LitHashFunction { - size_t operator () (const Lit& l) const { - return toInt(l); - } -}; - -//const Lit lit_Undef = mkLit(var_Undef, false); // }- Useful special constants. -//const Lit lit_Error = mkLit(var_Undef, true ); // } - -const Lit lit_Undef = { -2 }; // }- Useful special constants. -const Lit lit_Error = { -1 }; // } - -//================================================================================================= -// Lifted booleans: -// -// NOTE: this implementation is optimized for the case when comparisons between -// values are mostly -// between one variable and one constant. Some care had to be taken to -// make sure that gcc does enough constant propagation to produce sensible -// code, and this appears to be somewhat fragile unfortunately. - -#ifndef l_True -#define l_True (lbool((uint8_t)0)) // gcc does not do constant propagation if these are real constants. -#endif - -#ifndef l_False -#define l_False (lbool((uint8_t)1)) -#endif - -#ifndef l_Undef -#define l_Undef (lbool((uint8_t)2)) -#endif - -class lbool { - uint8_t value; - -public: - explicit lbool(uint8_t v) : value(v) { } - - lbool() : value(0) { } - explicit lbool(bool x) : value(!x) { } - - bool operator == (lbool b) const { return ((b.value&2) & (value&2)) | (!(b.value&2)&(value == b.value)); } - bool operator != (lbool b) const { return !(*this == b); } - lbool operator ^ (bool b) const { return lbool((uint8_t)(value^(uint8_t)b)); } - - lbool operator&&(lbool b) const - { - uint8_t sel = (this->value << 1) | (b.value << 3); - uint8_t v = (0xF7F755F4 >> sel) & 3; - return lbool(v); - } - - lbool operator || (lbool b) const { - uint8_t sel = (this->value << 1) | (b.value << 3); - uint8_t v = (0xFCFCF400 >> sel) & 3; - return lbool(v); } - - friend int toInt (lbool l); - friend lbool toLbool(int v); -}; -inline int toInt (lbool l) { return l.value; } -inline lbool toLbool(int v) { return lbool((uint8_t)v); } - -//================================================================================================= -// Clause -- a simple class for representing a clause: - -class Clause; -typedef RegionAllocator<uint32_t>::Ref CRef; - -class Clause { - struct { - unsigned mark : 2; - unsigned learnt : 1; - unsigned has_extra : 1; - unsigned reloced : 1; - unsigned size : 27; } header; - union { Lit lit; float act; uint32_t abs; CRef rel; } data[0]; - - friend class ClauseAllocator; - - // NOTE: This constructor cannot be used directly (doesn't allocate enough memory). - template<class V> - Clause(const V& ps, bool use_extra, bool learnt) { - header.mark = 0; - header.learnt = learnt; - header.has_extra = use_extra; - header.reloced = 0; - header.size = ps.size(); - - for (int i = 0; i < ps.size(); i++) data[i].lit = ps[i]; - - if (header.has_extra){ - if (header.learnt) - data[header.size].act = 0; - else - calcAbstraction(); - } - } - -public: - void calcAbstraction() { - Assert(header.has_extra); - uint32_t abstraction = 0; - for (int i = 0; i < size(); i++) - abstraction |= 1 << (var(data[i].lit) & 31); - data[header.size].abs = abstraction; - } - - int size () const { return header.size; } - void shrink(int i) - { - Assert(i <= size()); - if (header.has_extra) data[header.size - i] = data[header.size]; - header.size -= i; - } - void pop () { shrink(1); } - bool learnt () const { return header.learnt; } - bool has_extra () const { return header.has_extra; } - uint32_t mark () const { return header.mark; } - void mark (uint32_t m) { header.mark = m; } - const Lit& last () const { return data[header.size-1].lit; } - - bool reloced () const { return header.reloced; } - CRef relocation () const { return data[0].rel; } - void relocate (CRef c) { header.reloced = 1; data[0].rel = c; } - - // NOTE: somewhat unsafe to change the clause in-place! Must manually call 'calcAbstraction' afterwards for - // subsumption operations to behave correctly. - Lit& operator [] (int i) { return data[i].lit; } - Lit operator [] (int i) const { return data[i].lit; } - operator const Lit* (void) const { return (Lit*)data; } - - float& activity() - { - Assert(header.has_extra); - return data[header.size].act; - } - uint32_t abstraction() const - { - Assert(header.has_extra); - return data[header.size].abs; - } - - Lit subsumes (const Clause& other) const; - void strengthen (Lit p); -}; - - -//================================================================================================= -// ClauseAllocator -- a simple class for allocating memory for clauses: - - -const CRef CRef_Undef = RegionAllocator<uint32_t>::Ref_Undef; -const CRef CRef_Lazy = RegionAllocator<uint32_t>::Ref_Undef - 1; - -class ClauseAllocator : public RegionAllocator<uint32_t> -{ - static int clauseWord32Size(int size, bool has_extra){ - return (sizeof(Clause) + (sizeof(Lit) * (size + (int)has_extra))) / sizeof(uint32_t); } - public: - bool extra_clause_field; - - ClauseAllocator(uint32_t start_cap) : RegionAllocator<uint32_t>(start_cap), extra_clause_field(false){} - ClauseAllocator() : extra_clause_field(false){} - - void moveTo(ClauseAllocator& to){ - to.extra_clause_field = extra_clause_field; - RegionAllocator<uint32_t>::moveTo(to); } - - template<class Lits> - CRef alloc(const Lits& ps, bool learnt = false) - { - Assert(sizeof(Lit) == sizeof(uint32_t)); - Assert(sizeof(float) == sizeof(uint32_t)); - bool use_extra = learnt | extra_clause_field; - - CRef cid = RegionAllocator<uint32_t>::alloc( - clauseWord32Size(ps.size(), use_extra)); - new (lea(cid)) Clause(ps, use_extra, learnt); - - return cid; - } - - // Deref, Load Effective Address (LEA), Inverse of LEA (AEL): - Clause& operator[](Ref r) { return (Clause&)RegionAllocator<uint32_t>::operator[](r); } - const Clause& operator[](Ref r) const { return (Clause&)RegionAllocator<uint32_t>::operator[](r); } - Clause* lea (Ref r) { return (Clause*)RegionAllocator<uint32_t>::lea(r); } - const Clause* lea (Ref r) const { return (Clause*)RegionAllocator<uint32_t>::lea(r); } - Ref ael (const Clause* t){ return RegionAllocator<uint32_t>::ael((uint32_t*)t); } - - void free(CRef cid) - { - Clause& c = operator[](cid); - RegionAllocator<uint32_t>::free(clauseWord32Size(c.size(), c.has_extra())); - } - - void reloc(CRef& cr, ClauseAllocator& to); -}; - - -//================================================================================================= -// OccLists -- a class for maintaining occurence lists with lazy deletion: - -template<class Idx, class Vec, class Deleted> -class OccLists -{ - vec<Vec> occs; - vec<char> dirty; - vec<Idx> dirties; - Deleted deleted; - - public: - OccLists(const Deleted& d) : deleted(d) {} - - void init (const Idx& idx){ occs.growTo(toInt(idx)+1); dirty.growTo(toInt(idx)+1, 0); } - // Vec& operator[](const Idx& idx){ return occs[toInt(idx)]; } - Vec& operator[](const Idx& idx){ return occs[toInt(idx)]; } - Vec& lookup (const Idx& idx){ if (dirty[toInt(idx)]) clean(idx); return occs[toInt(idx)]; } - - void cleanAll (); - void clean (const Idx& idx); - void smudge (const Idx& idx){ - if (dirty[toInt(idx)] == 0){ - dirty[toInt(idx)] = 1; - dirties.push(idx); - } - } - - void clear(bool free = true){ - occs .clear(free); - dirty .clear(free); - dirties.clear(free); - } -}; - - -template<class Idx, class Vec, class Deleted> -void OccLists<Idx,Vec,Deleted>::cleanAll() -{ - for (int i = 0; i < dirties.size(); i++) - // Dirties may contain duplicates so check here if a variable is already cleaned: - if (dirty[toInt(dirties[i])]) - clean(dirties[i]); - dirties.clear(); -} - - -template<class Idx, class Vec, class Deleted> -void OccLists<Idx,Vec,Deleted>::clean(const Idx& idx) -{ - Vec& vec = occs[toInt(idx)]; - int i, j; - for (i = j = 0; i < vec.size(); i++) - if (!deleted(vec[i])) - vec[j++] = vec[i]; - vec.shrink(i - j); - dirty[toInt(idx)] = 0; -} - - -//================================================================================================= -// CMap -- a class for mapping clauses to values: - - -template<class T> -class CMap -{ - struct CRefHash { - uint32_t operator()(CRef cr) const { return (uint32_t)cr; } }; - - typedef Map<CRef, T, CRefHash> HashTable; - HashTable map; - - public: - // Size-operations: - void clear () { map.clear(); } - int size () const { return map.elems(); } - - // Insert/Remove/Test mapping: - void insert (CRef cr, const T& t){ map.insert(cr, t); } - void growTo (CRef cr, const T& t){ map.insert(cr, t); } // NOTE: for compatibility - void remove (CRef cr) { map.remove(cr); } - bool has (CRef cr, T& t) { return map.peek(cr, t); } - - // Vector interface (the clause 'c' must already exist): - const T& operator [] (CRef cr) const { return map[cr]; } - T& operator [] (CRef cr) { return map[cr]; } - - // Iteration (not transparent at all at the moment): - int bucket_count() const { return map.bucket_count(); } - const vec<typename HashTable::Pair>& bucket(int i) const { return map.bucket(i); } - - // Move contents to other map: - void moveTo(CMap& other){ map.moveTo(other.map); } - - // TMP debug: - void debug(){ - printf(" --- size = %d, bucket_count = %d\n", size(), map.bucket_count()); } -}; - -/*_________________________________________________________________________________________________ -| -| subsumes : (other : const Clause&) -> Lit -| -| Description: -| Checks if clause subsumes 'other', and at the same time, if it can be -used to simplify 'other' | by subsumption resolution. -| -| Result: -| lit_Error - No subsumption or simplification -| lit_Undef - Clause subsumes 'other' -| p - The literal p can be deleted from 'other' -|________________________________________________________________________________________________@*/ -inline Lit Clause::subsumes(const Clause& other) const -{ - //if (other.size() < size() || (extra.abst & ~other.extra.abst) != 0) - //if (other.size() < size() || (!learnt() && !other.learnt() && (extra.abst & ~other.extra.abst) != 0)) - Assert(!header.learnt); - Assert(!other.header.learnt); - Assert(header.has_extra); - Assert(other.header.has_extra); - if (other.header.size < header.size || (data[header.size].abs & ~other.data[other.header.size].abs) != 0) - return lit_Error; - - Lit ret = lit_Undef; - const Lit* c = (const Lit*)(*this); - const Lit* d = (const Lit*)other; - - for (unsigned i = 0; i < header.size; i++) { - // search for c[i] or ~c[i] - for (unsigned j = 0; j < other.header.size; j++) - if (c[i] == d[j]) - goto ok; - else if (ret == lit_Undef && c[i] == ~d[j]){ - ret = c[i]; - goto ok; - } - - // did not find it - return lit_Error; - ok:; - } - - return ret; -} - -inline void Clause::strengthen(Lit p) -{ - remove(*this, p); - calcAbstraction(); -} - - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/doc/ReleaseNotes-2.2.0.txt b/src/prop/bvminisat/doc/ReleaseNotes-2.2.0.txt deleted file mode 100644 index 7f084de2b..000000000 --- a/src/prop/bvminisat/doc/ReleaseNotes-2.2.0.txt +++ /dev/null @@ -1,79 +0,0 @@ -Release Notes for MiniSat 2.2.0 -=============================== - -Changes since version 2.0: - - * Started using a more standard release numbering. - - * Includes some now well-known heuristics: phase-saving and luby - restarts. The old heuristics are still present and can be activated - if needed. - - * Detection/Handling of out-of-memory and vector capacity - overflow. This is fairly new and relatively untested. - - * Simple resource controls: CPU-time, memory, number of - conflicts/decisions. - - * CPU-time limiting is implemented by a more general, but simple, - asynchronous interruption feature. This means that the solving - procedure can be interrupted from another thread or in a signal - handler. - - * Improved portability with respect to building on Solaris and with - Visual Studio. This is not regularly tested and chances are that - this have been broken since, but should be fairly easy to fix if - so. - - * Changed C++ file-extention to the less problematic ".cc". - - * Source code is now namespace-protected - - * Introducing a new Clause Memory Allocator that brings reduced - memory consumption on 64-bit architechtures and improved - performance (to some extent). The allocator uses a region-based - approach were all references to clauses are represented as a 32-bit - index into a global memory region that contains all clauses. To - free up and compact memory it uses a simple copying garbage - collector. - - * Improved unit-propagation by Blocking Literals. For each entry in - the watcher lists, pair the pointer to a clause with some - (arbitrary) literal from the clause. The idea is that if the - literal is currently true (i.e. the clause is satisfied) the - watchers of the clause does not need to be altered. This can thus - be detected without touching the clause's memory at all. As often - as can be done cheaply, the blocking literal for entries to the - watcher list of a literal 'p' is set to the other literal watched - in the corresponding clause. - - * Basic command-line/option handling system. Makes it easy to specify - options in the class that they affect, and whenever that class is - used in an executable, parsing of options and help messages are - brought in automatically. - - * General clean-up and various minor bug-fixes. - - * Changed implementation of variable-elimination/model-extension: - - - The interface is changed so that arbitrary remembering is no longer - possible. If you need to mention some variable again in the future, - this variable has to be frozen. - - - When eliminating a variable, only clauses that contain the variable - with one sign is necessary to store. Thereby making the other sign - a "default" value when extending models. - - - The memory consumption for eliminated clauses is further improved - by storing all eliminated clauses in a single contiguous vector. - - * Some common utility code (I/O, Parsing, CPU-time, etc) is ripped - out and placed in a separate "utils" directory. - - * The DIMACS parse is refactored so that it can be reused in other - applications (not very elegant, but at least possible). - - * Some simple improvements to scalability of preprocessing, using - more lazy clause removal from data-structures and a couple of - ad-hoc limits (the longest clause that can be produced in variable - elimination, and the longest clause used in backward subsumption). diff --git a/src/prop/bvminisat/mtl/Alg.h b/src/prop/bvminisat/mtl/Alg.h deleted file mode 100644 index ae72ca878..000000000 --- a/src/prop/bvminisat/mtl/Alg.h +++ /dev/null @@ -1,87 +0,0 @@ -/*******************************************************************************************[Alg.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Alg_h -#define BVMinisat_Alg_h - -#include "base/check.h" -#include "prop/bvminisat/mtl/Vec.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// Useful functions on vector-like types: - -//================================================================================================= -// Removing and searching for elements: -// - -template<class V, class T> -static inline void remove(V& ts, const T& t) -{ - int j = 0; - for (; j < ts.size() && ts[j] != t; j++); - Assert(j < ts.size()); - for (; j < ts.size()-1; j++) ts[j] = ts[j+1]; - ts.pop(); -} - - -template<class V, class T> -static inline bool find(V& ts, const T& t) -{ - int j = 0; - for (; j < ts.size() && ts[j] != t; j++); - return j < ts.size(); -} - - -//================================================================================================= -// Copying vectors with support for nested vector types: -// - -// Base case: -template<class T> -static inline void copy(const T& from, T& to) -{ - to = from; -} - -// Recursive case: -template<class T> -static inline void copy(const vec<T>& from, vec<T>& to, bool append = false) -{ - if (!append) - to.clear(); - for (int i = 0; i < from.size(); i++){ - to.push(); - copy(from[i], to.last()); - } -} - -template<class T> -static inline void append(const vec<T>& from, vec<T>& to){ copy(from, to, true); } - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/Alloc.h b/src/prop/bvminisat/mtl/Alloc.h deleted file mode 100644 index 2697f13b9..000000000 --- a/src/prop/bvminisat/mtl/Alloc.h +++ /dev/null @@ -1,154 +0,0 @@ -/*****************************************************************************************[Alloc.h] -Copyright (c) 2008-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - - -#ifndef BVMinisat_Alloc_h -#define BVMinisat_Alloc_h - -#include "base/check.h" -#include "prop/bvminisat/mtl/Vec.h" -#include "prop/bvminisat/mtl/XAlloc.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// Simple Region-based memory allocator: - -template<class T> -class RegionAllocator -{ - T* memory; - uint32_t sz; - uint32_t cap; - uint32_t wasted_; - - void capacity(uint32_t min_cap); - - public: - // TODO: make this a class for better type-checking? - typedef uint32_t Ref; - enum { Ref_Undef = UINT32_MAX }; - enum { Unit_Size = sizeof(uint32_t) }; - - explicit RegionAllocator(uint32_t start_cap = 1024*1024) : memory(NULL), sz(0), cap(0), wasted_(0){ capacity(start_cap); } - ~RegionAllocator() - { - if (memory != NULL) - ::free(memory); - } - - - uint32_t size () const { return sz; } - uint32_t wasted () const { return wasted_; } - - Ref alloc (int size); - void free (int size) { wasted_ += size; } - - // Deref, Load Effective Address (LEA), Inverse of LEA (AEL): - T& operator[](Ref r) - { - Assert(r >= 0 && r < sz); - return memory[r]; - } - const T& operator[](Ref r) const - { - Assert(r >= 0 && r < sz); - return memory[r]; - } - - T* lea(Ref r) - { - Assert(r >= 0 && r < sz); - return &memory[r]; - } - const T* lea(Ref r) const - { - Assert(r >= 0 && r < sz); - return &memory[r]; - } - Ref ael(const T* t) - { - Assert((void*)t >= (void*)&memory[0] - && (void*)t < (void*)&memory[sz - 1]); - return (Ref)(t - &memory[0]); - } - - void moveTo(RegionAllocator& to) { - if (to.memory != NULL) ::free(to.memory); - to.memory = memory; - to.sz = sz; - to.cap = cap; - to.wasted_ = wasted_; - - memory = NULL; - sz = cap = wasted_ = 0; - } - - -}; - -template<class T> -void RegionAllocator<T>::capacity(uint32_t min_cap) -{ - if (cap >= min_cap) return; - - uint32_t prev_cap = cap; - while (cap < min_cap){ - // NOTE: Multiply by a factor (13/8) without causing overflow, then add 2 and make the - // result even by clearing the least significant bit. The resulting sequence of capacities - // is carefully chosen to hit a maximum capacity that is close to the '2^32-1' limit when - // using 'uint32_t' as indices so that as much as possible of this space can be used. - uint32_t delta = ((cap >> 1) + (cap >> 3) + 2) & ~1; - cap += delta; - - if (cap <= prev_cap) - throw OutOfMemoryException(); - } - // printf(" .. (%p) cap = %u\n", this, cap); - - Assert(cap > 0); - memory = (T*)xrealloc(memory, sizeof(T)*cap); -} - - -template<class T> -typename RegionAllocator<T>::Ref -RegionAllocator<T>::alloc(int size) -{ - // printf("ALLOC called (this = %p, size = %d)\n", this, size); fflush(stdout); - Assert(size > 0); - capacity(sz + size); - - uint32_t prev_sz = sz; - sz += size; - - // Handle overflow: - if (sz < prev_sz) - throw OutOfMemoryException(); - - return prev_sz; -} - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/Heap.h b/src/prop/bvminisat/mtl/Heap.h deleted file mode 100644 index 73c1f07d2..000000000 --- a/src/prop/bvminisat/mtl/Heap.h +++ /dev/null @@ -1,161 +0,0 @@ -/******************************************************************************************[Heap.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Heap_h -#define BVMinisat_Heap_h - -#include "base/check.h" -#include "prop/bvminisat/mtl/Vec.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// A heap implementation with support for decrease/increase key. - - -template<class Comp> -class Heap { - Comp lt; // The heap is a minimum-heap with respect to this comparator - vec<int> heap; // Heap of integers - vec<int> indices; // Each integers position (index) in the Heap - - // Index "traversal" functions - static inline int left (int i) { return i*2+1; } - static inline int right (int i) { return (i+1)*2; } - static inline int parent(int i) { return (i-1) >> 1; } - - - void percolateUp(int i) - { - int x = heap[i]; - int p = parent(i); - - while (i != 0 && lt(x, heap[p])){ - heap[i] = heap[p]; - indices[heap[p]] = i; - i = p; - p = parent(p); - } - heap [i] = x; - indices[x] = i; - } - - - void percolateDown(int i) - { - int x = heap[i]; - while (left(i) < heap.size()){ - int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i); - if (!lt(heap[child], x)) break; - heap[i] = heap[child]; - indices[heap[i]] = i; - i = child; - } - heap [i] = x; - indices[x] = i; - } - - - public: - Heap(const Comp& c) : lt(c) { } - - int size () const { return heap.size(); } - bool empty () const { return heap.size() == 0; } - bool inHeap (int n) const { return n < indices.size() && indices[n] >= 0; } - int operator[](int index) const - { - Assert(index < heap.size()); - return heap[index]; - } - - void decrease(int n) - { - Assert(inHeap(n)); - percolateUp(indices[n]); - } - void increase(int n) - { - Assert(inHeap(n)); - percolateDown(indices[n]); - } - - // Safe variant of insert/decrease/increase: - void update(int n) - { - if (!inHeap(n)) - insert(n); - else { - percolateUp(indices[n]); - percolateDown(indices[n]); } - } - - - void insert(int n) - { - indices.growTo(n+1, -1); - Assert(!inHeap(n)); - - indices[n] = heap.size(); - heap.push(n); - percolateUp(indices[n]); - } - - - int removeMin() - { - int x = heap[0]; - heap[0] = heap.last(); - indices[heap[0]] = 0; - indices[x] = -1; - heap.pop(); - if (heap.size() > 1) percolateDown(0); - return x; - } - - - // Rebuild the heap from scratch, using the elements in 'ns': - void build(vec<int>& ns) { - for (int i = 0; i < heap.size(); i++) - indices[heap[i]] = -1; - heap.clear(); - - for (int i = 0; i < ns.size(); i++){ - indices[ns[i]] = i; - heap.push(ns[i]); } - - for (int i = heap.size() / 2 - 1; i >= 0; i--) - percolateDown(i); - } - - void clear(bool dealloc = false) - { - for (int i = 0; i < heap.size(); i++) - indices[heap[i]] = -1; - heap.clear(dealloc); - } -}; - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/IntTypes.h b/src/prop/bvminisat/mtl/IntTypes.h deleted file mode 100644 index 7856dc07c..000000000 --- a/src/prop/bvminisat/mtl/IntTypes.h +++ /dev/null @@ -1,50 +0,0 @@ -/**************************************************************************************[IntTypes.h] -Copyright (c) 2009-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_IntTypes_h -#define BVMinisat_IntTypes_h - -#ifdef __sun - // Not sure if there are newer versions that support C99 headers. The - // needed features are implemented in the headers below though: - -# include <sys/int_types.h> -# include <sys/int_fmtio.h> -# include <sys/int_limits.h> - -#else - -// In contrast to the original MiniSat source code, we are including the -// cstdint/cinttypes/climits headers instead of stdint.h/inttypes.h/limits.h -// here. This ensures that the macros in cinttypes/inttypes.h, e.g., PRIi64, -// are actually defined. The C99 standard suggested that those macros are only -// defined for C++ code when __STDC_FORMAT_MACROS is defined. This was never -// adopted by a C++ standard (https://en.cppreference.com/w/cpp/types/integer). -// However, certain versions of mingw-w64 seem to require it with inttypes.h -// but not cinttypes. -# include <cstdint> -# include <cinttypes> - -#endif - -#include <climits> - -//================================================================================================= - -#endif diff --git a/src/prop/bvminisat/mtl/Map.h b/src/prop/bvminisat/mtl/Map.h deleted file mode 100644 index 2d5db2561..000000000 --- a/src/prop/bvminisat/mtl/Map.h +++ /dev/null @@ -1,196 +0,0 @@ -/*******************************************************************************************[Map.h] -Copyright (c) 2006-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Map_h -#define BVMinisat_Map_h - -#include "base/check.h" -#include "prop/bvminisat/mtl/IntTypes.h" -#include "prop/bvminisat/mtl/Vec.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// Default hash/equals functions -// - -static inline uint32_t hash(uint32_t x){ return x; } -static inline uint32_t hash(uint64_t x){ return (uint32_t)x; } -static inline uint32_t hash(int32_t x) { return (uint32_t)x; } -static inline uint32_t hash(int64_t x) { return (uint32_t)x; } - -template<class K> struct Hash { uint32_t operator()(const K& k) const { return hash(k); } }; -template<class K> struct Equal { bool operator()(const K& k1, const K& k2) const { return k1 == k2; } }; - -template<class K> struct DeepHash { uint32_t operator()(const K* k) const { return hash(*k); } }; -template<class K> struct DeepEqual { bool operator()(const K* k1, const K* k2) const { return *k1 == *k2; } }; - - - -//================================================================================================= -// Some primes -// - -static const int nprimes = 25; -static const int primes [nprimes] = { 31, 73, 151, 313, 643, 1291, 2593, 5233, 10501, 21013, 42073, 84181, 168451, 337219, 674701, 1349473, 2699299, 5398891, 10798093, 21596719, 43193641, 86387383, 172775299, 345550609, 691101253 }; - -//================================================================================================= -// Hash table implementation of Maps -// - -template<class K, class D, class H = Hash<K>, class E = Equal<K> > -class Map { - public: - struct Pair { K key; D data; }; - - private: - H hash; - E equals; - - vec<Pair>* table; - int cap; - int size; - - // Don't allow copying (error prone): - Map<K, D, H, E>& operator=(Map<K, D, H, E>& other) { Assert(0); } - Map(Map<K, D, H, E>& other) { Assert(0); } - - bool checkCap(int new_size) const { return new_size > cap; } - - int32_t index (const K& k) const { return hash(k) % cap; } - void _insert (const K& k, const D& d) { - vec<Pair>& ps = table[index(k)]; - ps.push(); ps.last().key = k; ps.last().data = d; } - - void rehash () { - const vec<Pair>* old = table; - - int old_cap = cap; - int newsize = primes[0]; - for (int i = 1; newsize <= cap && i < nprimes; i++) - newsize = primes[i]; - - table = new vec<Pair>[newsize]; - cap = newsize; - - for (int i = 0; i < old_cap; i++){ - for (int j = 0; j < old[i].size(); j++){ - _insert(old[i][j].key, old[i][j].data); }} - - delete [] old; - - // printf(" --- rehashing, old-cap=%d, new-cap=%d\n", cap, newsize); - } - - - public: - - Map () : table(NULL), cap(0), size(0) {} - Map (const H& h, const E& e) : hash(h), equals(e), table(NULL), cap(0), size(0){} - ~Map () { delete [] table; } - - // PRECONDITION: the key must already exist in the map. - const D& operator [] (const K& k) const - { - Assert(size != 0); - const D* res = NULL; - const vec<Pair>& ps = table[index(k)]; - for (int i = 0; i < ps.size(); i++) - if (equals(ps[i].key, k)) res = &ps[i].data; - Assert(res != NULL); - return *res; - } - - // PRECONDITION: the key must already exist in the map. - D& operator [] (const K& k) - { - Assert(size != 0); - D* res = NULL; - vec<Pair>& ps = table[index(k)]; - for (int i = 0; i < ps.size(); i++) - if (equals(ps[i].key, k)) res = &ps[i].data; - Assert(res != NULL); - return *res; - } - - // PRECONDITION: the key must *NOT* exist in the map. - void insert (const K& k, const D& d) { if (checkCap(size+1)) rehash(); _insert(k, d); size++; } - bool peek (const K& k, D& d) const { - if (size == 0) return false; - const vec<Pair>& ps = table[index(k)]; - for (int i = 0; i < ps.size(); i++) - if (equals(ps[i].key, k)){ - d = ps[i].data; - return true; } - return false; - } - - bool has (const K& k) const { - if (size == 0) return false; - const vec<Pair>& ps = table[index(k)]; - for (int i = 0; i < ps.size(); i++) - if (equals(ps[i].key, k)) - return true; - return false; - } - - // PRECONDITION: the key must exist in the map. - void remove(const K& k) { - Assert(table != NULL); - vec<Pair>& ps = table[index(k)]; - int j = 0; - for (; j < ps.size() && !equals(ps[j].key, k); j++) - ; - Assert(j < ps.size()); - ps[j] = ps.last(); - ps.pop(); - size--; - } - - void clear () { - cap = size = 0; - delete [] table; - table = NULL; - } - - int elems() const { return size; } - int bucket_count() const { return cap; } - - // NOTE: the hash and equality objects are not moved by this method: - void moveTo(Map& other){ - delete [] other.table; - - other.table = table; - other.cap = cap; - other.size = size; - - table = NULL; - size = cap = 0; - } - - // NOTE: given a bit more time, I could make a more C++-style iterator out of this: - const vec<Pair>& bucket(int i) const { return table[i]; } -}; - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/Queue.h b/src/prop/bvminisat/mtl/Queue.h deleted file mode 100644 index 8407fd7ee..000000000 --- a/src/prop/bvminisat/mtl/Queue.h +++ /dev/null @@ -1,91 +0,0 @@ -/*****************************************************************************************[Queue.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Queue_h -#define BVMinisat_Queue_h - -#include "base/check.h" -#include "prop/bvminisat/mtl/Vec.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= - -template<class T> -class Queue { - vec<T> buf; - int first; - int end; - -public: - typedef T Key; - - Queue() : buf(1), first(0), end(0) {} - - void clear (bool dealloc = false) { buf.clear(dealloc); buf.growTo(1); first = end = 0; } - int size () const { return (end >= first) ? end - first : end - first + buf.size(); } - - const T& operator[](int index) const - { - Assert(index >= 0); - Assert(index < size()); - return buf[(first + index) % buf.size()]; - } - T& operator[](int index) - { - Assert(index >= 0); - Assert(index < size()); - return buf[(first + index) % buf.size()]; - } - - T peek() const - { - Assert(first != end); - return buf[first]; - } - void pop() - { - Assert(first != end); - first++; - if (first == buf.size()) first = 0; - } - void insert(T elem) { // INVARIANT: buf[end] is always unused - buf[end++] = elem; - if (end == buf.size()) end = 0; - if (first == end){ // Resize: - vec<T> tmp((buf.size()*3 + 1) >> 1); - //**/printf("queue alloc: %d elems (%.1f MB)\n", tmp.size(), tmp.size() * sizeof(T) / 1000000.0); - int i = 0; - for (int j = first; j < buf.size(); j++) tmp[i++] = buf[j]; - for (int j = 0 ; j < end ; j++) tmp[i++] = buf[j]; - first = 0; - end = buf.size(); - tmp.moveTo(buf); - } - } -}; - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/Sort.h b/src/prop/bvminisat/mtl/Sort.h deleted file mode 100644 index 30b3b5396..000000000 --- a/src/prop/bvminisat/mtl/Sort.h +++ /dev/null @@ -1,99 +0,0 @@ -/******************************************************************************************[Sort.h] -Copyright (c) 2003-2007, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Sort_h -#define BVMinisat_Sort_h - -#include "prop/bvminisat/mtl/Vec.h" - -//================================================================================================= -// Some sorting algorithms for vec's - -namespace cvc5 { -namespace BVMinisat { - -template<class T> -struct LessThan_default { - bool operator () (T x, T y) { return x < y; } -}; - - -template <class T, class LessThan> -void selectionSort(T* array, int size, LessThan lt) -{ - int i, j, best_i; - T tmp; - - for (i = 0; i < size-1; i++){ - best_i = i; - for (j = i+1; j < size; j++){ - if (lt(array[j], array[best_i])) - best_i = j; - } - tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp; - } -} -template <class T> static inline void selectionSort(T* array, int size) { - selectionSort(array, size, LessThan_default<T>()); } - -template <class T, class LessThan> -void sort(T* array, int size, LessThan lt) -{ - if (size <= 15) - selectionSort(array, size, lt); - - else{ - T pivot = array[size / 2]; - T tmp; - int i = -1; - int j = size; - - for(;;){ - do i++; while(lt(array[i], pivot)); - do j--; while(lt(pivot, array[j])); - - if (i >= j) break; - - tmp = array[i]; array[i] = array[j]; array[j] = tmp; - } - - sort(array , i , lt); - sort(&array[i], size-i, lt); - } -} -template <class T> static inline void sort(T* array, int size) { - sort(array, size, LessThan_default<T>()); } - - -//================================================================================================= -// For 'vec's: - - -template <class T, class LessThan> void sort(vec<T>& v, LessThan lt) { - sort((T*)v, v.size(), lt); } -template <class T> void sort(vec<T>& v) { - sort(v, LessThan_default<T>()); } - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/Vec.h b/src/prop/bvminisat/mtl/Vec.h deleted file mode 100644 index 047a89991..000000000 --- a/src/prop/bvminisat/mtl/Vec.h +++ /dev/null @@ -1,152 +0,0 @@ -/*******************************************************************************************[Vec.h] -Copyright (c) 2003-2007, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Vec_h -#define BVMinisat_Vec_h - -#include <new> - -#include "base/check.h" -#include "prop/bvminisat/mtl/IntTypes.h" -#include "prop/bvminisat/mtl/XAlloc.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// Automatically resizable arrays -// -// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc) - -template<class T> -class vec { - T* data; - int sz; - int cap; - - // Don't allow copying (error prone): - vec<T>& operator=(vec<T>& other) - { - Assert(0); - return *this; - } - vec(vec<T>& other) { Assert(0); } - - // Helpers for calculating next capacity: - static inline int imax (int x, int y) { int mask = (y-x) >> (sizeof(int)*8-1); return (x&mask) + (y&(~mask)); } - //static inline void nextCap(int& cap){ cap += ((cap >> 1) + 2) & ~1; } - static inline void nextCap(int& cap){ cap += ((cap >> 1) + 2) & ~1; } - -public: - // Constructors: - vec() : data(NULL) , sz(0) , cap(0) { } - explicit vec(int size) : data(NULL) , sz(0) , cap(0) { growTo(size); } - vec(int size, const T& pad) : data(NULL) , sz(0) , cap(0) { growTo(size, pad); } - ~vec() { clear(true); } - - // Pointer to first element: - operator T* (void) { return data; } - - // Size operations: - int size (void) const { return sz; } - void shrink(int nelems) - { - Assert(nelems <= sz); - for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); - } - void shrink_(int nelems) - { - Assert(nelems <= sz); - sz -= nelems; - } - int capacity (void) const { return cap; } - void capacity (int min_cap); - void growTo (int size); - void growTo (int size, const T& pad); - void clear (bool dealloc = false); - - // Stack interface: - void push (void) { if (sz == cap) capacity(sz+1); new (&data[sz]) T(); sz++; } - void push (const T& elem) { if (sz == cap) capacity(sz+1); data[sz++] = elem; } - void push_(const T& elem) - { - Assert(sz < cap); - data[sz++] = elem; - } - void pop(void) - { - Assert(sz > 0); - sz--, data[sz].~T(); - } - // NOTE: it seems possible that overflow can happen in the 'sz+1' expression of 'push()', but - // in fact it can not since it requires that 'cap' is equal to INT_MAX. This in turn can not - // happen given the way capacities are calculated (below). Essentially, all capacities are - // even, but INT_MAX is odd. - - const T& last (void) const { return data[sz-1]; } - T& last (void) { return data[sz-1]; } - - // Vector interface: - const T& operator [] (int index) const { return data[index]; } - T& operator [] (int index) { return data[index]; } - - // Duplicatation (preferred instead): - void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) copy[i] = data[i]; } - void moveTo(vec<T>& dest) { dest.clear(true); dest.data = data; dest.sz = sz; dest.cap = cap; data = NULL; sz = 0; cap = 0; } -}; - - -template<class T> -void vec<T>::capacity(int min_cap) { - if (cap >= min_cap) return; - int add = imax((min_cap - cap + 1) & ~1, ((cap >> 1) + 2) & ~1); // NOTE: grow by approximately 3/2 - if (add > INT_MAX - cap || (((data = (T*)::realloc(data, (cap += add) * sizeof(T))) == NULL) && errno == ENOMEM)) - throw OutOfMemoryException(); - } - - -template<class T> -void vec<T>::growTo(int size, const T& pad) { - if (sz >= size) return; - capacity(size); - for (int i = sz; i < size; i++) data[i] = pad; - sz = size; } - - -template<class T> -void vec<T>::growTo(int size) { - if (sz >= size) return; - capacity(size); - for (int i = sz; i < size; i++) new (&data[i]) T(); - sz = size; } - - -template<class T> -void vec<T>::clear(bool dealloc) { - if (data != NULL){ - for (int i = 0; i < sz; i++) data[i].~T(); - sz = 0; - if (dealloc) free(data), data = NULL, cap = 0; } } - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/mtl/XAlloc.h b/src/prop/bvminisat/mtl/XAlloc.h deleted file mode 100644 index 581915d36..000000000 --- a/src/prop/bvminisat/mtl/XAlloc.h +++ /dev/null @@ -1,47 +0,0 @@ -/****************************************************************************************[XAlloc.h] -Copyright (c) 2009-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - - -#ifndef BVMinisat_XAlloc_h -#define BVMinisat_XAlloc_h - -#include <errno.h> -#include <stdlib.h> - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// Simple layer on top of malloc/realloc to catch out-of-memory situtaions and provide some typing: - -class OutOfMemoryException{}; -static inline void* xrealloc(void *ptr, size_t size) -{ - void* mem = realloc(ptr, size); - if (mem == NULL && errno == ENOMEM){ - throw OutOfMemoryException(); - }else - return mem; -} - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/simp/SimpSolver.cc b/src/prop/bvminisat/simp/SimpSolver.cc deleted file mode 100644 index e399fac4c..000000000 --- a/src/prop/bvminisat/simp/SimpSolver.cc +++ /dev/null @@ -1,812 +0,0 @@ -/***********************************************************************************[SimpSolver.cc] -Copyright (c) 2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#include "prop/bvminisat/simp/SimpSolver.h" - -#include "base/check.h" -#include "options/bv_options.h" -#include "options/smt_options.h" -#include "proof/clause_id.h" -#include "prop/bvminisat/mtl/Sort.h" -#include "prop/bvminisat/utils/System.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================= -// Options: - - -static const char* _cat = "SIMP"; - -static BoolOption opt_use_asymm (_cat, "asymm", "Shrink clauses by asymmetric branching.", false); -static BoolOption opt_use_rcheck (_cat, "rcheck", "Check if a clause is already implied. (costly)", false); -static BoolOption opt_use_elim (_cat, "elim", "Perform variable elimination.", true); -static IntOption opt_grow (_cat, "grow", "Allow a variable elimination step to grow by a number of clauses.", 0); -static IntOption opt_clause_lim (_cat, "cl-lim", "Variables are not eliminated if it produces a resolvent with a length above this limit. -1 means no limit", 20, IntRange(-1, INT32_MAX)); -static IntOption opt_subsumption_lim (_cat, "sub-lim", "Do not check if subsumption against a clause larger than this. -1 means no limit.", 1000, IntRange(-1, INT32_MAX)); -static DoubleOption opt_simp_garbage_frac(_cat, "simp-gc-frac", "The fraction of wasted memory allowed before a garbage collection is triggered during simplification.", 0.5, DoubleRange(0, false, HUGE_VAL, false)); - - -//================================================================================================= -// Constructor/Destructor: - -SimpSolver::SimpSolver(cvc5::context::Context* context) - : Solver(context), - grow(opt_grow), - clause_lim(opt_clause_lim), - subsumption_lim(opt_subsumption_lim), - simp_garbage_frac(opt_simp_garbage_frac), - use_asymm(opt_use_asymm), - use_rcheck(opt_use_rcheck), - use_elim(opt_use_elim - && cvc5::options::bitblastMode() - == cvc5::options::BitblastMode::EAGER - && !cvc5::options::produceModels()), - merges(0), - asymm_lits(0), - eliminated_vars(0), - elimorder(1), - use_simplification(true), - occurs(ClauseDeleted(ca)), - elim_heap(ElimLt(n_occ)), - bwdsub_assigns(0), - n_touched(0) -{ - - vec<Lit> dummy(1,lit_Undef); - ca.extra_clause_field = true; // NOTE: must happen before allocating the dummy clause below. - bwdsub_tmpunit = ca.alloc(dummy); - remove_satisfied = false; - - // add the initialization for all the internal variables - for (int i = frozen.size(); i < vardata.size(); ++ i) { - frozen .push(1); - eliminated.push(0); - if (use_simplification){ - n_occ .push(0); - n_occ .push(0); - occurs .init(i); - touched .push(0); - elim_heap .insert(i); - } - } - -} - - -SimpSolver::~SimpSolver() -{ - // cvc5::StatisticsRegistry::unregisterStat(&total_eliminate_time); -} - - -Var SimpSolver::newVar(bool sign, bool dvar, bool freeze) { - Var v = Solver::newVar(sign, dvar); - - frozen .push((char)false); - eliminated.push((char)false); - - if (use_simplification){ - n_occ .push(0); - n_occ .push(0); - occurs .init(v); - touched .push(0); - elim_heap .insert(v); - if (freeze) { - setFrozen(v, true); - } - } - return v; -} - - - -lbool SimpSolver::solve_(bool do_simp, bool turn_off_simp) -{ - only_bcp = false; - - vec<Var> extra_frozen; - lbool result = l_True; - - do_simp &= use_simplification; - - if (do_simp) { - // Assumptions must be temporarily frozen to run variable elimination: - for (int i = 0; i < assumptions.size(); i++){ - Var v = var(assumptions[i]); - - // If an assumption has been eliminated, remember it. - Assert(!isEliminated(v)); - - if (!frozen[v]){ - // Freeze and store. - setFrozen(v, true); - extra_frozen.push(v); - } } - - if (do_simp && clause_added) { - cancelUntil(0); - result = lbool(eliminate(turn_off_simp)); - clause_added = false; - } - } - - if (result == l_True) - result = Solver::solve_(); - else if (verbosity >= 1) - printf("===============================================================================\n"); - - if (do_simp) - // Unfreeze the assumptions that were frozen: - for (int i = 0; i < extra_frozen.size(); i++) - setFrozen(extra_frozen[i], false); - - return result; -} - - - -bool SimpSolver::addClause_(vec<Lit>& ps, ClauseId& id) -{ -#ifdef CVC5_ASSERTIONS - for (int i = 0; i < ps.size(); i++) Assert(!isEliminated(var(ps[i]))); -#endif - - int nclauses = clauses.size(); - - if (use_rcheck && implied(ps)) - return true; - - if (!Solver::addClause_(ps, id)) - return false; - - if (use_simplification && clauses.size() == nclauses + 1){ - CRef cr = clauses.last(); - const Clause& clause = ca[cr]; - - // NOTE: the clause is added to the queue immediately and then - // again during 'gatherTouchedClauses()'. If nothing happens - // in between, it will only be checked once. Otherwise, it may - // be checked twice unnecessarily. This is an unfortunate - // consequence of how backward subsumption is used to mimic - // forward subsumption. - subsumption_queue.insert(cr); - for (int i = 0; i < clause.size(); i++) - { - occurs[var(clause[i])].push(cr); - n_occ[toInt(clause[i])]++; - touched[var(clause[i])] = 1; - n_touched++; - if (elim_heap.inHeap(var(clause[i]))) - elim_heap.increase(var(clause[i])); - } - } - - return true; -} - - -void SimpSolver::removeClause(CRef cr) -{ - const Clause& clause = ca[cr]; - - if (use_simplification) - { - for (int i = 0; i < clause.size(); i++) - { - n_occ[toInt(clause[i])]--; - updateElimHeap(var(clause[i])); - occurs.smudge(var(clause[i])); - } - } - Solver::removeClause(cr); -} - - -bool SimpSolver::strengthenClause(CRef cr, Lit l) -{ - Clause& clause = ca[cr]; - Assert(decisionLevel() == 0); - Assert(use_simplification); - - // FIX: this is too inefficient but would be nice to have (properly - // implemented) if (!find(subsumption_queue, &clause)) - subsumption_queue.insert(cr); - - if (clause.size() == 2) - { - removeClause(cr); - clause.strengthen(l); - } - else - { - detachClause(cr, true); - clause.strengthen(l); - attachClause(cr); - remove(occurs[var(l)], cr); - n_occ[toInt(l)]--; - updateElimHeap(var(l)); - } - - return clause.size() == 1 ? enqueue(clause[0]) && propagate() == CRef_Undef - : true; -} - - -// Returns FALSE if clause is always satisfied ('out_clause' should not be used). -bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& out_clause) -{ - merges++; - out_clause.clear(); - - bool ps_smallest = _ps.size() < _qs.size(); - const Clause& ps = ps_smallest ? _qs : _ps; - const Clause& qs = ps_smallest ? _ps : _qs; - - for (int i = 0; i < qs.size(); i++) - { - if (var(qs[i]) != v) - { - for (int j = 0; j < ps.size(); j++) - { - if (var(ps[j]) == var(qs[i])) - { - if (ps[j] == ~qs[i]) - return false; - else - goto next; - } - } - out_clause.push(qs[i]); - } - next:; - } - - for (int i = 0; i < ps.size(); i++) - if (var(ps[i]) != v) - out_clause.push(ps[i]); - - return true; -} - - -// Returns FALSE if clause is always satisfied. -bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, int& size) -{ - merges++; - - bool ps_smallest = _ps.size() < _qs.size(); - const Clause& ps = ps_smallest ? _qs : _ps; - const Clause& qs = ps_smallest ? _ps : _qs; - const Lit* __ps = (const Lit*)ps; - const Lit* __qs = (const Lit*)qs; - - size = ps.size()-1; - - for (int i = 0; i < qs.size(); i++) - { - if (var(__qs[i]) != v) - { - for (int j = 0; j < ps.size(); j++) - { - if (var(__ps[j]) == var(__qs[i])) - { - if (__ps[j] == ~__qs[i]) - return false; - else - goto next; - } - } - size++; - } - next:; - } - - return true; -} - - -void SimpSolver::gatherTouchedClauses() -{ - if (n_touched == 0) return; - - int i,j; - for (i = j = 0; i < subsumption_queue.size(); i++) - if (ca[subsumption_queue[i]].mark() == 0) - ca[subsumption_queue[i]].mark(2); - - for (i = 0; i < touched.size(); i++) - if (touched[i]){ - const vec<CRef>& cs = occurs.lookup(i); - for (j = 0; j < cs.size(); j++) - if (ca[cs[j]].mark() == 0){ - subsumption_queue.insert(cs[j]); - ca[cs[j]].mark(2); - } - touched[i] = 0; - } - - for (i = 0; i < subsumption_queue.size(); i++) - if (ca[subsumption_queue[i]].mark() == 2) - ca[subsumption_queue[i]].mark(0); - - n_touched = 0; -} - -bool SimpSolver::implied(const vec<Lit>& clause) -{ - Assert(decisionLevel() == 0); - - trail_lim.push(trail.size()); - for (int i = 0; i < clause.size(); i++) - { - if (value(clause[i]) == l_True) - { - cancelUntil(0); - return false; - } - else if (value(clause[i]) != l_False) - { - Assert(value(clause[i]) == l_Undef); - uncheckedEnqueue(~clause[i]); - } - } - - bool result = propagate() != CRef_Undef; - cancelUntil(0); - return result; -} - - -// Backward subsumption + backward subsumption resolution -bool SimpSolver::backwardSubsumptionCheck(bool verbose) -{ - int cnt = 0; - int subsumed = 0; - int deleted_literals = 0; - Assert(decisionLevel() == 0); - - while (subsumption_queue.size() > 0 || bwdsub_assigns < trail.size()){ - - // Empty subsumption queue and return immediately on user-interrupt: - if (asynch_interrupt){ - subsumption_queue.clear(); - bwdsub_assigns = trail.size(); - break; } - - // Check top-level assignments by creating a dummy clause and placing it in the queue: - if (subsumption_queue.size() == 0 && bwdsub_assigns < trail.size()){ - Lit l = trail[bwdsub_assigns++]; - ca[bwdsub_tmpunit][0] = l; - ca[bwdsub_tmpunit].calcAbstraction(); - subsumption_queue.insert(bwdsub_tmpunit); } - - CRef cr = subsumption_queue.peek(); subsumption_queue.pop(); - Clause& clause = ca[cr]; - - if (clause.mark()) continue; - - if (verbose && verbosity >= 2 && cnt++ % 1000 == 0) - printf("subsumption left: %10d (%10d subsumed, %10d deleted literals)\r", subsumption_queue.size(), subsumed, deleted_literals); - - Assert(clause.size() > 1 - || value(clause[0]) == l_True); // Unit-clauses should have been - // propagated before this point. - - // Find best variable to scan: - Var best = var(clause[0]); - for (int i = 1; i < clause.size(); i++) - if (occurs[var(clause[i])].size() < occurs[best].size()) - best = var(clause[i]); - - // Search all candidates: - vec<CRef>& _cs = occurs.lookup(best); - CRef* cs = (CRef*)_cs; - - for (int j = 0; j < _cs.size(); j++) - if (clause.mark()) - break; - else if (!ca[cs[j]].mark() && cs[j] != cr - && (subsumption_lim == -1 - || ca[cs[j]].size() < subsumption_lim)) - { - Lit l = clause.subsumes(ca[cs[j]]); - - if (l == lit_Undef) - subsumed++, removeClause(cs[j]); - else if (l != lit_Error) - { - deleted_literals++; - - if (!strengthenClause(cs[j], ~l)) return false; - - // Did current candidate get deleted from cs? Then check candidate - // at index j again: - if (var(l) == best) j--; - } - } - } - - return true; -} - - -bool SimpSolver::asymm(Var v, CRef cr) -{ - Clause& clause = ca[cr]; - Assert(decisionLevel() == 0); - - if (clause.mark() || satisfied(clause)) return true; - - trail_lim.push(trail.size()); - Lit l = lit_Undef; - for (int i = 0; i < clause.size(); i++) - if (var(clause[i]) != v && value(clause[i]) != l_False) - uncheckedEnqueue(~clause[i]); - else - l = clause[i]; - - if (propagate() != CRef_Undef) - { - cancelUntil(0); - asymm_lits++; - if (!strengthenClause(cr, l)) return false; - } - else - cancelUntil(0); - - return true; -} - - -bool SimpSolver::asymmVar(Var v) -{ - Assert(use_simplification); - - const vec<CRef>& cls = occurs.lookup(v); - - if (value(v) != l_Undef || cls.size() == 0) return true; - - for (int i = 0; i < cls.size(); i++) - if (!asymm(v, cls[i])) return false; - - return backwardSubsumptionCheck(); -} - - -static void mkElimClause(vec<uint32_t>& elimclauses, Lit x) -{ - elimclauses.push(toInt(x)); - elimclauses.push(1); -} - -static void mkElimClause(vec<uint32_t>& elimclauses, Var v, Clause& clause) -{ - int first = elimclauses.size(); - int v_pos = -1; - - // Copy clause to elimclauses-vector. Remember position where the - // variable 'v' occurs: - for (int i = 0; i < clause.size(); i++) - { - elimclauses.push(toInt(clause[i])); - if (var(clause[i]) == v) v_pos = i + first; - } - Assert(v_pos != -1); - - // Swap the first literal with the 'v' literal, so that the literal - // containing 'v' will occur first in the clause: - uint32_t tmp = elimclauses[v_pos]; - elimclauses[v_pos] = elimclauses[first]; - elimclauses[first] = tmp; - - // Store the length of the clause last: - elimclauses.push(clause.size()); -} - - - -bool SimpSolver::eliminateVar(Var v) -{ - Assert(!frozen[v]); - Assert(!isEliminated(v)); - Assert(value(v) == l_Undef); - - // Split the occurrences into positive and negative: - // - const vec<CRef>& cls = occurs.lookup(v); - vec<CRef> pos, neg; - for (int i = 0; i < cls.size(); i++) - (find(ca[cls[i]], mkLit(v)) ? pos : neg).push(cls[i]); - - // Check whether the increase in number of clauses stays within the allowed - // ('grow'). Moreover, no clause must exceed the limit on the maximal clause - // size (if it is set): - // - int cnt = 0; - int clause_size = 0; - - for (int i = 0; i < pos.size(); i++) - for (int j = 0; j < neg.size(); j++) - if (merge(ca[pos[i]], ca[neg[j]], v, clause_size) - && (++cnt > cls.size() + grow - || (clause_lim != -1 && clause_size > clause_lim))) - return true; - - // Delete and store old clauses: - eliminated[v] = true; - setDecisionVar(v, false); - eliminated_vars++; - - if (pos.size() > neg.size()) - { - for (int i = 0; i < neg.size(); i++) - mkElimClause(elimclauses, v, ca[neg[i]]); - mkElimClause(elimclauses, mkLit(v)); - } - else - { - for (int i = 0; i < pos.size(); i++) - mkElimClause(elimclauses, v, ca[pos[i]]); - mkElimClause(elimclauses, ~mkLit(v)); - } - - for (int i = 0; i < cls.size(); i++) removeClause(cls[i]); - - // Produce clauses in cross product: - vec<Lit>& resolvent = add_tmp; - for (int i = 0; i < pos.size(); i++) - for (int j = 0; j < neg.size(); j++) { - ClauseId id = -1; - if (merge(ca[pos[i]], ca[neg[j]], v, resolvent) && - !addClause_(resolvent, id)) - return false; - } - - // Free occurs list for this variable: - occurs[v].clear(true); - - // Free watchers lists for this variable, if possible: - if (watches[ mkLit(v)].size() == 0) watches[ mkLit(v)].clear(true); - if (watches[~mkLit(v)].size() == 0) watches[~mkLit(v)].clear(true); - - return backwardSubsumptionCheck(); -} - - -bool SimpSolver::substitute(Var v, Lit x) -{ - Assert(!frozen[v]); - Assert(!isEliminated(v)); - Assert(value(v) == l_Undef); - - if (!ok) return false; - - eliminated[v] = true; - setDecisionVar(v, false); - const vec<CRef>& cls = occurs.lookup(v); - - vec<Lit>& subst_clause = add_tmp; - for (int i = 0; i < cls.size(); i++) - { - Clause& clause = ca[cls[i]]; - - subst_clause.clear(); - for (int j = 0; j < clause.size(); j++) - { - Lit p = clause[j]; - subst_clause.push(var(p) == v ? x ^ sign(p) : p); - } - - removeClause(cls[i]); - ClauseId id; - if (!addClause_(subst_clause, id)) return ok = false; - } - - return true; -} - - -void SimpSolver::extendModel() -{ - int i, j; - Lit x; - - for (i = elimclauses.size()-1; i > 0; i -= j){ - for (j = elimclauses[i--]; j > 1; j--, i--) - if (modelValue(toLit(elimclauses[i])) != l_False) - goto next; - - x = toLit(elimclauses[i]); - model[var(x)] = lbool(!sign(x)); - next:; - } -} - - -bool SimpSolver::eliminate(bool turn_off_elim) -{ - // cvc5::TimerStat::CodeTimer codeTimer(total_eliminate_time); - - if (!simplify()) - return false; - else if (!use_simplification) - return true; - - // Main simplification loop: - // - while (n_touched > 0 || bwdsub_assigns < trail.size() || elim_heap.size() > 0) - { - gatherTouchedClauses(); - // printf(" ## (time = %6.2f s) BWD-SUB: queue = %d, trail = %d\n", - // cpuTime(), subsumption_queue.size(), trail.size() - bwdsub_assigns); - if ((subsumption_queue.size() > 0 || bwdsub_assigns < trail.size()) - && !backwardSubsumptionCheck(true)) - { - ok = false; - goto cleanup; - } - - // Empty elim_heap and return immediately on user-interrupt: - if (asynch_interrupt) - { - Assert(bwdsub_assigns == trail.size()); - Assert(subsumption_queue.size() == 0); - Assert(n_touched == 0); - elim_heap.clear(); - goto cleanup; - } - - // printf(" ## (time = %6.2f s) ELIM: vars = %d\n", cpuTime(), - // elim_heap.size()); - for (int cnt = 0; !elim_heap.empty(); cnt++) - { - Var elim = elim_heap.removeMin(); - - if (asynch_interrupt) break; - - if (isEliminated(elim) || value(elim) != l_Undef) continue; - - if (verbosity >= 2 && cnt % 100 == 0) - printf("elimination left: %10d\r", elim_heap.size()); - - if (use_asymm) - { - // Temporarily freeze variable. Otherwise, it would immediately end up - // on the queue again: - bool was_frozen = frozen[elim]; - frozen[elim] = true; - if (!asymmVar(elim)) - { - ok = false; - goto cleanup; - } - frozen[elim] = was_frozen; - } - - // At this point, the variable may have been set by assymetric branching, - // so check it again. Also, don't eliminate frozen variables: - if (use_elim && value(elim) == l_Undef && !frozen[elim] - && !eliminateVar(elim)) - { - ok = false; - goto cleanup; - } - - checkGarbage(simp_garbage_frac); - } - - Assert(subsumption_queue.size() == 0); - } - cleanup: - - // If no more simplification is needed, free all simplification-related data structures: - if (turn_off_elim){ - touched .clear(true); - occurs .clear(true); - n_occ .clear(true); - elim_heap.clear(true); - subsumption_queue.clear(true); - - use_simplification = false; - remove_satisfied = true; - ca.extra_clause_field = false; - - // Force full cleanup (this is safe and desirable since it only happens once): - rebuildOrderHeap(); - garbageCollect(); - }else{ - // Cheaper cleanup: - cleanUpClauses(); // TODO: can we make 'cleanUpClauses()' not be linear in the problem size somehow? - checkGarbage(); - } - - if (verbosity >= 1 && elimclauses.size() > 0) - printf( - "| Eliminated clauses: %10.2f Mb " - " |\n", - double(elimclauses.size() * sizeof(uint32_t)) / (1024 * 1024)); - - return ok; - - - -} - - -void SimpSolver::cleanUpClauses() -{ - occurs.cleanAll(); - int i,j; - for (i = j = 0; i < clauses.size(); i++) - if (ca[clauses[i]].mark() == 0) - clauses[j++] = clauses[i]; - clauses.shrink(i - j); -} - - -//================================================================================================= -// Garbage Collection methods: - - -void SimpSolver::relocAll(ClauseAllocator& to) -{ - if (!use_simplification) return; - - // All occurs lists: - // - for (int i = 0; i < nVars(); i++){ - vec<CRef>& cs = occurs[i]; - for (int j = 0; j < cs.size(); j++) - ca.reloc(cs[j], to); - } - - // Subsumption queue: - // - for (int i = 0; i < subsumption_queue.size(); i++) - ca.reloc(subsumption_queue[i], to); - - // Temporary clause: - // - ca.reloc(bwdsub_tmpunit, to); -} - - -void SimpSolver::garbageCollect() -{ - // Initialize the next region to a size corresponding to the estimated utilization degree. This - // is not precise but should avoid some unnecessary reallocations for the new region: - ClauseAllocator to(ca.size() - ca.wasted()); - - cleanUpClauses(); - to.extra_clause_field = ca.extra_clause_field; // NOTE: this is important to keep (or lose) the extra fields. - relocAll(to); - Solver::relocAll(to); - if (verbosity >= 2) - printf( - "| Garbage collection: %12d bytes => %12d bytes |\n", - ca.size() * ClauseAllocator::Unit_Size, - to.size() * ClauseAllocator::Unit_Size); - to.moveTo(ca); -} - -} // namespace BVMinisat -} // namespace cvc5 diff --git a/src/prop/bvminisat/simp/SimpSolver.h b/src/prop/bvminisat/simp/SimpSolver.h deleted file mode 100644 index ec6ed375a..000000000 --- a/src/prop/bvminisat/simp/SimpSolver.h +++ /dev/null @@ -1,243 +0,0 @@ -/************************************************************************************[SimpSolver.h] -Copyright (c) 2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_SimpSolver_h -#define BVMinisat_SimpSolver_h - -#include "base/check.h" -#include "proof/clause_id.h" -#include "prop/bvminisat/core/Solver.h" -#include "prop/bvminisat/mtl/Queue.h" - -namespace cvc5 { - -namespace context { -class Context; -} - -namespace BVMinisat { - -//================================================================================================= - - -class SimpSolver : public Solver { - public: - // Constructor/Destructor: - // - SimpSolver(cvc5::context::Context* context); - ~SimpSolver(); - - // Problem specification: - // - Var newVar(bool polarity = true, bool dvar = true, bool freeze = false); - bool addClause(const vec<Lit>& ps, ClauseId& id); - bool addEmptyClause(); // Add the empty clause to the solver. - bool addClause(Lit p, ClauseId& id); // Add a unit clause to the solver. - bool addClause(Lit p, - Lit q, - ClauseId& id); // Add a binary clause to the solver. - bool addClause(Lit p, - Lit q, - Lit r, - ClauseId& id); // Add a ternary clause to the solver. - bool addClause_(vec<Lit>& ps, ClauseId& id); - bool substitute(Var v, Lit x); // Replace all occurrences of v with x (may - // cause a contradiction). - - // Variable mode: - // - void setFrozen(Var v, - bool b); // If a variable is frozen it will not be eliminated. - bool isEliminated(Var v) const; - - // Solving: - // - lbool solve(const vec<Lit>& assumps, - bool do_simp = true, - bool turn_off_simp = false); - lbool solveLimited(const vec<Lit>& assumps, - bool do_simp = true, - bool turn_off_simp = false); - lbool solveLimited(bool do_simp = true, bool turn_off_simp = false); - lbool solve(bool do_simp = true, bool turn_off_simp = false); - lbool solve(Lit p, bool do_simp = true, bool turn_off_simp = false); - lbool solve(Lit p, Lit q, bool do_simp = true, bool turn_off_simp = false); - lbool solve( - Lit p, Lit q, Lit r, bool do_simp = true, bool turn_off_simp = false); - bool eliminate(bool turn_off_elim = false); // Perform variable elimination - // based simplification. - - // Memory managment: - // - void garbageCollect() override; - - // Generate a (possibly simplified) DIMACS file: - // -#if 0 - void toDimacs (const char* file, const vec<Lit>& assumps); - void toDimacs (const char* file); - void toDimacs (const char* file, Lit p); - void toDimacs (const char* file, Lit p, Lit q); - void toDimacs (const char* file, Lit p, Lit q, Lit r); -#endif - - // Mode of operation: - // - int grow; // Allow a variable elimination step to grow by a number of clauses (default to zero). - int clause_lim; // Variables are not eliminated if it produces a resolvent with a length above this limit. - // -1 means no limit. - int subsumption_lim; // Do not check if subsumption against a clause larger than this. -1 means no limit. - double simp_garbage_frac; // A different limit for when to issue a GC during simplification (Also see 'garbage_frac'). - - bool use_asymm; // Shrink clauses by asymmetric branching. - bool use_rcheck; // Check if a clause is already implied. Prett costly, and subsumes subsumptions :) - bool use_elim; // Perform variable elimination. - - // Statistics: - // - int merges; - int asymm_lits; - int64_t eliminated_vars; - // cvc5::TimerStat total_eliminate_time; - - protected: - - // Helper structures: - // - struct ElimLt { - const vec<int>& n_occ; - explicit ElimLt(const vec<int>& no) : n_occ(no) {} - - // TODO: are 64-bit operations here noticably bad on 32-bit platforms? Could use a saturating - // 32-bit implementation instead then, but this will have to do for now. - uint64_t cost (Var x) const { return (uint64_t)n_occ[toInt(mkLit(x))] * (uint64_t)n_occ[toInt(~mkLit(x))]; } - bool operator()(Var x, Var y) const { return cost(x) < cost(y); } - - // TODO: investigate this order alternative more. - // bool operator()(Var x, Var y) const { - // int c_x = cost(x); - // int c_y = cost(y); - // return c_x < c_y || c_x == c_y && x < y; } - }; - - struct ClauseDeleted { - const ClauseAllocator& ca; - explicit ClauseDeleted(const ClauseAllocator& _ca) : ca(_ca) {} - bool operator()(const CRef& cr) const { return ca[cr].mark() == 1; } }; - - // Solver state: - // - int elimorder; - bool use_simplification; - vec<uint32_t> elimclauses; - vec<char> touched; - OccLists<Var, vec<CRef>, ClauseDeleted> - occurs; - vec<int> n_occ; - Heap<ElimLt> elim_heap; - Queue<CRef> subsumption_queue; - vec<char> frozen; - vec<char> eliminated; - int bwdsub_assigns; - int n_touched; - - // Temporaries: - // - CRef bwdsub_tmpunit; - - // Main internal methods: - // - lbool solve_ (bool do_simp = true, bool turn_off_simp = false); - bool asymm (Var v, CRef cr); - bool asymmVar (Var v); - void updateElimHeap (Var v); - void gatherTouchedClauses (); - bool merge (const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& out_clause); - bool merge (const Clause& _ps, const Clause& _qs, Var v, int& size); - bool backwardSubsumptionCheck (bool verbose = false); - bool eliminateVar (Var v); - void extendModel (); - - void removeClause (CRef cr); - bool strengthenClause (CRef cr, Lit l); - void cleanUpClauses (); - bool implied (const vec<Lit>& c); - void relocAll (ClauseAllocator& to); -}; - - -//================================================================================================= -// Implementation of inline methods: - - -inline bool SimpSolver::isEliminated (Var v) const { return eliminated[v]; } -inline void SimpSolver::updateElimHeap(Var v) { - Assert(use_simplification); - // if (!frozen[v] && !isEliminated(v) && value(v) == l_Undef) - if (elim_heap.inHeap(v) - || (!frozen[v] && !isEliminated(v) && value(v) == l_Undef)) - elim_heap.update(v); -} - -inline bool SimpSolver::addClause (const vec<Lit>& ps, ClauseId& id) { ps.copyTo(add_tmp); return addClause_(add_tmp, id); } -inline bool SimpSolver::addEmptyClause() { add_tmp.clear(); ClauseId id; return addClause_(add_tmp, id); } -inline bool SimpSolver::addClause (Lit p, ClauseId& id) { add_tmp.clear(); add_tmp.push(p); return addClause_(add_tmp, id); } -inline bool SimpSolver::addClause (Lit p, Lit q, ClauseId& id) { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); return addClause_(add_tmp, id); } -inline bool SimpSolver::addClause (Lit p, Lit q, Lit r, ClauseId& id) { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); add_tmp.push(r); return addClause_(add_tmp, id); } -inline void SimpSolver::setFrozen (Var v, bool b) { frozen[v] = (char)b; if (use_simplification && !b) { updateElimHeap(v); } } - -inline lbool SimpSolver::solve ( bool do_simp, bool turn_off_simp) { - budgetOff(); - return solve_(do_simp, turn_off_simp); - } -inline lbool SimpSolver::solve (Lit p , bool do_simp, bool turn_off_simp) { - budgetOff(); - assumptions.push(p); - return solve_(do_simp, turn_off_simp); - } -inline lbool SimpSolver::solve (Lit p, Lit q, bool do_simp, bool turn_off_simp) { - budgetOff(); - assumptions.push(p); - assumptions.push(q); - return solve_(do_simp, turn_off_simp); - } -inline lbool SimpSolver::solve (Lit p, Lit q, Lit r, bool do_simp, bool turn_off_simp) { - budgetOff(); - assumptions.push(p); - assumptions.push(q); - assumptions.push(r); - return solve_(do_simp, turn_off_simp); - } -inline lbool SimpSolver::solve (const vec<Lit>& assumps, bool do_simp, bool turn_off_simp){ - budgetOff(); assumps.copyTo(assumptions); - return solve_(do_simp, turn_off_simp); -} - -inline lbool SimpSolver::solveLimited (const vec<Lit>& assumps, bool do_simp, bool turn_off_simp){ - assumps.copyTo(assumptions); return solve_(do_simp, turn_off_simp); } - -inline lbool SimpSolver::solveLimited (bool do_simp, bool turn_off_simp){ - return solve_(do_simp, turn_off_simp); } - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/utils/Options.cc b/src/prop/bvminisat/utils/Options.cc deleted file mode 100644 index 0b05d5cf6..000000000 --- a/src/prop/bvminisat/utils/Options.cc +++ /dev/null @@ -1,94 +0,0 @@ -/**************************************************************************************[Options.cc] -Copyright (c) 2008-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#include "prop/bvminisat/utils/Options.h" -#include "prop/bvminisat/mtl/Sort.h" -#include "prop/bvminisat/utils/ParseUtils.h" - -namespace cvc5 { -namespace BVMinisat { - -void BVMinisat::parseOptions(int& argc, char** argv, bool strict) -{ - int i, j; - for (i = j = 1; i < argc; i++){ - const char* str = argv[i]; - if (match(str, "--") && match(str, Option::getHelpPrefixString()) && match(str, "help")){ - if (*str == '\0') - printUsageAndExit(argc, argv); - else if (match(str, "-verb")) - printUsageAndExit(argc, argv, true); - } else { - bool parsed_ok = false; - - for (int k = 0; !parsed_ok && k < Option::getOptionList().size(); k++){ - parsed_ok = Option::getOptionList()[k]->parse(argv[i]); - - // fprintf(stderr, "checking %d: %s against flag <%s> (%s)\n", i, argv[i], Option::getOptionList()[k]->name, parsed_ok ? "ok" : "skip"); - } - - if (!parsed_ok) - if (strict && match(argv[i], "-")) - fprintf(stderr, "ERROR! Unknown flag \"%s\". Use '--%shelp' for help.\n", argv[i], Option::getHelpPrefixString()), exit(1); - else - argv[j++] = argv[i]; - } - } - - argc -= (i - j); -} - - -void BVMinisat::setUsageHelp (const char* str){ Option::getUsageString() = str; } -void BVMinisat::setHelpPrefixStr (const char* str){ Option::getHelpPrefixString() = str; } -void BVMinisat::printUsageAndExit (int argc, char** argv, bool verbose) -{ - const char* usage = Option::getUsageString(); - if (usage != NULL) - fprintf(stderr, usage, argv[0]); - - sort(Option::getOptionList(), Option::OptionLt()); - - const char* prev_cat = NULL; - const char* prev_type = NULL; - - for (int i = 0; i < Option::getOptionList().size(); i++){ - const char* cat = Option::getOptionList()[i]->category; - const char* type = Option::getOptionList()[i]->type_name; - - if (cat != prev_cat) - fprintf(stderr, "\n%s OPTIONS:\n\n", cat); - else if (type != prev_type) - fprintf(stderr, "\n"); - - Option::getOptionList()[i]->help(verbose); - - prev_cat = Option::getOptionList()[i]->category; - prev_type = Option::getOptionList()[i]->type_name; - } - - fprintf(stderr, "\nHELP OPTIONS:\n\n"); - fprintf(stderr, " --%shelp Print help message.\n", Option::getHelpPrefixString()); - fprintf(stderr, " --%shelp-verb Print verbose help message.\n", Option::getHelpPrefixString()); - fprintf(stderr, "\n"); - exit(0); -} - -} // namespace BVMinisat -} // namespace cvc5 diff --git a/src/prop/bvminisat/utils/Options.h b/src/prop/bvminisat/utils/Options.h deleted file mode 100644 index 033ffb64f..000000000 --- a/src/prop/bvminisat/utils/Options.h +++ /dev/null @@ -1,437 +0,0 @@ -/***************************************************************************************[Options.h] -Copyright (c) 2008-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_Options_h -#define BVMinisat_Options_h - -#include <stdlib.h> -#include <stdio.h> -#include <math.h> -#include <string.h> - -#include "prop/bvminisat/mtl/IntTypes.h" -#include "prop/bvminisat/mtl/Vec.h" -#include "prop/bvminisat/utils/ParseUtils.h" - -namespace cvc5 { -namespace BVMinisat { - -//================================================================================================== -// Top-level option parse/help functions: - - -extern void parseOptions (int& argc, char** argv, bool strict = false); -extern void printUsageAndExit(int argc, char** argv, bool verbose = false); -extern void setUsageHelp (const char* str); -extern void setHelpPrefixStr (const char* str); - - -//================================================================================================== -// Options is an abstract class that gives the interface for all types options: - - -class Option -{ - protected: - const char* name; - const char* description; - const char* category; - const char* type_name; - - static vec<Option*>& getOptionList () { static vec<Option*> options; return options; } - static const char*& getUsageString() { static const char* usage_str; return usage_str; } - static const char*& getHelpPrefixString() { static const char* help_prefix_str = ""; return help_prefix_str; } - - struct OptionLt { - bool operator()(const Option* x, const Option* y) { - int test1 = strcmp(x->category, y->category); - return test1 < 0 || (test1 == 0 && strcmp(x->type_name, y->type_name) < 0); - } - }; - - Option(const char* name_, - const char* desc_, - const char* cate_, - const char* type_) : - name (name_) - , description(desc_) - , category (cate_) - , type_name (type_) - { - getOptionList().push(this); - } - - public: - virtual ~Option() {} - - virtual bool parse (const char* str) = 0; - virtual void help (bool verbose = false) = 0; - - friend void parseOptions (int& argc, char** argv, bool strict); - friend void printUsageAndExit (int argc, char** argv, bool verbose); - friend void setUsageHelp (const char* str); - friend void setHelpPrefixStr (const char* str); -}; - - -//================================================================================================== -// Range classes with specialization for floating types: - - -struct IntRange { - int begin; - int end; - IntRange(int b, int e) : begin(b), end(e) {} -}; - -struct Int64Range { - int64_t begin; - int64_t end; - Int64Range(int64_t b, int64_t e) : begin(b), end(e) {} -}; - -struct DoubleRange { - double begin; - double end; - bool begin_inclusive; - bool end_inclusive; - DoubleRange(double b, bool binc, double e, bool einc) : begin(b), end(e), begin_inclusive(binc), end_inclusive(einc) {} -}; - - -//================================================================================================== -// Double options: - - -class DoubleOption : public Option -{ - protected: - DoubleRange range; - double value; - - public: - DoubleOption(const char* c, const char* n, const char* d, double def = double(), DoubleRange r = DoubleRange(-HUGE_VAL, false, HUGE_VAL, false)) - : Option(n, d, c, "<double>"), range(r), value(def) { - // FIXME: set LC_NUMERIC to "C" to make sure that strtof/strtod parses decimal point correctly. - } - - operator double (void) const { return value; } - operator double& (void) { return value; } - DoubleOption& operator=(double x) { value = x; return *this; } - - bool parse(const char* str) override - { - const char* span = str; - - if (!match(span, "-") || !match(span, name) || !match(span, "=")) - return false; - - char* end; - double tmp = strtod(span, &end); - - if (end == NULL) - return false; - else if (tmp >= range.end && (!range.end_inclusive || tmp != range.end)) - { - fprintf(stderr, - "ERROR! value <%s> is too large for option \"%s\".\n", - span, - name); - exit(1); - } - else if (tmp <= range.begin - && (!range.begin_inclusive || tmp != range.begin)) - { - fprintf(stderr, - "ERROR! value <%s> is too small for option \"%s\".\n", - span, - name); - exit(1); - } - - value = tmp; - // fprintf(stderr, "READ VALUE: %g\n", value); - - return true; - } - - void help(bool verbose = false) override - { - fprintf(stderr, - " -%-12s = %-8s %c%4.2g .. %4.2g%c (default: %g)\n", - name, - type_name, - range.begin_inclusive ? '[' : '(', - range.begin, - range.end, - range.end_inclusive ? ']' : ')', - value); - if (verbose) - { - fprintf(stderr, "\n %s\n", description); - fprintf(stderr, "\n"); - } - } -}; - - -//================================================================================================== -// Int options: - - -class IntOption : public Option -{ - protected: - IntRange range; - int32_t value; - - public: - IntOption(const char* c, const char* n, const char* d, int32_t def = int32_t(), IntRange r = IntRange(INT32_MIN, INT32_MAX)) - : Option(n, d, c, "<int32>"), range(r), value(def) {} - - operator int32_t (void) const { return value; } - operator int32_t& (void) { return value; } - IntOption& operator= (int32_t x) { value = x; return *this; } - - bool parse(const char* str) override - { - const char* span = str; - - if (!match(span, "-") || !match(span, name) || !match(span, "=")) - return false; - - char* end; - int32_t tmp = strtol(span, &end, 10); - - if (end == NULL) - return false; - else if (tmp > range.end) - { - fprintf(stderr, - "ERROR! value <%s> is too large for option \"%s\".\n", - span, - name); - exit(1); - } - else if (tmp < range.begin) - { - fprintf(stderr, - "ERROR! value <%s> is too small for option \"%s\".\n", - span, - name); - exit(1); - } - - value = tmp; - - return true; - } - - void help(bool verbose = false) override - { - fprintf(stderr, " -%-12s = %-8s [", name, type_name); - if (range.begin == INT32_MIN) - fprintf(stderr, "imin"); - else - fprintf(stderr, "%4d", range.begin); - - fprintf(stderr, " .. "); - if (range.end == INT32_MAX) - fprintf(stderr, "imax"); - else - fprintf(stderr, "%4d", range.end); - - fprintf(stderr, "] (default: %d)\n", value); - if (verbose) - { - fprintf(stderr, "\n %s\n", description); - fprintf(stderr, "\n"); - } - } -}; - - -// Leave this out for visual C++ until Microsoft implements C99 and gets support for strtoll. -#ifndef _MSC_VER - -class Int64Option : public Option -{ - protected: - Int64Range range; - int64_t value; - - public: - Int64Option(const char* c, const char* n, const char* d, int64_t def = int64_t(), Int64Range r = Int64Range(INT64_MIN, INT64_MAX)) - : Option(n, d, c, "<int64>"), range(r), value(def) {} - - operator int64_t (void) const { return value; } - operator int64_t& (void) { return value; } - Int64Option& operator= (int64_t x) { value = x; return *this; } - - bool parse(const char* str) override - { - const char* span = str; - - if (!match(span, "-") || !match(span, name) || !match(span, "=")) - return false; - - char* end; - int64_t tmp = strtoll(span, &end, 10); - - if (end == NULL) - return false; - else if (tmp > range.end) - { - fprintf(stderr, - "ERROR! value <%s> is too large for option \"%s\".\n", - span, - name); - exit(1); - } - else if (tmp < range.begin) - { - fprintf(stderr, - "ERROR! value <%s> is too small for option \"%s\".\n", - span, - name); - exit(1); - } - - value = tmp; - - return true; - } - - void help(bool verbose = false) override - { - fprintf(stderr, " -%-12s = %-8s [", name, type_name); - if (range.begin == INT64_MIN) - fprintf(stderr, "imin"); - else - fprintf(stderr, "%4" PRIi64, range.begin); - - fprintf(stderr, " .. "); - if (range.end == INT64_MAX) - fprintf(stderr, "imax"); - else - fprintf(stderr, "%4" PRIi64, range.end); - - fprintf(stderr, "] (default: %" PRIi64 ")\n", value); - if (verbose) - { - fprintf(stderr, "\n %s\n", description); - fprintf(stderr, "\n"); - } - } -}; -#endif - -//================================================================================================== -// String option: - - -class StringOption : public Option -{ - const char* value; - public: - StringOption(const char* c, const char* n, const char* d, const char* def = NULL) - : Option(n, d, c, "<string>"), value(def) {} - - operator const char* (void) const { return value; } - operator const char*& (void) { return value; } - StringOption& operator= (const char* x) { value = x; return *this; } - - bool parse(const char* str) override - { - const char* span = str; - - if (!match(span, "-") || !match(span, name) || !match(span, "=")) - return false; - - value = span; - return true; - } - - void help(bool verbose = false) override - { - fprintf(stderr, " -%-10s = %8s\n", name, type_name); - if (verbose) - { - fprintf(stderr, "\n %s\n", description); - fprintf(stderr, "\n"); - } - } -}; - - -//================================================================================================== -// Bool option: - - -class BoolOption : public Option -{ - bool value; - - public: - BoolOption(const char* c, const char* n, const char* d, bool v) - : Option(n, d, c, "<bool>"), value(v) {} - - operator bool (void) const { return value; } - operator bool& (void) { return value; } - BoolOption& operator=(bool b) { value = b; return *this; } - - bool parse(const char* str) override - { - const char* span = str; - - if (match(span, "-")) - { - bool b = !match(span, "no-"); - - if (strcmp(span, name) == 0) - { - value = b; - return true; - } - } - - return false; - } - - void help(bool verbose = false) override - { - fprintf(stderr, " -%s, -no-%s", name, name); - - for (uint32_t i = 0; i < 32 - strlen(name) * 2; i++) fprintf(stderr, " "); - - fprintf(stderr, " "); - fprintf(stderr, "(default: %s)\n", value ? "on" : "off"); - if (verbose) - { - fprintf(stderr, "\n %s\n", description); - fprintf(stderr, "\n"); - } - } -}; - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/utils/ParseUtils.h b/src/prop/bvminisat/utils/ParseUtils.h deleted file mode 100644 index d69856ebb..000000000 --- a/src/prop/bvminisat/utils/ParseUtils.h +++ /dev/null @@ -1,125 +0,0 @@ -/************************************************************************************[ParseUtils.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_ParseUtils_h -#define BVMinisat_ParseUtils_h - -#include <stdlib.h> -#include <stdio.h> - -//#include <zlib.h> -#include <unistd.h> - -namespace cvc5 { -namespace BVMinisat { - -//------------------------------------------------------------------------------------------------- -// A simple buffered character stream class: - -static const int buffer_size = 1048576; - - -class StreamBuffer { - int in; - unsigned char buf[buffer_size]; - int pos; - int size; - - void assureLookahead() { - if (pos >= size) { - pos = 0; - size = read(in, buf, sizeof(buf)); } } - -public: - explicit StreamBuffer(int i) : in(i), pos(0), size(0) { assureLookahead(); } - - int operator * () const { return (pos >= size) ? EOF : buf[pos]; } - void operator ++ () { pos++; assureLookahead(); } - int position () const { return pos; } -}; - - -//------------------------------------------------------------------------------------------------- -// End-of-file detection functions for StreamBuffer and char*: - - -static inline bool isEof(StreamBuffer& in) { return *in == EOF; } -static inline bool isEof(const char* in) { return *in == '\0'; } - -//------------------------------------------------------------------------------------------------- -// Generic parse functions parametrized over the input-stream type. - - -template<class B> -static void skipWhitespace(B& in) { - while ((*in >= 9 && *in <= 13) || *in == 32) - ++in; } - - -template<class B> -static void skipLine(B& in) { - for (;;){ - if (isEof(in)) return; - if (*in == '\n') { ++in; return; } - ++in; } } - - -template<class B> -static int parseInt(B& in) { - int val = 0; - bool neg = false; - skipWhitespace(in); - if (*in == '-') neg = true, ++in; - else if (*in == '+') ++in; - if (*in < '0' || *in > '9') fprintf(stderr, "PARSE ERROR! Unexpected char: %c\n", *in), exit(3); - while (*in >= '0' && *in <= '9') - val = val*10 + (*in - '0'), - ++in; - return neg ? -val : val; } - - -// String matching: in case of a match the input iterator will be advanced the corresponding -// number of characters. -template<class B> -static bool match(B& in, const char* str) { - int i; - for (i = 0; str[i] != '\0'; i++) - if (in[i] != str[i]) - return false; - - in += i; - - return true; -} - -// String matching: consumes characters eagerly, but does not require random access iterator. -template<class B> -static bool eagerMatch(B& in, const char* str) { - for (; *str != '\0'; ++str, ++in) - if (*str != *in) - return false; - return true; } - - -//================================================================================================= -} // namespace BVMinisat -} // namespace cvc5 - -#endif diff --git a/src/prop/bvminisat/utils/System.cc b/src/prop/bvminisat/utils/System.cc deleted file mode 100644 index d86678097..000000000 --- a/src/prop/bvminisat/utils/System.cc +++ /dev/null @@ -1,99 +0,0 @@ -/***************************************************************************************[System.cc] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#include "prop/bvminisat/utils/System.h" - -#if defined(__linux__) - -#include <stdio.h> -#include <stdlib.h> - -namespace cvc5 { -namespace BVMinisat { - -// TODO: split the memory reading functions into two: one for reading high-watermark of RSS, and -// one for reading the current virtual memory size. - -static inline int memReadStat(int field) -{ - char name[256]; - pid_t pid = getpid(); - int value; - - sprintf(name, "/proc/%d/statm", pid); - FILE* in = fopen(name, "rb"); - if (in == NULL) return 0; - - for (; field >= 0; field--) - if (fscanf(in, "%d", &value) != 1) - printf("ERROR! Failed to parse memory statistics from \"/proc\".\n"), exit(1); - fclose(in); - return value; -} - - -static inline int memReadPeak(void) -{ - char name[256]; - pid_t pid = getpid(); - - sprintf(name, "/proc/%d/status", pid); - FILE* in = fopen(name, "rb"); - if (in == NULL) return 0; - - // Find the correct line, beginning with "VmPeak:": - int peak_kb = 0; - while (!feof(in) && fscanf(in, "VmPeak: %d kB", &peak_kb) != 1) - while (!feof(in) && fgetc(in) != '\n') - ; - fclose(in); - - return peak_kb; -} - -double BVMinisat::memUsed() { return (double)memReadStat(0) * (double)getpagesize() / (1024*1024); } -double BVMinisat::memUsedPeak() { - double peak = memReadPeak() / 1024; - return peak == 0 ? memUsed() : peak; } - -#elif defined(__FreeBSD__) - -double BVMinisat::memUsed(void) { - struct rusage ru; - getrusage(RUSAGE_SELF, &ru); - return (double)ru.ru_maxrss / 1024; } -double MiniSat::memUsedPeak(void) { return memUsed(); } - - -#elif defined(__APPLE__) -#include <malloc/malloc.h> - -double BVMinisat::memUsed(void) { - malloc_statistics_t t; - malloc_zone_statistics(NULL, &t); - return (double)t.max_size_in_use / (1024*1024); } - -#else -double BVMinisat::memUsed() { - return 0; } -#endif - -} /* cvc5::BVMinisat namespace */ -} /* cvc5 namespace */ diff --git a/src/prop/bvminisat/utils/System.h b/src/prop/bvminisat/utils/System.h deleted file mode 100644 index c805c232a..000000000 --- a/src/prop/bvminisat/utils/System.h +++ /dev/null @@ -1,67 +0,0 @@ -/****************************************************************************************[System.h] -Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson -Copyright (c) 2007-2010, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#ifndef BVMinisat_System_h -#define BVMinisat_System_h - -#if defined(__linux__) -#include <fpu_control.h> -#endif - -#include "prop/bvminisat/mtl/IntTypes.h" - -//------------------------------------------------------------------------------------------------- - -namespace cvc5 { -namespace BVMinisat { - -static inline double cpuTime(void); // CPU-time in seconds. -extern double memUsed(); // Memory in mega bytes (returns 0 for unsupported architectures). -extern double memUsedPeak(); // Peak-memory in mega bytes (returns 0 for unsupported architectures). - -} // namespace BVMinisat -} // namespace cvc5 - -//------------------------------------------------------------------------------------------------- -// Implementation of inline functions: - -#if defined(_MSC_VER) || defined(__MINGW32__) -#include <time.h> - -static inline double cvc5::BVMinisat::cpuTime(void) -{ - return (double)clock() / CLOCKS_PER_SEC; -} - -#else -#include <sys/time.h> -#include <sys/resource.h> -#include <unistd.h> - -static inline double cvc5::BVMinisat::cpuTime(void) -{ - struct rusage ru; - getrusage(RUSAGE_SELF, &ru); - return (double)ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec / 1000000; -} - -#endif - -#endif |