Search Engine
[Validity Checker]

Collaboration diagram for Search Engine:

Modules

Classes

CNF Caches

These caches are for subexpressions of the translated formula phi, to avoid expanding phi into a tree. We cannot use d_cnfCache for that, since it is effectively non-backtracking, and we do not know if a subexpression of phi was translated at the current level, or at some other (inactive) branch of the decision tree.

Functions

Variables

Detailed Description

The search engine includes Boolean reasoning and coordinates with theory reasoning. It consists of a generic abstract API (class SearchEngine) and subclasses implementing concrete instances of search engines.

Function Documentation

SearchEngineRules * SearchEngine::createRules (  )  [protected, inherited]

Create the trusted component.

This function is defined in search_theorem_producer.cpp

Definition at line 41 of file search_theorem_producer.cpp.

References CVC3::SearchEngine::d_core, and CVC3::TheoryCore::getTM().

Referenced by CVC3::SearchEngine::SearchEngine().

SearchEngine::SearchEngine ( TheoryCore *  core  )  [inherited]

Constructor.

Definition at line 34 of file search.cpp.

References CVC3::SearchEngine::createRules(), and CVC3::SearchEngine::d_rules.

SearchEngine::~SearchEngine (  )  [virtual, inherited]

Destructor.

Definition at line 43 of file search.cpp.

References CVC3::SearchEngine::d_rules.

virtual const std::string& CVC3::SearchEngine::getName (  )  [pure virtual, inherited]

Name of this search engine.

Implemented in CVC3::SearchEngineFast, CVC3::SearchSat, and CVC3::SearchSimple.

Referenced by CVC3::VCL::reprocessFlags().

CommonProofRules* CVC3::SearchEngine::getCommonRules (  )  [inline, inherited]

Accessor for common rules.

Definition at line 81 of file search.h.

References CVC3::SearchEngine::d_commonRules.

Referenced by CVC3::VCL::deriveClosure(), and CVC3::VCL::query().

TheoryCore* CVC3::SearchEngine::theoryCore (  )  [inline, inherited]

Accessor for TheoryCore.

Definition at line 84 of file search.h.

References CVC3::SearchEngine::d_core.

Referenced by CVC3::SearchSat::addLemma(), CVC3::SearchSat::assertLit(), CVC3::CoreSatAPI_implBase::check(), CVC3::SearchImplBase::newIntAssumption(), CVC3::SearchSatTheoryAPI::outOfResources(), and CVC3::SearchSatCNFCallback::registerAtom().

virtual void CVC3::SearchEngine::registerAtom ( const Expr &  e  )  [pure virtual, inherited]

Register an atomic formula of interest.

Registered atoms are tracked by the decision procedures. If one of them is deduced to be true or false, it is added to a list of implied literals. Implied literals can be retrieved with the getImpliedLiteral function

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::registerAtom().

virtual Theorem CVC3::SearchEngine::getImpliedLiteral (  )  [pure virtual, inherited]

Return next literal implied by last assertion. Null Expr if none.

Returned literals are either registered atomic formulas or their negation

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::getImpliedLiteral().

virtual void CVC3::SearchEngine::push (  )  [pure virtual, inherited]

Push a checkpoint.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::checkTCC(), CVC3::SearchEngine::getConcreteModel(), and CVC3::VCL::push().

virtual void CVC3::SearchEngine::pop (  )  [pure virtual, inherited]

Restore last checkpoint.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::checkTCC(), CVC3::SearchEngine::getConcreteModel(), CVC3::VCL::pop(), and CVC3::VCL::popto().

virtual QueryResult CVC3::SearchEngine::checkValid ( const Expr &  e,
Theorem &  result 
) [pure virtual, inherited]

Checks the validity of a formula in the current context.

If the query is valid, it returns VALID, the result parameter contains the corresponding theorem, and the scope and context are the same as when called. If it returns INVALID, the context will be one which falsifies the query. If it returns UNKNOWN, the context will falsify the query, but the context may be inconsistent. Finally, if it returns ABORT, the context will be one which satisfies as much as possible.

Parameters:
e the formula to check.
result the resulting theorem, if the formula is valid.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::checkTCC(), CVC3::SearchEngine::getConcreteModel(), and CVC3::VCL::query().

virtual QueryResult CVC3::SearchEngine::restart ( const Expr &  e,
Theorem &  result 
) [pure virtual, inherited]

Reruns last check with e as an additional assumption.

This method should only be called after a query which is invalid.

Parameters:
e the additional assumption
result the resulting theorem, if the query is valid.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::checkContinue(), and CVC3::VCL::restart().

virtual void CVC3::SearchEngine::returnFromCheck (  )  [pure virtual, inherited]

Returns to context immediately before last call to checkValid.

This method should only be called after a query which returns something other than VALID.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::returnFromCheck().

virtual Theorem CVC3::SearchEngine::lastThm (  )  [pure virtual, inherited]

Returns the result of the most recent valid theorem.

Returns Null Theorem if last call was not valid

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::getAssumptionsUsed(), and CVC3::SearchEngine::getConcreteModel().

virtual Theorem CVC3::SearchEngine::newUserAssumption ( const Expr &  e  )  [pure virtual, inherited]

Generate and add an assumption to the set of assumptions in the current context.

By default, the assumption is added at the current scope. The default can be overridden by specifying the scope parameter.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::assertFormula().

virtual void CVC3::SearchEngine::getUserAssumptions ( std::vector< Expr > &  assumptions  )  [pure virtual, inherited]

Get all user assumptions made in this and all previous contexts.

User assumptions are created either by calls to newUserAssumption or a call to checkValid. In the latter case, the negated query is added as an assumption.

