Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/quantifiers/fmf/bounded_integers.h	Lines:	14	14	100.0 %
Date:	2021-05-24	Branches:	10	16	62.5 %


/******************************************************************************
 * Top contributors (to current version):
 *   Andrew Reynolds, Mathias Preiner, Mudathir Mohamed
 *
 * 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.
 * ****************************************************************************
 *
 * Bounded integers module
 */

#include "cvc5_private.h"

#ifndef CVC5__BOUNDED_INTEGERS_H
#define CVC5__BOUNDED_INTEGERS_H

#include "theory/quantifiers/quant_module.h"

#include "context/cdhashmap.h"
#include "context/context.h"
#include "expr/attribute.h"
#include "theory/decision_strategy.h"
#include "theory/quantifiers/quant_bound_inference.h"

namespace cvc5 {
namespace theory {

class RepSetIterator;
class DecisionManager;

/**
 * Attribute set to 1 for literals that comprise the bounds of a quantified
 * formula. For example, for:
 *   forall x. ( 0 <= x ^ x <= n ) => P( x )
 * the literals 0 <= x and x <= n are marked 1.
 */
struct BoundIntLitAttributeId
{
};
typedef expr::Attribute<BoundIntLitAttributeId, uint64_t> BoundIntLitAttribute;

namespace quantifiers {

class BoundedIntegers : public QuantifiersModule
{
  typedef context::CDHashMap<Node, bool> NodeBoolMap;
  typedef context::CDHashMap<Node, int> NodeIntMap;
  typedef context::CDHashMap<Node, Node> NodeNodeMap;
  typedef context::CDHashMap<int, bool> IntBoolMap;
private:
  //for determining bounds
  bool hasNonBoundVar( Node f, Node b, std::map< Node, bool >& visited );
  bool hasNonBoundVar( Node f, Node b );
  /** The bound type for each quantified formula, variable pair */
  std::map<Node, std::map<Node, BoundVarType>> d_bound_type;
  /**
   * The ordered list of variables that are finitely bound, for each quantified
   * formulas. Variables that occur later in this list may depend on having
   * finite bounds for variables earlier in this list.
   */
  std::map< Node, std::vector< Node > > d_set;
  std::map< Node, std::map< Node, int > > d_set_nums;
  std::map< Node, std::map< Node, Node > > d_range;
  std::map< Node, std::map< Node, Node > > d_nground_range;
  //integer lower/upper bounds
  std::map< Node, std::map< Node, Node > > d_bounds[2];
  //set membership range
  std::map< Node, std::map< Node, Node > > d_setm_range;
  std::map< Node, std::map< Node, Node > > d_setm_range_lit;
  /** set membership element choice functions
   *
   * For each set S and integer n, d_setm_choice[S][n] is the canonical
   * representation for the (n+1)^th member of set S. It is of the form:
   * witness x. (|S| <= n OR ( x in S AND
   *   distinct( x, d_setm_choice[S][0], ..., d_setm_choice[S][n-1] ) ) )
   */
  std::map<Node, std::vector<Node> > d_setm_choice;
  //fixed finite set range
  std::map< Node, std::map< Node, std::vector< Node > > > d_fixed_set_gr_range;
  std::map< Node, std::map< Node, std::vector< Node > > > d_fixed_set_ngr_range;
  void process( Node q, Node n, bool pol,
                std::map< Node, unsigned >& bound_lit_type_map,
                std::map< int, std::map< Node, Node > >& bound_lit_map,
                std::map< int, std::map< Node, bool > >& bound_lit_pol_map,
                std::map< int, std::map< Node, Node > >& bound_int_range_term,
                std::map< Node, std::vector< Node > >& bound_fixed_set );
  bool processEqDisjunct( Node q, Node n, Node& v, std::vector< Node >& v_cases );
  void processMatchBoundVars( Node q, Node n, std::vector< Node >& bvs, std::map< Node, bool >& visited );
  std::vector< Node > d_bound_quants;
private:
 /**
  * This decision strategy is used for minimizing the value of an integer
  * arithmetic term t. It decides positively on literals of the form
  * t < 0, t <= 0, t <= 1, t <=2, and so on.
  */
 class IntRangeDecisionHeuristic : public DecisionStrategyFmf
 {
  public:
   IntRangeDecisionHeuristic(Node r,
                             context::Context* c,
                             context::Context* u,
                             Valuation valuation,
                             bool isProxy);
   /** make the n^th literal of this strategy */
   Node mkLiteral(unsigned n) override;
   /** identify */
   std::string identify() const override
   {
     return std::string("bound_int_range");
   }
   /** Returns the current proxy lemma if one exists (see below). */
   Node proxyCurrentRangeLemma();

