Fixed last currently known bug in array models

5 files changed, 193 insertions, 52 deletions

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<TNode>& 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<Node> termSet;
 
+  // Compute terms appearing in assertions and shared terms
   computeRelevantTerms(termSet);
 
-  // Add selects that were generated internally
-  context::CDHashSet<TNode, TNodeHashFunction>::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<Node> arrays;
-  std::map<Node, std::vector<Node> > 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<Node, std::vector<Node> > selects;
+  set<Node>::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<Node, Node> defValues;
   map<Node, Node>::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<Node, NodeHashFunction > 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<TNode, TNodeHashFunction> d_sharedOther;
   context::CDO<bool> d_sharedTerms;
   context::CDList<TNode> d_reads;
-  context::CDHashSet<TNode, TNodeHashFunction> d_readsInternal;
   std::hash_map<TNode, Node, TNodeHashFunction> 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<Node>& 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
+)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
+