Modify lemma vs fact policy for datatype equalities (#5115)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Thu, 24 Sep 2020 03:13:35 +0000 (22:13 -0500)
committerGitHub <noreply@github.com>
Thu, 24 Sep 2020 03:13:35 +0000 (22:13 -0500)
commit3075a8e20dba6a784316714543c8a1b262459d9a
tree1ef809c91de2f1a944331ea0cb93959c35126bcf
parentaacc90c1234c488f49814fae6dbf0e720e2dfa88
Modify lemma vs fact policy for datatype equalities (#5115)

This changes the lemma vs fact policy for datatype equalities. Previously, datatype equalities were sent as lemmas unless they were over datatypes that were composed of datatypes only. This is now changed so that equalities that do not involve direct subterms with finite non-datatype types are kept internal.

The primary type of equality that this targets are "Instantiate" equalities, e.g. the conclusion of:
(is-cons x) => x = (cons (head x) (tail x))
These equalities have been observed to generate large amounts of new terms for many benchmarks.

With this PR, the the challenging Facebook benchmark goes from 2 min 45 sec -> 29 sec. If the instantiate rule is disabled altogether, it still correctly solves, and is faster (~14 seconds), which however is not correct in general.

This change triggered two other issues:
(1) A relations benchmark involving transitive closure now times out. This has been a common issue for the relations solver and should be revisited.
(2) A potential issue with doPendingLemmas in InferenceManagerBuffer was uncovered. In rare cases, we can be re-entrant into this method since OutputChannel::lemma may trigger further preregistration of terms, which can trigger a recursive call to doPendingLemmas in the case of datatypes, which causes a segfault due to corrupting an iterator. This PR adds a simple guard for this method.

This PR also fixes some existing issues in computing cardinality for parametric datatypes.
src/expr/dtype_cons.cpp
src/expr/dtype_cons.h
src/theory/datatypes/inference_manager.cpp
src/theory/datatypes/inference_manager.h
src/theory/datatypes/theory_datatypes.cpp
src/theory/inference_manager_buffered.cpp
src/theory/inference_manager_buffered.h
test/regress/CMakeLists.txt
test/regress/regress0/datatypes/dt-different-params.smt2 [new file with mode: 0644]
test/regress/regress0/datatypes/list-bool.smt2 [new file with mode: 0644]