Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/smt/preprocess_proof_generator.cpp	Lines:	110	118	93.2 %
Date:	2021-11-07	Branches:	245	552	44.4 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Gereon Kremer
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
 * in the top-level source directory and their institutional affiliations.
 * All rights reserved.  See the file COPYING in the top-level source
 * directory for licensing information.
 * ****************************************************************************
 *
 * The implementation of the module for proofs for preprocessing in an
 * SMT engine.
 */

#include "smt/preprocess_proof_generator.h"

#include <sstream>

#include "options/proof_options.h"
#include "proof/method_id.h"
#include "proof/proof.h"
#include "proof/proof_checker.h"
#include "proof/proof_node.h"
#include "theory/quantifiers/extended_rewrite.h"
#include "theory/rewriter.h"

namespace cvc5 {
namespace smt {

PreprocessProofGenerator::PreprocessProofGenerator(ProofNodeManager* pnm,
                                                   context::Context* c,
                                                   std::string name,
                                                   PfRule ra,
                                                   PfRule rpp)
    : d_pnm(pnm),
      d_ctx(c ? c : &d_context),
      d_src(d_ctx),
      d_helperProofs(pnm, d_ctx),
      d_inputPf(pnm, c, "InputProof"),
      d_name(name),
      d_ra(ra),
      d_rpp(rpp)
{
}

void PreprocessProofGenerator::notifyInput(Node n)
{
  notifyNewAssert(n, &d_inputPf);
}

void PreprocessProofGenerator::notifyNewAssert(Node n, ProofGenerator* pg)
{
  if (n.isConst() && n.getConst<bool>())
  {
    // ignore true assertions
    return;
  }
  Trace("smt-proof-pp-debug")
      << "PreprocessProofGenerator::notifyNewAssert: " << identify() << " " << n
      << " from " << (pg == nullptr ? "null" : pg->identify()) << std::endl;
  if (d_src.find(n) == d_src.end())
  {
    // if no proof generator provided for (non-true) assertion
    if (pg == nullptr)
    {
      checkEagerPedantic(d_ra);
    }
    d_src[n] = TrustNode::mkTrustLemma(n, pg);
  }
  else
  {
    Trace("smt-proof-pp-debug") << "...already proven" << std::endl;
  }
}

void PreprocessProofGenerator::notifyNewTrustedAssert(TrustNode tn)
{
  notifyNewAssert(tn.getProven(), tn.getGenerator());
}

void PreprocessProofGenerator::notifyPreprocessed(Node n,
                                                  Node np,
                                                  ProofGenerator* pg)
{
  // only do anything if indeed it rewrote
  if (n == np)
  {
    return;
  }
  // call the trusted version
  notifyTrustedPreprocessed(TrustNode::mkTrustRewrite(n, np, pg));
}

void PreprocessProofGenerator::notifyTrustedPreprocessed(TrustNode tnp)
{
  if (tnp.isNull())
  {
    // no rewrite, nothing to do
    return;
  }
  Assert(tnp.getKind() == TrustNodeKind::REWRITE);
  Node np = tnp.getNode();
  Trace("smt-proof-pp-debug")
      << "PreprocessProofGenerator::notifyPreprocessed: " << tnp << std::endl;
  if (d_src.find(np) == d_src.end())
  {
    if (tnp.getGenerator() == nullptr)
    {
      checkEagerPedantic(d_rpp);
    }
    d_src[np] = tnp;
  }
  else
  {
    Trace("smt-proof-pp-debug") << "...already proven" << std::endl;
  }
}

std::shared_ptr<ProofNode> PreprocessProofGenerator::getProofFor(Node f)
{
  Trace("smt-pppg") << "PreprocessProofGenerator::getProofFor: (" << d_name
                    << ") input " << f << std::endl;
  NodeTrustNodeMap::iterator it = d_src.find(f);
  if (it == d_src.end())
  {
    Trace("smt-pppg") << "...no proof for " << identify() << " " << f
                      << std::endl;
    // could be an assumption, return nullptr
    return nullptr;
  }
  // make CDProof to construct the proof below
  CDProof cdp(d_pnm);

  Node curr = f;
  std::vector<Node> transChildren;
  std::unordered_set<Node> processed;
  bool success;
  // we connect the proof of f to its source via the map d_src until we
  // discover that its source is a preprocessing lemma (a lemma stored in d_src)
  // or otherwise it is assumed to be an input assumption.
  do
  {
    success = false;
    if (it != d_src.end())
    {
      Assert((*it).second.getNode() == curr);
      // get the proven node
      Node proven = (*it).second.getProven();
      Assert(!proven.isNull());
      Trace("smt-pppg") << "...process proven " << proven << std::endl;
      if (processed.find(proven) != processed.end())
      {
        Unhandled() << "Cyclic steps in preprocess proof generator";
        continue;
      }
      processed.insert(proven);
      bool proofStepProcessed = false;

      // if a generator for the step was provided, it is stored in the proof
      Trace("smt-pppg-debug")
          << "...get provided proof " << (*it).second << std::endl;
      std::shared_ptr<ProofNode> pfr = (*it).second.toProofNode();
      if (pfr != nullptr)
      {
        Trace("smt-pppg-debug") << "...add provided " << *pfr << std::endl;
        Assert(pfr->getResult() == proven);
        cdp.addProof(pfr);
        proofStepProcessed = true;
      }

      Trace("smt-pppg-debug") << "...update" << std::endl;
      TrustNodeKind tnk = (*it).second.getKind();
      if (tnk == TrustNodeKind::REWRITE)
      {
        Trace("smt-pppg-debug")
            << "...rewritten from " << proven[0] << std::endl;
        Assert(proven.getKind() == kind::EQUAL);
        if (!proofStepProcessed)
        {
          // maybe its just an (extended) rewrite?
          Node pr = theory::Rewriter::callExtendedRewrite(proven[0]);
          if (proven[1] == pr)
          {
            Node idr = mkMethodId(MethodId::RW_EXT_REWRITE);
            Trace("smt-pppg-debug") << "...add simple rewrite" << std::endl;
            cdp.addStep(proven, PfRule::REWRITE, {}, {proven[0], idr});
            proofStepProcessed = true;
          }
        }
        transChildren.push_back(proven);
        // continue with source
        curr = proven[0];
        success = true;
        // find the next node
        Trace("smt-pppg") << "...continue " << curr << std::endl;
        it = d_src.find(curr);
      }
      else
      {
        Trace("smt-pppg") << "...lemma" << std::endl;
        Assert(tnk == TrustNodeKind::LEMMA);
      }

      if (!proofStepProcessed)
      {
        Trace("smt-pppg-debug")
            << "...justify missing step with "
            << (tnk == TrustNodeKind::LEMMA ? d_ra : d_rpp) << std::endl;
        // add trusted step, the rule depends on the kind of trust node
        cdp.addStep(
            proven, tnk == TrustNodeKind::LEMMA ? d_ra : d_rpp, {}, {proven});
      }
    }
  } while (success);

  // prove ( curr == f ), which is not necessary if they are the same
  // modulo symmetry.
  if (!CDProof::isSame(f, curr))
  {
    Node fullRewrite = curr.eqNode(f);
    if (transChildren.size() >= 2)
    {
      Trace("smt-pppg") << "...apply trans to get " << fullRewrite << std::endl;
      std::reverse(transChildren.begin(), transChildren.end());
      cdp.addStep(fullRewrite, PfRule::TRANS, transChildren, {});
    }
    Trace("smt-pppg") << "...eq_resolve to prove" << std::endl;
    // prove f
    cdp.addStep(f, PfRule::EQ_RESOLVE, {curr, fullRewrite}, {});
    Trace("smt-pppg") << "...finished" << std::endl;
  }

  // overall, proof is:
  //        --------- from proof generator       ---------- from proof generator
  //        F_1 = F_2          ...               F_{n-1} = F_n
  // ---?   -------------------------------------------------- TRANS
  // F_1    F_1 = F_n
  // ---------------- EQ_RESOLVE
  // F_n
  // Note F_1 may have been given a proof if it was not an input assumption.

  return cdp.getProofFor(f);
}

ProofNodeManager* PreprocessProofGenerator::getManager() { return d_pnm; }

LazyCDProof* PreprocessProofGenerator::allocateHelperProof()
{
  return d_helperProofs.allocateProof(nullptr, d_ctx);
}

std::string PreprocessProofGenerator::identify() const { return d_name; }

void PreprocessProofGenerator::checkEagerPedantic(PfRule r)
{
  if (options::proofCheck() == options::ProofCheckMode::EAGER)
  {
    // catch a pedantic failure now, which otherwise would not be
    // triggered since we are doing lazy proof generation
    ProofChecker* pc = d_pnm->getChecker();
    std::stringstream serr;
    if (pc->isPedanticFailure(r, serr))
    {
      Unhandled() << "PreprocessProofGenerator::checkEagerPedantic: "
                  << serr.str();
    }
  }
}

}  // namespace smt
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Gereon Kremer
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 implementation of the module for proofs for preprocessing in an
14		* SMT engine.
15		*/
16
17		#include "smt/preprocess_proof_generator.h"
18
19		#include <sstream>
20
21		#include "options/proof_options.h"
22		#include "proof/method_id.h"
23		#include "proof/proof.h"
24		#include "proof/proof_checker.h"
25		#include "proof/proof_node.h"
26		#include "theory/quantifiers/extended_rewrite.h"
27		#include "theory/rewriter.h"
28
29		namespace cvc5 {
30		namespace smt {
31
32	15994	PreprocessProofGenerator::PreprocessProofGenerator(ProofNodeManager* pnm,
33		context::Context* c,
34		std::string name,
35		PfRule ra,
36	15994	PfRule rpp)
37		: d_pnm(pnm),
38	15994	d_ctx(c ? c : &d_context),
39		d_src(d_ctx),
40		d_helperProofs(pnm, d_ctx),
41		d_inputPf(pnm, c, "InputProof"),
42		d_name(name),
43		d_ra(ra),
44	31988	d_rpp(rpp)
45		{
46	15994	}
47
48	43533	void PreprocessProofGenerator::notifyInput(Node n)
49		{
50	43533	notifyNewAssert(n, &d_inputPf);
51	43533	}
52
53	100900	void PreprocessProofGenerator::notifyNewAssert(Node n, ProofGenerator* pg)
54		{
55	100900	if (n.isConst() && n.getConst<bool>())
56		{
57		// ignore true assertions
58	9715	return;
59		}
60	182370	Trace("smt-proof-pp-debug")
61	182370	<< "PreprocessProofGenerator::notifyNewAssert: " << identify() << " " << n
62	91185	<< " from " << (pg == nullptr ? "null" : pg->identify()) << std::endl;
63	91185	if (d_src.find(n) == d_src.end())
64		{
65		// if no proof generator provided for (non-true) assertion
66	88165	if (pg == nullptr)
67		{
68	578	checkEagerPedantic(d_ra);
69		}
70	88165	d_src[n] = TrustNode::mkTrustLemma(n, pg);
71		}
72		else
73		{
74	3020	Trace("smt-proof-pp-debug") << "...already proven" << std::endl;
75		}
76		}
77
78	32040	void PreprocessProofGenerator::notifyNewTrustedAssert(TrustNode tn)
79		{
80	32040	notifyNewAssert(tn.getProven(), tn.getGenerator());
81	32040	}
82
83	38290	void PreprocessProofGenerator::notifyPreprocessed(Node n,
84		Node np,
85		ProofGenerator* pg)
86		{
87		// only do anything if indeed it rewrote
88	38290	if (n == np)
89		{
90		return;
91		}
92		// call the trusted version
93	38290	notifyTrustedPreprocessed(TrustNode::mkTrustRewrite(n, np, pg));
94		}
95
96	54146	void PreprocessProofGenerator::notifyTrustedPreprocessed(TrustNode tnp)
97		{
98	54146	if (tnp.isNull())
99		{
100		// no rewrite, nothing to do
101		return;
102		}
103	54146	Assert(tnp.getKind() == TrustNodeKind::REWRITE);
104	108292	Node np = tnp.getNode();
105	108292	Trace("smt-proof-pp-debug")
106	54146	<< "PreprocessProofGenerator::notifyPreprocessed: " << tnp << std::endl;
107	54146	if (d_src.find(np) == d_src.end())
108		{
109	45360	if (tnp.getGenerator() == nullptr)
110		{
111	2429	checkEagerPedantic(d_rpp);
112		}
113	45360	d_src[np] = tnp;
114		}
115		else
116		{
117	8786	Trace("smt-proof-pp-debug") << "...already proven" << std::endl;
118		}
119		}
120
121	69940	std::shared_ptr<ProofNode> PreprocessProofGenerator::getProofFor(Node f)
122		{
123	139880	Trace("smt-pppg") << "PreprocessProofGenerator::getProofFor: (" << d_name
124	69940	<< ") input " << f << std::endl;
125	69940	NodeTrustNodeMap::iterator it = d_src.find(f);
126	69940	if (it == d_src.end())
127		{
128	39396	Trace("smt-pppg") << "...no proof for " << identify() << " " << f
129	19698	<< std::endl;
130		// could be an assumption, return nullptr
131	19698	return nullptr;
132		}
133		// make CDProof to construct the proof below
134	100484	CDProof cdp(d_pnm);
135
136	100484	Node curr = f;
137	100484	std::vector<Node> transChildren;
138	100484	std::unordered_set<Node> processed;
139		bool success;
140		// we connect the proof of f to its source via the map d_src until we
141		// discover that its source is a preprocessing lemma (a lemma stored in d_src)
142		// or otherwise it is assumed to be an input assumption.
143	66503	do
144		{
145	66503	success = false;
146	66503	if (it != d_src.end())
147		{
148	66503	Assert((*it).second.getNode() == curr);
149		// get the proven node
150	133006	Node proven = (*it).second.getProven();
151	66503	Assert(!proven.isNull());
152	66503	Trace("smt-pppg") << "...process proven " << proven << std::endl;
153	66503	if (processed.find(proven) != processed.end())
154		{
155		Unhandled() << "Cyclic steps in preprocess proof generator";
156		continue;
157		}
158	66503	processed.insert(proven);
159	66503	bool proofStepProcessed = false;
160
161		// if a generator for the step was provided, it is stored in the proof
162	133006	Trace("smt-pppg-debug")
163	66503	<< "...get provided proof " << (*it).second << std::endl;
164	133006	std::shared_ptr<ProofNode> pfr = (*it).second.toProofNode();
165	66503	if (pfr != nullptr)
166		{
167	65555	Trace("smt-pppg-debug") << "...add provided " << *pfr << std::endl;
168	65555	Assert(pfr->getResult() == proven);
169	65555	cdp.addProof(pfr);
170	65555	proofStepProcessed = true;
171		}
172
173	66503	Trace("smt-pppg-debug") << "...update" << std::endl;
174	66503	TrustNodeKind tnk = (*it).second.getKind();
175	66503	if (tnk == TrustNodeKind::REWRITE)
176		{
177	32522	Trace("smt-pppg-debug")
178	16261	<< "...rewritten from " << proven[0] << std::endl;
179	16261	Assert(proven.getKind() == kind::EQUAL);
180	16261	if (!proofStepProcessed)
181		{
182		// maybe its just an (extended) rewrite?
183	1562	Node pr = theory::Rewriter::callExtendedRewrite(proven[0]);
184	781	if (proven[1] == pr)
185		{
186	16	Node idr = mkMethodId(MethodId::RW_EXT_REWRITE);
187	8	Trace("smt-pppg-debug") << "...add simple rewrite" << std::endl;
188	8	cdp.addStep(proven, PfRule::REWRITE, {}, {proven[0], idr});
189	8	proofStepProcessed = true;
190		}
191		}
192	16261	transChildren.push_back(proven);
193		// continue with source
194	16261	curr = proven[0];
195	16261	success = true;
196		// find the next node
197	16261	Trace("smt-pppg") << "...continue " << curr << std::endl;
198	16261	it = d_src.find(curr);
199		}
200		else
201		{
202	50242	Trace("smt-pppg") << "...lemma" << std::endl;
203	50242	Assert(tnk == TrustNodeKind::LEMMA);
204		}
205
206	66503	if (!proofStepProcessed)
207		{
208	1880	Trace("smt-pppg-debug")
209	940	<< "...justify missing step with "
210	940	<< (tnk == TrustNodeKind::LEMMA ? d_ra : d_rpp) << std::endl;
211		// add trusted step, the rule depends on the kind of trust node
212	1880	cdp.addStep(
213	940	proven, tnk == TrustNodeKind::LEMMA ? d_ra : d_rpp, {}, {proven});
214		}
215		}
216		} while (success);
217
218		// prove ( curr == f ), which is not necessary if they are the same
219		// modulo symmetry.
220	50242	if (!CDProof::isSame(f, curr))
221		{
222	27444	Node fullRewrite = curr.eqNode(f);
223	13722	if (transChildren.size() >= 2)
224		{
225	1822	Trace("smt-pppg") << "...apply trans to get " << fullRewrite << std::endl;
226	1822	std::reverse(transChildren.begin(), transChildren.end());
227	1822	cdp.addStep(fullRewrite, PfRule::TRANS, transChildren, {});
228		}
229	13722	Trace("smt-pppg") << "...eq_resolve to prove" << std::endl;
230		// prove f
231	13722	cdp.addStep(f, PfRule::EQ_RESOLVE, {curr, fullRewrite}, {});
232	13722	Trace("smt-pppg") << "...finished" << std::endl;
233		}
234
235		// overall, proof is:
236		// --------- from proof generator ---------- from proof generator
237		// F_1 = F_2 ... F_{n-1} = F_n
238		// ---? -------------------------------------------------- TRANS
239		// F_1 F_1 = F_n
240		// ---------------- EQ_RESOLVE
241		// F_n
242		// Note F_1 may have been given a proof if it was not an input assumption.
243
244	50242	return cdp.getProofFor(f);
245		}
246
247	7989	ProofNodeManager* PreprocessProofGenerator::getManager() { return d_pnm; }
248
249	413	LazyCDProof* PreprocessProofGenerator::allocateHelperProof()
250		{
251	413	return d_helperProofs.allocateProof(nullptr, d_ctx);
252		}
253
254	163905	std::string PreprocessProofGenerator::identify() const { return d_name; }
255
256	3007	void PreprocessProofGenerator::checkEagerPedantic(PfRule r)
257		{
258	3007	if (options::proofCheck() == options::ProofCheckMode::EAGER)
259		{
260		// catch a pedantic failure now, which otherwise would not be
261		// triggered since we are doing lazy proof generation
262		ProofChecker* pc = d_pnm->getChecker();
263		std::stringstream serr;
264		if (pc->isPedanticFailure(r, serr))
265		{
266		Unhandled() << "PreprocessProofGenerator::checkEagerPedantic: "
267		<< serr.str();
268		}
269		}
270	3007	}
271
272		} // namespace smt
273	31137	} // namespace cvc5