GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/expr/proof_node_updater.h Lines: 1 1 100.0 %
Date: 2021-03-22 Branches: 0 0 0.0 %

Line Exec Source
1
/*********************                                                        */
2
/*! \file proof_node_updater.h
3
 ** \verbatim
4
 ** Top contributors (to current version):
5
 **   Andrew Reynolds, Haniel Barbosa, Gereon Kremer
6
 ** This file is part of the CVC4 project.
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.\endverbatim
11
 **
12
 ** \brief A utility for updating proof nodes
13
 **/
14
15
#include "cvc4_private.h"
16
17
#ifndef CVC4__EXPR__PROOF_NODE_UPDATER_H
18
#define CVC4__EXPR__PROOF_NODE_UPDATER_H
19
20
#include <map>
21
#include <memory>
22
23
#include "expr/node.h"
24
#include "expr/proof_node.h"
25
26
namespace CVC4 {
27
28
class CDProof;
29
class ProofNode;
30
class ProofNodeManager;
31
32
/**
33
 * A virtual callback class for updating ProofNode. An example use case of this
34
 * class is to eliminate a proof rule by expansion.
35
 */
36
class ProofNodeUpdaterCallback
37
{
38
 public:
39
  ProofNodeUpdaterCallback();
40
  virtual ~ProofNodeUpdaterCallback();
41
  /** Should proof pn be updated?
42
   *
43
   * @param pn the proof node that maybe should be updated
44
   * @param continueUpdate whether we should continue recursively updating pn
45
   * @return whether we should run the update method on pn
46
   */
47
  virtual bool shouldUpdate(std::shared_ptr<ProofNode> pn,
48
                            bool& continueUpdate) = 0;
49
  /**
50
   * Update the proof rule application, store steps in cdp. Return true if
51
   * the proof changed. It can be assumed that cdp contains proofs of each
52
   * fact in children.
53
   *
54
   * If continueUpdate is set to false in this method, then the resulting
55
   * proof (the proof of res in cdp) is *not* called back to update by the
56
   * proof node updater, nor are its children recursed. Otherwise, by default,
57
   * the proof node updater will continue updating the resulting proof and will
58
   * recursively update its children. This is analogous to marking REWRITE_DONE
59
   * in a rewrite response.
60
   */
61
  virtual bool update(Node res,
62
                      PfRule id,
63
                      const std::vector<Node>& children,
64
                      const std::vector<Node>& args,
65
                      CDProof* cdp,
66
                      bool& continueUpdate);
67
};
68
69
/**
70
 * A generic class for updating ProofNode. It is parameterized by a callback
71
 * class. Its process method runs this callback on all subproofs of a provided
72
 * ProofNode application that meet some criteria
73
 * (ProofNodeUpdaterCallback::shouldUpdate)
74
 * and overwrites them based on the update procedure of the callback
75
 * (ProofNodeUpdaterCallback::update), which uses local CDProof objects that
76
 * should be filled in the callback for each ProofNode to update.
77
 */
78
4216
class ProofNodeUpdater
79
{
80
 public:
81
  /**
82
   * @param pnm The proof node manager we are using
83
   * @param cb The callback to apply to each node
84
   * @param mergeSubproofs Whether to automatically merge subproofs within
85
   * the same SCOPE that prove the same fact.
86
   * @param autoSym Whether intermediate CDProof objects passed to updater
87
   * callbacks automatically introduce SYMM steps.
88
   */
89
  ProofNodeUpdater(ProofNodeManager* pnm,
90
                   ProofNodeUpdaterCallback& cb,
91
                   bool mergeSubproofs = false,
92
                   bool autoSym = true);
93
  /**
94
   * Post-process, which performs the main post-processing technique described
95
   * above.
96
   */
97
  void process(std::shared_ptr<ProofNode> pf);
98
99
  /**
100
   * Set free assumptions to freeAssumps. This indicates that we expect
101
   * the proof we are processing to have free assumptions that are in
102
   * freeAssumps. This enables checking when this is violated, which is
103
   * expensive in general. It is not recommended that this method is called
104
   * by default.
105
   */
106
  void setDebugFreeAssumptions(const std::vector<Node>& freeAssumps);
107
108
 private:
109
  /** The proof node manager */
110
  ProofNodeManager* d_pnm;
111
  /** The callback */
112
  ProofNodeUpdaterCallback& d_cb;
113
  /**
114
   * Post-process, which performs the main post-processing technique described
115
   * above.
116
   *
117
   * @param pf The proof to process
118
   * @param fa The assumptions of the scope that fa is a subproof of with
119
   * respect to the original proof. For example, if (SCOPE P :args (A B)), we
120
   * may call this method on P with fa = { A, B }.
121
   * @param traversing The list of proof nodes we are currently traversing
122
   * beneath. This is used for checking for cycles in the overall proof.
123
   */
124
  void processInternal(std::shared_ptr<ProofNode> pf,
125
                       const std::vector<Node>& fa,
126
                       std::vector<std::shared_ptr<ProofNode>>& traversing);
127
  /**
128
   * Update proof node cur based on the callback. This modifies curr using
129
   * ProofNodeManager::updateNode based on the proof node constructed to
130
   * replace it by the callback. Return true if cur was updated. If
131
   * continueUpdate is updated to false, then cur is not updated further
132
   * and its children are not traversed.
133
   */
134
  bool runUpdate(std::shared_ptr<ProofNode> cur,
135
                 const std::vector<Node>& fa,
136
                 bool& continueUpdate);
137
  /**
138
   * Finalize the node cur. This is called at the moment that it is established
139
   * that cur will appear in the final proof. We do any final debug checking
140
   * and add it to the results cache resCache if we are merging subproofs.
141
   */
142
  void runFinalize(std::shared_ptr<ProofNode> cur,
143
                   const std::vector<Node>& fa,
144
                   std::map<Node, std::shared_ptr<ProofNode>>& resCache);
145
  /** Are we debugging free assumptions? */
146
  bool d_debugFreeAssumps;
147
  /** The initial free assumptions */
148
  std::vector<Node> d_freeAssumps;
149
  /** Whether we are merging subproofs */
150
  bool d_mergeSubproofs;
151
  /**
152
   * Whether intermediate CDProof objects passed to updater callbacks
153
   * automatically introduce SYMM steps.
154
   */
155
  bool d_autoSym;
156
};
157
158
}  // namespace CVC4
159
160
#endif