Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/arith/nl/nonlinear_extension.cpp	Lines:	280	313	89.5 %
Date:	2021-11-05	Branches:	483	943	51.2 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Gereon Kremer, Tim King
 *
 * 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.
 * ****************************************************************************
 *
 * [[ Add one-line brief description here ]]
 *
 * [[ Add lengthier description here ]]
 * \todo document this file
 */

#include "theory/arith/nl/nonlinear_extension.h"

#include "options/arith_options.h"
#include "options/smt_options.h"
#include "theory/arith/arith_state.h"
#include "theory/arith/bound_inference.h"
#include "theory/arith/inference_manager.h"
#include "theory/arith/nl/nl_lemma_utils.h"
#include "theory/arith/theory_arith.h"
#include "theory/ext_theory.h"
#include "theory/rewriter.h"
#include "theory/theory_model.h"
#include "util/rational.h"

using namespace cvc5::kind;

namespace cvc5 {
namespace theory {
namespace arith {
namespace nl {

NonlinearExtension::NonlinearExtension(Env& env,
                                       TheoryArith& containing,
                                       ArithState& state)
    : EnvObj(env),
      d_containing(containing),
      d_astate(state),
      d_im(containing.getInferenceManager()),
      d_hasNlTerms(false),
      d_checkCounter(0),
      d_extTheoryCb(state.getEqualityEngine()),
      d_extTheory(env, d_extTheoryCb, d_im),
      d_model(),
      d_trSlv(d_im, d_model, d_env),
      d_extState(d_im, d_model, d_env),
      d_factoringSlv(&d_extState),
      d_monomialBoundsSlv(&d_extState),
      d_monomialSlv(&d_extState),
      d_splitZeroSlv(&d_extState),
      d_tangentPlaneSlv(&d_extState),
      d_cadSlv(d_env, d_im, d_model),
      d_icpSlv(d_im),
      d_iandSlv(env, d_im, state, d_model),
      d_pow2Slv(env, d_im, state, d_model)
{
  d_extTheory.addFunctionKind(kind::NONLINEAR_MULT);
  d_extTheory.addFunctionKind(kind::EXPONENTIAL);
  d_extTheory.addFunctionKind(kind::SINE);
  d_extTheory.addFunctionKind(kind::PI);
  d_extTheory.addFunctionKind(kind::IAND);
  d_extTheory.addFunctionKind(kind::POW2);
  d_true = NodeManager::currentNM()->mkConst(true);
  d_zero = NodeManager::currentNM()->mkConst(Rational(0));
  d_one = NodeManager::currentNM()->mkConst(Rational(1));
  d_neg_one = NodeManager::currentNM()->mkConst(Rational(-1));

  if (d_env.isTheoryProofProducing())
  {
    ProofChecker* pc = d_env.getProofNodeManager()->getChecker();
    d_proofChecker.registerTo(pc);
  }
}

NonlinearExtension::~NonlinearExtension() {}

void NonlinearExtension::preRegisterTerm(TNode n)
{
  // register terms with extended theory, to find extended terms that can be
  // eliminated by context-depedendent simplification.
  d_extTheory.registerTerm(n);
}

void NonlinearExtension::processSideEffect(const NlLemma& se)
{
  d_trSlv.processSideEffect(se);
}

void NonlinearExtension::computeRelevantAssertions(
    const std::vector<Node>& assertions, std::vector<Node>& keep)
{
  const Valuation& v = d_containing.getValuation();
  for (const Node& a : assertions)
  {
    if (v.isRelevant(a))
    {
      keep.emplace_back(a);
    }
  }
  Trace("nl-ext-rlv") << "...relevant assertions: " << keep.size() << "/"
                      << assertions.size() << std::endl;
}

void NonlinearExtension::getAssertions(std::vector<Node>& assertions)
{
  Trace("nl-ext-assert-debug") << "Getting assertions..." << std::endl;
  bool useRelevance = false;
  if (options().arith.nlRlvMode == options::NlRlvMode::INTERLEAVE)
  {
    useRelevance = (d_checkCounter % 2);
  }
  else if (options().arith.nlRlvMode == options::NlRlvMode::ALWAYS)
  {
    useRelevance = true;
  }
  Valuation v = d_containing.getValuation();

  BoundInference bounds;

  std::unordered_set<Node> init_assertions;

  for (Theory::assertions_iterator it = d_containing.facts_begin();
       it != d_containing.facts_end();
       ++it)
  {
    const Assertion& assertion = *it;
    Trace("nl-ext-assert-debug")
        << "Loaded " << assertion.d_assertion << " from theory" << std::endl;
    Node lit = assertion.d_assertion;
    if (useRelevance && !v.isRelevant(lit))
    {
      // not relevant, skip
      continue;
    }
    // if using the bound inference utility
    if (options().arith.nlRlvAssertBounds && bounds.add(lit, false))
    {
      continue;
    }
    init_assertions.insert(lit);
  }

  for (const auto& vb : bounds.get())
  {
    const Bounds& b = vb.second;
    if (!b.lower_bound.isNull())
    {
      init_assertions.insert(b.lower_bound);
    }
    if (!b.upper_bound.isNull())
    {
      init_assertions.insert(b.upper_bound);
    }
  }

  // Try to be "more deterministic" by adding assertions in the order they were
  // given
  for (auto it = d_containing.facts_begin(); it != d_containing.facts_end();
       ++it)
  {
    Node lit = (*it).d_assertion;
    auto iait = init_assertions.find(lit);
    if (iait != init_assertions.end())
    {
      Trace("nl-ext-assert-debug") << "Adding " << lit << std::endl;
      assertions.push_back(lit);
      init_assertions.erase(iait);
    }
  }
  // Now add left over assertions that have been newly created within this
  // function by the code above.
  for (const Node& a : init_assertions)
  {
    Trace("nl-ext-assert-debug") << "Adding " << a << std::endl;
    assertions.push_back(a);
  }
  Trace("nl-ext") << "...keep " << assertions.size() << " / "
                  << d_containing.numAssertions() << " assertions."
                  << std::endl;
}

std::vector<Node> NonlinearExtension::getUnsatisfiedAssertions(
    const std::vector<Node>& assertions)
{
  std::vector<Node> false_asserts;
  for (const auto& lit : assertions)
  {
    Node litv = d_model.computeConcreteModelValue(lit);
    Trace("nl-ext-mv-assert") << "M[[ " << lit << " ]] -> " << litv;
    if (litv != d_true)
    {
      Trace("nl-ext-mv-assert") << " [model-false]";
      false_asserts.push_back(lit);
    }
    Trace("nl-ext-mv-assert") << std::endl;
  }
  return false_asserts;
}

bool NonlinearExtension::checkModel(const std::vector<Node>& assertions)
{
  Trace("nl-ext-cm") << "--- check-model ---" << std::endl;

  // get the presubstitution
  Trace("nl-ext-cm-debug") << "  apply pre-substitution..." << std::endl;
  // Notice that we do not consider relevance here, since assertions were
  // already filtered based on relevance. It is incorrect to filter based on
  // relevance here, since we may have discarded literals that are relevant
  // that are entailed based on the techniques in getAssertions.
  std::vector<Node> passertions = assertions;
  if (options().arith.nlExt == options::NlExtMode::FULL)
  {
    // preprocess the assertions with the trancendental solver
    if (!d_trSlv.preprocessAssertionsCheckModel(passertions))
    {
      return false;
    }
  }
  if (options().arith.nlCad)
  {
    d_cadSlv.constructModelIfAvailable(passertions);
  }

  Trace("nl-ext-cm") << "-----" << std::endl;
  unsigned tdegree = d_trSlv.getTaylorDegree();
  std::vector<NlLemma> lemmas;
  bool ret = d_model.checkModel(passertions, tdegree, lemmas);
  for (const auto& al: lemmas)
  {
    d_im.addPendingLemma(al);
  }
  return ret;
}

void NonlinearExtension::checkFullEffort(std::map<Node, Node>& arithModel,
                                         const std::set<Node>& termSet)
{
  Trace("nl-ext") << "NonlinearExtension::checkFullEffort" << std::endl;

  d_hasNlTerms = true;
  if (options().arith.nlExtRewrites)
  {
    std::vector<Node> nred;
    if (!d_extTheory.doInferences(0, nred))
    {
      Trace("nl-ext") << "...sent no lemmas, # extf to reduce = " << nred.size()
                      << std::endl;
      if (nred.empty())
      {
        d_hasNlTerms = false;
      }
    }
    else
    {
      Trace("nl-ext") << "...sent lemmas." << std::endl;
    }
  }

  if (!hasNlTerms())
  {
    // no non-linear constraints, we are done
    return;
  }
  Trace("nl-ext") << "NonlinearExtension::interceptModel begin" << std::endl;
  d_model.reset(d_containing.getValuation().getModel(), arithModel);
  // run a last call effort check
  Trace("nl-ext") << "interceptModel: do model-based refinement" << std::endl;
  Result::Sat res = modelBasedRefinement(termSet);
  if (res == Result::Sat::SAT)
  {
    Trace("nl-ext") << "interceptModel: do model repair" << std::endl;
    d_approximations.clear();
    d_witnesses.clear();
    // modify the model values
    d_model.getModelValueRepair(arithModel,
                                d_approximations,
                                d_witnesses,
                                options().smt.modelWitnessValue);
  }
}

void NonlinearExtension::finalizeModel(TheoryModel* tm)
{
  Trace("nl-ext") << "NonlinearExtension::finalizeModel" << std::endl;

  for (std::pair<const Node, std::pair<Node, Node>>& a : d_approximations)
  {
    if (a.second.second.isNull())
    {
      tm->recordApproximation(a.first, a.second.first);
    }
    else
    {
      tm->recordApproximation(a.first, a.second.first, a.second.second);
    }
  }
  for (const auto& vw : d_witnesses)
  {
    tm->recordApproximation(vw.first, vw.second);
  }
}

Result::Sat NonlinearExtension::modelBasedRefinement(const std::set<Node>& termSet)
{
  ++(d_stats.d_mbrRuns);
  d_checkCounter++;

  // get the assertions
  std::vector<Node> assertions;
  getAssertions(assertions);

  Trace("nl-ext-mv-assert")
      << "Getting model values... check for [model-false]" << std::endl;
  // get the assertions that are false in the model
  const std::vector<Node> false_asserts = getUnsatisfiedAssertions(assertions);
  Trace("nl-ext") << "# false asserts = " << false_asserts.size() << std::endl;

  // get the extended terms belonging to this theory
  std::vector<Node> xtsAll;
  d_extTheory.getTerms(xtsAll);
  // only consider those that are currently relevant based on the current
  // assertions, i.e. those contained in termSet
  std::vector<Node> xts;
  for (const Node& x : xtsAll)
  {
    if (termSet.find(x) != termSet.end())
    {
      xts.push_back(x);
    }
  }

  if (Trace.isOn("nl-ext-debug"))
  {
    Trace("nl-ext-debug") << "  processing NonlinearExtension::check : "
                          << std::endl;
    Trace("nl-ext-debug") << "     " << false_asserts.size()
                          << " false assertions" << std::endl;
    Trace("nl-ext-debug") << "     " << xts.size()
                          << " extended terms: " << std::endl;
    Trace("nl-ext-debug") << "       ";
    for (unsigned j = 0; j < xts.size(); j++)
    {
      Trace("nl-ext-debug") << xts[j] << " ";
    }
    Trace("nl-ext-debug") << std::endl;
  }

  // compute whether shared terms have correct values
  unsigned num_shared_wrong_value = 0;
  std::vector<Node> shared_term_value_splits;
  // must ensure that shared terms are equal to their concrete value
  Trace("nl-ext-mv") << "Shared terms : " << std::endl;
  for (context::CDList<TNode>::const_iterator its =
           d_containing.shared_terms_begin();
       its != d_containing.shared_terms_end();
       ++its)
  {
    TNode shared_term = *its;
    // compute its value in the model, and its evaluation in the model
    Node stv0 = d_model.computeConcreteModelValue(shared_term);
    Node stv1 = d_model.computeAbstractModelValue(shared_term);
    d_model.printModelValue("nl-ext-mv", shared_term);
    if (stv0 != stv1)
    {
      num_shared_wrong_value++;
      Trace("nl-ext-mv") << "Bad shared term value : " << shared_term
                         << std::endl;
      if (shared_term != stv0)
      {
        // split on the value, this is non-terminating in general, TODO :
        // improve this
        Node eq = shared_term.eqNode(stv0);
        shared_term_value_splits.push_back(eq);
      }
      else
      {
        // this can happen for transcendental functions
        // the problem is that we cannot evaluate transcendental functions
        // (they don't have a rewriter that returns constants)
        // thus, the actual value in their model can be themselves, hence we
        // have no reference point to rule out the current model.  In this
        // case, we may set incomplete below.
      }
    }
  }
  Trace("nl-ext-debug") << "     " << num_shared_wrong_value
                        << " shared terms with wrong model value." << std::endl;
  bool needsRecheck;
  do
  {
    d_model.resetCheck();
    needsRecheck = false;
    // complete_status:
    //   1 : we may answer SAT, -1 : we may not answer SAT, 0 : unknown
    int complete_status = 1;
    // We require a check either if an assertion is false or a shared term has
    // a wrong value
    if (!false_asserts.empty() || num_shared_wrong_value > 0)
    {
      complete_status = num_shared_wrong_value > 0 ? -1 : 0;
      runStrategy(Theory::Effort::EFFORT_FULL, assertions, false_asserts, xts);
      if (d_im.hasSentLemma() || d_im.hasPendingLemma())
      {
        d_im.clearWaitingLemmas();
        return Result::Sat::UNSAT;
      }
    }
    Trace("nl-ext") << "Finished check with status : " << complete_status
                    << std::endl;

    // if we did not add a lemma during check and there is a chance for SAT
    if (complete_status == 0)
    {
      Trace("nl-ext")
          << "Check model based on bounds for irrational-valued functions..."
          << std::endl;
      // check the model based on simple solving of equalities and using
      // error bounds on the Taylor approximation of transcendental functions.
      if (checkModel(assertions))
      {
        complete_status = 1;
      }
      if (d_im.hasUsed())
      {
        d_im.clearWaitingLemmas();
        return Result::Sat::UNSAT;
      }
    }

    // if we have not concluded SAT
    if (complete_status != 1)
    {
      // flush the waiting lemmas
      if (d_im.hasWaitingLemma())
      {
        std::size_t count = d_im.numWaitingLemmas();
        d_im.flushWaitingLemmas();
        Trace("nl-ext") << "...added " << count << " waiting lemmas."
                        << std::endl;
        return Result::Sat::UNSAT;
      }
      // resort to splitting on shared terms with their model value
      // if we did not add any lemmas
      if (num_shared_wrong_value > 0)
      {
        complete_status = -1;
        if (!shared_term_value_splits.empty())
        {
          for (const Node& eq : shared_term_value_splits)
          {
            Node req = Rewriter::rewrite(eq);
            Node literal = d_containing.getValuation().ensureLiteral(req);
            d_containing.getOutputChannel().requirePhase(literal, true);
            Trace("nl-ext-debug") << "Split on : " << literal << std::endl;
            Node split = literal.orNode(literal.negate());
            d_im.addPendingLemma(split,
                                 InferenceId::ARITH_NL_SHARED_TERM_VALUE_SPLIT,
                                 nullptr,
                                 true);
          }
          if (d_im.hasWaitingLemma())
          {
            d_im.flushWaitingLemmas();
            Trace("nl-ext") << "...added " << d_im.numPendingLemmas()
                            << " shared term value split lemmas." << std::endl;
            return Result::Sat::UNSAT;
          }
        }
        else
        {
          // this can happen if we are trying to do theory combination with
          // trancendental functions
          // since their model value cannot even be computed exactly
        }
      }

      // we are incomplete
      if (options().arith.nlExt == options::NlExtMode::FULL
          && options().arith.nlExtIncPrecision && d_model.usedApproximate())
      {
        d_trSlv.incrementTaylorDegree();
        needsRecheck = true;
        // increase precision for PI?
        // Difficult since Taylor series is very slow to converge
        Trace("nl-ext") << "...increment Taylor degree to "
                        << d_trSlv.getTaylorDegree() << std::endl;
      }
      else
      {
        Trace("nl-ext") << "...failed to send lemma in "
                           "NonLinearExtension, set incomplete"
                        << std::endl;
        d_containing.getOutputChannel().setIncomplete(IncompleteId::ARITH_NL);
        return Result::Sat::SAT_UNKNOWN;
      }
    }
    d_im.clearWaitingLemmas();
  } while (needsRecheck);

  // did not add lemmas
  return Result::Sat::SAT;
}

void NonlinearExtension::runStrategy(Theory::Effort effort,
                                     const std::vector<Node>& assertions,
                                     const std::vector<Node>& false_asserts,
                                     const std::vector<Node>& xts)
{
  ++(d_stats.d_checkRuns);

  if (Trace.isOn("nl-strategy"))
  {
    for (const auto& a : assertions)
    {
      Trace("nl-strategy") << "Input assertion: " << a << std::endl;
    }
  }
  if (!d_strategy.isStrategyInit())
  {
    d_strategy.initializeStrategy(options());
  }

  auto steps = d_strategy.getStrategy();
  bool stop = false;
  while (!stop && steps.hasNext())
  {
    InferStep step = steps.next();
    Trace("nl-strategy") << "Step " << step << std::endl;
    switch (step)
    {
      case InferStep::BREAK: stop = d_im.hasPendingLemma(); break;
      case InferStep::FLUSH_WAITING_LEMMAS: d_im.flushWaitingLemmas(); break;
      case InferStep::CAD_FULL: d_cadSlv.checkFull(); break;
      case InferStep::CAD_INIT: d_cadSlv.initLastCall(assertions); break;
      case InferStep::NL_FACTORING:
        d_factoringSlv.check(assertions, false_asserts);
        break;
      case InferStep::IAND_INIT:
        d_iandSlv.initLastCall(assertions, false_asserts, xts);
        break;
      case InferStep::IAND_FULL: d_iandSlv.checkFullRefine(); break;
      case InferStep::IAND_INITIAL: d_iandSlv.checkInitialRefine(); break;
      case InferStep::POW2_INIT:
        d_pow2Slv.initLastCall(assertions, false_asserts, xts);
        break;
      case InferStep::POW2_FULL: d_pow2Slv.checkFullRefine(); break;
      case InferStep::POW2_INITIAL: d_pow2Slv.checkInitialRefine(); break;
      case InferStep::ICP:
        d_icpSlv.reset(assertions);
        d_icpSlv.check();
        break;
      case InferStep::NL_INIT:
        d_extState.init(xts);
        d_monomialBoundsSlv.init();
        d_monomialSlv.init(xts);
        break;
      case InferStep::NL_MONOMIAL_INFER_BOUNDS:
        d_monomialBoundsSlv.checkBounds(assertions, false_asserts);
        break;
      case InferStep::NL_MONOMIAL_MAGNITUDE0:
        d_monomialSlv.checkMagnitude(0);
        break;
      case InferStep::NL_MONOMIAL_MAGNITUDE1:
        d_monomialSlv.checkMagnitude(1);
        break;
      case InferStep::NL_MONOMIAL_MAGNITUDE2:
        d_monomialSlv.checkMagnitude(2);
        break;
      case InferStep::NL_MONOMIAL_SIGN: d_monomialSlv.checkSign(); break;
      case InferStep::NL_RESOLUTION_BOUNDS:
        d_monomialBoundsSlv.checkResBounds();
        break;
      case InferStep::NL_SPLIT_ZERO: d_splitZeroSlv.check(); break;
      case InferStep::NL_TANGENT_PLANES: d_tangentPlaneSlv.check(false); break;
      case InferStep::NL_TANGENT_PLANES_WAITING:
        d_tangentPlaneSlv.check(true);
        break;
      case InferStep::TRANS_INIT:
        d_trSlv.initLastCall(xts);
        break;
      case InferStep::TRANS_INITIAL:
        d_trSlv.checkTranscendentalInitialRefine();
        break;
      case InferStep::TRANS_MONOTONIC:
        d_trSlv.checkTranscendentalMonotonic();
        break;
      case InferStep::TRANS_TANGENT_PLANES:
        d_trSlv.checkTranscendentalTangentPlanes();
        break;
    }
  }

  Trace("nl-ext") << "finished strategy" << std::endl;
  Trace("nl-ext") << "  ...finished with " << d_im.numWaitingLemmas()
                  << " waiting lemmas." << std::endl;
  Trace("nl-ext") << "  ...finished with " << d_im.numPendingLemmas()
                  << " pending lemmas." << std::endl;
}

}  // namespace nl
}  // 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, Gereon Kremer, Tim King
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		* [[ Add one-line brief description here ]]
14		*
15		* [[ Add lengthier description here ]]
16		* \todo document this file
17		*/
18
19		#include "theory/arith/nl/nonlinear_extension.h"
20
21		#include "options/arith_options.h"
22		#include "options/smt_options.h"
23		#include "theory/arith/arith_state.h"
24		#include "theory/arith/bound_inference.h"
25		#include "theory/arith/inference_manager.h"
26		#include "theory/arith/nl/nl_lemma_utils.h"
27		#include "theory/arith/theory_arith.h"
28		#include "theory/ext_theory.h"
29		#include "theory/rewriter.h"
30		#include "theory/theory_model.h"
31		#include "util/rational.h"
32
33		using namespace cvc5::kind;
34
35		namespace cvc5 {
36		namespace theory {
37		namespace arith {
38		namespace nl {
39
40	9700	NonlinearExtension::NonlinearExtension(Env& env,
41		TheoryArith& containing,
42	9700	ArithState& state)
43		: EnvObj(env),
44		d_containing(containing),
45		d_astate(state),
46	9700	d_im(containing.getInferenceManager()),
47		d_hasNlTerms(false),
48		d_checkCounter(0),
49		d_extTheoryCb(state.getEqualityEngine()),
50	9700	d_extTheory(env, d_extTheoryCb, d_im),
51		d_model(),
52		d_trSlv(d_im, d_model, d_env),
53		d_extState(d_im, d_model, d_env),
54		d_factoringSlv(&d_extState),
55		d_monomialBoundsSlv(&d_extState),
56		d_monomialSlv(&d_extState),
57		d_splitZeroSlv(&d_extState),
58		d_tangentPlaneSlv(&d_extState),
59		d_cadSlv(d_env, d_im, d_model),
60		d_icpSlv(d_im),
61		d_iandSlv(env, d_im, state, d_model),
62	29100	d_pow2Slv(env, d_im, state, d_model)
63		{
64	9700	d_extTheory.addFunctionKind(kind::NONLINEAR_MULT);
65	9700	d_extTheory.addFunctionKind(kind::EXPONENTIAL);
66	9700	d_extTheory.addFunctionKind(kind::SINE);
67	9700	d_extTheory.addFunctionKind(kind::PI);
68	9700	d_extTheory.addFunctionKind(kind::IAND);
69	9700	d_extTheory.addFunctionKind(kind::POW2);
70	9700	d_true = NodeManager::currentNM()->mkConst(true);
71	9700	d_zero = NodeManager::currentNM()->mkConst(Rational(0));
72	9700	d_one = NodeManager::currentNM()->mkConst(Rational(1));
73	9700	d_neg_one = NodeManager::currentNM()->mkConst(Rational(-1));
74
75	9700	if (d_env.isTheoryProofProducing())
76		{
77	4682	ProofChecker* pc = d_env.getProofNodeManager()->getChecker();
78	4682	d_proofChecker.registerTo(pc);
79		}
80	9700	}
81
82	19394	NonlinearExtension::~NonlinearExtension() {}
83
84	440640	void NonlinearExtension::preRegisterTerm(TNode n)
85		{
86		// register terms with extended theory, to find extended terms that can be
87		// eliminated by context-depedendent simplification.
88	440640	d_extTheory.registerTerm(n);
89	440640	}
90
91		void NonlinearExtension::processSideEffect(const NlLemma& se)
92		{
93		d_trSlv.processSideEffect(se);
94		}
95
96		void NonlinearExtension::computeRelevantAssertions(
97		const std::vector<Node>& assertions, std::vector<Node>& keep)
98		{
99		const Valuation& v = d_containing.getValuation();
100		for (const Node& a : assertions)
101		{
102		if (v.isRelevant(a))
103		{
104		keep.emplace_back(a);
105		}
106		}
107		Trace("nl-ext-rlv") << "...relevant assertions: " << keep.size() << "/"
108		<< assertions.size() << std::endl;
109		}
110
111	4708	void NonlinearExtension::getAssertions(std::vector<Node>& assertions)
112		{
113	4708	Trace("nl-ext-assert-debug") << "Getting assertions..." << std::endl;
114	4708	bool useRelevance = false;
115	4708	if (options().arith.nlRlvMode == options::NlRlvMode::INTERLEAVE)
116		{
117	622	useRelevance = (d_checkCounter % 2);
118		}
119	4086	else if (options().arith.nlRlvMode == options::NlRlvMode::ALWAYS)
120		{
121	31	useRelevance = true;
122		}
123	4708	Valuation v = d_containing.getValuation();
124
125	9416	BoundInference bounds;
126
127	9416	std::unordered_set<Node> init_assertions;
128
129	558561	for (Theory::assertions_iterator it = d_containing.facts_begin();
130	558561	it != d_containing.facts_end();
131		++it)
132		{
133	553853	const Assertion& assertion = *it;
134	1107706	Trace("nl-ext-assert-debug")
135	553853	<< "Loaded " << assertion.d_assertion << " from theory" << std::endl;
136	849604	Node lit = assertion.d_assertion;
137	553853	if (useRelevance && !v.isRelevant(lit))
138		{
139		// not relevant, skip
140	2172	continue;
141		}
142		// if using the bound inference utility
143	551681	if (options().arith.nlRlvAssertBounds && bounds.add(lit, false))
144		{
145	255930	continue;
146		}
147	295751	init_assertions.insert(lit);
148		}
149
150	138429	for (const auto& vb : bounds.get())
151		{
152	133721	const Bounds& b = vb.second;
153	133721	if (!b.lower_bound.isNull())
154		{
155	88657	init_assertions.insert(b.lower_bound);
156		}
157	133721	if (!b.upper_bound.isNull())
158		{
159	77467	init_assertions.insert(b.upper_bound);
160		}
161		}
162
163		// Try to be "more deterministic" by adding assertions in the order they were
164		// given
165	558561	for (auto it = d_containing.facts_begin(); it != d_containing.facts_end();
166		++it)
167		{
168	1107706	Node lit = (*it).d_assertion;
169	553853	auto iait = init_assertions.find(lit);
170	553853	if (iait != init_assertions.end())
171		{
172	433877	Trace("nl-ext-assert-debug") << "Adding " << lit << std::endl;
173	433877	assertions.push_back(lit);
174	433877	init_assertions.erase(iait);
175		}
176		}
177		// Now add left over assertions that have been newly created within this
178		// function by the code above.
179	6309	for (const Node& a : init_assertions)
180		{
181	1601	Trace("nl-ext-assert-debug") << "Adding " << a << std::endl;
182	1601	assertions.push_back(a);
183		}
184	9416	Trace("nl-ext") << "...keep " << assertions.size() << " / "
185	9416	<< d_containing.numAssertions() << " assertions."
186	4708	<< std::endl;
187	4708	}
188
189	4708	std::vector<Node> NonlinearExtension::getUnsatisfiedAssertions(
190		const std::vector<Node>& assertions)
191		{
192	4708	std::vector<Node> false_asserts;
193	440186	for (const auto& lit : assertions)
194		{
195	870956	Node litv = d_model.computeConcreteModelValue(lit);
196	435478	Trace("nl-ext-mv-assert") << "M[[ " << lit << " ]] -> " << litv;
197	435478	if (litv != d_true)
198		{
199	62854	Trace("nl-ext-mv-assert") << " [model-false]";
200	62854	false_asserts.push_back(lit);
201		}
202	435478	Trace("nl-ext-mv-assert") << std::endl;
203		}
204	4708	return false_asserts;
205		}
206
207	270	bool NonlinearExtension::checkModel(const std::vector<Node>& assertions)
208		{
209	270	Trace("nl-ext-cm") << "--- check-model ---" << std::endl;
210
211		// get the presubstitution
212	270	Trace("nl-ext-cm-debug") << " apply pre-substitution..." << std::endl;
213		// Notice that we do not consider relevance here, since assertions were
214		// already filtered based on relevance. It is incorrect to filter based on
215		// relevance here, since we may have discarded literals that are relevant
216		// that are entailed based on the techniques in getAssertions.
217	540	std::vector<Node> passertions = assertions;
218	270	if (options().arith.nlExt == options::NlExtMode::FULL)
219		{
220		// preprocess the assertions with the trancendental solver
221	247	if (!d_trSlv.preprocessAssertionsCheckModel(passertions))
222		{
223		return false;
224		}
225		}
226	270	if (options().arith.nlCad)
227		{
228	23	d_cadSlv.constructModelIfAvailable(passertions);
229		}
230
231	270	Trace("nl-ext-cm") << "-----" << std::endl;
232	270	unsigned tdegree = d_trSlv.getTaylorDegree();
233	540	std::vector<NlLemma> lemmas;
234	270	bool ret = d_model.checkModel(passertions, tdegree, lemmas);
235	270	for (const auto& al: lemmas)
236		{
237		d_im.addPendingLemma(al);
238		}
239	270	return ret;
240		}
241
242	41496	void NonlinearExtension::checkFullEffort(std::map<Node, Node>& arithModel,
243		const std::set<Node>& termSet)
244		{
245	41496	Trace("nl-ext") << "NonlinearExtension::checkFullEffort" << std::endl;
246
247	41496	d_hasNlTerms = true;
248	41496	if (options().arith.nlExtRewrites)
249		{
250	82992	std::vector<Node> nred;
251	41496	if (!d_extTheory.doInferences(0, nred))
252		{
253	81644	Trace("nl-ext") << "...sent no lemmas, # extf to reduce = " << nred.size()
254	40822	<< std::endl;
255	40822	if (nred.empty())
256		{
257	36788	d_hasNlTerms = false;
258		}
259		}
260		else
261		{
262	674	Trace("nl-ext") << "...sent lemmas." << std::endl;
263		}
264		}
265
266	41496	if (!hasNlTerms())
267		{
268		// no non-linear constraints, we are done
269	36788	return;
270		}
271	4708	Trace("nl-ext") << "NonlinearExtension::interceptModel begin" << std::endl;
272	4708	d_model.reset(d_containing.getValuation().getModel(), arithModel);
273		// run a last call effort check
274	4708	Trace("nl-ext") << "interceptModel: do model-based refinement" << std::endl;
275	4708	Result::Sat res = modelBasedRefinement(termSet);
276	4708	if (res == Result::Sat::SAT)
277		{
278	585	Trace("nl-ext") << "interceptModel: do model repair" << std::endl;
279	585	d_approximations.clear();
280	585	d_witnesses.clear();
281		// modify the model values
282	1170	d_model.getModelValueRepair(arithModel,
283		d_approximations,
284		d_witnesses,
285	585	options().smt.modelWitnessValue);
286		}
287		}
288
289	337	void NonlinearExtension::finalizeModel(TheoryModel* tm)
290		{
291	337	Trace("nl-ext") << "NonlinearExtension::finalizeModel" << std::endl;
292
293	360	for (std::pair<const Node, std::pair<Node, Node>>& a : d_approximations)
294		{
295	23	if (a.second.second.isNull())
296		{
297	23	tm->recordApproximation(a.first, a.second.first);
298		}
299		else
300		{
301		tm->recordApproximation(a.first, a.second.first, a.second.second);
302		}
303		}
304	344	for (const auto& vw : d_witnesses)
305		{
306	7	tm->recordApproximation(vw.first, vw.second);
307		}
308	337	}
309
310	4708	Result::Sat NonlinearExtension::modelBasedRefinement(const std::set<Node>& termSet)
311		{
312	4708	++(d_stats.d_mbrRuns);
313	4708	d_checkCounter++;
314
315		// get the assertions
316	9416	std::vector<Node> assertions;
317	4708	getAssertions(assertions);
318
319	9416	Trace("nl-ext-mv-assert")
320	4708	<< "Getting model values... check for [model-false]" << std::endl;
321		// get the assertions that are false in the model
322	9416	const std::vector<Node> false_asserts = getUnsatisfiedAssertions(assertions);
323	4708	Trace("nl-ext") << "# false asserts = " << false_asserts.size() << std::endl;
324
325		// get the extended terms belonging to this theory
326	9416	std::vector<Node> xtsAll;
327	4708	d_extTheory.getTerms(xtsAll);
328		// only consider those that are currently relevant based on the current
329		// assertions, i.e. those contained in termSet
330	9416	std::vector<Node> xts;
331	39328	for (const Node& x : xtsAll)
332		{
333	34620	if (termSet.find(x) != termSet.end())
334		{
335	33500	xts.push_back(x);
336		}
337		}
338
339	4708	if (Trace.isOn("nl-ext-debug"))
340		{
341		Trace("nl-ext-debug") << " processing NonlinearExtension::check : "
342		<< std::endl;
343		Trace("nl-ext-debug") << " " << false_asserts.size()
344		<< " false assertions" << std::endl;
345		Trace("nl-ext-debug") << " " << xts.size()
346		<< " extended terms: " << std::endl;
347		Trace("nl-ext-debug") << " ";
348		for (unsigned j = 0; j < xts.size(); j++)
349		{
350		Trace("nl-ext-debug") << xts[j] << " ";
351		}
352		Trace("nl-ext-debug") << std::endl;
353		}
354
355		// compute whether shared terms have correct values
356	4708	unsigned num_shared_wrong_value = 0;
357	9416	std::vector<Node> shared_term_value_splits;
358		// must ensure that shared terms are equal to their concrete value
359	4708	Trace("nl-ext-mv") << "Shared terms : " << std::endl;
360	60643	for (context::CDList<TNode>::const_iterator its =
361	4708	d_containing.shared_terms_begin();
362	65351	its != d_containing.shared_terms_end();
363		++its)
364		{
365	121286	TNode shared_term = *its;
366		// compute its value in the model, and its evaluation in the model
367	121286	Node stv0 = d_model.computeConcreteModelValue(shared_term);
368	121286	Node stv1 = d_model.computeAbstractModelValue(shared_term);
369	60643	d_model.printModelValue("nl-ext-mv", shared_term);
370	60643	if (stv0 != stv1)
371		{
372	6586	num_shared_wrong_value++;
373	13172	Trace("nl-ext-mv") << "Bad shared term value : " << shared_term
374	6586	<< std::endl;
375	6586	if (shared_term != stv0)
376		{
377		// split on the value, this is non-terminating in general, TODO :
378		// improve this
379	13140	Node eq = shared_term.eqNode(stv0);
380	6570	shared_term_value_splits.push_back(eq);
381		}
382		else
383		{
384		// this can happen for transcendental functions
385		// the problem is that we cannot evaluate transcendental functions
386		// (they don't have a rewriter that returns constants)
387		// thus, the actual value in their model can be themselves, hence we
388		// have no reference point to rule out the current model. In this
389		// case, we may set incomplete below.
390		}
391		}
392		}
393	9416	Trace("nl-ext-debug") << " " << num_shared_wrong_value
394	4708	<< " shared terms with wrong model value." << std::endl;
395		bool needsRecheck;
396	617	do
397		{
398	4724	d_model.resetCheck();
399	4724	needsRecheck = false;
400		// complete_status:
401		// 1 : we may answer SAT, -1 : we may not answer SAT, 0 : unknown
402	4724	int complete_status = 1;
403		// We require a check either if an assertion is false or a shared term has
404		// a wrong value
405	4724	if (!false_asserts.empty() \|\| num_shared_wrong_value > 0)
406		{
407	4207	complete_status = num_shared_wrong_value > 0 ? -1 : 0;
408	4207	runStrategy(Theory::Effort::EFFORT_FULL, assertions, false_asserts, xts);
409	4207	if (d_im.hasSentLemma() \|\| d_im.hasPendingLemma())
410		{
411	3816	d_im.clearWaitingLemmas();
412	7939	return Result::Sat::UNSAT;
413		}
414		}
415	1816	Trace("nl-ext") << "Finished check with status : " << complete_status
416	908	<< std::endl;
417
418		// if we did not add a lemma during check and there is a chance for SAT
419	908	if (complete_status == 0)
420		{
421	540	Trace("nl-ext")
422	270	<< "Check model based on bounds for irrational-valued functions..."
423	270	<< std::endl;
424		// check the model based on simple solving of equalities and using
425		// error bounds on the Taylor approximation of transcendental functions.
426	270	if (checkModel(assertions))
427		{
428	68	complete_status = 1;
429		}
430	270	if (d_im.hasUsed())
431		{
432		d_im.clearWaitingLemmas();
433		return Result::Sat::UNSAT;
434		}
435		}
436
437		// if we have not concluded SAT
438	908	if (complete_status != 1)
439		{
440		// flush the waiting lemmas
441	323	if (d_im.hasWaitingLemma())
442		{
443	287	std::size_t count = d_im.numWaitingLemmas();
444	287	d_im.flushWaitingLemmas();
445	574	Trace("nl-ext") << "...added " << count << " waiting lemmas."
446	287	<< std::endl;
447	287	return Result::Sat::UNSAT;
448		}
449		// resort to splitting on shared terms with their model value
450		// if we did not add any lemmas
451	36	if (num_shared_wrong_value > 0)
452		{
453	18	complete_status = -1;
454	18	if (!shared_term_value_splits.empty())
455		{
456	88	for (const Node& eq : shared_term_value_splits)
457		{
458	144	Node req = Rewriter::rewrite(eq);
459	144	Node literal = d_containing.getValuation().ensureLiteral(req);
460	72	d_containing.getOutputChannel().requirePhase(literal, true);
461	72	Trace("nl-ext-debug") << "Split on : " << literal << std::endl;
462	144	Node split = literal.orNode(literal.negate());
463	72	d_im.addPendingLemma(split,
464		InferenceId::ARITH_NL_SHARED_TERM_VALUE_SPLIT,
465		nullptr,
466		true);
467		}
468	16	if (d_im.hasWaitingLemma())
469		{
470	14	d_im.flushWaitingLemmas();
471	28	Trace("nl-ext") << "...added " << d_im.numPendingLemmas()
472	14	<< " shared term value split lemmas." << std::endl;
473	14	return Result::Sat::UNSAT;
474		}
475		}
476		else
477		{
478		// this can happen if we are trying to do theory combination with
479		// trancendental functions
480		// since their model value cannot even be computed exactly
481		}
482		}
483
484		// we are incomplete
485	44	if (options().arith.nlExt == options::NlExtMode::FULL
486	22	&& options().arith.nlExtIncPrecision && d_model.usedApproximate())
487		{
488	16	d_trSlv.incrementTaylorDegree();
489	16	needsRecheck = true;
490		// increase precision for PI?
491		// Difficult since Taylor series is very slow to converge
492	32	Trace("nl-ext") << "...increment Taylor degree to "
493	16	<< d_trSlv.getTaylorDegree() << std::endl;
494		}
495		else
496		{
497	12	Trace("nl-ext") << "...failed to send lemma in "
498	6	"NonLinearExtension, set incomplete"
499	6	<< std::endl;
500	6	d_containing.getOutputChannel().setIncomplete(IncompleteId::ARITH_NL);
501	6	return Result::Sat::SAT_UNKNOWN;
502		}
503		}
504	601	d_im.clearWaitingLemmas();
505		} while (needsRecheck);
506
507		// did not add lemmas
508	585	return Result::Sat::SAT;
509		}
510
511	4207	void NonlinearExtension::runStrategy(Theory::Effort effort,
512		const std::vector<Node>& assertions,
513		const std::vector<Node>& false_asserts,
514		const std::vector<Node>& xts)
515		{
516	4207	++(d_stats.d_checkRuns);
517
518	4207	if (Trace.isOn("nl-strategy"))
519		{
520		for (const auto& a : assertions)
521		{
522		Trace("nl-strategy") << "Input assertion: " << a << std::endl;
523		}
524		}
525	4207	if (!d_strategy.isStrategyInit())
526		{
527	540	d_strategy.initializeStrategy(options());
528		}
529
530	4207	auto steps = d_strategy.getStrategy();
531	4207	bool stop = false;
532	139903	while (!stop && steps.hasNext())
533		{
534	67848	InferStep step = steps.next();
535	67848	Trace("nl-strategy") << "Step " << step << std::endl;
536	67848	switch (step)
537		{
538	30463	case InferStep::BREAK: stop = d_im.hasPendingLemma(); break;
539	537	case InferStep::FLUSH_WAITING_LEMMAS: d_im.flushWaitingLemmas(); break;
540	100	case InferStep::CAD_FULL: d_cadSlv.checkFull(); break;
541	100	case InferStep::CAD_INIT: d_cadSlv.initLastCall(assertions); break;
542	428	case InferStep::NL_FACTORING:
543	428	d_factoringSlv.check(assertions, false_asserts);
544	428	break;
545	3432	case InferStep::IAND_INIT:
546	3432	d_iandSlv.initLastCall(assertions, false_asserts, xts);
547	3432	break;
548	495	case InferStep::IAND_FULL: d_iandSlv.checkFullRefine(); break;
549	3432	case InferStep::IAND_INITIAL: d_iandSlv.checkInitialRefine(); break;
550	3367	case InferStep::POW2_INIT:
551	3367	d_pow2Slv.initLastCall(assertions, false_asserts, xts);
552	3367	break;
553	495	case InferStep::POW2_FULL: d_pow2Slv.checkFullRefine(); break;
554	3367	case InferStep::POW2_INITIAL: d_pow2Slv.checkInitialRefine(); break;
555	48	case InferStep::ICP:
556	48	d_icpSlv.reset(assertions);
557	48	d_icpSlv.check();
558	48	break;
559	4188	case InferStep::NL_INIT:
560	4188	d_extState.init(xts);
561	4188	d_monomialBoundsSlv.init();
562	4188	d_monomialSlv.init(xts);
563	4188	break;
564	762	case InferStep::NL_MONOMIAL_INFER_BOUNDS:
565	762	d_monomialBoundsSlv.checkBounds(assertions, false_asserts);
566	762	break;
567	2093	case InferStep::NL_MONOMIAL_MAGNITUDE0:
568	2093	d_monomialSlv.checkMagnitude(0);
569	2093	break;
570	1414	case InferStep::NL_MONOMIAL_MAGNITUDE1:
571	1414	d_monomialSlv.checkMagnitude(1);
572	1414	break;
573	1033	case InferStep::NL_MONOMIAL_MAGNITUDE2:
574	1033	d_monomialSlv.checkMagnitude(2);
575	1033	break;
576	3340	case InferStep::NL_MONOMIAL_SIGN: d_monomialSlv.checkSign(); break;
577		case InferStep::NL_RESOLUTION_BOUNDS:
578		d_monomialBoundsSlv.checkResBounds();
579		break;
580		case InferStep::NL_SPLIT_ZERO: d_splitZeroSlv.check(); break;
581		case InferStep::NL_TANGENT_PLANES: d_tangentPlaneSlv.check(false); break;
582	25	case InferStep::NL_TANGENT_PLANES_WAITING:
583	25	d_tangentPlaneSlv.check(true);
584	25	break;
585	3532	case InferStep::TRANS_INIT:
586	3532	d_trSlv.initLastCall(xts);
587	3532	break;
588	3361	case InferStep::TRANS_INITIAL:
589	3361	d_trSlv.checkTranscendentalInitialRefine();
590	3361	break;
591	1441	case InferStep::TRANS_MONOTONIC:
592	1441	d_trSlv.checkTranscendentalMonotonic();
593	1441	break;
594	395	case InferStep::TRANS_TANGENT_PLANES:
595	395	d_trSlv.checkTranscendentalTangentPlanes();
596	395	break;
597		}
598		}
599
600	4207	Trace("nl-ext") << "finished strategy" << std::endl;
601	8414	Trace("nl-ext") << " ...finished with " << d_im.numWaitingLemmas()
602	4207	<< " waiting lemmas." << std::endl;
603	8414	Trace("nl-ext") << " ...finished with " << d_im.numPendingLemmas()
604	4207	<< " pending lemmas." << std::endl;
605	4207	}
606
607		} // namespace nl
608		} // namespace arith
609		} // namespace theory
610	31125	} // namespace cvc5