src/theory/output_channel.h

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