1 /********************* */
2 /*! \file model_engine.cpp
3 ** \verbatim
4 ** Top contributors (to current version):
5 ** Andrew Reynolds, Morgan Deters, Kshitij Bansal
6 ** This file is part of the CVC4 project.
7 ** Copyright (c) 2009-2019 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 Implementation of model engine class
13 **/
14
15 #include "theory/quantifiers/fmf/model_engine.h"
16
17 #include "options/quantifiers_options.h"
18 #include "theory/quantifiers/first_order_model.h"
19 #include "theory/quantifiers/fmf/full_model_check.h"
20 #include "theory/quantifiers/instantiate.h"
21 #include "theory/quantifiers/quantifiers_attributes.h"
22 #include "theory/quantifiers/term_database.h"
23 #include "theory/quantifiers/term_util.h"
24 #include "theory/theory_engine.h"
25 #include "theory/uf/equality_engine.h"
26 #include "theory/uf/theory_uf.h"
27 #include "theory/uf/theory_uf_strong_solver.h"
28
29 using namespace std;
30 using namespace CVC4;
31 using namespace CVC4::kind;
32 using namespace CVC4::context;
33 using namespace CVC4::theory;
34 using namespace CVC4::theory::quantifiers;
35 using namespace CVC4::theory::inst;
36
37 //Model Engine constructor
ModelEngine(context::Context * c,QuantifiersEngine * qe)38 ModelEngine::ModelEngine( context::Context* c, QuantifiersEngine* qe ) :
39 QuantifiersModule( qe ),
40 d_incomplete_check(true),
41 d_addedLemmas(0),
42 d_triedLemmas(0),
43 d_totalLemmas(0)
44 {
45
46 }
47
~ModelEngine()48 ModelEngine::~ModelEngine() {
49
50 }
51
needsCheck(Theory::Effort e)52 bool ModelEngine::needsCheck( Theory::Effort e ) {
53 return e==Theory::EFFORT_LAST_CALL;
54 }
55
needsModel(Theory::Effort e)56 QuantifiersModule::QEffort ModelEngine::needsModel(Theory::Effort e)
57 {
58 if( options::mbqiInterleave() ){
59 return QEFFORT_STANDARD;
60 }else{
61 return QEFFORT_MODEL;
62 }
63 }
64
reset_round(Theory::Effort e)65 void ModelEngine::reset_round( Theory::Effort e ) {
66 d_incomplete_check = true;
67 }
check(Theory::Effort e,QEffort quant_e)68 void ModelEngine::check(Theory::Effort e, QEffort quant_e)
69 {
70 bool doCheck = false;
71 if( options::mbqiInterleave() ){
72 doCheck = quant_e == QEFFORT_STANDARD && d_quantEngine->hasAddedLemma();
73 }
74 if( !doCheck ){
75 doCheck = quant_e == QEFFORT_MODEL;
76 }
77 if( doCheck ){
78 Assert( !d_quantEngine->inConflict() );
79 int addedLemmas = 0;
80 FirstOrderModel* fm = d_quantEngine->getModel();
81
82 //the following will test that the model satisfies all asserted universal quantifiers by
83 // (model-based) exhaustive instantiation.
84 double clSet = 0;
85 if( Trace.isOn("model-engine") ){
86 Trace("model-engine") << "---Model Engine Round---" << std::endl;
87 clSet = double(clock())/double(CLOCKS_PER_SEC);
88 }
89
90 Trace("model-engine-debug") << "Verify uf ss is minimal..." << std::endl;
91 //let the strong solver verify that the model is minimal
92 //for debugging, this will if there are terms in the model that the strong solver was not notified of
93 uf::StrongSolverTheoryUF * ufss = ((uf::TheoryUF*)d_quantEngine->getTheoryEngine()->theoryOf( THEORY_UF ))->getStrongSolver();
94 if( !ufss || ufss->debugModel( fm ) ){
95 Trace("model-engine-debug") << "Check model..." << std::endl;
96 d_incomplete_check = false;
97 //print debug
98 if( Trace.isOn("fmf-model-complete") ){
99 Trace("fmf-model-complete") << std::endl;
100 debugPrint("fmf-model-complete");
101 }
102 //successfully built an acceptable model, now check it
103 addedLemmas += checkModel();
104 }else{
105 addedLemmas++;
106 }
107
108 if( Trace.isOn("model-engine") ){
109 double clSet2 = double(clock())/double(CLOCKS_PER_SEC);
110 Trace("model-engine") << "Finished model engine, time = " << (clSet2-clSet) << std::endl;
111 }
112
113 if( addedLemmas==0 ){
114 Trace("model-engine-debug") << "No lemmas added, incomplete = " << ( d_incomplete_check || !d_incomplete_quants.empty() ) << std::endl;
115 //CVC4 will answer SAT or unknown
116 if( Trace.isOn("fmf-consistent") ){
117 Trace("fmf-consistent") << std::endl;
118 debugPrint("fmf-consistent");
119 }
120 }
121 }
122 }
123
checkComplete()124 bool ModelEngine::checkComplete() {
125 return !d_incomplete_check;
126 }
127
checkCompleteFor(Node q)128 bool ModelEngine::checkCompleteFor( Node q ) {
129 return std::find( d_incomplete_quants.begin(), d_incomplete_quants.end(), q )==d_incomplete_quants.end();
130 }
131
registerQuantifier(Node f)132 void ModelEngine::registerQuantifier( Node f ){
133 if( Trace.isOn("fmf-warn") ){
134 bool canHandle = true;
135 for( unsigned i=0; i<f[0].getNumChildren(); i++ ){
136 TypeNode tn = f[0][i].getType();
137 if( !tn.isSort() ){
138 if (!tn.isInterpretedFinite())
139 {
140 if( tn.isInteger() ){
141 if( !options::fmfBound() ){
142 canHandle = false;
143 }
144 }else{
145 canHandle = false;
146 }
147 }
148 }
149 }
150 if( !canHandle ){
151 Trace("fmf-warn") << "Warning : Model Engine : may not be able to answer SAT because of formula : " << f << std::endl;
152 }
153 }
154 }
155
assertNode(Node f)156 void ModelEngine::assertNode( Node f ){
157
158 }
159
optOneQuantPerRound()160 bool ModelEngine::optOneQuantPerRound(){
161 return options::fmfOneQuantPerRound();
162 }
163
164
checkModel()165 int ModelEngine::checkModel(){
166 FirstOrderModel* fm = d_quantEngine->getModel();
167
168 //for debugging, setup
169 for (std::map<TypeNode, std::vector<Node> >::iterator it =
170 fm->getRepSetPtr()->d_type_reps.begin();
171 it != fm->getRepSetPtr()->d_type_reps.end();
172 ++it)
173 {
174 if( it->first.isSort() ){
175 Trace("model-engine") << "Cardinality( " << it->first << " )" << " = " << it->second.size() << std::endl;
176 Trace("model-engine-debug") << " Reps : ";
177 for( size_t i=0; i<it->second.size(); i++ ){
178 Trace("model-engine-debug") << it->second[i] << " ";
179 }
180 Trace("model-engine-debug") << std::endl;
181 Trace("model-engine-debug") << " Term reps : ";
182 for( size_t i=0; i<it->second.size(); i++ ){
183 Node r = d_quantEngine->getInternalRepresentative( it->second[i], Node::null(), 0 );
184 Trace("model-engine-debug") << r << " ";
185 }
186 Trace("model-engine-debug") << std::endl;
187 Node mbt = fm->getModelBasisTerm(it->first);
188 Trace("model-engine-debug") << " Basis term : " << mbt << std::endl;
189 }
190 }
191
192 d_triedLemmas = 0;
193 d_addedLemmas = 0;
194 d_totalLemmas = 0;
195 //for statistics
196 if( Trace.isOn("model-engine") ){
197 for( unsigned i=0; i<fm->getNumAssertedQuantifiers(); i++ ){
198 Node f = fm->getAssertedQuantifier( i );
199 if( d_quantEngine->getModel()->isQuantifierActive( f ) && d_quantEngine->hasOwnership( f, this ) ){
200 int totalInst = 1;
201 for( unsigned j=0; j<f[0].getNumChildren(); j++ ){
202 TypeNode tn = f[0][j].getType();
203 if (fm->getRepSet()->hasType(tn))
204 {
205 totalInst =
206 totalInst * (int)fm->getRepSet()->getNumRepresentatives(tn);
207 }
208 }
209 d_totalLemmas += totalInst;
210 }
211 }
212 }
213
214 Trace("model-engine-debug") << "Do exhaustive instantiation..." << std::endl;
215 // FMC uses two sub-effort levels
216 int e_max = options::mbqiMode() == MBQI_FMC
217 ? 2
218 : (options::mbqiMode() == MBQI_TRUST ? 0 : 1);
219 for( int e=0; e<e_max; e++) {
220 d_incomplete_quants.clear();
221 for( unsigned i=0; i<fm->getNumAssertedQuantifiers(); i++ ){
222 Node q = fm->getAssertedQuantifier( i, true );
223 Trace("fmf-exh-inst") << "-> Exhaustive instantiate " << q << ", effort = " << e << "..." << std::endl;
224 //determine if we should check this quantifier
225 if( d_quantEngine->getModel()->isQuantifierActive( q ) && d_quantEngine->hasOwnership( q, this ) ){
226 exhaustiveInstantiate( q, e );
227 if( d_quantEngine->inConflict() || ( optOneQuantPerRound() && d_addedLemmas>0 ) ){
228 break;
229 }
230 }else{
231 Trace("fmf-exh-inst") << "-> Inactive : " << q << std::endl;
232 }
233 }
234 if( d_addedLemmas>0 ){
235 break;
236 }else{
237 Assert( !d_quantEngine->inConflict() );
238 }
239 }
240
241 //print debug information
242 if( d_quantEngine->inConflict() ){
243 Trace("model-engine") << "Conflict, added lemmas = ";
244 }else{
245 Trace("model-engine") << "Added Lemmas = ";
246 }
247 Trace("model-engine") << d_addedLemmas << " / " << d_triedLemmas << " / ";
248 Trace("model-engine") << d_totalLemmas << std::endl;
249 return d_addedLemmas;
250 }
251
252
253
exhaustiveInstantiate(Node f,int effort)254 void ModelEngine::exhaustiveInstantiate( Node f, int effort ){
255 //first check if the builder can do the exhaustive instantiation
256 quantifiers::QModelBuilder * mb = d_quantEngine->getModelBuilder();
257 unsigned prev_alem = mb->getNumAddedLemmas();
258 unsigned prev_tlem = mb->getNumTriedLemmas();
259 int retEi = mb->doExhaustiveInstantiation( d_quantEngine->getModel(), f, effort );
260 if( retEi!=0 ){
261 if( retEi<0 ){
262 Trace("fmf-exh-inst") << "-> Builder determined complete instantiation was impossible." << std::endl;
263 d_incomplete_quants.push_back( f );
264 }else{
265 Trace("fmf-exh-inst") << "-> Builder determined instantiation(s)." << std::endl;
266 }
267 d_triedLemmas += mb->getNumTriedLemmas()-prev_tlem;
268 d_addedLemmas += mb->getNumAddedLemmas()-prev_alem;
269 d_quantEngine->d_statistics.d_instantiations_fmf_mbqi +=
270 (mb->getNumAddedLemmas() - prev_alem);
271 }else{
272 if( Trace.isOn("fmf-exh-inst-debug") ){
273 Trace("fmf-exh-inst-debug") << " Instantiation Constants: ";
274 for( size_t i=0; i<f[0].getNumChildren(); i++ ){
275 Trace("fmf-exh-inst-debug") << d_quantEngine->getTermUtil()->getInstantiationConstant( f, i ) << " ";
276 }
277 Trace("fmf-exh-inst-debug") << std::endl;
278 }
279 //create a rep set iterator and iterate over the (relevant) domain of the quantifier
280 QRepBoundExt qrbe(d_quantEngine);
281 RepSetIterator riter(d_quantEngine->getModel()->getRepSet(), &qrbe);
282 if( riter.setQuantifier( f ) ){
283 Trace("fmf-exh-inst") << "...exhaustive instantiation set, incomplete=" << riter.isIncomplete() << "..." << std::endl;
284 if( !riter.isIncomplete() ){
285 int triedLemmas = 0;
286 int addedLemmas = 0;
287 EqualityQuery* qy = d_quantEngine->getEqualityQuery();
288 Instantiate* inst = d_quantEngine->getInstantiate();
289 while( !riter.isFinished() && ( addedLemmas==0 || !options::fmfOneInstPerRound() ) ){
290 //instantiation was not shown to be true, construct the match
291 InstMatch m( f );
292 for (unsigned i = 0; i < riter.getNumTerms(); i++)
293 {
294 m.set(qy, i, riter.getCurrentTerm(i));
295 }
296 Debug("fmf-model-eval") << "* Add instantiation " << m << std::endl;
297 triedLemmas++;
298 //add as instantiation
299 if (inst->addInstantiation(f, m, true))
300 {
301 addedLemmas++;
302 if( d_quantEngine->inConflict() ){
303 break;
304 }
305 }else{
306 Debug("fmf-model-eval") << "* Failed Add instantiation " << m << std::endl;
307 }
308 riter.increment();
309 }
310 d_addedLemmas += addedLemmas;
311 d_triedLemmas += triedLemmas;
312 d_quantEngine->d_statistics.d_instantiations_fmf_exh += addedLemmas;
313 }
314 }else{
315 Trace("fmf-exh-inst") << "...exhaustive instantiation did set, incomplete=" << riter.isIncomplete() << "..." << std::endl;
316 }
317 //if the iterator is incomplete, we will return unknown instead of sat if no instantiations are added this round
318 if( riter.isIncomplete() ){
319 d_incomplete_quants.push_back( f );
320 }
321 }
322 }
323
debugPrint(const char * c)324 void ModelEngine::debugPrint( const char* c ){
325 Trace( c ) << "Quantifiers: " << std::endl;
326 for( unsigned i=0; i<d_quantEngine->getModel()->getNumAssertedQuantifiers(); i++ ){
327 Node q = d_quantEngine->getModel()->getAssertedQuantifier( i );
328 if( d_quantEngine->hasOwnership( q, this ) ){
329 Trace( c ) << " ";
330 if( !d_quantEngine->getModel()->isQuantifierActive( q ) ){
331 Trace( c ) << "*Inactive* ";
332 }else{
333 Trace( c ) << " ";
334 }
335 Trace( c ) << q << std::endl;
336 }
337 }
338 //d_quantEngine->getModel()->debugPrint( c );
339 }
340
341