//===- PathDiagnostic.cpp - Path-Specific Diagnostic Handling -------------===//

//

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

//

//===----------------------------------------------------------------------===//

#include "clang/Analysis/PathDiagnostic.h"

#include "clang/AST/Decl.h"

#include "clang/AST/DeclBase.h"

#include "clang/AST/DeclCXX.h"

#include "clang/AST/DeclObjC.h"

#include "clang/AST/DeclTemplate.h"

#include "clang/AST/Expr.h"

#include "clang/AST/ExprCXX.h"

#include "clang/AST/OperationKinds.h"

#include "clang/AST/ParentMap.h"

#include "clang/AST/PrettyPrinter.h"

#include "clang/AST/Stmt.h"

#include "clang/AST/Type.h"

#include "clang/Analysis/AnalysisDeclContext.h"

#include "clang/Analysis/CFG.h"

#include "clang/Analysis/ProgramPoint.h"

#include "clang/Basic/FileManager.h"

#include "clang/Basic/LLVM.h"

#include "clang/Basic/SourceLocation.h"

#include "clang/Basic/SourceManager.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/FoldingSet.h"

#include "llvm/ADT/None.h"

#include "llvm/ADT/Optional.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallString.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/StringExtras.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/raw_ostream.h"

#include <cassert>

#include <cstring>

#include <memory>

#include <utility>

#include <vector>

using namespace clang;

using namespace ento;

static StringRef StripTrailingDots(StringRef s) {

  for (StringRef::size_type i = s.size(); i != 0; 
--i1.93k
)

    if (s[i - 1] != '.')

      return s.substr(0, i);

  return {};

}

PathDiagnosticPiece::PathDiagnosticPiece(StringRef s,

                                         Kind k, DisplayHint hint)

    : str(StripTrailingDots(s)), kind(k), Hint(hint) {}

PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint)

    : kind(k), Hint(hint) {}

PathDiagnosticPiece::~PathDiagnosticPiece() = default;

PathDiagnosticEventPiece::~PathDiagnosticEventPiece() = default;

PathDiagnosticCallPiece::~PathDiagnosticCallPiece() = default;

PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() = default;

PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() = default;

PathDiagnosticNotePiece::~PathDiagnosticNotePiece() = default;

PathDiagnosticPopUpPiece::~PathDiagnosticPopUpPiece() = default;

void PathPieces::flattenTo(PathPieces &Primary, PathPieces &Current,

                           bool ShouldFlattenMacros) const {

  for (auto &Piece : *this) {

    switch (Piece->getKind()) {

    case PathDiagnosticPiece::Call: {

      auto &Call = cast<PathDiagnosticCallPiece>(*Piece);

      if (auto CallEnter = Call.getCallEnterEvent())

        Current.push_back(std::move(CallEnter));

      Call.path.flattenTo(Primary, Primary, ShouldFlattenMacros);

      if (auto callExit = Call.getCallExitEvent())

        Current.push_back(std::move(callExit));

      break;

    }

    case PathDiagnosticPiece::Macro: {

      auto &Macro = cast<PathDiagnosticMacroPiece>(*Piece);

      if (ShouldFlattenMacros) {

        Macro.subPieces.flattenTo(Primary, Primary, ShouldFlattenMacros);

      } else {

        Current.push_back(Piece);

        PathPieces NewPath;

        Macro.subPieces.flattenTo(Primary, NewPath, ShouldFlattenMacros);

        // FIXME: This probably shouldn't mutate the original path piece.

        Macro.subPieces = NewPath;

      }

      break;

    }

    case PathDiagnosticPiece::Event:

    case PathDiagnosticPiece::ControlFlow:

    case PathDiagnosticPiece::Note:

    case PathDiagnosticPiece::PopUp:

      Current.push_back(Piece);

      break;

    }

  }

}

PathDiagnostic::~PathDiagnostic() = default;

PathDiagnostic::PathDiagnostic(

    StringRef CheckerName, const Decl *declWithIssue, StringRef bugtype,

    StringRef verboseDesc, StringRef shortDesc, StringRef category,

    PathDiagnosticLocation LocationToUnique, const Decl *DeclToUnique,

    std::unique_ptr<FilesToLineNumsMap> ExecutedLines)

    : CheckerName(CheckerName), DeclWithIssue(declWithIssue),

      BugType(StripTrailingDots(bugtype)),

      VerboseDesc(StripTrailingDots(verboseDesc)),

      ShortDesc(StripTrailingDots(shortDesc)),

      Category(StripTrailingDots(category)), UniqueingLoc(LocationToUnique),

      UniqueingDecl(DeclToUnique), ExecutedLines(std::move(ExecutedLines)),

      path(pathImpl) {}

