[Analyzer][solver] Do not remove the simplified symbol from the eq class
authorGabor Marton <gabor.marton@ericsson.com>
Fri, 26 Nov 2021 09:59:09 +0000 (10:59 +0100)
committerGabor Marton <gabor.marton@ericsson.com>
Tue, 30 Nov 2021 10:13:13 +0000 (11:13 +0100)
commitf02c5f3478318075d1a469203900e452ba651421
tree0f9102e4bfe6eb4764fcfc72bf46d21e66d1f9fa
parent9a14adeae00015798843ff5cad987e5fdbdddb34
[Analyzer][solver] Do not remove the simplified symbol from the eq class

Currently, during symbol simplification we remove the original member symbol
from the equivalence class (`ClassMembers` trait). However, we keep the
reverse link (`ClassMap` trait), in order to be able the query the
related constraints even for the old member. This asymmetry can lead to
a problem when we merge equivalence classes:
```
ClassA: [a, b]   // ClassMembers trait,
a->a, b->a       // ClassMap trait, a is the representative symbol
```
Now lets delete `a`:
```
ClassA: [b]
a->a, b->a
```
Let's merge the trivial class `c` into ClassA:
```
ClassA: [c, b]
c->c, b->c, a->a
```
Now after the merge operation, `c` and `a` are actually in different
equivalence classes, which is inconsistent.

One solution to this problem is to simply avoid removing the original
member and this is what this patch does.

Other options I have considered:
1) Always merge the trivial class into the non-trivial class. This might
   work most of the time, however, will fail if we have to merge two
   non-trivial classes (in that case we no longer can track equivalences
   precisely).
2) In `removeMember`, update the reverse link as well. This would cease
   the inconsistency, but we'd loose precision since we could not query
   the constraints for the removed member.

Differential Revision: https://reviews.llvm.org/D114619
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/expr-inspection-printState-eq-classes.c
clang/test/Analysis/symbol-simplification-disequality-info.cpp
clang/test/Analysis/symbol-simplification-fixpoint-one-iteration.cpp
clang/test/Analysis/symbol-simplification-fixpoint-two-iterations.cpp