From a1624b7f5b7809329845f4a31e7b6a0e86ebc9d3 Mon Sep 17 00:00:00 2001 From: Andrew Reynolds Date: Thu, 27 May 2021 18:22:28 -0500 Subject: [PATCH] Fix regular expression aggressive elim (#6627) Fixes #6620, fixes #6622. Fixes cvc5/cvc5-projects#254. The benchmarks from the 2 issues timeout, a regression is added for the projects issue. --- src/theory/strings/regexp_elim.cpp | 7 ++++++- test/regress/CMakeLists.txt | 1 + test/regress/regress1/strings/proj254-re-elim-agg.smt2 | 10 ++++++++++ 3 files changed, 17 insertions(+), 1 deletion(-) create mode 100644 test/regress/regress1/strings/proj254-re-elim-agg.smt2 diff --git a/src/theory/strings/regexp_elim.cpp b/src/theory/strings/regexp_elim.cpp index ac0e487f9..45b1f62fb 100644 --- a/src/theory/strings/regexp_elim.cpp +++ b/src/theory/strings/regexp_elim.cpp @@ -400,6 +400,12 @@ Node RegExpElimination::eliminateConcat(Node atom, bool isAgg) { sStartIndex = lens; } + else if (r == 1 && sConstraints.size() == 2) + { + // first and last children cannot overlap + Node bound = nm->mkNode(GEQ, sss, sStartIndex); + sConstraints.push_back(bound); + } sLength = nm->mkNode(MINUS, sLength, lens); } if (r == 1 && !sConstraints.empty()) @@ -417,7 +423,6 @@ Node RegExpElimination::eliminateConcat(Node atom, bool isAgg) } if (!sConstraints.empty()) { - Assert(rexpElimChildren.size() + sConstraints.size() == nchildren); Node ss = nm->mkNode(STRING_SUBSTR, x, sStartIndex, sLength); Assert(!rexpElimChildren.empty()); Node regElim = utils::mkConcat(rexpElimChildren, nm->regExpType()); diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt index 422acd048..e10b89c79 100644 --- a/test/regress/CMakeLists.txt +++ b/test/regress/CMakeLists.txt @@ -2133,6 +2133,7 @@ set(regress_1_tests regress1/strings/pierre150331.smt2 regress1/strings/policy_variable.smt2 regress1/strings/pre_ctn_no_skolem_share.smt2 + regress1/strings/proj254-re-elim-agg.smt2 regress1/strings/query4674.smt2 regress1/strings/query8485.smt2 regress1/strings/re-all-char-hard.smt2 diff --git a/test/regress/regress1/strings/proj254-re-elim-agg.smt2 b/test/regress/regress1/strings/proj254-re-elim-agg.smt2 new file mode 100644 index 000000000..cd19dc114 --- /dev/null +++ b/test/regress/regress1/strings/proj254-re-elim-agg.smt2 @@ -0,0 +1,10 @@ +(set-logic ALL) +(set-info :status sat) +(set-option :produce-models true) +(set-option :strings-exp true) +(set-option :re-elim true) +(set-option :re-elim-agg true) +(declare-fun a () String) +(assert (str.in_re a (re.++ (re.+ (str.to_re "AB")) (str.to_re "B")))) +(assert (<= (str.len a) 4)) +(check-sat) -- 2.30.2