From 39020386be1c6cb304a5bfd1eaca37af46bb0bfc Mon Sep 17 00:00:00 2001 From: Clark Barrett Date: Sat, 17 Nov 2012 20:54:30 +0000 Subject: [PATCH] Fixed last currently known bug in array models --- src/theory/arrays/theory_arrays.cpp | 137 +++++++++++++++--------- src/theory/arrays/theory_arrays.h | 3 +- src/theory/theory.cpp | 1 + test/regress/regress0/aufbv/Makefile.am | 1 + test/regress/regress0/aufbv/fuzz15.smt | 103 ++++++++++++++++++ 5 files changed, 193 insertions(+), 52 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 e079c4010..f40fea0ba 100644 --- a/src/theory/arrays/theory_arrays.cpp +++ b/src/theory/arrays/theory_arrays.cpp @@ -79,7 +79,6 @@ TheoryArrays::TheoryArrays(context::Context* c, context::UserContext* u, OutputC d_sharedOther(c), d_sharedTerms(c, false), d_reads(c), - d_readsInternal(c), d_decisionRequests(c), d_permRef(c) { @@ -363,7 +362,7 @@ void TheoryArrays::explain(TNode literal, std::vector& assumptions) { * Note: completeness depends on having pre-register called on all the input * terms before starting to instantiate lemmas. */ -void TheoryArrays::preRegisterTermInternal(TNode node, bool internalAssert) +void TheoryArrays::preRegisterTermInternal(TNode node) { if (d_conflict) { return; @@ -422,9 +421,6 @@ void TheoryArrays::preRegisterTermInternal(TNode node, bool internalAssert) Assert(d_equalityEngine.getRepresentative(store) == store); d_infoMap.addIndex(store, node[1]); - if (internalAssert) { - d_readsInternal.insert(node); - } d_reads.push_back(node); Assert((d_isPreRegistered.insert(node), true)); checkRowForIndex(node[1], store); @@ -445,7 +441,7 @@ void TheoryArrays::preRegisterTermInternal(TNode node, bool internalAssert) NodeManager* nm = NodeManager::currentNM(); Node ni = nm->mkNode(kind::SELECT, node, i); if (!d_equalityEngine.hasTerm(ni)) { - preRegisterTermInternal(ni, false); + preRegisterTermInternal(ni); } // Apply RIntro1 Rule @@ -477,7 +473,7 @@ void TheoryArrays::preRegisterTermInternal(TNode node, bool internalAssert) void TheoryArrays::preRegisterTerm(TNode node) { - preRegisterTermInternal(node, false); + preRegisterTermInternal(node); } @@ -653,61 +649,116 @@ void TheoryArrays::collectModelInfo( TheoryModel* m, bool fullModel ) { set termSet; + // Compute terms appearing in assertions and shared terms computeRelevantTerms(termSet); - // Add selects that were generated internally - context::CDHashSet::iterator internal_it = d_readsInternal.begin(), internal_it_end = d_readsInternal.end(); - for (; internal_it != internal_it_end; ++internal_it) { - termSet.insert(*internal_it); - } - - // Go through all equivalence classes and collect relevant arrays and reads + // Compute arrays that we need to produce representatives for and also make sure RIntro1 reads are included in the relevant set of reads + NodeManager* nm = NodeManager::currentNM(); std::vector arrays; - std::map > selects; bool computeRep, isArray; - eq::EqClassesIterator eqcs_i = eq::EqClassesIterator( &d_equalityEngine ); - while( !eqcs_i.isFinished() ){ + eq::EqClassesIterator eqcs_i = eq::EqClassesIterator(&d_equalityEngine); + for (; !eqcs_i.isFinished(); ++eqcs_i) { Node eqc = (*eqcs_i); isArray = eqc.getType().isArray(); + if (!isArray) { + continue; + } computeRep = false; - eq::EqClassIterator eqc_i = eq::EqClassIterator( eqc, &d_equalityEngine ); - while( !eqc_i.isFinished() ){ + eq::EqClassIterator eqc_i = eq::EqClassIterator(eqc, &d_equalityEngine); + for (; !eqc_i.isFinished(); ++eqc_i) { Node n = *eqc_i; // If this EC is an array type and it contains something other than STORE nodes, we have to compute a representative explicitly if (isArray && termSet.find(n) != termSet.end()) { if (n.getKind() == kind::STORE) { // Make sure RIntro1 reads are included - termSet.insert(NodeManager::currentNM()->mkNode(kind::SELECT, n, n[1])); + Node r = nm->mkNode(kind::SELECT, n, n[1]); + Trace("arrays::collectModelInfo") << "TheoryArrays::collectModelInfo, adding RIntro1 read: " << r << endl; + termSet.insert(r); } else if (!computeRep) { arrays.push_back(eqc); computeRep = true; } } - ++eqc_i; } - ++eqcs_i; } - eqcs_i = eq::EqClassesIterator( &d_equalityEngine ); - while( !eqcs_i.isFinished() ){ - Node eqc = (*eqcs_i); - eq::EqClassIterator eqc_i = eq::EqClassIterator( eqc, &d_equalityEngine ); - while( !eqc_i.isFinished() ){ - Node n = *eqc_i; - // If this term is a select, and it appears in an assertion or was derived from one, - // record that the EC rep of its store parameter is being read from using this term - if (n.getKind() == kind::SELECT && termSet.find(n) != termSet.end()) { - selects[d_equalityEngine.getRepresentative(n[0])].push_back(n); + // Now do a fixed-point iteration to get all reads that need to be included because of RIntro2 rule + bool changed; + do { + changed = false; + eqcs_i = eq::EqClassesIterator(&d_equalityEngine); + for (; !eqcs_i.isFinished(); ++eqcs_i) { + Node eqc = (*eqcs_i); + eq::EqClassIterator eqc_i = eq::EqClassIterator(eqc, &d_equalityEngine); + for (; !eqc_i.isFinished(); ++eqc_i) { + Node n = *eqc_i; + if (n.getKind() == kind::SELECT && termSet.find(n) != termSet.end()) { + + // Find all terms equivalent to n[0] and get corresponding read terms + Node array_eqc = d_equalityEngine.getRepresentative(n[0]); + eq::EqClassIterator array_eqc_i = eq::EqClassIterator(array_eqc, &d_equalityEngine); + for (; !array_eqc_i.isFinished(); ++array_eqc_i) { + Node arr = *array_eqc_i; + if (arr.getKind() == kind::STORE && + termSet.find(arr) != termSet.end() && + !d_equalityEngine.areEqual(arr[1],n[1])) { + Node r = nm->mkNode(kind::SELECT, arr, n[1]); + if (termSet.find(r) == termSet.end() && d_equalityEngine.hasTerm(r)) { + Trace("arrays::collectModelInfo") << "TheoryArrays::collectModelInfo, adding RIntro2(a) read: " << r << endl; + termSet.insert(r); + changed = true; + } + r = nm->mkNode(kind::SELECT, arr[0], n[1]); + if (termSet.find(r) == termSet.end() && d_equalityEngine.hasTerm(r)) { + Trace("arrays::collectModelInfo") << "TheoryArrays::collectModelInfo, adding RIntro2(b) read: " << r << endl; + termSet.insert(r); + changed = true; + } + } + } + + // Find all stores in which n[0] appears and get corresponding read terms + const CTNodeList* instores = d_infoMap.getInStores(array_eqc); + size_t it = 0; + for(; it < instores->size(); ++it) { + TNode instore = (*instores)[it]; + Assert(instore.getKind()==kind::STORE); + if (termSet.find(instore) != termSet.end() && + !d_equalityEngine.areEqual(instore[1],n[1])) { + Node r = nm->mkNode(kind::SELECT, instore, n[1]); + if (termSet.find(r) == termSet.end() && d_equalityEngine.hasTerm(r)) { + Trace("arrays::collectModelInfo") << "TheoryArrays::collectModelInfo, adding RIntro2(c) read: " << r << endl; + termSet.insert(r); + changed = true; + } + r = nm->mkNode(kind::SELECT, instore[0], n[1]); + if (termSet.find(r) == termSet.end() && d_equalityEngine.hasTerm(r)) { + Trace("arrays::collectModelInfo") << "TheoryArrays::collectModelInfo, adding RIntro2(d) read: " << r << endl; + termSet.insert(r); + changed = true; + } + } + } + } } - ++eqc_i; } - ++eqcs_i; - } + } while (changed); + // Send the equality engine information to the model m->assertEqualityEngine(&d_equalityEngine, &termSet); - NodeManager* nm = NodeManager::currentNM(); + // Build a list of all the relevant reads, indexed by the store representative + std::map > selects; + set::iterator set_it = termSet.begin(), set_it_end = termSet.end(); + for (; set_it != set_it_end; ++set_it) { + Node n = *set_it; + // If this term is a select, record that the EC rep of its store parameter is being read from using this term + if (n.getKind() == kind::SELECT) { + selects[d_equalityEngine.getRepresentative(n[0])].push_back(n); + } + } + Node rep; map defValues; map::iterator it; @@ -1235,8 +1286,6 @@ void TheoryArrays::queueRowLemma(RowLemmaType lem) Node i_eq_j = i.eqNode(j); Node reason = nm->mkNode(kind::OR, aj_eq_bj, i_eq_j); d_permRef.push_back(reason); - d_readsInternal.insert(aj); - d_readsInternal.insert(bj); if (!ajExists) { preRegisterTermInternal(aj); } @@ -1279,8 +1328,6 @@ void TheoryArrays::queueRowLemma(RowLemmaType lem) // Make sure that any terms introduced by rewriting are appropriately stored in the equality database Node aj2 = Rewriter::rewrite(aj); if (aj != aj2) { - d_readsInternal.insert(aj); - d_readsInternal.insert(aj2); if (!ajExists) { preRegisterTermInternal(aj); } @@ -1291,8 +1338,6 @@ void TheoryArrays::queueRowLemma(RowLemmaType lem) } Node bj2 = Rewriter::rewrite(bj); if (bj != bj2) { - d_readsInternal.insert(bj); - d_readsInternal.insert(bj2); if (!bjExists) { preRegisterTermInternal(bj); } @@ -1309,8 +1354,6 @@ void TheoryArrays::queueRowLemma(RowLemmaType lem) Node eq1 = aj2.eqNode(bj2); Node eq1_r = Rewriter::rewrite(eq1); if (eq1_r == d_true) { - d_readsInternal.insert(aj2); - d_readsInternal.insert(bj2); if (!d_equalityEngine.hasTerm(aj2)) { preRegisterTermInternal(aj2); } @@ -1385,8 +1428,6 @@ void TheoryArrays::dischargeLemmas() // Make sure that any terms introduced by rewriting are appropriately stored in the equality database Node aj2 = Rewriter::rewrite(aj); if (aj != aj2) { - d_readsInternal.insert(aj); - d_readsInternal.insert(aj2); if (!ajExists) { preRegisterTermInternal(aj); } @@ -1397,8 +1438,6 @@ void TheoryArrays::dischargeLemmas() } Node bj2 = Rewriter::rewrite(bj); if (bj != bj2) { - d_readsInternal.insert(bj); - d_readsInternal.insert(bj2); if (!bjExists) { preRegisterTermInternal(bj); } @@ -1415,8 +1454,6 @@ void TheoryArrays::dischargeLemmas() Node eq1 = aj2.eqNode(bj2); Node eq1_r = Rewriter::rewrite(eq1); if (eq1_r == d_true) { - d_readsInternal.insert(aj2); - d_readsInternal.insert(bj2); if (!d_equalityEngine.hasTerm(aj2)) { preRegisterTermInternal(aj2); } diff --git a/src/theory/arrays/theory_arrays.h b/src/theory/arrays/theory_arrays.h index 65b77f801..eaa3ca431 100644 --- a/src/theory/arrays/theory_arrays.h +++ b/src/theory/arrays/theory_arrays.h @@ -178,7 +178,7 @@ class TheoryArrays : public Theory { context::CDHashSet d_isPreRegistered; /** Helper for preRegisterTerm, also used internally */ - void preRegisterTermInternal(TNode n, bool internalAssert = true); + void preRegisterTermInternal(TNode n); public: @@ -335,7 +335,6 @@ class TheoryArrays : public Theory { context::CDHashSet d_sharedOther; context::CDO d_sharedTerms; context::CDList d_reads; - context::CDHashSet d_readsInternal; std::hash_map d_diseqCache; // The decision requests we have for the core diff --git a/src/theory/theory.cpp b/src/theory/theory.cpp index 5dcafff39..f8e2ec777 100644 --- a/src/theory/theory.cpp +++ b/src/theory/theory.cpp @@ -251,6 +251,7 @@ void Theory::collectTerms(TNode n, set& termSet) if (termSet.find(n) != termSet.end()) { return; } + Trace("theory::collectTerms") << "Theory::collectTerms: adding " << n << endl; 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) { diff --git a/test/regress/regress0/aufbv/Makefile.am b/test/regress/regress0/aufbv/Makefile.am index 564f5cd56..23dabffcb 100644 --- a/test/regress/regress0/aufbv/Makefile.am +++ b/test/regress/regress0/aufbv/Makefile.am @@ -47,6 +47,7 @@ TESTS = \ fuzz12.smt \ fuzz13.smt \ fuzz14.smt \ + fuzz15.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..83950d3c5 --- /dev/null +++ b/test/regress/regress0/aufbv/fuzz15.smt @@ -0,0 +1,103 @@ +(benchmark fuzzsmt +:logic QF_AUFBV +:status sat +:extrafuns ((v0 BitVec[12])) +:extrafuns ((a1 Array[10:2])) +:formula +(let (?e2 bv62635[16]) +(let (?e3 (bvand ?e2 ?e2)) +(let (?e4 (bvnand v0 v0)) +(let (?e5 (store a1 (extract[9:0] v0) (extract[5:4] ?e3))) +(let (?e6 (store ?e5 (extract[10:1] ?e4) (extract[10:9] ?e4))) +(let (?e7 (select ?e5 (extract[10:1] v0))) +(let (?e8 (select ?e6 (extract[14:5] ?e3))) +(let (?e9 (store ?e5 (extract[15:6] ?e3) (extract[11:10] ?e2))) +(let (?e10 (select ?e6 (sign_extend[8] ?e8))) +(let (?e11 (select ?e5 (extract[9:0] ?e4))) +(let (?e12 (bvnot v0)) +(let (?e13 (zero_extend[10] ?e10)) +(let (?e14 (bvsub ?e2 (sign_extend[14] ?e8))) +(let (?e15 (bvsmod (sign_extend[10] ?e8) ?e13)) +(let (?e16 (bvurem ?e14 ?e14)) +(let (?e17 (ite (= ?e15 ?e12) bv1[1] bv0[1])) +(let (?e18 (bvadd (sign_extend[14] ?e7) ?e3)) +(let (?e19 (sign_extend[3] ?e13)) +(let (?e20 (bvurem (zero_extend[11] ?e17) ?e12)) +(let (?e21 (sign_extend[8] ?e11)) +(let (?e22 (bvxnor (zero_extend[4] ?e4) ?e14)) +(flet ($e23 (bvult ?e22 (sign_extend[4] v0))) +(flet ($e24 (bvsge ?e18 (sign_extend[4] ?e4))) +(flet ($e25 (bvsgt ?e2 (sign_extend[4] ?e15))) +(flet ($e26 (bvsge ?e22 (sign_extend[4] ?e15))) +(flet ($e27 (= ?e20 ?e12)) +(flet ($e28 (distinct (sign_extend[10] ?e7) ?e12)) +(flet ($e29 (distinct (zero_extend[13] ?e7) ?e19)) +(flet ($e30 (bvsgt ?e2 (sign_extend[4] ?e4))) +(flet ($e31 (bvult ?e2 (zero_extend[4] v0))) +(flet ($e32 (bvslt (zero_extend[10] ?e8) ?e12)) +(flet ($e33 (bvslt ?e4 ?e4)) +(flet ($e34 (bvsle ?e15 ?e15)) +(flet ($e35 (bvugt (zero_extend[14] ?e10) ?e2)) +(flet ($e36 (bvult ?e8 ?e7)) +(flet ($e37 (bvugt (sign_extend[14] ?e10) ?e16)) +(flet ($e38 (bvult v0 ?e20)) +(flet ($e39 (bvsgt ?e8 ?e10)) +(flet ($e40 (bvsle (zero_extend[11] ?e17) v0)) +(flet ($e41 (distinct (zero_extend[14] ?e17) ?e19)) +(flet ($e42 (distinct (zero_extend[11] ?e17) ?e20)) +(flet ($e43 (bvule (sign_extend[10] ?e7) ?e12)) +(flet ($e44 (bvsle ?e18 (sign_extend[14] ?e10))) +(flet ($e45 (bvsgt ?e2 ?e14)) +(flet ($e46 (bvult ?e13 v0)) +(flet ($e47 (bvsge ?e20 (zero_extend[11] ?e17))) +(flet ($e48 (bvule (sign_extend[5] ?e21) ?e19)) +(flet ($e49 (bvsgt ?e16 (sign_extend[6] ?e21))) +(flet ($e50 (bvult (sign_extend[14] ?e11) ?e14)) +(flet ($e51 (distinct ?e22 (zero_extend[4] ?e12))) +(flet ($e52 (bvuge (sign_extend[4] ?e12) ?e22)) +(flet ($e53 (bvsgt (sign_extend[2] ?e21) ?e13)) +(flet ($e54 (bvslt (sign_extend[14] ?e8) ?e2)) +(flet ($e55 (bvule ?e13 (zero_extend[10] ?e11))) +(flet ($e56 (= ?e2 ?e14)) +(flet ($e57 (distinct ?e22 ?e3)) +(flet ($e58 (or $e52 $e23)) +(flet ($e59 (implies $e48 $e41)) +(flet ($e60 (if_then_else $e25 $e58 $e37)) +(flet ($e61 (implies $e51 $e32)) +(flet ($e62 (not $e40)) +(flet ($e63 (not $e54)) +(flet ($e64 (and $e34 $e31)) +(flet ($e65 (and $e47 $e59)) +(flet ($e66 (implies $e43 $e28)) +(flet ($e67 (iff $e49 $e65)) +(flet ($e68 (if_then_else $e56 $e53 $e60)) +(flet ($e69 (implies $e57 $e30)) +(flet ($e70 (if_then_else $e69 $e42 $e38)) +(flet ($e71 (iff $e68 $e39)) +(flet ($e72 (xor $e44 $e33)) +(flet ($e73 (implies $e70 $e67)) +(flet ($e74 (or $e45 $e24)) +(flet ($e75 (and $e26 $e74)) +(flet ($e76 (not $e36)) +(flet ($e77 (and $e76 $e71)) +(flet ($e78 (not $e50)) +(flet ($e79 (implies $e46 $e61)) +(flet ($e80 (iff $e66 $e72)) +(flet ($e81 (or $e73 $e29)) +(flet ($e82 (if_then_else $e27 $e77 $e79)) +(flet ($e83 (implies $e35 $e81)) +(flet ($e84 (xor $e62 $e55)) +(flet ($e85 (not $e80)) +(flet ($e86 (iff $e84 $e82)) +(flet ($e87 (implies $e64 $e63)) +(flet ($e88 (implies $e87 $e83)) +(flet ($e89 (if_then_else $e75 $e85 $e88)) +(flet ($e90 (xor $e86 $e78)) +(flet ($e91 (implies $e89 $e90)) +(flet ($e92 (and $e91 (not (= ?e13 bv0[12])))) +(flet ($e93 (and $e92 (not (= ?e13 (bvnot bv0[12]))))) +(flet ($e94 (and $e93 (not (= ?e14 bv0[16])))) +(flet ($e95 (and $e94 (not (= ?e12 bv0[12])))) +$e95 +))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) + -- 2.30.2