From dc0372a91ae46e6fc5ead1f51a1fe033cfd19944 Mon Sep 17 00:00:00 2001 From: Clark Barrett Date: Thu, 15 Nov 2012 02:14:42 +0000 Subject: [PATCH] Fixed another AUFBV model bug. BV equality subtheory needed to do something similar to arrays - limit the set of terms reported to those relevant in the current context. Also removed collectModelInfo from sharedTermsDatabase - doesn't seem to be needed any more. --- src/theory/arrays/theory_arrays.cpp | 27 +--------- src/theory/arrays/theory_arrays.h | 2 - src/theory/bv/bv_subtheory_eq.cpp | 4 +- src/theory/theory.cpp | 31 ++++++++++++ src/theory/theory.h | 10 ++++ src/theory/theory_engine.cpp | 2 +- test/regress/regress0/aufbv/Makefile.am | 1 + test/regress/regress0/aufbv/fuzz15.smt | 67 +++++++++++++++++++++++++ 8 files changed, 114 insertions(+), 30 deletions(-) create mode 100644 test/regress/regress0/aufbv/fuzz15.smt diff --git a/src/theory/arrays/theory_arrays.cpp b/src/theory/arrays/theory_arrays.cpp index 3a109b51a..e079c4010 100644 --- a/src/theory/arrays/theory_arrays.cpp +++ b/src/theory/arrays/theory_arrays.cpp @@ -649,36 +649,11 @@ void TheoryArrays::computeCareGraph() ///////////////////////////////////////////////////////////////////////////// -void TheoryArrays::collectTerms(TNode n, set& termSet) -{ - if (termSet.find(n) != termSet.end()) { - return; - } - termSet.insert(n); - if (n.getType().isBoolean() || !isLeaf(n)) { - for(TNode::iterator child_it = n.begin(); child_it != n.end(); ++child_it) { - collectTerms(*child_it, termSet); - } - } -} - - void TheoryArrays::collectModelInfo( TheoryModel* m, bool fullModel ) { set termSet; - set cache; - // Collect all terms appearing in assertions - context::CDList::const_iterator assert_it = facts_begin(), assert_it_end = facts_end(); - for (; assert_it != assert_it_end; ++assert_it) { - collectTerms(*assert_it, termSet); - } - - // Add terms that are shared terms - context::CDList::const_iterator shared_it = shared_terms_begin(), shared_it_end = shared_terms_end(); - for (; shared_it != shared_it_end; ++shared_it) { - collectTerms(*shared_it, termSet); - } + computeRelevantTerms(termSet); // Add selects that were generated internally context::CDHashSet::iterator internal_it = d_readsInternal.begin(), internal_it_end = d_readsInternal.end(); diff --git a/src/theory/arrays/theory_arrays.h b/src/theory/arrays/theory_arrays.h index 9bf1201f3..65b77f801 100644 --- a/src/theory/arrays/theory_arrays.h +++ b/src/theory/arrays/theory_arrays.h @@ -218,8 +218,6 @@ class TheoryArrays : public Theory { ///////////////////////////////////////////////////////////////////////////// private: - /** Helper function for collectModelInfo */ - void collectTerms(TNode n, std::set& termSet); public: diff --git a/src/theory/bv/bv_subtheory_eq.cpp b/src/theory/bv/bv_subtheory_eq.cpp index e809a2566..f8e6882a9 100644 --- a/src/theory/bv/bv_subtheory_eq.cpp +++ b/src/theory/bv/bv_subtheory_eq.cpp @@ -174,5 +174,7 @@ void EqualitySolver::collectModelInfo(TheoryModel* m) { << *it << ")\n"; } } - m->assertEqualityEngine(&d_equalityEngine); + set termSet; + d_bv->computeRelevantTerms(termSet); + m->assertEqualityEngine(&d_equalityEngine, &termSet); } diff --git a/src/theory/theory.cpp b/src/theory/theory.cpp index 43574f6e4..5dcafff39 100644 --- a/src/theory/theory.cpp +++ b/src/theory/theory.cpp @@ -245,5 +245,36 @@ std::hash_set Theory::currentlySharedTerms() const{ return currentlyShared; } + +void Theory::collectTerms(TNode n, set& termSet) +{ + if (termSet.find(n) != termSet.end()) { + return; + } + termSet.insert(n); + if (n.getKind() == kind::NOT || n.getKind() == kind::EQUAL || !isLeaf(n)) { + for(TNode::iterator child_it = n.begin(); child_it != n.end(); ++child_it) { + collectTerms(*child_it, termSet); + } + } +} + + +void Theory::computeRelevantTerms(set& termSet) +{ + // Collect all terms appearing in assertions + context::CDList::const_iterator assert_it = facts_begin(), assert_it_end = facts_end(); + for (; assert_it != assert_it_end; ++assert_it) { + collectTerms(*assert_it, termSet); + } + + // Add terms that are shared terms + context::CDList::const_iterator shared_it = shared_terms_begin(), shared_it_end = shared_terms_end(); + for (; shared_it != shared_it_end; ++shared_it) { + collectTerms(*shared_it, termSet); + } +} + + }/* CVC4::theory namespace */ }/* CVC4 namespace */ diff --git a/src/theory/theory.h b/src/theory/theory.h index 9cc5058cc..72206afb8 100644 --- a/src/theory/theory.h +++ b/src/theory/theory.h @@ -232,6 +232,16 @@ protected: */ context::CDList d_sharedTerms; + /** + * Helper function for computeRelevantTerms + */ + void collectTerms(TNode n, std::set& termSet); + /** + * Scans the current set of assertions and shared terms top-down until a theory-leaf is reached, and adds all terms found to termSet. + * This is used by collectModelInfo to delimit the set of terms that should be used when constructing a model + */ + void computeRelevantTerms(std::set& termSet); + /** * Construct a Theory. */ diff --git a/src/theory/theory_engine.cpp b/src/theory/theory_engine.cpp index 9d93c6cc0..c32f36275 100644 --- a/src/theory/theory_engine.cpp +++ b/src/theory/theory_engine.cpp @@ -546,7 +546,7 @@ bool TheoryEngine::properExplanation(TNode node, TNode expl) const { void TheoryEngine::collectModelInfo( theory::TheoryModel* m, bool fullModel ){ //have shared term engine collectModelInfo - d_sharedTerms.collectModelInfo( m, fullModel ); + // d_sharedTerms.collectModelInfo( m, fullModel ); // Consult each active theory to get all relevant information // concerning the model. for(TheoryId theoryId = theory::THEORY_FIRST; theoryId < theory::THEORY_LAST; ++theoryId) { diff --git a/test/regress/regress0/aufbv/Makefile.am b/test/regress/regress0/aufbv/Makefile.am index c67ce5b00..aadaf39e7 100644 --- a/test/regress/regress0/aufbv/Makefile.am +++ b/test/regress/regress0/aufbv/Makefile.am @@ -45,6 +45,7 @@ TESTS = \ fuzz11.smt \ fuzz12.smt \ fuzz13.smt \ + fuzz14.smt \ fifo32bc06k08.delta01.smt \ rewrite_bug.smt \ array_rewrite_bug.smt diff --git a/test/regress/regress0/aufbv/fuzz15.smt b/test/regress/regress0/aufbv/fuzz15.smt new file mode 100644 index 000000000..094e7ecf7 --- /dev/null +++ b/test/regress/regress0/aufbv/fuzz15.smt @@ -0,0 +1,67 @@ +(benchmark fuzzsmt +:logic QF_AUFBV +:status sat +:extrafuns ((v0 BitVec[6])) +:extrafuns ((v1 BitVec[2])) +:extrafuns ((v2 BitVec[13])) +:extrafuns ((v3 BitVec[9])) +:extrafuns ((a4 Array[5:15])) +:formula +(let (?e5 bv2[3]) +(let (?e6 (bvand v3 v3)) +(let (?e7 (bvxor (sign_extend[7] v1) ?e6)) +(let (?e8 (bvashr (zero_extend[7] v0) v2)) +(let (?e9 (sign_extend[2] ?e5)) +(let (?e10 (store a4 (extract[4:0] ?e8) (sign_extend[12] ?e5))) +(let (?e11 (store ?e10 (zero_extend[3] v1) (sign_extend[6] ?e6))) +(let (?e12 (store a4 (extract[4:0] ?e7) (sign_extend[6] ?e6))) +(let (?e13 (select ?e10 (zero_extend[2] ?e5))) +(let (?e14 (store ?e10 (sign_extend[3] v1) (zero_extend[10] ?e9))) +(let (?e15 (store ?e11 (sign_extend[3] v1) (sign_extend[6] v3))) +(let (?e16 (ite (bvsge (zero_extend[7] v1) ?e6) bv1[1] bv0[1])) +(let (?e17 (bvcomp ?e8 (sign_extend[4] ?e7))) +(let (?e18 (ite (= bv1[1] (extract[4:4] ?e6)) (zero_extend[2] v2) ?e13)) +(let (?e19 (ite (bvuge ?e8 ?e8) bv1[1] bv0[1])) +(let (?e20 (repeat[1] ?e9)) +(let (?e21 (bvor (zero_extend[6] ?e5) ?e6)) +(let (?e22 (bvnot v3)) +(let (?e23 (bvnand v0 (sign_extend[1] ?e20))) +(flet ($e24 (bvsge v2 (sign_extend[7] ?e23))) +(flet ($e25 (bvsgt (sign_extend[6] v3) ?e13)) +(flet ($e26 (distinct (zero_extend[2] ?e16) ?e5)) +(flet ($e27 (= v1 (sign_extend[1] ?e17))) +(flet ($e28 (bvule ?e8 (zero_extend[4] ?e6))) +(flet ($e29 (bvule (sign_extend[4] ?e7) ?e8)) +(flet ($e30 (bvslt (sign_extend[12] ?e16) ?e8)) +(flet ($e31 (bvsgt ?e6 ?e6)) +(flet ($e32 (bvsgt ?e18 (zero_extend[14] ?e19))) +(flet ($e33 (bvult (zero_extend[3] v1) ?e20)) +(flet ($e34 (distinct v3 (sign_extend[4] ?e9))) +(flet ($e35 (bvule ?e22 (sign_extend[8] ?e17))) +(flet ($e36 (bvule (zero_extend[2] v2) ?e13)) +(flet ($e37 (bvuge ?e18 (sign_extend[9] ?e23))) +(flet ($e38 (= (sign_extend[10] ?e5) v2)) +(flet ($e39 (= ?e13 (zero_extend[2] v2))) +(flet ($e40 (bvslt (sign_extend[8] ?e19) ?e21)) +(flet ($e41 (bvule (sign_extend[5] ?e19) v0)) +(flet ($e42 (if_then_else $e31 $e25 $e27)) +(flet ($e43 (implies $e26 $e41)) +(flet ($e44 (or $e29 $e38)) +(flet ($e45 (or $e42 $e28)) +(flet ($e46 (xor $e30 $e35)) +(flet ($e47 (not $e46)) +(flet ($e48 (if_then_else $e37 $e39 $e33)) +(flet ($e49 (or $e32 $e47)) +(flet ($e50 (xor $e43 $e34)) +(flet ($e51 (not $e44)) +(flet ($e52 (xor $e51 $e48)) +(flet ($e53 (and $e24 $e36)) +(flet ($e54 (or $e53 $e49)) +(flet ($e55 (if_then_else $e45 $e45 $e54)) +(flet ($e56 (if_then_else $e52 $e40 $e50)) +(flet ($e57 (not $e56)) +(flet ($e58 (and $e55 $e55)) +(flet ($e59 (or $e58 $e57)) +$e59 +)))))))))))))))))))))))))))))))))))))))))))))))))))))))) + -- 2.30.2