Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/arith/nl/nl_lemma_utils.h	Lines:	18	19	94.7 %
Date:	2021-09-06	Branches:	3	8	37.5 %


/******************************************************************************
 * 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.
 * ****************************************************************************
 *
 * Utilities for processing lemmas from the non-linear solver.
 */

#ifndef CVC5__THEORY__ARITH__NL__NL_LEMMA_UTILS_H
#define CVC5__THEORY__ARITH__NL__NL_LEMMA_UTILS_H

#include <tuple>
#include <vector>

#include "expr/node.h"
#include "theory/theory_inference.h"

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

class NlModel;
class NonlinearExtension;

/**
 * The data structure for a single lemma to process by the non-linear solver,
 * including the lemma itself and whether it should be preprocessed (see
 * OutputChannel::lemma).
 *
 * This also includes data structures that encapsulate the side effect of adding
 * this lemma in the non-linear solver. This is used to specify how the state of
 * the non-linear solver should update. This includes:
 * - A set of secant points to record (for transcendental secant plane
 * inferences).
 */
class NlLemma : public SimpleTheoryLemma
{
 public:
  NlLemma(InferenceId inf,
          Node n,
          LemmaProperty p = LemmaProperty::NONE,
          ProofGenerator* pg = nullptr)
      : SimpleTheoryLemma(inf, n, p, pg)
  {
  }
  ~NlLemma() {}

  TrustNode processLemma(LemmaProperty& p) override;

  /** secant points to add
   *
   * A member (tf, d, c) in this vector indicates that point c should be added
   * to the list of secant points for an application of a transcendental
   * function tf for Taylor degree d. This is used for incremental linearization
   * for underapproximation (resp. overapproximations) of convex (resp.
   * concave) regions of transcendental functions. For details, see
   * Cimatti et al., CADE 2017.
   */
  std::vector<std::tuple<Node, unsigned, Node> > d_secantPoint;

  NonlinearExtension* d_nlext;
};
/**
 * Writes a non-linear lemma to a stream.
 */
std::ostream& operator<<(std::ostream& out, NlLemma& n);

struct SortNlModel
{
  SortNlModel()
      : d_nlm(nullptr),
        d_isConcrete(true),
        d_isAbsolute(false),
        d_reverse_order(false)
  {
  }
  /** pointer to the model */
  NlModel* d_nlm;
  /** are we comparing concrete model values? */
  bool d_isConcrete;
  /** are we comparing absolute values? */
  bool d_isAbsolute;
  /** are we in reverse order? */
  bool d_reverse_order;
  /** the comparison */
  bool operator()(Node i, Node j);
};

/**
 * Wrapper for std::sort that uses SortNlModel to sort an iterator range.
 */
template <typename It>
void sortByNlModel(It begin,
                   It end,
                   NlModel* model,
                   bool concrete = true,
                   bool absolute = false,
                   bool reverse = false)
{
  SortNlModel smv;
  smv.d_nlm = model;
  smv.d_isConcrete = concrete;
  smv.d_isAbsolute = absolute;
  smv.d_reverse_order = reverse;
  std::sort(begin, end, smv);
}

struct SortNonlinearDegree
{
  SortNonlinearDegree(const std::map<Node, unsigned>& m) : d_mdegree(m) {}
  /** pointer to the non-linear extension */
  const std::map<Node, unsigned>& d_mdegree;
  /** Get the degree of n in d_mdegree */
  unsigned getDegree(Node n) const;
  /**
   * Sorts by degree of the monomials, where lower degree monomials come
   * first.
   */
  bool operator()(Node i, Node j);
};

/** An argument trie, for computing congruent terms */
class ArgTrie
{
 public:
  /** children of this node */
  std::map<Node, ArgTrie> d_children;
  /** the data of this node */
  Node d_data;
  /**
   * Set d as the data on the node whose path is [args], return either d if
   * that node has no data, or the data that already occurs there.
   */
  Node add(Node d, const std::vector<Node>& args);
};

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

