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