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