GCC Code Coverage Report
Directory: . Exec Total Coverage
File: src/theory/quantifiers/sygus/ce_guided_single_inv_sol.h Lines: 1 1 100.0 %
Date: 2021-03-22 Branches: 0 0 0.0 %

Line Exec Source
1
/*********************                                                        */
2
/*! \file ce_guided_single_inv_sol.h
3
 ** \verbatim
4
 ** Top contributors (to current version):
5
 **   Andrew Reynolds, Mathias Preiner
6
 ** This file is part of the CVC4 project.
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.\endverbatim
11
 **
12
 ** \brief utility for reconstructing solutions for single invocation synthesis
13
 **  conjectures
14
 **/
15
16
#include "cvc4_private.h"
17
18
#ifndef CVC4__THEORY__QUANTIFIERS__CE_GUIDED_SINGLE_INV_SOL_H
19
#define CVC4__THEORY__QUANTIFIERS__CE_GUIDED_SINGLE_INV_SOL_H
20
21
#include <map>
22
#include <vector>
23
24
#include "context/cdhashmap.h"
25
#include "expr/dtype.h"
26
#include "expr/node.h"
27
28
namespace CVC4 {
29
namespace theory {
30
31
class QuantifiersEngine;
32
33
namespace quantifiers {
34
35
class CegSingleInv;
36
37
/** CegSingleInvSol
38
 *
39
 * This function implements Figure 5 of "Counterexample-Guided Quantifier
40
 * Instantiation for Synthesis in SMT", Reynolds et al CAV 2015.
41
 *
42
 */
43
2188
class CegSingleInvSol
44
{
45
  friend class CegSingleInv;
46
47
 private:
48
  QuantifiersEngine * d_qe;
49
  std::vector< Node > d_varList;
50
  std::map< Node, int > d_dterm_size;
51
  std::map< Node, int > d_dterm_ite_size;
52
53
 public:
54
  CegSingleInvSol(QuantifiersEngine* qe);
55
  /** reconstruct solution
56
   *
57
   * Returns (if possible) a node that is equivalent to sol those syntax
58
   * matches the grammar corresponding to sygus datatype stn.
59
   * The value reconstructed is set to 1 if we successfully return a node,
60
   * otherwise it is set to -1.
61
   *
62
   * This method quickly tries to match sol to the grammar induced by stn. If
63
   * this fails, we use enumerative techniques to try to repair the solution.
64
   * The number of iterations for this enumeration is bounded by the argument
65
   * enumLimit if it is positive, and unbounded otherwise.
66
   */
67
  Node reconstructSolution(Node sol,
68
                           TypeNode stn,
69
                           int& reconstructed,
70
                           int enumLimit);
71
  /** preregister conjecture
72
   *
73
   * q : the synthesis conjecture this class is for.
74
   * This is used as a heuristic to find terms in the original conjecture which
75
   * may be helpful for using during reconstruction.
76
   */
77
  void preregisterConjecture(Node q);
78
79
 private:
80
  int d_id_count;
81
  int d_root_id;
82
  std::map< int, Node > d_id_node;
83
  std::map< int, TypeNode > d_id_type;
84
  std::map< TypeNode, std::map< Node, int > > d_rcons_to_id;
85
  std::map< TypeNode, std::map< Node, int > > d_rcons_to_status;
86
87
  std::map< int, std::map< Node, std::vector< int > > > d_reconstruct_op;
88
  std::map< int, Node > d_reconstruct;
89
  std::map< int, std::vector< int > > d_parents;
90
91
  std::map< int, std::vector< int > > d_eqc;
92
  std::map< int, int > d_rep;
93
94
  //equivalent terms
95
  std::map< Node, Node > d_eqt_rep;
96
  std::map< Node, std::vector< Node > > d_eqt_eqc;
97
98
  //cache when reconstructing solutions
99
  std::vector< int > d_tmp_fail;
100
  // get reconstructed solution
101
  Node getReconstructedSolution( int id, bool mod_eq = true );
102
103
  // allocate node with type
104
  int allocate( Node n, TypeNode stn );
105
  // term t with sygus type st, returns inducted templated form of t
106
  int collectReconstructNodes( Node t, TypeNode stn, int& status );
107
  bool collectReconstructNodes(int pid,
108
                               std::vector<Node>& ts,
109
                               const DTypeConstructor& dtc,
110
                               std::vector<int>& ids,
111
                               int& status);
112
  bool getPathToRoot( int id );
113
  void setReconstructed( int id, Node n );
114
  //get equivalent terms to n with top symbol k
115
  void getEquivalentTerms( Kind k, Node n, std::vector< Node >& equiv );
116
  //register equivalent terms
117
  void registerEquivalentTerms( Node n );
118
  /** builtin to sygus const
119
   *
120
   * Returns a sygus term of type tn that encodes the builtin constant c.
121
   * If the sygus datatype tn allows any constant, this may return a variable
122
   * with the attribute SygusPrintProxyAttribute that associates it with c.
123
   *
124
   * rcons_depth limits the number of recursive calls when doing accelerated
125
   * constant reconstruction (currently limited to 1000). Notice this is hacky:
126
   * depending upon order of calls, constant rcons may succeed, e.g. 1001, 999
127
   * vs. 999, 1001.
128
   */
129
  Node builtinToSygusConst(Node c, TypeNode tn, int rcons_depth = 0);
130
  /** cache for the above function */
131
  std::map<TypeNode, std::map<Node, Node> > d_builtin_const_to_sygus;
132
  /** sorted list of constants, per type */
133
  std::map<TypeNode, std::vector<Node> > d_const_list;
134
  /** number of positive constants, per type */
135
  std::map<TypeNode, unsigned> d_const_list_pos;
136
  /** list of constructor indices whose operators are identity functions */
137
  std::map<TypeNode, std::vector<int> > d_id_funcs;
138
  /** initialize the above information for sygus type tn */
139
  void registerType(TypeNode tn);
140
  /** get generic base
141
   *
142
   * This returns the builtin term that is the analog of an application of the
143
   * c^th constructor of dt to fresh variables.
144
   */
145
  Node getGenericBase(TypeNode tn, const DType& dt, int c);
146
  /** cache for the above function */
147
  std::map<TypeNode, std::map<int, Node> > d_generic_base;
148
  /** get match
149
   *
150
   * This function attempts to find a substitution for which p = n. If
151
   * successful, this function returns a substitution in the form of s/new_s,
152
   * where:
153
   * s : substitution, where the domain are indices of terms in the sygus
154
   * term database, and
155
   * new_s : the members that were added to s on this call.
156
   * Otherwise, this function returns false and s and new_s are unmodified.
157
   */
158
  bool getMatch(Node p,
159
                Node n,
160
                std::map<int, Node>& s,
161
                std::vector<int>& new_s);
162
  /** get match
163
   *
164
   * This function attempts to find a builtin term that is analog to a value
165
   * of the sygus datatype st that is equivalent to n. If this function returns
166
   * true, then it has found such a term. Then we set:
167
   *   index_found : updated to the constructor index of the sygus term whose
168
   *   analog to equivalent to n.
169
   *   args : builtin terms corresponding to the match, in order.
170
   * Otherwise, this function returns false and index_found and args are
171
   * unmodified.
172
   * For example, for grammar:
173
   *   A -> 0 | 1 | x | +( A, A )
174
   * Given input ( 5 + (x+1) ) and A we would return true, where:
175
   *   index_found is set to 3 and args is set to { 5, x+1 }.
176
   *
177
   * index_exc : (if applicable) exclude a constructor index of st
178
   * index_start : start index of constructors of st to try
179
   */
180
  bool getMatch(Node n,
181
                TypeNode st,
182
                int& index_found,
183
                std::vector<Node>& args,
184
                int index_exc = -1,
185
                int index_start = 0);
186
  /** given a term, construct an equivalent smaller one that respects syntax */
187
  Node minimizeBuiltinTerm(Node n);
188
  /**
189
   * Return the kind of "is less than" for type tn, where tn is either Int or
190
   * BV.
191
   */
192
  static Kind getComparisonKind(TypeNode tn);
193
  /**
194
   * Return the kind of "plus" for type tn, or "minus" if is_neg is true, where
195
   * tn is either Int or BV.
196
   */
197
  static Kind getPlusKind(TypeNode tn, bool is_neg = false);
198
};
199
200
201
}
202
}
203
}
204
205
#endif