Parameters:
assumptions should be empty on entry.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::getUserAssumptions().

virtual void CVC3::SearchEngine::getInternalAssumptions ( std::vector< Expr > &  assumptions  )  [pure virtual, inherited]

Get assumptions made internally in this and all previous contexts.

Internal assumptions are literals assumed by the sat solver.

Parameters:
assumptions should be empty on entry.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::getInternalAssumptions().

virtual void CVC3::SearchEngine::getAssumptions ( std::vector< Expr > &  assumptions  )  [pure virtual, inherited]

Get all assumptions made in this and all previous contexts.

Parameters:
assumptions should be an empty vector which will be filled \ with the assumptions

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::getAssumptions(), and CVC3::SearchEngine::getConcreteModel().

virtual bool CVC3::SearchEngine::isAssumption ( const Expr &  e  )  [pure virtual, inherited]

Check if the formula has already been assumed previously.

Implemented in CVC3::SearchEngineFast, CVC3::SearchImplBase, and CVC3::SearchSat.

virtual void CVC3::SearchEngine::getCounterExample ( std::vector< Expr > &  assertions,
bool  inOrder = true 
) [pure virtual, inherited]

Will return the set of assertions which make the queried formula false.

This method should only be called after an query which returns INVALID. It will try to return the simplest possible set of assertions which are sufficient to make the queried expression false.

Parameters:
assertions should be empty on entry.
inOrder if true, returns the assertions in the order they were asserted. This is slightly more expensive than inOrder = false.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::checkContinue(), and CVC3::VCL::getCounterExample().

virtual Proof CVC3::SearchEngine::getProof (  )  [pure virtual, inherited]

Returns the proof term for the last proven query.

It should be called only after a query which returns VALID. In any other case, it returns Null.

Implemented in CVC3::SearchImplBase, and CVC3::SearchSat.

Referenced by CVC3::VCL::getProof().

void SearchEngine::getConcreteModel ( ExprMap< Expr > &  m  )  [inherited]

Build a concrete Model (assign values to variables), should only be called after a query which returns INVALID.

Definition at line 49 of file search.cpp.

References CVC3::TheoryCore::buildModel(), CVC3::SearchEngine::checkValid(), CVC3::TheoryCore::collectBasicVars(), CVC3::SearchEngine::d_core, CVC3::Theory::falseExpr(), CVC3::SearchEngine::getAssumptions(), CVC3::Theory::getEM(), CVC3::Theorem::getLeafAssumptions(), CVC3::TheoryCore::inconsistentThm(), CVC3::SearchEngine::lastThm(), CVC3::SearchEngine::pop(), CVC3::SearchEngine::push(), CVC3::RAW_LIST, CVC3::TheoryCore::refineCounterExample(), CVC3::Expr::toString(), CVC3::TRACE, and CVC3::VALID.

Referenced by CVC3::VCL::getConcreteModel().

Literal CVC3::SearchImplBase::newLiteral ( const Expr &  e  )  [inline, protected, inherited]

Construct a Literal out of an Expr or return an existing one.

Definition at line 119 of file search_impl_base.h.

References CVC3::SearchImplBase::d_vm.

Referenced by CVC3::SearchEngineFast::addLiteralFact(), CVC3::SearchEngineFast::addNonLiteralFact(), CVC3::SearchImplBase::addSplitter(), CVC3::SearchEngineFast::addSplitter(), CVC3::SearchEngineFast::newIntAssumption(), CVC3::Circuit::propagate(), CVC3::SearchEngineFast::recordFact(), CVC3::SearchEngineFast::split(), CVC3::SearchEngineFast::traceConflict(), and CVC3::SearchEngineFast::unitPropagation().

Theorem CVC3::SearchImplBase::simplify ( const Theorem &  e  )  [inline, protected, inherited]

Our version of simplifier: take Theorem(e), apply simplifier to get Theorem(e==e'), return Theorem(e').

Definition at line 123 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, CVC3::Theorem::getExpr(), CVC3::Theory::iffMP(), and CVC3::TheoryCore::simplify().

Referenced by CVC3::SearchEngineFast::bcp(), CVC3::SearchEngineFast::checkValidMain(), and CVC3::SearchSimple::checkValidRec().

virtual void CVC3::SearchImplBase::addLiteralFact ( const Theorem &  thm  )  [protected, pure virtual, inherited]

Notify the search engine about a new literal fact.

It should be called by SearchEngine::addFact() only. Must be implemented by the subclasses of SearchEngine.

IMPORTANT: do not call addFact() from this function; use enqueueFact() or setInconsistent() instead.

Implemented in CVC3::SearchEngineFast, and CVC3::SearchSimple.

Referenced by CVC3::SearchImplBase::addCNFFact(), and CVC3::DecisionEngine::pushDecision().

virtual void CVC3::SearchImplBase::addNonLiteralFact ( const Theorem &  thm  )  [protected, pure virtual, inherited]

Notify the search engine about a new non-literal fact.

It should be called by SearchEngine::addFact() only. Must be implemented by the subclasses of SearchEngine.

IMPORTANT: do not call addFact() from this function; use enqueueFact() or setInconsistent() instead.

Implemented in CVC3::SearchEngineFast, and CVC3::SearchSimple.

Referenced by CVC3::SearchImplBase::addCNFFact().

void SearchImplBase::addCNFFact ( const Theorem &  thm,
bool  fromCore = false 
) [protected, inherited]

Add a new fact to the search engine bypassing CNF converter.

Calls either addLiteralFact() or addNonLiteralFact() appropriately, and converts to CNF when d_cnfOption is set. If fromCore==true, this fact already comes from the core, and doesn't need to be reported back to the core.

Definition at line 216 of file search_impl_base.cpp.

