From b7a4d6b22d32728ce1a024e7058be3f80e52a119 Mon Sep 17 00:00:00 2001
From: Andrew Reynolds <andrew.j.reynolds@gmail.com>
Date: Mon, 4 Dec 2017 14:18:16 -0600
Subject: [PATCH] Fix strings rewriter for strip constant endpoint reverse
 direction (#1424)

---
 .../strings/theory_strings_rewriter.cpp       | 11 ++++---
 test/regress/regress0/strings/Makefile.am     |  3 +-
 .../regress0/strings/strip-endpt-sound.smt2   | 29 +++++++++++++++++++
 3 files changed, 38 insertions(+), 5 deletions(-)
 create mode 100644 test/regress/regress0/strings/strip-endpt-sound.smt2

diff --git a/src/theory/strings/theory_strings_rewriter.cpp b/src/theory/strings/theory_strings_rewriter.cpp
index aab4196cc..5cb58729e 100644
--- a/src/theory/strings/theory_strings_rewriter.cpp
+++ b/src/theory/strings/theory_strings_rewriter.cpp
@@ -2401,7 +2401,7 @@ bool TheoryStringsRewriter::stripConstantEndpoints(std::vector<Node>& n1,
         if (n2[index1].isConst())
         {
           CVC4::String t = n2[index1].getConst<String>();
-          std::size_t ret = s.find(t);
+          std::size_t ret = r == 0 ? s.find(t) : s.rfind(t);
           if (ret == std::string::npos)
           {
             if (n1.size() == 1)
@@ -2423,9 +2423,12 @@ bool TheoryStringsRewriter::stripConstantEndpoints(std::vector<Node>& n1,
           else
           {
             Assert(ret < s.size());
-            // can strip off up to the find position
-            // e.g. str.contains( str.++( "abc", x ), str.++( "b", y ) ) -->
-            // str.contains( str.++( "bc", x ), str.++( "b", y ) )
+            // can strip off up to the find position, e.g.
+            // str.contains( str.++( "abc", x ), str.++( "b", y ) ) -->
+            // str.contains( str.++( "bc", x ), str.++( "b", y ) ),
+            // and
+            // str.contains( str.++( x, "abbd" ), str.++( y, "b" ) ) -->
+            // str.contains( str.++( x, "abb" ), str.++( y, "b" ) )
             overlap = s.size() - ret;
           }
         }
diff --git a/test/regress/regress0/strings/Makefile.am b/test/regress/regress0/strings/Makefile.am
index 99fd2b630..18b07b91d 100644
--- a/test/regress/regress0/strings/Makefile.am
+++ b/test/regress/regress0/strings/Makefile.am
@@ -94,7 +94,8 @@ TESTS = \
   rewrites-v2.smt2 \
   substr-rewrites.smt2 \
   norn-ab.smt2 \
-  type002.smt2
+  type002.smt2 \
+  strip-endpt-sound.smt2
 
 FAILING_TESTS =
 
diff --git a/test/regress/regress0/strings/strip-endpt-sound.smt2 b/test/regress/regress0/strings/strip-endpt-sound.smt2
new file mode 100644
index 000000000..0c1dd123c
--- /dev/null
+++ b/test/regress/regress0/strings/strip-endpt-sound.smt2
@@ -0,0 +1,29 @@
+; COMMAND-LINE: --strings-exp
+; EXPECT: sat
+(set-logic QF_S)
+(declare-fun x () String)
+(declare-fun y () String)
+
+(assert (str.contains "c(ab)" (str.++ x ")")))
+(assert (str.contains "c(ab)" (str.++ "c(" y)))
+
+(declare-fun z () String)
+(declare-fun w () String)
+
+(assert (str.contains "c(ab))" (str.++ z "))")))
+(assert (str.contains z "b"))
+
+(assert (str.contains "c(ab))" (str.++ w "b)")))
+(assert (str.contains w "a"))
+
+
+(declare-fun p () String)
+(declare-fun q () String)
+
+(assert (str.contains "c(aab))" (str.++ "a" p)))
+(assert (str.contains p "a"))
+
+(assert (str.contains "c(abb))" (str.++ q "b")))
+(assert (str.contains q "b"))
+
+(check-sat)
-- 
2.30.2