Add option --snorm-infer-eq to infer equalities based on normalization in ArithCongruenceManager at standard effort (disabled by default).

3 files changed, 109 insertions, 21 deletions

diff --git a/src/options/arith_options b/src/options/arith_options
index 9f4003004..f38e377ba 100644
--- a/src/options/arith_options
+++ b/src/options/arith_options
@@ -162,4 +162,7 @@ option pbRewrites --pb-rewrites bool :default false
 option pbRewriteThreshold --pb-rewrite-threshold int :default 256
  threshold of number of pseudoboolean variables to have before doing rewrites
 
+option sNormInferEq --snorm-infer-eq bool :default false
+ infer equalities based on Shostak normalization
+
 endmodule
diff --git a/src/theory/arith/congruence_manager.cpp b/src/theory/arith/congruence_manager.cpp
index 833565c9e..cb8cd8dca 100644
--- a/src/theory/arith/congruence_manager.cpp
+++ b/src/theory/arith/congruence_manager.cpp
@@ -2,7 +2,7 @@
 /*! \file congruence_manager.cpp
  ** \verbatim
  ** Top contributors (to current version):
- **   Tim King, Dejan Jovanovic, Morgan Deters
+ **   Tim King, Dejan Jovanovic, Morgan Deters, Andrew Reynolds
  ** This file is part of the CVC4 project.
  ** Copyright (c) 2009-2016 by the authors listed in the file AUTHORS
  ** in the top-level source directory) and their institutional affiliations.
@@ -15,27 +15,14 @@
  ** \todo document this file
  **/
 
-/*! \file congruence_manager.cpp
- ** \verbatim
- ** Original author: Tim King
- ** Major contributors: none
- ** Minor contributors (to current version): Morgan Deters, Dejan Jovanovic
- ** This file is part of the CVC4 project.
- ** Copyright (c) 2009-2014  New York University and The University of Iowa
- ** See the file COPYING in the top-level source directory for licensing
- ** information.\endverbatim
- **
- ** \brief [[ Add one-line brief description here ]]
- **
- ** [[ Add lengthier description here ]]
- ** \todo document this file
- **/
 #include "theory/arith/congruence_manager.h"
 
 #include "base/output.h"
 #include "smt/smt_statistics_registry.h"
 #include "theory/arith/arith_utilities.h"
 #include "theory/arith/constraint.h"