References CVC3::SearchImplBase::addLiteralFact(), CVC3::SearchImplBase::addNonLiteralFact(), CVC3::SearchEngine::d_core, CVC3::TheoryCore::enqueueFact(), CVC3::Theorem::getExpr(), CVC3::Theorem::isAbsLiteral(), CVC3::TRACE, and TRACE_MSG.

Referenced by CVC3::SearchImplBase::addFact(), CVC3::SearchImplBase::applyCNFRules(), CVC3::SearchImplBase::enqueueCNF(), and CVC3::SearchImplBase::enqueueCNFrec().

int CVC3::SearchImplBase::getBottomScope (  )  [inline, inherited]

Definition at line 152 of file search_impl_base.h.

References CVC3::SearchImplBase::d_bottomScope.

bool SearchImplBase::isClause ( const Expr &  e  )  [inherited]

Check if e is a clause (a literal, or a disjunction of literals).

Definition at line 685 of file search_impl_base.cpp.

References CVC3::Expr::begin(), CVC3::Expr::end(), CVC3::Expr::isAbsLiteral(), and CVC3::Expr::isOr().

bool SearchImplBase::isPropClause ( const Expr &  e  )  [inherited]

Check if e is a propositional clause.

See also:
isPropAtom()

Definition at line 697 of file search_impl_base.cpp.

References CVC3::Expr::begin(), CVC3::Expr::end(), CVC3::Expr::isOr(), and CVC3::Expr::isPropLiteral().

bool CVC3::SearchImplBase::isCNFVar ( const Expr &  e  )  [inline, inherited]

Check whether e is a fresh variable introduced by the CNF converter.

Search engines do not need to split on those variables in order to be complete

Definition at line 164 of file search_impl_base.h.

References CVC3::SearchImplBase::d_cnfVars.

Referenced by CVC3::SearchImplBase::isGoodSplitter().

bool SearchImplBase::isGoodSplitter ( const Expr &  e  )  [inherited]

Check if a splitter is required for completeness.

Currently, it checks that 'e' is not an auxiliary CNF variable

Definition at line 709 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_ignoreCnfVarsOption, CVC3::SearchImplBase::isCNFVar(), CVC3::Expr::isNot(), and CVC3::TRACE.

Referenced by CVC3::SearchEngineFast::findSplitter(), and CVC3::DecisionEngine::findSplitterRec().

void SearchImplBase::enqueueCNF ( const Theorem &  theta  )  [private, inherited]

Translate theta to CNF and enqueue the new clauses.

Definition at line 358 of file search_impl_base.cpp.

References CVC3::SearchImplBase::addCNFFact(), CVC3::SearchImplBase::d_origFormulaOption, CVC3::SearchImplBase::enqueueCNFrec(), CVC3::TRACE, and TRACE_MSG.

Referenced by CVC3::SearchImplBase::addFact().

void SearchImplBase::enqueueCNFrec ( const Theorem &  theta  )  [private, inherited]

Recursive version of enqueueCNF().

Definition at line 369 of file search_impl_base.cpp.

References CVC3::SearchImplBase::addCNFFact(), CVC3::SearchImplBase::addToCNFCache(), CVC3::AND, CVC3::CommonProofRules::andElim(), CVC3::SearchImplBase::applyCNFRules(), CVC3::Expr::arity(), CVC3::SearchImplBase::d_cnfVars, CVC3::SearchEngine::d_commonRules, CVC3::SearchImplBase::d_enqueueCNFCache, CVC3::SearchImplBase::d_ifLiftOption, CVC3::SearchEngine::d_rules, DebugAssert, CVC3::SearchImplBase::findInCNFCache(), CVC3::Theorem::getExpr(), CVC3::Theorem::getLHS(), CVC3::Theorem::getRHS(), CVC3::Theorem::getScope(), CVC3::IFF, CVC3::CommonProofRules::iffMP(), CVC3::Expr::isAbsLiteral(), CVC3::Theorem::isAbsLiteral(), CVC3::Expr::isAnd(), CVC3::Theorem::isNull(), CVC3::Expr::isPropLiteral(), CVC3::Theorem::isRewrite(), CVC3::ITE, CVC3::SearchEngineRules::iteToClauses(), CVC3::CommonProofRules::notNotElim(), CVC3::OR, CVC3::SearchImplBase::replaceITE(), CVC3::SearchImplBase::scopeLevel(), CVC3::CommonProofRules::substitutivityRule(), CVC3::CommonProofRules::symmetryRule(), CVC3::Theorem::toString(), CVC3::Expr::toString(), CVC3::TRACE, TRACE_MSG, CVC3::CommonProofRules::transitivityRule(), and CVC3::CommonProofRules::varIntroSkolem().

Referenced by CVC3::SearchImplBase::enqueueCNF().

void SearchImplBase::applyCNFRules ( const Theorem &  thm  )  [private, inherited]

FIXME: write a comment.

Parameters:
thm is the input of the form phi <=> v

Definition at line 561 of file search_impl_base.cpp.

