Better heuristic for str.code/re.range (#3220)

To make sure that our `str.code` function is injectve (except for -1 in
the codomain), we send the inference that `str.code(x) == -1 v
str.code(x) != str.code(y) v x == y` for each pair of `str.code` terms.
Because of the order of disjuncts, `str.code(x) != str.code(y)` was
usually assigned true. This in turn lead to a difficult problem for the
arithmetic engine if there were more `str.code` applications than the
size of the domain. E.g. if we had `0 <= str.code(xi) < 10` for 0 <= i
<= 10, then the arithmetic engine had a difficult time finding a
conflict. This PR improves the heuristic by setting the phase of
`str.code(x) != str.code(y)` to false, so we prefer to keep the
`str.code` values equal instead of trying to make them different.

This change is also reflected in the models produced for inputs
involving `str.code`: Previously, we were producing models with
different values for the `str.code` whereas now the models are much more
uniform.

The PR adds two regressions, one testing `str.code` performance directly
and one testing it for `str.code` terms generated by `re.range`.

Signed-off-by: Andres Noetzli <anoetzli@amazon.com>

1 files changed, 48 insertions, 0 deletions

diff --git a/test/regress/regress0/strings/code-perf.smt2 b/test/regress/regress0/strings/code-perf.smt2
new file mode 100644
index 000000000..39cab48ce
--- /dev/null
+++ b/test/regress/regress0/strings/code-perf.smt2
@@ -0,0 +1,48 @@
+; COMMAND-LINE: --strings-exp
+; EXPECT: sat
+(set-logic QF_SLIA)
+(declare-const x0 String)
+(declare-const x1 String)
+(declare-const x2 String)
+(declare-const x3 String)
+(declare-const x4 String)
+(declare-const x5 String)
+(declare-const x6 String)
+(declare-const x7 String)
+(declare-const x8 String)
+(declare-const x9 String)
+(declare-const x10 String)
+(declare-const y0 Int)
+(declare-const y1 Int)
+(declare-const y2 Int)
+(declare-const y3 Int)
+(declare-const y4 Int)
+(declare-const y5 Int)
+(declare-const y6 Int)
+(declare-const y7 Int)
+(declare-const y8 Int)
+(declare-const y9 Int)
+(declare-const y10 Int)
+(assert (and (= y0 (str.code x0)) (>= y0 (str.code "0")) (<= y0 (str.code "9"))))
+(assert (and (= y1 (str.code x1)) (>= y1 (str.code "0")) (<= y1 (str.code "9"))))
+(assert (and (= y2 (str.code x2)) (>= y2 (str.code "0")) (<= y2 (str.code "9"))))
+(assert (and (= y3 (str.code x3)) (>= y3 (str.code "0")) (<= y3 (str.code "9"))))
+(assert (and (= y4 (str.code x4)) (>= y4 (str.code "0")) (<= y4 (str.code "9"))))
+(assert (and (= y5 (str.code x5)) (>= y5 (str.code "0")) (<= y5 (str.code "9"))))
+(assert (and (= y6 (str.code x6)) (>= y6 (str.code "0")) (<= y6 (str.code "9"))))
+(assert (and (= y7 (str.code x7)) (>= y7 (str.code "0")) (<= y7 (str.code "9"))))
+(assert (and (= y8 (str.code x8)) (>= y8 (str.code "0")) (<= y8 (str.code "9"))))
+(assert (and (= y9 (str.code x9)) (>= y9 (str.code "0")) (<= y9 (str.code "9"))))
+(assert (and (= y10 (str.code x10)) (>= y10 (str.code "0")) (<= y10 (str.code "9"))))
+(assert (= (str.len x0) 1))
+(assert (= (str.len x1) 1))
+(assert (= (str.len x2) 1))
+(assert (= (str.len x3) 1))
+(assert (= (str.len x4) 1))
+(assert (= (str.len x5) 1))
+(assert (= (str.len x6) 1))
+(assert (= (str.len x7) 1))
+(assert (= (str.len x8) 1))
+(assert (= (str.len x9) 1))
+(assert (= (str.len x10) 1))
+(check-sat)