Refactoring the rewriter of sets (#4856)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Mon, 14 Sep 2020 17:49:58 +0000 (12:49 -0500)
committerGitHub <noreply@github.com>
Mon, 14 Sep 2020 17:49:58 +0000 (12:49 -0500)
commit92a007b4a35a925c92eafc29df5bacacac75f6f9
treeaf69c6aa8cf3ff5470c25aca27d8d340d9d0b141
parentc82d061abb0c011da2700051b7a0548f5d59904b
Refactoring the rewriter of sets (#4856)

Changes it so that we don't flatten unions if at least one child is non-constant, since this may lead to children that are non-constant by mixing constant/non-constant elements and is generally expensive for large unions of singleton elements.

The previous rewriting policy was causing an incorrect model in a separation logic benchmark reported by Andrew Jones, due to unions of constant elements that were unsorted (and hence not considered constants). We now have the invariant that all subterms that are unions of constant elements are set constants.

Note this PR changes the normal form of set constants to be (union (singleton c1) ... (union (singleton cn-1) (singleton cn) ... ) not (union ... (union (singleton c1) (singleton c2)) ... (singleton cn)).

It changes a unit test which was impacted by this change which was failing due to hardcoding the enumeration order in the unit test. The test is now agnostic to the order of elements.
src/theory/sep/theory_sep.cpp
src/theory/sets/normal_form.h
src/theory/sets/theory_sets_private.cpp
src/theory/sets/theory_sets_rewriter.cpp
src/theory/sets/theory_sets_rewriter.h
test/regress/CMakeLists.txt
test/regress/regress0/sep/simple-080420-const-sets.smt2 [new file with mode: 0644]
test/unit/theory/theory_sets_type_enumerator_white.h