References CVC3::SearchImplBase::addCNFFact(), CVC3::SearchImplBase::addToCNFCache(), CVC3::AND, CVC3::SearchEngineRules::andCNFRule(), CVC3::CommonProofRules::andElim(), CVC3::Expr::arity(), CVC3::SearchImplBase::d_applyCNFRulesCache, CVC3::SearchEngine::d_commonRules, CVC3::SearchEngine::d_rules, DebugAssert, CVC3::SearchImplBase::findInCNFCache(), CVC3::Theorem::getExpr(), CVC3::Theorem::getLHS(), CVC3::IFF, CVC3::SearchEngineRules::iffCNFRule(), CVC3::CommonProofRules::iffContrapositive(), CVC3::SearchEngineRules::iffToClauses(), CVC3::SearchEngineRules::impCNFRule(), CVC3::IMPLIES, CVC3::Expr::isAbsLiteral(), CVC3::Expr::isAnd(), CVC3::Theorem::isNull(), CVC3::ITE, CVC3::SearchEngineRules::iteCNFRule(), CVC3::OR, CVC3::SearchEngineRules::orCNFRule(), CVC3::SearchImplBase::replaceITE(), CVC3::CommonProofRules::substitutivityRule(), CVC3::CommonProofRules::symmetryRule(), CVC3::Expr::toString(), CVC3::TRACE, TRACE_MSG, CVC3::CommonProofRules::transitivityRule(), and CVC3::CommonProofRules::varIntroSkolem().

Referenced by CVC3::SearchImplBase::enqueueCNFrec(), and CVC3::SearchImplBase::replaceITE().

void SearchImplBase::addToCNFCache ( const Theorem &  thm  )  [private, inherited]

Cache a theorem phi <=> v by phi, where v is a literal.

Definition at line 721 of file search_impl_base.cpp.

References CVC3::Statistics::counter(), CVC3::SearchImplBase::d_bottomScope, CVC3::SearchImplBase::d_cnfCache, CVC3::SearchImplBase::d_cnfVars, CVC3::SearchEngine::d_commonRules, CVC3::SearchEngine::d_core, DebugAssert, CVC3::Theorem::getExpr(), CVC3::Theorem::getLHS(), CVC3::Theorem::getRHS(), CVC3::TheoryCore::getStatistics(), CVC3::CommonProofRules::iffContrapositive(), CVC3::Expr::isNot(), CVC3::Theorem::isRewrite(), CVC3::Expr::toString(), and CVC3::TRACE.

Referenced by CVC3::SearchImplBase::applyCNFRules(), CVC3::SearchImplBase::enqueueCNFrec(), and CVC3::SearchImplBase::replaceITE().

Theorem SearchImplBase::findInCNFCache ( const Expr &  e  )  [private, inherited]

Find a theorem phi <=> v by phi, where v is a literal.

Returns:
Null Theorem if not found.

Definition at line 748 of file search_impl_base.cpp.

References CVC3::Statistics::counter(), CVC3::SearchImplBase::d_cnfCache, CVC3::SearchEngine::d_commonRules, CVC3::SearchEngine::d_core, DebugAssert, CVC3::Theorem::getExpr(), CVC3::Theorem::getLHS(), CVC3::TheoryCore::getStatistics(), CVC3::CommonProofRules::iffContrapositive(), CVC3::Expr::isNot(), CVC3::Theorem::isRewrite(), CVC3::CommonProofRules::rewriteNotNot(), CVC3::Expr::toString(), CVC3::TRACE, TRACE_MSG, and CVC3::CommonProofRules::transitivityRule().

Referenced by CVC3::SearchImplBase::applyCNFRules(), CVC3::SearchImplBase::enqueueCNFrec(), and CVC3::SearchImplBase::replaceITE().

Theorem SearchImplBase::replaceITE ( const Expr &  e  )  [private, inherited]

Replaces ITE subexpressions in e with variables.

Strategy:

For a given atomic formula phi(ite(c, t1, t2)) which depends on a term ITE, generate an equisatisfiable formula:

phi(x) & ite(c, t1=x, t2=x),

where x is a new variable.

The phi(x) part will be generated by the caller, and our job is to assert the 'ite(c, t1=x, t2=x)', and return a rewrite theorem phi(ite(c, t1, t2)) <=> phi(x).

Definition at line 802 of file search_impl_base.cpp.

References CVC3::SearchImplBase::addToCNFCache(), CVC3::SearchImplBase::applyCNFRules(), CVC3::SearchEngine::d_commonRules, CVC3::SearchEngine::d_core, CVC3::SearchImplBase::d_replaceITECache, CVC3::SearchImplBase::findInCNFCache(), CVC3::Theorem::getRHS(), CVC3::CommonProofRules::iffMP(), CVC3::Expr::isAbsLiteral(), CVC3::Expr::isPropLiteral(), CVC3::Theorem::isRewrite(), CVC3::CommonProofRules::reflexivityRule(), CVC3::TheoryCore::rewriteLiteral(), CVC3::TRACE, CVC3::CommonProofRules::transitivityRule(), and CVC3::CommonProofRules::varIntroSkolem().

Referenced by CVC3::SearchImplBase::applyCNFRules(), and CVC3::SearchImplBase::enqueueCNFrec().

int CVC3::SearchImplBase::scopeLevel (  )  [inline, protected, inherited]

Return the current scope level (for convenience).

Definition at line 191 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, CVC3::TheoryCore::getCM(), and CVC3::ContextManager::scopeLevel().

Referenced by CVC3::SearchEngineFast::addLiteralFact(), CVC3::SearchEngineFast::addNonLiteralFact(), CVC3::SearchEngineFast::bcp(), CVC3::SearchSimple::checkValidInternal(), CVC3::SearchEngineFast::checkValidInternal(), CVC3::SearchImplBase::enqueueCNFrec(), CVC3::SearchEngineFast::fixConflict(), CVC3::SearchEngineFast::newIntAssumption(), CVC3::SearchEngineFast::ConflictClauseManager::notify(), CVC3::SearchEngineFast::ConflictClauseManager::setRestorePoint(), and CVC3::SearchEngineFast::traceConflict().

SearchImplBase::SearchImplBase ( TheoryCore *  core  )  [inherited]

Constructor.