void PathDiagnosticConsumer::anchor() {}

PathDiagnosticConsumer::~PathDiagnosticConsumer() {

  // Delete the contents of the FoldingSet if it isn't empty already.

  for (auto &Diag : Diags)

    delete &Diag;

}

void PathDiagnosticConsumer::HandlePathDiagnostic(

    std::unique_ptr<PathDiagnostic> D) {

  if (!D || D->path.empty())

    return;

  // We need to flatten the locations (convert Stmt* to locations) because

  // the referenced statements may be freed by the time the diagnostics

  // are emitted.

  D->flattenLocations();

  // If the PathDiagnosticConsumer does not support diagnostics that

  // cross file boundaries, prune out such diagnostics now.

  if (!supportsCrossFileDiagnostics()) {

    // Verify that the entire path is from the same FileID.

    FileID FID;

    const SourceManager &SMgr = D->path.front()->getLocation().getManager();

    SmallVector<const PathPieces *, 5> WorkList;

    WorkList.push_back(&D->path);

    SmallString<128> buf;

    llvm::raw_svector_ostream warning(buf);

    warning << "warning: Path diagnostic report is not generated. Current "

            << "output format does not support diagnostics that cross file "

            << "boundaries. Refer to --analyzer-output for valid output "

            << "formats\n";

    while (!WorkList.empty()) {

      const PathPieces &path = *WorkList.pop_back_val();

      for (const auto &I : path) {

        const PathDiagnosticPiece *piece = I.get();

        FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc();

        if (FID.isInvalid()) {

          FID = SMgr.getFileID(L);

        } else if (SMgr.getFileID(L) != FID) {

          llvm::errs() << warning.str();

          return;

        }

        // Check the source ranges.

        ArrayRef<SourceRange> Ranges = piece->getRanges();

        for (const auto &I : Ranges) {

          SourceLocation L = SMgr.getExpansionLoc(I.getBegin());

          if (!L.isFileID() || SMgr.getFileID(L) != FID) {

            llvm::errs() << warning.str();

            return;

          }

          L = SMgr.getExpansionLoc(I.getEnd());

          if (!L.isFileID() || SMgr.getFileID(L) != FID) {

            llvm::errs() << warning.str();

            return;

          }

        }

        if (const auto *call = dyn_cast<PathDiagnosticCallPiece>(piece))

          WorkList.push_back(&call->path);

        else if (const auto *macro = dyn_cast<PathDiagnosticMacroPiece>(piece))

          WorkList.push_back(&macro->subPieces);

      }

    }

    if (FID.isInvalid())

      return; // FIXME: Emit a warning?

  }

  // Profile the node to see if we already have something matching it

  llvm::FoldingSetNodeID profile;

  D->Profile(profile);

  void *InsertPos = nullptr;

  if (PathDiagnostic *orig = Diags.FindNodeOrInsertPos(profile, InsertPos)) {

    // Keep the PathDiagnostic with the shorter path.

    // Note, the enclosing routine is called in deterministic order, so the

    // results will be consistent between runs (no reason to break ties if the

    // size is the same).

    const unsigned orig_size = orig->full_size();

    const unsigned new_size = D->full_size();

    if (orig_size <= new_size)

      return;

    assert(orig != D.get());

    Diags.RemoveNode(orig);

    delete orig;

  }

  Diags.InsertNode(D.release());

}

static Optional<bool> comparePath(const PathPieces &X, const PathPieces &Y);

static Optional<bool>

compareControlFlow(const PathDiagnosticControlFlowPiece &X,

                   const PathDiagnosticControlFlowPiece &Y) {

  FullSourceLoc XSL = X.getStartLocation().asLocation();

  FullSourceLoc YSL = Y.getStartLocation().asLocation();

  if (XSL != YSL)

    return XSL.isBeforeInTranslationUnitThan(YSL);

  FullSourceLoc XEL = X.getEndLocation().asLocation();

  FullSourceLoc YEL = Y.getEndLocation().asLocation();

  if (XEL != YEL)

    return XEL.isBeforeInTranslationUnitThan(YEL);

  return None;

}

static Optional<bool> compareMacro(const PathDiagnosticMacroPiece &X,

                                   const PathDiagnosticMacroPiece &Y) {

  return comparePath(X.subPieces, Y.subPieces);

}

