Add new eager conflict detection in strings for integer equivalence classes (#7453)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Sun, 24 Oct 2021 18:31:56 +0000 (13:31 -0500)
committerGitHub <noreply@github.com>
Sun, 24 Oct 2021 18:31:56 +0000 (13:31 -0500)
commitc99aa755bd62205b3f7381e6d67c7a1f2d37a3a2
treee6c16ea6babc4463dc2f4edae1b07855f3a219c2
parentf493ea93e925e3ad9bfe0036e1d876d5600d5b30
Add new eager conflict detection in strings for integer equivalence classes (#7453)

Required to address Zelkova bottlenecks.

This generalizes the methods for eager prefix/suffix conflicts for strings to do eager lower/upper bound conflicts for integer equivalence classes based on string-specific reasoning about length terms. This avoids cases where Simplex fails to show a concise conflict due to not having access to string reasoning (e.g. strings::ArithEntail) for arithmetic bounds.

The approach can still be improved by inferring fixed length for regular expression memberships, analogous to what is done for prefix/suffix conflicts.

It also changes EqcInfo to store (str.len x) instead of x for length terms.
15 files changed:
src/theory/inference_id.cpp
src/theory/inference_id.h
src/theory/strings/arith_entail.cpp
src/theory/strings/arith_entail.h
src/theory/strings/core_solver.cpp
src/theory/strings/eager_solver.cpp
src/theory/strings/eager_solver.h
src/theory/strings/eqc_info.cpp
src/theory/strings/eqc_info.h
src/theory/strings/solver_state.cpp
src/theory/strings/solver_state.h
src/theory/strings/theory_strings.cpp
src/theory/strings/theory_strings.h
test/regress/CMakeLists.txt
test/regress/regress1/strings/pattern1.smt2 [new file with mode: 0644]