PathDiagnostic.cpp revision 62ff52868976a8494224a2914f1869329777944c
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/DeclObjC.h" 20#include "clang/AST/ParentMap.h" 21#include "clang/AST/StmtCXX.h" 22#include "llvm/ADT/SmallString.h" 23 24using namespace clang; 25using namespace ento; 26 27bool PathDiagnosticMacroPiece::containsEvent() const { 28 for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end(); 29 I!=E; ++I) { 30 if (isa<PathDiagnosticEventPiece>(*I)) 31 return true; 32 if (PathDiagnosticMacroPiece *MP = dyn_cast<PathDiagnosticMacroPiece>(*I)) 33 if (MP->containsEvent()) 34 return true; 35 } 36 return false; 37} 38 39static StringRef StripTrailingDots(StringRef s) { 40 for (StringRef::size_type i = s.size(); i != 0; --i) 41 if (s[i - 1] != '.') 42 return s.substr(0, i); 43 return ""; 44} 45 46PathDiagnosticPiece::PathDiagnosticPiece(StringRef s, 47 Kind k, DisplayHint hint) 48 : str(StripTrailingDots(s)), kind(k), Hint(hint) {} 49 50PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint) 51 : kind(k), Hint(hint) {} 52 53PathDiagnosticPiece::~PathDiagnosticPiece() {} 54PathDiagnosticEventPiece::~PathDiagnosticEventPiece() {} 55PathDiagnosticCallPiece::~PathDiagnosticCallPiece() {} 56PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() {} 57PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() {} 58PathDiagnostic::PathDiagnostic() : path(pathImpl) {} 59PathPieces::~PathPieces() {} 60PathDiagnostic::~PathDiagnostic() {} 61 62PathDiagnostic::PathDiagnostic(StringRef bugtype, StringRef desc, 63 StringRef category) 64 : BugType(StripTrailingDots(bugtype)), 65 Desc(StripTrailingDots(desc)), 66 Category(StripTrailingDots(category)), 67 path(pathImpl) {} 68 69void PathDiagnosticConsumer::anchor() { } 70 71PathDiagnosticConsumer::~PathDiagnosticConsumer() { 72 // Delete the contents of the FoldingSet if it isn't empty already. 73 for (llvm::FoldingSet<PathDiagnostic>::iterator it = 74 Diags.begin(), et = Diags.end() ; it != et ; ++it) { 75 delete &*it; 76 } 77} 78 79void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) { 80 llvm::OwningPtr<PathDiagnostic> OwningD(D); 81 82 if (!D || D->path.empty()) 83 return; 84 85 // We need to flatten the locations (convert Stmt* to locations) because 86 // the referenced statements may be freed by the time the diagnostics 87 // are emitted. 88 D->flattenLocations(); 89 90 // If the PathDiagnosticConsumer does not support diagnostics that 91 // cross file boundaries, prune out such diagnostics now. 92 if (!supportsCrossFileDiagnostics()) { 93 // Verify that the entire path is from the same FileID. 94 FileID FID; 95 const SourceManager &SMgr = (*D->path.begin())->getLocation().getManager(); 96 llvm::SmallVector<const PathPieces *, 5> WorkList; 97 WorkList.push_back(&D->path); 98 99 while (!WorkList.empty()) { 100 const PathPieces &path = *WorkList.back(); 101 WorkList.pop_back(); 102 103 for (PathPieces::const_iterator I = path.begin(), E = path.end(); 104 I != E; ++I) { 105 const PathDiagnosticPiece *piece = I->getPtr(); 106 FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc(); 107 108 if (FID.isInvalid()) { 109 FID = SMgr.getFileID(L); 110 } else if (SMgr.getFileID(L) != FID) 111 return; // FIXME: Emit a warning? 112 113 // Check the source ranges. 114 for (PathDiagnosticPiece::range_iterator RI = piece->ranges_begin(), 115 RE = piece->ranges_end(); 116 RI != RE; ++RI) { 117 SourceLocation L = SMgr.getExpansionLoc(RI->getBegin()); 118 if (!L.isFileID() || SMgr.getFileID(L) != FID) 119 return; // FIXME: Emit a warning? 120 L = SMgr.getExpansionLoc(RI->getEnd()); 121 if (!L.isFileID() || SMgr.getFileID(L) != FID) 122 return; // FIXME: Emit a warning? 123 } 124 125 if (const PathDiagnosticCallPiece *call = 126 dyn_cast<PathDiagnosticCallPiece>(piece)) { 127 WorkList.push_back(&call->path); 128 } 129 else if (const PathDiagnosticMacroPiece *macro = 130 dyn_cast<PathDiagnosticMacroPiece>(piece)) { 131 WorkList.push_back(¯o->subPieces); 132 } 133 } 134 } 135 136 if (FID.isInvalid()) 137 return; // FIXME: Emit a warning? 138 } 139 140 // Profile the node to see if we already have something matching it 141 llvm::FoldingSetNodeID profile; 142 D->Profile(profile); 143 void *InsertPos = 0; 144 145 if (PathDiagnostic *orig = Diags.FindNodeOrInsertPos(profile, InsertPos)) { 146 // Keep the PathDiagnostic with the shorter path. 147 const unsigned orig_size = orig->full_size(); 148 const unsigned new_size = D->full_size(); 149 150 if (orig_size <= new_size) { 151 bool shouldKeepOriginal = true; 152 if (orig_size == new_size) { 153 // Here we break ties in a fairly arbitrary, but deterministic, way. 154 llvm::FoldingSetNodeID fullProfile, fullProfileOrig; 155 D->FullProfile(fullProfile); 156 orig->FullProfile(fullProfileOrig); 157 if (fullProfile.ComputeHash() < fullProfileOrig.ComputeHash()) 158 shouldKeepOriginal = false; 159 } 160 161 if (shouldKeepOriginal) 162 return; 163 } 164 Diags.RemoveNode(orig); 165 delete orig; 166 } 167 168 Diags.InsertNode(OwningD.take()); 169} 170 171 172namespace { 173struct CompareDiagnostics { 174 // Compare if 'X' is "<" than 'Y'. 175 bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const { 176 // First compare by location 177 const FullSourceLoc &XLoc = X->getLocation().asLocation(); 178 const FullSourceLoc &YLoc = Y->getLocation().asLocation(); 179 if (XLoc < YLoc) 180 return true; 181 if (XLoc != YLoc) 182 return false; 183 184 // Next, compare by bug type. 185 StringRef XBugType = X->getBugType(); 186 StringRef YBugType = Y->getBugType(); 187 if (XBugType < YBugType) 188 return true; 189 if (XBugType != YBugType) 190 return false; 191 192 // Next, compare by bug description. 193 StringRef XDesc = X->getDescription(); 194 StringRef YDesc = Y->getDescription(); 195 if (XDesc < YDesc) 196 return true; 197 if (XDesc != YDesc) 198 return false; 199 200 // FIXME: Further refine by comparing PathDiagnosticPieces? 201 return false; 202 } 203}; 204} 205 206void 207PathDiagnosticConsumer::FlushDiagnostics(SmallVectorImpl<std::string> *Files) { 208 if (flushed) 209 return; 210 211 flushed = true; 212 213 std::vector<const PathDiagnostic *> BatchDiags; 214 for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(), 215 et = Diags.end(); it != et; ++it) { 216 BatchDiags.push_back(&*it); 217 } 218 219 // Clear out the FoldingSet. 220 Diags.clear(); 221 222 // Sort the diagnostics so that they are always emitted in a deterministic 223 // order. 224 if (!BatchDiags.empty()) 225 std::sort(BatchDiags.begin(), BatchDiags.end(), CompareDiagnostics()); 226 227 FlushDiagnosticsImpl(BatchDiags, Files); 228 229 // Delete the flushed diagnostics. 230 for (std::vector<const PathDiagnostic *>::iterator it = BatchDiags.begin(), 231 et = BatchDiags.end(); it != et; ++it) { 232 const PathDiagnostic *D = *it; 233 delete D; 234 } 235} 236 237//===----------------------------------------------------------------------===// 238// PathDiagnosticLocation methods. 239//===----------------------------------------------------------------------===// 240 241static SourceLocation getValidSourceLocation(const Stmt* S, 242 LocationOrAnalysisDeclContext LAC) { 243 SourceLocation L = S->getLocStart(); 244 assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should " 245 "be passed to PathDiagnosticLocation upon creation."); 246 247 // S might be a temporary statement that does not have a location in the 248 // source code, so find an enclosing statement and use it's location. 249 if (!L.isValid()) { 250 251 ParentMap *PM = 0; 252 if (LAC.is<const LocationContext*>()) 253 PM = &LAC.get<const LocationContext*>()->getParentMap(); 254 else 255 PM = &LAC.get<AnalysisDeclContext*>()->getParentMap(); 256 257 while (!L.isValid()) { 258 S = PM->getParent(S); 259 L = S->getLocStart(); 260 } 261 } 262 263 return L; 264} 265 266PathDiagnosticLocation 267 PathDiagnosticLocation::createBegin(const Decl *D, 268 const SourceManager &SM) { 269 return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK); 270} 271 272PathDiagnosticLocation 273 PathDiagnosticLocation::createBegin(const Stmt *S, 274 const SourceManager &SM, 275 LocationOrAnalysisDeclContext LAC) { 276 return PathDiagnosticLocation(getValidSourceLocation(S, LAC), 277 SM, SingleLocK); 278} 279 280PathDiagnosticLocation 281 PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO, 282 const SourceManager &SM) { 283 return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK); 284} 285 286PathDiagnosticLocation 287 PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME, 288 const SourceManager &SM) { 289 return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK); 290} 291 292PathDiagnosticLocation 293 PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS, 294 const SourceManager &SM) { 295 SourceLocation L = CS->getLBracLoc(); 296 return PathDiagnosticLocation(L, SM, SingleLocK); 297} 298 299PathDiagnosticLocation 300 PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS, 301 const SourceManager &SM) { 302 SourceLocation L = CS->getRBracLoc(); 303 return PathDiagnosticLocation(L, SM, SingleLocK); 304} 305 306PathDiagnosticLocation 307 PathDiagnosticLocation::createDeclBegin(const LocationContext *LC, 308 const SourceManager &SM) { 309 // FIXME: Should handle CXXTryStmt if analyser starts supporting C++. 310 if (const CompoundStmt *CS = 311 dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody())) 312 if (!CS->body_empty()) { 313 SourceLocation Loc = (*CS->body_begin())->getLocStart(); 314 return PathDiagnosticLocation(Loc, SM, SingleLocK); 315 } 316 317 return PathDiagnosticLocation(); 318} 319 320PathDiagnosticLocation 321 PathDiagnosticLocation::createDeclEnd(const LocationContext *LC, 322 const SourceManager &SM) { 323 SourceLocation L = LC->getDecl()->getBodyRBrace(); 324 return PathDiagnosticLocation(L, SM, SingleLocK); 325} 326 327PathDiagnosticLocation 328 PathDiagnosticLocation::create(const ProgramPoint& P, 329 const SourceManager &SMng) { 330 331 const Stmt* S = 0; 332 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 333 const CFGBlock *BSrc = BE->getSrc(); 334 S = BSrc->getTerminatorCondition(); 335 } 336 else if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) { 337 S = PS->getStmt(); 338 } 339 340 return PathDiagnosticLocation(S, SMng, P.getLocationContext()); 341} 342 343PathDiagnosticLocation 344 PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N, 345 const SourceManager &SM) { 346 assert(N && "Cannot create a location with a null node."); 347 348 const ExplodedNode *NI = N; 349 350 while (NI) { 351 ProgramPoint P = NI->getLocation(); 352 const LocationContext *LC = P.getLocationContext(); 353 if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P)) 354 return PathDiagnosticLocation(PS->getStmt(), SM, LC); 355 else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 356 const Stmt *Term = BE->getSrc()->getTerminator(); 357 if (Term) { 358 return PathDiagnosticLocation(Term, SM, LC); 359 } 360 } 361 NI = NI->succ_empty() ? 0 : *(NI->succ_begin()); 362 } 363 364 return createDeclEnd(N->getLocationContext(), SM); 365} 366 367PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation( 368 const PathDiagnosticLocation &PDL) { 369 FullSourceLoc L = PDL.asLocation(); 370 return PathDiagnosticLocation(L, L.getManager(), SingleLocK); 371} 372 373FullSourceLoc 374 PathDiagnosticLocation::genLocation(SourceLocation L, 375 LocationOrAnalysisDeclContext LAC) const { 376 assert(isValid()); 377 // Note that we want a 'switch' here so that the compiler can warn us in 378 // case we add more cases. 379 switch (K) { 380 case SingleLocK: 381 case RangeK: 382 break; 383 case StmtK: 384 // Defensive checking. 385 if (!S) 386 break; 387 return FullSourceLoc(getValidSourceLocation(S, LAC), 388 const_cast<SourceManager&>(*SM)); 389 case DeclK: 390 // Defensive checking. 391 if (!D) 392 break; 393 return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM)); 394 } 395 396 return FullSourceLoc(L, const_cast<SourceManager&>(*SM)); 397} 398 399PathDiagnosticRange 400 PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const { 401 assert(isValid()); 402 // Note that we want a 'switch' here so that the compiler can warn us in 403 // case we add more cases. 404 switch (K) { 405 case SingleLocK: 406 return PathDiagnosticRange(SourceRange(Loc,Loc), true); 407 case RangeK: 408 break; 409 case StmtK: { 410 const Stmt *S = asStmt(); 411 switch (S->getStmtClass()) { 412 default: 413 break; 414 case Stmt::DeclStmtClass: { 415 const DeclStmt *DS = cast<DeclStmt>(S); 416 if (DS->isSingleDecl()) { 417 // Should always be the case, but we'll be defensive. 418 return SourceRange(DS->getLocStart(), 419 DS->getSingleDecl()->getLocation()); 420 } 421 break; 422 } 423 // FIXME: Provide better range information for different 424 // terminators. 425 case Stmt::IfStmtClass: 426 case Stmt::WhileStmtClass: 427 case Stmt::DoStmtClass: 428 case Stmt::ForStmtClass: 429 case Stmt::ChooseExprClass: 430 case Stmt::IndirectGotoStmtClass: 431 case Stmt::SwitchStmtClass: 432 case Stmt::BinaryConditionalOperatorClass: 433 case Stmt::ConditionalOperatorClass: 434 case Stmt::ObjCForCollectionStmtClass: { 435 SourceLocation L = getValidSourceLocation(S, LAC); 436 return SourceRange(L, L); 437 } 438 } 439 SourceRange R = S->getSourceRange(); 440 if (R.isValid()) 441 return R; 442 break; 443 } 444 case DeclK: 445 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 446 return MD->getSourceRange(); 447 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 448 if (Stmt *Body = FD->getBody()) 449 return Body->getSourceRange(); 450 } 451 else { 452 SourceLocation L = D->getLocation(); 453 return PathDiagnosticRange(SourceRange(L, L), true); 454 } 455 } 456 457 return SourceRange(Loc,Loc); 458} 459 460void PathDiagnosticLocation::flatten() { 461 if (K == StmtK) { 462 K = RangeK; 463 S = 0; 464 D = 0; 465 } 466 else if (K == DeclK) { 467 K = SingleLocK; 468 S = 0; 469 D = 0; 470 } 471} 472 473PathDiagnosticLocation PathDiagnostic::getLocation() const { 474 assert(path.size() > 0 && 475 "getLocation() requires a non-empty PathDiagnostic."); 476 477 PathDiagnosticPiece *p = path.rbegin()->getPtr(); 478 479 while (true) { 480 if (PathDiagnosticCallPiece *cp = dyn_cast<PathDiagnosticCallPiece>(p)) { 481 assert(!cp->path.empty()); 482 p = cp->path.rbegin()->getPtr(); 483 continue; 484 } 485 break; 486 } 487 488 return p->getLocation(); 489} 490 491//===----------------------------------------------------------------------===// 492// Manipulation of PathDiagnosticCallPieces. 493//===----------------------------------------------------------------------===// 494 495static PathDiagnosticLocation getLastStmtLoc(const ExplodedNode *N, 496 const SourceManager &SM) { 497 while (N) { 498 ProgramPoint PP = N->getLocation(); 499 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) 500 return PathDiagnosticLocation(SP->getStmt(), SM, PP.getLocationContext()); 501 if (N->pred_empty()) 502 break; 503 N = *N->pred_begin(); 504 } 505 return PathDiagnosticLocation(); 506} 507 508PathDiagnosticCallPiece * 509PathDiagnosticCallPiece::construct(const ExplodedNode *N, 510 const CallExit &CE, 511 const SourceManager &SM) { 512 const Decl *caller = CE.getLocationContext()->getParent()->getDecl(); 513 PathDiagnosticLocation pos = getLastStmtLoc(N, SM); 514 return new PathDiagnosticCallPiece(caller, pos); 515} 516 517PathDiagnosticCallPiece * 518PathDiagnosticCallPiece::construct(PathPieces &path) { 519 PathDiagnosticCallPiece *C = new PathDiagnosticCallPiece(path); 520 path.clear(); 521 path.push_front(C); 522 return C; 523} 524 525void PathDiagnosticCallPiece::setCallee(const CallEnter &CE, 526 const SourceManager &SM) { 527 const Decl *D = CE.getCalleeContext()->getDecl(); 528 Callee = D; 529 callEnter = PathDiagnosticLocation(CE.getCallExpr(), SM, 530 CE.getLocationContext()); 531} 532 533IntrusiveRefCntPtr<PathDiagnosticEventPiece> 534PathDiagnosticCallPiece::getCallEnterEvent() const { 535 if (!Callee) 536 return 0; 537 SmallString<256> buf; 538 llvm::raw_svector_ostream Out(buf); 539 if (isa<BlockDecl>(Callee)) 540 Out << "Entering call to block"; 541 else if (const NamedDecl *ND = dyn_cast<NamedDecl>(Callee)) 542 Out << "Entering call to '" << *ND << "'"; 543 StringRef msg = Out.str(); 544 if (msg.empty()) 545 return 0; 546 return new PathDiagnosticEventPiece(callEnter, msg); 547} 548 549IntrusiveRefCntPtr<PathDiagnosticEventPiece> 550PathDiagnosticCallPiece::getCallExitEvent() const { 551 if (!Caller) 552 return 0; 553 SmallString<256> buf; 554 llvm::raw_svector_ostream Out(buf); 555 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Caller)) 556 Out << "Returning to '" << *ND << "'"; 557 else 558 Out << "Returning to caller"; 559 return new PathDiagnosticEventPiece(callReturn, Out.str()); 560} 561 562static void compute_path_size(const PathPieces &pieces, unsigned &size) { 563 for (PathPieces::const_iterator it = pieces.begin(), 564 et = pieces.end(); it != et; ++it) { 565 const PathDiagnosticPiece *piece = it->getPtr(); 566 if (const PathDiagnosticCallPiece *cp = 567 dyn_cast<PathDiagnosticCallPiece>(piece)) { 568 compute_path_size(cp->path, size); 569 } 570 else 571 ++size; 572 } 573} 574 575unsigned PathDiagnostic::full_size() { 576 unsigned size = 0; 577 compute_path_size(path, size); 578 return size; 579} 580 581//===----------------------------------------------------------------------===// 582// FoldingSet profiling methods. 583//===----------------------------------------------------------------------===// 584 585void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const { 586 ID.AddInteger(Range.getBegin().getRawEncoding()); 587 ID.AddInteger(Range.getEnd().getRawEncoding()); 588 ID.AddInteger(Loc.getRawEncoding()); 589 return; 590} 591 592void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const { 593 ID.AddInteger((unsigned) getKind()); 594 ID.AddString(str); 595 // FIXME: Add profiling support for code hints. 596 ID.AddInteger((unsigned) getDisplayHint()); 597 for (range_iterator I = ranges_begin(), E = ranges_end(); I != E; ++I) { 598 ID.AddInteger(I->getBegin().getRawEncoding()); 599 ID.AddInteger(I->getEnd().getRawEncoding()); 600 } 601} 602 603void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const { 604 PathDiagnosticPiece::Profile(ID); 605 for (PathPieces::const_iterator it = path.begin(), 606 et = path.end(); it != et; ++it) { 607 ID.Add(**it); 608 } 609} 610 611void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const { 612 PathDiagnosticPiece::Profile(ID); 613 ID.Add(Pos); 614} 615 616void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const { 617 PathDiagnosticPiece::Profile(ID); 618 for (const_iterator I = begin(), E = end(); I != E; ++I) 619 ID.Add(*I); 620} 621 622void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const { 623 PathDiagnosticSpotPiece::Profile(ID); 624 for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end(); 625 I != E; ++I) 626 ID.Add(**I); 627} 628 629void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const { 630 if (!path.empty()) 631 getLocation().Profile(ID); 632 ID.AddString(BugType); 633 ID.AddString(Desc); 634 ID.AddString(Category); 635} 636 637void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const { 638 Profile(ID); 639 for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I) 640 ID.Add(**I); 641 for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I) 642 ID.AddString(*I); 643} 644