Fix model construction for parametric types (#1059)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Wed, 30 Aug 2017 22:59:24 +0000 (00:59 +0200)
committerAina Niemetz <aina.niemetz@gmail.com>
Wed, 30 Aug 2017 22:59:24 +0000 (15:59 -0700)
commitd7dadde871ae4775748695b0b7f9deee49576c0a
tree9fd407f953671e7ec1b8670db86753d8ab88ddf5
parentfa9fe7dafcc57ec967992a00693650fd11d643ab
Fix model construction for parametric types (#1059)

Fix model construction for parametric types so that we enumerate types in order of dependencies, and avoid subterms of previously enumerated values.

There was a bug in model construction for parametric types which was related to enumerating values that are subterms of other previously enumerated values created during model construction (which were not recorded).

This commit adds all subterms of values we enumerate to the "already used value" sets of their respective types, as reflected in the changes to TypeSet.

There is an extra wrinkle in making the above change, which was caught by the regression test/regress/regress0/fmf/dt-proper-model.smt2. The issue is specific to finite model finding and can be corrected by ensuring that base types (e.g. uninterpreted sorts) are enumerated first.

The change to TheoryModel::buildModel that replaces "allTypes" with "type_list" fixes this wrinkle. This constructs a partially ordered list of types where T1 comes before T2 if values of T2 can contain terms of type T1 but not vice versa. Ordering our enumeration in this way is probably a good idea in general. This ensures we enumerate values for equivalence classes of e.g. Int before (Array Int Int) and means we exclude fewer intermediate values during model construction.
src/theory/theory_model.cpp
src/theory/theory_model.h
test/regress/regress0/datatypes/Makefile.am
test/regress/regress0/datatypes/model-subterms-min.smt2 [new file with mode: 0644]