Definition at line 105 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_assumptions, CVC3::SearchImplBase::d_coreSatAPI_implBase, CVC3::SearchEngine::d_rules, CVC3::SearchImplBase::d_vm, CVC3::TheoryCore::getCM(), CVC3::TheoryCore::getFlags(), IF_DEBUG, and CVC3::TheoryCore::registerCoreSatAPI().

SearchImplBase::~SearchImplBase (  )  [virtual, inherited]

Destructor.

Definition at line 130 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_coreSatAPI_implBase, and CVC3::SearchImplBase::d_vm.

virtual void CVC3::SearchImplBase::registerAtom ( const Expr &  e  )  [inline, virtual, inherited]

Register an atomic formula of interest.

Registered atoms are tracked by the decision procedures. If one of them is deduced to be true or false, it is added to a list of implied literals. Implied literals can be retrieved with the getImpliedLiteral function

Implements CVC3::SearchEngine.

Definition at line 199 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, and CVC3::TheoryCore::registerAtom().

virtual Theorem CVC3::SearchImplBase::getImpliedLiteral (  )  [inline, virtual, inherited]

Return next literal implied by last assertion. Null Expr if none.

Returned literals are either registered atomic formulas or their negation

Implements CVC3::SearchEngine.

Definition at line 201 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, and CVC3::TheoryCore::getImpliedLiteral().

virtual void CVC3::SearchImplBase::push (  )  [inline, virtual, inherited]

Push a checkpoint.

Implements CVC3::SearchEngine.

Definition at line 202 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, CVC3::TheoryCore::getCM(), and CVC3::ContextManager::push().

virtual void CVC3::SearchImplBase::pop (  )  [inline, virtual, inherited]

Restore last checkpoint.

Implements CVC3::SearchEngine.

Definition at line 203 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, CVC3::TheoryCore::getCM(), and CVC3::ContextManager::pop().

virtual QueryResult CVC3::SearchImplBase::checkValidInternal ( const Expr &  e  )  [pure virtual, inherited]

Checks the validity of a formula in the current context.

The method that actually calls the SAT solver (implemented in a subclass). It should maintain d_assumptions (add all asserted splitters to it), and set d_lastValid and d_lastCounterExample appropriately before exiting.

Implemented in CVC3::SearchEngineFast, and CVC3::SearchSimple.

Referenced by CVC3::SearchImplBase::checkValid().

QueryResult SearchImplBase::checkValid ( const Expr &  e,
Theorem &  result 
) [virtual, inherited]

Similar to checkValidInternal(), only returns Theorem(e) or Null.

Implements CVC3::SearchEngine.

Definition at line 342 of file search_impl_base.cpp.

References CVC3::SearchImplBase::checkValidInternal(), CVC3::CommonProofRules::clearSkolemAxioms(), CVC3::SearchEngine::d_commonRules, and CVC3::SearchImplBase::d_lastValid.

Referenced by CVC3::CoreSatAPI_implBase::check().

virtual QueryResult CVC3::SearchImplBase::restartInternal ( const Expr &  e  )  [pure virtual, inherited]

Reruns last check with e as an additional assumption.

Implemented in CVC3::SearchEngineFast, and CVC3::SearchSimple.

Referenced by CVC3::SearchImplBase::restart().

QueryResult SearchImplBase::restart ( const Expr &  e,
Theorem &  result 
) [virtual, inherited]

Reruns last check with e as an additional assumption.

Implements CVC3::SearchEngine.

Definition at line 350 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_lastValid, and CVC3::SearchImplBase::restartInternal().

Referenced by CVC3::SearchImplBase::returnFromCheck().

void CVC3::SearchImplBase::returnFromCheck (  )  [inline, virtual, inherited]

Returns to context immediately before last call to checkValid.

This method should only be called after a query which returns something other than VALID.

Implements CVC3::SearchEngine.

Definition at line 221 of file search_impl_base.h.

References CVC3::SearchEngine::d_core, CVC3::Theory::falseExpr(), and CVC3::SearchImplBase::restart().

virtual Theorem CVC3::SearchImplBase::lastThm (  )  [inline, virtual, inherited]

Returns the result of the most recent valid theorem.

Returns Null Theorem if last call was not valid

Implements CVC3::SearchEngine.

Definition at line 223 of file search_impl_base.h.

References CVC3::SearchImplBase::d_lastValid.

Theorem SearchImplBase::newUserAssumption ( const Expr &  e  )  [virtual, inherited]

Generate and add a new assertion to the set of assertions in the current context. This should only be used by class VCL in assertFormula().

Implements CVC3::SearchEngine.

Definition at line 139 of file search_impl_base.cpp.

References CVC3::TheoryCore::addFact(), CVC3::CommonProofRules::assumpRule(), CVC3::SearchImplBase::d_assumptions, CVC3::SearchEngine::d_commonRules, CVC3::SearchEngine::d_core, CVC3::debugger, std::endl(), CVC3::TheoryCore::getExprTrans(), CVC3::Debug::getOS(), IF_DEBUG, CVC3::Theorem::isNull(), CVC3::ExprTransform::preprocess(), CVC3::Expr::setUserAssumption(), CVC3::TRACE, and CVC3::Debug::trace().

Referenced by CVC3::SearchSimple::checkValidInternal(), CVC3::SearchEngineFast::checkValidInternal(), CVC3::SearchSimple::restartInternal(), and CVC3::SearchEngineFast::restartInternal().

Theorem SearchImplBase::newIntAssumption ( const Expr &  e  )  [virtual, inherited]

Add a new internal asserion.

Reimplemented in CVC3::SearchEngineFast.

Definition at line 168 of file search_impl_base.cpp.

References CVC3::CommonProofRules::assumpRule(), CVC3::SearchEngine::d_commonRules, CVC3::Expr::isNot(), CVC3::Theorem::setQuantLevel(), and CVC3::SearchEngine::theoryCore().