static Optional<bool> compareCall(const PathDiagnosticCallPiece &X,

                                  const PathDiagnosticCallPiece &Y) {

  FullSourceLoc X_CEL = X.callEnter.asLocation();

  FullSourceLoc Y_CEL = Y.callEnter.asLocation();

  if (X_CEL != Y_CEL)

    return X_CEL.isBeforeInTranslationUnitThan(Y_CEL);

  FullSourceLoc X_CEWL = X.callEnterWithin.asLocation();

  FullSourceLoc Y_CEWL = Y.callEnterWithin.asLocation();

  if (X_CEWL != Y_CEWL)

    return X_CEWL.isBeforeInTranslationUnitThan(Y_CEWL);

  FullSourceLoc X_CRL = X.callReturn.asLocation();

  FullSourceLoc Y_CRL = Y.callReturn.asLocation();

  if (X_CRL != Y_CRL)

    return X_CRL.isBeforeInTranslationUnitThan(Y_CRL);

  return comparePath(X.path, Y.path);

}

static Optional<bool> comparePiece(const PathDiagnosticPiece &X,

                                   const PathDiagnosticPiece &Y) {

  if (X.getKind() != Y.getKind())

    return X.getKind() < Y.getKind();

  FullSourceLoc XL = X.getLocation().asLocation();

  FullSourceLoc YL = Y.getLocation().asLocation();

  if (XL != YL)

    return XL.isBeforeInTranslationUnitThan(YL);

  if (X.getString() != Y.getString())

    return X.getString() < Y.getString();

  if (X.getRanges().size() != Y.getRanges().size())

    return X.getRanges().size() < Y.getRanges().size();

  const SourceManager &SM = XL.getManager();

  for (unsigned i = 0, n = X.getRanges().size(); i < n; 
++i0
) {

    SourceRange XR = X.getRanges()[i];

    SourceRange YR = Y.getRanges()[i];

    if (XR != YR) {

      if (XR.getBegin() != YR.getBegin())

        return SM.isBeforeInTranslationUnit(XR.getBegin(), YR.getBegin());

      return SM.isBeforeInTranslationUnit(XR.getEnd(), YR.getEnd());

    }

  }

  switch (X.getKind()) {

    case PathDiagnosticPiece::ControlFlow:

      return compareControlFlow(cast<PathDiagnosticControlFlowPiece>(X),

                                cast<PathDiagnosticControlFlowPiece>(Y));

    case PathDiagnosticPiece::Macro:

      return compareMacro(cast<PathDiagnosticMacroPiece>(X),

                          cast<PathDiagnosticMacroPiece>(Y));

    case PathDiagnosticPiece::Call:

      return compareCall(cast<PathDiagnosticCallPiece>(X),

                         cast<PathDiagnosticCallPiece>(Y));

    case PathDiagnosticPiece::Event:

    case PathDiagnosticPiece::Note:

    case PathDiagnosticPiece::PopUp:

      return None;

  }

  llvm_unreachable("all cases handled");

}

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();

  for ( ; X_I != X_end && Y_I != Y_end; 
++X_I, ++Y_I0
) {

    Optional<bool> b = comparePiece(**X_I, **Y_I);

    if (b)

      return b.value();

  }

  return None;

}

static bool compareCrossTUSourceLocs(FullSourceLoc XL, FullSourceLoc YL) {

  if (XL.isInvalid() && 
YL.isValid()29
)

    return true;

  if (XL.isValid() && YL.isInvalid())

    return false;

  std::pair<FileID, unsigned> XOffs = XL.getDecomposedLoc();

  std::pair<FileID, unsigned> YOffs = YL.getDecomposedLoc();

  const SourceManager &SM = XL.getManager();

  std::pair<bool, bool> InSameTU = SM.isInTheSameTranslationUnit(XOffs, YOffs);

  if (InSameTU.first)

    return XL.isBeforeInTranslationUnitThan(YL);

  const FileEntry *XFE = SM.getFileEntryForID(XL.getSpellingLoc().getFileID());

  const FileEntry *YFE = SM.getFileEntryForID(YL.getSpellingLoc().getFileID());

  if (!XFE || !YFE)

    return XFE && !YFE;

  int NameCmp = XFE->getName().compare(YFE->getName());

  if (NameCmp != 0)

    return NameCmp == -1;

  // Last resort: Compare raw file IDs that are possibly expansions.

  return XL.getFileID() < YL.getFileID();

}