  private:
   /** The range we are minimizing */
   Node d_range;
   /** a proxy of the range
    *
    * When option::fmfBoundLazy is enabled, this class uses a lazy strategy
    * for enforcing the bounds on term t by using a fresh variable x of type
    * integer. The point of this variable is to serve as a proxy for t, so
    * that we can decide on literals of the form x <= c instead of t <= c. The
    * advantage of this is that we avoid unfairness, say, if t is constrained
    * to be strictly greater c. Then, at full effort check, we add "proxy
    * lemmas" of the form: (t <= c) <=> (x <= c) for the current minimal
    * upper bound c for x.
    */
   Node d_proxy_range;
   /** ranges that have been proxied
    *
    * This is a user-context-dependent cache that stores which value we have
    * added proxy lemmas for.
    */
   IntBoolMap d_ranges_proxied;
  };
private:
  //information for minimizing ranges
  std::vector< Node > d_ranges;
  /** Decision heuristics for each integer range */
  std::map<Node, std::unique_ptr<IntRangeDecisionHeuristic>> d_rms;

 private:
  //class to store whether bounding lemmas have been added
  class BoundInstTrie
  {
  public:
    std::map< Node, BoundInstTrie > d_children;
    bool hasInstantiated( std::vector< Node > & vals, int index = 0, bool madeNew = false ){
      if( index>=(int)vals.size() ){
        return !madeNew;
      }else{
        Node n = vals[index];
        if( d_children.find(n)==d_children.end() ){
          madeNew = true;
        }
        return d_children[n].hasInstantiated(vals,index+1,madeNew);
      }
    }
  };
  std::map< Node, std::map< Node, BoundInstTrie > > d_bnd_it;

 public:
  BoundedIntegers(QuantifiersState& qs,
                  QuantifiersInferenceManager& qim,
                  QuantifiersRegistry& qr,
                  TermRegistry& tr);
  virtual ~BoundedIntegers();

  void presolve() override;
  bool needsCheck(Theory::Effort e) override;
  void check(Theory::Effort e, QEffort quant_e) override;
  void checkOwnership(Node q) override;
  /**
   * Is v a variable of quantified formula q that this class has inferred to
   * have a finite bound?
   */
  bool isBound(Node q, Node v) const;
  /**
   * Get the type of bound that was inferred for variable v of quantified
   * formula q, or BOUND_NONE if no bound was inferred.
   */
  BoundVarType getBoundVarType(Node q, Node v) const;
  /**
   * Get the indices of bound variables, in the order they should be processed
   * in a RepSetIterator. For example, for q:
   *   forall xyz. 0 <= x < 5 ^ 0 <= z <= x+7 => P(x,y,z)
   * this would add {1,3} to the vector indices, indicating that x has a finite
   * bound, z has a finite bound assuming x has a finite bound, and y does not
   * have a finite bound.
   */
  void getBoundVarIndices(Node q, std::vector<unsigned>& indices) const;
  /**
   * Get bound elements
   *
   * This gets the (finite) enumeration of the range of variable v of quantified
   * formula q and adds it into the vector elements in the context of the
   * iteration being performed by rsi. It returns true if it could successfully
   * determine this range.
   *
   * This method determines the range of a variable depending on the current
   * state of the iterator rsi and flag initial (which is true when rsi is
   * being initialized). For example, if q is:
   *   forall xy. 0 <= x < 5 ^ 0 <= y <= x+7 => P(x,y)
   * v is y, and rsi currently maps x to 4, then we add the elements 0...11 to
   * the vector elements.
   */
  bool getBoundElements(RepSetIterator* rsi,
                        bool initial,
                        Node q,
                        Node v,
                        std::vector<Node>& elements);
  /** Identify this module */
  std::string identify() const override { return "BoundedIntegers"; }

