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