2 files changed, 31 insertions, 0 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index e60922e478..5ce219b4ed 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -60,10 +60,20 @@ class ExplodedNode : public llvm::FoldingSetNode {
   friend class SwitchNodeBuilder;
   friend class EndOfFunctionNodeBuilder;
 
+  /// Efficiently stores a list of ExplodedNodes, or an optional flag.
+  ///
+  /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
+  /// for the case when there is only one node in the group. This is a fairly
+  /// common case in an ExplodedGraph, where most nodes have only one
+  /// predecessor and many have only one successor. It can also be used to
+  /// store a flag rather than a node list, which ExplodedNode uses to mark
+  /// whether a node is a sink. If the flag is set, the group is implicitly
+  /// empty and no nodes may be added.
   class NodeGroup {
     // Conceptually a discriminated union. If the low bit is set, the node is
     // a sink. If the low bit is not set, the pointer refers to the storage
     // for the nodes in the group.
+    // This is not a PointerIntPair in order to keep the storage type opaque.
     uintptr_t P;
     
   public:
@@ -79,10 +89,19 @@ class ExplodedNode : public llvm::FoldingSetNode {
 
     bool empty() const { return P == 0 || getFlag() != 0; }
 
+    /// Adds a node to the list.
+    ///
+    /// The group must not have been created with its flag set.
     void addNode(ExplodedNode *N, ExplodedGraph &G);
 
+    /// Replaces the single node in this group with a new node.
+    ///
+    /// Note that this should only be used when you know the group was not
+    /// created with its flag set, and that the group is empty or contains
+    /// only a single node.
     void replaceNode(ExplodedNode *node);
 
+    /// Returns whether this group was created with its flag set.
     bool getFlag() const {
       return (P & 1);
     }
diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 24d1c094d0..9145565d3a 100644
--- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -162,6 +162,16 @@ void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
 // ExplodedNode.
 //===----------------------------------------------------------------------===//
 
+// An NodeGroup's storage type is actually very much like a TinyPtrVector:
+// it can be either a pointer to a single ExplodedNode, or a pointer to a
+// BumpVector allocated with the ExplodedGraph's allocator. This allows the
+// common case of single-node NodeGroups to be implemented with no extra memory.
+//
+// Consequently, each of the NodeGroup methods have up to four cases to handle:
+// 1. The flag is set and this group does not actually contain any nodes.
+// 2. The group is empty, in which case the storage value is null.
+// 3. The group contains a single node.
+// 4. The group contains more than one node.
 typedef BumpVector<ExplodedNode *> ExplodedNodeVector;
 typedef llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *> GroupStorage;
 
@@ -175,6 +185,8 @@ void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
 }
 
 void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
+  assert(!getFlag());
+
   GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
   assert(Storage.is<ExplodedNode *>());
   Storage = node;