static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y) {

  FullSourceLoc XL = X.getLocation().asLocation();

  FullSourceLoc YL = Y.getLocation().asLocation();

  if (XL != YL)

    return compareCrossTUSourceLocs(XL, YL);

  FullSourceLoc XUL = X.getUniqueingLoc().asLocation();

  FullSourceLoc YUL = Y.getUniqueingLoc().asLocation();

  if (XUL != YUL)

    return compareCrossTUSourceLocs(XUL, YUL);

  if (X.getBugType() != Y.getBugType())

    return X.getBugType() < Y.getBugType();

  if (X.getCategory() != Y.getCategory())

    return X.getCategory() < Y.getCategory();

  if (X.getVerboseDescription() != Y.getVerboseDescription())

    return X.getVerboseDescription() < Y.getVerboseDescription();

  if (X.getShortDescription() != Y.getShortDescription())

    return X.getShortDescription() < Y.getShortDescription();

  auto CompareDecls = [&XL](const Decl *D1, const Decl *D2) -> Optional<bool> {

    if (D1 == D2)

      return None;

    if (!D1)

      return true;

    if (!D2)

      return false;

    SourceLocation D1L = D1->getLocation();

    SourceLocation D2L = D2->getLocation();

    if (D1L != D2L) {

      const SourceManager &SM = XL.getManager();

      return compareCrossTUSourceLocs(FullSourceLoc(D1L, SM),

                                      FullSourceLoc(D2L, SM));

    }

    return None;

  };

  if (auto Result = CompareDecls(X.getDeclWithIssue(), Y.getDeclWithIssue()))

    return *Result;

  if (XUL.isValid()) {

    if (auto Result = CompareDecls(X.getUniqueingDecl(), Y.getUniqueingDecl()))

      return *Result;

  }

  PathDiagnostic::meta_iterator XI = X.meta_begin(), XE = X.meta_end();

  PathDiagnostic::meta_iterator YI = Y.meta_begin(), YE = Y.meta_end();

  if (XE - XI != YE - YI)

    return (XE - XI) < (YE - YI);

  for ( ; XI != XE ; 
++XI, ++YI0
) {

    if (*XI != *YI)

      return (*XI) < (*YI);

  }

  Optional<bool> b = comparePath(X.path, Y.path);

  assert(b);

  return b.value();

}

void PathDiagnosticConsumer::FlushDiagnostics(

                                     PathDiagnosticConsumer::FilesMade *Files) {

  if (flushed)

    return;

  flushed = true;

  std::vector<const PathDiagnostic *> BatchDiags;

  for (const auto &D : Diags)

    BatchDiags.push_back(&D);

  // Sort the diagnostics so that they are always emitted in a deterministic

  // order.

  int (*Comp)(const PathDiagnostic *const *, const PathDiagnostic *const *) =

      [](const PathDiagnostic *const *X, const PathDiagnostic *const *Y) {

        assert(*X != *Y && "PathDiagnostics not uniqued!");

        if (compare(**X, **Y))

          return -1;

        assert(compare(**Y, **X) && "Not a total order!");

        return 1;

      };

  array_pod_sort(BatchDiags.begin(), BatchDiags.end(), Comp);

  FlushDiagnosticsImpl(BatchDiags, Files);

  // Delete the flushed diagnostics.

  for (const auto D : BatchDiags)

    delete D;

  // Clear out the FoldingSet.

  Diags.clear();

}

PathDiagnosticConsumer::FilesMade::~FilesMade() {

  for (auto It = Set.begin(); It != Set.end();)

    (It++)->~PDFileEntry();

}

void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD,

                                                      StringRef ConsumerName,

                                                      StringRef FileName) {

  llvm::FoldingSetNodeID NodeID;

  NodeID.Add(PD);

  void *InsertPos;

  PDFileEntry *Entry = Set.FindNodeOrInsertPos(NodeID, InsertPos);

  if (!Entry) {

    Entry = Alloc.Allocate<PDFileEntry>();

    Entry = new (Entry) PDFileEntry(NodeID);

    Set.InsertNode(Entry, InsertPos);

  }

  // Allocate persistent storage for the file name.

  char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1);

  memcpy(FileName_cstr, FileName.data(), FileName.size());

  Entry->files.push_back(std::make_pair(ConsumerName,

                                        StringRef(FileName_cstr,

                                                  FileName.size())));

}

PathDiagnosticConsumer::PDFileEntry::ConsumerFiles *

PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) {

  llvm::FoldingSetNodeID NodeID;

  NodeID.Add(PD);

  void *InsertPos;

  PDFileEntry *Entry = Set.FindNodeOrInsertPos(NodeID, InsertPos);

  if (!Entry)

    return nullptr;

  return &Entry->files;

}

//===----------------------------------------------------------------------===//

// PathDiagnosticLocation methods.

//===----------------------------------------------------------------------===//

