Compute model values for nested sequences in order (#6631)
authorAndres Noetzli <andres.noetzli@gmail.com>
Mon, 31 May 2021 00:35:08 +0000 (17:35 -0700)
committerGitHub <noreply@github.com>
Mon, 31 May 2021 00:35:08 +0000 (00:35 +0000)
commit21511862f74c74a9c75da1de01e6b0e0a8120613
treed023b93ea6d7a34ca8afb4c8802bf93d1b211582
parent0133367f9ed242aa01e42867364c7be74ffe5618
Compute model values for nested sequences in order (#6631)

Fixes #6337 (the other benchmarks in this issue are either solved
correctly or time out after the changes in #6615) and fixes #5665.

While computing the model for a nested equivalence class containing
seq.unit, we were looking up the representative of the argument in
(seq.unit (seq.unit j)) and the representative was simpliy (seq.unit j). However, we had assigned (seq.unit 0) to (seq.unit j) earlier.
A second equivalence class of type (Seq (Seq Int)) and length 1 was
later assigned (seq.unit (seq.unit 0)) and we didn't detect that
(seq.unit (seq.unit j)) and (seq.unit (seq.unit 0)) have the same
value. This was incorrect because we do not allow assigning the same
value to different equivalence classes. In this case, it led to one of
the assertions being false.

This commit fixes the issues in two ways: it ensures that types are
processed in ascending order of nesting (e.g., (Seq Int) terms are
processed before (Seq (Seq Int)) terms) and it changes the procedure
to look up the representative in the model instead of the theory state
to take into account the model values assigned to the elements of
sequences.

cc @yoni206
src/theory/strings/theory_strings.cpp
src/theory/strings/theory_strings.h
test/regress/CMakeLists.txt
test/regress/regress0/seq/issue5665-invalid-model.smt2 [new file with mode: 0644]
test/regress/regress0/seq/issue6337-seq.smt2 [new file with mode: 0644]