1 /********************* */
4 ** Top contributors (to current version):
5 ** Dejan Jovanovic, Morgan Deters, Tim King
6 ** This file is part of the CVC4 project.
7 ** Copyright (c) 2009-2016 by the authors listed in the file AUTHORS
8 ** in the top-level source directory) and their institutional affiliations.
9 ** All rights reserved. See the file COPYING in the top-level source
10 ** directory for licensing information.\endverbatim
12 ** \brief Base of the theory interface.
14 ** Base of the theory interface.
17 #include "cvc4_private.h"
19 #ifndef __CVC4__THEORY__THEORY_H
20 #define __CVC4__THEORY__THEORY_H
22 #include <ext/hash_set>
28 #include "context/cdlist.h"
29 #include "context/cdhashset.h"
30 #include "context/cdo.h"
31 #include "context/context.h"
32 #include "expr/node.h"
34 #include "options/options.h"
35 #include "options/theory_options.h"
36 #include "options/theoryof_mode.h"
37 #include "smt/command.h"
39 #include "smt/logic_request.h"
40 #include "theory/assertion.h"
41 #include "theory/care_graph.h"
42 #include "theory/logic_info.h"
43 #include "theory/output_channel.h"
44 #include "theory/valuation.h"
45 #include "util/statistics_registry.h"
53 class QuantifiersEngine
;
55 class SubstitutionMap
;
58 class EntailmentCheckParameters
;
59 class EntailmentCheckSideEffects
;
62 class CandidateGenerator
;
63 }/* CVC4::theory::rrinst namespace */
67 }/* CVC4::theory::eq namespace */
70 * Base class for T-solvers. Abstract DPLL(T).
72 * This is essentially an interface class. The TheoryEngine has
73 * pointers to Theory. Note that only one specific Theory type (e.g.,
74 * TheoryUF) can exist per NodeManager, because of how the
75 * RegisteredAttr works. (If you need multiple instances of the same
76 * theory, you'll have to write a multiplexed theory that dispatches
83 friend class ::CVC4::TheoryEngine
;
85 // Disallow default construction, copy, assignment.
86 Theory() CVC4_UNDEFINED
;
87 Theory(const Theory
&) CVC4_UNDEFINED
;
88 Theory
& operator=(const Theory
&) CVC4_UNDEFINED
;
90 /** An integer identifying the type of the theory. */
93 /** Name of this theory instance. Along with the TheoryId this should provide
94 * an unique string identifier for each instance of a Theory class. We need
95 * this to ensure unique statistics names over multiple theory instances. */
96 std::string d_instanceName
;
98 /** The SAT search context for the Theory. */
99 context::Context
* d_satContext
;
101 /** The user level assertion context for the Theory. */
102 context::UserContext
* d_userContext
;
104 /** Information about the logic we're operating within. */
105 const LogicInfo
& d_logicInfo
;
108 * The assertFact() queue.
110 * These can not be TNodes as some atoms (such as equalities) are sent
111 * across theories without being stored in a global map.
113 context::CDList
<Assertion
> d_facts
;
115 /** Index into the head of the facts list */
116 context::CDO
<unsigned> d_factsHead
;
118 /** Add shared term to the theory. */
119 void addSharedTermInternal(TNode node
);
121 /** Indices for splitting on the shared terms. */
122 context::CDO
<unsigned> d_sharedTermsIndex
;
124 /** The care graph the theory will use during combination. */
125 CareGraph
* d_careGraph
;
128 * Pointer to the quantifiers engine (or NULL, if quantifiers are not
129 * supported or not enabled). Not owned by the theory.
131 QuantifiersEngine
* d_quantEngine
;
133 /** Extended theory module or NULL. Owned by the theory. */
134 ExtTheory
* d_extTheory
;
139 // === STATISTICS ===
140 /** time spent in check calls */
141 TimerStat d_checkTime
;
142 /** time spent in theory combination */
143 TimerStat d_computeCareGraphTime
;
146 * The only method to add suff to the care graph.
148 void addCarePair(TNode t1
, TNode t2
);
151 * The function should compute the care graph over the shared terms.
152 * The default function returns all the pairs among the shared variables.
154 virtual void computeCareGraph();
157 * A list of shared terms that the theory has.
159 context::CDList
<TNode
> d_sharedTerms
;
162 * Helper function for computeRelevantTerms
164 void collectTerms(TNode n
, std::set
<Node
>& termSet
) const;
167 * Scans the current set of assertions and shared terms top-down
168 * until a theory-leaf is reached, and adds all terms found to
169 * termSet. This is used by collectModelInfo to delimit the set of
170 * terms that should be used when constructing a model
172 void computeRelevantTerms(std::set
<Node
>& termSet
, bool includeShared
= true) const;
175 * Construct a Theory.
177 * The pair <id, instance> is assumed to uniquely identify this Theory
178 * w.r.t. the SmtEngine.
180 Theory(TheoryId id
, context::Context
* satContext
,
181 context::UserContext
* userContext
, OutputChannel
& out
,
182 Valuation valuation
, const LogicInfo
& logicInfo
,
183 std::string instance
= "") throw(); // taking : No default.
186 * This is called at shutdown time by the TheoryEngine, just before
187 * destruction. It is important because there are destruction
188 * ordering issues between PropEngine and Theory (based on what
189 * hard-links to Nodes are outstanding). As the fact queue might be
190 * nonempty, we ensure here that it's clear. If you overload this,
191 * you must make an explicit call here to this->Theory::shutdown()
194 virtual void shutdown() { }
197 * The output channel for the Theory.
199 OutputChannel
* d_out
;
202 * The valuation proxy for the Theory to communicate back with the
203 * theory engine (and other theories).
205 Valuation d_valuation
;
208 * Whether proofs are enabled
211 bool d_proofsEnabled
;
214 * Returns the next assertion in the assertFact() queue.
216 * @return the next assertion in the assertFact() queue
218 inline Assertion
get();
220 const LogicInfo
& getLogicInfo() const {
225 * The theory that owns the uninterpreted sort.
227 static TheoryId s_uninterpretedSortOwner
;
229 void printFacts(std::ostream
& os
) const;
230 void debugPrintFacts() const;
233 * Whether proofs are enabled
241 * Return the ID of the theory responsible for the given type.
243 static inline TheoryId
theoryOf(TypeNode typeNode
) {
244 Trace("theory::internal") << "theoryOf(" << typeNode
<< ")" << std::endl
;
246 while (typeNode
.isPredicateSubtype()) {
247 typeNode
= typeNode
.getSubtypeParentType();
249 if (typeNode
.getKind() == kind::TYPE_CONSTANT
) {
250 id
= typeConstantToTheoryId(typeNode
.getConst
<TypeConstant
>());
252 id
= kindToTheoryId(typeNode
.getKind());
254 if (id
== THEORY_BUILTIN
) {
255 Trace("theory::internal") << "theoryOf(" << typeNode
<< ") == " << s_uninterpretedSortOwner
<< std::endl
;
256 return s_uninterpretedSortOwner
;
262 * Returns the ID of the theory responsible for the given node.
264 static TheoryId
theoryOf(TheoryOfMode mode
, TNode node
);
267 * Returns the ID of the theory responsible for the given node.
269 static inline TheoryId
theoryOf(TNode node
) {
270 return theoryOf(options::theoryOfMode(), node
);
274 * Set the owner of the uninterpreted sort.
276 static void setUninterpretedSortOwner(TheoryId theory
) {
277 s_uninterpretedSortOwner
= theory
;
281 * Get the owner of the uninterpreted sort.
283 static TheoryId
getUninterpretedSortOwner() {
284 return s_uninterpretedSortOwner
;
288 * Checks if the node is a leaf node of this theory
290 inline bool isLeaf(TNode node
) const {
291 return node
.getNumChildren() == 0 || theoryOf(node
) != d_id
;
295 * Checks if the node is a leaf node of a theory.
297 inline static bool isLeafOf(TNode node
, TheoryId theoryId
) {
298 return node
.getNumChildren() == 0 || theoryOf(node
) != theoryId
;
302 * Returns true if the assertFact queue is empty
304 bool done() const throw() {
305 return d_factsHead
== d_facts
.size();
309 * Destructs a Theory.
314 * Subclasses of Theory may add additional efforts. DO NOT CHECK
315 * equality with one of these values (e.g. if STANDARD xxx) but
316 * rather use range checks (or use the helper functions below).
317 * Normally we call QUICK_CHECK or STANDARD; at the leaves we call
322 * Standard effort where theory need not do anything
324 EFFORT_STANDARD
= 50,
326 * Full effort requires the theory make sure its assertions are satisfiable or not
330 * Combination effort means that the individual theories are already satisfied, and
331 * it is time to put some effort into propagation of shared term equalities
333 EFFORT_COMBINATION
= 150,
335 * Last call effort, reserved for quantifiers.
337 EFFORT_LAST_CALL
= 200
340 static inline bool standardEffortOrMore(Effort e
) CVC4_CONST_FUNCTION
341 { return e
>= EFFORT_STANDARD
; }
342 static inline bool standardEffortOnly(Effort e
) CVC4_CONST_FUNCTION
343 { return e
>= EFFORT_STANDARD
&& e
< EFFORT_FULL
; }
344 static inline bool fullEffort(Effort e
) CVC4_CONST_FUNCTION
345 { return e
== EFFORT_FULL
; }
346 static inline bool combination(Effort e
) CVC4_CONST_FUNCTION
347 { return e
== EFFORT_COMBINATION
; }
350 * Get the id for this Theory.
352 TheoryId
getId() const {
357 * Returns a string that uniquely identifies this theory solver w.r.t. the
360 std::string
getFullInstanceName() const;
364 * Get the SAT context associated to this Theory.
366 context::Context
* getSatContext() const {
371 * Get the context associated to this Theory.
373 context::UserContext
* getUserContext() const {
374 return d_userContext
;
378 * Set the output channel associated to this theory.
380 void setOutputChannel(OutputChannel
& out
) {
385 * Get the output channel associated to this theory.
387 OutputChannel
& getOutputChannel() {
392 * Get the valuation associated to this theory.
394 Valuation
& getValuation() {
399 * Get the quantifiers engine associated to this theory.
401 QuantifiersEngine
* getQuantifiersEngine() {
402 return d_quantEngine
;
406 * Get the quantifiers engine associated to this theory (const version).
408 const QuantifiersEngine
* getQuantifiersEngine() const {
409 return d_quantEngine
;
413 * Finish theory initialization. At this point, options and the logic
414 * setting are final, and the master equality engine and quantifiers
415 * engine (if any) are initialized. This base class implementation
418 virtual void finishInit() { }
421 * Some theories have kinds that are effectively definitions and
422 * should be expanded before they are handled. Definitions allow
423 * a much wider range of actions than the normal forms given by the
424 * rewriter; they can enable other theories and create new terms.
425 * However no assumptions can be made about subterms having been
426 * expanded or rewritten. Where possible rewrite rules should be
427 * used, definitions should only be used when rewrites are not
428 * possible, for example in handling under-specified operations
429 * using partially defined functions.
431 virtual Node
expandDefinition(LogicRequest
&logicRequest
, Node node
) {
432 // by default, do nothing
437 * Pre-register a term. Done one time for a Node per SAT context level.
439 virtual void preRegisterTerm(TNode
) { }
442 * Assert a fact in the current context.
444 void assertFact(TNode assertion
, bool isPreregistered
) {
445 Trace("theory") << "Theory<" << getId() << ">::assertFact["
446 << d_satContext
->getLevel() << "](" << assertion
<< ", "
447 << (isPreregistered
? "true" : "false") << ")" << std::endl
;
448 d_facts
.push_back(Assertion(assertion
, isPreregistered
));
452 * This method is called to notify a theory that the node n should
453 * be considered a "shared term" by this theory
455 virtual void addSharedTerm(TNode n
) { }
458 * Called to set the master equality engine.
460 virtual void setMasterEqualityEngine(eq::EqualityEngine
* eq
) { }
462 /** Called to set the quantifiers engine. */
463 virtual void setQuantifiersEngine(QuantifiersEngine
* qe
);
465 /** Setup an ExtTheory module for this Theory. Can only be called once. */
466 void setupExtTheory();
469 * Return the current theory care graph. Theories should overload
470 * computeCareGraph to do the actual computation, and use addCarePair to add
471 * pairs to the care graph.
473 void getCareGraph(CareGraph
* careGraph
);
476 * Return the status of two terms in the current context. Should be
477 * implemented in sub-theories to enable more efficient theory-combination.
479 virtual EqualityStatus
getEqualityStatus(TNode a
, TNode b
) {
480 return EQUALITY_UNKNOWN
;
484 * Return the model value of the give shared term (or null if not available).
486 virtual Node
getModelValue(TNode var
) { return Node::null(); }
489 * Check the current assignment's consistency.
491 * An implementation of check() is required to either:
492 * - return a conflict on the output channel,
494 * - throw an exception
495 * - or call get() until done() is true.
497 virtual void check(Effort level
= EFFORT_FULL
) { }
499 /** Needs last effort check? */
500 virtual bool needsCheckLastEffort() { return false; }
502 /** T-propagate new literal assignments in the current context. */
503 virtual void propagate(Effort level
= EFFORT_FULL
) { }
506 * Return an explanation for the literal represented by parameter n
507 * (which was previously propagated by this theory).
509 virtual Node
explain(TNode n
) {
510 Unimplemented("Theory %s propagated a node but doesn't implement the "
511 "Theory::explain() interface!", identify().c_str());
515 * Get all relevant information in this theory regarding the current
516 * model. This should be called after a call to check( FULL_EFFORT )
517 * for all theories with no conflicts and no lemmas added.
518 * If fullModel is true, then we must specify sufficient information for
519 * the model class to construct constant representatives for each equivalence
522 virtual void collectModelInfo( TheoryModel
* m
, bool fullModel
){ }
524 /** if theories want to do something with model after building, do it here */
525 virtual void postProcessModel( TheoryModel
* m
){ }
528 * Return a decision request, if the theory has one, or the NULL node
530 * If returning non-null node, hould set priority to
531 * 0 if decision is necessary for model-soundness,
532 * 1 if decision is necessary for completeness,
535 virtual Node
getNextDecisionRequest( unsigned& priority
) { return Node(); }
538 * Statically learn from assertion "in," which has been asserted
539 * true at the top level. The theory should only add (via
540 * ::operator<< or ::append()) to the "learned" builder---it should
541 * *never* clear it. It is a conjunction to add to the formula at
542 * the top-level and may contain other theories' contributions.
544 virtual void ppStaticLearn(TNode in
, NodeBuilder
<>& learned
) { }
546 enum PPAssertStatus
{
547 /** Atom has been solved */
548 PP_ASSERT_STATUS_SOLVED
,
549 /** Atom has not been solved */
550 PP_ASSERT_STATUS_UNSOLVED
,
551 /** Atom is inconsistent */
552 PP_ASSERT_STATUS_CONFLICT
556 * Given a literal, add the solved substitutions to the map, if any.
557 * The method should return true if the literal can be safely removed.
559 virtual PPAssertStatus
ppAssert(TNode in
, SubstitutionMap
& outSubstitutions
);
562 * Given an atom of the theory coming from the input formula, this
563 * method can be overridden in a theory implementation to rewrite
564 * the atom into an equivalent form. This is only called just
565 * before an input atom to the engine.
567 virtual Node
ppRewrite(TNode atom
) { return atom
; }
570 * Don't preprocess subterm of this term
572 virtual bool ppDontRewriteSubterm(TNode atom
) { return false; }
575 * Notify preprocessed assertions. Called on new assertions after
576 * preprocessing before they are asserted to theory engine.
578 virtual void ppNotifyAssertions(const std::vector
<Node
>& assertions
) {}
581 * A Theory is called with presolve exactly one time per user
582 * check-sat. presolve() is called after preregistration,
583 * rewriting, and Boolean propagation, (other theories'
584 * propagation?), but the notified Theory has not yet had its
585 * check() or propagate() method called. A Theory may empty its
586 * assertFact() queue using get(). A Theory can raise conflicts,
587 * add lemmas, and propagate literals during presolve().
589 * NOTE: The presolve property must be added to the kinds file for
592 virtual void presolve() { }
595 * A Theory is called with postsolve exactly one time per user
596 * check-sat. postsolve() is called after the query has completed
597 * (regardless of whether sat, unsat, or unknown), and after any
598 * model-querying related to the query has been performed.
599 * After this call, the theory will not get another check() or
600 * propagate() call until presolve() is called again. A Theory
601 * cannot raise conflicts, add lemmas, or propagate literals during
604 virtual void postsolve() { }
607 * Notification sent to the theory wheneven the search restarts.
608 * Serves as a good time to do some clean-up work, and you can
609 * assume you're at DL 0 for the purposes of Contexts. This function
610 * should not use the output channel.
612 virtual void notifyRestart() { }
615 * Identify this theory (for debugging, dynamic configuration,
618 virtual std::string
identify() const = 0;
620 /** Set user attribute
621 * This function is called when an attribute is set by a user. In SMT-LIBv2 this is done
622 * via the syntax (! n :attr)
624 virtual void setUserAttribute(const std::string
& attr
, Node n
, std::vector
<Node
> node_values
, std::string str_value
) {
625 Unimplemented("Theory %s doesn't support Theory::setUserAttribute interface",
629 /** A set of theories */
630 typedef uint32_t Set
;
632 /** A set of all theories */
633 static const Set AllTheories
= (1 << theory::THEORY_LAST
) - 1;
635 /** Pops a first theory off the set */
636 static inline TheoryId
setPop(Set
& set
) {
637 uint32_t i
= ffs(set
); // Find First Set (bit)
638 if (i
== 0) { return THEORY_LAST
; }
639 TheoryId id
= (TheoryId
)(i
-1);
640 set
= setRemove(id
, set
);
644 /** Returns the size of a set of theories */
645 static inline size_t setSize(Set set
) {
647 while (setPop(set
) != THEORY_LAST
) {
653 /** Returns the index size of a set of theories */
654 static inline size_t setIndex(TheoryId id
, Set set
) {
655 Assert (setContains(id
, set
));
657 while (setPop(set
) != id
) {
663 /** Add the theory to the set. If no set specified, just returns a singleton set */
664 static inline Set
setInsert(TheoryId theory
, Set set
= 0) {
665 return set
| (1 << theory
);
668 /** Add the theory to the set. If no set specified, just returns a singleton set */
669 static inline Set
setRemove(TheoryId theory
, Set set
= 0) {
670 return setDifference(set
, setInsert(theory
));
673 /** Check if the set contains the theory */
674 static inline bool setContains(TheoryId theory
, Set set
) {
675 return set
& (1 << theory
);
678 static inline Set
setComplement(Set a
) {
679 return (~a
) & AllTheories
;
682 static inline Set
setIntersection(Set a
, Set b
) {
686 static inline Set
setUnion(Set a
, Set b
) {
691 static inline Set
setDifference(Set a
, Set b
) {
695 static inline std::string
setToString(theory::Theory::Set theorySet
) {
696 std::stringstream ss
;
698 for(unsigned theoryId
= 0; theoryId
< theory::THEORY_LAST
; ++theoryId
) {
699 if (theory::Theory::setContains((theory::TheoryId
)theoryId
, theorySet
)) {
700 ss
<< (theory::TheoryId
) theoryId
<< " ";
707 typedef context::CDList
<Assertion
>::const_iterator assertions_iterator
;
710 * Provides access to the facts queue, primarily intended for theory
711 * debugging purposes.
713 * @return the iterator to the beginning of the fact queue
715 assertions_iterator
facts_begin() const {
716 return d_facts
.begin();
720 * Provides access to the facts queue, primarily intended for theory
721 * debugging purposes.
723 * @return the iterator to the end of the fact queue
725 assertions_iterator
facts_end() const {
726 return d_facts
.end();
729 * Whether facts have been asserted to this theory.
731 * @return true iff facts have been asserted to this theory.
734 return !d_facts
.empty();
737 typedef context::CDList
<TNode
>::const_iterator shared_terms_iterator
;
740 * Provides access to the shared terms, primarily intended for theory
741 * debugging purposes.
743 * @return the iterator to the beginning of the shared terms list
745 shared_terms_iterator
shared_terms_begin() const {
746 return d_sharedTerms
.begin();
750 * Provides access to the facts queue, primarily intended for theory
751 * debugging purposes.
753 * @return the iterator to the end of the shared terms list
755 shared_terms_iterator
shared_terms_end() const {
756 return d_sharedTerms
.end();
761 * This is a utility function for constructing a copy of the currently shared terms
762 * in a queriable form. As this is
764 std::hash_set
<TNode
, TNodeHashFunction
> currentlySharedTerms() const;
767 * This allows the theory to be queried for whether a literal, lit, is
768 * entailed by the theory. This returns a pair of a Boolean and a node E.
770 * If the Boolean is true, then E is a formula that entails lit and E is propositionally
771 * entailed by the assertions to the theory.
773 * If the Boolean is false, it is "unknown" if lit is entailed and E may be
776 * The literal lit is either an atom a or (not a), which must belong to the theory:
777 * There is some TheoryOfMode m s.t. Theory::theoryOf(m, a) == this->getId().
779 * There are NO assumptions that a or the subterms of a have been
780 * preprocessed in any form. This includes ppRewrite, rewriting,
781 * preregistering, registering, definition expansion or ITE removal!
783 * Theories are free to limit the amount of effort they use and so may
784 * always opt to return "unknown". Both "unknown" and "not entailed",
785 * may return for E a non-boolean Node (e.g. Node::null()). (There is no explicit output
786 * for the negation of lit is entailed.)
788 * If lit is theory valid, the return result may be the Boolean constant
791 * If lit is entailed by multiple assertions on the theory's getFact()
792 * queue, a_1, a_2, ... and a_k, this may return E=(and a_1 a_2 ... a_k) or
793 * another theory entailed explanation E=(and (and a_1 a_2) (and a3 a_4) ... a_k)
795 * If lit is entailed by a single assertion on the theory's getFact()
796 * queue, say a, this may return E=a.
798 * The theory may always return false!
800 * The search is controlled by the parameter params. For default behavior,
801 * this may be left NULL.
803 * Theories that want parameters extend the virtual EntailmentCheckParameters
804 * class. Users ask the theory for an appropriate subclass from the theory
805 * and configure that. How this is implemented is on a per theory basis.
807 * The search may provide additional output to guide the user of
808 * this function. This output is stored in a EntailmentCheckSideEffects*
809 * output parameter. The implementation of this is theory specific. For
810 * no output, this is NULL.
812 * Theories may not touch their output stream during an entailment check.
814 * @param lit a literal belonging to the theory.
815 * @param params the control parameters for the entailment check.
816 * @param out a theory specific output object of the entailment search.
817 * @return a pair <b,E> s.t. if b is true, then a formula E such that
818 * E |= lit in the theory.
820 virtual std::pair
<bool, Node
> entailmentCheck(
821 TNode lit
, const EntailmentCheckParameters
* params
= NULL
,
822 EntailmentCheckSideEffects
* out
= NULL
);
824 /* equality engine TODO: use? */
825 virtual eq::EqualityEngine
* getEqualityEngine() { return NULL
; }
827 /* Get extended theory if one has been installed. */
828 ExtTheory
* getExtTheory();
830 /* get current substitution at an effort
833 * where ( exp[vars[i]] => vars[i] = subs[i] ) holds for all i
835 virtual bool getCurrentSubstitution(int effort
, std::vector
<Node
>& vars
,
836 std::vector
<Node
>& subs
,
837 std::map
<Node
, std::vector
<Node
> >& exp
) {
842 * Get reduction for node
843 * If return value is not 0, then n is reduced.
844 * If return value <0 then n is reduced SAT-context-independently (e.g. by a
845 * lemma that persists at this user-context level).
846 * If nr is non-null, then ( n = nr ) should be added as a lemma by caller,
847 * and return value should be <0.
849 virtual int getReduction( int effort
, Node n
, Node
& nr
) { return 0; }
851 /** Turn on proof-production mode. */
852 void produceProofs() { d_proofsEnabled
= true; }
856 std::ostream
& operator<<(std::ostream
& os
, theory::Theory::Effort level
);
859 inline theory::Assertion
Theory::get() {
860 Assert( !done(), "Theory::get() called with assertion queue empty!" );
863 Assertion fact
= d_facts
[d_factsHead
];
864 d_factsHead
= d_factsHead
+ 1;
866 Trace("theory") << "Theory::get() => " << fact
<< " (" << d_facts
.size() - d_factsHead
<< " left)" << std::endl
;
868 if(Dump
.isOn("state")) {
869 Dump("state") << AssertCommand(fact
.assertion
.toExpr());
875 inline std::ostream
& operator<<(std::ostream
& out
,
876 const CVC4::theory::Theory
& theory
) {
877 return out
<< theory
.identify();
880 inline std::ostream
& operator << (std::ostream
& out
, theory::Theory::PPAssertStatus status
) {
882 case theory::Theory::PP_ASSERT_STATUS_SOLVED
:
883 out
<< "SOLVE_STATUS_SOLVED"; break;
884 case theory::Theory::PP_ASSERT_STATUS_UNSOLVED
:
885 out
<< "SOLVE_STATUS_UNSOLVED"; break;
886 case theory::Theory::PP_ASSERT_STATUS_CONFLICT
:
887 out
<< "SOLVE_STATUS_CONFLICT"; break;
894 class EntailmentCheckParameters
{
898 EntailmentCheckParameters(TheoryId tid
);
900 TheoryId
getTheoryId() const;
901 virtual ~EntailmentCheckParameters();
902 };/* class EntailmentCheckParameters */
904 class EntailmentCheckSideEffects
{
908 EntailmentCheckSideEffects(TheoryId tid
);
910 TheoryId
getTheoryId() const;
911 virtual ~EntailmentCheckSideEffects();
912 };/* class EntailmentCheckSideEffects */
916 typedef context::CDHashMap
<Node
, bool, NodeHashFunction
> NodeBoolMap
;
917 typedef context::CDHashSet
<Node
, NodeHashFunction
> NodeSet
;
920 static std::vector
<Node
> collectVars(Node n
);
921 // is context dependent inactive
922 bool isContextIndependentInactive( Node n
) const;
923 //do inferences internal
924 bool doInferencesInternal(int effort
, const std::vector
<Node
>& terms
,
925 std::vector
<Node
>& nred
, bool batch
, bool isRed
);
927 bool sendLemma( Node lem
, bool preprocess
= false );
928 // register term (recursive)
929 void registerTermRec(Node n
, std::set
<Node
>* visited
);
933 //extended string terms, map to whether they are active
934 NodeBoolMap d_ext_func_terms
;
935 //set of terms from d_ext_func_terms that are SAT-context-independently inactive
936 // (e.g. term t when a reduction lemma of the form t = t' was added)
937 NodeSet d_ci_inactive
;
938 //cache of all lemmas sent
941 //watched term for checking if any non-reduced extended functions exist
942 context::CDO
< Node
> d_has_extf
;
944 std::map
< Kind
, bool > d_extf_kind
;
945 //information for each term in d_ext_func_terms
948 //all variables in this term
949 std::vector
< Node
> d_vars
;
951 std::map
< Node
, ExtfInfo
> d_extf_info
;
954 ExtTheory(Theory
* p
);
955 virtual ~ExtTheory() {}
957 void addFunctionKind(Kind k
) { d_extf_kind
[k
] = true; }
958 bool hasFunctionKind(Kind k
) const {
959 return d_extf_kind
.find(k
) != d_extf_kind
.end();
962 // adds n to d_ext_func_terms if addFunctionKind( n.getKind() ) was called
963 void registerTerm( Node n
);
964 void registerTermRec( Node n
);
965 // set n as reduced/inactive
966 // if contextDepend = false, then n remains inactive in the duration of this user-context level
967 void markReduced( Node n
, bool contextDepend
= true );
968 // mark that a and b are congruent terms: set b inactive, set a to inactive if b was inactive
969 void markCongruent( Node a
, Node b
);
971 //getSubstitutedTerms
972 // input : effort, terms
973 // output : sterms, exp, where ( exp[i] => terms[i] = sterms[i] ) for all i
974 void getSubstitutedTerms(int effort
, const std::vector
<Node
>& terms
,
975 std::vector
<Node
>& sterms
,
976 std::vector
<std::vector
<Node
> >& exp
);
978 // * input : effort, terms, batch (whether to send one lemma or lemmas for
980 // * sends rewriting lemmas of the form ( exp => t = c ) where t is in terms
981 // and c is a constant, c = rewrite( t*sigma ) where exp |= sigma
982 // * output : nred (the terms that are still active)
983 // * return : true iff lemma is sent
984 bool doInferences(int effort
, const std::vector
<Node
>& terms
,
985 std::vector
<Node
>& nred
, bool batch
= true);
986 bool doInferences(int effort
, std::vector
<Node
>& nred
, bool batch
= true);
988 // same as doInferences, but will send reduction lemmas of the form ( t = t' )
989 // where t is in terms, t' is equivalent, reduced term.
990 bool doReductions(int effort
, const std::vector
<Node
>& terms
,
991 std::vector
<Node
>& nred
, bool batch
= true);
992 bool doReductions(int effort
, std::vector
<Node
>& nred
, bool batch
= true);
995 bool hasActiveTerm();
997 bool isActive(Node n
);
998 // get the set of active terms from d_ext_func_terms
999 std::vector
<Node
> getActive() const;
1000 // get the set of active terms from d_ext_func_terms of kind k
1001 std::vector
<Node
> getActive(Kind k
) const;
1004 }/* CVC4::theory namespace */
1005 }/* CVC4 namespace */
1007 #endif /* __CVC4__THEORY__THEORY_H */