Proper implementation of expand definitions for sequences (#5616)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Tue, 8 Dec 2020 06:38:14 +0000 (00:38 -0600)
committerGitHub <noreply@github.com>
Tue, 8 Dec 2020 06:38:14 +0000 (00:38 -0600)
commit0309ef4aa7462c6fa2a65c1ef408dc9063bb1f21
tree6a5165e43890811a91d01bce0ff7cb3893a4257c
parent3223d3c765b87db9d87a7ca65c4b7cf5dc9a7885
Proper implementation of expand definitions for sequences (#5616)

Expand definitions for sequences was wrong in two ways: (1) we replaced str.from_code with a witness term. This led to it being unevaluatable in models. (2) we did not handle seq.nth, meaning its model value was unevaluatable if it was out of bounds. Now it evaluates the value of the uninterpreted function we replace with.

This corrects both issues and adds a regression to demonstrate both kinds of terms evaluate correctly.

To do this, I added a helper function to skolem cache as well as a new (internal-only) kind SEQ_NTH_TOTAL. Notice applications of this kind should only be used for model evaluation.

Notice this fixes several check-model warnings in the regressions. It still does not fix others since other things must be corrected for model evaluation (e.g. expandDefinitions must be applied on theory assertions for --debug-check-models). This will be done in later PRs.
12 files changed:
src/theory/strings/kinds
src/theory/strings/rewrites.cpp
src/theory/strings/rewrites.h
src/theory/strings/sequences_rewriter.cpp
src/theory/strings/skolem_cache.cpp
src/theory/strings/skolem_cache.h
src/theory/strings/theory_strings.cpp
src/theory/strings/theory_strings_preprocess.cpp
test/regress/CMakeLists.txt
test/regress/regress0/seq/seq-expand-defs.smt2 [new file with mode: 0644]
test/regress/regress0/seq/seq-nth-undef-unsat.smt2
test/regress/regress0/seq/seq-types.smt2