4 files changed, 1089 insertions, 26 deletions

diff --git a/include/clang/Analysis/AnalysisDeclContext.h b/include/clang/Analysis/AnalysisDeclContext.h
index 1961d571e9e12..9faa78cde89c2 100644
--- a/include/clang/Analysis/AnalysisDeclContext.h
+++ b/include/clang/Analysis/AnalysisDeclContext.h
@@ -183,9 +183,8 @@ public:
   const ImplicitParamDecl *getSelfDecl() const;
 
   const StackFrameContext *getStackFrame(LocationContext const *Parent,
-                                         const Stmt *S,
-                                         const CFGBlock *Blk,
-                                         unsigned Idx);
+                                         const Stmt *S, const CFGBlock *Blk,
+                                         unsigned BlockCount, unsigned Idx);
 
   const BlockInvocationContext *
   getBlockInvocationContext(const LocationContext *parent,
@@ -258,7 +257,7 @@ public:
     return getAnalysisDeclContext()->getAnalysis<T>();
   }
 
-  ParentMap &getParentMap() const {
+  const ParentMap &getParentMap() const {
     return getAnalysisDeclContext()->getParentMap();
   }
 
@@ -303,15 +302,19 @@ class StackFrameContext : public LocationContext {
   // The parent block of the callsite.
   const CFGBlock *Block;
 
+  // The number of times the 'Block' has been visited.
+  // It allows discriminating between stack frames of the same call that is
+  // called multiple times in a loop.
+  const unsigned BlockCount;
+
   // The index of the callsite in the CFGBlock.
-  unsigned Index;
+  const unsigned Index;
 
   StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent,
-                    const Stmt *s, const CFGBlock *blk,
-                    unsigned idx,
-                    int64_t ID)
-      : LocationContext(StackFrame, ctx, parent, ID), CallSite(s),
-        Block(blk), Index(idx) {}
+                    const Stmt *s, const CFGBlock *blk, unsigned blockCount,
+                    unsigned idx, int64_t ID)
+      : LocationContext(StackFrame, ctx, parent, ID), CallSite(s), Block(blk),
+        BlockCount(blockCount), Index(idx) {}
 
 public:
   ~StackFrameContext() override = default;
@@ -329,9 +332,10 @@ public:
 
   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
                       const LocationContext *parent, const Stmt *s,
-                      const CFGBlock *blk, unsigned idx) {
+                      const CFGBlock *blk, unsigned blockCount, unsigned idx) {
     ProfileCommon(ID, StackFrame, ctx, parent, s);
     ID.AddPointer(blk);
+    ID.AddInteger(blockCount);
     ID.AddInteger(idx);
   }
 
@@ -410,8 +414,8 @@ public:
 
   const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
                                          const LocationContext *parent,
-                                         const Stmt *s,
-                                         const CFGBlock *blk, unsigned idx);
+                                         const Stmt *s, const CFGBlock *blk,
+                                         unsigned blockCount, unsigned idx);
 
   const ScopeContext *getScope(AnalysisDeclContext *ctx,
                                const LocationContext *parent,
@@ -483,26 +487,25 @@ public:
   bool synthesizeBodies() const { return SynthesizeBodies; }
 
   const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx,
-                                         LocationContext const *Parent,
-                                         const Stmt *S,
-                                         const CFGBlock *Blk,
-                                         unsigned Idx) {
-    return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx);
+                                         const LocationContext *Parent,
+                                         const Stmt *S, const CFGBlock *Blk,
+                                         unsigned BlockCount, unsigned Idx) {
+    return LocContexts.getStackFrame(Ctx, Parent, S, Blk, BlockCount, Idx);
   }
 
   // Get the top level stack frame.
   const StackFrameContext *getStackFrame(const Decl *D) {
     return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr,
-                                     0);
+                                     0, 0);
   }
 
   // Get a stack frame with parent.
   StackFrameContext const *getStackFrame(const Decl *D,
-                                         LocationContext const *Parent,
-                                         const Stmt *S,
-                                         const CFGBlock *Blk,
-                                         unsigned Idx) {
-    return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx);
+                                         const LocationContext *Parent,
+                                         const Stmt *S, const CFGBlock *Blk,
+                                         unsigned BlockCount, unsigned Idx) {
+    return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, BlockCount,
+                                     Idx);
   }
 
   /// Get a reference to {@code BodyFarm} instance.
diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h
index 277b2292e5eac..a8301a0e0063f 100644
--- a/include/clang/Analysis/CFG.h
+++ b/include/clang/Analysis/CFG.h
@@ -121,6 +121,12 @@ public:
     x |= Data1.getInt();
     return (Kind) x;
   }
