| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
reachability analysis are too big to be solved in reasonable time, then we skip
the analysis. I also cleaned up warnings.
Why did `t9181.scala` work fine with 2.11.4, but is now running out of memory?
In order to ensure that the scrutinee is associated only with one of the 400
derived classes we add 400*400 / 2 ~ 80k clauses to ensure mutual exclusivity.
In 2.11.4 the translation into CNF used to fail, since it would blow up already
at this point in memory. This has been fixed in 2.11.5, but now the DPLL solver
is the bottleneck.
There's a check in the search for all models (exhaustivity) that it would avoid
a blow up, but in the search for a model (reachability), such a check is
missing.
|
|
|
Avoid blowing the stack/the analysis budget by more eagerly translating
the propositions that model matches to CNF.
First building a large proposition that represents the match,
and then converting to CNF tends to blow the stack.
Luckily, it's easy to convert to CNF as we go.
The optimization relies on `CNF(P1 /\ ... /\ PN) == CNF(P1) ++ CNF(...) ++ CNF(PN)`:
Normalizing a conjunction of propositions
yields the same formula as
concatenating the normalized conjuncts.
CNF conversion is expensive for large propositions,
so we push it down into the conjunction and
then concatenate the resulting arrays of clauses (which is cheap).
(CNF converts a free-form proposition into an `Array[Set[Lit]]`, where:
- the Array's elements are /\'ed together;
- and the Set's elements are \/'ed;
- a Lit is a possibly negated variable.)
NOTE:
- removeVarEq may throw an AnalysisBudget.Exception
- also reworked the interface used to build formula,
so that we can more easily plug in SAT4J when the time comes
|