SourceLocation PathDiagnosticLocation::getValidSourceLocation(

    const Stmt *S, LocationOrAnalysisDeclContext LAC, bool UseEndOfStatement) {

  SourceLocation L = UseEndOfStatement ? 
S->getEndLoc()5
 : 
S->getBeginLoc()120k
;

  assert(!LAC.isNull() &&

         "A valid LocationContext or AnalysisDeclContext should be passed to "

         "PathDiagnosticLocation upon creation.");

  // S might be a temporary statement that does not have a location in the

  // source code, so find an enclosing statement and use its location.

  if (!L.isValid()) {

    AnalysisDeclContext *ADC;

    if (LAC.is<const LocationContext*>())

      ADC = LAC.get<const LocationContext*>()->getAnalysisDeclContext();

    else

      ADC = LAC.get<AnalysisDeclContext*>();

    ParentMap &PM = ADC->getParentMap();

    const Stmt *Parent = S;

    do {

      Parent = PM.getParent(Parent);

      // In rare cases, we have implicit top-level expressions,

      // such as arguments for implicit member initializers.

      // In this case, fall back to the start of the body (even if we were

      // asked for the statement end location).

      if (!Parent) {

        const Stmt *Body = ADC->getBody();

        if (Body)

          L = Body->getBeginLoc();

        else

          L = ADC->getDecl()->getEndLoc();

        break;

      }

      L = UseEndOfStatement ? 
Parent->getEndLoc()0
 : Parent->getBeginLoc();

    } while (!L.isValid());

  }

  // FIXME: Ironically, this assert actually fails in some cases.

  //assert(L.isValid());

  return L;

}

static PathDiagnosticLocation

getLocationForCaller(const StackFrameContext *SFC,

                     const LocationContext *CallerCtx,

                     const SourceManager &SM) {

  const CFGBlock &Block = *SFC->getCallSiteBlock();

  CFGElement Source = Block[SFC->getIndex()];

  switch (Source.getKind()) {

  case CFGElement::Statement:

  case CFGElement::Constructor:

  case CFGElement::CXXRecordTypedCall:

    return PathDiagnosticLocation(Source.castAs<CFGStmt>().getStmt(),

                                  SM, CallerCtx);

  case CFGElement::Initializer: {

    const CFGInitializer &Init = Source.castAs<CFGInitializer>();

    return PathDiagnosticLocation(Init.getInitializer()->getInit(),

                                  SM, CallerCtx);

  }

  case CFGElement::AutomaticObjectDtor: {

    const CFGAutomaticObjDtor &Dtor = Source.castAs<CFGAutomaticObjDtor>();

    return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(),

                                             SM, CallerCtx);

  }

  case CFGElement::DeleteDtor: {

    const CFGDeleteDtor &Dtor = Source.castAs<CFGDeleteDtor>();

    return PathDiagnosticLocation(Dtor.getDeleteExpr(), SM, CallerCtx);

  }

  case CFGElement::BaseDtor:

  case CFGElement::MemberDtor: {

    const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();

    if (const Stmt *CallerBody = CallerInfo->getBody())

      return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);

    return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);

  }

  case CFGElement::NewAllocator: {

    const CFGNewAllocator &Alloc = Source.castAs<CFGNewAllocator>();

    return PathDiagnosticLocation(Alloc.getAllocatorExpr(), SM, CallerCtx);

  }

  case CFGElement::TemporaryDtor: {

    // Temporary destructors are for temporaries. They die immediately at around

    // the location of CXXBindTemporaryExpr. If they are lifetime-extended,

    // they'd be dealt with via an AutomaticObjectDtor instead.

    const auto &Dtor = Source.castAs<CFGTemporaryDtor>();

    return PathDiagnosticLocation::createEnd(Dtor.getBindTemporaryExpr(), SM,

                                             CallerCtx);

  }

  case CFGElement::ScopeBegin:

  case CFGElement::ScopeEnd:

    llvm_unreachable("not yet implemented!");

  case CFGElement::LifetimeEnds:

  case CFGElement::LoopExit:

    llvm_unreachable("CFGElement kind should not be on callsite!");

  }

  llvm_unreachable("Unknown CFGElement kind");

}

PathDiagnosticLocation

