[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.

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

6 files changed, 139 insertions, 52 deletions

diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h
index 7b5b1c2e2a..bd4f7c19b8 100644
--- a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h
+++ b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h
@@ -20,6 +20,8 @@
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
 #include <deque>
 #include <iterator>
 #include <string>
@@ -386,12 +388,32 @@ public:
 
   virtual void Profile(llvm::FoldingSetNodeID &ID) const;
 };
-  
-  
-class PathPieces : public std::deque<IntrusiveRefCntPtr<PathDiagnosticPiece> > {
+
+/// \brief An ordered collection of PathDiagnosticPieces.
+///
+/// Multiple PathPieces are allowed to reference the same PathDiagnosticPieces.
+/// This sharing is needed for some clients that want "flattened" copies
+/// of the same pieces.
+class PathPieces {
+  /// A simple wrapper for PathDiagnosticPiece, allowing sharing of
+  /// the same pieces between different PathPieces.
+  struct Node : public llvm::ilist_node<Node> {
+    IntrusiveRefCntPtr<PathDiagnosticPiece> Data;
+    explicit Node(PathDiagnosticPiece *P) : Data(P) {}
+    explicit Node() {}
+  };
+  llvm::ilist<Node> L;
+
   void flattenTo(PathPieces &Primary, PathPieces &Current,
                  bool ShouldFlattenMacros) const;
+
 public:
+  PathPieces() {}
+  PathPieces &operator=(const PathPieces & X);
+  PathPieces(const PathPieces &X) {
+    *this = X;
+  }
+
   ~PathPieces();
 
   PathPieces flatten(bool ShouldFlattenMacros) const {
@@ -399,6 +421,63 @@ public:
     flattenTo(Result, Result, ShouldFlattenMacros);
     return Result;
   }
+
+  class iterator {
+    typedef llvm::ilist<Node>::iterator impl_iterator;
+    friend class PathPieces;
+    impl_iterator Impl;
+    iterator(const impl_iterator &Impl) : Impl(Impl) {}
+  public:
+    typedef PathDiagnosticPiece value_type;
+    typedef value_type* pointer;
+    typedef value_type& reference;
+    typedef ptrdiff_t difference_type;
+    typedef std::bidirectional_iterator_tag iterator_category;
+
+    bool operator==(const iterator &X) const {
+      return Impl == X.Impl;
+    }
+
+    bool operator!=(const iterator &X) const {
+      return Impl != X.Impl;
+    }
+
+    reference operator*() const { return *Impl->Data; }
+    pointer operator->() const { return Impl->Data.getPtr(); }
+
+    iterator &operator++() {
+      ++Impl;
+      return *this;
+    }
+
+    iterator &operator--() {
+      --Impl;
+      return *this;
+    }
+  };
+
+  typedef std::reverse_iterator<iterator> reverse_iterator;
+
+  iterator begin() const { return iterator(const_cast<PathPieces*>(this)->L.begin()); }
+  iterator end() const { return iterator(const_cast<PathPieces*>(this)->L.end()); }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+
+  void push_front(PathDiagnosticPiece *P) {
+    L.push_front(new Node(P));
+  }
+  void pop_front() { L.pop_front(); }
+
+  void push_back(PathDiagnosticPiece *P) { L.push_back(new Node(P)); }
+  void push_back(const IntrusiveRefCntPtr<PathDiagnosticPiece> &P) {
+    push_back(P.getPtr());
+  }
+
+  PathDiagnosticPiece *front() const { return L.front().Data.getPtr(); }
+  PathDiagnosticPiece *back() const { return L.back().Data.getPtr(); }
+  void clear() { L.clear(); }
+  bool empty() const { return L.empty(); }
+  unsigned size() const { return L.size(); }
 };
 
 class PathDiagnosticSpotPiece : public PathDiagnosticPiece {
@@ -568,7 +647,7 @@ public:
     callEnter.flatten();
     callReturn.flatten();
     for (PathPieces::iterator I = path.begin(), 
-         E = path.end(); I != E; ++I) (*I)->flattenLocations();
+         E = path.end(); I != E; ++I) I->flattenLocations();
   }
   
   static PathDiagnosticCallPiece *construct(const ExplodedNode *N,
@@ -655,7 +734,7 @@ public:
   virtual void flattenLocations() {
     PathDiagnosticSpotPiece::flattenLocations();
     for (PathPieces::iterator I = subPieces.begin(), 
-         E = subPieces.end(); I != E; ++I) (*I)->flattenLocations();
+         E = subPieces.end(); I != E; ++I) I->flattenLocations();
   }
 
   static inline bool classof(const PathDiagnosticPiece *P) {
@@ -693,7 +772,7 @@ public:
 
   ~PathDiagnostic();
   
-  const PathPieces &path;
+  PathPieces &path;
 
   /// Return the path currently used by builders for constructing the 
   /// PathDiagnostic.
@@ -764,7 +843,7 @@ public:
   void flattenLocations() {
     Loc.flatten();
     for (PathPieces::iterator I = pathImpl.begin(), E = pathImpl.end(); 
-         I != E; ++I) (*I)->flattenLocations();
+         I != E; ++I) I->flattenLocations();
   }
 
   /// Profiles the diagnostic, independent of the path it references.
diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp
index 52c364e891..930f4bc99a 100644
--- a/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/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/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
index 73426da2b4..a5fe300fb6 100644
--- a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
+++ b/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/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
index 03513106ec..e2228aa13b 100644
--- a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
+++ b/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/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp b/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp
index 850955561e..2701951410 100644
--- a/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp
+++ b/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/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp b/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp
index d5706d6dbb..9ba001eea5 100644
--- a/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp
+++ b/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);
     }
   }
 }