diff options
author | Andrew Reynolds <andrew.j.reynolds@gmail.com> | 2021-05-27 18:22:28 -0500 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-05-27 23:22:28 +0000 |
commit | a1624b7f5b7809329845f4a31e7b6a0e86ebc9d3 (patch) | |
tree | cb05e79b2aba4728d6ec9bbf472fa90666677a67 | |
parent | 29f0b8f378377ed836bddaaf88883d0b2eeb545d (diff) |
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.
-rw-r--r-- | src/theory/strings/regexp_elim.cpp | 7 | ||||
-rw-r--r-- | test/regress/CMakeLists.txt | 1 | ||||
-rw-r--r-- | test/regress/regress1/strings/proj254-re-elim-agg.smt2 | 10 |
3 files changed, 17 insertions, 1 deletions
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) |