Fix strings rewriter for strip constant endpoint reverse direction (#1424)

3 files changed, 38 insertions, 5 deletions

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)