+
+  void dumpToStream(llvm::raw_ostream &OS) const;
+
+  void dump() const {
+    dumpToStream(llvm::errs());
+  }
 };
 
 class CFGStmt : public CFGElement {
@@ -610,6 +616,153 @@ class CFGBlock {
     bool empty() const { return Impl.empty(); }
   };
 
+  /// A convenience class for comparing CFGElements, since methods of CFGBlock
+  /// like operator[] return CFGElements by value. This is practically a wrapper
+  /// around a (CFGBlock, Index) pair.
+  template <bool IsConst> class ElementRefImpl {
+
+    template <bool IsOtherConst> friend class ElementRefImpl;
+
+    using CFGBlockPtr =
+        typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
+
+    using CFGElementPtr = typename std::conditional<IsConst, const CFGElement *,
+                                                    CFGElement *>::type;
+
+  protected:
+    CFGBlockPtr Parent;
+    size_t Index;
+
+  public:
+    ElementRefImpl(CFGBlockPtr Parent, size_t Index)
+        : Parent(Parent), Index(Index) {}
+
+    template <bool IsOtherConst>
+    ElementRefImpl(ElementRefImpl<IsOtherConst> Other)
+        : ElementRefImpl(Other.Parent, Other.Index) {}
+
+    size_t getIndexInBlock() const { return Index; }
+
+    CFGBlockPtr getParent() { return Parent; }
+    CFGBlockPtr getParent() const { return Parent; }
+
+    bool operator<(ElementRefImpl Other) const {
+      return std::make_pair(Parent, Index) <
+             std::make_pair(Other.Parent, Other.Index);
+    }
+
+    bool operator==(ElementRefImpl Other) const {
+      return Parent == Other.Parent && Index == Other.Index;
+    }
+
+    bool operator!=(ElementRefImpl Other) const { return !(*this == Other); }
+    CFGElement operator*() const { return (*Parent)[Index]; }
+    CFGElementPtr operator->() const { return &*(Parent->begin() + Index); }
+
+    void dumpToStream(llvm::raw_ostream &OS) const {
+      OS << getIndexInBlock() + 1 << ": ";
+      (*this)->dumpToStream(OS);
+    }
+
+    void dump() const {
+      dumpToStream(llvm::errs());
+    }
+  };
+
+  template <bool IsReverse, bool IsConst> class ElementRefIterator {
+
+    template <bool IsOtherReverse, bool IsOtherConst>
+    friend class ElementRefIterator;
+
+    using CFGBlockRef =
+        typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
+
+    using UnderlayingIteratorTy = typename std::conditional<
+        IsConst,
+        typename std::conditional<IsReverse,
+                                  ElementList::const_reverse_iterator,
+                                  ElementList::const_iterator>::type,
+        typename std::conditional<IsReverse, ElementList::reverse_iterator,
+                                  ElementList::iterator>::type>::type;
+
+    using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>;
+    using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>;
+
+  public:
+    using difference_type = typename IteratorTraits::difference_type;
+    using value_type = ElementRef;
+    using pointer = ElementRef *;
+    using iterator_category = typename IteratorTraits::iterator_category;
+
+  private:
+    CFGBlockRef Parent;
+    UnderlayingIteratorTy Pos;
+
+  public:
+    ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos)
+        : Parent(Parent), Pos(Pos) {}
+
+    template <bool IsOtherConst>
+    ElementRefIterator(ElementRefIterator<false, IsOtherConst> E)
+        : ElementRefIterator(E.Parent, E.Pos.base()) {}
+
+    template <bool IsOtherConst>
+    ElementRefIterator(ElementRefIterator<true, IsOtherConst> E)
+        : ElementRefIterator(E.Parent, llvm::make_reverse_iterator(E.Pos)) {}
+
+    bool operator<(ElementRefIterator Other) const {
+      assert(Parent == Other.Parent);
+      return Pos < Other.Pos;
+    }
+
+    bool operator==(ElementRefIterator Other) const {
+      return Parent == Other.Parent && Pos == Other.Pos;
+    }
+
+    bool operator!=(ElementRefIterator Other) const {
+      return !(*this == Other);
+    }
+
+  private:
+    template <bool IsOtherConst>
+    static size_t
+    getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) {
+      return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1;
+    }
+
+    template <bool IsOtherConst>
+    static size_t
+    getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) {
+      return E.Pos - E.Parent->begin();
+    }
+
+  public:
+    value_type operator*() { return {Parent, getIndexInBlock(*this)}; }
+
+    difference_type operator-(ElementRefIterator Other) const {
+      return Pos - Other.Pos;
+    }
+
+    ElementRefIterator operator++() {
+      ++this->Pos;
+      return *this;
+    }
+    ElementRefIterator operator++(int) {
+      ElementRefIterator Ret = *this;
+      ++*this;
+      return Ret;
+    }
+    ElementRefIterator operator+(size_t count) {
+      this->Pos += count;
+      return *this;
+    }
+    ElementRefIterator operator-(size_t count) {
+      this->Pos -= count;
+      return *this;
+    }
+  };
+
+public:
   /// The set of statements in the basic block.
   ElementList Elements;
 
@@ -715,6 +868,8 @@ public:
   using reverse_iterator = ElementList::reverse_iterator;
   using const_reverse_iterator = ElementList::const_reverse_iterator;
 
+  size_t getIndexInCFG() const;
+
   CFGElement                 front()       const { return Elements.front();   }
   CFGElement                 back()        const { return Elements.back();    }
 
@@ -728,6 +883,38 @@ public:
   const_reverse_iterator     rbegin()      const { return Elements.rbegin();  }
   const_reverse_iterator     rend()        const { return Elements.rend();    }
 
