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 /src/theory/strings | |
parent | f7a77c4c14af25466e7ce31455a9636e0f8234e3 (diff) |
Fix cd-simplification for strings (#1624)
Diffstat (limited to 'src/theory/strings')
-rw-r--r-- | src/theory/strings/theory_strings.cpp | 21 |
1 files changed, 18 insertions, 3 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(); } |