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