Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/smt/preprocess_proof_generator.cpp	Lines:	108	116	93.1 %
Date:	2021-08-20	Branches:	243	548	44.3 %


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