From bdaa3049467fd17d3fb95701f7946a4bf0f5206a Mon Sep 17 00:00:00 2001
From: Morgan Deters <mdeters@gmail.com>
Date: Tue, 9 Oct 2012 11:58:08 +0000
Subject: [PATCH] fix beta reduction in both preRewrite() *and* postRewrite(),
 related to bug 417.  oops.  also fix spelling on "rewritting" test

---
 src/theory/uf/theory_uf_rewriter.h            | 34 ++++++++++---------
 .../regress/regress0/rewriterules/Makefile.am |  2 +-
 ...ewritting.smt2 => simulate_rewriting.smt2} |  0
 3 files changed, 19 insertions(+), 17 deletions(-)
 rename test/regress/regress0/rewriterules/{simulate_rewritting.smt2 => simulate_rewriting.smt2} (100%)

diff --git a/src/theory/uf/theory_uf_rewriter.h b/src/theory/uf/theory_uf_rewriter.h
index 50211f1ad..15ac0f605 100644
--- a/src/theory/uf/theory_uf_rewriter.h
+++ b/src/theory/uf/theory_uf_rewriter.h
@@ -53,7 +53,23 @@ public:
       for(TNode::iterator formal = lambda[0].begin(), arg = node.begin(); formal != lambda[0].end(); ++formal, ++arg) {
         // typechecking should ensure that the APPLY_UF is well-typed, correct arity, etc.
         Assert(formal != node.end());
-        substitutions.addSubstitution(*formal, *arg);
+        // This rewrite step is important: if we have (f (f 5)) for
+        // some lambda term f, we want to beta-reduce the inside (f 5)
+        // application first.  Otherwise, we can end up in infinite
+        // recursion, because f's formal (say "x") gives the
+        // substitution "x |-> (f 5)".  Fine, the body of the lambda
+        // gets (f 5) in place for x.  But since the same lambda ("f")
+        // now occurs in the body, it's got the same bound var "x", so
+        // substitution continues and we replace that x by (f 5).  And
+        // then again.  :-(
+        //
+        // We need a better solution for distinguishing bound
+        // variables like this, but for now, handle it by going
+        // inside-out.  (Quantifiers shouldn't ever have this problem,
+        // so long as the bound vars in different quantifiers are kept
+        // different.)
+        Node n = Rewriter::rewrite(*arg);
+        substitutions.addSubstitution(*formal, n);
       }
       return RewriteResponse(REWRITE_DONE, substitutions.apply(lambda[1]));
     }
@@ -77,21 +93,7 @@ public:
       for(TNode::iterator formal = lambda[0].begin(), arg = node.begin(); formal != lambda[0].end(); ++formal, ++arg) {
         // typechecking should ensure that the APPLY_UF is well-typed, correct arity, etc.
         Assert(formal != node.end());
-        // This rewrite step is important: if we have (f (f 5)) for
-        // some lambda term f, we want to beta-reduce the inside (f 5)
-        // application first.  Otherwise, we can end up in infinite
-        // recursion, because f's formal (say "x") gives the
-        // substitution "x |-> (f 5)".  Fine, the body of the lambda
-        // gets (f 5) in place for x.  But since the same lambda ("f")
-        // now occurs in the body, it's got the same bound var "x", so
-        // substitution continues and we replace that x by (f 5).  And
-        // then again.  :-(
-        //
-        // We need a better solution for distinguishing bound
-        // variables like this, but for now, handle it by going
-        // inside-out.  (Quantifiers shouldn't ever have this problem,
-        // so long as the bound vars in different quantifiers are kept
-        // different.)
+        // This rewrite step is important: see note in postRewrite().
         Node n = Rewriter::rewrite(*arg);
         substitutions.addSubstitution(*formal, n);
       }
diff --git a/test/regress/regress0/rewriterules/Makefile.am b/test/regress/regress0/rewriterules/Makefile.am
index 3bcf8e62c..f0d45c283 100644
--- a/test/regress/regress0/rewriterules/Makefile.am
+++ b/test/regress/regress0/rewriterules/Makefile.am
@@ -21,7 +21,7 @@ MAKEFLAGS = -k
 TESTS =	\
 	length_trick.smt2 length_trick2.smt2 length_gen_020.smt2 \
 	datatypes.smt2 datatypes_sat.smt2 set_A_new_fast_tableau-base.smt2 \
-	set_A_new_fast_tableau-base_sat.smt2 relation.smt2 simulate_rewritting.smt2 \
+	set_A_new_fast_tableau-base_sat.smt2 relation.smt2 simulate_rewriting.smt2 \
 	reachability_back_to_the_future.smt2 native_arrays.smt2 reachability_bbttf_eT_arrays.smt2
 
 EXTRA_DIST = $(TESTS)
diff --git a/test/regress/regress0/rewriterules/simulate_rewritting.smt2 b/test/regress/regress0/rewriterules/simulate_rewriting.smt2
similarity index 100%
rename from test/regress/regress0/rewriterules/simulate_rewritting.smt2
rename to test/regress/regress0/rewriterules/simulate_rewriting.smt2
-- 
2.30.2