Enable model-based reduction technique for strings (#7680)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Tue, 23 Nov 2021 22:47:09 +0000 (16:47 -0600)
committerGitHub <noreply@github.com>
Tue, 23 Nov 2021 22:47:09 +0000 (22:47 +0000)
commit9815b2b391c2fa708188da81b162bb98931c5d14
treecd7a25fda48014f3d79ef6a9dc8fee24b1bb7dc3
parent38e4cf3fe6dd8f171657943155e875c180649e15
Enable model-based reduction technique for strings (#7680)

This changes our default strategy for deferring (some) reductions until after the model is constructed. It introduces the option `--strings-mbr` (model-based reduction) which is enabled by default.

When using model-based reductions, only *negatIve* contains and negative memberships are deferred for reduction/unfolding until LAST_CALL effort, where a candidate model is available. These steps are performed only if the constraints are not already satisfied in the model.  The intuition is that negative contains/membership are the *most* expensive constraints to process and are moreover the *least* likely to be false in the model.

It makes a few fixes to the extended/RE solvers:
- 2 kinds of inferences in `checkExtfEval` should not be performed for substitutions based on models
- The regular expression solver should not use inclusion tests to justify reduction of memberships when the basis for the reduction is an unfolded membership, due to the reasoning being potentially cyclic.  This led to a bogus model on a regression when the new strategy was enabled.

It also does minor refactoring of those solvers that was required for implementing the new policy.

This branch is +446-1 on SMT-LIB, with all gains coming on "sat" benchmarks, mostly from pyex.  It also solves 2 previously unsolved challenge Amazon benchmarks quickly.
src/options/strings_options.toml
src/theory/strings/extf_solver.cpp
src/theory/strings/extf_solver.h
src/theory/strings/regexp_solver.cpp
src/theory/strings/regexp_solver.h
src/theory/strings/strategy.cpp
src/theory/strings/theory_strings.cpp