PathDiagnosticLocation::createBegin(const Decl *D,

                                    const SourceManager &SM) {

  return PathDiagnosticLocation(D->getBeginLoc(), SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createBegin(const Stmt *S,

                                    const SourceManager &SM,

                                    LocationOrAnalysisDeclContext LAC) {

  return PathDiagnosticLocation(getValidSourceLocation(S, LAC),

                                SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createEnd(const Stmt *S,

                                  const SourceManager &SM,

                                  LocationOrAnalysisDeclContext LAC) {

  if (const auto *CS = dyn_cast<CompoundStmt>(S))

    return createEndBrace(CS, SM);

  return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),

                                SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,

                                          const SourceManager &SM) {

  return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createConditionalColonLoc(

                                            const ConditionalOperator *CO,

                                            const SourceManager &SM) {

  return PathDiagnosticLocation(CO->getColonLoc(), SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,

                                        const SourceManager &SM) {

  assert(ME->getMemberLoc().isValid() || ME->getBeginLoc().isValid());

  // In some cases, getMemberLoc isn't valid -- in this case we'll return with

  // some other related valid SourceLocation.

  if (ME->getMemberLoc().isValid())

    return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);

  return PathDiagnosticLocation(ME->getBeginLoc(), SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,

                                         const SourceManager &SM) {

  SourceLocation L = CS->getLBracLoc();

  return PathDiagnosticLocation(L, SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,

                                       const SourceManager &SM) {

  SourceLocation L = CS->getRBracLoc();

  return PathDiagnosticLocation(L, SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,

                                        const SourceManager &SM) {

  // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.

  if (const auto *CS = dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))

    if (!CS->body_empty()) {

      SourceLocation Loc = (*CS->body_begin())->getBeginLoc();

      return PathDiagnosticLocation(Loc, SM, SingleLocK);

    }

  return PathDiagnosticLocation();

}

PathDiagnosticLocation

PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,

                                      const SourceManager &SM) {

  SourceLocation L = LC->getDecl()->getBodyRBrace();

  return PathDiagnosticLocation(L, SM, SingleLocK);

}

PathDiagnosticLocation

PathDiagnosticLocation::create(const ProgramPoint& P,

                               const SourceManager &SMng) {

  const Stmt* S = nullptr;

  if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {

    const CFGBlock *BSrc = BE->getSrc();

    if (BSrc->getTerminator().isVirtualBaseBranch()) {

      // TODO: VirtualBaseBranches should also appear for destructors.

      // In this case we should put the diagnostic at the end of decl.

      return PathDiagnosticLocation::createBegin(

          P.getLocationContext()->getDecl(), SMng);

    } else {

      S = BSrc->getTerminatorCondition();

      if (!S) {

        // If the BlockEdge has no terminator condition statement but its

        // source is the entry of the CFG (e.g. a checker crated the branch at

        // the beginning of a function), use the function's declaration instead.

        assert(BSrc == &BSrc->getParent()->getEntry() && "CFGBlock has no "

               "TerminatorCondition and is not the enrty block of the CFG");

        return PathDiagnosticLocation::createBegin(

            P.getLocationContext()->getDecl(), SMng);

      }

    }

  } else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {

    S = SP->getStmt();

    if (P.getAs<PostStmtPurgeDeadSymbols>())

      return PathDiagnosticLocation::createEnd(S, SMng, P.getLocationContext());

  } else 
if (Optional<PostInitializer> 103
PIP103
 = P.getAs<PostInitializer>()) {

    return PathDiagnosticLocation(PIP->getInitializer()->getSourceLocation(),

                                  SMng);

  } else if (Optional<PreImplicitCall> PIC = P.getAs<PreImplicitCall>()) {

    return PathDiagnosticLocation(PIC->getLocation(), SMng);

  } else if (Optional<PostImplicitCall> PIE = P.getAs<PostImplicitCall>()) {

    return PathDiagnosticLocation(PIE->getLocation(), SMng);

  } else if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {

    return getLocationForCaller(CE->getCalleeContext(),

                                CE->getLocationContext(),

                                SMng);

  } else if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>()) {

    return getLocationForCaller(CEE->getCalleeContext(),

                                CEE->getLocationContext(),

                                SMng);

  } else if (auto CEB = P.getAs<CallExitBegin>()) {

    if (const ReturnStmt *RS = CEB->getReturnStmt())

      return PathDiagnosticLocation::createBegin(RS, SMng,

                                                 CEB->getLocationContext());

    return PathDiagnosticLocation(

        CEB->getLocationContext()->getDecl()->getSourceRange().getEnd(), SMng);

  } else 
if (Optional<BlockEntrance> 6
BE6
 = P.getAs<BlockEntrance>()) {

    if (Optional<CFGElement> BlockFront = BE->getFirstElement()) {

      if (auto StmtElt = BlockFront->getAs<CFGStmt>()) {

        return PathDiagnosticLocation(StmtElt->getStmt()->getBeginLoc(), SMng);

      } else 
if (auto 1
NewAllocElt1
 = BlockFront->getAs<CFGNewAllocator>()) {

        return PathDiagnosticLocation(

            NewAllocElt->getAllocatorExpr()->getBeginLoc(), SMng);

      }

      llvm_unreachable("Unexpected CFG element at front of block");

    }

    return PathDiagnosticLocation(

        BE->getBlock()->getTerminatorStmt()->getBeginLoc(), SMng);

  } else 
if (Optional<FunctionExitPoint> 1
FE1
 = P.getAs<FunctionExitPoint>()) {

    return PathDiagnosticLocation(FE->getStmt(), SMng,

                                  FE->getLocationContext());

  } else {

    llvm_unreachable("Unexpected ProgramPoint");

  }

  return PathDiagnosticLocation(S, SMng, P.getLocationContext());

}

PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(

                                           const PathDiagnosticLocation &PDL) {

  FullSourceLoc L = PDL.asLocation();

  return PathDiagnosticLocation(L, L.getManager(), SingleLocK);

}

FullSourceLoc

  PathDiagnosticLocation::genLocation(SourceLocation L,

                                      LocationOrAnalysisDeclContext LAC) const {

  assert(isValid());

  // Note that we want a 'switch' here so that the compiler can warn us in

  // case we add more cases.

  switch (K) {

    case SingleLocK:

    case RangeK:

      break;

    case StmtK:

      // Defensive checking.

      if (!S)

        break;

      return FullSourceLoc(getValidSourceLocation(S, LAC),

                           const_cast<SourceManager&>(*SM));

    case DeclK:

      // Defensive checking.

      if (!D)

        break;

      return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));

  }

  return FullSourceLoc(L, const_cast<SourceManager&>(*SM));

}

PathDiagnosticRange

  PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {

  assert(isValid());

  // Note that we want a 'switch' here so that the compiler can warn us in

  // case we add more cases.

  switch (K) {

    case SingleLocK:

      return PathDiagnosticRange(SourceRange(Loc,Loc), true);

    case RangeK:

      break;

    case StmtK: {

      const Stmt *S = asStmt();

      switch (S->getStmtClass()) {

        default:

          break;

        case Stmt::DeclStmtClass: {

          const auto *DS = cast<DeclStmt>(S);

          if (DS->isSingleDecl()) {

            // Should always be the case, but we'll be defensive.

            return SourceRange(DS->getBeginLoc(),

                               DS->getSingleDecl()->getLocation());

          }

          break;

        }

          // FIXME: Provide better range information for different

          //  terminators.

        case Stmt::IfStmtClass:

        case Stmt::WhileStmtClass:

        case Stmt::DoStmtClass:

        case Stmt::ForStmtClass:

        case Stmt::ChooseExprClass:

        case Stmt::IndirectGotoStmtClass:

        case Stmt::SwitchStmtClass:

        case Stmt::BinaryConditionalOperatorClass:

        case Stmt::ConditionalOperatorClass:

        case Stmt::ObjCForCollectionStmtClass: {

          SourceLocation L = getValidSourceLocation(S, LAC);

          return SourceRange(L, L);

        }

      }

      SourceRange R = S->getSourceRange();

      if (R.isValid())

        return R;

      break;

    }

    case DeclK:

      if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))

        return MD->getSourceRange();

      if (const auto *FD = dyn_cast<FunctionDecl>(D)) {

        if (Stmt *Body = FD->getBody())

          return Body->getSourceRange();

      }

      else {

        SourceLocation L = D->getLocation();

        return PathDiagnosticRange(SourceRange(L, L), true);

      }

  }

  return SourceRange(Loc, Loc);

}