+  using CFGElementRef = ElementRefImpl<false>;
+  using ConstCFGElementRef = ElementRefImpl<true>;
+
+  using ref_iterator = ElementRefIterator<false, false>;
+  using ref_iterator_range = llvm::iterator_range<ref_iterator>;
+  using const_ref_iterator = ElementRefIterator<false, true>;
+  using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>;
+
+  using reverse_ref_iterator = ElementRefIterator<true, false>;
+  using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>;
+
+  using const_reverse_ref_iterator = ElementRefIterator<true, true>;
+  using const_reverse_ref_iterator_range =
+      llvm::iterator_range<const_reverse_ref_iterator>;
+
+  ref_iterator ref_begin() { return {this, begin()}; }
+  ref_iterator ref_end() { return {this, end()}; }
+  const_ref_iterator ref_begin() const { return {this, begin()}; }
+  const_ref_iterator ref_end() const { return {this, end()}; }
+
+  reverse_ref_iterator rref_begin() { return {this, rbegin()}; }
+  reverse_ref_iterator rref_end() { return {this, rend()}; }
+  const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; }
+  const_reverse_ref_iterator rref_end() const { return {this, rend()}; }
+
+  ref_iterator_range refs() { return {ref_begin(), ref_end()}; }
+  const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; }
+  reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; }
+  const_reverse_ref_iterator_range rrefs() const {
+    return {rref_begin(), rref_end()};
+  }
+
   unsigned                   size()        const { return Elements.size();    }
   bool                       empty()       const { return Elements.empty();   }
 
@@ -855,6 +1042,10 @@ public:
   void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
   void setHasNoReturnElement() { HasNoReturnElement = true; }
 
+  /// Returns true if the block would eventually end with a sink (a noreturn
+  /// node).
+  bool isInevitablySinking() const;
+
   CFGTerminator getTerminator() const { return Terminator; }
 
   Stmt *getTerminatorStmt() { return Terminator.getStmt(); }
@@ -894,7 +1085,7 @@ public:
   void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
   void printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
                            bool AddQuotes) const;
-  
+
   void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
     OS << "BB#" << getBlockID();
   }
@@ -1010,7 +1201,6 @@ public:
     *I = CFGScopeEnd(VD, S);
     return ++I;
   }
-
 };
 
 /// CFGCallback defines methods that should be called when a logical
@@ -1023,6 +1213,7 @@ public:
   virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
   virtual void compareBitwiseEquality(const BinaryOperator *B,
                                       bool isAlwaysTrue) {}
+  virtual void compareBitwiseOr(const BinaryOperator *B) {}
 };
 
 /// Represents a source-level, intra-procedural CFG that represents the
diff --git a/include/clang/Analysis/CallGraph.h b/include/clang/Analysis/CallGraph.h
index 49c04490fed2c..dae2b58ffc102 100644
--- a/include/clang/Analysis/CallGraph.h
+++ b/include/clang/Analysis/CallGraph.h
@@ -131,6 +131,7 @@ public:
 
   bool shouldWalkTypesOfTypeLocs() const { return false; }
   bool shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const { return true; }
 
 private:
   /// Add the given declaration to the call graph.
