[analyzer] Fix a bug in "collapsed" graph viewer

Nodes which have only one predecessor and only one successor can not
always be hidden, even if all states are the same.
An additional condition is needed: the predecessor may have only one successor.
This can be seen on this example:

```
  A
 / \
B   C
 \ /
  D
```

Nodes B and C can not be hidden even if all nodes in the graph have the
same state.

Differential Revision: https://reviews.llvm.org/D53735

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@345341 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 16 insertions, 8 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index cf4164dcd2..bf460df278 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -210,10 +210,14 @@ public:
     return const_cast<ExplodedNode*>(this)->getFirstPred();
   }
 
-  const ExplodedNode *getFirstSucc() const {
+  ExplodedNode *getFirstSucc() {
     return succ_empty() ? nullptr : *(succ_begin());
   }
 
+  const ExplodedNode *getFirstSucc() const {
+    return const_cast<ExplodedNode*>(this)->getFirstSucc();
+  }
+
   // Iterators over successor and predecessor vertices.
   using succ_iterator = ExplodedNode * const *;
   using const_succ_iterator = const ExplodedNode * const *;
@@ -243,8 +247,10 @@ public:
   int64_t getID(ExplodedGraph *G) const;
 
   /// The node is trivial if it has only one successor, only one predecessor,
+  /// it's predecessor has only one successor,
   /// and its program state is the same as the program state of the previous
   /// node.
+  /// Trivial nodes may be skipped while printing exploded graph.
   bool isTrivial() const;
 
 private:
@@ -460,7 +466,6 @@ public:
 // GraphTraits
 
 namespace llvm {
-
   template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
     using GraphTy = clang::ento::ExplodedGraph *;
     using NodeRef = clang::ento::ExplodedNode *;
@@ -471,17 +476,19 @@ namespace llvm {
       return *G->roots_begin();
     }
 
+    static bool predecessorOfTrivial(NodeRef N) {
+      return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
+    }
+
     static ChildIteratorType child_begin(NodeRef N) {
-      if (N->succ_size() == 1 && (*N->succ_begin())->isTrivial()) {
+      if (predecessorOfTrivial(N))
         return child_begin(*N->succ_begin());
-      }
       return N->succ_begin();
     }
 
     static ChildIteratorType child_end(NodeRef N) {
-      if (N->succ_size() == 1 && (*N->succ_begin())->isTrivial()) {
-        return child_end(*N->succ_begin());
-      }
+      if (predecessorOfTrivial(N))
+        return child_end(N->getFirstSucc());
       return N->succ_end();
     }
 
diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 7d7b88a811..d76710004c 100644
--- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -292,7 +292,8 @@ int64_t ExplodedNode::getID(ExplodedGraph *G) const {
 
 bool ExplodedNode::isTrivial() const {
   return pred_size() == 1 && succ_size() == 1 &&
-         (*pred_begin())->getState()->getID() == getState()->getID();
+         getFirstPred()->getState()->getID() == getState()->getID() &&
+         getFirstPred()->succ_size() == 1;
 }
 
 ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,