Ensure strict length constraint for decompose rule (#4821)
authorAndres Noetzli <andres.noetzli@gmail.com>
Sun, 2 Aug 2020 06:56:27 +0000 (23:56 -0700)
committerGitHub <noreply@github.com>
Sun, 2 Aug 2020 06:56:27 +0000 (23:56 -0700)
commit475985ccc80b1ddb38d912a3c6658912f1fc6207
treeffc5cf8164e9bbc8a1e2edf169833463b26df693
parent5be889668bfb52d6705c2dc37ec05c291c7c9445
Ensure strict length constraint for decompose rule (#4821)

Fixes #4820. The performance issue was caused by
0988217562006d3f59e01dc261f39121df6d75f5. That commit introduced an
option (`--strings-len-conc`) that optionally moves the length
constraint for skolems to the conclusion of an inference instead of
making it part of the term registration. However, for
`DEQ_DISL_STRINGS_SPLIT`, we were only asserting that `LENGTH_GEQ_ONE`
in the case where this option was not enabled, instead of asserting that
the length of the skolem is equal to the component on the other side of
the disequality. This lead to an infinite loop of inferences because we
effectively were just splitting a component into two skolems and the
only restriction was that the first one was non-empty. We guessed the
second skolem to be empty, so the first skolem was equal to the
component, the skolem was marked congruent, and we ended up with the
same normal form as before.

The commit fixes the issue by adding an argument to
`getDecomposeConclusion()` that specifies whether to add the length
constraint or not. This option is used to always add the length
constraint in the case of `DEQ_DISL_STRINGS_SPLIT`.
src/theory/strings/core_solver.cpp
src/theory/strings/core_solver.h
test/regress/CMakeLists.txt
test/regress/regress0/strings/issue4820.smt2 [new file with mode: 0644]