diff --git a/include/clang/Analysis/PathDiagnostic.h b/include/clang/Analysis/PathDiagnostic.h
new file mode 100644
index 0000000000000..6730057cf0adc
--- /dev/null
+++ b/include/clang/Analysis/PathDiagnostic.h
@@ -0,0 +1,868 @@
+//===- PathDiagnostic.h - Path-Specific Diagnostic Handling -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the PathDiagnostic-related interfaces.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_PATHDIAGNOSTIC_H
+#define LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_PATHDIAGNOSTIC_H
+
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
+#include <cassert>
+#include <deque>
+#include <iterator>
+#include <list>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace clang {
+
+class AnalysisDeclContext;
+class BinaryOperator;
+class CallEnter;
+class CallExitEnd;
+class CallExpr;
+class ConditionalOperator;
+class Decl;
+class Expr;
+class LocationContext;
+class MemberExpr;
+class ProgramPoint;
+class SourceManager;
+
+namespace ento {
+
+//===----------------------------------------------------------------------===//
+// High-level interface for handlers of path-sensitive diagnostics.
+//===----------------------------------------------------------------------===//
+
+class PathDiagnostic;
+
+class PathDiagnosticConsumer {
+public:
+  class PDFileEntry : public llvm::FoldingSetNode {
+  public:
+    PDFileEntry(llvm::FoldingSetNodeID &NodeID) : NodeID(NodeID) {}
+
+    using ConsumerFiles = std::vector<std::pair<StringRef, StringRef>>;
+
+    /// A vector of <consumer,file> pairs.
+    ConsumerFiles files;
+
+    /// A precomputed hash tag used for uniquing PDFileEntry objects.
+    const llvm::FoldingSetNodeID NodeID;
+
+    /// Used for profiling in the FoldingSet.
+    void Profile(llvm::FoldingSetNodeID &ID) { ID = NodeID; }
+  };
+
+  class FilesMade {
+    llvm::BumpPtrAllocator Alloc;
+    llvm::FoldingSet<PDFileEntry> Set;
+
+  public:
+    ~FilesMade();
+
+    bool empty() const { return Set.empty(); }
+
+    void addDiagnostic(const PathDiagnostic &PD,
+                       StringRef ConsumerName,
+                       StringRef fileName);
+
+    PDFileEntry::ConsumerFiles *getFiles(const PathDiagnostic &PD);
+  };
+
+private:
+  virtual void anchor();
+
+public:
+  PathDiagnosticConsumer() = default;
+  virtual ~PathDiagnosticConsumer();
+
+  void FlushDiagnostics(FilesMade *FilesMade);
+
+  virtual void FlushDiagnosticsImpl(std::vector<const PathDiagnostic *> &Diags,
+                                    FilesMade *filesMade) = 0;
+
+  virtual StringRef getName() const = 0;
+
+  void HandlePathDiagnostic(std::unique_ptr<PathDiagnostic> D);
+
+  enum PathGenerationScheme {
+    /// Only runs visitors, no output generated.
+    None,
+
+    /// Used for HTML, SARIF, and text output.
+    Minimal,
+
+    /// Used for plist output, used for "arrows" generation.
+    Extensive,
+  };
+
+  virtual PathGenerationScheme getGenerationScheme() const { return Minimal; }
+
+  bool shouldGenerateDiagnostics() const {
+    return getGenerationScheme() != None;
+  }
+
+  bool shouldAddPathEdges() const { return getGenerationScheme() == Extensive; }
+
+  virtual bool supportsLogicalOpControlFlow() const { return false; }
+
+  /// Return true if the PathDiagnosticConsumer supports individual
+  /// PathDiagnostics that span multiple files.
+  virtual bool supportsCrossFileDiagnostics() const { return false; }
+
+protected:
+  bool flushed = false;
+  llvm::FoldingSet<PathDiagnostic> Diags;
+};
+
+//===----------------------------------------------------------------------===//
+// Path-sensitive diagnostics.
+//===----------------------------------------------------------------------===//
+
+class PathDiagnosticRange : public SourceRange {
+public:
+  bool isPoint = false;
+
+  PathDiagnosticRange(SourceRange R, bool isP = false)
+      : SourceRange(R), isPoint(isP) {}
+  PathDiagnosticRange() = default;
+};
+
+using LocationOrAnalysisDeclContext =
+    llvm::PointerUnion<const LocationContext *, AnalysisDeclContext *>;
+
+class PathDiagnosticLocation {
+private:
+  enum Kind { RangeK, SingleLocK, StmtK, DeclK } K = SingleLocK;
+
+  const Stmt *S = nullptr;
+  const Decl *D = nullptr;
+  const SourceManager *SM = nullptr;
+  FullSourceLoc Loc;
+  PathDiagnosticRange Range;
+
+  PathDiagnosticLocation(SourceLocation L, const SourceManager &sm, Kind kind)
+      : K(kind), SM(&sm), Loc(genLocation(L)), Range(genRange()) {}
+
+  FullSourceLoc genLocation(
+      SourceLocation L = SourceLocation(),
+      LocationOrAnalysisDeclContext LAC = (AnalysisDeclContext *)nullptr) const;
+
+  PathDiagnosticRange genRange(
+      LocationOrAnalysisDeclContext LAC = (AnalysisDeclContext *)nullptr) const;
+
+public:
+  /// Create an invalid location.
+  PathDiagnosticLocation() = default;
+
+  /// Create a location corresponding to the given statement.
+  PathDiagnosticLocation(const Stmt *s, const SourceManager &sm,
+                         LocationOrAnalysisDeclContext lac)
+      : K(s->getBeginLoc().isValid() ? StmtK : SingleLocK),
+        S(K == StmtK ? s : nullptr), SM(&sm),
+        Loc(genLocation(SourceLocation(), lac)), Range(genRange(lac)) {
+    assert(K == SingleLocK || S);
+    assert(K == SingleLocK || Loc.isValid());
+    assert(K == SingleLocK || Range.isValid());
+  }
+
+  /// Create a location corresponding to the given declaration.
+  PathDiagnosticLocation(const Decl *d, const SourceManager &sm)
+      : K(DeclK), D(d), SM(&sm), Loc(genLocation()), Range(genRange()) {
+    assert(D);
+    assert(Loc.isValid());
+    assert(Range.isValid());
+  }
+
+  /// Create a location at an explicit offset in the source.
+  ///
+  /// This should only be used if there are no more appropriate constructors.
+  PathDiagnosticLocation(SourceLocation loc, const SourceManager &sm)
+      : SM(&sm), Loc(loc, sm), Range(genRange()) {
+    assert(Loc.isValid());
+    assert(Range.isValid());
+  }
+
+  /// Create a location corresponding to the given declaration.
+  static PathDiagnosticLocation create(const Decl *D,
+                                       const SourceManager &SM) {
+    return PathDiagnosticLocation(D, SM);
+  }
+
+  /// Create a location for the beginning of the declaration.
+  static PathDiagnosticLocation createBegin(const Decl *D,
+                                            const SourceManager &SM);
+
+  /// Create a location for the beginning of the declaration.
+  /// The third argument is ignored, useful for generic treatment
+  /// of statements and declarations.
+  static PathDiagnosticLocation
+  createBegin(const Decl *D, const SourceManager &SM,
+              const LocationOrAnalysisDeclContext LAC) {
+    return createBegin(D, SM);
+  }
+
+  /// Create a location for the beginning of the statement.
+  static PathDiagnosticLocation createBegin(const Stmt *S,
+                                            const SourceManager &SM,
+                                            const LocationOrAnalysisDeclContext LAC);
+
+  /// Create a location for the end of the statement.
+  ///
+  /// If the statement is a CompoundStatement, the location will point to the
+  /// closing brace instead of following it.
+  static PathDiagnosticLocation createEnd(const Stmt *S,
+                                          const SourceManager &SM,
+                                       const LocationOrAnalysisDeclContext LAC);
+
+  /// Create the location for the operator of the binary expression.
+  /// Assumes the statement has a valid location.
+  static PathDiagnosticLocation createOperatorLoc(const BinaryOperator *BO,
+                                                  const SourceManager &SM);
+  static PathDiagnosticLocation createConditionalColonLoc(
+                                                  const ConditionalOperator *CO,
+                                                  const SourceManager &SM);
+
+  /// For member expressions, return the location of the '.' or '->'.
+  /// Assumes the statement has a valid location.
+  static PathDiagnosticLocation createMemberLoc(const MemberExpr *ME,
+                                                const SourceManager &SM);
+
+  /// Create a location for the beginning of the compound statement.
+  /// Assumes the statement has a valid location.
+  static PathDiagnosticLocation createBeginBrace(const CompoundStmt *CS,
+                                                 const SourceManager &SM);
+
+  /// Create a location for the end of the compound statement.
+  /// Assumes the statement has a valid location.
+  static PathDiagnosticLocation createEndBrace(const CompoundStmt *CS,
+                                               const SourceManager &SM);
+
+  /// Create a location for the beginning of the enclosing declaration body.
+  /// Defaults to the beginning of the first statement in the declaration body.
+  static PathDiagnosticLocation createDeclBegin(const LocationContext *LC,
+                                                const SourceManager &SM);
+
+  /// Constructs a location for the end of the enclosing declaration body.
+  /// Defaults to the end of brace.
+  static PathDiagnosticLocation createDeclEnd(const LocationContext *LC,
+                                                   const SourceManager &SM);
+
+  /// Create a location corresponding to the given valid ProgramPoint.
+  static PathDiagnosticLocation create(const ProgramPoint &P,
+                                       const SourceManager &SMng);
+
+  /// Convert the given location into a single kind location.
+  static PathDiagnosticLocation createSingleLocation(
+                                             const PathDiagnosticLocation &PDL);
+
+  /// Construct a source location that corresponds to either the beginning
+  /// or the end of the given statement, or a nearby valid source location
+  /// if the statement does not have a valid source location of its own.
+  static SourceLocation
+  getValidSourceLocation(const Stmt *S, LocationOrAnalysisDeclContext LAC,
+                         bool UseEndOfStatement = false);
+
+  bool operator==(const PathDiagnosticLocation &X) const {
+    return K == X.K && Loc == X.Loc && Range == X.Range;
+  }
+
+  bool operator!=(const PathDiagnosticLocation &X) const {
+    return !(*this == X);
+  }
+
+  bool isValid() const {
+    return SM != nullptr;
+  }
+
+  FullSourceLoc asLocation() const {
+    return Loc;
+  }
+
+  PathDiagnosticRange asRange() const {
+    return Range;
+  }
+
+  const Stmt *asStmt() const { assert(isValid()); return S; }
+  const Stmt *getStmtOrNull() const {
+    if (!isValid())
+      return nullptr;
+    return asStmt();
+  }
+
+  const Decl *asDecl() const { assert(isValid()); return D; }
+
+  bool hasRange() const { return K == StmtK || K == RangeK || K == DeclK; }
+
+  bool hasValidLocation() const { return asLocation().isValid(); }
+
+  void invalidate() {
+    *this = PathDiagnosticLocation();
+  }
+
+  void flatten();
+
+  const SourceManager& getManager() const { assert(isValid()); return *SM; }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const;
+
+  void dump() const;
+};
+
+class PathDiagnosticLocationPair {
+private:
+  PathDiagnosticLocation Start, End;
+
+public:
+  PathDiagnosticLocationPair(const PathDiagnosticLocation &start,
+                             const PathDiagnosticLocation &end)
+      : Start(start), End(end) {}
+
+  const PathDiagnosticLocation &getStart() const { return Start; }
+  const PathDiagnosticLocation &getEnd() const { return End; }
+
+  void setStart(const PathDiagnosticLocation &L) { Start = L; }
+  void setEnd(const PathDiagnosticLocation &L) { End = L; }
+
+  void flatten() {
+    Start.flatten();
+    End.flatten();
+  }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    Start.Profile(ID);
+    End.Profile(ID);
+  }
+};
+
+//===----------------------------------------------------------------------===//
+// Path "pieces" for path-sensitive diagnostics.
+//===----------------------------------------------------------------------===//
+
+class PathDiagnosticPiece: public llvm::FoldingSetNode {
+public:
+  enum Kind { ControlFlow, Event, Macro, Call, Note, PopUp };
+  enum DisplayHint { Above, Below };
+
+private:
+  const std::string str;
+  const Kind kind;
+  const DisplayHint Hint;
+
+  /// In the containing bug report, this piece is the last piece from
+  /// the main source file.
+  bool LastInMainSourceFile = false;
+
+  /// A constant string that can be used to tag the PathDiagnosticPiece,
+  /// typically with the identification of the creator.  The actual pointer
+  /// value is meant to be an identifier; the string itself is useful for
+  /// debugging.
+  StringRef Tag;
+
+  std::vector<SourceRange> ranges;
+  std::vector<FixItHint> fixits;
+
+protected:
+  PathDiagnosticPiece(StringRef s, Kind k, DisplayHint hint = Below);
+  PathDiagnosticPiece(Kind k, DisplayHint hint = Below);
+
+public:
+  PathDiagnosticPiece() = delete;
+  PathDiagnosticPiece(const PathDiagnosticPiece &) = delete;
+  PathDiagnosticPiece &operator=(const PathDiagnosticPiece &) = delete;
+  virtual ~PathDiagnosticPiece();
+
+  StringRef getString() const { return str; }
+
+  /// Tag this PathDiagnosticPiece with the given C-string.
+  void setTag(const char *tag) { Tag = tag; }
+
+  /// Return the opaque tag (if any) on the PathDiagnosticPiece.
+  const void *getTag() const { return Tag.data(); }
+
+  /// Return the string representation of the tag.  This is useful
+  /// for debugging.
+  StringRef getTagStr() const { return Tag; }
+
+  /// getDisplayHint - Return a hint indicating where the diagnostic should
+  ///  be displayed by the PathDiagnosticConsumer.
+  DisplayHint getDisplayHint() const { return Hint; }
+
+  virtual PathDiagnosticLocation getLocation() const = 0;
+  virtual void flattenLocations() = 0;
+
+  Kind getKind() const { return kind; }
+
+  void addRange(SourceRange R) {
+    if (!R.isValid())
+      return;
+    ranges.push_back(R);
+  }
+
+  void addRange(SourceLocation B, SourceLocation E) {
+    if (!B.isValid() || !E.isValid())
+      return;
+    ranges.push_back(SourceRange(B,E));
+  }
+
+  void addFixit(FixItHint F) {
+    fixits.push_back(F);
+  }
+
+  /// Return the SourceRanges associated with this PathDiagnosticPiece.
+  ArrayRef<SourceRange> getRanges() const { return ranges; }
+
+  /// Return the fix-it hints associated with this PathDiagnosticPiece.
+  ArrayRef<FixItHint> getFixits() const { return fixits; }
+
+  virtual void Profile(llvm::FoldingSetNodeID &ID) const;
+
+  void setAsLastInMainSourceFile() {
+    LastInMainSourceFile = true;
+  }
+
+  bool isLastInMainSourceFile() const {
+    return LastInMainSourceFile;
+  }
+
+  virtual void dump() const = 0;
+};
+
+using PathDiagnosticPieceRef = std::shared_ptr<PathDiagnosticPiece>;
+
+class PathPieces : public std::list<PathDiagnosticPieceRef> {
+  void flattenTo(PathPieces &Primary, PathPieces &Current,
+                 bool ShouldFlattenMacros) const;
+
+public:
+  PathPieces flatten(bool ShouldFlattenMacros) const {
+    PathPieces Result;
+    flattenTo(Result, Result, ShouldFlattenMacros);
+    return Result;
+  }
+
+  void dump() const;
+};
+
+class PathDiagnosticSpotPiece : public PathDiagnosticPiece {
+private:
+  PathDiagnosticLocation Pos;
+
+public:
+  PathDiagnosticSpotPiece(const PathDiagnosticLocation &pos,
+                          StringRef s,
+                          PathDiagnosticPiece::Kind k,
+                          bool addPosRange = true)
+      : PathDiagnosticPiece(s, k), Pos(pos) {
+    assert(Pos.isValid() && Pos.hasValidLocation() &&
+           "PathDiagnosticSpotPiece's must have a valid location.");
+    if (addPosRange && Pos.hasRange()) addRange(Pos.asRange());
+  }
+
+  PathDiagnosticLocation getLocation() const override { return Pos; }
+  void flattenLocations() override { Pos.flatten(); }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == Event || P->getKind() == Macro ||
+           P->getKind() == Note || P->getKind() == PopUp;
+  }
+};
+
+class PathDiagnosticEventPiece : public PathDiagnosticSpotPiece {
+  Optional<bool> IsPrunable;
+
+public:
+  PathDiagnosticEventPiece(const PathDiagnosticLocation &pos,
+                           StringRef s, bool addPosRange = true)
+      : PathDiagnosticSpotPiece(pos, s, Event, addPosRange) {}
+  ~PathDiagnosticEventPiece() override;
+
+  /// Mark the diagnostic piece as being potentially prunable.  This
+  /// flag may have been previously set, at which point it will not
+  /// be reset unless one specifies to do so.
+  void setPrunable(bool isPrunable, bool override = false) {
+    if (IsPrunable.hasValue() && !override)
+     return;
+    IsPrunable = isPrunable;
+  }
+
+  /// Return true if the diagnostic piece is prunable.
+  bool isPrunable() const {
+    return IsPrunable.hasValue() ? IsPrunable.getValue() : false;
+  }
+
+  void dump() const override;
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == Event;
+  }
+};
+
+class PathDiagnosticCallPiece : public PathDiagnosticPiece {
+  const Decl *Caller;
+  const Decl *Callee = nullptr;
+
+  // Flag signifying that this diagnostic has only call enter and no matching
+  // call exit.
+  bool NoExit;
+
+  // Flag signifying that the callee function is an Objective-C autosynthesized
+  // property getter or setter.
+  bool IsCalleeAnAutosynthesizedPropertyAccessor = false;
+
+  // The custom string, which should appear after the call Return Diagnostic.
+  // TODO: Should we allow multiple diagnostics?
+  std::string CallStackMessage;
+
+  PathDiagnosticCallPiece(const Decl *callerD,
+                          const PathDiagnosticLocation &callReturnPos)
+      : PathDiagnosticPiece(Call), Caller(callerD), NoExit(false),
+        callReturn(callReturnPos) {}
+  PathDiagnosticCallPiece(PathPieces &oldPath, const Decl *caller)
+      : PathDiagnosticPiece(Call), Caller(caller), NoExit(true),
+        path(oldPath) {}
+
+public:
+  PathDiagnosticLocation callEnter;
+  PathDiagnosticLocation callEnterWithin;
+  PathDiagnosticLocation callReturn;
+  PathPieces path;
+
+  ~PathDiagnosticCallPiece() override;
+
+  const Decl *getCaller() const { return Caller; }
+
+  const Decl *getCallee() const { return Callee; }
+  void setCallee(const CallEnter &CE, const SourceManager &SM);
+
+  bool hasCallStackMessage() { return !CallStackMessage.empty(); }
+  void setCallStackMessage(StringRef st) { CallStackMessage = st; }
+
+  PathDiagnosticLocation getLocation() const override { return callEnter; }
+
+  std::shared_ptr<PathDiagnosticEventPiece> getCallEnterEvent() const;
+  std::shared_ptr<PathDiagnosticEventPiece>
+  getCallEnterWithinCallerEvent() const;
+  std::shared_ptr<PathDiagnosticEventPiece> getCallExitEvent() const;
+
+  void flattenLocations() override {
+    callEnter.flatten();
+    callReturn.flatten();
+    for (const auto &I : path)
+      I->flattenLocations();
+  }
+
+  static std::shared_ptr<PathDiagnosticCallPiece>
+  construct(const CallExitEnd &CE,
+            const SourceManager &SM);
+
+  static PathDiagnosticCallPiece *construct(PathPieces &pieces,
+                                            const Decl *caller);
+
+  void dump() const override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == Call;
+  }
+};
+
+class PathDiagnosticControlFlowPiece : public PathDiagnosticPiece {
+  std::vector<PathDiagnosticLocationPair> LPairs;
+
+public:
+  PathDiagnosticControlFlowPiece(const PathDiagnosticLocation &startPos,
+                                 const PathDiagnosticLocation &endPos,
+                                 StringRef s)
+      : PathDiagnosticPiece(s, ControlFlow) {
+    LPairs.push_back(PathDiagnosticLocationPair(startPos, endPos));
+  }
+
+  PathDiagnosticControlFlowPiece(const PathDiagnosticLocation &startPos,
+                                 const PathDiagnosticLocation &endPos)
+      : PathDiagnosticPiece(ControlFlow) {
+    LPairs.push_back(PathDiagnosticLocationPair(startPos, endPos));
+  }
+
+  ~PathDiagnosticControlFlowPiece() override;
+
+  PathDiagnosticLocation getStartLocation() const {
+    assert(!LPairs.empty() &&
+           "PathDiagnosticControlFlowPiece needs at least one location.");
+    return LPairs[0].getStart();
+  }
+
+  PathDiagnosticLocation getEndLocation() const {
+    assert(!LPairs.empty() &&
+           "PathDiagnosticControlFlowPiece needs at least one location.");
+    return LPairs[0].getEnd();
+  }
+
+  void setStartLocation(const PathDiagnosticLocation &L) {
+    LPairs[0].setStart(L);
+  }
+
+  void setEndLocation(const PathDiagnosticLocation &L) {
+    LPairs[0].setEnd(L);
+  }
+
+  void push_back(const PathDiagnosticLocationPair &X) { LPairs.push_back(X); }
+
+  PathDiagnosticLocation getLocation() const override {
+    return getStartLocation();
+  }
+
+  using iterator = std::vector<PathDiagnosticLocationPair>::iterator;
+
+  iterator begin() { return LPairs.begin(); }
+  iterator end() { return LPairs.end(); }
+
+  void flattenLocations() override {
+    for (auto &I : *this)
+      I.flatten();
+  }
+
+  using const_iterator =
+      std::vector<PathDiagnosticLocationPair>::const_iterator;
+
+  const_iterator begin() const { return LPairs.begin(); }
+  const_iterator end() const { return LPairs.end(); }
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == ControlFlow;
+  }
+
+  void dump() const override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+};
+
+class PathDiagnosticMacroPiece : public PathDiagnosticSpotPiece {
+public:
+  PathDiagnosticMacroPiece(const PathDiagnosticLocation &pos)
+      : PathDiagnosticSpotPiece(pos, "", Macro) {}
+  ~PathDiagnosticMacroPiece() override;
+
+  PathPieces subPieces;
+
+  void flattenLocations() override {
+    PathDiagnosticSpotPiece::flattenLocations();
+    for (const auto &I : subPieces)
+      I->flattenLocations();
+  }
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == Macro;
+  }
+
+  void dump() const override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+};
+
+class PathDiagnosticNotePiece: public PathDiagnosticSpotPiece {
+public:
+  PathDiagnosticNotePiece(const PathDiagnosticLocation &Pos, StringRef S,
+                          bool AddPosRange = true)
+      : PathDiagnosticSpotPiece(Pos, S, Note, AddPosRange) {}
+  ~PathDiagnosticNotePiece() override;
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == Note;
+  }
+
+  void dump() const override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+};
+
+class PathDiagnosticPopUpPiece: public PathDiagnosticSpotPiece {
+public:
+  PathDiagnosticPopUpPiece(const PathDiagnosticLocation &Pos, StringRef S,
+                           bool AddPosRange = true)
+      : PathDiagnosticSpotPiece(Pos, S, PopUp, AddPosRange) {}
+  ~PathDiagnosticPopUpPiece() override;
+
+  static bool classof(const PathDiagnosticPiece *P) {
+    return P->getKind() == PopUp;
+  }
+
+  void dump() const override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+};
+
+/// File IDs mapped to sets of line numbers.
+using FilesToLineNumsMap = std::map<FileID, std::set<unsigned>>;
+
+/// PathDiagnostic - PathDiagnostic objects represent a single path-sensitive
+///  diagnostic.  It represents an ordered-collection of PathDiagnosticPieces,
+///  each which represent the pieces of the path.
+class PathDiagnostic : public llvm::FoldingSetNode {
+  std::string CheckerName;
+  const Decl *DeclWithIssue;
+  std::string BugType;
+  std::string VerboseDesc;
+  std::string ShortDesc;
+  std::string Category;
+  std::deque<std::string> OtherDesc;
+
+  /// Loc The location of the path diagnostic report.
+  PathDiagnosticLocation Loc;
+
+  PathPieces pathImpl;
+  SmallVector<PathPieces *, 3> pathStack;
+
+  /// Important bug uniqueing location.
+  /// The location info is useful to differentiate between bugs.
+  PathDiagnosticLocation UniqueingLoc;
+  const Decl *UniqueingDecl;
+
+  /// Lines executed in the path.
+  std::unique_ptr<FilesToLineNumsMap> ExecutedLines;
+
+public:
+  PathDiagnostic() = delete;
+  PathDiagnostic(StringRef CheckerName, const Decl *DeclWithIssue,
+                 StringRef bugtype, StringRef verboseDesc, StringRef shortDesc,
+                 StringRef category, PathDiagnosticLocation LocationToUnique,
+                 const Decl *DeclToUnique,
+                 std::unique_ptr<FilesToLineNumsMap> ExecutedLines);
+  ~PathDiagnostic();
+
+  const PathPieces &path;
+
+  /// Return the path currently used by builders for constructing the
+  /// PathDiagnostic.
+  PathPieces &getActivePath() {
+    if (pathStack.empty())
+      return pathImpl;
+    return *pathStack.back();
+  }
+
+  /// Return a mutable version of 'path'.
+  PathPieces &getMutablePieces() {
+    return pathImpl;
+  }
+
+  /// Return the unrolled size of the path.
+  unsigned full_size();
+
+  void pushActivePath(PathPieces *p) { pathStack.push_back(p); }
+  void popActivePath() { if (!pathStack.empty()) pathStack.pop_back(); }
+
+  bool isWithinCall() const { return !pathStack.empty(); }
+
+  void setEndOfPath(PathDiagnosticPieceRef EndPiece) {
+    assert(!Loc.isValid() && "End location already set!");
+    Loc = EndPiece->getLocation();
+    assert(Loc.isValid() && "Invalid location for end-of-path piece");
+    getActivePath().push_back(std::move(EndPiece));
+  }
+
+  void appendToDesc(StringRef S) {
+    if (!ShortDesc.empty())
+      ShortDesc += S;
+    VerboseDesc += S;
+  }
+
+  StringRef getVerboseDescription() const { return VerboseDesc; }
+
+  StringRef getShortDescription() const {
+    return ShortDesc.empty() ? VerboseDesc : ShortDesc;
+  }
+
+  StringRef getCheckerName() const { return CheckerName; }
+  StringRef getBugType() const { return BugType; }
+  StringRef getCategory() const { return Category; }
+
+  using meta_iterator = std::deque<std::string>::const_iterator;
+
+  meta_iterator meta_begin() const { return OtherDesc.begin(); }
+  meta_iterator meta_end() const { return OtherDesc.end(); }
+  void addMeta(StringRef s) { OtherDesc.push_back(s); }
+
+  const FilesToLineNumsMap &getExecutedLines() const {
+    return *ExecutedLines;
+  }
+
+  FilesToLineNumsMap &getExecutedLines() {
+    return *ExecutedLines;
+  }
+
+  /// Return the semantic context where an issue occurred.  If the
+  /// issue occurs along a path, this represents the "central" area
+  /// where the bug manifests.
+  const Decl *getDeclWithIssue() const { return DeclWithIssue; }
+
+  void setDeclWithIssue(const Decl *D) {
+    DeclWithIssue = D;
+  }
+
+  PathDiagnosticLocation getLocation() const {
+    return Loc;
+  }
+
+  void setLocation(PathDiagnosticLocation NewLoc) {
+    Loc = NewLoc;
+  }
+
+  /// Get the location on which the report should be uniqued.
+  PathDiagnosticLocation getUniqueingLoc() const {
+    return UniqueingLoc;
+  }
+
+  /// Get the declaration containing the uniqueing location.
+  const Decl *getUniqueingDecl() const {
+    return UniqueingDecl;
+  }
+
+  void flattenLocations() {
+    Loc.flatten();
+    for (const auto &I : pathImpl)
+      I->flattenLocations();
+  }
+
+  /// Profiles the diagnostic, independent of the path it references.
+  ///
+  /// This can be used to merge diagnostics that refer to the same issue
+  /// along different paths.
+  void Profile(llvm::FoldingSetNodeID &ID) const;
+
+  /// Profiles the diagnostic, including its path.
+  ///
+  /// Two diagnostics with the same issue along different paths will generate
+  /// different profiles.
+  void FullProfile(llvm::FoldingSetNodeID &ID) const;
+};
+
+} // namespace ento
+} // namespace clang
+
+#endif // LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_PATHDIAGNOSTIC_H