Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/proof/theory_proof_step_buffer.cpp	Lines:	81	100	81.0 %
Date:	2021-08-15	Branches:	140	340	41.2 %


/******************************************************************************
 * Top contributors (to current version):
 *   Haniel Barbosa, Andrew Reynolds, Aina Niemetz
 *
 * 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 theory proof step buffer utility.
 */

#include "proof/theory_proof_step_buffer.h"

#include "proof/proof.h"

using namespace cvc5::kind;

namespace cvc5 {

TheoryProofStepBuffer::TheoryProofStepBuffer(ProofChecker* pc)
    : ProofStepBuffer(pc)
{
}

bool TheoryProofStepBuffer::applyEqIntro(Node src,
                                         Node tgt,
                                         const std::vector<Node>& exp,
                                         MethodId ids,
                                         MethodId ida,
                                         MethodId idr)
{
  std::vector<Node> args;
  args.push_back(src);
  addMethodIds(args, ids, ida, idr);
  Node res = tryStep(PfRule::MACRO_SR_EQ_INTRO, exp, args);
  if (res.isNull())
  {
    // failed to apply
    return false;
  }
  // should have concluded the expected equality
  Node expected = src.eqNode(tgt);
  if (res != expected)
  {
    // did not provide the correct target
    popStep();
    return false;
  }
  // successfully proved src == tgt.
  return true;
}

bool TheoryProofStepBuffer::applyPredTransform(Node src,
                                               Node tgt,
                                               const std::vector<Node>& exp,
                                               MethodId ids,
                                               MethodId ida,
                                               MethodId idr)
{
  // symmetric equalities
  if (CDProof::isSame(src, tgt))
  {
    return true;
  }
  std::vector<Node> children;
  children.push_back(src);
  std::vector<Node> args;
  // try to prove that tgt rewrites to src
  children.insert(children.end(), exp.begin(), exp.end());
  args.push_back(tgt);
  addMethodIds(args, ids, ida, idr);
  Node res = tryStep(PfRule::MACRO_SR_PRED_TRANSFORM, children, args);
  if (res.isNull())
  {
    // failed to apply
    return false;
  }
  // should definitely have concluded tgt
  Assert(res == tgt);
  return true;
}

bool TheoryProofStepBuffer::applyPredIntro(Node tgt,
                                           const std::vector<Node>& exp,
                                           MethodId ids,
                                           MethodId ida,
                                           MethodId idr)
{
  std::vector<Node> args;
  args.push_back(tgt);
  addMethodIds(args, ids, ida, idr);
  Node res = tryStep(PfRule::MACRO_SR_PRED_INTRO, exp, args);
  if (res.isNull())
  {
    return false;
  }
  Assert(res == tgt);
  return true;
}

Node TheoryProofStepBuffer::applyPredElim(Node src,
                                          const std::vector<Node>& exp,
                                          MethodId ids,
                                          MethodId ida,
                                          MethodId idr)
{
  std::vector<Node> children;
  children.push_back(src);
  children.insert(children.end(), exp.begin(), exp.end());
  std::vector<Node> args;
  addMethodIds(args, ids, ida, idr);
  Node srcRew = tryStep(PfRule::MACRO_SR_PRED_ELIM, children, args);
  if (CDProof::isSame(src, srcRew))
  {
    popStep();
  }
  return srcRew;
}

Node TheoryProofStepBuffer::factorReorderElimDoubleNeg(Node n)
{
  if (n.getKind() != kind::OR)
  {
    return elimDoubleNegLit(n);
  }
  NodeManager* nm = NodeManager::currentNM();
  std::vector<Node> children{n.begin(), n.end()};
  std::vector<Node> childrenEqs;
  // eliminate double neg for each lit. Do it first because it may expose
  // duplicates
  bool hasDoubleNeg = false;
  for (unsigned i = 0; i < children.size(); ++i)
  {
    if (children[i].getKind() == kind::NOT
        && children[i][0].getKind() == kind::NOT)
    {
      hasDoubleNeg = true;
      childrenEqs.push_back(children[i].eqNode(children[i][0][0]));
      addStep(PfRule::MACRO_SR_PRED_INTRO,
              {},
              {childrenEqs.back()},
              childrenEqs.back());
      // update child
      children[i] = children[i][0][0];
    }
    else
    {
      childrenEqs.push_back(children[i].eqNode(children[i]));
      addStep(PfRule::REFL, {}, {children[i]}, childrenEqs.back());
    }
  }
  if (hasDoubleNeg)
  {
    Node oldn = n;
    n = nm->mkNode(kind::OR, children);
    // Create a congruence step to justify replacement of each doubly negated
    // literal. This is done to avoid having to use MACRO_SR_PRED_TRANSFORM
    // from the old clause to the new one, which, under the standard rewriter,
    // may not hold. An example is
    //
    //   ---------------------------------------------------------------------
    //   (or (or (not x2) x1 x2) (not (not x2))) = (or (or (not x2) x1 x2) x2)
    //
    // which fails due to factoring not happening after flattening.
    //
    // Using congruence only the
    //
    //  ------------------ MACRO_SR_PRED_INTRO
    //  (not (not t)) = t
    //
    // steps are added, which, since double negation is eliminated in a
    // pre-rewrite in the Boolean rewriter, will always hold under the
    // standard rewriter.
    Node congEq = oldn.eqNode(n);
    addStep(PfRule::CONG,
            childrenEqs,
            {ProofRuleChecker::mkKindNode(kind::OR)},
            congEq);
    // add an equality resolution step to derive normalize clause
    addStep(PfRule::EQ_RESOLVE, {oldn, congEq}, {}, n);
  }
  children.clear();
  // remove duplicates while keeping the order of children
  std::unordered_set<TNode> clauseSet;
  unsigned size = n.getNumChildren();
  for (unsigned i = 0; i < size; ++i)
  {
    if (clauseSet.count(n[i]))
    {
      continue;
    }
    children.push_back(n[i]);
    clauseSet.insert(n[i]);
  }
  // if factoring changed
  if (children.size() < size)
  {
    Node factored = children.empty()
                        ? nm->mkConst<bool>(false)
                        : children.size() == 1 ? children[0]
                                               : nm->mkNode(kind::OR, children);
    // don't overwrite what already has a proof step to avoid cycles
    addStep(PfRule::FACTORING, {n}, {}, factored);
    n = factored;
  }
  // nothing to order
  if (children.size() < 2)
  {
    return n;
  }
  // order
  std::sort(children.begin(), children.end());
  Node ordered = nm->mkNode(kind::OR, children);
  // if ordering changed
  if (ordered != n)
  {
    // don't overwrite what already has a proof step to avoid cycles
    addStep(PfRule::REORDERING, {n}, {ordered}, ordered);
  }
  return ordered;
}

Node TheoryProofStepBuffer::elimDoubleNegLit(Node n)
{
  // eliminate double neg
  if (n.getKind() == kind::NOT && n[0].getKind() == kind::NOT)
  {
    addStep(PfRule::NOT_NOT_ELIM, {n}, {}, n[0][0]);
    return n[0][0];
  }
  return n;
}

}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Haniel Barbosa, Andrew Reynolds, Aina Niemetz
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 theory proof step buffer utility.
14		*/
15
16		#include "proof/theory_proof_step_buffer.h"
17
18		#include "proof/proof.h"
19
20		using namespace cvc5::kind;
21
22		namespace cvc5 {
23
24	11521	TheoryProofStepBuffer::TheoryProofStepBuffer(ProofChecker* pc)
25	11521	: ProofStepBuffer(pc)
26		{
27	11521	}
28
29	11775	bool TheoryProofStepBuffer::applyEqIntro(Node src,
30		Node tgt,
31		const std::vector<Node>& exp,
32		MethodId ids,
33		MethodId ida,
34		MethodId idr)
35		{
36	23550	std::vector<Node> args;
37	11775	args.push_back(src);
38	11775	addMethodIds(args, ids, ida, idr);
39	23550	Node res = tryStep(PfRule::MACRO_SR_EQ_INTRO, exp, args);
40	11775	if (res.isNull())
41		{
42		// failed to apply
43		return false;
44		}
45		// should have concluded the expected equality
46	23550	Node expected = src.eqNode(tgt);
47	11775	if (res != expected)
48		{
49		// did not provide the correct target
50		popStep();
51		return false;
52		}
53		// successfully proved src == tgt.
54	11775	return true;
55		}
56
57	3049	bool TheoryProofStepBuffer::applyPredTransform(Node src,
58		Node tgt,
59		const std::vector<Node>& exp,
60		MethodId ids,
61		MethodId ida,
62		MethodId idr)
63		{
64		// symmetric equalities
65	3049	if (CDProof::isSame(src, tgt))
66		{
67	818	return true;
68		}
69	4462	std::vector<Node> children;
70	2231	children.push_back(src);
71	4462	std::vector<Node> args;
72		// try to prove that tgt rewrites to src
73	2231	children.insert(children.end(), exp.begin(), exp.end());
74	2231	args.push_back(tgt);
75	2231	addMethodIds(args, ids, ida, idr);
76	4462	Node res = tryStep(PfRule::MACRO_SR_PRED_TRANSFORM, children, args);
77	2231	if (res.isNull())
78		{
79		// failed to apply
80	256	return false;
81		}
82		// should definitely have concluded tgt
83	1975	Assert(res == tgt);
84	1975	return true;
85		}
86
87		bool TheoryProofStepBuffer::applyPredIntro(Node tgt,
88		const std::vector<Node>& exp,
89		MethodId ids,
90		MethodId ida,
91		MethodId idr)
92		{
93		std::vector<Node> args;
94		args.push_back(tgt);
95		addMethodIds(args, ids, ida, idr);
96		Node res = tryStep(PfRule::MACRO_SR_PRED_INTRO, exp, args);
97		if (res.isNull())
98		{
99		return false;
100		}
101		Assert(res == tgt);
102		return true;
103		}
104
105	154	Node TheoryProofStepBuffer::applyPredElim(Node src,
106		const std::vector<Node>& exp,
107		MethodId ids,
108		MethodId ida,
109		MethodId idr)
110		{
111	308	std::vector<Node> children;
112	154	children.push_back(src);
113	154	children.insert(children.end(), exp.begin(), exp.end());
114	308	std::vector<Node> args;
115	154	addMethodIds(args, ids, ida, idr);
116	154	Node srcRew = tryStep(PfRule::MACRO_SR_PRED_ELIM, children, args);
117	154	if (CDProof::isSame(src, srcRew))
118		{
119	82	popStep();
120		}
121	308	return srcRew;
122		}
123
124	705023	Node TheoryProofStepBuffer::factorReorderElimDoubleNeg(Node n)
125		{
126	705023	if (n.getKind() != kind::OR)
127		{
128		return elimDoubleNegLit(n);
129		}
130	705023	NodeManager* nm = NodeManager::currentNM();
131	1410046	std::vector<Node> children{n.begin(), n.end()};
132	1410046	std::vector<Node> childrenEqs;
133		// eliminate double neg for each lit. Do it first because it may expose
134		// duplicates
135	705023	bool hasDoubleNeg = false;
136	2853114	for (unsigned i = 0; i < children.size(); ++i)
137		{
138	4296182	if (children[i].getKind() == kind::NOT
139	4296182	&& children[i][0].getKind() == kind::NOT)
140		{
141	206710	hasDoubleNeg = true;
142	206710	childrenEqs.push_back(children[i].eqNode(children[i][0][0]));
143	826840	addStep(PfRule::MACRO_SR_PRED_INTRO,
144		{},
145	206710	{childrenEqs.back()},
146	413420	childrenEqs.back());
147		// update child
148	206710	children[i] = children[i][0][0];
149		}
150		else
151		{
152	1941381	childrenEqs.push_back(children[i].eqNode(children[i]));
153	1941381	addStep(PfRule::REFL, {}, {children[i]}, childrenEqs.back());
154		}
155		}
156	705023	if (hasDoubleNeg)
157		{
158	134764	Node oldn = n;
159	67382	n = nm->mkNode(kind::OR, children);
160		// Create a congruence step to justify replacement of each doubly negated
161		// literal. This is done to avoid having to use MACRO_SR_PRED_TRANSFORM
162		// from the old clause to the new one, which, under the standard rewriter,
163		// may not hold. An example is
164		//
165		// ---------------------------------------------------------------------
166		// (or (or (not x2) x1 x2) (not (not x2))) = (or (or (not x2) x1 x2) x2)
167		//
168		// which fails due to factoring not happening after flattening.
169		//
170		// Using congruence only the
171		//
172		// ------------------ MACRO_SR_PRED_INTRO
173		// (not (not t)) = t
174		//
175		// steps are added, which, since double negation is eliminated in a
176		// pre-rewrite in the Boolean rewriter, will always hold under the
177		// standard rewriter.
178	134764	Node congEq = oldn.eqNode(n);
179	134764	addStep(PfRule::CONG,
180		childrenEqs,
181		{ProofRuleChecker::mkKindNode(kind::OR)},
182	67382	congEq);
183		// add an equality resolution step to derive normalize clause
184	67382	addStep(PfRule::EQ_RESOLVE, {oldn, congEq}, {}, n);
185		}
186	705023	children.clear();
187		// remove duplicates while keeping the order of children
188	1410046	std::unordered_set<TNode> clauseSet;
189	705023	unsigned size = n.getNumChildren();
190	2853114	for (unsigned i = 0; i < size; ++i)
191		{
192	2148091	if (clauseSet.count(n[i]))
193		{
194	699	continue;
195		}
196	2147392	children.push_back(n[i]);
197	2147392	clauseSet.insert(n[i]);
198		}
199		// if factoring changed
200	705023	if (children.size() < size)
201		{
202	541	Node factored = children.empty()
203		? nm->mkConst<bool>(false)
204	541	: children.size() == 1 ? children[0]
205	1623	: nm->mkNode(kind::OR, children);
206		// don't overwrite what already has a proof step to avoid cycles
207	541	addStep(PfRule::FACTORING, {n}, {}, factored);
208	541	n = factored;
209		}
210		// nothing to order
211	705023	if (children.size() < 2)
212		{
213		return n;
214		}
215		// order
216	705023	std::sort(children.begin(), children.end());
217	1410046	Node ordered = nm->mkNode(kind::OR, children);
218		// if ordering changed
219	705023	if (ordered != n)
220		{
221		// don't overwrite what already has a proof step to avoid cycles
222	587793	addStep(PfRule::REORDERING, {n}, {ordered}, ordered);
223		}
224	705023	return ordered;
225		}
226
227		Node TheoryProofStepBuffer::elimDoubleNegLit(Node n)
228		{
229		// eliminate double neg
230		if (n.getKind() == kind::NOT && n[0].getKind() == kind::NOT)
231		{
232		addStep(PfRule::NOT_NOT_ELIM, {n}, {}, n[0][0]);
233		return n[0][0];
234		}
235		return n;
236		}
237
238	29337	} // namespace cvc5