Refactor operator elimination in arithmetic (#4519)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Sat, 23 May 2020 03:39:16 +0000 (22:39 -0500)
committerGitHub <noreply@github.com>
Sat, 23 May 2020 03:39:16 +0000 (22:39 -0500)
commit52082c72d78eee219e3049285d5df559dacac8b5
tree112417e90cc651c3b8523870c5955992ceeeaa99
parent02a7dc0ba7f00b02c2639a884d1f3983b2004a3e
Refactor operator elimination in arithmetic (#4519)

This is a major refactor of how operators are eliminated in arithmetic. Currently there were (at least) two things wrong:
(1) ppRewriteTerm sent lemmas on the output channel. This behavior is incompatible with how preprocessing works. In particular, this caused unconstrained simplification to be unaware of terms from such lemmas, leading to incorrect "sat" answers.
(2) Lemmas used to eliminate certain "div-like" terms were processed in a context-independent way. However, lemmas should be cached in a user-context-dependent way. This was leading to incorrect "sat" answers in incremental.

The solution to these issues is to eliminate operators via the construction of witness terms. No lemmas are sent out, and instead these lemmas are the consequence of term formula removal in the standard way.

As a result of the refactor, 2 quantifiers regressions time out due to infinite branch and bound issues (one only during --check-unsat-cores). These appear to be random and I've changed the options to avoid these issues. 3 others now have check-model warnings, which I've added --quiet to. Improving check-model will be addressed on a future PR.

This PR is not required for SMT COMP since we have workarounds that avoid both the incorrect behaviors in our scripts.

Also notice that --rewrite-divk is effectively now enabled by default always.

Fixes #4484, fixes #4486, fixes #4481.
28 files changed:
src/options/arith_options.toml
src/smt/set_defaults.cpp
src/theory/arith/theory_arith_private.cpp
src/theory/arith/theory_arith_private.h
test/regress/CMakeLists.txt
test/regress/regress0/arith/bug547.2.smt2
test/regress/regress0/arith/div-chainable.smt2
test/regress/regress0/arith/mod-simp.smt2
test/regress/regress0/bug548a.smt2
test/regress/regress0/quantifiers/mix-match.smt2
test/regress/regress0/unconstrained/4481.smt2 [new file with mode: 0644]
test/regress/regress0/unconstrained/4484.smt2 [new file with mode: 0644]
test/regress/regress0/unconstrained/4486.smt2 [new file with mode: 0644]
test/regress/regress1/arith/bug547.1.smt2
test/regress/regress1/bv/bv-int-collapse2-sat.smt2
test/regress/regress1/bv/cmu-rdk-3.smt2
test/regress/regress1/bv/issue3776.smt2
test/regress/regress1/fmf/fmf-fun-no-elim-ext-arith.smt2
test/regress/regress1/fmf/fmf-fun-no-elim-ext-arith2.smt2
test/regress/regress1/fmf/issue3626.smt2
test/regress/regress1/nl/issue3441.smt2
test/regress/regress1/nl/issue3955-ee-double-notify.smt2
test/regress/regress1/push-pop/model-unsound-ania.smt2 [new file with mode: 0644]
test/regress/regress1/strings/chapman150408.smt2
test/regress/regress1/strings/cmu-substr-rw.smt2
test/regress/regress1/strings/crash-1019.smt2
test/regress/regress2/bug674.smt2
test/regress/regress2/strings/cmi-split-cm-fail.smt2