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

[george.karpenkov]

Summary

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.

[NoQ]

Thx!~

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

public:
   ExplodedNode *getFirstPred() {
     return pred_empty() ? nullptr : *(pred_begin());
   }
 
   const ExplodedNode *getFirstPred() const {
     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 *;
   using pred_iterator = ExplodedNode * const *;
   using const_pred_iterator = const ExplodedNode * const *;
 
   pred_iterator pred_begin() { return Preds.begin(); }
   pred_iterator pred_end() { return Preds.end(); }
public:
   }
   const_succ_iterator succ_end() const {
     return const_cast<ExplodedNode*>(this)->succ_end();
   }
 
   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:
   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
 };
 
 using InterExplodedGraphMap =

 
 } // namespace ento
 
 } // namespace clang
 
 // GraphTraits
 
 namespace llvm {
-
   template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
     using GraphTy = clang::ento::ExplodedGraph *;
     using NodeRef = clang::ento::ExplodedNode *;
     using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
     using nodes_iterator = llvm::df_iterator<GraphTy>;
 
     static NodeRef getEntryNode(const GraphTy G) {
       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();
     }
 
     static nodes_iterator nodes_begin(const GraphTy G) {
       return df_begin(G);
     }
 
     static nodes_iterator nodes_end(const GraphTy G) {
       return df_end(G);
     }
   };
 } // namespace llvm
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

int64_t ExplodedNode::getID(ExplodedGraph *G) const {
   Optional<int64_t> Out = G->getAllocator().identifyObject(this);
   assert(Out && "Wrong allocator used");
   assert(*Out % alignof(ExplodedNode) == 0 && "Wrong alignment information");
   return *Out / alignof(ExplodedNode);
 }
 
 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,
                                      ProgramStateRef State,
                                      bool IsSink,
                                      bool* IsNew) {
   // Profile 'State' to determine if we already have an existing node.
   llvm::FoldingSetNodeID profile;