From b7a4d6b22d32728ce1a024e7058be3f80e52a119 Mon Sep 17 00:00:00 2001 From: Andrew Reynolds 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& n1, if (n2[index1].isConst()) { CVC4::String t = n2[index1].getConst(); - 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& 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