void PathDiagnosticLocation::flatten() {

  if (K == StmtK) {

    K = RangeK;

    S = nullptr;

    D = nullptr;

  }

  else if (K == DeclK) {

    K = SingleLocK;

    S = nullptr;

    D = nullptr;

  }

}

//===----------------------------------------------------------------------===//

// Manipulation of PathDiagnosticCallPieces.

//===----------------------------------------------------------------------===//

std::shared_ptr<PathDiagnosticCallPiece>

PathDiagnosticCallPiece::construct(const CallExitEnd &CE,

                                   const SourceManager &SM) {

  const Decl *caller = CE.getLocationContext()->getDecl();

  PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),

                                                    CE.getLocationContext(),

                                                    SM);

  return std::shared_ptr<PathDiagnosticCallPiece>(

      new PathDiagnosticCallPiece(caller, pos));

}

PathDiagnosticCallPiece *

PathDiagnosticCallPiece::construct(PathPieces &path,

                                   const Decl *caller) {

  std::shared_ptr<PathDiagnosticCallPiece> C(

      new PathDiagnosticCallPiece(path, caller));

  path.clear();

  auto *R = C.get();

  path.push_front(std::move(C));

  return R;

}

void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,

                                        const SourceManager &SM) {

  const StackFrameContext *CalleeCtx = CE.getCalleeContext();

  Callee = CalleeCtx->getDecl();

  callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);

  callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);

  // Autosynthesized property accessors are special because we'd never

  // pop back up to non-autosynthesized code until we leave them.

  // This is not generally true for autosynthesized callees, which may call

  // non-autosynthesized callbacks.

  // Unless set here, the IsCalleeAnAutosynthesizedPropertyAccessor flag

  // defaults to false.

  if (const auto *MD = dyn_cast<ObjCMethodDecl>(Callee))

    IsCalleeAnAutosynthesizedPropertyAccessor = (

        MD->isPropertyAccessor() &&

        
CalleeCtx->getAnalysisDeclContext()->isBodyAutosynthesized()3
);

}

