Home | History | Annotate | Download | only in Core 
      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   for (unsigned i = 0, n = X.size(); i != n; ++i) {
    301     Optional<bool> b = comparePiece(*X[i], *Y[i]);
    302     if (b.hasValue())
    303       return b.getValue();
    304   }
    305   return None;
    306 }
    307 
    308 static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y) {
    309   FullSourceLoc XL = X.getLocation().asLocation();
    310   FullSourceLoc YL = Y.getLocation().asLocation();
    311   if (XL != YL)
    312     return XL.isBeforeInTranslationUnitThan(YL);
    313   if (X.getBugType() != Y.getBugType())
    314     return X.getBugType() < Y.getBugType();
    315   if (X.getCategory() != Y.getCategory())
    316     return X.getCategory() < Y.getCategory();
    317   if (X.getVerboseDescription() != Y.getVerboseDescription())
    318     return X.getVerboseDescription() < Y.getVerboseDescription();
    319   if (X.getShortDescription() != Y.getShortDescription())
    320     return X.getShortDescription() < Y.getShortDescription();
    321   if (X.getDeclWithIssue() != Y.getDeclWithIssue()) {
    322     const Decl *XD = X.getDeclWithIssue();
    323     if (!XD)
    324       return true;
    325     const Decl *YD = Y.getDeclWithIssue();
    326     if (!YD)
    327       return false;
    328     SourceLocation XDL = XD->getLocation();
    329     SourceLocation YDL = YD->getLocation();
    330     if (XDL != YDL) {
    331       const SourceManager &SM = XL.getManager();
    332       return SM.isBeforeInTranslationUnit(XDL, YDL);
    333     }
    334   }
    335   PathDiagnostic::meta_iterator XI = X.meta_begin(), XE = X.meta_end();
    336   PathDiagnostic::meta_iterator YI = Y.meta_begin(), YE = Y.meta_end();
    337   if (XE - XI != YE - YI)
    338     return (XE - XI) < (YE - YI);
    339   for ( ; XI != XE ; ++XI, ++YI) {
    340     if (*XI != *YI)
    341       return (*XI) < (*YI);
    342   }
    343   Optional<bool> b = comparePath(X.path, Y.path);
    344   assert(b.hasValue());
    345   return b.getValue();
    346 }
    347 
    348 namespace {
    349 struct CompareDiagnostics {
    350   // Compare if 'X' is "<" than 'Y'.
    351   bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const {
    352     if (X == Y)
    353       return false;
    354     return compare(*X, *Y);
    355   }
    356 };
    357 }
    358 
    359 void PathDiagnosticConsumer::FlushDiagnostics(
    360                                      PathDiagnosticConsumer::FilesMade *Files) {
    361   if (flushed)
    362     return;
    363 
    364   flushed = true;
    365 
    366   std::vector<const PathDiagnostic *> BatchDiags;
    367   for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(),
    368        et = Diags.end(); it != et; ++it) {
    369     const PathDiagnostic *D = &*it;
    370     BatchDiags.push_back(D);
    371   }
    372 
    373   // Sort the diagnostics so that they are always emitted in a deterministic
    374   // order.
    375   if (!BatchDiags.empty())
    376     std::sort(BatchDiags.begin(), BatchDiags.end(), CompareDiagnostics());
    377 
    378   FlushDiagnosticsImpl(BatchDiags, Files);
    379 
    380   // Delete the flushed diagnostics.
    381   for (std::vector<const PathDiagnostic *>::iterator it = BatchDiags.begin(),
    382        et = BatchDiags.end(); it != et; ++it) {
    383     const PathDiagnostic *D = *it;
    384     delete D;
    385   }
    386 
    387   // Clear out the FoldingSet.
    388   Diags.clear();
    389 }
    390 
    391 void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD,
    392                                                       StringRef ConsumerName,
    393                                                       StringRef FileName) {
    394   llvm::FoldingSetNodeID NodeID;
    395   NodeID.Add(PD);
    396   void *InsertPos;
    397   PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
    398   if (!Entry) {
    399     Entry = Alloc.Allocate<PDFileEntry>();
    400     Entry = new (Entry) PDFileEntry(NodeID);
    401     InsertNode(Entry, InsertPos);
    402   }
    403 
    404   // Allocate persistent storage for the file name.
    405   char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1);
    406   memcpy(FileName_cstr, FileName.data(), FileName.size());
    407 
    408   Entry->files.push_back(std::make_pair(ConsumerName,
    409                                         StringRef(FileName_cstr,
    410                                                   FileName.size())));
    411 }
    412 
    413 PathDiagnosticConsumer::PDFileEntry::ConsumerFiles *
    414 PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) {
    415   llvm::FoldingSetNodeID NodeID;
    416   NodeID.Add(PD);
    417   void *InsertPos;
    418   PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
    419   if (!Entry)
    420     return 0;
    421   return &Entry->files;
    422 }
    423 
    424 //===----------------------------------------------------------------------===//
    425 // PathDiagnosticLocation methods.
    426 //===----------------------------------------------------------------------===//
    427 
    428 static SourceLocation getValidSourceLocation(const Stmt* S,
    429                                              LocationOrAnalysisDeclContext LAC,
    430                                              bool UseEnd = false) {
    431   SourceLocation L = UseEnd ? S->getLocEnd() : S->getLocStart();
    432   assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should "
    433                           "be passed to PathDiagnosticLocation upon creation.");
    434 
    435   // S might be a temporary statement that does not have a location in the
    436   // source code, so find an enclosing statement and use its location.
    437   if (!L.isValid()) {
    438 
    439     AnalysisDeclContext *ADC;
    440     if (LAC.is<const LocationContext*>())
    441       ADC = LAC.get<const LocationContext*>()->getAnalysisDeclContext();
    442     else
    443       ADC = LAC.get<AnalysisDeclContext*>();
    444 
    445     ParentMap &PM = ADC->getParentMap();
    446 
    447     const Stmt *Parent = S;
    448     do {
    449       Parent = PM.getParent(Parent);
    450 
    451       // In rare cases, we have implicit top-level expressions,
    452       // such as arguments for implicit member initializers.
    453       // In this case, fall back to the start of the body (even if we were
    454       // asked for the statement end location).
    455       if (!Parent) {
    456         const Stmt *Body = ADC->getBody();
    457         if (Body)
    458           L = Body->getLocStart();
    459         else
    460           L = ADC->getDecl()->getLocEnd();
    461         break;
    462       }
    463 
    464       L = UseEnd ? Parent->getLocEnd() : Parent->getLocStart();
    465     } while (!L.isValid());
    466   }
    467 
    468   return L;
    469 }
    470 
    471 static PathDiagnosticLocation
    472 getLocationForCaller(const StackFrameContext *SFC,
    473                      const LocationContext *CallerCtx,
    474                      const SourceManager &SM) {
    475   const CFGBlock &Block = *SFC->getCallSiteBlock();
    476   CFGElement Source = Block[SFC->getIndex()];
    477 
    478   switch (Source.getKind()) {
    479   case CFGElement::Statement:
    480     return PathDiagnosticLocation(Source.castAs<CFGStmt>().getStmt(),
    481                                   SM, CallerCtx);
    482   case CFGElement::Initializer: {
    483     const CFGInitializer &Init = Source.castAs<CFGInitializer>();
    484     return PathDiagnosticLocation(Init.getInitializer()->getInit(),
    485                                   SM, CallerCtx);
    486   }
    487   case CFGElement::AutomaticObjectDtor: {
    488     const CFGAutomaticObjDtor &Dtor = Source.castAs<CFGAutomaticObjDtor>();
    489     return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(),
    490                                              SM, CallerCtx);
    491   }
    492   case CFGElement::BaseDtor:
    493   case CFGElement::MemberDtor: {
    494     const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
    495     if (const Stmt *CallerBody = CallerInfo->getBody())
    496       return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
    497     return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
    498   }
    499   case CFGElement::TemporaryDtor:
    500     llvm_unreachable("not yet implemented!");
    501   }
    502 
    503   llvm_unreachable("Unknown CFGElement kind");
    504 }
    505 
    506 
    507 PathDiagnosticLocation
    508   PathDiagnosticLocation::createBegin(const Decl *D,
    509                                       const SourceManager &SM) {
    510   return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
    511 }
    512 
    513 PathDiagnosticLocation
    514   PathDiagnosticLocation::createBegin(const Stmt *S,
    515                                       const SourceManager &SM,
    516                                       LocationOrAnalysisDeclContext LAC) {
    517   return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
    518                                 SM, SingleLocK);
    519 }
    520 
    521 
    522 PathDiagnosticLocation
    523 PathDiagnosticLocation::createEnd(const Stmt *S,
    524                                   const SourceManager &SM,
    525                                   LocationOrAnalysisDeclContext LAC) {
    526   if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(S))
    527     return createEndBrace(CS, SM);
    528   return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),
    529                                 SM, SingleLocK);
    530 }
    531 
    532 PathDiagnosticLocation
    533   PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
    534                                             const SourceManager &SM) {
    535   return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
    536 }
    537 
    538 PathDiagnosticLocation
    539   PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
    540                                           const SourceManager &SM) {
    541   return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
    542 }
    543 
    544 PathDiagnosticLocation
    545   PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
    546                                            const SourceManager &SM) {
    547   SourceLocation L = CS->getLBracLoc();
    548   return PathDiagnosticLocation(L, SM, SingleLocK);
    549 }
    550 
    551 PathDiagnosticLocation
    552   PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
    553                                          const SourceManager &SM) {
    554   SourceLocation L = CS->getRBracLoc();
    555   return PathDiagnosticLocation(L, SM, SingleLocK);
    556 }
    557 
    558 PathDiagnosticLocation
    559   PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
    560                                           const SourceManager &SM) {
    561   // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
    562   if (const CompoundStmt *CS =
    563         dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
    564     if (!CS->body_empty()) {
    565       SourceLocation Loc = (*CS->body_begin())->getLocStart();
    566       return PathDiagnosticLocation(Loc, SM, SingleLocK);
    567     }
    568 
    569   return PathDiagnosticLocation();
    570 }
    571 
    572 PathDiagnosticLocation
    573   PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
    574                                         const SourceManager &SM) {
    575   SourceLocation L = LC->getDecl()->getBodyRBrace();
    576   return PathDiagnosticLocation(L, SM, SingleLocK);
    577 }
    578 
    579 PathDiagnosticLocation
    580   PathDiagnosticLocation::create(const ProgramPoint& P,
    581                                  const SourceManager &SMng) {
    582 
    583   const Stmt* S = 0;
    584   if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
    585     const CFGBlock *BSrc = BE->getSrc();
    586     S = BSrc->getTerminatorCondition();
    587   } else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {
    588     S = SP->getStmt();
    589     if (P.getAs<PostStmtPurgeDeadSymbols>())
    590       return PathDiagnosticLocation::createEnd(S, SMng, P.getLocationContext());
    591   } else if (Optional<PostImplicitCall> PIE = P.getAs<PostImplicitCall>()) {
    592     return PathDiagnosticLocation(PIE->getLocation(), SMng);
    593   } else if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
    594     return getLocationForCaller(CE->getCalleeContext(),
    595                                 CE->getLocationContext(),
    596                                 SMng);
    597   } else if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>()) {
    598     return getLocationForCaller(CEE->getCalleeContext(),
    599                                 CEE->getLocationContext(),
    600                                 SMng);
    601   } else {
    602     llvm_unreachable("Unexpected ProgramPoint");
    603   }
    604 
    605   return PathDiagnosticLocation(S, SMng, P.getLocationContext());
    606 }
    607 
    608 PathDiagnosticLocation
    609   PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N,
    610                                           const SourceManager &SM) {
    611   assert(N && "Cannot create a location with a null node.");
    612 
    613   const ExplodedNode *NI = N;
    614   const Stmt *S = 0;
    615 
    616   while (NI) {
    617     ProgramPoint P = NI->getLocation();
    618     if (Optional<StmtPoint> PS = P.getAs<StmtPoint>()) {
    619       S = PS->getStmt();
    620       if (P.getAs<PostStmtPurgeDeadSymbols>())
    621         return PathDiagnosticLocation::createEnd(S, SM,
    622                                                  NI->getLocationContext());
    623       break;
    624     } else if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
    625       S = BE->getSrc()->getTerminator();
    626       break;
    627     }
    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 static inline void describeClass(raw_ostream &Out, const CXXRecordDecl *D,
    781                                  StringRef Prefix = StringRef()) {
    782   if (!D->getIdentifier())
    783     return;
    784   Out << Prefix << '\'' << *D << '\'';
    785 }
    786 
    787 static bool describeCodeDecl(raw_ostream &Out, const Decl *D,
    788                              bool ExtendedDescription,
    789                              StringRef Prefix = StringRef()) {
    790   if (!D)
    791     return false;
    792 
    793   if (isa<BlockDecl>(D)) {
    794     if (ExtendedDescription)
    795       Out << Prefix << "anonymous block";
    796     return ExtendedDescription;
    797   }
    798 
    799   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
    800     Out << Prefix;
    801     if (ExtendedDescription && !MD->isUserProvided()) {
    802       if (MD->isExplicitlyDefaulted())
    803         Out << "defaulted ";
    804       else
    805         Out << "implicit ";
    806     }
    807 
    808     if (const CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(MD)) {
    809       if (CD->isDefaultConstructor())
    810         Out << "default ";
    811       else if (CD->isCopyConstructor())
    812         Out << "copy ";
    813       else if (CD->isMoveConstructor())
    814         Out << "move ";
    815 
    816       Out << "constructor";
    817       describeClass(Out, MD->getParent(), " for ");
    818 
    819     } else if (isa<CXXDestructorDecl>(MD)) {
    820       if (!MD->isUserProvided()) {
    821         Out << "destructor";
    822         describeClass(Out, MD->getParent(), " for ");
    823       } else {
    824         // Use ~Foo for explicitly-written destructors.
    825         Out << "'" << *MD << "'";
    826       }
    827 
    828     } else if (MD->isCopyAssignmentOperator()) {
    829         Out << "copy assignment operator";
    830         describeClass(Out, MD->getParent(), " for ");
    831 
    832     } else if (MD->isMoveAssignmentOperator()) {
    833         Out << "move assignment operator";
    834         describeClass(Out, MD->getParent(), " for ");
    835 
    836     } else {
    837       if (MD->getParent()->getIdentifier())
    838         Out << "'" << *MD->getParent() << "::" << *MD << "'";
    839       else
    840         Out << "'" << *MD << "'";
    841     }
    842 
    843     return true;
    844   }
    845 
    846   Out << Prefix << '\'' << cast<NamedDecl>(*D) << '\'';
    847   return true;
    848 }
    849 
    850 IntrusiveRefCntPtr<PathDiagnosticEventPiece>
    851 PathDiagnosticCallPiece::getCallEnterEvent() const {
    852   if (!Callee)
    853     return 0;
    854 
    855   SmallString<256> buf;
    856   llvm::raw_svector_ostream Out(buf);
    857 
    858   Out << "Calling ";
    859   describeCodeDecl(Out, Callee, /*ExtendedDescription=*/true);
    860 
    861   assert(callEnter.asLocation().isValid());
    862   return new PathDiagnosticEventPiece(callEnter, Out.str());
    863 }
    864 
    865 IntrusiveRefCntPtr<PathDiagnosticEventPiece>
    866 PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
    867   if (!callEnterWithin.asLocation().isValid())
    868     return 0;
    869   if (Callee->isImplicit())
    870     return 0;
    871   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Callee))
    872     if (MD->isDefaulted())
    873       return 0;
    874 
    875   SmallString<256> buf;
    876   llvm::raw_svector_ostream Out(buf);
    877 
    878   Out << "Entered call";
    879   describeCodeDecl(Out, Caller, /*ExtendedDescription=*/false, " from ");
    880 
    881   return new PathDiagnosticEventPiece(callEnterWithin, Out.str());
    882 }
    883 
    884 IntrusiveRefCntPtr<PathDiagnosticEventPiece>
    885 PathDiagnosticCallPiece::getCallExitEvent() const {
    886   if (NoExit)
    887     return 0;
    888 
    889   SmallString<256> buf;
    890   llvm::raw_svector_ostream Out(buf);
    891 
    892   if (!CallStackMessage.empty()) {
    893     Out << CallStackMessage;
    894   } else {
    895     bool DidDescribe = describeCodeDecl(Out, Callee,
    896                                         /*ExtendedDescription=*/false,
    897                                         "Returning from ");
    898     if (!DidDescribe)
    899       Out << "Returning to caller";
    900   }
    901 
    902   assert(callReturn.asLocation().isValid());
    903   return new PathDiagnosticEventPiece(callReturn, Out.str());
    904 }
    905 
    906 static void compute_path_size(const PathPieces &pieces, unsigned &size) {
    907   for (PathPieces::const_iterator it = pieces.begin(),
    908                                   et = pieces.end(); it != et; ++it) {
    909     const PathDiagnosticPiece *piece = it->getPtr();
    910     if (const PathDiagnosticCallPiece *cp =
    911         dyn_cast<PathDiagnosticCallPiece>(piece)) {
    912       compute_path_size(cp->path, size);
    913     }
    914     else
    915       ++size;
    916   }
    917 }
    918 
    919 unsigned PathDiagnostic::full_size() {
    920   unsigned size = 0;
    921   compute_path_size(path, size);
    922   return size;
    923 }
    924 
    925 //===----------------------------------------------------------------------===//
    926 // FoldingSet profiling methods.
    927 //===----------------------------------------------------------------------===//
    928 
    929 void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
    930   ID.AddInteger(Range.getBegin().getRawEncoding());
    931   ID.AddInteger(Range.getEnd().getRawEncoding());
    932   ID.AddInteger(Loc.getRawEncoding());
    933   return;
    934 }
    935 
    936 void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
    937   ID.AddInteger((unsigned) getKind());
    938   ID.AddString(str);
    939   // FIXME: Add profiling support for code hints.
    940   ID.AddInteger((unsigned) getDisplayHint());
    941   ArrayRef<SourceRange> Ranges = getRanges();
    942   for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
    943                                         I != E; ++I) {
    944     ID.AddInteger(I->getBegin().getRawEncoding());
    945     ID.AddInteger(I->getEnd().getRawEncoding());
    946   }
    947 }
    948 
    949 void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
    950   PathDiagnosticPiece::Profile(ID);
    951   for (PathPieces::const_iterator it = path.begin(),
    952        et = path.end(); it != et; ++it) {
    953     ID.Add(**it);
    954   }
    955 }
    956 
    957 void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
    958   PathDiagnosticPiece::Profile(ID);
    959   ID.Add(Pos);
    960 }
    961 
    962 void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
    963   PathDiagnosticPiece::Profile(ID);
    964   for (const_iterator I = begin(), E = end(); I != E; ++I)
    965     ID.Add(*I);
    966 }
    967 
    968 void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
    969   PathDiagnosticSpotPiece::Profile(ID);
    970   for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
    971        I != E; ++I)
    972     ID.Add(**I);
    973 }
    974 
    975 void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
    976   ID.Add(getLocation());
    977   ID.AddString(BugType);
    978   ID.AddString(VerboseDesc);
    979   ID.AddString(Category);
    980 }
    981 
    982 void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
    983   Profile(ID);
    984   for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
    985     ID.Add(**I);
    986   for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
    987     ID.AddString(*I);
    988 }
    989 
    990 StackHintGenerator::~StackHintGenerator() {}
    991 
    992 std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
    993   ProgramPoint P = N->getLocation();
    994   CallExitEnd CExit = P.castAs<CallExitEnd>();
    995 
    996   // FIXME: Use CallEvent to abstract this over all calls.
    997   const Stmt *CallSite = CExit.getCalleeContext()->getCallSite();
    998   const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite);
    999   if (!CE)
   1000     return "";
   1001 
   1002   if (!N)
   1003     return getMessageForSymbolNotFound();
   1004 
   1005   // Check if one of the parameters are set to the interesting symbol.
   1006   ProgramStateRef State = N->getState();
   1007   const LocationContext *LCtx = N->getLocationContext();
   1008   unsigned ArgIndex = 0;
   1009   for (CallExpr::const_arg_iterator I = CE->arg_begin(),
   1010                                     E = CE->arg_end(); I != E; ++I, ++ArgIndex){
   1011     SVal SV = State->getSVal(*I, LCtx);
   1012 
   1013     // Check if the variable corresponding to the symbol is passed by value.
   1014     SymbolRef AS = SV.getAsLocSymbol();
   1015     if (AS == Sym) {
   1016       return getMessageForArg(*I, ArgIndex);
   1017     }
   1018 
   1019     // Check if the parameter is a pointer to the symbol.
   1020     if (Optional<loc::MemRegionVal> Reg = SV.getAs<loc::MemRegionVal>()) {
   1021       SVal PSV = State->getSVal(Reg->getRegion());
   1022       SymbolRef AS = PSV.getAsLocSymbol();
   1023       if (AS == Sym) {
   1024         return getMessageForArg(*I, ArgIndex);
   1025       }
   1026     }
   1027   }
   1028 
   1029   // Check if we are returning the interesting symbol.
   1030   SVal SV = State->getSVal(CE, LCtx);
   1031   SymbolRef RetSym = SV.getAsLocSymbol();
   1032   if (RetSym == Sym) {
   1033     return getMessageForReturn(CE);
   1034   }
   1035 
   1036   return getMessageForSymbolNotFound();
   1037 }
   1038 
   1039 std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
   1040                                                           unsigned ArgIndex) {
   1041   // Printed parameters start at 1, not 0.
   1042   ++ArgIndex;
   1043 
   1044   SmallString<200> buf;
   1045   llvm::raw_svector_ostream os(buf);
   1046 
   1047   os << Msg << " via " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
   1048      << " parameter";
   1049 
   1050   return os.str();
   1051 }
   1052