Change FunctionSummary.h's definition of SetOfDecls to be an ImmutableList instead

of a mutable SmallPtrSet.  While iterating over LocalTUDecls, there were cases
where we could modify LocalTUDecls, which could result in invalidating an iterator
and an analyzer crash.  Along the way, switch some uses of std::queue to std::dequeue,
which should be slightly more efficient.

Unfortunately, this is a difficult case to create a test case for.

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

2 files changed, 24 insertions, 11 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h b/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h
index 42adff3e2b..3f72432935 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h
@@ -16,13 +16,14 @@
 
 #include "clang/AST/Decl.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/ImmutableList.h"
 
 namespace clang {
 namespace ento {
-typedef llvm::SmallPtrSet<Decl*, 24> SetOfDecls;
-typedef llvm::SmallPtrSet<const Decl*, 24> SetOfConstDecls;
+typedef llvm::ImmutableList<Decl*> SetOfDecls;
+typedef llvm::DenseSet<const Decl*> SetOfConstDecls;
 
 class FunctionSummariesTy {
   struct FunctionSummary {
diff --git a/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp b/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
index 008f744957..dd60b201f8 100644
--- a/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
+++ b/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
@@ -103,6 +103,8 @@ public:
   /// working with a PCH file.
   SetOfDecls LocalTUDecls;
 
+  SetOfDecls::Factory LocalTUDeclsFactory;
+                           
   // PD is owned by AnalysisManager.
   PathDiagnosticConsumer *PD;
 
@@ -306,7 +308,9 @@ void AnalysisConsumer::storeTopLevelDecls(DeclGroupRef DG) {
     if (isa<ObjCMethodDecl>(*I))
       continue;
 
-    LocalTUDecls.insert(*I);
+    // We use an ImmutableList to avoid issues with invalidating iterators
+    // to the list while we are traversing it.
+    LocalTUDecls = LocalTUDeclsFactory.add(*I, LocalTUDecls);
   }
 }
 
@@ -315,6 +319,9 @@ void AnalysisConsumer::HandleDeclsGallGraph() {
   // Build the Call Graph.
   CallGraph CG;
   // Add all the top level declarations to the graph.
+  //
+  // NOTE: We use an ImmutableList to avoid issues with invalidating iterators
+  // to the list while we are traversing it.
   for (SetOfDecls::iterator I = LocalTUDecls.begin(),
                             E = LocalTUDecls.end(); I != E; ++I)
     CG.addToCallGraph(*I);
@@ -338,11 +345,11 @@ void AnalysisConsumer::HandleDeclsGallGraph() {
   // translation unit. This step is very important for performance. It ensures 
   // that we analyze the root functions before the externally available 
   // subroutines.
-  std::queue<CallGraphNode*> BFSQueue;
+  std::deque<CallGraphNode*> BFSQueue;
   for (llvm::SmallVector<CallGraphNode*, 24>::reverse_iterator
          TI = TopLevelFunctions.rbegin(), TE = TopLevelFunctions.rend();
          TI != TE; ++TI)
-    BFSQueue.push(*TI);
+    BFSQueue.push_front(*TI);
 
   // BFS over all of the functions, while skipping the ones inlined into
   // the previously processed functions. Use external Visited set, which is
@@ -350,7 +357,7 @@ void AnalysisConsumer::HandleDeclsGallGraph() {
   SmallPtrSet<CallGraphNode*,24> Visited;
   while(!BFSQueue.empty()) {
     CallGraphNode *N = BFSQueue.front();
-    BFSQueue.pop();
+    BFSQueue.pop_front();
 
     // Skip the functions which have been processed already or previously
     // inlined.
@@ -365,8 +372,8 @@ void AnalysisConsumer::HandleDeclsGallGraph() {
                (Mgr->InliningMode == All ? 0 : &VisitedCallees));
 
     // Add the visited callees to the global visited set.
-    for (SetOfConstDecls::const_iterator I = VisitedCallees.begin(),
-                                         E = VisitedCallees.end(); I != E; ++I){
+    for (SetOfConstDecls::iterator I = VisitedCallees.begin(),
+                                   E = VisitedCallees.end(); I != E; ++I) {
       CallGraphNode *VN = CG.getNode(*I);
       if (VN)
         Visited.insert(VN);
@@ -376,7 +383,7 @@ void AnalysisConsumer::HandleDeclsGallGraph() {
     // Push the children into the queue.
     for (CallGraphNode::const_iterator CI = N->begin(),
                                        CE = N->end(); CI != CE; ++CI) {
-      BFSQueue.push(*CI);
+      BFSQueue.push_front(*CI);
     }
   }
 }
@@ -402,9 +409,14 @@ void AnalysisConsumer::HandleTranslationUnit(ASTContext &C) {
     RecVisitorBR = &BR;
 
     // Process all the top level declarations.
+    //
+    // NOTE: We use an ImmutableList to avoid issues with invalidating iterators
+    // to the list while we are traversing it.
+    //
     for (SetOfDecls::iterator I = LocalTUDecls.begin(),
-                              E = LocalTUDecls.end(); I != E; ++I)
+         E = LocalTUDecls.end(); I != E; ++I) {
       TraverseDecl(*I);
+    }
 
     if (Mgr->shouldInlineCall())
       HandleDeclsGallGraph();