Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/arith/theory_arith.cpp	Lines:	130	131	99.2 %
Date:	2021-05-21	Branches:	175	376	46.5 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Tim King, Alex Ozdemir
 *
 * 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.
 * ****************************************************************************
 *
 * Arithmetic theory.
 */

#include "theory/arith/theory_arith.h"

#include "expr/proof_checker.h"
#include "expr/proof_rule.h"
#include "options/smt_options.h"
#include "smt/smt_statistics_registry.h"
#include "theory/arith/arith_rewriter.h"
#include "theory/arith/infer_bounds.h"
#include "theory/arith/nl/nonlinear_extension.h"
#include "theory/arith/theory_arith_private.h"
#include "theory/ext_theory.h"
#include "theory/rewriter.h"
#include "theory/theory_model.h"

using namespace std;
using namespace cvc5::kind;

namespace cvc5 {
namespace theory {
namespace arith {

TheoryArith::TheoryArith(context::Context* c,
                         context::UserContext* u,
                         OutputChannel& out,
                         Valuation valuation,
                         const LogicInfo& logicInfo,
                         ProofNodeManager* pnm)
    : Theory(THEORY_ARITH, c, u, out, valuation, logicInfo, pnm),
      d_internal(
          new TheoryArithPrivate(*this, c, u, out, valuation, logicInfo, pnm)),
      d_ppRewriteTimer(smtStatisticsRegistry().registerTimer(
          "theory::arith::ppRewriteTimer")),
      d_ppPfGen(pnm, c, "Arith::ppRewrite"),
      d_astate(*d_internal, c, u, valuation),
      d_im(*this, d_astate, pnm),
      d_nonlinearExtension(nullptr),
      d_opElim(pnm, logicInfo),
      d_arithPreproc(d_astate, d_im, pnm, d_opElim),
      d_rewriter(d_opElim)
{
  // indicate we are using the theory state object and inference manager
  d_theoryState = &d_astate;
  d_inferManager = &d_im;
}

TheoryArith::~TheoryArith(){
  delete d_internal;
}

TheoryRewriter* TheoryArith::getTheoryRewriter() { return &d_rewriter; }

ProofRuleChecker* TheoryArith::getProofChecker()
{
  return d_internal->getProofChecker();
}

bool TheoryArith::needsEqualityEngine(EeSetupInfo& esi)
{
  return d_internal->needsEqualityEngine(esi);
}
void TheoryArith::finishInit()
{
  if (getLogicInfo().isTheoryEnabled(THEORY_ARITH)
      && getLogicInfo().areTranscendentalsUsed())
  {
    // witness is used to eliminate square root
    d_valuation.setUnevaluatedKind(kind::WITNESS);
    // we only need to add the operators that are not syntax sugar
    d_valuation.setUnevaluatedKind(kind::EXPONENTIAL);
    d_valuation.setUnevaluatedKind(kind::SINE);
    d_valuation.setUnevaluatedKind(kind::PI);
  }
  // only need to create nonlinear extension if non-linear logic
  const LogicInfo& logicInfo = getLogicInfo();
  if (logicInfo.isTheoryEnabled(THEORY_ARITH) && !logicInfo.isLinear())
  {
    d_nonlinearExtension.reset(
        new nl::NonlinearExtension(*this, d_astate, d_equalityEngine, d_pnm));
  }
  // finish initialize internally
  d_internal->finishInit();
}

void TheoryArith::preRegisterTerm(TNode n)
{
  if (d_nonlinearExtension != nullptr)
  {
    d_nonlinearExtension->preRegisterTerm(n);
  }
  d_internal->preRegisterTerm(n);
}

void TheoryArith::notifySharedTerm(TNode n) { d_internal->notifySharedTerm(n); }

TrustNode TheoryArith::ppRewrite(TNode atom, std::vector<SkolemLemma>& lems)
{
  CodeTimer timer(d_ppRewriteTimer, /* allow_reentrant = */ true);
  Debug("arith::preprocess") << "arith::preprocess() : " << atom << endl;

  if (atom.getKind() == kind::EQUAL)
  {
    return ppRewriteEq(atom);
  }
  Assert(Theory::theoryOf(atom) == THEORY_ARITH);
  // Eliminate operators. Notice we must do this here since other
  // theories may generate lemmas that involve non-standard operators. For
  // example, quantifier instantiation may use TO_INTEGER terms; SyGuS may
  // introduce non-standard arithmetic terms appearing in grammars.
  // call eliminate operators. In contrast to expandDefinitions, we eliminate
  // *all* extended arithmetic operators here, including total ones.
  return d_arithPreproc.eliminate(atom, lems, false);
}

TrustNode TheoryArith::ppRewriteEq(TNode atom)
{
  Assert(atom.getKind() == kind::EQUAL);
  if (!options::arithRewriteEq())
  {
    return TrustNode::null();
  }
  Assert(atom[0].getType().isReal());
  Node leq = NodeBuilder(kind::LEQ) << atom[0] << atom[1];
  Node geq = NodeBuilder(kind::GEQ) << atom[0] << atom[1];
  Node rewritten = Rewriter::rewrite(leq.andNode(geq));
  Debug("arith::preprocess")
      << "arith::preprocess() : returning " << rewritten << endl;
  // don't need to rewrite terms since rewritten is not a non-standard op
  if (proofsEnabled())
  {
    return d_ppPfGen.mkTrustedRewrite(
        atom,
        rewritten,
        d_pnm->mkNode(PfRule::INT_TRUST, {}, {atom.eqNode(rewritten)}));
  }
  return TrustNode::mkTrustRewrite(atom, rewritten, nullptr);
}

Theory::PPAssertStatus TheoryArith::ppAssert(
    TrustNode tin, TrustSubstitutionMap& outSubstitutions)
{
  return d_internal->ppAssert(tin, outSubstitutions);
}

void TheoryArith::ppStaticLearn(TNode n, NodeBuilder& learned)
{
  d_internal->ppStaticLearn(n, learned);
}

bool TheoryArith::preCheck(Effort level)
{
  Trace("arith-check") << "TheoryArith::preCheck " << level << std::endl;
  return d_internal->preCheck(level);
}

void TheoryArith::postCheck(Effort level)
{
  Trace("arith-check") << "TheoryArith::postCheck " << level << std::endl;
  // check with the non-linear solver at last call
  if (level == Theory::EFFORT_LAST_CALL)
  {
    if (d_nonlinearExtension != nullptr)
    {
      d_nonlinearExtension->check(level);
    }
    return;
  }
  // otherwise, check with the linear solver
  if (d_internal->postCheck(level))
  {
    // linear solver emitted a conflict or lemma, return
    return;
  }

  if (Theory::fullEffort(level))
  {
    if (d_nonlinearExtension != nullptr)
    {
      d_nonlinearExtension->check(level);
    }
    else if (d_internal->foundNonlinear())
    {
      // set incomplete
      d_im.setIncomplete(IncompleteId::ARITH_NL_DISABLED);
    }
  }
}

bool TheoryArith::preNotifyFact(
    TNode atom, bool pol, TNode fact, bool isPrereg, bool isInternal)
{
  Trace("arith-check") << "TheoryArith::preNotifyFact: " << fact
                       << ", isPrereg=" << isPrereg
                       << ", isInternal=" << isInternal << std::endl;
  d_internal->preNotifyFact(atom, pol, fact);
  // We do not assert to the equality engine of arithmetic in the standard way,
  // hence we return "true" to indicate we are finished with this fact.
  return true;
}

bool TheoryArith::needsCheckLastEffort() {
  if (d_nonlinearExtension != nullptr)
  {
    return d_nonlinearExtension->needsCheckLastEffort();
  }
  return false;
}

TrustNode TheoryArith::explain(TNode n) { return d_internal->explain(n); }

void TheoryArith::propagate(Effort e) {
  d_internal->propagate(e);
}

bool TheoryArith::collectModelInfo(TheoryModel* m,
                                   const std::set<Node>& termSet)
{
  // this overrides behavior to not assert equality engine
  return collectModelValues(m, termSet);
}

bool TheoryArith::collectModelValues(TheoryModel* m,
                                     const std::set<Node>& termSet)
{
  // get the model from the linear solver
  std::map<Node, Node> arithModel;
  d_internal->collectModelValues(termSet, arithModel);
  // if non-linear is enabled, intercept the model, which may repair its values
  if (d_nonlinearExtension != nullptr)
  {
    // Non-linear may repair values to satisfy non-linear constraints (see
    // documentation for NonlinearExtension::interceptModel).
    d_nonlinearExtension->interceptModel(arithModel, termSet);
  }
  // We are now ready to assert the model.
  for (const std::pair<const Node, Node>& p : arithModel)
  {
    // maps to constant of comparable type
    Assert(p.first.getType().isComparableTo(p.second.getType()));
    if (m->assertEquality(p.first, p.second, true))
    {
      continue;
    }
    // If we failed to assert an equality, it is likely due to theory
    // combination, namely the repaired model for non-linear changed
    // an equality status that was agreed upon by both (linear) arithmetic
    // and another theory. In this case, we must add a lemma, or otherwise
    // we would terminate with an invalid model. Thus, we add a splitting
    // lemma of the form ( x = v V x != v ) where v is the model value
    // assigned by the non-linear solver to x.
    if (d_nonlinearExtension != nullptr)
    {
      Node eq = p.first.eqNode(p.second);
      Node lem = NodeManager::currentNM()->mkNode(kind::OR, eq, eq.negate());
      bool added = d_im.lemma(lem, InferenceId::ARITH_SPLIT_FOR_NL_MODEL);
      AlwaysAssert(added) << "The lemma was already in cache. Probably there is something wrong with theory combination...";
    }
    return false;
  }
  return true;
}

void TheoryArith::notifyRestart(){
  d_internal->notifyRestart();
}

void TheoryArith::presolve(){
  d_internal->presolve();
  if (d_nonlinearExtension != nullptr)
  {
    d_nonlinearExtension->presolve();
  }
}

EqualityStatus TheoryArith::getEqualityStatus(TNode a, TNode b) {
  return d_internal->getEqualityStatus(a,b);
}

Node TheoryArith::getModelValue(TNode var) {
  return d_internal->getModelValue( var );
}

std::pair<bool, Node> TheoryArith::entailmentCheck(TNode lit)
{
  ArithEntailmentCheckParameters def;
  def.addLookupRowSumAlgorithms();
  ArithEntailmentCheckSideEffects ase;
  std::pair<bool, Node> res = d_internal->entailmentCheck(lit, def, ase);
  return res;
}
eq::ProofEqEngine* TheoryArith::getProofEqEngine()
{
  return d_im.getProofEqEngine();
}

}  // namespace arith
}  // namespace theory
}  // namespace cvc5


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Tim King, Alex Ozdemir
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		* Arithmetic theory.
14		*/
15
16		#include "theory/arith/theory_arith.h"
17
18		#include "expr/proof_checker.h"
19		#include "expr/proof_rule.h"
20		#include "options/smt_options.h"
21		#include "smt/smt_statistics_registry.h"
22		#include "theory/arith/arith_rewriter.h"
23		#include "theory/arith/infer_bounds.h"
24		#include "theory/arith/nl/nonlinear_extension.h"
25		#include "theory/arith/theory_arith_private.h"
26		#include "theory/ext_theory.h"
27		#include "theory/rewriter.h"
28		#include "theory/theory_model.h"
29
30		using namespace std;
31		using namespace cvc5::kind;
32
33		namespace cvc5 {
34		namespace theory {
35		namespace arith {
36
37	8954	TheoryArith::TheoryArith(context::Context* c,
38		context::UserContext* u,
39		OutputChannel& out,
40		Valuation valuation,
41		const LogicInfo& logicInfo,
42	8954	ProofNodeManager* pnm)
43		: Theory(THEORY_ARITH, c, u, out, valuation, logicInfo, pnm),
44		d_internal(
45	8954	new TheoryArithPrivate(*this, c, u, out, valuation, logicInfo, pnm)),
46	8954	d_ppRewriteTimer(smtStatisticsRegistry().registerTimer(
47	17908	"theory::arith::ppRewriteTimer")),
48		d_ppPfGen(pnm, c, "Arith::ppRewrite"),
49	8954	d_astate(*d_internal, c, u, valuation),
50		d_im(*this, d_astate, pnm),
51		d_nonlinearExtension(nullptr),
52		d_opElim(pnm, logicInfo),
53		d_arithPreproc(d_astate, d_im, pnm, d_opElim),
54	44770	d_rewriter(d_opElim)
55		{
56		// indicate we are using the theory state object and inference manager
57	8954	d_theoryState = &d_astate;
58	8954	d_inferManager = &d_im;
59	8954	}
60
61	26862	TheoryArith::~TheoryArith(){
62	8954	delete d_internal;
63	17908	}
64
65	8954	TheoryRewriter* TheoryArith::getTheoryRewriter() { return &d_rewriter; }
66
67	3117	ProofRuleChecker* TheoryArith::getProofChecker()
68		{
69	3117	return d_internal->getProofChecker();
70		}
71
72	8954	bool TheoryArith::needsEqualityEngine(EeSetupInfo& esi)
73		{
74	8954	return d_internal->needsEqualityEngine(esi);
75		}
76	8954	void TheoryArith::finishInit()
77		{
78	17908	if (getLogicInfo().isTheoryEnabled(THEORY_ARITH)
79	8954	&& getLogicInfo().areTranscendentalsUsed())
80		{
81		// witness is used to eliminate square root
82	3900	d_valuation.setUnevaluatedKind(kind::WITNESS);
83		// we only need to add the operators that are not syntax sugar
84	3900	d_valuation.setUnevaluatedKind(kind::EXPONENTIAL);
85	3900	d_valuation.setUnevaluatedKind(kind::SINE);
86	3900	d_valuation.setUnevaluatedKind(kind::PI);
87		}
88		// only need to create nonlinear extension if non-linear logic
89	8954	const LogicInfo& logicInfo = getLogicInfo();
90	8954	if (logicInfo.isTheoryEnabled(THEORY_ARITH) && !logicInfo.isLinear())
91		{
92	9562	d_nonlinearExtension.reset(
93	4781	new nl::NonlinearExtension(*this, d_astate, d_equalityEngine, d_pnm));
94		}
95		// finish initialize internally
96	8954	d_internal->finishInit();
97	8954	}
98
99	698884	void TheoryArith::preRegisterTerm(TNode n)
100		{
101	698884	if (d_nonlinearExtension != nullptr)
102		{
103	358997	d_nonlinearExtension->preRegisterTerm(n);
104		}
105	698885	d_internal->preRegisterTerm(n);
106	698883	}
107
108	572727	void TheoryArith::notifySharedTerm(TNode n) { d_internal->notifySharedTerm(n); }
109
110	716076	TrustNode TheoryArith::ppRewrite(TNode atom, std::vector<SkolemLemma>& lems)
111		{
112	1432152	CodeTimer timer(d_ppRewriteTimer, /* allow_reentrant = */ true);
113	716076	Debug("arith::preprocess") << "arith::preprocess() : " << atom << endl;
114
115	716076	if (atom.getKind() == kind::EQUAL)
116		{
117	29147	return ppRewriteEq(atom);
118		}
119	686929	Assert(Theory::theoryOf(atom) == THEORY_ARITH);
120		// Eliminate operators. Notice we must do this here since other
121		// theories may generate lemmas that involve non-standard operators. For
122		// example, quantifier instantiation may use TO_INTEGER terms; SyGuS may
123		// introduce non-standard arithmetic terms appearing in grammars.
124		// call eliminate operators. In contrast to expandDefinitions, we eliminate
125		// all extended arithmetic operators here, including total ones.
126	686935	return d_arithPreproc.eliminate(atom, lems, false);
127		}
128
129	30059	TrustNode TheoryArith::ppRewriteEq(TNode atom)
130		{
131	30059	Assert(atom.getKind() == kind::EQUAL);
132	30059	if (!options::arithRewriteEq())
133		{
134	12288	return TrustNode::null();
135		}
136	17771	Assert(atom[0].getType().isReal());
137	35542	Node leq = NodeBuilder(kind::LEQ) << atom[0] << atom[1];
138	35542	Node geq = NodeBuilder(kind::GEQ) << atom[0] << atom[1];
139	35542	Node rewritten = Rewriter::rewrite(leq.andNode(geq));
140	35542	Debug("arith::preprocess")
141	17771	<< "arith::preprocess() : returning " << rewritten << endl;
142		// don't need to rewrite terms since rewritten is not a non-standard op
143	17771	if (proofsEnabled())
144		{
145		return d_ppPfGen.mkTrustedRewrite(
146		atom,
147		rewritten,
148	3404	d_pnm->mkNode(PfRule::INT_TRUST, {}, {atom.eqNode(rewritten)}));
149		}
150	14367	return TrustNode::mkTrustRewrite(atom, rewritten, nullptr);
151		}
152
153	11527	Theory::PPAssertStatus TheoryArith::ppAssert(
154		TrustNode tin, TrustSubstitutionMap& outSubstitutions)
155		{
156	11527	return d_internal->ppAssert(tin, outSubstitutions);
157		}
158
159	98754	void TheoryArith::ppStaticLearn(TNode n, NodeBuilder& learned)
160		{
161	98754	d_internal->ppStaticLearn(n, learned);
162	98754	}
163
164	1307273	bool TheoryArith::preCheck(Effort level)
165		{
166	1307273	Trace("arith-check") << "TheoryArith::preCheck " << level << std::endl;
167	1307273	return d_internal->preCheck(level);
168		}
169
170	1307273	void TheoryArith::postCheck(Effort level)
171		{
172	1307273	Trace("arith-check") << "TheoryArith::postCheck " << level << std::endl;
173		// check with the non-linear solver at last call
174	1307273	if (level == Theory::EFFORT_LAST_CALL)
175		{
176	2963	if (d_nonlinearExtension != nullptr)
177		{
178	2963	d_nonlinearExtension->check(level);
179		}
180	2963	return;
181		}
182		// otherwise, check with the linear solver
183	1304310	if (d_internal->postCheck(level))
184		{
185		// linear solver emitted a conflict or lemma, return
186	49466	return;
187		}
188
189	1254844	if (Theory::fullEffort(level))
190		{
191	46974	if (d_nonlinearExtension != nullptr)
192		{
193	26139	d_nonlinearExtension->check(level);
194		}
195	20835	else if (d_internal->foundNonlinear())
196		{
197		// set incomplete
198		d_im.setIncomplete(IncompleteId::ARITH_NL_DISABLED);
199		}
200		}
201		}
202
203	4938025	bool TheoryArith::preNotifyFact(
204		TNode atom, bool pol, TNode fact, bool isPrereg, bool isInternal)
205		{
206	9876050	Trace("arith-check") << "TheoryArith::preNotifyFact: " << fact
207	4938025	<< ", isPrereg=" << isPrereg
208	4938025	<< ", isInternal=" << isInternal << std::endl;
209	4938025	d_internal->preNotifyFact(atom, pol, fact);
210		// We do not assert to the equality engine of arithmetic in the standard way,
211		// hence we return "true" to indicate we are finished with this fact.
212	4938025	return true;
213		}
214
215	16595	bool TheoryArith::needsCheckLastEffort() {
216	16595	if (d_nonlinearExtension != nullptr)
217		{
218	9462	return d_nonlinearExtension->needsCheckLastEffort();
219		}
220	7133	return false;
221		}
222
223	21216	TrustNode TheoryArith::explain(TNode n) { return d_internal->explain(n); }
224
225	2132391	void TheoryArith::propagate(Effort e) {
226	2132391	d_internal->propagate(e);
227	2132391	}
228
229	13338	bool TheoryArith::collectModelInfo(TheoryModel* m,
230		const std::set<Node>& termSet)
231		{
232		// this overrides behavior to not assert equality engine
233	13338	return collectModelValues(m, termSet);
234		}
235
236	13338	bool TheoryArith::collectModelValues(TheoryModel* m,
237		const std::set<Node>& termSet)
238		{
239		// get the model from the linear solver
240	26676	std::map<Node, Node> arithModel;
241	13338	d_internal->collectModelValues(termSet, arithModel);
242		// if non-linear is enabled, intercept the model, which may repair its values
243	13338	if (d_nonlinearExtension != nullptr)
244		{
245		// Non-linear may repair values to satisfy non-linear constraints (see
246		// documentation for NonlinearExtension::interceptModel).
247	8421	d_nonlinearExtension->interceptModel(arithModel, termSet);
248		}
249		// We are now ready to assert the model.
250	234446	for (const std::pair<const Node, Node>& p : arithModel)
251		{
252		// maps to constant of comparable type
253	221110	Assert(p.first.getType().isComparableTo(p.second.getType()));
254	221110	if (m->assertEquality(p.first, p.second, true))
255		{
256	221108	continue;
257		}
258		// If we failed to assert an equality, it is likely due to theory
259		// combination, namely the repaired model for non-linear changed
260		// an equality status that was agreed upon by both (linear) arithmetic
261		// and another theory. In this case, we must add a lemma, or otherwise
262		// we would terminate with an invalid model. Thus, we add a splitting
263		// lemma of the form ( x = v V x != v ) where v is the model value
264		// assigned by the non-linear solver to x.
265	2	if (d_nonlinearExtension != nullptr)
266		{
267	4	Node eq = p.first.eqNode(p.second);
268	4	Node lem = NodeManager::currentNM()->mkNode(kind::OR, eq, eq.negate());
269	2	bool added = d_im.lemma(lem, InferenceId::ARITH_SPLIT_FOR_NL_MODEL);
270	2	AlwaysAssert(added) << "The lemma was already in cache. Probably there is something wrong with theory combination...";
271		}
272	2	return false;
273		}
274	13336	return true;
275		}
276
277	1602	void TheoryArith::notifyRestart(){
278	1602	d_internal->notifyRestart();
279	1602	}
280
281	12744	void TheoryArith::presolve(){
282	12744	d_internal->presolve();
283	12744	if (d_nonlinearExtension != nullptr)
284		{
285	5492	d_nonlinearExtension->presolve();
286		}
287	12744	}
288
289	806665	EqualityStatus TheoryArith::getEqualityStatus(TNode a, TNode b) {
290	806665	return d_internal->getEqualityStatus(a,b);
291		}
292
293	2850	Node TheoryArith::getModelValue(TNode var) {
294	2850	return d_internal->getModelValue( var );
295		}
296
297	4830	std::pair<bool, Node> TheoryArith::entailmentCheck(TNode lit)
298		{
299	9660	ArithEntailmentCheckParameters def;
300	4830	def.addLookupRowSumAlgorithms();
301	9660	ArithEntailmentCheckSideEffects ase;
302	4830	std::pair<bool, Node> res = d_internal->entailmentCheck(lit, def, ase);
303	9660	return res;
304		}
305	8954	eq::ProofEqEngine* TheoryArith::getProofEqEngine()
306		{
307	8954	return d_im.getProofEqEngine();
308		}
309
310		} // namespace arith
311		} // namespace theory
312	27735	} // namespace cvc5