Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/smt/preprocess_proof_generator.cpp	Lines:	108	116	93.1 %
Date:	2021-08-01	Branches:	243	554	43.9 %


/******************************************************************************
 * 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	7512	PreprocessProofGenerator::PreprocessProofGenerator(ProofNodeManager* pnm,
31		context::Context* c,
32		std::string name,
33		PfRule ra,
34	7512	PfRule rpp)
35		: d_pnm(pnm),
36	7512	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	15024	d_rpp(rpp)
43		{
44	7512	}
45
46	37953	void PreprocessProofGenerator::notifyInput(Node n)
47		{
48	37953	notifyNewAssert(n, &d_inputPf);
49	37953	}
50
51	86333	void PreprocessProofGenerator::notifyNewAssert(Node n, ProofGenerator* pg)
52		{
53	86333	if (n.isConst() && n.getConst<bool>())
54		{
55		// ignore true assertions
56	5476	return;
57		}
58	161714	Trace("smt-proof-pp-debug")
59	161714	<< "PreprocessProofGenerator::notifyNewAssert: " << identify() << " " << n
60	80857	<< " from " << (pg == nullptr ? "null" : pg->identify()) << std::endl;
61	80857	if (d_src.find(n) == d_src.end())
62		{
63		// if no proof generator provided for (non-true) assertion
64	78212	if (pg == nullptr)
65		{
66	1514	checkEagerPedantic(d_ra);
67		}
68	78212	d_src[n] = TrustNode::mkTrustLemma(n, pg);
69		}
70		else
71		{
72	2645	Trace("smt-proof-pp-debug") << "...already proven" << std::endl;
73		}
74		}
75
76	28282	void PreprocessProofGenerator::notifyNewTrustedAssert(TrustNode tn)
77		{
78	28282	notifyNewAssert(tn.getProven(), tn.getGenerator());
79	28282	}
80
81	32930	void PreprocessProofGenerator::notifyPreprocessed(Node n,
82		Node np,
83		ProofGenerator* pg)
84		{
85		// only do anything if indeed it rewrote
86	32930	if (n == np)
87		{
88		return;
89		}
90		// call the trusted version
91	32930	notifyTrustedPreprocessed(TrustNode::mkTrustRewrite(n, np, pg));
92		}
93
94	48125	void PreprocessProofGenerator::notifyTrustedPreprocessed(TrustNode tnp)
95		{
96	48125	if (tnp.isNull())
97		{
98		// no rewrite, nothing to do
99		return;
100		}
101	48125	Assert(tnp.getKind() == TrustNodeKind::REWRITE);
102	96250	Node np = tnp.getNode();
103	96250	Trace("smt-proof-pp-debug")
104	48125	<< "PreprocessProofGenerator::notifyPreprocessed: " << tnp << std::endl;
105	48125	if (d_src.find(np) == d_src.end())
106		{
107	40802	if (tnp.getGenerator() == nullptr)
108		{
109	2753	checkEagerPedantic(d_rpp);
110		}
111	40802	d_src[np] = tnp;
112		}
113		else
114		{
115	7323	Trace("smt-proof-pp-debug") << "...already proven" << std::endl;
116		}
117		}
118
119	54067	std::shared_ptr<ProofNode> PreprocessProofGenerator::getProofFor(Node f)
120		{
121	108134	Trace("smt-pppg") << "PreprocessProofGenerator::getProofFor: (" << d_name
122	54067	<< ") input " << f << std::endl;
123	54067	NodeTrustNodeMap::iterator it = d_src.find(f);
124	54067	if (it == d_src.end())
125		{
126	34360	Trace("smt-pppg") << "...no proof for " << identify() << " " << f
127	17180	<< std::endl;
128		// could be an assumption, return nullptr
129	17180	return nullptr;
130		}
131		// make CDProof to construct the proof below
132	73774	CDProof cdp(d_pnm);
133
134	73774	Node curr = f;
135	73774	std::vector<Node> transChildren;
136	73774	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	49042	do
142		{
143	49042	success = false;
144	49042	if (it != d_src.end())
145		{
146	49042	Assert((*it).second.getNode() == curr);
147		// get the proven node
148	98084	Node proven = (*it).second.getProven();
149	49042	Assert(!proven.isNull());
150	49042	Trace("smt-pppg") << "...process proven " << proven << std::endl;
151	49042	if (processed.find(proven) != processed.end())
152		{
153		Unhandled() << "Cyclic steps in preprocess proof generator";
154		continue;
155		}
156	49042	processed.insert(proven);
157	49042	bool proofStepProcessed = false;
158
159		// if a generator for the step was provided, it is stored in the proof
160	98084	Trace("smt-pppg-debug")
161	49042	<< "...get provided proof " << (*it).second << std::endl;
162	98084	std::shared_ptr<ProofNode> pfr = (*it).second.toProofNode();
163	49042	if (pfr != nullptr)
164		{
165	48211	Trace("smt-pppg-debug") << "...add provided " << *pfr << std::endl;
166	48211	Assert(pfr->getResult() == proven);
167	48211	cdp.addProof(pfr);
168	48211	proofStepProcessed = true;
169		}
170
171	49042	Trace("smt-pppg-debug") << "...update" << std::endl;
172	49042	TrustNodeKind tnk = (*it).second.getKind();
173	49042	if (tnk == TrustNodeKind::REWRITE)
174		{
175	24310	Trace("smt-pppg-debug")
176	12155	<< "...rewritten from " << proven[0] << std::endl;
177	12155	Assert(proven.getKind() == kind::EQUAL);
178	12155	if (!proofStepProcessed)
179		{
180		// maybe its just a simple rewrite?
181	715	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	12155	transChildren.push_back(proven);
189		// continue with source
190	12155	curr = proven[0];
191	12155	success = true;
192		// find the next node
193	12155	Trace("smt-pppg") << "...continue " << curr << std::endl;
194	12155	it = d_src.find(curr);
195		}
196		else
197		{
198	36887	Trace("smt-pppg") << "...lemma" << std::endl;
199	36887	Assert(tnk == TrustNodeKind::LEMMA);
200		}
201
202	49042	if (!proofStepProcessed)
203		{
204	1648	Trace("smt-pppg-debug")
205	824	<< "...justify missing step with "
206	824	<< (tnk == TrustNodeKind::LEMMA ? d_ra : d_rpp) << std::endl;
207		// add trusted step, the rule depends on the kind of trust node
208	1648	cdp.addStep(
209	824	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	36887	if (!CDProof::isSame(f, curr))
217		{
218	20636	Node fullRewrite = curr.eqNode(f);
219	10318	if (transChildren.size() >= 2)
220		{
221	1159	Trace("smt-pppg") << "...apply trans to get " << fullRewrite << std::endl;
222	1159	std::reverse(transChildren.begin(), transChildren.end());
223	1159	cdp.addStep(fullRewrite, PfRule::TRANS, transChildren, {});
224		}
225	10318	Trace("smt-pppg") << "...eq_resolve to prove" << std::endl;
226		// prove f
227	10318	cdp.addStep(f, PfRule::EQ_RESOLVE, {curr, fullRewrite}, {});
228	10318	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	36887	return cdp.getProofFor(f);
241		}
242
243	3756	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	143338	std::string PreprocessProofGenerator::identify() const { return d_name; }
251
252	4267	void PreprocessProofGenerator::checkEagerPedantic(PfRule r)
253		{
254	4267	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	4267	}
267
268		} // namespace smt
269	29280	} // namespace cvc5