Eliminate shadowing in the quantifiers rewriter (#8244)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Tue, 8 Mar 2022 07:12:23 +0000 (01:12 -0600)
committerGitHub <noreply@github.com>
Tue, 8 Mar 2022 07:12:23 +0000 (07:12 +0000)
commit6ddfbe07e3f855c712d86f832c1065cb082bfd1a
tree7da2d49e62d5f1b8961a0423070913a26f491693
parent444a2f493e7b5d7b7d0d39bb9a5991654056bf8f
Eliminate shadowing in the quantifiers rewriter (#8244)

Fixes #8227.

Recently, we allowed unevaluatable terms to be in the range of substitutions solved during preprocess.

In very rare cases, it may be the case that a quantified formula is substituted into itself, e.g.:
forall x. P(x, b) where b was solved to be forall x. P(x, c)
This leads to forall x. P(x, forall x. P(x, c)) where x is shadowed.

To resolve this issue, we eliminate shadowing in the quantifiers rewriter, e.g. we rewrite the above to forall x. P(x, forall y. P(y, c)).

An alternative solution would be to ensure we use capture avoiding substitutions, but this severely complicates our usage of substitutions throughout the preprocessor / proof system.

This PR also eliminates some dead code in the quantifiers rewriter.
src/preprocessing/passes/non_clausal_simp.cpp
src/theory/quantifiers/quantifiers_rewriter.cpp
src/theory/quantifiers/quantifiers_rewriter.h
test/regress/CMakeLists.txt
test/regress/regress0/quantifiers/issue8227-subs-shadow.smt2 [new file with mode: 0644]