static void describeTemplateParameters(raw_ostream &Out,

                                       const ArrayRef<TemplateArgument> TAList,

                                       const LangOptions &LO,

                                       StringRef Prefix = StringRef(),

                                       StringRef Postfix = StringRef());

static void describeTemplateParameter(raw_ostream &Out,

                                      const TemplateArgument &TArg,

                                      const LangOptions &LO) {

  if (TArg.getKind() == TemplateArgument::ArgKind::Pack) {

    describeTemplateParameters(Out, TArg.getPackAsArray(), LO);

  } else {

    TArg.print(PrintingPolicy(LO), Out, /*IncludeType*/ true);

  }

}

static void describeTemplateParameters(raw_ostream &Out,

                                       const ArrayRef<TemplateArgument> TAList,

                                       const LangOptions &LO,

                                       StringRef Prefix, StringRef Postfix) {

  if (TAList.empty())

    return;

  Out << Prefix;

  for (int I = 0, Last = TAList.size() - 1; I != Last; 
++I64
) {

    describeTemplateParameter(Out, TAList[I], LO);

    Out << ", ";

  }

  describeTemplateParameter(Out, TAList[TAList.size() - 1], LO);

  Out << Postfix;

}

static void describeClass(raw_ostream &Out, const CXXRecordDecl *D,

                          StringRef Prefix = StringRef()) {

  if (!D->getIdentifier())

    return;

  Out << Prefix << '\'' << *D;

  if (const auto T = dyn_cast<ClassTemplateSpecializationDecl>(D))

    describeTemplateParameters(Out, T->getTemplateArgs().asArray(),

                               D->getLangOpts(), "<", ">");

  Out << '\'';

}

static bool describeCodeDecl(raw_ostream &Out, const Decl *D,

                             bool ExtendedDescription,

                             StringRef Prefix = StringRef()) {

  if (!D)

    return false;

  if (isa<BlockDecl>(D)) {

    if (ExtendedDescription)

      Out << Prefix << "anonymous block";

    return ExtendedDescription;

  }

  if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {

    Out << Prefix;

    if (ExtendedDescription && 
!MD->isUserProvided()256
) {

      if (MD->isExplicitlyDefaulted())

        Out << "defaulted ";

      else

        Out << "implicit ";

    }

    if (const auto *CD = dyn_cast<CXXConstructorDecl>(MD)) {

      if (CD->isDefaultConstructor())

        Out << "default ";

      else if (CD->isCopyConstructor())

        Out << "copy ";

      else if (CD->isMoveConstructor())

        Out << "move ";

      Out << "constructor";

      describeClass(Out, MD->getParent(), " for ");

    } else if (isa<CXXDestructorDecl>(MD)) {

      if (!MD->isUserProvided()) {

        Out << "destructor";

        describeClass(Out, MD->getParent(), " for ");

      } else {

        // Use ~Foo for explicitly-written destructors.

        Out << "'" << *MD << "'";

      }

    } else if (MD->isCopyAssignmentOperator()) {

        Out << "copy assignment operator";

        describeClass(Out, MD->getParent(), " for ");

    } else if (MD->isMoveAssignmentOperator()) {

        Out << "move assignment operator";

        describeClass(Out, MD->getParent(), " for ");

    } else {

      if (MD->getParent()->getIdentifier())

        Out << "'" << *MD->getParent() << "::" << *MD << "'";

      else

        Out << "'" << *MD << "'";

    }

    return true;

  }

  Out << Prefix << '\'' << cast<NamedDecl>(*D);

  // Adding template parameters.

  if (const auto FD = dyn_cast<FunctionDecl>(D))

    if (const TemplateArgumentList *TAList =

                                    FD->getTemplateSpecializationArgs())

      describeTemplateParameters(Out, TAList->asArray(), FD->getLangOpts(), "<",

                                 ">");

  Out << '\'';

  return true;

}