Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/uf/proof_equality_engine.cpp	Lines:	205	262	78.2 %
Date:	2021-08-16	Branches:	462	1314	35.2 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Gereon Kremer, 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 the proof-producing equality engine.
 */

#include "theory/uf/proof_equality_engine.h"

#include "proof/lazy_proof_chain.h"
#include "proof/proof_node.h"
#include "proof/proof_node_manager.h"
#include "theory/rewriter.h"
#include "theory/uf/eq_proof.h"
#include "theory/uf/equality_engine.h"
#include "theory/uf/proof_checker.h"

using namespace cvc5::kind;

namespace cvc5 {
namespace theory {
namespace eq {

ProofEqEngine::ProofEqEngine(context::Context* c,
                             context::UserContext* u,
                             EqualityEngine& ee,
                             ProofNodeManager* pnm)
    : EagerProofGenerator(pnm, u, "pfee::" + ee.identify()),
      d_ee(ee),
      d_factPg(c, pnm),
      d_pnm(pnm),
      d_proof(pnm, nullptr, c, "pfee::LazyCDProof::" + ee.identify()),
      d_keep(c)
{
  NodeManager* nm = NodeManager::currentNM();
  d_true = nm->mkConst(true);
  d_false = nm->mkConst(false);
  AlwaysAssert(pnm != nullptr)
      << "Should not construct ProofEqEngine without proof node manager";
}

bool ProofEqEngine::assertFact(Node lit,
                               PfRule id,
                               const std::vector<Node>& exp,
                               const std::vector<Node>& args)
{
  Trace("pfee") << "pfee::assertFact " << lit << " " << id << ", exp = " << exp
                << ", args = " << args << std::endl;

  Node atom = lit.getKind() == NOT ? lit[0] : lit;
  bool polarity = lit.getKind() != NOT;
  // register the step in the proof
  if (holds(atom, polarity))
  {
    // we do not process this fact if it already holds
    return false;
  }
  // Buffer the step in the fact proof generator. We do this instead of
  // adding explict steps to the lazy proof d_proof since CDProof has
  // (at most) one proof for each formula. Thus, we "claim" only the
  // formula that is proved by this fact. Otherwise, aliasing may occur,
  // which leads to cyclic or bogus proofs.
  ProofStep ps;
  ps.d_rule = id;
  ps.d_children = exp;
  ps.d_args = args;
  d_factPg.addStep(lit, ps);
  // add lazy step to proof
  d_proof.addLazyStep(lit, &d_factPg);
  // second, assert it to the equality engine
  Node reason = NodeManager::currentNM()->mkAnd(exp);
  return assertFactInternal(atom, polarity, reason);
}

bool ProofEqEngine::assertFact(Node lit,
                               PfRule id,
                               Node exp,
                               const std::vector<Node>& args)
{
  Trace("pfee") << "pfee::assertFact " << lit << " " << id << ", exp = " << exp
                << ", args = " << args << std::endl;
  Node atom = lit.getKind() == NOT ? lit[0] : lit;
  bool polarity = lit.getKind() != NOT;
  // register the step in the proof
  if (holds(atom, polarity))
  {
    // we do not process this fact if it already holds
    return false;
  }
  // must extract the explanation as a vector
  std::vector<Node> expv;
  // Flatten (single occurrences) of AND. We do not allow nested AND, it is
  // the responsibilty of the caller to ensure these do not occur.
  if (exp != d_true)
  {
    if (exp.getKind() == AND)
    {
      for (const Node& expc : exp)
      {
        // should not have doubly nested AND
        Assert(expc.getKind() != AND);
        expv.push_back(expc);
      }
    }
    else
    {
      expv.push_back(exp);
    }
  }
  // buffer the step in the fact proof generator
  ProofStep ps;
  ps.d_rule = id;
  ps.d_children = expv;
  ps.d_args = args;
  d_factPg.addStep(lit, ps);
  // add lazy step to proof
  d_proof.addLazyStep(lit, &d_factPg);
  // second, assert it to the equality engine
  return assertFactInternal(atom, polarity, exp);
}

bool ProofEqEngine::assertFact(Node lit, Node exp, ProofStepBuffer& psb)
{
  Trace("pfee") << "pfee::assertFact " << lit << ", exp = " << exp
                << " via buffer with " << psb.getNumSteps() << " steps"
                << std::endl;
  Node atom = lit.getKind() == NOT ? lit[0] : lit;
  bool polarity = lit.getKind() != NOT;
  if (holds(atom, polarity))
  {
    // we do not process this fact if it already holds
    return false;
  }
  // buffer the steps in the fact proof generator
  const std::vector<std::pair<Node, ProofStep>>& steps = psb.getSteps();
  for (const std::pair<Node, ProofStep>& step : steps)
  {
    d_factPg.addStep(step.first, step.second);
  }
  // add lazy step to proof
  d_proof.addLazyStep(lit, &d_factPg);
  // second, assert it to the equality engine
  return assertFactInternal(atom, polarity, exp);
}

bool ProofEqEngine::assertFact(Node lit, Node exp, ProofGenerator* pg)
{
  Trace("pfee") << "pfee::assertFact " << lit << ", exp = " << exp
                << " via generator" << std::endl;
  Node atom = lit.getKind() == NOT ? lit[0] : lit;
  bool polarity = lit.getKind() != NOT;
  if (holds(atom, polarity))
  {
    // we do not process this fact if it already holds
    return false;
  }
  // note the proof generator is responsible for remembering the explanation
  d_proof.addLazyStep(lit, pg);
  // second, assert it to the equality engine
  return assertFactInternal(atom, polarity, exp);
}

TrustNode ProofEqEngine::assertConflict(Node lit)
{
  Trace("pfee") << "pfee::assertConflict " << lit << std::endl;
  std::vector<TNode> assumps;
  explainWithProof(lit, assumps, &d_proof);
  // lit may not be equivalent to false, but should rewrite to false
  if (lit != d_false)
  {
    Assert(Rewriter::rewrite(lit) == d_false)
        << "pfee::assertConflict: conflict literal is not rewritable to "
           "false";
    std::vector<Node> exp;
    exp.push_back(lit);
    std::vector<Node> args;
    if (!d_proof.addStep(d_false, PfRule::MACRO_SR_PRED_ELIM, exp, args))
    {
      Assert(false) << "pfee::assertConflict: failed conflict step";
      return TrustNode::null();
    }
  }
  return ensureProofForFact(
      d_false, assumps, TrustNodeKind::CONFLICT, &d_proof);
}

TrustNode ProofEqEngine::assertConflict(PfRule id,
                                        const std::vector<Node>& exp,
                                        const std::vector<Node>& args)
{
  Trace("pfee") << "pfee::assertConflict " << id << ", exp = " << exp
                << ", args = " << args << std::endl;
  // conflict is same as lemma concluding false
  return assertLemma(d_false, id, exp, {}, args);
}

TrustNode ProofEqEngine::assertConflict(const std::vector<Node>& exp,
                                        ProofGenerator* pg)
{
  Assert(pg != nullptr);
  Trace("pfee") << "pfee::assertConflict " << exp << " via generator"
                << std::endl;
  return assertLemma(d_false, exp, {}, pg);
}

TrustNode ProofEqEngine::assertLemma(Node conc,
                                     PfRule id,
                                     const std::vector<Node>& exp,
                                     const std::vector<Node>& noExplain,
                                     const std::vector<Node>& args)
{
  Trace("pfee") << "pfee::assertLemma " << conc << " " << id
                << ", exp = " << exp << ", noExplain = " << noExplain
                << ", args = " << args << std::endl;
  Assert(conc != d_true);
  LazyCDProof tmpProof(d_pnm, &d_proof);
  LazyCDProof* curr;
  TrustNodeKind tnk;
  // same policy as above: for conflicts, use existing lazy proof
  if (conc == d_false)
  {
    curr = &d_proof;
    tnk = TrustNodeKind::CONFLICT;
  }
  else
  {
    curr = &tmpProof;
    tnk = TrustNodeKind::LEMMA;
  }
  // explain each literal in the vector
  std::vector<TNode> assumps;
  explainVecWithProof(tnk, assumps, exp, noExplain, curr);
  // Register the proof step. We use a separate lazy CDProof which will make
  // calls to curr above for the proofs of the literals in exp.
  LazyCDProof outer(d_pnm, curr);
  if (!outer.addStep(conc, id, exp, args))
  {
    // a step went wrong, e.g. during checking
    Assert(false) << "pfee::assertConflict: register proof step";
    return TrustNode::null();
  }
  // Now get the proof for conc.
  return ensureProofForFact(conc, assumps, tnk, &outer);
}

TrustNode ProofEqEngine::assertLemma(Node conc,
                                     const std::vector<Node>& exp,
                                     const std::vector<Node>& noExplain,
                                     ProofGenerator* pg)
{
  Assert(pg != nullptr);
  Trace("pfee") << "pfee::assertLemma " << conc << ", exp = " << exp
                << ", noExplain = " << noExplain << " via generator"
                << std::endl;
  LazyCDProof tmpProof(d_pnm, &d_proof);
  LazyCDProof* curr;
  TrustNodeKind tnk;
  // same policy as above: for conflicts, use existing lazy proof
  if (conc == d_false)
  {
    curr = &d_proof;
    tnk = TrustNodeKind::CONFLICT;
  }
  else
  {
    curr = &tmpProof;
    tnk = TrustNodeKind::LEMMA;
  }
  // explain each literal in the vector
  std::vector<TNode> assumps;
  explainVecWithProof(tnk, assumps, exp, noExplain, curr);
  // We use a lazy proof chain here. The provided proof generator sets up the
  // "skeleton" that is the base of the proof we are constructing. The call to
  // LazyCDProofChain::getProofFor will expand the leaves of this proof via
  // calls to curr.
  LazyCDProofChain outer(d_pnm, true, nullptr, curr, false);
  outer.addLazyStep(conc, pg);
  return ensureProofForFact(conc, assumps, tnk, &outer);
}

TrustNode ProofEqEngine::explain(Node conc)
{
  Trace("pfee") << "pfee::explain " << conc << std::endl;
  LazyCDProof tmpProof(d_pnm, &d_proof);
  std::vector<TNode> assumps;
  explainWithProof(conc, assumps, &tmpProof);
  return ensureProofForFact(conc, assumps, TrustNodeKind::PROP_EXP, &tmpProof);
}

void ProofEqEngine::explainVecWithProof(TrustNodeKind& tnk,
                                        std::vector<TNode>& assumps,
                                        const std::vector<Node>& exp,
                                        const std::vector<Node>& noExplain,
                                        LazyCDProof* curr)
{
  std::vector<Node> expn;
  for (const Node& e : exp)
  {
    if (std::find(noExplain.begin(), noExplain.end(), e) == noExplain.end())
    {
      explainWithProof(e, assumps, curr);
    }
    else
    {
      // it did not have a proof; it was an assumption of the previous rule
      assumps.push_back(e);
      // it is not a conflict, since it may involve new literals
      tnk = TrustNodeKind::LEMMA;
    }
  }
}

TrustNode ProofEqEngine::ensureProofForFact(Node conc,
                                            const std::vector<TNode>& assumps,
                                            TrustNodeKind tnk,
                                            ProofGenerator* curr)
{
  Trace("pfee-proof") << std::endl;
  Trace("pfee-proof") << "pfee::ensureProofForFact: input " << conc << " via "
                      << assumps << ", TrustNodeKind=" << tnk << std::endl;
  NodeManager* nm = NodeManager::currentNM();
  // The proof
  std::shared_ptr<ProofNode> pf;
  ProofGenerator* pfg = nullptr;
  // the explanation is the conjunction of assumptions
  Node exp;
  // If proofs are enabled, generate the proof and possibly modify the
  // assumptions to match SCOPE.
  Assert(curr != nullptr);
  Trace("pfee-proof") << "pfee::ensureProofForFact: make proof for fact"
                      << std::endl;
  // get the proof for conc
  std::shared_ptr<ProofNode> pfBody = curr->getProofFor(conc);
  if (pfBody == nullptr)
  {
    Trace("pfee-proof")
        << "pfee::ensureProofForFact: failed to make proof for fact"
        << std::endl
        << std::endl;
    // should have existed
    Assert(false) << "pfee::assertConflict: failed to get proof for " << conc;
    return TrustNode::null();
  }
  // clone it so that we have a fresh copy
  pfBody = d_pnm->clone(pfBody);
  Trace("pfee-proof") << "pfee::ensureProofForFact: add scope" << std::endl;
  // The free assumptions must be closed by assumps, which should be passed
  // as arguments of SCOPE. However, some of the free assumptions may not
  // literally be equal to assumps, for instance, due to symmetry. In other
  // words, the SCOPE could be closing (= x y) in a proof with free
  // assumption (= y x). We modify the proof leaves to account for this
  // below.

  std::vector<Node> scopeAssumps;
  // we first ensure the assumptions are flattened
  for (const TNode& a : assumps)
  {
    if (a.getKind() == AND)
    {
      scopeAssumps.insert(scopeAssumps.end(), a.begin(), a.end());
    }
    else
    {
      scopeAssumps.push_back(a);
    }
  }
  // Scope the proof constructed above, and connect the formula with the proof
  // minimize the assumptions.
  pf = d_pnm->mkScope(pfBody, scopeAssumps, true, true);
  // If we have no assumptions, and are proving an explanation for propagation
  if (scopeAssumps.empty() && tnk == TrustNodeKind::PROP_EXP)
  {
    // Must add "true" as an explicit argument. This is to ensure that the
    // propagation F from true proves (=> true F) instead of F, since this is
    // the form required by TrustNodeKind::PROP_EXP. We do not ensure closed or
    // minimize here, since we already ensured the proof was closed above, and
    // we do not want to minimize, or else "true" would be omitted.
    scopeAssumps.push_back(nm->mkConst(true));
    pf = d_pnm->mkScope(pf, scopeAssumps, false);
  }
  exp = nm->mkAnd(scopeAssumps);
  // Make the lemma or conflict node. This must exactly match the conclusion
  // of SCOPE below.
  Node formula;
  if (tnk == TrustNodeKind::CONFLICT)
  {
    // conflict is negated
    Assert(conc == d_false);
    formula = exp;
  }
  else
  {
    formula =
        exp == d_true
            ? conc
            : (conc == d_false ? exp.negate() : nm->mkNode(IMPLIES, exp, conc));
  }
  Trace("pfee-proof") << "pfee::ensureProofForFact: formula is " << formula
                      << std::endl;
  // should always be non-null
  Assert(pf != nullptr);
  if (Trace.isOn("pfee-proof") || Trace.isOn("pfee-proof-final"))
  {
    Trace("pfee-proof") << "pfee::ensureProofForFact: printing proof"
                        << std::endl;
    std::stringstream ss;
    pf->printDebug(ss);
    Trace("pfee-proof") << "pfee::ensureProofForFact: Proof is " << ss.str()
                        << std::endl;
  }
  // Should be a closed proof now. If it is not, then the overall proof
  // is malformed.
  Assert(pf->isClosed());
  pfg = this;
  // set the proof for the conflict or lemma, which can be queried later
  switch (tnk)
  {
    case TrustNodeKind::CONFLICT: setProofForConflict(formula, pf); break;
    case TrustNodeKind::LEMMA: setProofForLemma(formula, pf); break;
    case TrustNodeKind::PROP_EXP: setProofForPropExp(conc, exp, pf); break;
    default:
      pfg = nullptr;
      Unhandled() << "Unhandled trust node kind " << tnk;
      break;
  }
  Trace("pfee-proof") << "pfee::ensureProofForFact: finish" << std::endl
                      << std::endl;
  // we can provide a proof for conflict, lemma or explained propagation
  switch (tnk)
  {
    case TrustNodeKind::CONFLICT:
      return TrustNode::mkTrustConflict(formula, pfg);
    case TrustNodeKind::LEMMA: return TrustNode::mkTrustLemma(formula, pfg);
    case TrustNodeKind::PROP_EXP:
      return TrustNode::mkTrustPropExp(conc, exp, pfg);
    default: Unhandled() << "Unhandled trust node kind " << tnk; break;
  }
  return TrustNode::null();
}

bool ProofEqEngine::assertFactInternal(TNode atom, bool polarity, TNode reason)
{
  Trace("pfee-debug") << "pfee::assertFactInternal: " << atom << " " << polarity
                      << " " << reason << std::endl;
  bool ret;
  if (atom.getKind() == EQUAL)
  {
    ret = d_ee.assertEquality(atom, polarity, reason);
  }
  else
  {
    ret = d_ee.assertPredicate(atom, polarity, reason);
  }
  if (ret)
  {
    // must reference count the new atom and explanation
    d_keep.insert(atom);
    d_keep.insert(reason);
  }
  return ret;
}

bool ProofEqEngine::holds(TNode atom, bool polarity)
{
  if (atom.getKind() == EQUAL)
  {
    if (!d_ee.hasTerm(atom[0]) || !d_ee.hasTerm(atom[1]))
    {
      return false;
    }
    return polarity ? d_ee.areEqual(atom[0], atom[1])
                    : d_ee.areDisequal(atom[0], atom[1], false);
  }
  if (!d_ee.hasTerm(atom))
  {
    return false;
  }
  TNode b = polarity ? d_true : d_false;
  return d_ee.areEqual(atom, b);
}

void ProofEqEngine::explainWithProof(Node lit,
                                     std::vector<TNode>& assumps,
                                     LazyCDProof* curr)
{
  if (std::find(assumps.begin(), assumps.end(), lit) != assumps.end())
  {
    return;
  }
  std::shared_ptr<eq::EqProof> pf = std::make_shared<eq::EqProof>();
  Trace("pfee-proof") << "pfee::explainWithProof: " << lit << std::endl;
  bool polarity = lit.getKind() != NOT;
  TNode atom = polarity ? lit : lit[0];
  Assert(atom.getKind() != AND);
  std::vector<TNode> tassumps;
  if (atom.getKind() == EQUAL)
  {
    if (atom[0] == atom[1])
    {
      return;
    }
    Assert(d_ee.hasTerm(atom[0]));
    Assert(d_ee.hasTerm(atom[1]));
    if (!polarity)
    {
      // ensure the explanation exists
      AlwaysAssert(d_ee.areDisequal(atom[0], atom[1], true));
    }
    d_ee.explainEquality(atom[0], atom[1], polarity, tassumps, pf.get());
  }
  else
  {
    Assert(d_ee.hasTerm(atom));
    d_ee.explainPredicate(atom, polarity, tassumps, pf.get());
  }
  Trace("pfee-proof") << "...got " << tassumps << std::endl;
  // avoid duplicates
  for (TNode a : tassumps)
  {
    if (a == lit)
    {
      assumps.push_back(a);
    }
    else if (std::find(assumps.begin(), assumps.end(), a) == assumps.end())
    {
      assumps.push_back(a);
    }
  }
  if (Trace.isOn("pfee-proof"))
  {
    Trace("pfee-proof") << "pfee::explainWithProof: add to proof ---"
                        << std::endl;
    std::stringstream sse;
    pf->debug_print(sse);
    Trace("pfee-proof") << sse.str() << std::endl;
    Trace("pfee-proof") << "---" << std::endl;
  }
  // add the steps in the equality engine proof to the Proof
  pf->addToProof(curr);
  Trace("pfee-proof") << "pfee::explainWithProof: finished" << std::endl;
}

}  // namespace eq
}  // namespace theory
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Gereon Kremer, 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 the proof-producing equality engine.
14		*/
15
16		#include "theory/uf/proof_equality_engine.h"
17
18		#include "proof/lazy_proof_chain.h"
19		#include "proof/proof_node.h"
20		#include "proof/proof_node_manager.h"
21		#include "theory/rewriter.h"
22		#include "theory/uf/eq_proof.h"
23		#include "theory/uf/equality_engine.h"
24		#include "theory/uf/proof_checker.h"
25
26		using namespace cvc5::kind;
27
28		namespace cvc5 {
29		namespace theory {
30		namespace eq {
31
32	13141	ProofEqEngine::ProofEqEngine(context::Context* c,
33		context::UserContext* u,
34		EqualityEngine& ee,
35	13141	ProofNodeManager* pnm)
36	26282	: EagerProofGenerator(pnm, u, "pfee::" + ee.identify()),
37		d_ee(ee),
38		d_factPg(c, pnm),
39		d_pnm(pnm),
40	26282	d_proof(pnm, nullptr, c, "pfee::LazyCDProof::" + ee.identify()),
41	65705	d_keep(c)
42		{
43	13141	NodeManager* nm = NodeManager::currentNM();
44	13141	d_true = nm->mkConst(true);
45	13141	d_false = nm->mkConst(false);
46	13141	AlwaysAssert(pnm != nullptr)
47		<< "Should not construct ProofEqEngine without proof node manager";
48	13141	}
49
50		bool ProofEqEngine::assertFact(Node lit,
51		PfRule id,
52		const std::vector<Node>& exp,
53		const std::vector<Node>& args)
54		{
55		Trace("pfee") << "pfee::assertFact " << lit << " " << id << ", exp = " << exp
56		<< ", args = " << args << std::endl;
57
58		Node atom = lit.getKind() == NOT ? lit[0] : lit;
59		bool polarity = lit.getKind() != NOT;
60		// register the step in the proof
61		if (holds(atom, polarity))
62		{
63		// we do not process this fact if it already holds
64		return false;
65		}
66		// Buffer the step in the fact proof generator. We do this instead of
67		// adding explict steps to the lazy proof d_proof since CDProof has
68		// (at most) one proof for each formula. Thus, we "claim" only the
69		// formula that is proved by this fact. Otherwise, aliasing may occur,
70		// which leads to cyclic or bogus proofs.
71		ProofStep ps;
72		ps.d_rule = id;
73		ps.d_children = exp;
74		ps.d_args = args;
75		d_factPg.addStep(lit, ps);
76		// add lazy step to proof
77		d_proof.addLazyStep(lit, &d_factPg);
78		// second, assert it to the equality engine
79		Node reason = NodeManager::currentNM()->mkAnd(exp);
80		return assertFactInternal(atom, polarity, reason);
81		}
82
83	1619	bool ProofEqEngine::assertFact(Node lit,
84		PfRule id,
85		Node exp,
86		const std::vector<Node>& args)
87		{
88	3238	Trace("pfee") << "pfee::assertFact " << lit << " " << id << ", exp = " << exp
89	1619	<< ", args = " << args << std::endl;
90	3238	Node atom = lit.getKind() == NOT ? lit[0] : lit;
91	1619	bool polarity = lit.getKind() != NOT;
92		// register the step in the proof
93	1619	if (holds(atom, polarity))
94		{
95		// we do not process this fact if it already holds
96	548	return false;
97		}
98		// must extract the explanation as a vector
99	2142	std::vector<Node> expv;
100		// Flatten (single occurrences) of AND. We do not allow nested AND, it is
101		// the responsibilty of the caller to ensure these do not occur.
102	1071	if (exp != d_true)
103		{
104	655	if (exp.getKind() == AND)
105		{
106	171	for (const Node& expc : exp)
107		{
108		// should not have doubly nested AND
109	114	Assert(expc.getKind() != AND);
110	114	expv.push_back(expc);
111		}
112		}
113		else
114		{
115	598	expv.push_back(exp);
116		}
117		}
118		// buffer the step in the fact proof generator
119	2142	ProofStep ps;
120	1071	ps.d_rule = id;
121	1071	ps.d_children = expv;
122	1071	ps.d_args = args;
123	1071	d_factPg.addStep(lit, ps);
124		// add lazy step to proof
125	1071	d_proof.addLazyStep(lit, &d_factPg);
126		// second, assert it to the equality engine
127	1071	return assertFactInternal(atom, polarity, exp);
128		}
129
130		bool ProofEqEngine::assertFact(Node lit, Node exp, ProofStepBuffer& psb)
131		{
132		Trace("pfee") << "pfee::assertFact " << lit << ", exp = " << exp
133		<< " via buffer with " << psb.getNumSteps() << " steps"
134		<< std::endl;
135		Node atom = lit.getKind() == NOT ? lit[0] : lit;
136		bool polarity = lit.getKind() != NOT;
137		if (holds(atom, polarity))
138		{
139		// we do not process this fact if it already holds
140		return false;
141		}
142		// buffer the steps in the fact proof generator
143		const std::vector<std::pair<Node, ProofStep>>& steps = psb.getSteps();
144		for (const std::pair<Node, ProofStep>& step : steps)
145		{
146		d_factPg.addStep(step.first, step.second);
147		}
148		// add lazy step to proof
149		d_proof.addLazyStep(lit, &d_factPg);
150		// second, assert it to the equality engine
151		return assertFactInternal(atom, polarity, exp);
152		}
153
154	108267	bool ProofEqEngine::assertFact(Node lit, Node exp, ProofGenerator* pg)
155		{
156	216534	Trace("pfee") << "pfee::assertFact " << lit << ", exp = " << exp
157	108267	<< " via generator" << std::endl;
158	216534	Node atom = lit.getKind() == NOT ? lit[0] : lit;
159	108267	bool polarity = lit.getKind() != NOT;
160	108267	if (holds(atom, polarity))
161		{
162		// we do not process this fact if it already holds
163	35381	return false;
164		}
165		// note the proof generator is responsible for remembering the explanation
166	72886	d_proof.addLazyStep(lit, pg);
167		// second, assert it to the equality engine
168	72886	return assertFactInternal(atom, polarity, exp);
169		}
170
171	2487	TrustNode ProofEqEngine::assertConflict(Node lit)
172		{
173	2487	Trace("pfee") << "pfee::assertConflict " << lit << std::endl;
174	4974	std::vector<TNode> assumps;
175	2487	explainWithProof(lit, assumps, &d_proof);
176		// lit may not be equivalent to false, but should rewrite to false
177	2487	if (lit != d_false)
178		{
179	2487	Assert(Rewriter::rewrite(lit) == d_false)
180		<< "pfee::assertConflict: conflict literal is not rewritable to "
181		"false";
182	4974	std::vector<Node> exp;
183	2487	exp.push_back(lit);
184	4974	std::vector<Node> args;
185	2487	if (!d_proof.addStep(d_false, PfRule::MACRO_SR_PRED_ELIM, exp, args))
186		{
187		Assert(false) << "pfee::assertConflict: failed conflict step";
188		return TrustNode::null();
189		}
190		}
191		return ensureProofForFact(
192	2487	d_false, assumps, TrustNodeKind::CONFLICT, &d_proof);
193		}
194
195	2	TrustNode ProofEqEngine::assertConflict(PfRule id,
196		const std::vector<Node>& exp,
197		const std::vector<Node>& args)
198		{
199	4	Trace("pfee") << "pfee::assertConflict " << id << ", exp = " << exp
200	2	<< ", args = " << args << std::endl;
201		// conflict is same as lemma concluding false
202	2	return assertLemma(d_false, id, exp, {}, args);
203		}
204
205	436	TrustNode ProofEqEngine::assertConflict(const std::vector<Node>& exp,
206		ProofGenerator* pg)
207		{
208	436	Assert(pg != nullptr);
209	872	Trace("pfee") << "pfee::assertConflict " << exp << " via generator"
210	436	<< std::endl;
211	436	return assertLemma(d_false, exp, {}, pg);
212		}
213
214	53	TrustNode ProofEqEngine::assertLemma(Node conc,
215		PfRule id,
216		const std::vector<Node>& exp,
217		const std::vector<Node>& noExplain,
218		const std::vector<Node>& args)
219		{
220	106	Trace("pfee") << "pfee::assertLemma " << conc << " " << id
221	53	<< ", exp = " << exp << ", noExplain = " << noExplain
222	53	<< ", args = " << args << std::endl;
223	53	Assert(conc != d_true);
224	106	LazyCDProof tmpProof(d_pnm, &d_proof);
225		LazyCDProof* curr;
226		TrustNodeKind tnk;
227		// same policy as above: for conflicts, use existing lazy proof
228	53	if (conc == d_false)
229		{
230	2	curr = &d_proof;
231	2	tnk = TrustNodeKind::CONFLICT;
232		}
233		else
234		{
235	51	curr = &tmpProof;
236	51	tnk = TrustNodeKind::LEMMA;
237		}
238		// explain each literal in the vector
239	106	std::vector<TNode> assumps;
240	53	explainVecWithProof(tnk, assumps, exp, noExplain, curr);
241		// Register the proof step. We use a separate lazy CDProof which will make
242		// calls to curr above for the proofs of the literals in exp.
243	106	LazyCDProof outer(d_pnm, curr);
244	53	if (!outer.addStep(conc, id, exp, args))
245		{
246		// a step went wrong, e.g. during checking
247		Assert(false) << "pfee::assertConflict: register proof step";
248		return TrustNode::null();
249		}
250		// Now get the proof for conc.
251	53	return ensureProofForFact(conc, assumps, tnk, &outer);
252		}
253
254	2505	TrustNode ProofEqEngine::assertLemma(Node conc,
255		const std::vector<Node>& exp,
256		const std::vector<Node>& noExplain,
257		ProofGenerator* pg)
258		{
259	2505	Assert(pg != nullptr);
260	5010	Trace("pfee") << "pfee::assertLemma " << conc << ", exp = " << exp
261	2505	<< ", noExplain = " << noExplain << " via generator"
262	2505	<< std::endl;
263	5010	LazyCDProof tmpProof(d_pnm, &d_proof);
264		LazyCDProof* curr;
265		TrustNodeKind tnk;
266		// same policy as above: for conflicts, use existing lazy proof
267	2505	if (conc == d_false)
268		{
269	454	curr = &d_proof;
270	454	tnk = TrustNodeKind::CONFLICT;
271		}
272		else
273		{
274	2051	curr = &tmpProof;
275	2051	tnk = TrustNodeKind::LEMMA;
276		}
277		// explain each literal in the vector
278	5010	std::vector<TNode> assumps;
279	2505	explainVecWithProof(tnk, assumps, exp, noExplain, curr);
280		// We use a lazy proof chain here. The provided proof generator sets up the
281		// "skeleton" that is the base of the proof we are constructing. The call to
282		// LazyCDProofChain::getProofFor will expand the leaves of this proof via
283		// calls to curr.
284	5010	LazyCDProofChain outer(d_pnm, true, nullptr, curr, false);
285	2505	outer.addLazyStep(conc, pg);
286	5010	return ensureProofForFact(conc, assumps, tnk, &outer);
287		}
288
289	51803	TrustNode ProofEqEngine::explain(Node conc)
290		{
291	51803	Trace("pfee") << "pfee::explain " << conc << std::endl;
292	103606	LazyCDProof tmpProof(d_pnm, &d_proof);
293	103606	std::vector<TNode> assumps;
294	51803	explainWithProof(conc, assumps, &tmpProof);
295	103606	return ensureProofForFact(conc, assumps, TrustNodeKind::PROP_EXP, &tmpProof);
296		}
297
298	2558	void ProofEqEngine::explainVecWithProof(TrustNodeKind& tnk,
299		std::vector<TNode>& assumps,
300		const std::vector<Node>& exp,
301		const std::vector<Node>& noExplain,
302		LazyCDProof* curr)
303		{
304	5116	std::vector<Node> expn;
305	7337	for (const Node& e : exp)
306		{
307	4779	if (std::find(noExplain.begin(), noExplain.end(), e) == noExplain.end())
308		{
309	4207	explainWithProof(e, assumps, curr);
310		}
311		else
312		{
313		// it did not have a proof; it was an assumption of the previous rule
314	572	assumps.push_back(e);
315		// it is not a conflict, since it may involve new literals
316	572	tnk = TrustNodeKind::LEMMA;
317		}
318		}
319	2558	}
320
321	56848	TrustNode ProofEqEngine::ensureProofForFact(Node conc,
322		const std::vector<TNode>& assumps,
323		TrustNodeKind tnk,
324		ProofGenerator* curr)
325		{
326	56848	Trace("pfee-proof") << std::endl;
327	113696	Trace("pfee-proof") << "pfee::ensureProofForFact: input " << conc << " via "
328	56848	<< assumps << ", TrustNodeKind=" << tnk << std::endl;
329	56848	NodeManager* nm = NodeManager::currentNM();
330		// The proof
331	113696	std::shared_ptr<ProofNode> pf;
332	56848	ProofGenerator* pfg = nullptr;
333		// the explanation is the conjunction of assumptions
334	113696	Node exp;
335		// If proofs are enabled, generate the proof and possibly modify the
336		// assumptions to match SCOPE.
337	56848	Assert(curr != nullptr);
338	113696	Trace("pfee-proof") << "pfee::ensureProofForFact: make proof for fact"
339	56848	<< std::endl;
340		// get the proof for conc
341	113696	std::shared_ptr<ProofNode> pfBody = curr->getProofFor(conc);
342	56848	if (pfBody == nullptr)
343		{
344		Trace("pfee-proof")
345		<< "pfee::ensureProofForFact: failed to make proof for fact"
346		<< std::endl
347		<< std::endl;
348		// should have existed
349		Assert(false) << "pfee::assertConflict: failed to get proof for " << conc;
350		return TrustNode::null();
351		}
352		// clone it so that we have a fresh copy
353	56848	pfBody = d_pnm->clone(pfBody);
354	56848	Trace("pfee-proof") << "pfee::ensureProofForFact: add scope" << std::endl;
355		// The free assumptions must be closed by assumps, which should be passed
356		// as arguments of SCOPE. However, some of the free assumptions may not
357		// literally be equal to assumps, for instance, due to symmetry. In other
358		// words, the SCOPE could be closing (= x y) in a proof with free
359		// assumption (= y x). We modify the proof leaves to account for this
360		// below.
361
362	113696	std::vector<Node> scopeAssumps;
363		// we first ensure the assumptions are flattened
364	324878	for (const TNode& a : assumps)
365		{
366	268030	if (a.getKind() == AND)
367		{
368	1852	scopeAssumps.insert(scopeAssumps.end(), a.begin(), a.end());
369		}
370		else
371		{
372	266178	scopeAssumps.push_back(a);
373		}
374		}
375		// Scope the proof constructed above, and connect the formula with the proof
376		// minimize the assumptions.
377	56848	pf = d_pnm->mkScope(pfBody, scopeAssumps, true, true);
378		// If we have no assumptions, and are proving an explanation for propagation
379	56848	if (scopeAssumps.empty() && tnk == TrustNodeKind::PROP_EXP)
380		{
381		// Must add "true" as an explicit argument. This is to ensure that the
382		// propagation F from true proves (=> true F) instead of F, since this is
383		// the form required by TrustNodeKind::PROP_EXP. We do not ensure closed or
384		// minimize here, since we already ensured the proof was closed above, and
385		// we do not want to minimize, or else "true" would be omitted.
386	1675	scopeAssumps.push_back(nm->mkConst(true));
387	1675	pf = d_pnm->mkScope(pf, scopeAssumps, false);
388		}
389	56848	exp = nm->mkAnd(scopeAssumps);
390		// Make the lemma or conflict node. This must exactly match the conclusion
391		// of SCOPE below.
392	113696	Node formula;
393	56848	if (tnk == TrustNodeKind::CONFLICT)
394		{
395		// conflict is negated
396	2925	Assert(conc == d_false);
397	2925	formula = exp;
398		}
399		else
400		{
401	53923	formula =
402	53923	exp == d_true
403	159530	? conc
404	51684	: (conc == d_false ? exp.negate() : nm->mkNode(IMPLIES, exp, conc));
405		}
406	113696	Trace("pfee-proof") << "pfee::ensureProofForFact: formula is " << formula
407	56848	<< std::endl;
408		// should always be non-null
409	56848	Assert(pf != nullptr);
410	56848	if (Trace.isOn("pfee-proof") \|\| Trace.isOn("pfee-proof-final"))
411		{
412		Trace("pfee-proof") << "pfee::ensureProofForFact: printing proof"
413		<< std::endl;
414		std::stringstream ss;
415		pf->printDebug(ss);
416		Trace("pfee-proof") << "pfee::ensureProofForFact: Proof is " << ss.str()
417		<< std::endl;
418		}
419		// Should be a closed proof now. If it is not, then the overall proof
420		// is malformed.
421	56848	Assert(pf->isClosed());
422	56848	pfg = this;
423		// set the proof for the conflict or lemma, which can be queried later
424	56848	switch (tnk)
425		{
426	2925	case TrustNodeKind::CONFLICT: setProofForConflict(formula, pf); break;
427	2120	case TrustNodeKind::LEMMA: setProofForLemma(formula, pf); break;
428	51803	case TrustNodeKind::PROP_EXP: setProofForPropExp(conc, exp, pf); break;
429		default:
430		pfg = nullptr;
431		Unhandled() << "Unhandled trust node kind " << tnk;
432		break;
433		}
434	113696	Trace("pfee-proof") << "pfee::ensureProofForFact: finish" << std::endl
435	56848	<< std::endl;
436		// we can provide a proof for conflict, lemma or explained propagation
437	56848	switch (tnk)
438		{
439	2925	case TrustNodeKind::CONFLICT:
440	2925	return TrustNode::mkTrustConflict(formula, pfg);
441	2120	case TrustNodeKind::LEMMA: return TrustNode::mkTrustLemma(formula, pfg);
442	51803	case TrustNodeKind::PROP_EXP:
443	51803	return TrustNode::mkTrustPropExp(conc, exp, pfg);
444		default: Unhandled() << "Unhandled trust node kind " << tnk; break;
445		}
446		return TrustNode::null();
447		}
448
449	73957	bool ProofEqEngine::assertFactInternal(TNode atom, bool polarity, TNode reason)
450		{
451	147914	Trace("pfee-debug") << "pfee::assertFactInternal: " << atom << " " << polarity
452	73957	<< " " << reason << std::endl;
453		bool ret;
454	73957	if (atom.getKind() == EQUAL)
455		{
456	70913	ret = d_ee.assertEquality(atom, polarity, reason);
457		}
458		else
459		{
460	3044	ret = d_ee.assertPredicate(atom, polarity, reason);
461		}
462	73957	if (ret)
463		{
464		// must reference count the new atom and explanation
465	73957	d_keep.insert(atom);
466	73957	d_keep.insert(reason);
467		}
468	73957	return ret;
469		}
470
471	109886	bool ProofEqEngine::holds(TNode atom, bool polarity)
472		{
473	109886	if (atom.getKind() == EQUAL)
474		{
475	106814	if (!d_ee.hasTerm(atom[0]) \|\| !d_ee.hasTerm(atom[1]))
476		{
477	29798	return false;
478		}
479	224324	return polarity ? d_ee.areEqual(atom[0], atom[1])
480	147308	: d_ee.areDisequal(atom[0], atom[1], false);
481		}
482	3072	if (!d_ee.hasTerm(atom))
483		{
484	1976	return false;
485		}
486	2192	TNode b = polarity ? d_true : d_false;
487	1096	return d_ee.areEqual(atom, b);
488		}
489
490	58497	void ProofEqEngine::explainWithProof(Node lit,
491		std::vector<TNode>& assumps,
492		LazyCDProof* curr)
493		{
494	58497	if (std::find(assumps.begin(), assumps.end(), lit) != assumps.end())
495		{
496	4	return;
497		}
498	116990	std::shared_ptr<eq::EqProof> pf = std::make_shared<eq::EqProof>();
499	58495	Trace("pfee-proof") << "pfee::explainWithProof: " << lit << std::endl;
500	58495	bool polarity = lit.getKind() != NOT;
501	116990	TNode atom = polarity ? lit : lit[0];
502	58495	Assert(atom.getKind() != AND);
503	116990	std::vector<TNode> tassumps;
504	58495	if (atom.getKind() == EQUAL)
505		{
506	55202	if (atom[0] == atom[1])
507		{
508		return;
509		}
510	55202	Assert(d_ee.hasTerm(atom[0]));
511	55202	Assert(d_ee.hasTerm(atom[1]));
512	55202	if (!polarity)
513		{
514		// ensure the explanation exists
515	3450	AlwaysAssert(d_ee.areDisequal(atom[0], atom[1], true));
516		}
517	55202	d_ee.explainEquality(atom[0], atom[1], polarity, tassumps, pf.get());
518		}
519		else
520		{
521	3293	Assert(d_ee.hasTerm(atom));
522	3293	d_ee.explainPredicate(atom, polarity, tassumps, pf.get());
523		}
524	58495	Trace("pfee-proof") << "...got " << tassumps << std::endl;
525		// avoid duplicates
526	417737	for (TNode a : tassumps)
527		{
528	359242	if (a == lit)
529		{
530	1441	assumps.push_back(a);
531		}
532	357801	else if (std::find(assumps.begin(), assumps.end(), a) == assumps.end())
533		{
534	266017	assumps.push_back(a);
535		}
536		}
537	58495	if (Trace.isOn("pfee-proof"))
538		{
539		Trace("pfee-proof") << "pfee::explainWithProof: add to proof ---"
540		<< std::endl;
541		std::stringstream sse;
542		pf->debug_print(sse);
543		Trace("pfee-proof") << sse.str() << std::endl;
544		Trace("pfee-proof") << "---" << std::endl;
545		}
546		// add the steps in the equality engine proof to the Proof
547	58495	pf->addToProof(curr);
548	58495	Trace("pfee-proof") << "pfee::explainWithProof: finished" << std::endl;
549		}
550
551		} // namespace eq
552		} // namespace theory
553	29340	} // namespace cvc5