#endif /* CVC5__THEORY__ARITH__NL_LEMMA_UTILS_H */


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		* Utilities for processing lemmas from the non-linear solver.
14		*/
15
16		#ifndef CVC5__THEORY__ARITH__NL__NL_LEMMA_UTILS_H
17		#define CVC5__THEORY__ARITH__NL__NL_LEMMA_UTILS_H
18
19		#include <tuple>
20		#include <vector>
21
22		#include "expr/node.h"
23		#include "theory/theory_inference.h"
24
25		namespace cvc5 {
26		namespace theory {
27		namespace arith {
28		namespace nl {
29
30		class NlModel;
31		class NonlinearExtension;
32
33		/**
34		* The data structure for a single lemma to process by the non-linear solver,
35		* including the lemma itself and whether it should be preprocessed (see
36		* OutputChannel::lemma).
37		*
38		* This also includes data structures that encapsulate the side effect of adding
39		* this lemma in the non-linear solver. This is used to specify how the state of
40		* the non-linear solver should update. This includes:
41		* - A set of secant points to record (for transcendental secant plane
42		* inferences).
43		*/
44		class NlLemma : public SimpleTheoryLemma
45		{
46		public:
47	254	NlLemma(InferenceId inf,
48		Node n,
49		LemmaProperty p = LemmaProperty::NONE,
50		ProofGenerator* pg = nullptr)
51	254	: SimpleTheoryLemma(inf, n, p, pg)
52		{
53	254	}
54	254	~NlLemma() {}
55
56		TrustNode processLemma(LemmaProperty& p) override;
57
58		/** secant points to add
59		*
60		* A member (tf, d, c) in this vector indicates that point c should be added
61		* to the list of secant points for an application of a transcendental
62		* function tf for Taylor degree d. This is used for incremental linearization
63		* for underapproximation (resp. overapproximations) of convex (resp.
64		* concave) regions of transcendental functions. For details, see
65		* Cimatti et al., CADE 2017.
66		*/
67		std::vector<std::tuple<Node, unsigned, Node> > d_secantPoint;
68
69		NonlinearExtension* d_nlext;
70		};
71		/**
72		* Writes a non-linear lemma to a stream.
73		*/
74		std::ostream& operator<<(std::ostream& out, NlLemma& n);
75
76		struct SortNlModel
77		{
78	4345	SortNlModel()
79	4345	: d_nlm(nullptr),
80		d_isConcrete(true),
81		d_isAbsolute(false),
82	4345	d_reverse_order(false)
83		{
84	4345	}
85		/** pointer to the model */
86		NlModel* d_nlm;
87		/** are we comparing concrete model values? */
88		bool d_isConcrete;
89		/** are we comparing absolute values? */
90		bool d_isAbsolute;
91		/** are we in reverse order? */
92		bool d_reverse_order;
93		/** the comparison */
94		bool operator()(Node i, Node j);
95		};
96
97		/**
98		* Wrapper for std::sort that uses SortNlModel to sort an iterator range.
99		*/
100		template <typename It>
101	369	void sortByNlModel(It begin,
102		It end,
103		NlModel* model,
104		bool concrete = true,
105		bool absolute = false,
106		bool reverse = false)
107		{
108	369	SortNlModel smv;
109	369	smv.d_nlm = model;
110	369	smv.d_isConcrete = concrete;
111	369	smv.d_isAbsolute = absolute;
112	369	smv.d_reverse_order = reverse;
113	369	std::sort(begin, end, smv);
114	369	}
115
116		struct SortNonlinearDegree
117		{
118	743	SortNonlinearDegree(const std::map<Node, unsigned>& m) : d_mdegree(m) {}
119		/** pointer to the non-linear extension */
120		const std::map<Node, unsigned>& d_mdegree;
121		/** Get the degree of n in d_mdegree */
122		unsigned getDegree(Node n) const;
123		/**
124		* Sorts by degree of the monomials, where lower degree monomials come
125		* first.
126		*/
127		bool operator()(Node i, Node j);
128		};
129
130		/** An argument trie, for computing congruent terms */
131	8996	class ArgTrie
132		{
133		public:
134		/** children of this node */
135		std::map<Node, ArgTrie> d_children;
136		/** the data of this node */
137		Node d_data;
138		/**
139		* Set d as the data on the node whose path is [args], return either d if
140		* that node has no data, or the data that already occurs there.
141		*/
142		Node add(Node d, const std::vector<Node>& args);
143		};
144
145		} // namespace nl
146		} // namespace arith
147		} // namespace theory
148		} // namespace cvc5
149
150		#endif /* CVC5__THEORY__ARITH__NL_LEMMA_UTILS_H */