src/theory/output_channel.h

   1 /*********************                                                        */
   2 /*! \file output_channel.h
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Morgan Deters, Liana Hadarean, 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
  11  **
  12  ** \brief The theory output channel interface
  13  **
  14  ** The theory output channel interface.
  15  **/
  16
  17 #include "cvc4_private.h"
  18
  19 #ifndef __CVC4__THEORY__OUTPUT_CHANNEL_H
  20 #define __CVC4__THEORY__OUTPUT_CHANNEL_H
  21
  22 #include "base/cvc4_assert.h"
  23 #include "smt/logic_exception.h"
  24 #include "theory/interrupted.h"
  25 #include "proof/proof_manager.h"
  26 #include "util/resource_manager.h"
  27
  28 namespace CVC4 {
  29 namespace theory {
  30
  31 class Theory;
  32
  33 /**
  34  * A LemmaStatus, returned from OutputChannel::lemma(), provides information
  35  * about the lemma added.  In particular, it contains the T-rewritten lemma
  36  * for inspection and the user-level at which the lemma will reside.
  37  */
  38 class LemmaStatus {
  39   Node d_rewrittenLemma;
  40   unsigned d_level;
  41
  42 public:
  43   LemmaStatus(TNode rewrittenLemma, unsigned level) :
  44     d_rewrittenLemma(rewrittenLemma),
  45     d_level(level) {
  46   }
  47
  48   /** Get the T-rewritten form of the lemma. */
  49   TNode getRewrittenLemma() const throw() { return d_rewrittenLemma; }
  50
  51   /**
  52    * Get the user-level at which the lemma resides.  After this user level
  53    * is popped, the lemma is un-asserted from the SAT layer.  This level
  54    * will be 0 if the lemma didn't reach the SAT layer at all.
  55    */
  56   unsigned getLevel() const throw() { return d_level; }
  57
  58 };/* class LemmaStatus */
  59
  60 /**
  61  * Generic "theory output channel" interface.
  62  */
  63 class OutputChannel {
  64   /** Disallow copying: private constructor */
  65   OutputChannel(const OutputChannel&) CVC4_UNDEFINED;
  66
  67   /** Disallow assignment: private operator=() */
  68   OutputChannel& operator=(const OutputChannel&) CVC4_UNDEFINED;
  69
  70 public:
  71
  72   /**
  73    * Construct an OutputChannel.
  74    */
  75   OutputChannel() {
  76   }
  77
  78   /**
  79    * Destructs an OutputChannel.  This implementation does nothing,
  80    * but we need a virtual destructor for safety in case subclasses
  81    * have a destructor.
  82    */
  83   virtual ~OutputChannel() {
  84   }
  85
  86   /**
  87    * With safePoint(), the theory signals that it is at a safe point
  88    * and can be interrupted.
  89    */
  90   virtual void safePoint(uint64_t amount)
  91       throw(Interrupted, UnsafeInterruptException, AssertionException)
  92   {}
  93
  94   /**
  95    * Indicate a theory conflict has arisen.
  96    *
  97    * @param n - a conflict at the current decision level.  This should
  98    * be an AND-kinded node of literals that are TRUE in the current
  99    * assignment and are in conflict (i.e., at least one must be
 100    * assigned false), or else a literal by itself (in the case of a
 101    * unit conflict) which is assigned TRUE (and T-conflicting) in the
 102    * current assignment.
 103    * @param pf - a proof of the conflict. This is only non-null if proofs
 104    * are enabled.
 105    */
 106   virtual void conflict(TNode n, Proof* pf = NULL) throw(AssertionException, UnsafeInterruptException) = 0;
 107
 108   /**
 109    * Propagate a theory literal.
 110    *
 111    * @param n - a theory consequence at the current decision level
 112    * @return false if an immediate conflict was encountered
 113    */
 114   virtual bool propagate(TNode n) throw(AssertionException, UnsafeInterruptException) = 0;
 115
 116   /**
 117    * Tell the core that a valid theory lemma at decision level 0 has
 118    * been detected.  (This requests a split.)
 119    *
 120    * @param n - a theory lemma valid at decision level 0
 121    * @param rule - the proof rule for this lemma
 122    * @param removable - whether the lemma can be removed at any point
 123    * @param preprocess - whether to apply more aggressive preprocessing
 124    * @param sendAtoms - whether to ensure atoms are sent to the theory
 125    * @return the "status" of the lemma, including user level at which
 126    * the lemma resides; the lemma will be removed when this user level pops
 127    */
 128   virtual LemmaStatus lemma(TNode n, ProofRule rule,
 129                             bool removable = false,
 130                             bool preprocess = false,
 131                             bool sendAtoms = false)
 132     throw(TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) = 0;
 133
 134   /**
 135    * Variant of the lemma function that does not require providing a proof rule.
 136    */
 137   virtual LemmaStatus lemma(TNode n,
 138                             bool removable = false,
 139                             bool preprocess = false,
 140                             bool sendAtoms = false)
 141     throw(TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) {
 142     return lemma(n, RULE_INVALID, removable, preprocess, sendAtoms);
 143   }
 144
 145   /**
 146    * Request a split on a new theory atom.  This is equivalent to
 147    * calling lemma({OR n (NOT n)}).
 148    *
 149    * @param n - a theory atom; must be of Boolean type
 150    */
 151   LemmaStatus split(TNode n)
 152     throw(TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) {
 153     return splitLemma(n.orNode(n.notNode()));
 154   }
 155
 156   virtual LemmaStatus splitLemma(TNode n, bool removable = false)
 157     throw(TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) = 0;
 158
 159   /**
 160    * If a decision is made on n, it must be in the phase specified.
 161    * Note that this is enforced *globally*, i.e., it is completely
 162    * context-INdependent.  If you ever requirePhase() on a literal,
 163    * it is phase-locked forever and ever.  If it is to ever have the
 164    * other phase as its assignment, it will be because it has been
 165    * propagated that way (or it's a unit, at decision level 0).
 166    *
 167    * @param n - a theory atom with a SAT literal assigned; must have
 168    * been pre-registered
 169    * @param phase - the phase to decide on n
 170    */
 171   virtual void requirePhase(TNode n, bool phase)
 172     throw(Interrupted, TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) = 0;
 173
 174   /**
 175    * Flips the most recent unflipped decision to the other phase and
 176    * returns true.  If all decisions have been flipped, the root
 177    * decision is re-flipped and flipDecision() returns false.  If no
 178    * decisions (flipped nor unflipped) are on the decision stack, the
 179    * state is not affected and flipDecision() returns false.
 180    *
 181    * For example, if l1, l2, and l3 are all decision literals, and
 182    * have been decided in positive phase, a series of flipDecision()
 183    * calls has the following effects:
 184    *
 185    * l1 l2 l3 <br/>
 186    * l1 l2 ~l3 <br/>
 187    * l1 ~l2 <br/>
 188    * ~l1 <br/>
 189    * l1 (and flipDecision() returns false)
 190    *
 191    * Naturally, flipDecision() might be interleaved with search.  For example:
 192    *
 193    * l1 l2 l3 <br/>
 194    * flipDecision() <br/>
 195    * l1 l2 ~l3 <br/>
 196    * flipDecision() <br/>
 197    * l1 ~l2 <br/>
 198    * SAT decides l3 <br/>
 199    * l1 ~l2 l3 <br/>
 200    * flipDecision() <br/>
 201    * l1 ~l2 ~l3 <br/>
 202    * flipDecision() <br/>
 203    * ~l1 <br/>
 204    * SAT decides l2 <br/>
 205    * ~l1 l2 <br/>
 206    * flipDecision() <br/>
 207    * ~l1 ~l2 <br/>
 208    * flipDecision() returns FALSE<br/>
 209    * l1
 210    *
 211    * @return true if a decision was flipped; false if no decision
 212    * could be flipped, or if the root decision was re-flipped
 213    */
 214   virtual bool flipDecision()
 215     throw(Interrupted, TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) = 0;
 216
 217   /**
 218    * Notification from a theory that it realizes it is incomplete at
 219    * this context level.  If SAT is later determined by the
 220    * TheoryEngine, it should actually return an UNKNOWN result.
 221    */
 222   virtual void setIncomplete() throw(AssertionException, UnsafeInterruptException) = 0;
 223
 224   /**
 225    * "Spend" a "resource."  The meaning is specific to the context in
 226    * which the theory is operating, and may even be ignored.  The
 227    * intended meaning is that if the user has set a limit on the "units
 228    * of resource" that can be expended in a search, and that limit is
 229    * exceeded, then the search is terminated.  Note that the check for
 230    * termination occurs in the main search loop, so while theories
 231    * should call OutputChannel::spendResource() during particularly
 232    * long-running operations, they cannot rely on resource() to break
 233    * out of infinite or intractable computations.
 234    */
 235   virtual void spendResource(unsigned ammount) throw(UnsafeInterruptException) {}
 236
 237   /**
 238    * Handle user attribute.
 239    * Associates theory t with the attribute attr.  Theory t will be
 240    * notified whenever an attribute of name attr is set on a node.
 241    * This can happen through, for example, the SMT-LIBv2 language.
 242    */
 243   virtual void handleUserAttribute(const char* attr, Theory* t) {}
 244
 245
 246   /** Demands that the search restart from sat search level 0.
 247    * Using this leads to non-termination issues.
 248    * It is appropriate for prototyping for theories.
 249    */
 250   virtual void demandRestart() throw(TypeCheckingExceptionPrivate, AssertionException, UnsafeInterruptException) {}
 251
 252 };/* class OutputChannel */
 253
 254 }/* CVC4::theory namespace */
 255 }/* CVC4 namespace */
 256
 257 #endif /* __CVC4__THEORY__OUTPUT_CHANNEL_H */