[analyzer] Change PathPieces to be a wrapper around an ilist of (through indirection) PathDiagnosticPieces.

Much of this patch outside of PathDiagnostics.h are just minor
syntactic changes due to the return type for operator* and the like
changing for the iterator, so the real focus should be on
PathPieces itself.

This change is motivated so that we can do efficient insertion
and removal of individual pieces from within a PathPiece, just like
this was a kind of "IR" for static analyzer diagnostics.  We
currently implement path transformations by iterating over an
entire PathPiece and making a copy.  This isn't very natural for
some algorithms.

We use an ilist here instead of std::list because we want operations
to rip out/insert nodes in place, just like IR manipulation.  This
isn't being used yet, but opens the door for more powerful
transformation algorithms on diagnostic paths.

llvm-svn: 180741

5 files changed, 53 insertions, 45 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
index 52c364e8917..930f4bc99a6 100644
--- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -123,7 +123,7 @@ static void removeRedundantMsgs(PathPieces &path) {
           break;
         
         if (PathDiagnosticEventPiece *nextEvent =
-            dyn_cast<PathDiagnosticEventPiece>(path.front().getPtr())) {
+            dyn_cast<PathDiagnosticEventPiece>(path.front())) {
           PathDiagnosticEventPiece *event =
             cast<PathDiagnosticEventPiece>(piece);
           // Check to see if we should keep one of the two pieces.  If we
@@ -210,10 +210,10 @@ bool BugReporter::RemoveUnneededCalls(PathPieces &pieces, BugReport *R) {
 static void adjustCallLocations(PathPieces &Pieces,
                                 PathDiagnosticLocation *LastCallLocation = 0) {
   for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) {
-    PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I);
+    PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(&*I);
 
     if (!Call) {
-      assert((*I)->getLocation().asLocation().isValid());
+      assert(I->getLocation().asLocation().isValid());
       continue;
     }
 
@@ -946,7 +946,7 @@ public:
       // If the PathDiagnostic already has pieces, add the enclosing statement
       // of the first piece as a context as well.
       if (!PD.path.empty()) {
-        PrevLoc = (*PD.path.begin())->getLocation();
+        PrevLoc = PD.path.begin()->getLocation();
 
         if (const Stmt *S = PrevLoc.asStmt())
           addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
@@ -1987,10 +1987,10 @@ static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
   MacroStackTy MacroStack;
   PiecesTy Pieces;
 
-  for (PathPieces::const_iterator I = path.begin(), E = path.end();
+  for (PathPieces::iterator I = path.begin(), E = path.end();
        I!=E; ++I) {
     
-    PathDiagnosticPiece *piece = I->getPtr();
+    PathDiagnosticPiece *piece = &*I;
 
     // Recursively compact calls.
     if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){
diff --git a/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp b/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
index 73426da2b4d..a5fe300fb67 100644
--- a/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
+++ b/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
@@ -126,10 +126,10 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D,
 
   // The path as already been prechecked that all parts of the path are
   // from the same file and that it is non-empty.
-  const SourceManager &SMgr = (*path.begin())->getLocation().getManager();
+  const SourceManager &SMgr = path.begin()->getLocation().getManager();
   assert(!path.empty());
   FileID FID =
-    (*path.begin())->getLocation().asLocation().getExpansionLoc().getFileID();
+    path.begin()->getLocation().asLocation().getExpansionLoc().getFileID();
   assert(!FID.isInvalid());
 
   // Create a new rewriter to generate HTML.
@@ -139,10 +139,10 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D,
   unsigned n = path.size();
   unsigned max = n;
 
-  for (PathPieces::const_reverse_iterator I = path.rbegin(), 
+  for (PathPieces::reverse_iterator I = path.rbegin(), 
        E = path.rend();
         I != E; ++I, --n)
-    HandlePiece(R, FID, **I, n, max);
+    HandlePiece(R, FID, *I, n, max);
 
   // Add line numbers, header, footer, etc.
 
@@ -185,9 +185,9 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D,
       << html::EscapeText(Entry->getName())
       << "</td></tr>\n<tr><td class=\"rowname\">Location:</td><td>"
          "<a href=\"#EndPath\">line "
-      << (*path.rbegin())->getLocation().asLocation().getExpansionLineNumber()
+      << path.rbegin()->getLocation().asLocation().getExpansionLineNumber()
       << ", column "
-      << (*path.rbegin())->getLocation().asLocation().getExpansionColumnNumber()
+      << path.rbegin()->getLocation().asLocation().getExpansionColumnNumber()
       << "</a></td></tr>\n"
          "<tr><td class=\"rowname\">Description:</td><td>"
       << D.getVerboseDescription() << "</td></tr>\n";
@@ -503,16 +503,16 @@ unsigned HTMLDiagnostics::ProcessMacroPiece(raw_ostream &os,
                                             const PathDiagnosticMacroPiece& P,
                                             unsigned num) {
 
-  for (PathPieces::const_iterator I = P.subPieces.begin(), E=P.subPieces.end();
+  for (PathPieces::iterator I = P.subPieces.begin(), E=P.subPieces.end();
         I!=E; ++I) {
 
     if (const PathDiagnosticMacroPiece *MP =
-          dyn_cast<PathDiagnosticMacroPiece>(*I)) {
+          dyn_cast<PathDiagnosticMacroPiece>(&*I)) {
       num = ProcessMacroPiece(os, *MP, num);
       continue;
     }
 
-    if (PathDiagnosticEventPiece *EP = dyn_cast<PathDiagnosticEventPiece>(*I)) {
+    if (PathDiagnosticEventPiece *EP = dyn_cast<PathDiagnosticEventPiece>(&*I)){
       os << "<div class=\"msg msgEvent\" style=\"width:94%; "
             "margin-left:5px\">"
             "<table class=\"msgT\"><tr>"
diff --git a/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
index 03513106ecd..e2228aa13b1 100644
--- a/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
+++ b/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
@@ -28,11 +28,11 @@ using namespace clang;
 using namespace ento;
 
 bool PathDiagnosticMacroPiece::containsEvent() const {
-  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
+  for (PathPieces::iterator I = subPieces.begin(), E = subPieces.end();
        I!=E; ++I) {
     if (isa<PathDiagnosticEventPiece>(*I))
       return true;
-    if (PathDiagnosticMacroPiece *MP = dyn_cast<PathDiagnosticMacroPiece>(*I))
+    if (PathDiagnosticMacroPiece *MP = dyn_cast<PathDiagnosticMacroPiece>(&*I))
       if (MP->containsEvent())
         return true;
   }
@@ -59,13 +59,21 @@ PathDiagnosticCallPiece::~PathDiagnosticCallPiece() {}
 PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() {}
 PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() {}
 
+PathPieces &PathPieces::operator=(const PathPieces & X) {
+  clear();
+  for (llvm::ilist<Node>::const_iterator I = X.L.begin(), E = X.L.end();
+       I != E; ++I) {
+    L.push_back(new Node(&*(I->Data)));
+  }
+  return *this;
+}
 
 PathPieces::~PathPieces() {}
 
 void PathPieces::flattenTo(PathPieces &Primary, PathPieces &Current,
                            bool ShouldFlattenMacros) const {
-  for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
-    PathDiagnosticPiece *Piece = I->getPtr();
+  for (PathPieces::iterator I = begin(), E = end(); I != E; ++I) {
+    PathDiagnosticPiece *Piece = &*I;
 
     switch (Piece->getKind()) {
     case PathDiagnosticPiece::Call: {
@@ -145,7 +153,7 @@ void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) {
   if (!supportsCrossFileDiagnostics()) {
     // Verify that the entire path is from the same FileID.
     FileID FID;
-    const SourceManager &SMgr = (*D->path.begin())->getLocation().getManager();
+    const SourceManager &SMgr = D->path.begin()->getLocation().getManager();
     SmallVector<const PathPieces *, 5> WorkList;
     WorkList.push_back(&D->path);
 
@@ -153,9 +161,9 @@ void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) {
       const PathPieces &path = *WorkList.back();
       WorkList.pop_back();
 
-      for (PathPieces::const_iterator I = path.begin(), E = path.end();
+      for (PathPieces::iterator I = path.begin(), E = path.end();
            I != E; ++I) {
-        const PathDiagnosticPiece *piece = I->getPtr();
+        const PathDiagnosticPiece *piece = &*I;
         FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc();
       
         if (FID.isInvalid()) {
@@ -298,11 +306,11 @@ static Optional<bool> comparePath(const PathPieces &X, const PathPieces &Y) {
   if (X.size() != Y.size())
     return X.size() < Y.size();
 
-  PathPieces::const_iterator X_I = X.begin(), X_end = X.end();
-  PathPieces::const_iterator Y_I = Y.begin(), Y_end = Y.end();
+  PathPieces::iterator X_I = X.begin(), X_end = X.end();
+  PathPieces::iterator Y_I = Y.begin(), Y_end = Y.end();
 
   for ( ; X_I != X_end && Y_I != Y_end; ++X_I, ++Y_I) {
-    Optional<bool> b = comparePiece(**X_I, **Y_I);
+    Optional<bool> b = comparePiece(*X_I, *Y_I);
     if (b.hasValue())
       return b.getValue();
   }
@@ -954,9 +962,9 @@ PathDiagnosticCallPiece::getCallExitEvent() const {
 }
 
 static void compute_path_size(const PathPieces &pieces, unsigned &size) {
-  for (PathPieces::const_iterator it = pieces.begin(),
+  for (PathPieces::iterator it = pieces.begin(),
                                   et = pieces.end(); it != et; ++it) {
-    const PathDiagnosticPiece *piece = it->getPtr();
+    const PathDiagnosticPiece *piece = &*it;
     if (const PathDiagnosticCallPiece *cp = 
         dyn_cast<PathDiagnosticCallPiece>(piece)) {
       compute_path_size(cp->path, size);
@@ -998,9 +1006,9 @@ void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 
 void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
   PathDiagnosticPiece::Profile(ID);
-  for (PathPieces::const_iterator it = path.begin(), 
+  for (PathPieces::iterator it = path.begin(), 
        et = path.end(); it != et; ++it) {
-    ID.Add(**it);
+    ID.Add(*it);
   }
 }
 
@@ -1017,9 +1025,9 @@ void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 
 void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
   PathDiagnosticSpotPiece::Profile(ID);
-  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
+  for (PathPieces::iterator I = subPieces.begin(), E = subPieces.end();
        I != E; ++I)
-    ID.Add(**I);
+    ID.Add(*I);
 }
 
 void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
@@ -1031,8 +1039,8 @@ void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
 
 void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
   Profile(ID);
-  for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
-    ID.Add(**I);
+  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I)
+    ID.Add(*I);
   for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
     ID.AddString(*I);
 }
diff --git a/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp b/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp
index 850955561ec..2701951410d 100644
--- a/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp
+++ b/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp
@@ -294,8 +294,8 @@ static void ReportCall(raw_ostream &o,
     ReportPiece(o, *callEnterWithinCaller, FM, SM, LangOpts,
                 indent, depth, true);
   
-  for (PathPieces::const_iterator I = P.path.begin(), E = P.path.end();I!=E;++I)
-    ReportPiece(o, **I, FM, SM, LangOpts, indent, depth, true);
+  for (PathPieces::iterator I = P.path.begin(), E = P.path.end();I!=E;++I)
+    ReportPiece(o, *I, FM, SM, LangOpts, indent, depth, true);
 
   --depth;
   
@@ -313,9 +313,9 @@ static void ReportMacro(raw_ostream &o,
                         unsigned indent,
                         unsigned depth) {
 
-  for (PathPieces::const_iterator I = P.subPieces.begin(), E=P.subPieces.end();
+  for (PathPieces::iterator I = P.subPieces.begin(), E=P.subPieces.end();
        I!=E; ++I) {
-    ReportPiece(o, **I, FM, SM, LangOpts, indent, depth, false);
+    ReportPiece(o, *I, FM, SM, LangOpts, indent, depth, false);
   }
 }
 
@@ -363,7 +363,7 @@ void PlistDiagnostics::FlushDiagnosticsImpl(
   const SourceManager* SM = 0;
 
   if (!Diags.empty())
-    SM = &(*(*Diags.begin())->path.begin())->getLocation().getManager();
+    SM = &(*(*Diags.begin())->path.begin()).getLocation().getManager();
 
   
   for (std::vector<const PathDiagnostic*>::iterator DI = Diags.begin(),
@@ -378,9 +378,9 @@ void PlistDiagnostics::FlushDiagnosticsImpl(
       const PathPieces &path = *WorkList.back();
       WorkList.pop_back();
     
-      for (PathPieces::const_iterator I = path.begin(), E = path.end();
+      for (PathPieces::iterator I = path.begin(), E = path.end();
            I!=E; ++I) {
-        const PathDiagnosticPiece *piece = I->getPtr();
+        const PathDiagnosticPiece *piece = &*I;
         AddFID(FM, Fids, SM, piece->getLocation().asLocation());
         ArrayRef<SourceRange> Ranges = piece->getRanges();
         for (ArrayRef<SourceRange>::iterator I = Ranges.begin(),
@@ -450,9 +450,9 @@ void PlistDiagnostics::FlushDiagnosticsImpl(
 
     o << "   <array>\n";
 
-    for (PathPieces::const_iterator I = D->path.begin(), E = D->path.end(); 
+    for (PathPieces::iterator I = D->path.begin(), E = D->path.end(); 
          I != E; ++I)
-      ReportDiag(o, **I, FM, *SM, LangOpts);
+      ReportDiag(o, *I, FM, *SM, LangOpts);
 
     o << "   </array>\n";
 
diff --git a/clang/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp b/clang/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp
index d5706d6dbbe..9ba001eea51 100644
--- a/clang/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp
+++ b/clang/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp
@@ -61,12 +61,12 @@ void TextPathDiagnostics::FlushDiagnosticsImpl(
     const PathDiagnostic *D = *it;
 
     PathPieces FlatPath = D->path.flatten(/*ShouldFlattenMacros=*/true);
-    for (PathPieces::const_iterator I = FlatPath.begin(), E = FlatPath.end(); 
+    for (PathPieces::iterator I = FlatPath.begin(), E = FlatPath.end(); 
          I != E; ++I) {
       unsigned diagID =
         Diag.getDiagnosticIDs()->getCustomDiagID(DiagnosticIDs::Note,
-                                                 (*I)->getString());
-      Diag.Report((*I)->getLocation().asLocation(), diagID);
+                                                 I->getString());
+      Diag.Report(I->getLocation().asLocation(), diagID);
     }
   }
 }