contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp

   1 //===--- PathDiagnostic.cpp - Path-Specific Diagnostic Handling -*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines the PathDiagnostic-related interfaces.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  16 #include "clang/Basic/SourceManager.h"
  17 #include "clang/AST/Expr.h"
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/DeclObjC.h"
  21 #include "clang/AST/ParentMap.h"
  22 #include "clang/AST/StmtCXX.h"
  23 #include "llvm/ADT/SmallString.h"
  24 #include "llvm/ADT/StringExtras.h"
  25
  26 using namespace clang;
  27 using namespace ento;
  28
  29 bool PathDiagnosticMacroPiece::containsEvent() const {
  30   for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
  31        I!=E; ++I) {
  32     if (isa<PathDiagnosticEventPiece>(*I))
  33       return true;
  34     if (PathDiagnosticMacroPiece *MP = dyn_cast<PathDiagnosticMacroPiece>(*I))
  35       if (MP->containsEvent())
  36         return true;
  37   }
  38   return false;
  39 }
  40
  41 static StringRef StripTrailingDots(StringRef s) {
  42   for (StringRef::size_type i = s.size(); i != 0; --i)
  43     if (s[i - 1] != '.')
  44       return s.substr(0, i);
  45   return "";
  46 }
  47
  48 PathDiagnosticPiece::PathDiagnosticPiece(StringRef s,
  49                                          Kind k, DisplayHint hint)
  50   : str(StripTrailingDots(s)), kind(k), Hint(hint) {}
  51
  52 PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint)
  53   : kind(k), Hint(hint) {}
  54
  55 PathDiagnosticPiece::~PathDiagnosticPiece() {}
  56 PathDiagnosticEventPiece::~PathDiagnosticEventPiece() {}
  57 PathDiagnosticCallPiece::~PathDiagnosticCallPiece() {}
  58 PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() {}
  59 PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() {}
  60
  61
  62 PathPieces::~PathPieces() {}
  63
  64 void PathPieces::flattenTo(PathPieces &Primary, PathPieces &Current,
  65                            bool ShouldFlattenMacros) const {
  66   for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
  67     PathDiagnosticPiece *Piece = I->getPtr();
  68
  69     switch (Piece->getKind()) {
  70     case PathDiagnosticPiece::Call: {
  71       PathDiagnosticCallPiece *Call = cast<PathDiagnosticCallPiece>(Piece);
  72       IntrusiveRefCntPtr<PathDiagnosticEventPiece> CallEnter =
  73         Call->getCallEnterEvent();
  74       if (CallEnter)
  75         Current.push_back(CallEnter);
  76       Call->path.flattenTo(Primary, Primary, ShouldFlattenMacros);
  77       IntrusiveRefCntPtr<PathDiagnosticEventPiece> callExit =
  78         Call->getCallExitEvent();
  79       if (callExit)
  80         Current.push_back(callExit);
  81       break;
  82     }
  83     case PathDiagnosticPiece::Macro: {
  84       PathDiagnosticMacroPiece *Macro = cast<PathDiagnosticMacroPiece>(Piece);
  85       if (ShouldFlattenMacros) {
  86         Macro->subPieces.flattenTo(Primary, Primary, ShouldFlattenMacros);
  87       } else {
  88         Current.push_back(Piece);
  89         PathPieces NewPath;
  90         Macro->subPieces.flattenTo(Primary, NewPath, ShouldFlattenMacros);
  91         // FIXME: This probably shouldn't mutate the original path piece.
  92         Macro->subPieces = NewPath;
  93       }
  94       break;
  95     }
  96     case PathDiagnosticPiece::Event:
  97     case PathDiagnosticPiece::ControlFlow:
  98       Current.push_back(Piece);
  99       break;
 100     }
 101   }
 102 }
 103
 104
 105 PathDiagnostic::~PathDiagnostic() {}
 106
 107 PathDiagnostic::PathDiagnostic(const Decl *declWithIssue,
 108                                StringRef bugtype, StringRef verboseDesc,
 109                                StringRef shortDesc, StringRef category)
 110   : DeclWithIssue(declWithIssue),
 111     BugType(StripTrailingDots(bugtype)),
 112     VerboseDesc(StripTrailingDots(verboseDesc)),
 113     ShortDesc(StripTrailingDots(shortDesc)),
 114     Category(StripTrailingDots(category)),
 115     path(pathImpl) {}
 116
 117 void PathDiagnosticConsumer::anchor() { }
 118
 119 PathDiagnosticConsumer::~PathDiagnosticConsumer() {
 120   // Delete the contents of the FoldingSet if it isn't empty already.
 121   for (llvm::FoldingSet<PathDiagnostic>::iterator it =
 122        Diags.begin(), et = Diags.end() ; it != et ; ++it) {
 123     delete &*it;
 124   }
 125 }
 126
 127 void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) {
 128   llvm::OwningPtr<PathDiagnostic> OwningD(D);
 129
 130   if (!D || D->path.empty())
 131     return;
 132
 133   // We need to flatten the locations (convert Stmt* to locations) because
 134   // the referenced statements may be freed by the time the diagnostics
 135   // are emitted.
 136   D->flattenLocations();
 137
 138   // If the PathDiagnosticConsumer does not support diagnostics that
 139   // cross file boundaries, prune out such diagnostics now.
 140   if (!supportsCrossFileDiagnostics()) {
 141     // Verify that the entire path is from the same FileID.
 142     FileID FID;
 143     const SourceManager &SMgr = (*D->path.begin())->getLocation().getManager();
 144     llvm::SmallVector<const PathPieces *, 5> WorkList;
 145     WorkList.push_back(&D->path);
 146
 147     while (!WorkList.empty()) {
 148       const PathPieces &path = *WorkList.back();
 149       WorkList.pop_back();
 150
 151       for (PathPieces::const_iterator I = path.begin(), E = path.end();
 152            I != E; ++I) {
 153         const PathDiagnosticPiece *piece = I->getPtr();
 154         FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc();
 155
 156         if (FID.isInvalid()) {
 157           FID = SMgr.getFileID(L);
 158         } else if (SMgr.getFileID(L) != FID)
 159           return; // FIXME: Emit a warning?
 160
 161         // Check the source ranges.
 162         ArrayRef<SourceRange> Ranges = piece->getRanges();
 163         for (ArrayRef<SourceRange>::iterator I = Ranges.begin(),
 164                                              E = Ranges.end(); I != E; ++I) {
 165           SourceLocation L = SMgr.getExpansionLoc(I->getBegin());
 166           if (!L.isFileID() || SMgr.getFileID(L) != FID)
 167             return; // FIXME: Emit a warning?
 168           L = SMgr.getExpansionLoc(I->getEnd());
 169           if (!L.isFileID() || SMgr.getFileID(L) != FID)
 170             return; // FIXME: Emit a warning?
 171         }
 172
 173         if (const PathDiagnosticCallPiece *call =
 174             dyn_cast<PathDiagnosticCallPiece>(piece)) {
 175           WorkList.push_back(&call->path);
 176         }
 177         else if (const PathDiagnosticMacroPiece *macro =
 178                  dyn_cast<PathDiagnosticMacroPiece>(piece)) {
 179           WorkList.push_back(&macro->subPieces);
 180         }
 181       }
 182     }
 183
 184     if (FID.isInvalid())
 185       return; // FIXME: Emit a warning?
 186   }
 187
 188   // Profile the node to see if we already have something matching it
 189   llvm::FoldingSetNodeID profile;
 190   D->Profile(profile);
 191   void *InsertPos = 0;
 192
 193   if (PathDiagnostic *orig = Diags.FindNodeOrInsertPos(profile, InsertPos)) {
 194     // Keep the PathDiagnostic with the shorter path.
 195     // Note, the enclosing routine is called in deterministic order, so the
 196     // results will be consistent between runs (no reason to break ties if the
 197     // size is the same).
 198     const unsigned orig_size = orig->full_size();
 199     const unsigned new_size = D->full_size();
 200     if (orig_size <= new_size)
 201       return;
 202
 203     assert(orig != D);
 204     Diags.RemoveNode(orig);
 205     delete orig;
 206   }
 207
 208   Diags.InsertNode(OwningD.take());
 209 }
 210
 211 static llvm::Optional<bool> comparePath(const PathPieces &X,
 212                                         const PathPieces &Y);
 213 static llvm::Optional<bool>
 214 compareControlFlow(const PathDiagnosticControlFlowPiece &X,
 215                    const PathDiagnosticControlFlowPiece &Y) {
 216   FullSourceLoc XSL = X.getStartLocation().asLocation();
 217   FullSourceLoc YSL = Y.getStartLocation().asLocation();
 218   if (XSL != YSL)
 219     return XSL.isBeforeInTranslationUnitThan(YSL);
 220   FullSourceLoc XEL = X.getEndLocation().asLocation();
 221   FullSourceLoc YEL = Y.getEndLocation().asLocation();
 222   if (XEL != YEL)
 223     return XEL.isBeforeInTranslationUnitThan(YEL);
 224   return llvm::Optional<bool>();
 225 }
 226
 227 static llvm::Optional<bool>
 228 compareMacro(const PathDiagnosticMacroPiece &X,
 229              const PathDiagnosticMacroPiece &Y) {
 230   return comparePath(X.subPieces, Y.subPieces);
 231 }
 232
 233 static llvm::Optional<bool>
 234 compareCall(const PathDiagnosticCallPiece &X,
 235             const PathDiagnosticCallPiece &Y) {
 236   FullSourceLoc X_CEL = X.callEnter.asLocation();
 237   FullSourceLoc Y_CEL = Y.callEnter.asLocation();
 238   if (X_CEL != Y_CEL)
 239     return X_CEL.isBeforeInTranslationUnitThan(Y_CEL);
 240   FullSourceLoc X_CEWL = X.callEnterWithin.asLocation();
 241   FullSourceLoc Y_CEWL = Y.callEnterWithin.asLocation();
 242   if (X_CEWL != Y_CEWL)
 243     return X_CEWL.isBeforeInTranslationUnitThan(Y_CEWL);
 244   FullSourceLoc X_CRL = X.callReturn.asLocation();
 245   FullSourceLoc Y_CRL = Y.callReturn.asLocation();
 246   if (X_CRL != Y_CRL)
 247     return X_CRL.isBeforeInTranslationUnitThan(Y_CRL);
 248   return comparePath(X.path, Y.path);
 249 }
 250
 251 static llvm::Optional<bool> comparePiece(const PathDiagnosticPiece &X,
 252                                          const PathDiagnosticPiece &Y) {
 253   if (X.getKind() != Y.getKind())
 254     return X.getKind() < Y.getKind();
 255
 256   FullSourceLoc XL = X.getLocation().asLocation();
 257   FullSourceLoc YL = Y.getLocation().asLocation();
 258   if (XL != YL)
 259     return XL.isBeforeInTranslationUnitThan(YL);
 260
 261   if (X.getString() != Y.getString())
 262     return X.getString() < Y.getString();
 263
 264   if (X.getRanges().size() != Y.getRanges().size())
 265     return X.getRanges().size() < Y.getRanges().size();
 266
 267   const SourceManager &SM = XL.getManager();
 268
 269   for (unsigned i = 0, n = X.getRanges().size(); i < n; ++i) {
 270     SourceRange XR = X.getRanges()[i];
 271     SourceRange YR = Y.getRanges()[i];
 272     if (XR != YR) {
 273       if (XR.getBegin() != YR.getBegin())
 274         return SM.isBeforeInTranslationUnit(XR.getBegin(), YR.getBegin());
 275       return SM.isBeforeInTranslationUnit(XR.getEnd(), YR.getEnd());
 276     }
 277   }
 278
 279   switch (X.getKind()) {
 280     case clang::ento::PathDiagnosticPiece::ControlFlow:
 281       return compareControlFlow(cast<PathDiagnosticControlFlowPiece>(X),
 282                                 cast<PathDiagnosticControlFlowPiece>(Y));
 283     case clang::ento::PathDiagnosticPiece::Event:
 284       return llvm::Optional<bool>();
 285     case clang::ento::PathDiagnosticPiece::Macro:
 286       return compareMacro(cast<PathDiagnosticMacroPiece>(X),
 287                           cast<PathDiagnosticMacroPiece>(Y));
 288     case clang::ento::PathDiagnosticPiece::Call:
 289       return compareCall(cast<PathDiagnosticCallPiece>(X),
 290                          cast<PathDiagnosticCallPiece>(Y));
 291   }
 292   llvm_unreachable("all cases handled");
 293 }
 294
 295 static llvm::Optional<bool> comparePath(const PathPieces &X,
 296                                         const PathPieces &Y) {
 297   if (X.size() != Y.size())
 298     return X.size() < Y.size();
 299   for (unsigned i = 0, n = X.size(); i != n; ++i) {
 300     llvm::Optional<bool> b = comparePiece(*X[i], *Y[i]);
 301     if (b.hasValue())
 302       return b.getValue();
 303   }
 304   return llvm::Optional<bool>();
 305 }
 306
 307 static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y) {
 308   FullSourceLoc XL = X.getLocation().asLocation();
 309   FullSourceLoc YL = Y.getLocation().asLocation();
 310   if (XL != YL)
 311     return XL.isBeforeInTranslationUnitThan(YL);
 312   if (X.getBugType() != Y.getBugType())
 313     return X.getBugType() < Y.getBugType();
 314   if (X.getCategory() != Y.getCategory())
 315     return X.getCategory() < Y.getCategory();
 316   if (X.getVerboseDescription() != Y.getVerboseDescription())
 317     return X.getVerboseDescription() < Y.getVerboseDescription();
 318   if (X.getShortDescription() != Y.getShortDescription())
 319     return X.getShortDescription() < Y.getShortDescription();
 320   if (X.getDeclWithIssue() != Y.getDeclWithIssue()) {
 321     const Decl *XD = X.getDeclWithIssue();
 322     if (!XD)
 323       return true;
 324     const Decl *YD = Y.getDeclWithIssue();
 325     if (!YD)
 326       return false;
 327     SourceLocation XDL = XD->getLocation();
 328     SourceLocation YDL = YD->getLocation();
 329     if (XDL != YDL) {
 330       const SourceManager &SM = XL.getManager();
 331       return SM.isBeforeInTranslationUnit(XDL, YDL);
 332     }
 333   }
 334   PathDiagnostic::meta_iterator XI = X.meta_begin(), XE = X.meta_end();
 335   PathDiagnostic::meta_iterator YI = Y.meta_begin(), YE = Y.meta_end();
 336   if (XE - XI != YE - YI)
 337     return (XE - XI) < (YE - YI);
 338   for ( ; XI != XE ; ++XI, ++YI) {
 339     if (*XI != *YI)
 340       return (*XI) < (*YI);
 341   }
 342   llvm::Optional<bool> b = comparePath(X.path, Y.path);
 343   assert(b.hasValue());
 344   return b.getValue();
 345 }
 346
 347 namespace {
 348 struct CompareDiagnostics {
 349   // Compare if 'X' is "<" than 'Y'.
 350   bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const {
 351     if (X == Y)
 352       return false;
 353     return compare(*X, *Y);
 354   }
 355 };
 356 }
 357
 358 void PathDiagnosticConsumer::FlushDiagnostics(
 359                                      PathDiagnosticConsumer::FilesMade *Files) {
 360   if (flushed)
 361     return;
 362
 363   flushed = true;
 364
 365   std::vector<const PathDiagnostic *> BatchDiags;
 366   for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(),
 367        et = Diags.end(); it != et; ++it) {
 368     const PathDiagnostic *D = &*it;
 369     BatchDiags.push_back(D);
 370   }
 371
 372   // Sort the diagnostics so that they are always emitted in a deterministic
 373   // order.
 374   if (!BatchDiags.empty())
 375     std::sort(BatchDiags.begin(), BatchDiags.end(), CompareDiagnostics());
 376
 377   FlushDiagnosticsImpl(BatchDiags, Files);
 378
 379   // Delete the flushed diagnostics.
 380   for (std::vector<const PathDiagnostic *>::iterator it = BatchDiags.begin(),
 381        et = BatchDiags.end(); it != et; ++it) {
 382     const PathDiagnostic *D = *it;
 383     delete D;
 384   }
 385
 386   // Clear out the FoldingSet.
 387   Diags.clear();
 388 }
 389
 390 void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD,
 391                                                       StringRef ConsumerName,
 392                                                       StringRef FileName) {
 393   llvm::FoldingSetNodeID NodeID;
 394   NodeID.Add(PD);
 395   void *InsertPos;
 396   PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
 397   if (!Entry) {
 398     Entry = Alloc.Allocate<PDFileEntry>();
 399     Entry = new (Entry) PDFileEntry(NodeID);
 400     InsertNode(Entry, InsertPos);
 401   }
 402
 403   // Allocate persistent storage for the file name.
 404   char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1);
 405   memcpy(FileName_cstr, FileName.data(), FileName.size());
 406
 407   Entry->files.push_back(std::make_pair(ConsumerName,
 408                                         StringRef(FileName_cstr,
 409                                                   FileName.size())));
 410 }
 411
 412 PathDiagnosticConsumer::PDFileEntry::ConsumerFiles *
 413 PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) {
 414   llvm::FoldingSetNodeID NodeID;
 415   NodeID.Add(PD);
 416   void *InsertPos;
 417   PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
 418   if (!Entry)
 419     return 0;
 420   return &Entry->files;
 421 }
 422
 423 //===----------------------------------------------------------------------===//
 424 // PathDiagnosticLocation methods.
 425 //===----------------------------------------------------------------------===//
 426
 427 static SourceLocation getValidSourceLocation(const Stmt* S,
 428                                              LocationOrAnalysisDeclContext LAC,
 429                                              bool UseEnd = false) {
 430   SourceLocation L = UseEnd ? S->getLocEnd() : S->getLocStart();
 431   assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should "
 432                           "be passed to PathDiagnosticLocation upon creation.");
 433
 434   // S might be a temporary statement that does not have a location in the
 435   // source code, so find an enclosing statement and use its location.
 436   if (!L.isValid()) {
 437
 438     AnalysisDeclContext *ADC;
 439     if (LAC.is<const LocationContext*>())
 440       ADC = LAC.get<const LocationContext*>()->getAnalysisDeclContext();
 441     else
 442       ADC = LAC.get<AnalysisDeclContext*>();
 443
 444     ParentMap &PM = ADC->getParentMap();
 445
 446     const Stmt *Parent = S;
 447     do {
 448       Parent = PM.getParent(Parent);
 449
 450       // In rare cases, we have implicit top-level expressions,
 451       // such as arguments for implicit member initializers.
 452       // In this case, fall back to the start of the body (even if we were
 453       // asked for the statement end location).
 454       if (!Parent) {
 455         const Stmt *Body = ADC->getBody();
 456         if (Body)
 457           L = Body->getLocStart();
 458         else
 459           L = ADC->getDecl()->getLocEnd();
 460         break;
 461       }
 462
 463       L = UseEnd ? Parent->getLocEnd() : Parent->getLocStart();
 464     } while (!L.isValid());
 465   }
 466
 467   return L;
 468 }
 469
 470 static PathDiagnosticLocation
 471 getLocationForCaller(const StackFrameContext *SFC,
 472                      const LocationContext *CallerCtx,
 473                      const SourceManager &SM) {
 474   const CFGBlock &Block = *SFC->getCallSiteBlock();
 475   CFGElement Source = Block[SFC->getIndex()];
 476
 477   switch (Source.getKind()) {
 478   case CFGElement::Invalid:
 479     llvm_unreachable("Invalid CFGElement");
 480   case CFGElement::Statement:
 481     return PathDiagnosticLocation(cast<CFGStmt>(Source).getStmt(),
 482                                   SM, CallerCtx);
 483   case CFGElement::Initializer: {
 484     const CFGInitializer &Init = cast<CFGInitializer>(Source);
 485     return PathDiagnosticLocation(Init.getInitializer()->getInit(),
 486                                   SM, CallerCtx);
 487   }
 488   case CFGElement::AutomaticObjectDtor: {
 489     const CFGAutomaticObjDtor &Dtor = cast<CFGAutomaticObjDtor>(Source);
 490     return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(),
 491                                              SM, CallerCtx);
 492   }
 493   case CFGElement::BaseDtor:
 494   case CFGElement::MemberDtor: {
 495     const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
 496     if (const Stmt *CallerBody = CallerInfo->getBody())
 497       return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
 498     return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
 499   }
 500   case CFGElement::TemporaryDtor:
 501     llvm_unreachable("not yet implemented!");
 502   }
 503
 504   llvm_unreachable("Unknown CFGElement kind");
 505 }
 506
 507
 508 PathDiagnosticLocation
 509   PathDiagnosticLocation::createBegin(const Decl *D,
 510                                       const SourceManager &SM) {
 511   return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
 512 }
 513
 514 PathDiagnosticLocation
 515   PathDiagnosticLocation::createBegin(const Stmt *S,
 516                                       const SourceManager &SM,
 517                                       LocationOrAnalysisDeclContext LAC) {
 518   return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
 519                                 SM, SingleLocK);
 520 }
 521
 522
 523 PathDiagnosticLocation
 524 PathDiagnosticLocation::createEnd(const Stmt *S,
 525                                   const SourceManager &SM,
 526                                   LocationOrAnalysisDeclContext LAC) {
 527   if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(S))
 528     return createEndBrace(CS, SM);
 529   return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),
 530                                 SM, SingleLocK);
 531 }
 532
 533 PathDiagnosticLocation
 534   PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
 535                                             const SourceManager &SM) {
 536   return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
 537 }
 538
 539 PathDiagnosticLocation
 540   PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
 541                                           const SourceManager &SM) {
 542   return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
 543 }
 544
 545 PathDiagnosticLocation
 546   PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
 547                                            const SourceManager &SM) {
 548   SourceLocation L = CS->getLBracLoc();
 549   return PathDiagnosticLocation(L, SM, SingleLocK);
 550 }
 551
 552 PathDiagnosticLocation
 553   PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
 554                                          const SourceManager &SM) {
 555   SourceLocation L = CS->getRBracLoc();
 556   return PathDiagnosticLocation(L, SM, SingleLocK);
 557 }
 558
 559 PathDiagnosticLocation
 560   PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
 561                                           const SourceManager &SM) {
 562   // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
 563   if (const CompoundStmt *CS =
 564         dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
 565     if (!CS->body_empty()) {
 566       SourceLocation Loc = (*CS->body_begin())->getLocStart();
 567       return PathDiagnosticLocation(Loc, SM, SingleLocK);
 568     }
 569
 570   return PathDiagnosticLocation();
 571 }
 572
 573 PathDiagnosticLocation
 574   PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
 575                                         const SourceManager &SM) {
 576   SourceLocation L = LC->getDecl()->getBodyRBrace();
 577   return PathDiagnosticLocation(L, SM, SingleLocK);
 578 }
 579
 580 PathDiagnosticLocation
 581   PathDiagnosticLocation::create(const ProgramPoint& P,
 582                                  const SourceManager &SMng) {
 583
 584   const Stmt* S = 0;
 585   if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
 586     const CFGBlock *BSrc = BE->getSrc();
 587     S = BSrc->getTerminatorCondition();
 588   }
 589   else if (const StmtPoint *SP = dyn_cast<StmtPoint>(&P)) {
 590     S = SP->getStmt();
 591   }
 592   else if (const PostImplicitCall *PIE = dyn_cast<PostImplicitCall>(&P)) {
 593     return PathDiagnosticLocation(PIE->getLocation(), SMng);
 594   }
 595   else if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) {
 596     return getLocationForCaller(CE->getCalleeContext(),
 597                                 CE->getLocationContext(),
 598                                 SMng);
 599   }
 600   else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&P)) {
 601     return getLocationForCaller(CEE->getCalleeContext(),
 602                                 CEE->getLocationContext(),
 603                                 SMng);
 604   }
 605   else {
 606     llvm_unreachable("Unexpected ProgramPoint");
 607   }
 608
 609   return PathDiagnosticLocation(S, SMng, P.getLocationContext());
 610 }
 611
 612 PathDiagnosticLocation
 613   PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N,
 614                                           const SourceManager &SM) {
 615   assert(N && "Cannot create a location with a null node.");
 616
 617   const ExplodedNode *NI = N;
 618   const Stmt *S = 0;
 619
 620   while (NI) {
 621     ProgramPoint P = NI->getLocation();
 622     if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P))
 623       S = PS->getStmt();
 624     else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P))
 625       S = BE->getSrc()->getTerminator();
 626     if (S)
 627       break;
 628     NI = NI->succ_empty() ? 0 : *(NI->succ_begin());
 629   }
 630
 631   if (S) {
 632     const LocationContext *LC = NI->getLocationContext();
 633     if (S->getLocStart().isValid())
 634       return PathDiagnosticLocation(S, SM, LC);
 635     return PathDiagnosticLocation(getValidSourceLocation(S, LC), SM);
 636   }
 637
 638   return createDeclEnd(N->getLocationContext(), SM);
 639 }
 640
 641 PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
 642                                            const PathDiagnosticLocation &PDL) {
 643   FullSourceLoc L = PDL.asLocation();
 644   return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
 645 }
 646
 647 FullSourceLoc
 648   PathDiagnosticLocation::genLocation(SourceLocation L,
 649                                       LocationOrAnalysisDeclContext LAC) const {
 650   assert(isValid());
 651   // Note that we want a 'switch' here so that the compiler can warn us in
 652   // case we add more cases.
 653   switch (K) {
 654     case SingleLocK:
 655     case RangeK:
 656       break;
 657     case StmtK:
 658       // Defensive checking.
 659       if (!S)
 660         break;
 661       return FullSourceLoc(getValidSourceLocation(S, LAC),
 662                            const_cast<SourceManager&>(*SM));
 663     case DeclK:
 664       // Defensive checking.
 665       if (!D)
 666         break;
 667       return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
 668   }
 669
 670   return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
 671 }
 672
 673 PathDiagnosticRange
 674   PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
 675   assert(isValid());
 676   // Note that we want a 'switch' here so that the compiler can warn us in
 677   // case we add more cases.
 678   switch (K) {
 679     case SingleLocK:
 680       return PathDiagnosticRange(SourceRange(Loc,Loc), true);
 681     case RangeK:
 682       break;
 683     case StmtK: {
 684       const Stmt *S = asStmt();
 685       switch (S->getStmtClass()) {
 686         default:
 687           break;
 688         case Stmt::DeclStmtClass: {
 689           const DeclStmt *DS = cast<DeclStmt>(S);
 690           if (DS->isSingleDecl()) {
 691             // Should always be the case, but we'll be defensive.
 692             return SourceRange(DS->getLocStart(),
 693                                DS->getSingleDecl()->getLocation());
 694           }
 695           break;
 696         }
 697           // FIXME: Provide better range information for different
 698           //  terminators.
 699         case Stmt::IfStmtClass:
 700         case Stmt::WhileStmtClass:
 701         case Stmt::DoStmtClass:
 702         case Stmt::ForStmtClass:
 703         case Stmt::ChooseExprClass:
 704         case Stmt::IndirectGotoStmtClass:
 705         case Stmt::SwitchStmtClass:
 706         case Stmt::BinaryConditionalOperatorClass:
 707         case Stmt::ConditionalOperatorClass:
 708         case Stmt::ObjCForCollectionStmtClass: {
 709           SourceLocation L = getValidSourceLocation(S, LAC);
 710           return SourceRange(L, L);
 711         }
 712       }
 713       SourceRange R = S->getSourceRange();
 714       if (R.isValid())
 715         return R;
 716       break;
 717     }
 718     case DeclK:
 719       if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
 720         return MD->getSourceRange();
 721       if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 722         if (Stmt *Body = FD->getBody())
 723           return Body->getSourceRange();
 724       }
 725       else {
 726         SourceLocation L = D->getLocation();
 727         return PathDiagnosticRange(SourceRange(L, L), true);
 728       }
 729   }
 730
 731   return SourceRange(Loc,Loc);
 732 }
 733
 734 void PathDiagnosticLocation::flatten() {
 735   if (K == StmtK) {
 736     K = RangeK;
 737     S = 0;
 738     D = 0;
 739   }
 740   else if (K == DeclK) {
 741     K = SingleLocK;
 742     S = 0;
 743     D = 0;
 744   }
 745 }
 746
 747 //===----------------------------------------------------------------------===//
 748 // Manipulation of PathDiagnosticCallPieces.
 749 //===----------------------------------------------------------------------===//
 750
 751 PathDiagnosticCallPiece *
 752 PathDiagnosticCallPiece::construct(const ExplodedNode *N,
 753                                    const CallExitEnd &CE,
 754                                    const SourceManager &SM) {
 755   const Decl *caller = CE.getLocationContext()->getDecl();
 756   PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),
 757                                                     CE.getLocationContext(),
 758                                                     SM);
 759   return new PathDiagnosticCallPiece(caller, pos);
 760 }
 761
 762 PathDiagnosticCallPiece *
 763 PathDiagnosticCallPiece::construct(PathPieces &path,
 764                                    const Decl *caller) {
 765   PathDiagnosticCallPiece *C = new PathDiagnosticCallPiece(path, caller);
 766   path.clear();
 767   path.push_front(C);
 768   return C;
 769 }
 770
 771 void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,
 772                                         const SourceManager &SM) {
 773   const StackFrameContext *CalleeCtx = CE.getCalleeContext();
 774   Callee = CalleeCtx->getDecl();
 775
 776   callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);
 777   callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);
 778 }
 779
 780 IntrusiveRefCntPtr<PathDiagnosticEventPiece>
 781 PathDiagnosticCallPiece::getCallEnterEvent() const {
 782   if (!Callee)
 783     return 0;
 784   SmallString<256> buf;
 785   llvm::raw_svector_ostream Out(buf);
 786   if (isa<BlockDecl>(Callee))
 787     Out << "Calling anonymous block";
 788   else if (const NamedDecl *ND = dyn_cast<NamedDecl>(Callee))
 789     Out << "Calling '" << *ND << "'";
 790   StringRef msg = Out.str();
 791   if (msg.empty())
 792     return 0;
 793   return new PathDiagnosticEventPiece(callEnter, msg);
 794 }
 795
 796 IntrusiveRefCntPtr<PathDiagnosticEventPiece>
 797 PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
 798   SmallString<256> buf;
 799   llvm::raw_svector_ostream Out(buf);
 800   if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Caller))
 801     Out << "Entered call from '" << *ND << "'";
 802   else
 803     Out << "Entered call";
 804   StringRef msg = Out.str();
 805   if (msg.empty())
 806     return 0;
 807   return new PathDiagnosticEventPiece(callEnterWithin, msg);
 808 }
 809
 810 IntrusiveRefCntPtr<PathDiagnosticEventPiece>
 811 PathDiagnosticCallPiece::getCallExitEvent() const {
 812   if (NoExit)
 813     return 0;
 814   SmallString<256> buf;
 815   llvm::raw_svector_ostream Out(buf);
 816   if (!CallStackMessage.empty())
 817     Out << CallStackMessage;
 818   else if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Callee))
 819     Out << "Returning from '" << *ND << "'";
 820   else
 821     Out << "Returning to caller";
 822   return new PathDiagnosticEventPiece(callReturn, Out.str());
 823 }
 824
 825 static void compute_path_size(const PathPieces &pieces, unsigned &size) {
 826   for (PathPieces::const_iterator it = pieces.begin(),
 827                                   et = pieces.end(); it != et; ++it) {
 828     const PathDiagnosticPiece *piece = it->getPtr();
 829     if (const PathDiagnosticCallPiece *cp =
 830         dyn_cast<PathDiagnosticCallPiece>(piece)) {
 831       compute_path_size(cp->path, size);
 832     }
 833     else
 834       ++size;
 835   }
 836 }
 837
 838 unsigned PathDiagnostic::full_size() {
 839   unsigned size = 0;
 840   compute_path_size(path, size);
 841   return size;
 842 }
 843
 844 //===----------------------------------------------------------------------===//
 845 // FoldingSet profiling methods.
 846 //===----------------------------------------------------------------------===//
 847
 848 void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
 849   ID.AddInteger(Range.getBegin().getRawEncoding());
 850   ID.AddInteger(Range.getEnd().getRawEncoding());
 851   ID.AddInteger(Loc.getRawEncoding());
 852   return;
 853 }
 854
 855 void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 856   ID.AddInteger((unsigned) getKind());
 857   ID.AddString(str);
 858   // FIXME: Add profiling support for code hints.
 859   ID.AddInteger((unsigned) getDisplayHint());
 860   ArrayRef<SourceRange> Ranges = getRanges();
 861   for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
 862                                         I != E; ++I) {
 863     ID.AddInteger(I->getBegin().getRawEncoding());
 864     ID.AddInteger(I->getEnd().getRawEncoding());
 865   }
 866 }
 867
 868 void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 869   PathDiagnosticPiece::Profile(ID);
 870   for (PathPieces::const_iterator it = path.begin(),
 871        et = path.end(); it != et; ++it) {
 872     ID.Add(**it);
 873   }
 874 }
 875
 876 void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 877   PathDiagnosticPiece::Profile(ID);
 878   ID.Add(Pos);
 879 }
 880
 881 void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 882   PathDiagnosticPiece::Profile(ID);
 883   for (const_iterator I = begin(), E = end(); I != E; ++I)
 884     ID.Add(*I);
 885 }
 886
 887 void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
 888   PathDiagnosticSpotPiece::Profile(ID);
 889   for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
 890        I != E; ++I)
 891     ID.Add(**I);
 892 }
 893
 894 void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
 895   ID.Add(getLocation());
 896   ID.AddString(BugType);
 897   ID.AddString(VerboseDesc);
 898   ID.AddString(Category);
 899 }
 900
 901 void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
 902   Profile(ID);
 903   for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
 904     ID.Add(**I);
 905   for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
 906     ID.AddString(*I);
 907 }
 908
 909 StackHintGenerator::~StackHintGenerator() {}
 910
 911 std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
 912   ProgramPoint P = N->getLocation();
 913   const CallExitEnd *CExit = dyn_cast<CallExitEnd>(&P);
 914   assert(CExit && "Stack Hints should be constructed at CallExitEnd points.");
 915
 916   // FIXME: Use CallEvent to abstract this over all calls.
 917   const Stmt *CallSite = CExit->getCalleeContext()->getCallSite();
 918   const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite);
 919   if (!CE)
 920     return "";
 921
 922   if (!N)
 923     return getMessageForSymbolNotFound();
 924
 925   // Check if one of the parameters are set to the interesting symbol.
 926   ProgramStateRef State = N->getState();
 927   const LocationContext *LCtx = N->getLocationContext();
 928   unsigned ArgIndex = 0;
 929   for (CallExpr::const_arg_iterator I = CE->arg_begin(),
 930                                     E = CE->arg_end(); I != E; ++I, ++ArgIndex){
 931     SVal SV = State->getSVal(*I, LCtx);
 932
 933     // Check if the variable corresponding to the symbol is passed by value.
 934     SymbolRef AS = SV.getAsLocSymbol();
 935     if (AS == Sym) {
 936       return getMessageForArg(*I, ArgIndex);
 937     }
 938
 939     // Check if the parameter is a pointer to the symbol.
 940     if (const loc::MemRegionVal *Reg = dyn_cast<loc::MemRegionVal>(&SV)) {
 941       SVal PSV = State->getSVal(Reg->getRegion());
 942       SymbolRef AS = PSV.getAsLocSymbol();
 943       if (AS == Sym) {
 944         return getMessageForArg(*I, ArgIndex);
 945       }
 946     }
 947   }
 948
 949   // Check if we are returning the interesting symbol.
 950   SVal SV = State->getSVal(CE, LCtx);
 951   SymbolRef RetSym = SV.getAsLocSymbol();
 952   if (RetSym == Sym) {
 953     return getMessageForReturn(CE);
 954   }
 955
 956   return getMessageForSymbolNotFound();
 957 }
 958
 959 std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
 960                                                           unsigned ArgIndex) {
 961   // Printed parameters start at 1, not 0.
 962   ++ArgIndex;
 963
 964   SmallString<200> buf;
 965   llvm::raw_svector_ostream os(buf);
 966
 967   os << Msg << " via " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
 968      << " parameter";
 969
 970   return os.str();
 971 }