Referenced by CVC3::CoreSatAPI_implBase::addAssumption(), CVC3::SearchEngineFast::newIntAssumption(), and CVC3::DecisionEngine::pushDecision().

void SearchImplBase::newIntAssumption ( const Theorem &  thm  )  [inherited]

Helper for above function.

Definition at line 177 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_assumptions, DebugAssert, CVC3::Theorem::getExpr(), CVC3::Expr::setIntAssumption(), CVC3::Expr::toString(), and CVC3::TRACE.

void SearchImplBase::getUserAssumptions ( std::vector< Expr > &  assumptions  )  [virtual, inherited]

Get all assumptions made in this and all previous contexts.

Parameters:
assumptions should be an empty vector which will be filled \ with the assumptions

Implements CVC3::SearchEngine.

Definition at line 187 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_assumptions.

void SearchImplBase::getInternalAssumptions ( std::vector< Expr > &  assumptions  )  [virtual, inherited]

Get assumptions made internally in this and all previous contexts.

Internal assumptions are literals assumed by the sat solver.

Parameters:
assumptions should be empty on entry.

Implements CVC3::SearchEngine.

Definition at line 195 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_assumptions.

Referenced by CVC3::SearchImplBase::getCounterExample().

void SearchImplBase::getAssumptions ( std::vector< Expr > &  assumptions  )  [virtual, inherited]

Get all assumptions made in this and all previous contexts.

Parameters:
assumptions should be an empty vector which will be filled \ with the assumptions

Implements CVC3::SearchEngine.

Definition at line 203 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_assumptions.

Referenced by CVC3::SearchEngineFast::getCounterExample().

bool SearchImplBase::isAssumption ( const Expr &  e  )  [virtual, inherited]

Check if the formula has been assumed.

Implements CVC3::SearchEngine.

Reimplemented in CVC3::SearchEngineFast.

Definition at line 211 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_assumptions.

Referenced by CVC3::SearchEngineFast::isAssumption().

void SearchImplBase::addFact ( const Theorem &  thm  )  [inherited]

Add a new fact to the search engine from the core.

It should be called by TheoryCore::assertFactCore().

Definition at line 229 of file search_impl_base.cpp.

References CVC3::SearchImplBase::addCNFFact(), CVC3::SearchImplBase::d_cnfOption, CVC3::SearchImplBase::enqueueCNF(), CVC3::Theorem::getExpr(), CVC3::TRACE, and TRACE_MSG.

Referenced by CVC3::CoreSatAPI_implBase::addLemma().

void SearchImplBase::addSplitter ( const Expr &  e,
int  priority 
) [virtual, inherited]

Suggest a splitter to the SearchEngine.

The higher is the priority, the sooner the SAT solver will split on it. It can be positive or negative (default is 0).

The set of suggested splitters is backtracking; that is, a splitter is "forgotten" once the scope is backtracked.

This method can be used either to change the priority of existing splitters, or to introduce new splitters that DPs consider relevant, even though they do not appear in existing formulas.

Reimplemented in CVC3::SearchEngineFast.

Definition at line 239 of file search_impl_base.cpp.

References CVC3::SearchImplBase::d_dpSplitters, DebugAssert, CVC3::Expr::isAbsLiteral(), CVC3::SearchImplBase::newLiteral(), and CVC3::Expr::toString().

Referenced by CVC3::CoreSatAPI_implBase::addSplitter().

void SearchImplBase::getCounterExample ( std::vector< Expr > &  assertions,
bool  inOrder = true 
) [virtual, inherited]

Will return the set of assertions which make the queried formula false.

This method should only be called after an query which returns INVALID. It will try to return the simplest possible set of assertions which are sufficient to make the queried expression false.

Parameters:
assertions should be empty on entry.
inOrder if true, returns the assertions in the order they were asserted. This is slightly more expensive than inOrder = false.

Implements CVC3::SearchEngine.

Definition at line 245 of file search_impl_base.cpp.

References CVC3::SearchEngine::d_core, CVC3::SearchImplBase::d_lastValid, CVC3::SearchImplBase::getInternalAssumptions(), CVC3::TheoryCore::getTM(), CVC3::Theorem::isNull(), and CVC3::TheoremManager::withAssumptions().

Referenced by CVC3::SearchEngineFast::getCounterExample().

Proof SearchImplBase::getProof (  )  [virtual, inherited]

Returns the proof term for the last proven query.

It should be called only after a checkValid which returns true. In any other case, it returns Null.

Implements CVC3::SearchEngine.

Definition at line 280 of file search_impl_base.cpp.

References CVC3::SearchEngine::d_core, CVC3::SearchImplBase::d_lastValid, CVC3::Theorem::getProof(), CVC3::TheoryCore::getTM(), CVC3::Theorem::isNull(), and CVC3::TheoremManager::withProof().

const Assumptions & SearchImplBase::getAssumptionsUsed (  )  [virtual, inherited]

Returns the set of assumptions used in the proof. It should be a subset of getAssumptions().

It should be called only after a checkValid which returns true. In any other case, it returns Null.

Definition at line 295 of file search_impl_base.cpp.

References CVC3::SearchEngine::d_core, CVC3::SearchImplBase::d_lastValid, CVC3::Assumptions::emptyAssump(), CVC3::Theorem::getAssumptionsRef(), CVC3::TheoryCore::getTM(), CVC3::Theorem::isNull(), and CVC3::TheoremManager::withAssumptions().

void SearchImplBase::processResult ( const Theorem &  res,
const Expr &  e 
) [inherited]

Process result of checkValid.

Given a proof of FALSE ('res') from an assumption 'e', derive the proof of the inverse of e.