+#include "theory/quantifiers/equality_infer.h"
+#include "options/arith_options.h"
 
 namespace CVC4 {
 namespace theory {
@@ -45,6 +32,8 @@ ArithCongruenceManager::ArithCongruenceManager(context::Context* c, ConstraintDa
   : d_inConflict(c),
     d_raiseConflict(raiseConflict),
     d_notify(*this),
+    d_eq_infer(NULL),
+    d_eqi_counter(0,c),
     d_keepAlive(c),
     d_propagatations(c),
     d_explanationMap(c),
@@ -52,7 +41,19 @@ ArithCongruenceManager::ArithCongruenceManager(context::Context* c, ConstraintDa
     d_setupLiteral(setup),
     d_avariables(avars),
     d_ee(d_notify, c, "theory::arith::ArithCongruenceManager", true)
-{}
+{
+  //module to infer additional equalities based on normalization
+  if( options::sNormInferEq() ){
+    d_eq_infer = new quantifiers::EqualityInference(c, true);
+    d_true = NodeManager::currentNM()->mkConst( true );
+  }
+}
+
+ArithCongruenceManager::~ArithCongruenceManager() {
+  if( d_eq_infer ){
+    delete d_eq_infer;
+  }
+}
 
 ArithCongruenceManager::Statistics::Statistics():
   d_watchedVariables("theory::arith::congruence::watchedVariables", 0),
@@ -115,10 +116,12 @@ void ArithCongruenceManager::ArithCongruenceNotify::eqNotifyConstantTermMerge(TN
   }
 }
 void ArithCongruenceManager::ArithCongruenceNotify::eqNotifyNewClass(TNode t) {
+  d_acm.eqNotifyNewClass(t);
 }
 void ArithCongruenceManager::ArithCongruenceNotify::eqNotifyPreMerge(TNode t1, TNode t2) {
 }
 void ArithCongruenceManager::ArithCongruenceNotify::eqNotifyPostMerge(TNode t1, TNode t2) {
+  d_acm.eqNotifyPostMerge(t1,t2);
 }
 void ArithCongruenceManager::ArithCongruenceNotify::eqNotifyDisequal(TNode t1, TNode t2, TNode reason) {
 }
@@ -314,9 +317,9 @@ bool ArithCongruenceManager::propagate(TNode x){
     c->setEqualityEngineProof();
   }else if(c->hasProof() && x != rewritten){
     if(c->assertedToTheTheory()){
-      pushBack(x, rewritten, c->getWitness());
+      pushBack(x);
     }else{
-      pushBack(x, rewritten);
+      pushBack(x);
     }
   }else{
     Assert(c->hasProof() && x == rewritten);
@@ -356,8 +359,24 @@ Node ArithCongruenceManager::explainInternal(TNode internal){
     return conjunction;
   }
 }
+
+void ArithCongruenceManager::eqNotifyNewClass(TNode t) {
+  if( d_eq_infer ){
+    d_eq_infer->eqNotifyNewClass(t);
+    fixpointInfer();
+  }
+}
+void ArithCongruenceManager::eqNotifyPostMerge(TNode t1, TNode t2) {
+  if( d_eq_infer ){
+    d_eq_infer->eqNotifyMerge(t1, t2);
+    fixpointInfer();
+  }
+}
+
 Node ArithCongruenceManager::explain(TNode external){
+  Trace("arith-ee") << "Ask for explanation of " << external << std::endl;
   Node internal = externalToInternal(external);
+  Trace("arith-ee") << "...internal = " << internal << std::endl;
   return explainInternal(internal);
 }
 
@@ -393,6 +412,7 @@ void ArithCongruenceManager::assertionToEqualityEngine(bool isEquality, ArithVar
   TNode eq = d_watchedEqualities[s];
   Assert(eq.getKind() == kind::EQUAL);
 
+  Trace("arith-ee") << "Assert " << eq << ", pol " << isEquality << ", reason " << reason << std::endl;
   if(isEquality){
     d_ee.assertEquality(eq, true, reason);
   }else{
@@ -418,6 +438,7 @@ void ArithCongruenceManager::equalsConstant(ConstraintCP c){
   Node reason = c->externalExplainByAssertions();
   d_keepAlive.push_back(reason);
 
+  Trace("arith-ee") << "Assert equalsConstant " << eq << ", reason " << reason << std::endl;
   d_ee.assertEquality(eq, true, reason);
 }
 
@@ -441,7 +462,7 @@ void ArithCongruenceManager::equalsConstant(ConstraintCP lb, ConstraintCP ub){
   d_keepAlive.push_back(eq);
   d_keepAlive.push_back(reason);
 
-
+  Trace("arith-ee") << "Assert equalsConstant2 " << eq << ", reason " << reason << std::endl;
   d_ee.assertEquality(eq, true, reason);
 }
 
@@ -449,6 +470,55 @@ void ArithCongruenceManager::addSharedTerm(Node x){
   d_ee.addTriggerTerm(x, THEORY_ARITH);
 }
 
+bool ArithCongruenceManager::fixpointInfer() {
+  if( d_eq_infer ){
+    while(! inConflict() && d_eqi_counter.get()<d_eq_infer->getNumPendingMerges() ) {
+      Trace("snorm-infer-eq-debug") << "Processing " << d_eqi_counter.get() << " / " << d_eq_infer->getNumPendingMerges() << std::endl;
+      Node eq = d_eq_infer->getPendingMerge( d_eqi_counter.get() );
+      Trace("snorm-infer-eq") << "ArithCongruenceManager : Infer by normalization : " << eq << std::endl;
+      if( !d_ee.areEqual( eq[0], eq[1] ) ){
+        Node eq_exp = d_eq_infer->getPendingMergeExplanation( d_eqi_counter.get() );
+        Trace("snorm-infer-eq") << "           explanation : " << eq_exp << std::endl;
+        //regress explanation
+        std::vector<TNode> assumptions;
+        if( eq_exp.getKind()==kind::AND ){
+          for( unsigned i=0; i<eq_exp.getNumChildren(); i++ ){
+            explain( eq_exp[i], assumptions );
+          }
+        }else if( eq_exp.getKind()==kind::EQUAL ){
+          explain( eq_exp, assumptions );
+        }else{
+          //eq_exp should be true
+          Assert( eq_exp==d_true );
+        }
+        Node req_exp;
+        if( assumptions.empty() ){
+          req_exp = d_true;
+        }else{
+          std::set<TNode> assumptionSet;
+          assumptionSet.insert(assumptions.begin(), assumptions.end());
+          if( assumptionSet.size()==1 ){
+            req_exp = assumptions[0];
+          }else{
+            NodeBuilder<> conjunction(kind::AND);
+            enqueueIntoNB(assumptionSet, conjunction);
+            req_exp = conjunction;
+          }
+        }
+        Trace("snorm-infer-eq") << " regressed explanation : " << req_exp << std::endl;
+        d_ee.assertEquality( eq, true, req_exp );
+        d_keepAlive.push_back( req_exp );
+      }else{
+        Trace("snorm-infer-eq") << "...already equal." << std::endl;
+      }
+      d_eqi_counter = d_eqi_counter.get() + 1;
+    }
+  }
+  return inConflict();
+}
+
+
+
 }/* CVC4::theory::arith namespace */
 }/* CVC4::theory namespace */
 }/* CVC4 namespace */
diff --git a/src/theory/arith/congruence_manager.h b/src/theory/arith/congruence_manager.h
index 32e683509..a02f36a0f 100644
--- a/src/theory/arith/congruence_manager.h
+++ b/src/theory/arith/congruence_manager.h
@@ -2,7 +2,7 @@
 /*! \file congruence_manager.h
  ** \verbatim
  ** Top contributors (to current version):
- **   Tim King, Morgan Deters, Dejan Jovanovic
+ **   Tim King, Morgan Deters, Dejan Jovanovic, Andrew Reynolds
  ** This file is part of the CVC4 project.
  ** Copyright (c) 2009-2016 by the authors listed in the file AUTHORS
  ** in the top-level source directory) and their institutional affiliations.
@@ -33,6 +33,11 @@
 
 namespace CVC4 {
 namespace theory {
+
+namespace quantifiers {
+class EqualityInference;
+}
+
 namespace arith {
 
 class ArithCongruenceManager {
@@ -69,6 +74,11 @@ private:
     void eqNotifyDisequal(TNode t1, TNode t2, TNode reason);
   };
   ArithCongruenceNotify d_notify;
+  
+  /** module for shostak normalization, d_eqi_counter is how many pending merges in d_eq_infer we have processed */
+  quantifiers::EqualityInference * d_eq_infer;
+  context::CDO< unsigned > d_eqi_counter;
+  Node d_true;
 
   context::CDList<Node> d_keepAlive;
 
@@ -127,9 +137,12 @@ private:
 
   Node explainInternal(TNode internal);
 
+  void eqNotifyNewClass(TNode t);
+  void eqNotifyPostMerge(TNode t1, TNode t2);
 public:
 
   ArithCongruenceManager(context::Context* satContext, ConstraintDatabase&, SetupLiteralCallBack, const ArithVariables&, RaiseEqualityEngineConflict raiseConflict);
+  ~ArithCongruenceManager();
 
   Node explain(TNode literal);
   void explain(TNode lit, NodeBuilder<>& out);
@@ -160,6 +173,8 @@ public:
 
   void addSharedTerm(Node x);
 
+  /** process inferred equalities based on Shostak normalization */
+  bool fixpointInfer();
 private:
   class Statistics {
   public: