From 7ac83bb567ca0f0a45ebe3b4c3dffa0689f9b4b2 Mon Sep 17 00:00:00 2001 From: Andrew Reynolds Date: Wed, 1 May 2019 00:35:14 -0500 Subject: [PATCH] Use total versions of div/mod in re-elim-agg (#2986) --- src/theory/strings/regexp_elim.cpp | 8 ++++++-- test/regress/CMakeLists.txt | 2 ++ .../regress/regress1/strings/re-agg-total1.smt2 | 17 +++++++++++++++++ .../regress/regress1/strings/re-agg-total2.smt2 | 13 +++++++++++++ 4 files changed, 38 insertions(+), 2 deletions(-) create mode 100644 test/regress/regress1/strings/re-agg-total1.smt2 create mode 100644 test/regress/regress1/strings/re-agg-total2.smt2 diff --git a/src/theory/strings/regexp_elim.cpp b/src/theory/strings/regexp_elim.cpp index b6a997629..e132d8e24 100644 --- a/src/theory/strings/regexp_elim.cpp +++ b/src/theory/strings/regexp_elim.cpp @@ -547,11 +547,13 @@ Node RegExpElimination::eliminateStar(Node atom) Node lens = nm->mkNode(STRING_LENGTH, s); lens = Rewriter::rewrite(lens); Assert(lens.isConst()); + Assert(lens.getConst().sgn() > 0); std::vector conj; + // lens is a positive constant, so it is safe to use total div/mod here. Node bound = nm->mkNode( AND, nm->mkNode(LEQ, d_zero, index), - nm->mkNode(LT, index, nm->mkNode(INTS_DIVISION, lenx, lens))); + nm->mkNode(LT, index, nm->mkNode(INTS_DIVISION_TOTAL, lenx, lens))); Node conc = nm->mkNode(STRING_SUBSTR, x, nm->mkNode(MULT, index, lens), lens) .eqNode(s); @@ -559,7 +561,9 @@ Node RegExpElimination::eliminateStar(Node atom) Node bvl = nm->mkNode(BOUND_VAR_LIST, index); Node res = nm->mkNode(FORALL, bvl, body); res = nm->mkNode( - AND, nm->mkNode(INTS_MODULUS, lenx, lens).eqNode(d_zero), res); + AND, + nm->mkNode(INTS_MODULUS_TOTAL, lenx, lens).eqNode(d_zero), + res); // e.g. // x in ("abc")* ---> // forall k. 0 <= k < (len( x ) div 3) => substr(x,3*k,3) = "abc" ^ diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt index 714459a85..8ab86e772 100644 --- a/test/regress/CMakeLists.txt +++ b/test/regress/CMakeLists.txt @@ -1558,6 +1558,8 @@ set(regress_1_tests regress1/strings/nterm-re-inter-sigma.smt2 regress1/strings/pierre150331.smt2 regress1/strings/policy_variable.smt2 + regress1/strings/re-agg-total1.smt2 + regress1/strings/re-agg-total2.smt2 regress1/strings/re-elim-exact.smt2 regress1/strings/re-unsound-080718.smt2 regress1/strings/regexp001.smt2 diff --git a/test/regress/regress1/strings/re-agg-total1.smt2 b/test/regress/regress1/strings/re-agg-total1.smt2 new file mode 100644 index 000000000..440a733b7 --- /dev/null +++ b/test/regress/regress1/strings/re-agg-total1.smt2 @@ -0,0 +1,17 @@ +(set-info :smt-lib-version 2.6) +(set-logic QF_S) +(set-info :status unsat) +(set-option :strings-exp true) +(set-option :re-elim-agg true) +(declare-const x String) +(declare-const y String) + + +(assert (str.in.re x (re.* (str.to.re "ab") ) ) ) +(assert (str.in.re x (re.* (str.to.re "abab") ) ) ) +(assert (str.in.re x (re.* (str.to.re "ababac") ) ) ) + +(assert (> (str.len x) 1) ) + +(check-sat) +(get-model) diff --git a/test/regress/regress1/strings/re-agg-total2.smt2 b/test/regress/regress1/strings/re-agg-total2.smt2 new file mode 100644 index 000000000..e6e9d491a --- /dev/null +++ b/test/regress/regress1/strings/re-agg-total2.smt2 @@ -0,0 +1,13 @@ +(set-info :smt-lib-version 2.6) +(set-logic ALL) +(set-info :status unsat) +(set-option :strings-exp true) +(set-option :re-elim-agg true) +(declare-const x String) +(declare-const y String) +(assert (str.in.re x (re.* (str.to.re "'\r''k'\n'")))) +(assert (str.in.re x (re.* (str.to.re "'\r''k'\n''\r''k'\n'")))) +(assert (> (str.len x) 20)) +(assert (< (str.len x) 25)) +(check-sat) +(get-model) -- 2.30.2