Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/expr/lazy_proof_chain.cpp	Lines:	113	159	71.1 %
Date:	2021-05-24	Branches:	167	536	31.2 %


/******************************************************************************
 * Top contributors (to current version):
 *   Haniel Barbosa, 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.
 * ****************************************************************************
 *
 * Implementation of lazy proof utility.
 */

#include "expr/lazy_proof_chain.h"

#include "expr/proof.h"
#include "expr/proof_ensure_closed.h"
#include "expr/proof_node.h"
#include "expr/proof_node_algorithm.h"
#include "expr/proof_node_manager.h"
#include "options/proof_options.h"

namespace cvc5 {

LazyCDProofChain::LazyCDProofChain(ProofNodeManager* pnm,
                                   bool cyclic,
                                   context::Context* c,
                                   ProofGenerator* defGen,
                                   bool defRec)
    : d_manager(pnm),
      d_cyclic(cyclic),
      d_defRec(defRec),
      d_context(),
      d_gens(c ? c : &d_context),
      d_defGen(defGen)
{
}

LazyCDProofChain::~LazyCDProofChain() {}

const std::map<Node, std::shared_ptr<ProofNode>> LazyCDProofChain::getLinks()
    const
{
  std::map<Node, std::shared_ptr<ProofNode>> links;
  for (const std::pair<const Node, ProofGenerator* const>& link : d_gens)
  {
    Assert(link.second);
    std::shared_ptr<ProofNode> pfn = link.second->getProofFor(link.first);
    Assert(pfn);
    links[link.first] = pfn;
  }
  return links;
}

std::shared_ptr<ProofNode> LazyCDProofChain::getProofFor(Node fact)
{
  Trace("lazy-cdproofchain")
      << "LazyCDProofChain::getProofFor " << fact << "\n";
  // which facts have had proofs retrieved for. This is maintained to avoid
  // cycles. It also saves the proof node of the fact
  std::unordered_map<Node, std::shared_ptr<ProofNode>> toConnect;
  // leaves of proof node links in the chain, i.e. assumptions, yet to be
  // expanded
  std::unordered_map<Node, std::vector<std::shared_ptr<ProofNode>>>
      assumptionsToExpand;
  // invariant of the loop below, the first iteration notwithstanding:
  //   visit = domain(assumptionsToExpand) \ domain(toConnect)
  std::vector<Node> visit{fact};
  std::unordered_map<Node, bool> visited;
  Node cur;
  do
  {
    cur = visit.back();
    visit.pop_back();
    auto itVisited = visited.find(cur);
    // pre-traversal
    if (itVisited == visited.end())
    {
      Trace("lazy-cdproofchain")
          << "LazyCDProofChain::getProofFor: check " << cur << "\n";
      Assert(toConnect.find(cur) == toConnect.end());
      bool rec = true;
      ProofGenerator* pg = getGeneratorForInternal(cur, rec);
      if (!pg)
      {
        Trace("lazy-cdproofchain")
            << "LazyCDProofChain::getProofFor: nothing to do\n";
        // nothing to do for this fact, it'll be a leaf in the final proof
        // node, don't post-traverse.
        visited[cur] = true;
        continue;
      }
      Trace("lazy-cdproofchain")
          << "LazyCDProofChain::getProofFor: Call generator " << pg->identify()
          << " for chain link " << cur << "\n";
      std::shared_ptr<ProofNode> curPfn = pg->getProofFor(cur);
      if (curPfn == nullptr)
      {
        Trace("lazy-cdproofchain")
            << "LazyCDProofChain::getProofFor: No proof found, skip\n";
        visited[cur] = true;
        continue;
      }
      // map node whose proof node must be expanded to the respective poof node
      toConnect[cur] = curPfn;
      if (!rec)
      {
        // we don't want to recursively connect this proof
        visited[cur] = true;
        continue;
      }
      Trace("lazy-cdproofchain-debug")
          << "LazyCDProofChain::getProofFor: stored proof: " << *curPfn.get()
          << "\n";
      // retrieve free assumptions and their respective proof nodes
      std::map<Node, std::vector<std::shared_ptr<ProofNode>>> famap;
      expr::getFreeAssumptionsMap(curPfn, famap);
      if (Trace.isOn("lazy-cdproofchain"))
      {
        unsigned alreadyToVisit = 0;
        Trace("lazy-cdproofchain")
            << "LazyCDProofChain::getProofFor: " << famap.size()
            << " free assumptions:\n";
        for (auto fap : famap)
        {
          Trace("lazy-cdproofchain")
              << "LazyCDProofChain::getProofFor:  - " << fap.first << "\n";
          alreadyToVisit +=
              std::find(visit.begin(), visit.end(), fap.first) != visit.end()
                  ? 1
                  : 0;
        }
        Trace("lazy-cdproofchain")
            << "LazyCDProofChain::getProofFor: " << alreadyToVisit
            << " already to visit\n";
      }
      // mark for post-traversal if we are controlling cycles
      if (d_cyclic)
      {
        Trace("lazy-cdproofchain") << "LazyCDProofChain::getProofFor: marking "
                                   << cur << " for cycle check\n";
        visit.push_back(cur);
        visited[cur] = false;
      }
      else
      {
        visited[cur] = true;
      }
      // enqueue free assumptions to process
      for (const std::pair<const Node, std::vector<std::shared_ptr<ProofNode>>>&
               fap : famap)
      {
        // check cycles
        if (d_cyclic)
        {
          // cycles are assumptions being *currently* expanded and seen again,
          // i.e. in toConnect and not yet post-visited
          auto itToConnect = toConnect.find(fap.first);
          if (itToConnect != toConnect.end() && !visited[fap.first])
          {
            // Since we have a cycle with an assumption, this fact will be an
            // assumption in the final proof node produced by this
            // method. Thus we erase it as something to be connected, which
            // will keep it as an assumption.
            Trace("lazy-cdproofchain") << "LazyCDProofChain::getProofFor: "
                                          "removing cyclic assumption "
                                       << fap.first << " from expansion\n";
            continue;
          }
        }
        // We always add assumptions to visit so that their last seen occurrence
        // is expanded (rather than the first seen occurrence, if we were not
        // adding assumptions, say, in assumptionsToExpand). This is so because
        // in the case where we are checking cycles this is necessary (and
        // harmless when we are not). For example the cycle
        //
        //                 a2
        //                ...
        //               ----
        //                a1
        //               ...
        //             --------
        //   a0   a1    a2
        //       ...
        //  ---------------
        //       n
        //
        // in which a2 has a1 as an assumption, which has a2 an assumption,
        // would not be captured if we did not revisit a1, which is an
        // assumption of n and this already occur in assumptionsToExpand when
        // it shows up again as an assumption of a2.
        visit.push_back(fap.first);
        // add assumption proof nodes to be updated
        assumptionsToExpand[fap.first].insert(
            assumptionsToExpand[fap.first].end(),
            fap.second.begin(),
            fap.second.end());
      }
      if (d_cyclic)
      {
        Trace("lazy-cdproofchain") << push;
        Trace("lazy-cdproofchain-debug") << push;
      }
    }
    else if (!itVisited->second)
    {
      visited[cur] = true;
      Trace("lazy-cdproofchain") << pop;
      Trace("lazy-cdproofchain-debug") << pop;
      Trace("lazy-cdproofchain")
          << "LazyCDProofChain::getProofFor: post-visited " << cur << "\n";
    }
    else
    {
      Trace("lazy-cdproofchain")
          << "LazyCDProofChain::getProofFor: already fully processed " << cur
          << "\n";
    }
  } while (!visit.empty());
  // expand all assumptions marked to be connected
  for (const std::pair<const Node, std::shared_ptr<ProofNode>>& npfn :
       toConnect)
  {
    auto it = assumptionsToExpand.find(npfn.first);
    if (it == assumptionsToExpand.end())
    {
      Assert(npfn.first == fact);
      continue;
    }
    Assert(npfn.second);
    Trace("lazy-cdproofchain")
        << "LazyCDProofChain::getProofFor: expand assumption " << npfn.first
        << "\n";
    Trace("lazy-cdproofchain-debug")
        << "LazyCDProofChain::getProofFor: ...expand to " << *npfn.second.get()
        << "\n";
    // update each assumption proof node
    for (std::shared_ptr<ProofNode> pfn : it->second)
    {
      d_manager->updateNode(pfn.get(), npfn.second.get());
    }
  }
  // final proof of fact
  auto it = toConnect.find(fact);
  if (it == toConnect.end())
  {
    return nullptr;
  }
  return it->second;
}

void LazyCDProofChain::addLazyStep(Node expected, ProofGenerator* pg)
{
  Assert(pg != nullptr);
  Trace("lazy-cdproofchain") << "LazyCDProofChain::addLazyStep: " << expected
                             << " set to generator " << pg->identify() << "\n";
  // note this will replace the generator for expected, if any
  d_gens.insert(expected, pg);
}

void LazyCDProofChain::addLazyStep(Node expected,
                                   ProofGenerator* pg,
                                   const std::vector<Node>& assumptions,
                                   const char* ctx)
{
  Assert(pg != nullptr);
  Trace("lazy-cdproofchain") << "LazyCDProofChain::addLazyStep: " << expected
                             << " set to generator " << pg->identify() << "\n";
  // note this will rewrite the generator for expected, if any
  d_gens.insert(expected, pg);
  // check if chain is closed if options::proofEagerChecking() is on
  if (options::proofEagerChecking())
  {
    Trace("lazy-cdproofchain")
        << "LazyCDProofChain::addLazyStep: Checking closed proof...\n";
    std::shared_ptr<ProofNode> pfn = pg->getProofFor(expected);
    std::vector<Node> allowedLeaves{assumptions.begin(), assumptions.end()};
    // add all current links in the chain
    for (const std::pair<const Node, ProofGenerator* const>& link : d_gens)
    {
      allowedLeaves.push_back(link.first);
    }
    if (Trace.isOn("lazy-cdproofchain"))
    {
      Trace("lazy-cdproofchain") << "Checking relative to leaves...\n";
      for (const Node& n : allowedLeaves)
      {
        Trace("lazy-cdproofchain") << "  - " << n << "\n";
      }
      Trace("lazy-cdproofchain") << "\n";
    }
    pfnEnsureClosedWrt(pfn.get(), allowedLeaves, "lazy-cdproofchain", ctx);
  }
}

bool LazyCDProofChain::hasGenerator(Node fact) const
{
  return d_gens.find(fact) != d_gens.end();
}

ProofGenerator* LazyCDProofChain::getGeneratorFor(Node fact)
{
  bool rec = true;
  return getGeneratorForInternal(fact, rec);
}

ProofGenerator* LazyCDProofChain::getGeneratorForInternal(Node fact, bool& rec)
{
  auto it = d_gens.find(fact);
  if (it != d_gens.end())
  {
    return (*it).second;
  }
  // otherwise, if no explicit generators, we use the default one
  if (d_defGen != nullptr)
  {
    rec = d_defRec;
    return d_defGen;
  }
  return nullptr;
}

std::string LazyCDProofChain::identify() const { return "LazyCDProofChain"; }

}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Haniel Barbosa, 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		* Implementation of lazy proof utility.
14		*/
15
16		#include "expr/lazy_proof_chain.h"
17
18		#include "expr/proof.h"
19		#include "expr/proof_ensure_closed.h"
20		#include "expr/proof_node.h"
21		#include "expr/proof_node_algorithm.h"
22		#include "expr/proof_node_manager.h"
23		#include "options/proof_options.h"
24
25		namespace cvc5 {
26
27	10273	LazyCDProofChain::LazyCDProofChain(ProofNodeManager* pnm,
28		bool cyclic,
29		context::Context* c,
30		ProofGenerator* defGen,
31	10273	bool defRec)
32		: d_manager(pnm),
33		d_cyclic(cyclic),
34		d_defRec(defRec),
35		d_context(),
36		d_gens(c ? c : &d_context),
37	10273	d_defGen(defGen)
38		{
39	10273	}
40
41	17473	LazyCDProofChain::~LazyCDProofChain() {}
42
43		const std::map<Node, std::shared_ptr<ProofNode>> LazyCDProofChain::getLinks()
44		const
45		{
46		std::map<Node, std::shared_ptr<ProofNode>> links;
47		for (const std::pair<const Node, ProofGenerator* const>& link : d_gens)
48		{
49		Assert(link.second);
50		std::shared_ptr<ProofNode> pfn = link.second->getProofFor(link.first);
51		Assert(pfn);
52		links[link.first] = pfn;
53		}
54		return links;
55		}
56
57	32862	std::shared_ptr<ProofNode> LazyCDProofChain::getProofFor(Node fact)
58		{
59	65724	Trace("lazy-cdproofchain")
60	32862	<< "LazyCDProofChain::getProofFor " << fact << "\n";
61		// which facts have had proofs retrieved for. This is maintained to avoid
62		// cycles. It also saves the proof node of the fact
63	65724	std::unordered_map<Node, std::shared_ptr<ProofNode>> toConnect;
64		// leaves of proof node links in the chain, i.e. assumptions, yet to be
65		// expanded
66		std::unordered_map<Node, std::vector<std::shared_ptr<ProofNode>>>
67	65724	assumptionsToExpand;
68		// invariant of the loop below, the first iteration notwithstanding:
69		// visit = domain(assumptionsToExpand) \ domain(toConnect)
70	65724	std::vector<Node> visit{fact};
71	65724	std::unordered_map<Node, bool> visited;
72	65724	Node cur;
73	3208862	do
74		{
75	3241724	cur = visit.back();
76	3241724	visit.pop_back();
77	3241724	auto itVisited = visited.find(cur);
78		// pre-traversal
79	3241724	if (itVisited == visited.end())
80		{
81	804724	Trace("lazy-cdproofchain")
82	402362	<< "LazyCDProofChain::getProofFor: check " << cur << "\n";
83	402362	Assert(toConnect.find(cur) == toConnect.end());
84	402362	bool rec = true;
85	402362	ProofGenerator* pg = getGeneratorForInternal(cur, rec);
86	603328	if (!pg)
87		{
88	401932	Trace("lazy-cdproofchain")
89	200966	<< "LazyCDProofChain::getProofFor: nothing to do\n";
90		// nothing to do for this fact, it'll be a leaf in the final proof
91		// node, don't post-traverse.
92	200966	visited[cur] = true;
93	412582	continue;
94		}
95	402792	Trace("lazy-cdproofchain")
96	402792	<< "LazyCDProofChain::getProofFor: Call generator " << pg->identify()
97	201396	<< " for chain link " << cur << "\n";
98	392142	std::shared_ptr<ProofNode> curPfn = pg->getProofFor(cur);
99	204204	if (curPfn == nullptr)
100		{
101	5616	Trace("lazy-cdproofchain")
102	2808	<< "LazyCDProofChain::getProofFor: No proof found, skip\n";
103	2808	visited[cur] = true;
104	2808	continue;
105		}
106		// map node whose proof node must be expanded to the respective poof node
107	198588	toConnect[cur] = curPfn;
108	206430	if (!rec)
109		{
110		// we don't want to recursively connect this proof
111	7842	visited[cur] = true;
112	7842	continue;
113		}
114	381492	Trace("lazy-cdproofchain-debug")
115	190746	<< "LazyCDProofChain::getProofFor: stored proof: " << *curPfn.get()
116	190746	<< "\n";
117		// retrieve free assumptions and their respective proof nodes
118	381492	std::map<Node, std::vector<std::shared_ptr<ProofNode>>> famap;
119	190746	expr::getFreeAssumptionsMap(curPfn, famap);
120	190746	if (Trace.isOn("lazy-cdproofchain"))
121		{
122		unsigned alreadyToVisit = 0;
123		Trace("lazy-cdproofchain")
124		<< "LazyCDProofChain::getProofFor: " << famap.size()
125		<< " free assumptions:\n";
126		for (auto fap : famap)
127		{
128		Trace("lazy-cdproofchain")
129		<< "LazyCDProofChain::getProofFor: - " << fap.first << "\n";
130		alreadyToVisit +=
131		std::find(visit.begin(), visit.end(), fap.first) != visit.end()
132		? 1
133		: 0;
134		}
135		Trace("lazy-cdproofchain")
136		<< "LazyCDProofChain::getProofFor: " << alreadyToVisit
137		<< " already to visit\n";
138		}
139		// mark for post-traversal if we are controlling cycles
140	190746	if (d_cyclic)
141		{
142	381492	Trace("lazy-cdproofchain") << "LazyCDProofChain::getProofFor: marking "
143	190746	<< cur << " for cycle check\n";
144	190746	visit.push_back(cur);
145	190746	visited[cur] = false;
146		}
147		else
148		{
149		visited[cur] = true;
150		}
151		// enqueue free assumptions to process
152	3038941	for (const std::pair<const Node, std::vector<std::shared_ptr<ProofNode>>>&
153	190746	fap : famap)
154		{
155		// check cycles
156	3038941	if (d_cyclic)
157		{
158		// cycles are assumptions being currently expanded and seen again,
159		// i.e. in toConnect and not yet post-visited
160	3038941	auto itToConnect = toConnect.find(fap.first);
161	3059766	if (itToConnect != toConnect.end() && !visited[fap.first])
162		{
163		// Since we have a cycle with an assumption, this fact will be an
164		// assumption in the final proof node produced by this
165		// method. Thus we erase it as something to be connected, which
166		// will keep it as an assumption.
167	41650	Trace("lazy-cdproofchain") << "LazyCDProofChain::getProofFor: "
168	20825	"removing cyclic assumption "
169	20825	<< fap.first << " from expansion\n";
170	20825	continue;
171		}
172		}
173		// We always add assumptions to visit so that their last seen occurrence
174		// is expanded (rather than the first seen occurrence, if we were not
175		// adding assumptions, say, in assumptionsToExpand). This is so because
176		// in the case where we are checking cycles this is necessary (and
177		// harmless when we are not). For example the cycle
178		//
179		// a2
180		// ...
181		// ----
182		// a1
183		// ...
184		// --------
185		// a0 a1 a2
186		// ...
187		// ---------------
188		// n
189		//
190		// in which a2 has a1 as an assumption, which has a2 an assumption,
191		// would not be captured if we did not revisit a1, which is an
192		// assumption of n and this already occur in assumptionsToExpand when
193		// it shows up again as an assumption of a2.
194	3018116	visit.push_back(fap.first);
195		// add assumption proof nodes to be updated
196	6036232	assumptionsToExpand[fap.first].insert(
197	6036232	assumptionsToExpand[fap.first].end(),
198		fap.second.begin(),
199	9054348	fap.second.end());
200		}
201	190746	if (d_cyclic)
202		{
203	190746	Trace("lazy-cdproofchain") << push;
204	190746	Trace("lazy-cdproofchain-debug") << push;
205		}
206		}
207	2839362	else if (!itVisited->second)
208		{
209	190746	visited[cur] = true;
210	190746	Trace("lazy-cdproofchain") << pop;
211	190746	Trace("lazy-cdproofchain-debug") << pop;
212	381492	Trace("lazy-cdproofchain")
213	190746	<< "LazyCDProofChain::getProofFor: post-visited " << cur << "\n";
214		}
215		else
216		{
217	5297232	Trace("lazy-cdproofchain")
218	2648616	<< "LazyCDProofChain::getProofFor: already fully processed " << cur
219	2648616	<< "\n";
220		}
221	3241724	} while (!visit.empty());
222		// expand all assumptions marked to be connected
223	198588	for (const std::pair<const Node, std::shared_ptr<ProofNode>>& npfn :
224	32862	toConnect)
225		{
226	198588	auto it = assumptionsToExpand.find(npfn.first);
227	230640	if (it == assumptionsToExpand.end())
228		{
229	32052	Assert(npfn.first == fact);
230	32052	continue;
231		}
232	166536	Assert(npfn.second);
233	333072	Trace("lazy-cdproofchain")
234	166536	<< "LazyCDProofChain::getProofFor: expand assumption " << npfn.first
235	166536	<< "\n";
236	333072	Trace("lazy-cdproofchain-debug")
237	166536	<< "LazyCDProofChain::getProofFor: ...expand to " << *npfn.second.get()
238	166536	<< "\n";
239		// update each assumption proof node
240	736760	for (std::shared_ptr<ProofNode> pfn : it->second)
241		{
242	570224	d_manager->updateNode(pfn.get(), npfn.second.get());
243		}
244		}
245		// final proof of fact
246	32862	auto it = toConnect.find(fact);
247	32862	if (it == toConnect.end())
248		{
249	810	return nullptr;
250		}
251	32052	return it->second;
252		}
253
254	76025	void LazyCDProofChain::addLazyStep(Node expected, ProofGenerator* pg)
255		{
256	76025	Assert(pg != nullptr);
257	152050	Trace("lazy-cdproofchain") << "LazyCDProofChain::addLazyStep: " << expected
258	76025	<< " set to generator " << pg->identify() << "\n";
259		// note this will replace the generator for expected, if any
260	76025	d_gens.insert(expected, pg);
261	76025	}
262
263		void LazyCDProofChain::addLazyStep(Node expected,
264		ProofGenerator* pg,
265		const std::vector<Node>& assumptions,
266		const char* ctx)
267		{
268		Assert(pg != nullptr);
269		Trace("lazy-cdproofchain") << "LazyCDProofChain::addLazyStep: " << expected
270		<< " set to generator " << pg->identify() << "\n";
271		// note this will rewrite the generator for expected, if any
272		d_gens.insert(expected, pg);
273		// check if chain is closed if options::proofEagerChecking() is on
274		if (options::proofEagerChecking())
275		{
276		Trace("lazy-cdproofchain")
277		<< "LazyCDProofChain::addLazyStep: Checking closed proof...\n";
278		std::shared_ptr<ProofNode> pfn = pg->getProofFor(expected);
279		std::vector<Node> allowedLeaves{assumptions.begin(), assumptions.end()};
280		// add all current links in the chain
281		for (const std::pair<const Node, ProofGenerator* const>& link : d_gens)
282		{
283		allowedLeaves.push_back(link.first);
284		}
285		if (Trace.isOn("lazy-cdproofchain"))
286		{
287		Trace("lazy-cdproofchain") << "Checking relative to leaves...\n";
288		for (const Node& n : allowedLeaves)
289		{
290		Trace("lazy-cdproofchain") << " - " << n << "\n";
291		}
292		Trace("lazy-cdproofchain") << "\n";
293		}
294		pfnEnsureClosedWrt(pfn.get(), allowedLeaves, "lazy-cdproofchain", ctx);
295		}
296		}
297
298		bool LazyCDProofChain::hasGenerator(Node fact) const
299		{
300		return d_gens.find(fact) != d_gens.end();
301		}
302
303		ProofGenerator* LazyCDProofChain::getGeneratorFor(Node fact)
304		{
305		bool rec = true;
306		return getGeneratorForInternal(fact, rec);
307		}
308
309	402362	ProofGenerator* LazyCDProofChain::getGeneratorForInternal(Node fact, bool& rec)
310		{
311	402362	auto it = d_gens.find(fact);
312	402362	if (it != d_gens.end())
313		{
314	170816	return (*it).second;
315		}
316		// otherwise, if no explicit generators, we use the default one
317	231546	if (d_defGen != nullptr)
318		{
319	30580	rec = d_defRec;
320	30580	return d_defGen;
321		}
322	200966	return nullptr;
323		}
324
325	42674	std::string LazyCDProofChain::identify() const { return "LazyCDProofChain"; }
326
327	28191	} // namespace cvc5