Use substitutions for implementing defined functions (#6437)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Fri, 30 Apr 2021 19:12:56 +0000 (14:12 -0500)
committerGitHub <noreply@github.com>
Fri, 30 Apr 2021 19:12:56 +0000 (19:12 +0000)
commit327a24508ed1d02a3fa233e680ffd0b30aa685a9
treed130a4b5afcf34383b6bdf38c433d77c5911709d
parent38a45651953d3bcfe67cb80b4f2ba2d1b278f7ba
Use substitutions for implementing defined functions (#6437)

This eliminates explicit tracking of defined functions, and instead makes define-fun add to preprocessing substitutions.
In other words, the effect of:

(define-fun f X t)
is to add f -> (lambda X t) to the set of substitutions known by the preprocessor. This is essentially the same as when
(= f (lambda X t)) was an equality solved by non-clausal simplification

The motivation for this change is both uniformity and for performance, as fewer traversals of the input formula.

In this PR:

define-fun are now conceptually higher-order equalities provided to smt::Assertions. These assertions are always added as substitutions instead of being pushed to AssertionPipeline.
Top-level substitutions are moved from PreprocessingContext to Env, since they must be accessed by Assertions. Proofs for this class are enabled dynamically during SmtEngine::finishInit.
The expandDefinitions preprocessing step is replaced by apply-substs. The process assertions module no longer needs access to expand definitions.
The proof manager does not require a special case of using the define-function maps.
Define-function maps are eliminated from SmtEngine.
Further work will reorganize the relationship between the expand definitions module and the rewriter, after which global calls to SmtEngine::expandDefinitions can be cleaned up. There is also further work necessary to better integrate theory expand definitions and top-level substitutions, which will be done on a followup PR.
25 files changed:
src/CMakeLists.txt
src/preprocessing/preprocessing_pass_context.cpp
src/preprocessing/preprocessing_pass_context.h
src/smt/assertions.cpp
src/smt/assertions.h
src/smt/defined_function.h [deleted file]
src/smt/env.cpp
src/smt/env.h
src/smt/expand_definitions.cpp
src/smt/expand_definitions.h
src/smt/preprocessor.cpp
src/smt/preprocessor.h
src/smt/process_assertions.cpp
src/smt/process_assertions.h
src/smt/proof_manager.cpp
src/smt/proof_manager.h
src/smt/smt_engine.cpp
src/smt/smt_engine.h
src/smt/sygus_solver.cpp
src/theory/trust_substitutions.cpp
src/theory/trust_substitutions.h
test/regress/regress1/bug516.smt2
test/regress/regress1/model-blocker-values.smt2
test/regress/regress1/quantifiers/intersection-example-onelane.proof-node22337.smt2
test/regress/regress1/quantifiers/issue3664.smt2