diff options
| author | Andrew Reynolds <andrew.j.reynolds@gmail.com> | 2018-02-23 11:18:40 -0600 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2018-02-23 11:18:40 -0600 |
| commit | 86ce6eefaafe0f301feea38276bb364c072c71f0 (patch) | |
| tree | e68d0a57363ca943943029e4c80639cd02b7bdcc | |
| parent | f7a77c4c14af25466e7ce31455a9636e0f8234e3 (diff) | |
Fix cd-simplification for strings (#1624)
| -rw-r--r-- | src/theory/strings/theory_strings.cpp | 21 | ||||
| -rw-r--r-- | test/regress/regress1/strings/Makefile.am | 3 | ||||
| -rw-r--r-- | test/regress/regress1/strings/double-replace.smt2 | 7 |
3 files changed, 27 insertions, 4 deletions
diff --git a/src/theory/strings/theory_strings.cpp b/src/theory/strings/theory_strings.cpp index 6df2a1fdf..17551b528 100644 --- a/src/theory/strings/theory_strings.cpp +++ b/src/theory/strings/theory_strings.cpp @@ -1340,13 +1340,28 @@ void TheoryStrings::checkExtfEval( int effort ) { getExtTheory()->markReduced( n ); Trace("strings-extf-debug") << " resolvable by evaluation..." << std::endl; std::vector< Node > exps; + // The following optimization gets the "symbolic definition" of + // an extended term. The symbolic definition of a term t is a term + // t' where constants are replaced by their corresponding proxy + // variables. + // For example, if lsym is a proxy variable for "", then + // str.replace( lsym, lsym, lsym ) is the symbolic definition for + // str.replace( "", "", "" ). It is generally better to use symbolic + // definitions when doing cd-rewriting for the purpose of minimizing + // clauses, e.g. we infer the unit equality: + // str.replace( lsym, lsym, lsym ) == "" + // instead of making this inference multiple times: + // x = "" => str.replace( x, x, x ) == "" + // y = "" => str.replace( y, y, y ) == "" Trace("strings-extf-debug") << " get symbolic definition..." << std::endl; Node nrs = getSymbolicDefinition( sn, exps ); if( !nrs.isNull() ){ Trace("strings-extf-debug") << " rewrite " << nrs << "..." << std::endl; - nrs = Rewriter::rewrite( nrs ); - //ensure the symbolic form is non-trivial - if( nrs.isConst() ){ + Node nrsr = Rewriter::rewrite(nrs); + // ensure the symbolic form is not rewritable + if (nrsr != nrs) + { + // we cannot use the symbolic definition if it rewrites Trace("strings-extf-debug") << " symbolic definition is trivial..." << std::endl; nrs = Node::null(); } diff --git a/test/regress/regress1/strings/Makefile.am b/test/regress/regress1/strings/Makefile.am index 400ee7cff..493cd5b6d 100644 --- a/test/regress/regress1/strings/Makefile.am +++ b/test/regress/regress1/strings/Makefile.am @@ -72,7 +72,8 @@ TESTS = \ str001.smt2 \ str002.smt2 \ str007.smt2 \ - rew-020618.smt2 + rew-020618.smt2 \ + double-replace.smt2 EXTRA_DIST = $(TESTS) diff --git a/test/regress/regress1/strings/double-replace.smt2 b/test/regress/regress1/strings/double-replace.smt2 new file mode 100644 index 000000000..0800592d6 --- /dev/null +++ b/test/regress/regress1/strings/double-replace.smt2 @@ -0,0 +1,7 @@ +(set-logic SLIA) +(set-option :strings-exp true) +(set-info :status sat) +(declare-fun x () String) +(declare-fun y () String) +(assert (not (= (str.replace (str.replace x y x) x y) x))) +(check-sat)
\ No newline at end of file |