[Strings] Fix extended equality rewriter (#5092)
authorAndres Noetzli <andres.noetzli@gmail.com>
Fri, 18 Sep 2020 14:40:26 +0000 (07:40 -0700)
committerGitHub <noreply@github.com>
Fri, 18 Sep 2020 14:40:26 +0000 (09:40 -0500)
commitf12e2d5a3bd09a91f0d6cd093a62016e456dd4a7
tree24f3e65cb292befe65a5388acb199d097cce0559
parent89c5d4ac65f45f24a7dc0ab76bb2bdb447bdfcda
[Strings] Fix extended equality rewriter (#5092)

Fixes #5090. Our extended equality rewriter was performing the following
unsound rewrite:

(= (str.++ Str13 Str5 Str16 Str13) (str.++ Str5 Str16 Str13 "cjyfqapanogtdznjbtqlfrmmfauwjdpvnhfpfhzsxaarlfvlvs")) ---> (and (= (str.++ Str13 Str5) Str5) (= (str.++ Str16 Str13) (str.++ Str16 Str13 "cjyfqapanogtdznjbtqlfrmmfauwjdpvnhfpfhzsxaarlfvlvs")))
The rule being applied was SPLIT_EQ_STRIP_R. The rewrite was applied
due to the following circumstances:

The rewriter found that (str.++ Str13 Str5) is strictly shorter than (str.++ Str5 Str16 Str13 "cjyfqapanogtdznjbtqlfrmmfauwjdpvnhfpfhzsxaarlfvlvs")
The rewriter stripped the symbolic length of the former from the
latter
stripSymbolicLength() was only able to strip the first component, so
there was a remaining length of (str.len Str13)
The rule SPLIT_EQ_STRIP_R, however, was implicitly assuming that the
symbolic length can either be stripped completly or not at all and was
not considering the case where only a part of the length can be
stripped.

The commit adds a flag to stripSymbolicLength() that makes the
function only return true if the whole length can be stripped from the
input. The commit also refactors the code in stripSymbolicLength()
slightly.

Note: It is not necessary to try to do something smart in the case where
only a partial prefix can be stripped because the rewriter tries to
apply the rule to all the different prefix combinations anyway.
src/theory/strings/sequences_rewriter.cpp
src/theory/strings/strings_entail.cpp
src/theory/strings/strings_entail.h
test/regress/CMakeLists.txt
test/regress/regress0/strings/issue5090.smt2 [new file with mode: 0644]