GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/prop/prop_engine.h Lines: 1 1 100.0 %
Date: 2021-08-06 Branches: 0 0 0.0 %

Line Exec Source
1
/******************************************************************************
2
 * Top contributors (to current version):
3
 *   Andrew Reynolds, Morgan Deters, Dejan Jovanovic
4
 *
5
 * This file is part of the cvc5 project.
6
 *
7
 * Copyright (c) 2009-2021 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.
11
 * ****************************************************************************
12
 *
13
 * The PropEngine (propositional engine).
14
 *
15
 * Main interface point between cvc5's SMT infrastructure and the SAT solver.
16
 */
17
18
#include "cvc5_private.h"
19
20
#ifndef CVC5__PROP_ENGINE_H
21
#define CVC5__PROP_ENGINE_H
22
23
#include "context/cdlist.h"
24
#include "expr/node.h"
25
#include "proof/trust_node.h"
26
#include "prop/skolem_def_manager.h"
27
#include "theory/output_channel.h"
28
#include "util/result.h"
29
30
namespace cvc5 {
31
32
class Env;
33
class ResourceManager;
34
class ProofNodeManager;
35
class TheoryEngine;
36
37
namespace decision {
38
class DecisionEngine;
39
}
40
41
namespace prop {
42
43
class CnfStream;
44
class CDCLTSatSolverInterface;
45
class ProofCnfStream;
46
class PropPfManager;
47
class TheoryProxy;
48
49
/**
50
 * PropEngine is the abstraction of a Sat Solver, providing methods for
51
 * solving the SAT problem and conversion to CNF (via the CnfStream).
52
 */
53
class PropEngine
54
{
55
 public:
56
  /**
57
   * Create a PropEngine with a particular decision and theory engine.
58
   */
59
  PropEngine(TheoryEngine* te,
60
             Env& env,
61
             ProofNodeManager* pnm);
62
63
  /**
64
   * Destructor.
65
   */
66
  ~PropEngine();
67
68
  /**
69
   * Finish initialize. Call this after construction just before we are
70
   * ready to use this class. Should be called after TheoryEngine::finishInit.
71
   * This method converts and asserts true and false into the CNF stream.
72
   */
73
  void finishInit();
74
75
  /**
76
   * This is called by SmtEngine, at shutdown time, just before
77
   * destruction.  It is important because there are destruction
78
   * ordering issues between some parts of the system (notably between
79
   * PropEngine and Theory).  For now, there's nothing to do here in
80
   * the PropEngine.
81
   */
82
9853
  void shutdown() {}
83
84
  /**
85
   * Preprocess the given node. Return the REWRITE trust node corresponding to
86
   * rewriting node. New lemmas and skolems are added to ppLemmas and
87
   * ppSkolems respectively.
88
   *
89
   * @param node The assertion to preprocess,
90
   * @param ppLemmas The lemmas to add to the set of assertions,
91
   * @param ppSkolems The skolems that newLemmas correspond to,
92
   * @return The (REWRITE) trust node corresponding to rewritten node via
93
   * preprocessing.
94
   */
95
  TrustNode preprocess(TNode node,
96
                       std::vector<TrustNode>& ppLemmas,
97
                       std::vector<Node>& ppSkolems);
98
  /**
99
   * Remove term ITEs (and more generally, term formulas) from the given node.
100
   * Return the REWRITE trust node corresponding to rewriting node. New lemmas
101
   * and skolems are added to ppLemmas and ppSkolems respectively. This can
102
   * be seen a subset of the above preprocess method, which also does theory
103
   * preprocessing and rewriting.
104
   *
105
   * @param node The assertion to preprocess,
106
   * @param ppLemmas The lemmas to add to the set of assertions,
107
   * @param ppSkolems The skolems that newLemmas correspond to,
108
   * @return The (REWRITE) trust node corresponding to rewritten node via
109
   * preprocessing.
110
   */
111
  TrustNode removeItes(TNode node,
112
                       std::vector<TrustNode>& ppLemmas,
113
                       std::vector<Node>& ppSkolems);
114
115
  /**
116
   * Converts the given formulas to CNF and assert the CNF to the SAT solver.
117
   * These formulas are asserted permanently for the current context.
118
   * Information about which assertions correspond to skolem definitions is
119
   * contained in skolemMap.
120
   *
121
   * @param assertions the formulas to assert
122
   * @param skolemMap a map which says which skolem (if any) each assertion
123
   * corresponds to. For example, if (ite C (= k a) (= k b)) is the i^th
124
   * assertion, then skolemMap may contain the entry { i -> k }.
125
   */
126
  void assertInputFormulas(const std::vector<Node>& assertions,
127
                           std::unordered_map<size_t, Node>& skolemMap);
128
129
  /**
130
   * Converts the given formula to CNF and assert the CNF to the SAT solver.
131
   * The formula can be removed by the SAT solver after backtracking lower
132
   * than the (SAT and SMT) level at which it was asserted.
133
   *
134
   * @param trn the trust node storing the formula to assert
135
   * @param p the properties of the lemma
136
   */
137
  void assertLemma(TrustNode tlemma, theory::LemmaProperty p);
138
139
  /**
140
   * If ever n is decided upon, it must be in the given phase.  This
141
   * occurs *globally*, i.e., even if the literal is untranslated by
142
   * user pop and retranslated, it keeps this phase.  The associated
143
   * variable will _always_ be phase-locked.
144
   *
145
   * @param n the node in question; must have an associated SAT literal
146
   * @param phase the phase to use
147
   */
148
  void requirePhase(TNode n, bool phase);
149
150
  /**
151
   * Return whether the given literal is a SAT decision.  Either phase
152
   * is permitted; that is, if "lit" is a SAT decision, this function
153
   * returns true for both lit and the negation of lit.
154
   */
155
  bool isDecision(Node lit) const;
156
157
  /**
158
   * Return SAT context level at which `lit` was decided on.
159
   *
160
   * @param lit: The node in question, must have an associated SAT literal.
161
   * @return Decision level of the SAT variable of `lit` (phase is disregarded),
162
   *         or -1 if `lit` has not been assigned yet.
163
   */
164
  int32_t getDecisionLevel(Node lit) const;
165
166
  /**
167
   * Return the user-context level when `lit` was introduced..
168
   *
169
   * @return User-context level or -1 if not yet introduced.
170
   */
171
  int32_t getIntroLevel(Node lit) const;
172
173
  /**
174
   * Checks the current context for satisfiability.
175
   *
176
   */
177
  Result checkSat();
178
179
  /**
180
   * Get the value of a boolean variable.
181
   *
182
   * @return mkConst<true>, mkConst<false>, or Node::null() if
183
   * unassigned.
184
   */
185
  Node getValue(TNode node) const;
186
187
  /**
188
   * Return true if node has an associated SAT literal.
189
   */
190
  bool isSatLiteral(TNode node) const;
191
192
  /**
193
   * Check if the node has a value and return it if yes.
194
   */
195
  bool hasValue(TNode node, bool& value) const;
196
197
  /**
198
   * Returns the Boolean variables known to the SAT solver.
199
   */
200
  void getBooleanVariables(std::vector<TNode>& outputVariables) const;
201
202
  /**
203
   * Ensure that the given node will have a designated SAT literal
204
   * that is definitionally equal to it. Note that theory preprocessing is
205
   * applied to n. The node returned by this method can be subsequently queried
206
   * via getSatValue().
207
   */
208
  Node ensureLiteral(TNode n);
209
  /**
210
   * This returns the theory-preprocessed form of term n. This rewrites and
211
   * preprocesses n, which notice may involve adding clauses to the SAT solver
212
   * if preprocessing n involves introducing new skolems.
213
   */
214
  Node getPreprocessedTerm(TNode n);
215
  /**
216
   * Same as above, but also compute the skolems in n and in the lemmas
217
   * corresponding to their definition.
218
   *
219
   * Note this will include skolems that occur in the definition lemma
220
   * for all skolems in sks. This is run until a fixed point is reached.
221
   * For example, if k1 has definition (ite A (= k1 k2) (= k1 x)) where k2 is
222
   * another skolem introduced by term formula removal, then calling this
223
   * method on (P k1) will include both k1 and k2 in sks, and their definitions
224
   * in skAsserts.
225
   *
226
   * Notice that this method is not frequently used. It is used for algorithms
227
   * that explicitly care about knowing which skolems occur in the preprocessed
228
   * form of a term, recursively.
229
   */
230
  Node getPreprocessedTerm(TNode n,
231
                           std::vector<Node>& skAsserts,
232
                           std::vector<Node>& sks);
233
234
  /**
235
   * Push the context level.
236
   */
237
  void push();
238
239
  /**
240
   * Pop the context level.
241
   */
242
  void pop();
243
244
  /*
245
   * Reset the decisions in the DPLL(T) SAT solver at the current assertion
246
   * level.
247
   */
248
  void resetTrail();
249
250
  /**
251
   * Get the assertion level of the SAT solver.
252
   */
253
  unsigned getAssertionLevel() const;
254
255
  /**
256
   * Return true if we are currently searching (either in this or
257
   * another thread).
258
   */
259
  bool isRunning() const;
260
261
  /**
262
   * Interrupt a running solver (cause a timeout).
263
   *
264
   * Can potentially throw a ModalException.
265
   */
266
  void interrupt();
267
268
  /**
269
   * Informs the ResourceManager that a resource has been spent.  If out of
270
   * resources, can throw an UnsafeInterruptException exception.
271
   */
272
  void spendResource(Resource r);
273
274
  /**
275
   * For debugging.  Return true if "expl" is a well-formed
276
   * explanation for "node," meaning:
277
   *
278
   * 1. expl is either a SAT literal or an AND of SAT literals
279
   *    currently assigned true;
280
   * 2. node is assigned true;
281
   * 3. node does not appear in expl; and
282
   * 4. node was assigned after all of the literals in expl
283
   */
284
  bool properExplanation(TNode node, TNode expl) const;
285
286
  /** Retrieve this modules proof CNF stream. */
287
  ProofCnfStream* getProofCnfStream();
288
289
  /** Checks that the proof is closed w.r.t. asserted formulas to this engine as
290
   * well as to the given assertions. */
291
  void checkProof(context::CDList<Node>* assertions);
292
293
  /**
294
   * Return the prop engine proof. This should be called only when proofs are
295
   * enabled. Returns a proof of false whose free assumptions are the
296
   * preprocessed assertions.
297
   */
298
  std::shared_ptr<ProofNode> getProof();
299
300
  /** Is proof enabled? */
301
  bool isProofEnabled() const;
302
303
  /** Retrieve unsat core from SAT solver for assumption-based unsat cores. */
304
  void getUnsatCore(std::vector<Node>& core);
305
306
  /** Return the prop engine proof for assumption-based unsat cores. */
307
  std::shared_ptr<ProofNode> getRefutation();
308
309
 private:
310
  /** Dump out the satisfying assignment (after SAT result) */
311
  void printSatisfyingAssignment();
312
313
  /**
314
   * Converts the given formula to CNF and asserts the CNF to the SAT solver.
315
   * The formula can be removed by the SAT solver after backtracking lower
316
   * than the (SAT and SMT) level at which it was asserted.
317
   *
318
   * @param trn the trust node storing the formula to assert
319
   * @param removable whether this lemma can be quietly removed based
320
   * on an activity heuristic
321
   */
322
  void assertTrustedLemmaInternal(TrustNode trn, bool removable);
323
  /**
324
   * Assert node as a formula to the CNF stream
325
   * @param node The formula to assert
326
   * @param negated Whether to assert the negation of node
327
   * @param removable Whether the formula is removable
328
   * @param input Whether the formula came from the input
329
   * @param pg Pointer to a proof generator that can provide a proof of node
330
   * (or its negation if negated is true).
331
   */
332
  void assertInternal(TNode node,
333
                      bool negated,
334
                      bool removable,
335
                      bool input,
336
                      ProofGenerator* pg = nullptr);
337
  /**
338
   * Assert lemmas internal, where trn is a trust node corresponding to a
339
   * formula to assert to the CNF stream, ppLemmas and ppSkolems are the
340
   * skolem definitions and skolems obtained from preprocessing it, and
341
   * removable is whether the lemma is removable.
342
   */
343
  void assertLemmasInternal(TrustNode trn,
344
                            const std::vector<TrustNode>& ppLemmas,
345
                            const std::vector<Node>& ppSkolems,
346
                            bool removable);
347
348
  /**
349
   * Indicates that the SAT solver is currently solving something and we should
350
   * not mess with it's internal state.
351
   */
352
  bool d_inCheckSat;
353
354
  /** The theory engine we will be using */
355
  TheoryEngine* d_theoryEngine;
356
357
  /** Reference to the environment */
358
  Env& d_env;
359
360
  /** The decision engine we will be using */
361
  std::unique_ptr<decision::DecisionEngine> d_decisionEngine;
362
363
  /** The skolem definition manager */
364
  std::unique_ptr<SkolemDefManager> d_skdm;
365
366
  /** SAT solver's proxy back to theories; kept around for dtor cleanup */
367
  TheoryProxy* d_theoryProxy;
368
369
  /** The SAT solver proxy */
370
  CDCLTSatSolverInterface* d_satSolver;
371
372
  /** List of all of the assertions that need to be made */
373
  std::vector<Node> d_assertionList;
374
375
  /** A pointer to the proof node maneger to be used by this engine. */
376
  ProofNodeManager* d_pnm;
377
378
  /** The CNF converter in use */
379
  CnfStream* d_cnfStream;
380
  /** Proof-producing CNF converter */
381
  std::unique_ptr<ProofCnfStream> d_pfCnfStream;
382
383
  /** The proof manager for prop engine */
384
  std::unique_ptr<PropPfManager> d_ppm;
385
386
  /** Whether we were just interrupted (or not) */
387
  bool d_interrupted;
388
389
  /**
390
   * Stores assumptions added via assertInternal() if assumption-based unsat
391
   * cores are enabled.
392
   */
393
  context::CDList<Node> d_assumptions;
394
};
395
396
}  // namespace prop
397
}  // namespace cvc5
398
399
#endif /* CVC5__PROP_ENGINE_H */