Parameters:
res is a proof of FALSE
e is the assumption used in the above proof

Definition at line 315 of file search_impl_base.cpp.

References CVC3::ExprHashMap< Data >::clear(), CVC3::SearchEngine::d_commonRules, CVC3::SearchImplBase::d_lastCounterExample, CVC3::SearchImplBase::d_lastValid, CVC3::SearchEngine::d_rules, DebugAssert, CVC3::SearchEngineRules::eliminateSkolemAxioms(), CVC3::ExprHashMap< Data >::erase(), CVC3::Theorem::getExpr(), CVC3::CommonProofRules::getSkolemAxioms(), CVC3::Expr::isFalse(), CVC3::Expr::isNot(), CVC3::Theorem::isNull(), CVC3::SearchEngineRules::negIntro(), CVC3::SearchEngineRules::proofByContradiction(), and CVC3::Theorem::toString().

Referenced by CVC3::SearchSimple::checkValidMain(), and CVC3::SearchEngineFast::checkValidMain().

Variable Documentation

TheoryCore* CVC3::SearchEngine::d_core [protected, inherited]

Access to theory reasoning.

Definition at line 57 of file search.h.

Referenced by CVC3::SearchImplBase::addCNFFact(), CVC3::SearchEngineFast::addNonLiteralFact(), CVC3::SearchImplBase::addToCNFCache(), CVC3::SearchEngineFast::analyzeUIPs(), CVC3::SearchSat::assertLit(), CVC3::SearchEngineFast::bcp(), CVC3::SearchSat::check(), CVC3::SearchSat::checkConsistent(), CVC3::SearchEngineFast::checkSAT(), CVC3::SearchSimple::checkValidInternal(), CVC3::SearchEngineFast::checkValidInternal(), CVC3::SearchSimple::checkValidMain(), CVC3::SearchEngineFast::checkValidMain(), CVC3::SearchSimple::checkValidRec(), CVC3::SearchEngineFast::commitFacts(), CVC3::SearchEngine::createRules(), CVC3::SearchImplBase::findInCNFCache(), CVC3::SearchEngineFast::findSplitter(), CVC3::SearchImplBase::getAssumptionsUsed(), CVC3::SearchEngine::getConcreteModel(), CVC3::SearchImplBase::getCounterExample(), CVC3::SearchSat::getImplication(), CVC3::SearchSat::getImpliedLiteral(), CVC3::SearchImplBase::getImpliedLiteral(), CVC3::SearchSat::getProof(), CVC3::SearchImplBase::getProof(), CVC3::SearchImplBase::newUserAssumption(), CVC3::SearchSat::newUserAssumptionInt(), CVC3::SearchImplBase::pop(), CVC3::Circuit::propagate(), CVC3::SearchImplBase::push(), CVC3::SearchSat::recordNewRootLit(), CVC3::SearchSat::registerAtom(), CVC3::SearchImplBase::registerAtom(), CVC3::SearchImplBase::replaceITE(), CVC3::SearchSimple::restartInternal(), CVC3::SearchEngineFast::restartInternal(), CVC3::SearchSat::restorePre(), CVC3::SearchImplBase::returnFromCheck(), CVC3::SearchImplBase::scopeLevel(), CVC3::SearchEngineFast::setInconsistent(), CVC3::SearchImplBase::simplify(), CVC3::SearchEngineFast::split(), and CVC3::SearchEngine::theoryCore().

CommonProofRules* CVC3::SearchEngine::d_commonRules [protected, inherited]

Common proof rules.

Definition at line 60 of file search.h.

Referenced by CVC3::SearchEngineFast::addLiteralFact(), CVC3::SearchSimple::addNonLiteralFact(), CVC3::SearchEngineFast::addNonLiteralFact(), CVC3::SearchSat::addSplitter(), CVC3::SearchImplBase::addToCNFCache(), CVC3::SearchImplBase::applyCNFRules(), CVC3::SearchSat::assertLit(), CVC3::SearchEngineFast::bcp(), CVC3::SearchSat::check(), CVC3::SearchImplBase::checkValid(), CVC3::SearchSimple::checkValidMain(), CVC3::SearchEngineFast::checkValidMain(), CVC3::SearchSimple::checkValidRec(), CVC3::SearchImplBase::enqueueCNFrec(), CVC3::SearchImplBase::findInCNFCache(), CVC3::SearchEngineFast::fixConflict(), CVC3::SearchEngine::getCommonRules(), CVC3::SearchImplBase::newIntAssumption(), CVC3::SearchImplBase::newUserAssumption(), CVC3::SearchSat::newUserAssumptionInt(), CVC3::SearchImplBase::processResult(), CVC3::SearchEngineFast::recordFact(), CVC3::SearchImplBase::replaceITE(), CVC3::SearchSimple::SearchSimple(), and CVC3::SearchEngineFast::split().

SearchEngineRules* CVC3::SearchEngine::d_rules [protected, inherited]

Proof rules for the search engine.

Definition at line 63 of file search.h.

Referenced by CVC3::SearchEngineFast::addNonLiteralFact(), CVC3::SearchEngineFast::analyzeUIPs(), CVC3::SearchImplBase::applyCNFRules(), CVC3::SearchSat::check(), CVC3::SearchSimple::checkValidRec(), CVC3::SearchImplBase::enqueueCNFrec(), CVC3::SearchImplBase::processResult(), CVC3::SearchEngineFast::propagate(), CVC3::Circuit::propagate(), CVC3::SearchEngine::SearchEngine(), CVC3::SearchImplBase::SearchImplBase(), CVC3::SearchEngineFast::unitPropagation(), and CVC3::SearchEngine::~SearchEngine().