 private:
  /**
   * Set that variable v of quantified formula q has a finite bound, where
   * bound_type indicates how that bound was inferred.
   */
  void setBoundedVar(Node f, Node v, BoundVarType bound_type);
  //for integer range
  Node getLowerBound( Node q, Node v ){ return d_bounds[0][q][v]; }
  Node getUpperBound( Node q, Node v ){ return d_bounds[1][q][v]; }
  void getBounds( Node f, Node v, RepSetIterator * rsi, Node & l, Node & u );
  void getBoundValues( Node f, Node v, RepSetIterator * rsi, Node & l, Node & u );
  bool isGroundRange(Node f, Node v);
  //for set range
  Node getSetRange( Node q, Node v, RepSetIterator * rsi );
  Node getSetRangeValue( Node q, Node v, RepSetIterator * rsi );
  Node matchBoundVar( Node v, Node t, Node e );

  bool getRsiSubsitution( Node q, Node v, std::vector< Node >& vars, std::vector< Node >& subs, RepSetIterator * rsi );
};

}
}
}  // namespace cvc5

#endif


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Andrew Reynolds, Mathias Preiner, Mudathir Mohamed
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		* Bounded integers module
14		*/
15
16		#include "cvc5_private.h"
17
18		#ifndef CVC5__BOUNDED_INTEGERS_H
19		#define CVC5__BOUNDED_INTEGERS_H
20
21		#include "theory/quantifiers/quant_module.h"
22
23		#include "context/cdhashmap.h"
24		#include "context/context.h"
25		#include "expr/attribute.h"
26		#include "theory/decision_strategy.h"
27		#include "theory/quantifiers/quant_bound_inference.h"
28
29		namespace cvc5 {
30		namespace theory {
31
32		class RepSetIterator;
33		class DecisionManager;
34
35		/**
36		* Attribute set to 1 for literals that comprise the bounds of a quantified
37		* formula. For example, for:
38		* forall x. ( 0 <= x ^ x <= n ) => P( x )
39		* the literals 0 <= x and x <= n are marked 1.
40		*/
41		struct BoundIntLitAttributeId
42		{
43		};
44		typedef expr::Attribute<BoundIntLitAttributeId, uint64_t> BoundIntLitAttribute;
45
46		namespace quantifiers {
47
48		class BoundedIntegers : public QuantifiersModule
49		{
50		typedef context::CDHashMap<Node, bool> NodeBoolMap;
51		typedef context::CDHashMap<Node, int> NodeIntMap;
52		typedef context::CDHashMap<Node, Node> NodeNodeMap;
53		typedef context::CDHashMap<int, bool> IntBoolMap;
54		private:
55		//for determining bounds
56		bool hasNonBoundVar( Node f, Node b, std::map< Node, bool >& visited );
57		bool hasNonBoundVar( Node f, Node b );
58		/** The bound type for each quantified formula, variable pair */
59		std::map<Node, std::map<Node, BoundVarType>> d_bound_type;
60		/**
61		* The ordered list of variables that are finitely bound, for each quantified
62		* formulas. Variables that occur later in this list may depend on having
63		* finite bounds for variables earlier in this list.
64		*/
65		std::map< Node, std::vector< Node > > d_set;
66		std::map< Node, std::map< Node, int > > d_set_nums;
67		std::map< Node, std::map< Node, Node > > d_range;
68		std::map< Node, std::map< Node, Node > > d_nground_range;
69		//integer lower/upper bounds
70		std::map< Node, std::map< Node, Node > > d_bounds[2];
71		//set membership range
72		std::map< Node, std::map< Node, Node > > d_setm_range;
73		std::map< Node, std::map< Node, Node > > d_setm_range_lit;
74		/** set membership element choice functions
75		*
76		* For each set S and integer n, d_setm_choice[S][n] is the canonical
77		* representation for the (n+1)^th member of set S. It is of the form:
78		* witness x. (\|S\| <= n OR ( x in S AND
79		* distinct( x, d_setm_choice[S][0], ..., d_setm_choice[S][n-1] ) ) )
80		*/
81		std::map<Node, std::vector<Node> > d_setm_choice;
82		//fixed finite set range
83		std::map< Node, std::map< Node, std::vector< Node > > > d_fixed_set_gr_range;
84		std::map< Node, std::map< Node, std::vector< Node > > > d_fixed_set_ngr_range;
85		void process( Node q, Node n, bool pol,
86		std::map< Node, unsigned >& bound_lit_type_map,
87		std::map< int, std::map< Node, Node > >& bound_lit_map,
88		std::map< int, std::map< Node, bool > >& bound_lit_pol_map,
89		std::map< int, std::map< Node, Node > >& bound_int_range_term,
90		std::map< Node, std::vector< Node > >& bound_fixed_set );
91		bool processEqDisjunct( Node q, Node n, Node& v, std::vector< Node >& v_cases );
92		void processMatchBoundVars( Node q, Node n, std::vector< Node >& bvs, std::map< Node, bool >& visited );
93		std::vector< Node > d_bound_quants;
94		private:
95		/**
96		* This decision strategy is used for minimizing the value of an integer
97		* arithmetic term t. It decides positively on literals of the form
98		* t < 0, t <= 0, t <= 1, t <=2, and so on.
99		*/
100	652	class IntRangeDecisionHeuristic : public DecisionStrategyFmf
101		{
102		public:
103		IntRangeDecisionHeuristic(Node r,
104		context::Context* c,
105		context::Context* u,
106		Valuation valuation,
107		bool isProxy);
108		/** make the n^th literal of this strategy */
109		Node mkLiteral(unsigned n) override;
110		/** identify */
111	262350	std::string identify() const override
112		{
113	262350	return std::string("bound_int_range");
114		}
115		/** Returns the current proxy lemma if one exists (see below). */
116		Node proxyCurrentRangeLemma();
117
118		private:
119		/** The range we are minimizing */
120		Node d_range;
121		/** a proxy of the range
122		*
123		* When option::fmfBoundLazy is enabled, this class uses a lazy strategy
124		* for enforcing the bounds on term t by using a fresh variable x of type
125		* integer. The point of this variable is to serve as a proxy for t, so
126		* that we can decide on literals of the form x <= c instead of t <= c. The
127		* advantage of this is that we avoid unfairness, say, if t is constrained
128		* to be strictly greater c. Then, at full effort check, we add "proxy
129		* lemmas" of the form: (t <= c) <=> (x <= c) for the current minimal
130		* upper bound c for x.
131		*/
132		Node d_proxy_range;
133		/** ranges that have been proxied
134		*
135		* This is a user-context-dependent cache that stores which value we have
136		* added proxy lemmas for.
137		*/
138		IntBoolMap d_ranges_proxied;
139		};
140		private:
141		//information for minimizing ranges
142		std::vector< Node > d_ranges;
143		/** Decision heuristics for each integer range */
144		std::map<Node, std::unique_ptr<IntRangeDecisionHeuristic>> d_rms;
145
146		private:
147		//class to store whether bounding lemmas have been added
148	148	class BoundInstTrie
149		{
150		public:
151		std::map< Node, BoundInstTrie > d_children;
152	2784	bool hasInstantiated( std::vector< Node > & vals, int index = 0, bool madeNew = false ){
153	2784	if( index>=(int)vals.size() ){
154	1252	return !madeNew;
155		}else{
156	3064	Node n = vals[index];
157	1532	if( d_children.find(n)==d_children.end() ){
158	58	madeNew = true;
159		}
160	1532	return d_children[n].hasInstantiated(vals,index+1,madeNew);
161		}
162		}
163		};
164		std::map< Node, std::map< Node, BoundInstTrie > > d_bnd_it;
165
166		public:
167		BoundedIntegers(QuantifiersState& qs,
168		QuantifiersInferenceManager& qim,
169		QuantifiersRegistry& qr,
170		TermRegistry& tr);
171		virtual ~BoundedIntegers();
172
173		void presolve() override;
174		bool needsCheck(Theory::Effort e) override;
175		void check(Theory::Effort e, QEffort quant_e) override;
176		void checkOwnership(Node q) override;
177		/**
178		* Is v a variable of quantified formula q that this class has inferred to
179		* have a finite bound?
180		*/
181		bool isBound(Node q, Node v) const;
182		/**
183		* Get the type of bound that was inferred for variable v of quantified
184		* formula q, or BOUND_NONE if no bound was inferred.
185		*/
186		BoundVarType getBoundVarType(Node q, Node v) const;
187		/**
188		* Get the indices of bound variables, in the order they should be processed
189		* in a RepSetIterator. For example, for q:
190		* forall xyz. 0 <= x < 5 ^ 0 <= z <= x+7 => P(x,y,z)
191		* this would add {1,3} to the vector indices, indicating that x has a finite
192		* bound, z has a finite bound assuming x has a finite bound, and y does not
193		* have a finite bound.
194		*/
195		void getBoundVarIndices(Node q, std::vector<unsigned>& indices) const;
196		/**
197		* Get bound elements
198		*
199		* This gets the (finite) enumeration of the range of variable v of quantified
200		* formula q and adds it into the vector elements in the context of the
201		* iteration being performed by rsi. It returns true if it could successfully
202		* determine this range.
203		*
204		* This method determines the range of a variable depending on the current
205		* state of the iterator rsi and flag initial (which is true when rsi is
206		* being initialized). For example, if q is:
207		* forall xy. 0 <= x < 5 ^ 0 <= y <= x+7 => P(x,y)
208		* v is y, and rsi currently maps x to 4, then we add the elements 0...11 to
209		* the vector elements.
210		*/
211		bool getBoundElements(RepSetIterator* rsi,
212		bool initial,
213		Node q,
214		Node v,
215		std::vector<Node>& elements);
216		/** Identify this module */
217	10764	std::string identify() const override { return "BoundedIntegers"; }
218
219		private:
220		/**
221		* Set that variable v of quantified formula q has a finite bound, where
222		* bound_type indicates how that bound was inferred.
223		*/
224		void setBoundedVar(Node f, Node v, BoundVarType bound_type);
225		//for integer range
226	624	Node getLowerBound( Node q, Node v ){ return d_bounds[0][q][v]; }
227	624	Node getUpperBound( Node q, Node v ){ return d_bounds[1][q][v]; }
228		void getBounds( Node f, Node v, RepSetIterator * rsi, Node & l, Node & u );
229		void getBoundValues( Node f, Node v, RepSetIterator * rsi, Node & l, Node & u );
230		bool isGroundRange(Node f, Node v);
231		//for set range
232		Node getSetRange( Node q, Node v, RepSetIterator * rsi );
233		Node getSetRangeValue( Node q, Node v, RepSetIterator * rsi );
234		Node matchBoundVar( Node v, Node t, Node e );
235
236		bool getRsiSubsitution( Node q, Node v, std::vector< Node >& vars, std::vector< Node >& subs, RepSetIterator * rsi );
237		};
238
239		}
240		}
241		} // namespace cvc5
242
243		#endif