VariableManager* CVC3::SearchImplBase::d_vm [protected, inherited]

Variable manager for classes Variable and Literal.

Definition at line 43 of file search_impl_base.h.

Referenced by CVC3::SearchEngineFast::addNonLiteralFact(), CVC3::SearchEngineFast::analyzeUIPs(), CVC3::Circuit::Circuit(), CVC3::SearchImplBase::newLiteral(), CVC3::SearchImplBase::SearchImplBase(), and CVC3::SearchImplBase::~SearchImplBase().

CDO<int> CVC3::SearchImplBase::d_bottomScope [protected, inherited]

The bottom-most scope for the current call to checkSAT (where conflict clauses are still valid).

Definition at line 48 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::addToCNFCache(), CVC3::SearchEngineFast::analyzeUIPs(), CVC3::SearchSimple::checkValidInternal(), CVC3::SearchEngineFast::checkValidInternal(), CVC3::SearchEngineFast::checkValidMain(), CVC3::SearchEngineFast::fixConflict(), CVC3::SearchImplBase::getBottomScope(), CVC3::SearchSimple::restartInternal(), CVC3::SearchEngineFast::restartInternal(), and CVC3::SearchEngineFast::traceConflict().

TheoryCore::CoreSatAPI* CVC3::SearchImplBase::d_coreSatAPI_implBase [protected, inherited]

Definition at line 50 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::SearchImplBase(), and CVC3::SearchImplBase::~SearchImplBase().

CDList<Splitter> CVC3::SearchImplBase::d_dpSplitters [protected, inherited]

Backtracking ordered set of DP-suggested splitters.

Definition at line 73 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::addSplitter(), and CVC3::SearchEngineFast::addSplitter().

Theorem CVC3::SearchImplBase::d_lastValid [protected, inherited]

Theorem from the last successful checkValid call. It is used by getProof and getAssumptions.

Definition at line 77 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::checkValid(), CVC3::SearchSimple::checkValidMain(), CVC3::SearchEngineFast::checkValidMain(), CVC3::SearchImplBase::getAssumptionsUsed(), CVC3::SearchImplBase::getCounterExample(), CVC3::SearchImplBase::getProof(), CVC3::SearchImplBase::lastThm(), CVC3::SearchImplBase::processResult(), and CVC3::SearchImplBase::restart().

ExprHashMap<bool> CVC3::SearchImplBase::d_lastCounterExample [protected, inherited]

Assumptions from the last unsuccessful checkValid call. These are used by getCounterExample.

Definition at line 80 of file search_impl_base.h.

Referenced by CVC3::SearchSimple::checkValidMain(), CVC3::SearchEngineFast::checkValidMain(), and CVC3::SearchImplBase::processResult().

CDMap<Expr,Theorem> CVC3::SearchImplBase::d_assumptions [protected, inherited]

Maintain the list of current assumptions (user asserts and splitters) for getAssumptions().

Definition at line 83 of file search_impl_base.h.

Referenced by CVC3::SearchSimple::checkValidInternal(), CVC3::SearchEngineFast::checkValidInternal(), CVC3::SearchEngineFast::checkValidMain(), CVC3::SearchImplBase::getAssumptions(), CVC3::SearchImplBase::getInternalAssumptions(), CVC3::SearchImplBase::getUserAssumptions(), CVC3::SearchImplBase::isAssumption(), CVC3::SearchImplBase::newIntAssumption(), CVC3::SearchImplBase::newUserAssumption(), CVC3::SearchSimple::restartInternal(), CVC3::SearchEngineFast::restartInternal(), and CVC3::SearchImplBase::SearchImplBase().

CDMap<Expr, Theorem> CVC3::SearchImplBase::d_cnfCache [protected, inherited]

Backtracking cache for the CNF generator.

Definition at line 86 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::addToCNFCache(), and CVC3::SearchImplBase::findInCNFCache().

CDMap<Expr, bool> CVC3::SearchImplBase::d_cnfVars [protected, inherited]

Backtracking set of new variables generated by CNF translator.

Specific search engines do not have to split on these variables

Definition at line 89 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::addToCNFCache(), CVC3::SearchImplBase::enqueueCNFrec(), and CVC3::SearchImplBase::isCNFVar().

const bool* CVC3::SearchImplBase::d_cnfOption [protected, inherited]

Command line flag whether to convert to CNF.

Definition at line 91 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::addFact().

const bool* CVC3::SearchImplBase::d_ifLiftOption [protected, inherited]

Flag: whether to convert term ITEs into CNF.

Definition at line 93 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::enqueueCNFrec().

const bool* CVC3::SearchImplBase::d_ignoreCnfVarsOption [protected, inherited]

Flag: ignore auxiliary CNF variables when searching for a splitter.

Definition at line 95 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::isGoodSplitter().

const bool* CVC3::SearchImplBase::d_origFormulaOption [protected, inherited]

Flag: Preserve the original formula with +cnf (for splitter heuristics).

Definition at line 97 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::enqueueCNF().

CDMap<Expr,bool> CVC3::SearchImplBase::d_enqueueCNFCache [protected, inherited]

Cache for enqueueCNF().

Definition at line 111 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::enqueueCNFrec().

CDMap<Expr,bool> CVC3::SearchImplBase::d_applyCNFRulesCache [protected, inherited]

Cache for applyCNFRules().

Definition at line 113 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::applyCNFRules().

CDMap<Expr,Theorem> CVC3::SearchImplBase::d_replaceITECache [protected, inherited]

Cache for replaceITE().

Definition at line 115 of file search_impl_base.h.

Referenced by CVC3::SearchImplBase::replaceITE().

Generated on Tue Jul 3 14:35:22 2007 for CVC3 by  doxygen 1.5.1