BugReporter.cpp revision 341825
1//===- BugReporter.cpp - Generate PathDiagnostics for bugs ----------------===// 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 BugReporter, a utility class for generating 11// PathDiagnostics. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 16#include "clang/AST/Decl.h" 17#include "clang/AST/DeclBase.h" 18#include "clang/AST/DeclObjC.h" 19#include "clang/AST/Expr.h" 20#include "clang/AST/ExprCXX.h" 21#include "clang/AST/ParentMap.h" 22#include "clang/AST/Stmt.h" 23#include "clang/AST/StmtCXX.h" 24#include "clang/AST/StmtObjC.h" 25#include "clang/Analysis/AnalysisDeclContext.h" 26#include "clang/Analysis/CFG.h" 27#include "clang/Analysis/CFGStmtMap.h" 28#include "clang/Analysis/ProgramPoint.h" 29#include "clang/Basic/LLVM.h" 30#include "clang/Basic/SourceLocation.h" 31#include "clang/Basic/SourceManager.h" 32#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 33#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h" 34#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 35#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 36#include "clang/StaticAnalyzer/Core/Checker.h" 37#include "clang/StaticAnalyzer/Core/CheckerManager.h" 38#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 39#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 40#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 41#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 42#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 43#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 44#include "llvm/ADT/ArrayRef.h" 45#include "llvm/ADT/DenseMap.h" 46#include "llvm/ADT/DenseSet.h" 47#include "llvm/ADT/FoldingSet.h" 48#include "llvm/ADT/None.h" 49#include "llvm/ADT/Optional.h" 50#include "llvm/ADT/STLExtras.h" 51#include "llvm/ADT/SmallPtrSet.h" 52#include "llvm/ADT/SmallString.h" 53#include "llvm/ADT/SmallVector.h" 54#include "llvm/ADT/Statistic.h" 55#include "llvm/ADT/StringRef.h" 56#include "llvm/ADT/iterator_range.h" 57#include "llvm/Support/Casting.h" 58#include "llvm/Support/Compiler.h" 59#include "llvm/Support/ErrorHandling.h" 60#include "llvm/Support/MemoryBuffer.h" 61#include "llvm/Support/raw_ostream.h" 62#include <algorithm> 63#include <cassert> 64#include <cstddef> 65#include <iterator> 66#include <memory> 67#include <queue> 68#include <string> 69#include <tuple> 70#include <utility> 71#include <vector> 72 73using namespace clang; 74using namespace ento; 75 76#define DEBUG_TYPE "BugReporter" 77 78STATISTIC(MaxBugClassSize, 79 "The maximum number of bug reports in the same equivalence class"); 80STATISTIC(MaxValidBugClassSize, 81 "The maximum number of bug reports in the same equivalence class " 82 "where at least one report is valid (not suppressed)"); 83 84BugReporterVisitor::~BugReporterVisitor() = default; 85 86void BugReporterContext::anchor() {} 87 88//===----------------------------------------------------------------------===// 89// Helper routines for walking the ExplodedGraph and fetching statements. 90//===----------------------------------------------------------------------===// 91 92static const Stmt *GetPreviousStmt(const ExplodedNode *N) { 93 for (N = N->getFirstPred(); N; N = N->getFirstPred()) 94 if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 95 return S; 96 97 return nullptr; 98} 99 100static inline const Stmt* 101GetCurrentOrPreviousStmt(const ExplodedNode *N) { 102 if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 103 return S; 104 105 return GetPreviousStmt(N); 106} 107 108//===----------------------------------------------------------------------===// 109// Diagnostic cleanup. 110//===----------------------------------------------------------------------===// 111 112static PathDiagnosticEventPiece * 113eventsDescribeSameCondition(PathDiagnosticEventPiece *X, 114 PathDiagnosticEventPiece *Y) { 115 // Prefer diagnostics that come from ConditionBRVisitor over 116 // those that came from TrackConstraintBRVisitor, 117 // unless the one from ConditionBRVisitor is 118 // its generic fallback diagnostic. 119 const void *tagPreferred = ConditionBRVisitor::getTag(); 120 const void *tagLesser = TrackConstraintBRVisitor::getTag(); 121 122 if (X->getLocation() != Y->getLocation()) 123 return nullptr; 124 125 if (X->getTag() == tagPreferred && Y->getTag() == tagLesser) 126 return ConditionBRVisitor::isPieceMessageGeneric(X) ? Y : X; 127 128 if (Y->getTag() == tagPreferred && X->getTag() == tagLesser) 129 return ConditionBRVisitor::isPieceMessageGeneric(Y) ? X : Y; 130 131 return nullptr; 132} 133 134/// An optimization pass over PathPieces that removes redundant diagnostics 135/// generated by both ConditionBRVisitor and TrackConstraintBRVisitor. Both 136/// BugReporterVisitors use different methods to generate diagnostics, with 137/// one capable of emitting diagnostics in some cases but not in others. This 138/// can lead to redundant diagnostic pieces at the same point in a path. 139static void removeRedundantMsgs(PathPieces &path) { 140 unsigned N = path.size(); 141 if (N < 2) 142 return; 143 // NOTE: this loop intentionally is not using an iterator. Instead, we 144 // are streaming the path and modifying it in place. This is done by 145 // grabbing the front, processing it, and if we decide to keep it append 146 // it to the end of the path. The entire path is processed in this way. 147 for (unsigned i = 0; i < N; ++i) { 148 auto piece = std::move(path.front()); 149 path.pop_front(); 150 151 switch (piece->getKind()) { 152 case PathDiagnosticPiece::Call: 153 removeRedundantMsgs(cast<PathDiagnosticCallPiece>(*piece).path); 154 break; 155 case PathDiagnosticPiece::Macro: 156 removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(*piece).subPieces); 157 break; 158 case PathDiagnosticPiece::ControlFlow: 159 break; 160 case PathDiagnosticPiece::Event: { 161 if (i == N-1) 162 break; 163 164 if (auto *nextEvent = 165 dyn_cast<PathDiagnosticEventPiece>(path.front().get())) { 166 auto *event = cast<PathDiagnosticEventPiece>(piece.get()); 167 // Check to see if we should keep one of the two pieces. If we 168 // come up with a preference, record which piece to keep, and consume 169 // another piece from the path. 170 if (auto *pieceToKeep = 171 eventsDescribeSameCondition(event, nextEvent)) { 172 piece = std::move(pieceToKeep == event ? piece : path.front()); 173 path.pop_front(); 174 ++i; 175 } 176 } 177 break; 178 } 179 case PathDiagnosticPiece::Note: 180 break; 181 } 182 path.push_back(std::move(piece)); 183 } 184} 185 186/// A map from PathDiagnosticPiece to the LocationContext of the inlined 187/// function call it represents. 188using LocationContextMap = 189 llvm::DenseMap<const PathPieces *, const LocationContext *>; 190 191/// Recursively scan through a path and prune out calls and macros pieces 192/// that aren't needed. Return true if afterwards the path contains 193/// "interesting stuff" which means it shouldn't be pruned from the parent path. 194static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, 195 LocationContextMap &LCM, 196 bool IsInteresting = false) { 197 bool containsSomethingInteresting = IsInteresting; 198 const unsigned N = pieces.size(); 199 200 for (unsigned i = 0 ; i < N ; ++i) { 201 // Remove the front piece from the path. If it is still something we 202 // want to keep once we are done, we will push it back on the end. 203 auto piece = std::move(pieces.front()); 204 pieces.pop_front(); 205 206 switch (piece->getKind()) { 207 case PathDiagnosticPiece::Call: { 208 auto &call = cast<PathDiagnosticCallPiece>(*piece); 209 // Check if the location context is interesting. 210 assert(LCM.count(&call.path)); 211 if (!removeUnneededCalls(call.path, R, LCM, 212 R->isInteresting(LCM[&call.path]))) 213 continue; 214 215 containsSomethingInteresting = true; 216 break; 217 } 218 case PathDiagnosticPiece::Macro: { 219 auto ¯o = cast<PathDiagnosticMacroPiece>(*piece); 220 if (!removeUnneededCalls(macro.subPieces, R, LCM, IsInteresting)) 221 continue; 222 containsSomethingInteresting = true; 223 break; 224 } 225 case PathDiagnosticPiece::Event: { 226 auto &event = cast<PathDiagnosticEventPiece>(*piece); 227 228 // We never throw away an event, but we do throw it away wholesale 229 // as part of a path if we throw the entire path away. 230 containsSomethingInteresting |= !event.isPrunable(); 231 break; 232 } 233 case PathDiagnosticPiece::ControlFlow: 234 break; 235 236 case PathDiagnosticPiece::Note: 237 break; 238 } 239 240 pieces.push_back(std::move(piece)); 241 } 242 243 return containsSomethingInteresting; 244} 245 246/// Returns true if the given decl has been implicitly given a body, either by 247/// the analyzer or by the compiler proper. 248static bool hasImplicitBody(const Decl *D) { 249 assert(D); 250 return D->isImplicit() || !D->hasBody(); 251} 252 253/// Recursively scan through a path and make sure that all call pieces have 254/// valid locations. 255static void 256adjustCallLocations(PathPieces &Pieces, 257 PathDiagnosticLocation *LastCallLocation = nullptr) { 258 for (const auto &I : Pieces) { 259 auto *Call = dyn_cast<PathDiagnosticCallPiece>(I.get()); 260 261 if (!Call) 262 continue; 263 264 if (LastCallLocation) { 265 bool CallerIsImplicit = hasImplicitBody(Call->getCaller()); 266 if (CallerIsImplicit || !Call->callEnter.asLocation().isValid()) 267 Call->callEnter = *LastCallLocation; 268 if (CallerIsImplicit || !Call->callReturn.asLocation().isValid()) 269 Call->callReturn = *LastCallLocation; 270 } 271 272 // Recursively clean out the subclass. Keep this call around if 273 // it contains any informative diagnostics. 274 PathDiagnosticLocation *ThisCallLocation; 275 if (Call->callEnterWithin.asLocation().isValid() && 276 !hasImplicitBody(Call->getCallee())) 277 ThisCallLocation = &Call->callEnterWithin; 278 else 279 ThisCallLocation = &Call->callEnter; 280 281 assert(ThisCallLocation && "Outermost call has an invalid location"); 282 adjustCallLocations(Call->path, ThisCallLocation); 283 } 284} 285 286/// Remove edges in and out of C++ default initializer expressions. These are 287/// for fields that have in-class initializers, as opposed to being initialized 288/// explicitly in a constructor or braced list. 289static void removeEdgesToDefaultInitializers(PathPieces &Pieces) { 290 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 291 if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get())) 292 removeEdgesToDefaultInitializers(C->path); 293 294 if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get())) 295 removeEdgesToDefaultInitializers(M->subPieces); 296 297 if (auto *CF = dyn_cast<PathDiagnosticControlFlowPiece>(I->get())) { 298 const Stmt *Start = CF->getStartLocation().asStmt(); 299 const Stmt *End = CF->getEndLocation().asStmt(); 300 if (Start && isa<CXXDefaultInitExpr>(Start)) { 301 I = Pieces.erase(I); 302 continue; 303 } else if (End && isa<CXXDefaultInitExpr>(End)) { 304 PathPieces::iterator Next = std::next(I); 305 if (Next != E) { 306 if (auto *NextCF = 307 dyn_cast<PathDiagnosticControlFlowPiece>(Next->get())) { 308 NextCF->setStartLocation(CF->getStartLocation()); 309 } 310 } 311 I = Pieces.erase(I); 312 continue; 313 } 314 } 315 316 I++; 317 } 318} 319 320/// Remove all pieces with invalid locations as these cannot be serialized. 321/// We might have pieces with invalid locations as a result of inlining Body 322/// Farm generated functions. 323static void removePiecesWithInvalidLocations(PathPieces &Pieces) { 324 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 325 if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get())) 326 removePiecesWithInvalidLocations(C->path); 327 328 if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get())) 329 removePiecesWithInvalidLocations(M->subPieces); 330 331 if (!(*I)->getLocation().isValid() || 332 !(*I)->getLocation().asLocation().isValid()) { 333 I = Pieces.erase(I); 334 continue; 335 } 336 I++; 337 } 338} 339 340//===----------------------------------------------------------------------===// 341// PathDiagnosticBuilder and its associated routines and helper objects. 342//===----------------------------------------------------------------------===// 343 344namespace { 345 346class PathDiagnosticBuilder : public BugReporterContext { 347 BugReport *R; 348 PathDiagnosticConsumer *PDC; 349 350public: 351 const LocationContext *LC; 352 353 PathDiagnosticBuilder(GRBugReporter &br, 354 BugReport *r, InterExplodedGraphMap &Backmap, 355 PathDiagnosticConsumer *pdc) 356 : BugReporterContext(br, Backmap), R(r), PDC(pdc), 357 LC(r->getErrorNode()->getLocationContext()) {} 358 359 PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 360 361 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 362 const ExplodedNode *N); 363 364 BugReport *getBugReport() { return R; } 365 366 Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 367 368 ParentMap& getParentMap() { return LC->getParentMap(); } 369 370 const Stmt *getParent(const Stmt *S) { 371 return getParentMap().getParent(S); 372 } 373 374 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 375 376 PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const { 377 return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Minimal; 378 } 379 380 bool supportsLogicalOpControlFlow() const { 381 return PDC ? PDC->supportsLogicalOpControlFlow() : true; 382 } 383}; 384 385} // namespace 386 387PathDiagnosticLocation 388PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 389 if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N)) 390 return PathDiagnosticLocation(S, getSourceManager(), LC); 391 392 return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(), 393 getSourceManager()); 394} 395 396PathDiagnosticLocation 397PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 398 const ExplodedNode *N) { 399 // Slow, but probably doesn't matter. 400 if (os.str().empty()) 401 os << ' '; 402 403 const PathDiagnosticLocation &Loc = ExecutionContinues(N); 404 405 if (Loc.asStmt()) 406 os << "Execution continues on line " 407 << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 408 << '.'; 409 else { 410 os << "Execution jumps to the end of the "; 411 const Decl *D = N->getLocationContext()->getDecl(); 412 if (isa<ObjCMethodDecl>(D)) 413 os << "method"; 414 else if (isa<FunctionDecl>(D)) 415 os << "function"; 416 else { 417 assert(isa<BlockDecl>(D)); 418 os << "anonymous block"; 419 } 420 os << '.'; 421 } 422 423 return Loc; 424} 425 426static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) { 427 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 428 return PM.getParentIgnoreParens(S); 429 430 const Stmt *Parent = PM.getParentIgnoreParens(S); 431 if (!Parent) 432 return nullptr; 433 434 switch (Parent->getStmtClass()) { 435 case Stmt::ForStmtClass: 436 case Stmt::DoStmtClass: 437 case Stmt::WhileStmtClass: 438 case Stmt::ObjCForCollectionStmtClass: 439 case Stmt::CXXForRangeStmtClass: 440 return Parent; 441 default: 442 break; 443 } 444 445 return nullptr; 446} 447 448static PathDiagnosticLocation 449getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, 450 const LocationContext *LC, bool allowNestedContexts) { 451 if (!S) 452 return {}; 453 454 while (const Stmt *Parent = getEnclosingParent(S, P)) { 455 switch (Parent->getStmtClass()) { 456 case Stmt::BinaryOperatorClass: { 457 const auto *B = cast<BinaryOperator>(Parent); 458 if (B->isLogicalOp()) 459 return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC); 460 break; 461 } 462 case Stmt::CompoundStmtClass: 463 case Stmt::StmtExprClass: 464 return PathDiagnosticLocation(S, SMgr, LC); 465 case Stmt::ChooseExprClass: 466 // Similar to '?' if we are referring to condition, just have the edge 467 // point to the entire choose expression. 468 if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S) 469 return PathDiagnosticLocation(Parent, SMgr, LC); 470 else 471 return PathDiagnosticLocation(S, SMgr, LC); 472 case Stmt::BinaryConditionalOperatorClass: 473 case Stmt::ConditionalOperatorClass: 474 // For '?', if we are referring to condition, just have the edge point 475 // to the entire '?' expression. 476 if (allowNestedContexts || 477 cast<AbstractConditionalOperator>(Parent)->getCond() == S) 478 return PathDiagnosticLocation(Parent, SMgr, LC); 479 else 480 return PathDiagnosticLocation(S, SMgr, LC); 481 case Stmt::CXXForRangeStmtClass: 482 if (cast<CXXForRangeStmt>(Parent)->getBody() == S) 483 return PathDiagnosticLocation(S, SMgr, LC); 484 break; 485 case Stmt::DoStmtClass: 486 return PathDiagnosticLocation(S, SMgr, LC); 487 case Stmt::ForStmtClass: 488 if (cast<ForStmt>(Parent)->getBody() == S) 489 return PathDiagnosticLocation(S, SMgr, LC); 490 break; 491 case Stmt::IfStmtClass: 492 if (cast<IfStmt>(Parent)->getCond() != S) 493 return PathDiagnosticLocation(S, SMgr, LC); 494 break; 495 case Stmt::ObjCForCollectionStmtClass: 496 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 497 return PathDiagnosticLocation(S, SMgr, LC); 498 break; 499 case Stmt::WhileStmtClass: 500 if (cast<WhileStmt>(Parent)->getCond() != S) 501 return PathDiagnosticLocation(S, SMgr, LC); 502 break; 503 default: 504 break; 505 } 506 507 S = Parent; 508 } 509 510 assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 511 512 return PathDiagnosticLocation(S, SMgr, LC); 513} 514 515PathDiagnosticLocation 516PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 517 assert(S && "Null Stmt passed to getEnclosingStmtLocation"); 518 return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC, 519 /*allowNestedContexts=*/false); 520} 521 522//===----------------------------------------------------------------------===// 523// "Minimal" path diagnostic generation algorithm. 524//===----------------------------------------------------------------------===// 525using StackDiagPair = 526 std::pair<PathDiagnosticCallPiece *, const ExplodedNode *>; 527using StackDiagVector = SmallVector<StackDiagPair, 6>; 528 529static void updateStackPiecesWithMessage(PathDiagnosticPiece &P, 530 StackDiagVector &CallStack) { 531 // If the piece contains a special message, add it to all the call 532 // pieces on the active stack. 533 if (auto *ep = dyn_cast<PathDiagnosticEventPiece>(&P)) { 534 if (ep->hasCallStackHint()) 535 for (const auto &I : CallStack) { 536 PathDiagnosticCallPiece *CP = I.first; 537 const ExplodedNode *N = I.second; 538 std::string stackMsg = ep->getCallStackMessage(N); 539 540 // The last message on the path to final bug is the most important 541 // one. Since we traverse the path backwards, do not add the message 542 // if one has been previously added. 543 if (!CP->hasCallStackMessage()) 544 CP->setCallStackMessage(stackMsg); 545 } 546 } 547} 548 549static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); 550 551 552std::shared_ptr<PathDiagnosticControlFlowPiece> generateDiagForSwitchOP( 553 const ExplodedNode *N, 554 const CFGBlock *Dst, 555 const SourceManager &SM, 556 const LocationContext *LC, 557 PathDiagnosticBuilder &PDB, 558 PathDiagnosticLocation &Start 559 ) { 560 // Figure out what case arm we took. 561 std::string sbuf; 562 llvm::raw_string_ostream os(sbuf); 563 PathDiagnosticLocation End; 564 565 if (const Stmt *S = Dst->getLabel()) { 566 End = PathDiagnosticLocation(S, SM, LC); 567 568 switch (S->getStmtClass()) { 569 default: 570 os << "No cases match in the switch statement. " 571 "Control jumps to line " 572 << End.asLocation().getExpansionLineNumber(); 573 break; 574 case Stmt::DefaultStmtClass: 575 os << "Control jumps to the 'default' case at line " 576 << End.asLocation().getExpansionLineNumber(); 577 break; 578 579 case Stmt::CaseStmtClass: { 580 os << "Control jumps to 'case "; 581 const auto *Case = cast<CaseStmt>(S); 582 const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 583 584 // Determine if it is an enum. 585 bool GetRawInt = true; 586 587 if (const auto *DR = dyn_cast<DeclRefExpr>(LHS)) { 588 // FIXME: Maybe this should be an assertion. Are there cases 589 // were it is not an EnumConstantDecl? 590 const auto *D = dyn_cast<EnumConstantDecl>(DR->getDecl()); 591 592 if (D) { 593 GetRawInt = false; 594 os << *D; 595 } 596 } 597 598 if (GetRawInt) 599 os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); 600 601 os << ":' at line " << End.asLocation().getExpansionLineNumber(); 602 break; 603 } 604 } 605 } else { 606 os << "'Default' branch taken. "; 607 End = PDB.ExecutionContinues(os, N); 608 } 609 return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 610 os.str()); 611} 612 613 614std::shared_ptr<PathDiagnosticControlFlowPiece> generateDiagForGotoOP( 615 const Stmt *S, 616 PathDiagnosticBuilder &PDB, 617 PathDiagnosticLocation &Start) { 618 std::string sbuf; 619 llvm::raw_string_ostream os(sbuf); 620 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 621 os << "Control jumps to line " << End.asLocation().getExpansionLineNumber(); 622 return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()); 623 624} 625 626std::shared_ptr<PathDiagnosticControlFlowPiece> generateDiagForBinaryOP( 627 const ExplodedNode *N, 628 const Stmt *T, 629 const CFGBlock *Src, 630 const CFGBlock *Dst, 631 const SourceManager &SM, 632 PathDiagnosticBuilder &PDB, 633 const LocationContext *LC) { 634 const auto *B = cast<BinaryOperator>(T); 635 std::string sbuf; 636 llvm::raw_string_ostream os(sbuf); 637 os << "Left side of '"; 638 PathDiagnosticLocation Start, End; 639 640 if (B->getOpcode() == BO_LAnd) { 641 os << "&&" 642 << "' is "; 643 644 if (*(Src->succ_begin() + 1) == Dst) { 645 os << "false"; 646 End = PathDiagnosticLocation(B->getLHS(), SM, LC); 647 Start = 648 PathDiagnosticLocation::createOperatorLoc(B, SM); 649 } else { 650 os << "true"; 651 Start = PathDiagnosticLocation(B->getLHS(), SM, LC); 652 End = PDB.ExecutionContinues(N); 653 } 654 } else { 655 assert(B->getOpcode() == BO_LOr); 656 os << "||" 657 << "' is "; 658 659 if (*(Src->succ_begin() + 1) == Dst) { 660 os << "false"; 661 Start = PathDiagnosticLocation(B->getLHS(), SM, LC); 662 End = PDB.ExecutionContinues(N); 663 } else { 664 os << "true"; 665 End = PathDiagnosticLocation(B->getLHS(), SM, LC); 666 Start = 667 PathDiagnosticLocation::createOperatorLoc(B, SM); 668 } 669 } 670 return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 671 os.str()); 672} 673 674void generateMinimalDiagForBlockEdge(const ExplodedNode *N, BlockEdge BE, 675 const SourceManager &SM, 676 PathDiagnosticBuilder &PDB, 677 PathDiagnostic &PD) { 678 const LocationContext *LC = N->getLocationContext(); 679 const CFGBlock *Src = BE.getSrc(); 680 const CFGBlock *Dst = BE.getDst(); 681 const Stmt *T = Src->getTerminator(); 682 if (!T) 683 return; 684 685 auto Start = PathDiagnosticLocation::createBegin(T, SM, LC); 686 switch (T->getStmtClass()) { 687 default: 688 break; 689 690 case Stmt::GotoStmtClass: 691 case Stmt::IndirectGotoStmtClass: { 692 if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N)) 693 PD.getActivePath().push_front(generateDiagForGotoOP(S, PDB, Start)); 694 break; 695 } 696 697 case Stmt::SwitchStmtClass: { 698 PD.getActivePath().push_front( 699 generateDiagForSwitchOP(N, Dst, SM, LC, PDB, Start)); 700 break; 701 } 702 703 case Stmt::BreakStmtClass: 704 case Stmt::ContinueStmtClass: { 705 std::string sbuf; 706 llvm::raw_string_ostream os(sbuf); 707 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 708 PD.getActivePath().push_front( 709 std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str())); 710 break; 711 } 712 713 // Determine control-flow for ternary '?'. 714 case Stmt::BinaryConditionalOperatorClass: 715 case Stmt::ConditionalOperatorClass: { 716 std::string sbuf; 717 llvm::raw_string_ostream os(sbuf); 718 os << "'?' condition is "; 719 720 if (*(Src->succ_begin() + 1) == Dst) 721 os << "false"; 722 else 723 os << "true"; 724 725 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 726 727 if (const Stmt *S = End.asStmt()) 728 End = PDB.getEnclosingStmtLocation(S); 729 730 PD.getActivePath().push_front( 731 std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str())); 732 break; 733 } 734 735 // Determine control-flow for short-circuited '&&' and '||'. 736 case Stmt::BinaryOperatorClass: { 737 if (!PDB.supportsLogicalOpControlFlow()) 738 break; 739 740 std::shared_ptr<PathDiagnosticControlFlowPiece> Diag = 741 generateDiagForBinaryOP(N, T, Src, Dst, SM, PDB, LC); 742 PD.getActivePath().push_front(Diag); 743 break; 744 } 745 746 case Stmt::DoStmtClass: 747 if (*(Src->succ_begin()) == Dst) { 748 std::string sbuf; 749 llvm::raw_string_ostream os(sbuf); 750 751 os << "Loop condition is true. "; 752 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 753 754 if (const Stmt *S = End.asStmt()) 755 End = PDB.getEnclosingStmtLocation(S); 756 757 PD.getActivePath().push_front( 758 std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 759 os.str())); 760 } else { 761 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 762 763 if (const Stmt *S = End.asStmt()) 764 End = PDB.getEnclosingStmtLocation(S); 765 766 PD.getActivePath().push_front( 767 std::make_shared<PathDiagnosticControlFlowPiece>( 768 Start, End, "Loop condition is false. Exiting loop")); 769 } 770 break; 771 772 case Stmt::WhileStmtClass: 773 case Stmt::ForStmtClass: 774 if (*(Src->succ_begin() + 1) == Dst) { 775 std::string sbuf; 776 llvm::raw_string_ostream os(sbuf); 777 778 os << "Loop condition is false. "; 779 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 780 if (const Stmt *S = End.asStmt()) 781 End = PDB.getEnclosingStmtLocation(S); 782 783 PD.getActivePath().push_front( 784 std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 785 os.str())); 786 } else { 787 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 788 if (const Stmt *S = End.asStmt()) 789 End = PDB.getEnclosingStmtLocation(S); 790 791 PD.getActivePath().push_front( 792 std::make_shared<PathDiagnosticControlFlowPiece>( 793 Start, End, "Loop condition is true. Entering loop body")); 794 } 795 796 break; 797 798 case Stmt::IfStmtClass: { 799 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 800 801 if (const Stmt *S = End.asStmt()) 802 End = PDB.getEnclosingStmtLocation(S); 803 804 if (*(Src->succ_begin() + 1) == Dst) 805 PD.getActivePath().push_front( 806 std::make_shared<PathDiagnosticControlFlowPiece>( 807 Start, End, "Taking false branch")); 808 else 809 PD.getActivePath().push_front( 810 std::make_shared<PathDiagnosticControlFlowPiece>( 811 Start, End, "Taking true branch")); 812 813 break; 814 } 815 } 816} 817 818// Cone-of-influence: support the reverse propagation of "interesting" symbols 819// and values by tracing interesting calculations backwards through evaluated 820// expressions along a path. This is probably overly complicated, but the idea 821// is that if an expression computed an "interesting" value, the child 822// expressions are are also likely to be "interesting" as well (which then 823// propagates to the values they in turn compute). This reverse propagation 824// is needed to track interesting correlations across function call boundaries, 825// where formal arguments bind to actual arguments, etc. This is also needed 826// because the constraint solver sometimes simplifies certain symbolic values 827// into constants when appropriate, and this complicates reasoning about 828// interesting values. 829using InterestingExprs = llvm::DenseSet<const Expr *>; 830 831static void reversePropagateIntererstingSymbols(BugReport &R, 832 InterestingExprs &IE, 833 const ProgramState *State, 834 const Expr *Ex, 835 const LocationContext *LCtx) { 836 SVal V = State->getSVal(Ex, LCtx); 837 if (!(R.isInteresting(V) || IE.count(Ex))) 838 return; 839 840 switch (Ex->getStmtClass()) { 841 default: 842 if (!isa<CastExpr>(Ex)) 843 break; 844 // Fall through. 845 case Stmt::BinaryOperatorClass: 846 case Stmt::UnaryOperatorClass: { 847 for (const Stmt *SubStmt : Ex->children()) { 848 if (const auto *child = dyn_cast_or_null<Expr>(SubStmt)) { 849 IE.insert(child); 850 SVal ChildV = State->getSVal(child, LCtx); 851 R.markInteresting(ChildV); 852 } 853 } 854 break; 855 } 856 } 857 858 R.markInteresting(V); 859} 860 861static void reversePropagateInterestingSymbols(BugReport &R, 862 InterestingExprs &IE, 863 const ProgramState *State, 864 const LocationContext *CalleeCtx, 865 const LocationContext *CallerCtx) 866{ 867 // FIXME: Handle non-CallExpr-based CallEvents. 868 const StackFrameContext *Callee = CalleeCtx->getStackFrame(); 869 const Stmt *CallSite = Callee->getCallSite(); 870 if (const auto *CE = dyn_cast_or_null<CallExpr>(CallSite)) { 871 if (const auto *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) { 872 FunctionDecl::param_const_iterator PI = FD->param_begin(), 873 PE = FD->param_end(); 874 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 875 for (; AI != AE && PI != PE; ++AI, ++PI) { 876 if (const Expr *ArgE = *AI) { 877 if (const ParmVarDecl *PD = *PI) { 878 Loc LV = State->getLValue(PD, CalleeCtx); 879 if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV))) 880 IE.insert(ArgE); 881 } 882 } 883 } 884 } 885 } 886} 887 888//===----------------------------------------------------------------------===// 889// Functions for determining if a loop was executed 0 times. 890//===----------------------------------------------------------------------===// 891 892static bool isLoop(const Stmt *Term) { 893 switch (Term->getStmtClass()) { 894 case Stmt::ForStmtClass: 895 case Stmt::WhileStmtClass: 896 case Stmt::ObjCForCollectionStmtClass: 897 case Stmt::CXXForRangeStmtClass: 898 return true; 899 default: 900 // Note that we intentionally do not include do..while here. 901 return false; 902 } 903} 904 905static bool isJumpToFalseBranch(const BlockEdge *BE) { 906 const CFGBlock *Src = BE->getSrc(); 907 assert(Src->succ_size() == 2); 908 return (*(Src->succ_begin()+1) == BE->getDst()); 909} 910 911static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) { 912 while (SubS) { 913 if (SubS == S) 914 return true; 915 SubS = PM.getParent(SubS); 916 } 917 return false; 918} 919 920static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term, 921 const ExplodedNode *N) { 922 while (N) { 923 Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>(); 924 if (SP) { 925 const Stmt *S = SP->getStmt(); 926 if (!isContainedByStmt(PM, Term, S)) 927 return S; 928 } 929 N = N->getFirstPred(); 930 } 931 return nullptr; 932} 933 934static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) { 935 const Stmt *LoopBody = nullptr; 936 switch (Term->getStmtClass()) { 937 case Stmt::CXXForRangeStmtClass: { 938 const auto *FR = cast<CXXForRangeStmt>(Term); 939 if (isContainedByStmt(PM, FR->getInc(), S)) 940 return true; 941 if (isContainedByStmt(PM, FR->getLoopVarStmt(), S)) 942 return true; 943 LoopBody = FR->getBody(); 944 break; 945 } 946 case Stmt::ForStmtClass: { 947 const auto *FS = cast<ForStmt>(Term); 948 if (isContainedByStmt(PM, FS->getInc(), S)) 949 return true; 950 LoopBody = FS->getBody(); 951 break; 952 } 953 case Stmt::ObjCForCollectionStmtClass: { 954 const auto *FC = cast<ObjCForCollectionStmt>(Term); 955 LoopBody = FC->getBody(); 956 break; 957 } 958 case Stmt::WhileStmtClass: 959 LoopBody = cast<WhileStmt>(Term)->getBody(); 960 break; 961 default: 962 return false; 963 } 964 return isContainedByStmt(PM, LoopBody, S); 965} 966 967/// Adds a sanitized control-flow diagnostic edge to a path. 968static void addEdgeToPath(PathPieces &path, 969 PathDiagnosticLocation &PrevLoc, 970 PathDiagnosticLocation NewLoc, 971 const LocationContext *LC) { 972 if (!NewLoc.isValid()) 973 return; 974 975 SourceLocation NewLocL = NewLoc.asLocation(); 976 if (NewLocL.isInvalid()) 977 return; 978 979 if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) { 980 PrevLoc = NewLoc; 981 return; 982 } 983 984 // Ignore self-edges, which occur when there are multiple nodes at the same 985 // statement. 986 if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt()) 987 return; 988 989 path.push_front( 990 std::make_shared<PathDiagnosticControlFlowPiece>(NewLoc, PrevLoc)); 991 PrevLoc = NewLoc; 992} 993 994/// A customized wrapper for CFGBlock::getTerminatorCondition() 995/// which returns the element for ObjCForCollectionStmts. 996static const Stmt *getTerminatorCondition(const CFGBlock *B) { 997 const Stmt *S = B->getTerminatorCondition(); 998 if (const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(S)) 999 return FS->getElement(); 1000 return S; 1001} 1002 1003static const char StrEnteringLoop[] = "Entering loop body"; 1004static const char StrLoopBodyZero[] = "Loop body executed 0 times"; 1005static const char StrLoopRangeEmpty[] = 1006 "Loop body skipped when range is empty"; 1007static const char StrLoopCollectionEmpty[] = 1008 "Loop body skipped when collection is empty"; 1009 1010static std::unique_ptr<FilesToLineNumsMap> 1011findExecutedLines(SourceManager &SM, const ExplodedNode *N); 1012 1013/// Generate diagnostics for the node \p N, 1014/// and write it into \p PD. 1015/// \p AddPathEdges Whether diagnostic consumer can generate path arrows 1016/// showing both row and column. 1017static void generatePathDiagnosticsForNode(const ExplodedNode *N, 1018 PathDiagnostic &PD, 1019 PathDiagnosticLocation &PrevLoc, 1020 PathDiagnosticBuilder &PDB, 1021 LocationContextMap &LCM, 1022 StackDiagVector &CallStack, 1023 InterestingExprs &IE, 1024 bool AddPathEdges) { 1025 ProgramPoint P = N->getLocation(); 1026 const SourceManager& SM = PDB.getSourceManager(); 1027 1028 // Have we encountered an entrance to a call? It may be 1029 // the case that we have not encountered a matching 1030 // call exit before this point. This means that the path 1031 // terminated within the call itself. 1032 if (auto CE = P.getAs<CallEnter>()) { 1033 1034 if (AddPathEdges) { 1035 // Add an edge to the start of the function. 1036 const StackFrameContext *CalleeLC = CE->getCalleeContext(); 1037 const Decl *D = CalleeLC->getDecl(); 1038 // Add the edge only when the callee has body. We jump to the beginning 1039 // of the *declaration*, however we expect it to be followed by the 1040 // body. This isn't the case for autosynthesized property accessors in 1041 // Objective-C. No need for a similar extra check for CallExit points 1042 // because the exit edge comes from a statement (i.e. return), 1043 // not from declaration. 1044 if (D->hasBody()) 1045 addEdgeToPath(PD.getActivePath(), PrevLoc, 1046 PathDiagnosticLocation::createBegin(D, SM), CalleeLC); 1047 } 1048 1049 // Did we visit an entire call? 1050 bool VisitedEntireCall = PD.isWithinCall(); 1051 PD.popActivePath(); 1052 1053 PathDiagnosticCallPiece *C; 1054 if (VisitedEntireCall) { 1055 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front().get()); 1056 } else { 1057 const Decl *Caller = CE->getLocationContext()->getDecl(); 1058 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1059 1060 if (AddPathEdges) { 1061 // Since we just transferred the path over to the call piece, 1062 // reset the mapping from active to location context. 1063 assert(PD.getActivePath().size() == 1 && 1064 PD.getActivePath().front().get() == C); 1065 LCM[&PD.getActivePath()] = nullptr; 1066 } 1067 1068 // Record the location context mapping for the path within 1069 // the call. 1070 assert(LCM[&C->path] == nullptr || 1071 LCM[&C->path] == CE->getCalleeContext()); 1072 LCM[&C->path] = CE->getCalleeContext(); 1073 1074 // If this is the first item in the active path, record 1075 // the new mapping from active path to location context. 1076 const LocationContext *&NewLC = LCM[&PD.getActivePath()]; 1077 if (!NewLC) 1078 NewLC = N->getLocationContext(); 1079 1080 PDB.LC = NewLC; 1081 } 1082 C->setCallee(*CE, SM); 1083 1084 // Update the previous location in the active path. 1085 PrevLoc = C->getLocation(); 1086 1087 if (!CallStack.empty()) { 1088 assert(CallStack.back().first == C); 1089 CallStack.pop_back(); 1090 } 1091 return; 1092 } 1093 1094 1095 if (AddPathEdges) { 1096 // Query the location context here and the previous location 1097 // as processing CallEnter may change the active path. 1098 PDB.LC = N->getLocationContext(); 1099 1100 // Record the mapping from the active path to the location 1101 // context. 1102 assert(!LCM[&PD.getActivePath()] || LCM[&PD.getActivePath()] == PDB.LC); 1103 LCM[&PD.getActivePath()] = PDB.LC; 1104 } 1105 1106 // Have we encountered an exit from a function call? 1107 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 1108 1109 // We are descending into a call (backwards). Construct 1110 // a new call piece to contain the path pieces for that call. 1111 auto C = PathDiagnosticCallPiece::construct(N, *CE, SM); 1112 // Record the mapping from call piece to LocationContext. 1113 LCM[&C->path] = CE->getCalleeContext(); 1114 1115 if (AddPathEdges) { 1116 const Stmt *S = CE->getCalleeContext()->getCallSite(); 1117 // Propagate the interesting symbols accordingly. 1118 if (const auto *Ex = dyn_cast_or_null<Expr>(S)) { 1119 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1120 N->getState().get(), Ex, 1121 N->getLocationContext()); 1122 } 1123 // Add the edge to the return site. 1124 addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); 1125 PrevLoc.invalidate(); 1126 } 1127 1128 auto *P = C.get(); 1129 PD.getActivePath().push_front(std::move(C)); 1130 1131 // Make the contents of the call the active path for now. 1132 PD.pushActivePath(&P->path); 1133 CallStack.push_back(StackDiagPair(P, N)); 1134 return; 1135 } 1136 1137 if (auto PS = P.getAs<PostStmt>()) { 1138 if (!AddPathEdges) 1139 return; 1140 1141 // For expressions, make sure we propagate the 1142 // interesting symbols correctly. 1143 if (const Expr *Ex = PS->getStmtAs<Expr>()) 1144 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1145 N->getState().get(), Ex, 1146 N->getLocationContext()); 1147 1148 // Add an edge. If this is an ObjCForCollectionStmt do 1149 // not add an edge here as it appears in the CFG both 1150 // as a terminator and as a terminator condition. 1151 if (!isa<ObjCForCollectionStmt>(PS->getStmt())) { 1152 PathDiagnosticLocation L = 1153 PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); 1154 addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 1155 } 1156 1157 } else if (auto BE = P.getAs<BlockEdge>()) { 1158 1159 if (!AddPathEdges) { 1160 generateMinimalDiagForBlockEdge(N, *BE, SM, PDB, PD); 1161 return; 1162 } 1163 1164 // Does this represent entering a call? If so, look at propagating 1165 // interesting symbols across call boundaries. 1166 if (const ExplodedNode *NextNode = N->getFirstPred()) { 1167 const LocationContext *CallerCtx = NextNode->getLocationContext(); 1168 const LocationContext *CalleeCtx = PDB.LC; 1169 if (CallerCtx != CalleeCtx && AddPathEdges) { 1170 reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1171 N->getState().get(), 1172 CalleeCtx, CallerCtx); 1173 } 1174 } 1175 1176 // Are we jumping to the head of a loop? Add a special diagnostic. 1177 if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1178 PathDiagnosticLocation L(Loop, SM, PDB.LC); 1179 const Stmt *Body = nullptr; 1180 1181 if (const auto *FS = dyn_cast<ForStmt>(Loop)) 1182 Body = FS->getBody(); 1183 else if (const auto *WS = dyn_cast<WhileStmt>(Loop)) 1184 Body = WS->getBody(); 1185 else if (const auto *OFS = dyn_cast<ObjCForCollectionStmt>(Loop)) { 1186 Body = OFS->getBody(); 1187 } else if (const auto *FRS = dyn_cast<CXXForRangeStmt>(Loop)) { 1188 Body = FRS->getBody(); 1189 } 1190 // do-while statements are explicitly excluded here 1191 1192 auto p = std::make_shared<PathDiagnosticEventPiece>( 1193 L, "Looping back to the head " 1194 "of the loop"); 1195 p->setPrunable(true); 1196 1197 addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 1198 PD.getActivePath().push_front(std::move(p)); 1199 1200 if (const auto *CS = dyn_cast_or_null<CompoundStmt>(Body)) { 1201 addEdgeToPath(PD.getActivePath(), PrevLoc, 1202 PathDiagnosticLocation::createEndBrace(CS, SM), 1203 PDB.LC); 1204 } 1205 } 1206 1207 const CFGBlock *BSrc = BE->getSrc(); 1208 ParentMap &PM = PDB.getParentMap(); 1209 1210 if (const Stmt *Term = BSrc->getTerminator()) { 1211 // Are we jumping past the loop body without ever executing the 1212 // loop (because the condition was false)? 1213 if (isLoop(Term)) { 1214 const Stmt *TermCond = getTerminatorCondition(BSrc); 1215 bool IsInLoopBody = 1216 isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); 1217 1218 const char *str = nullptr; 1219 1220 if (isJumpToFalseBranch(&*BE)) { 1221 if (!IsInLoopBody) { 1222 if (isa<ObjCForCollectionStmt>(Term)) { 1223 str = StrLoopCollectionEmpty; 1224 } else if (isa<CXXForRangeStmt>(Term)) { 1225 str = StrLoopRangeEmpty; 1226 } else { 1227 str = StrLoopBodyZero; 1228 } 1229 } 1230 } else { 1231 str = StrEnteringLoop; 1232 } 1233 1234 if (str) { 1235 PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); 1236 auto PE = std::make_shared<PathDiagnosticEventPiece>(L, str); 1237 PE->setPrunable(true); 1238 addEdgeToPath(PD.getActivePath(), PrevLoc, 1239 PE->getLocation(), PDB.LC); 1240 PD.getActivePath().push_front(std::move(PE)); 1241 } 1242 } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) || 1243 isa<GotoStmt>(Term)) { 1244 PathDiagnosticLocation L(Term, SM, PDB.LC); 1245 addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 1246 } 1247 } 1248 } 1249} 1250 1251static std::unique_ptr<PathDiagnostic> 1252generateEmptyDiagnosticForReport(BugReport *R, SourceManager &SM) { 1253 BugType &BT = R->getBugType(); 1254 return llvm::make_unique<PathDiagnostic>( 1255 R->getBugType().getCheckName(), R->getDeclWithIssue(), 1256 R->getBugType().getName(), R->getDescription(), 1257 R->getShortDescription(/*Fallback=*/false), BT.getCategory(), 1258 R->getUniqueingLocation(), R->getUniqueingDecl(), 1259 findExecutedLines(SM, R->getErrorNode())); 1260} 1261 1262static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) { 1263 if (!S) 1264 return nullptr; 1265 1266 while (true) { 1267 S = PM.getParentIgnoreParens(S); 1268 1269 if (!S) 1270 break; 1271 1272 if (isa<ExprWithCleanups>(S) || 1273 isa<CXXBindTemporaryExpr>(S) || 1274 isa<SubstNonTypeTemplateParmExpr>(S)) 1275 continue; 1276 1277 break; 1278 } 1279 1280 return S; 1281} 1282 1283static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { 1284 switch (S->getStmtClass()) { 1285 case Stmt::BinaryOperatorClass: { 1286 const auto *BO = cast<BinaryOperator>(S); 1287 if (!BO->isLogicalOp()) 1288 return false; 1289 return BO->getLHS() == Cond || BO->getRHS() == Cond; 1290 } 1291 case Stmt::IfStmtClass: 1292 return cast<IfStmt>(S)->getCond() == Cond; 1293 case Stmt::ForStmtClass: 1294 return cast<ForStmt>(S)->getCond() == Cond; 1295 case Stmt::WhileStmtClass: 1296 return cast<WhileStmt>(S)->getCond() == Cond; 1297 case Stmt::DoStmtClass: 1298 return cast<DoStmt>(S)->getCond() == Cond; 1299 case Stmt::ChooseExprClass: 1300 return cast<ChooseExpr>(S)->getCond() == Cond; 1301 case Stmt::IndirectGotoStmtClass: 1302 return cast<IndirectGotoStmt>(S)->getTarget() == Cond; 1303 case Stmt::SwitchStmtClass: 1304 return cast<SwitchStmt>(S)->getCond() == Cond; 1305 case Stmt::BinaryConditionalOperatorClass: 1306 return cast<BinaryConditionalOperator>(S)->getCond() == Cond; 1307 case Stmt::ConditionalOperatorClass: { 1308 const auto *CO = cast<ConditionalOperator>(S); 1309 return CO->getCond() == Cond || 1310 CO->getLHS() == Cond || 1311 CO->getRHS() == Cond; 1312 } 1313 case Stmt::ObjCForCollectionStmtClass: 1314 return cast<ObjCForCollectionStmt>(S)->getElement() == Cond; 1315 case Stmt::CXXForRangeStmtClass: { 1316 const auto *FRS = cast<CXXForRangeStmt>(S); 1317 return FRS->getCond() == Cond || FRS->getRangeInit() == Cond; 1318 } 1319 default: 1320 return false; 1321 } 1322} 1323 1324static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) { 1325 if (const auto *FS = dyn_cast<ForStmt>(FL)) 1326 return FS->getInc() == S || FS->getInit() == S; 1327 if (const auto *FRS = dyn_cast<CXXForRangeStmt>(FL)) 1328 return FRS->getInc() == S || FRS->getRangeStmt() == S || 1329 FRS->getLoopVarStmt() || FRS->getRangeInit() == S; 1330 return false; 1331} 1332 1333using OptimizedCallsSet = llvm::DenseSet<const PathDiagnosticCallPiece *>; 1334 1335/// Adds synthetic edges from top-level statements to their subexpressions. 1336/// 1337/// This avoids a "swoosh" effect, where an edge from a top-level statement A 1338/// points to a sub-expression B.1 that's not at the start of B. In these cases, 1339/// we'd like to see an edge from A to B, then another one from B to B.1. 1340static void addContextEdges(PathPieces &pieces, SourceManager &SM, 1341 const ParentMap &PM, const LocationContext *LCtx) { 1342 PathPieces::iterator Prev = pieces.end(); 1343 for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E; 1344 Prev = I, ++I) { 1345 auto *Piece = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1346 1347 if (!Piece) 1348 continue; 1349 1350 PathDiagnosticLocation SrcLoc = Piece->getStartLocation(); 1351 SmallVector<PathDiagnosticLocation, 4> SrcContexts; 1352 1353 PathDiagnosticLocation NextSrcContext = SrcLoc; 1354 const Stmt *InnerStmt = nullptr; 1355 while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) { 1356 SrcContexts.push_back(NextSrcContext); 1357 InnerStmt = NextSrcContext.asStmt(); 1358 NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx, 1359 /*allowNested=*/true); 1360 } 1361 1362 // Repeatedly split the edge as necessary. 1363 // This is important for nested logical expressions (||, &&, ?:) where we 1364 // want to show all the levels of context. 1365 while (true) { 1366 const Stmt *Dst = Piece->getEndLocation().getStmtOrNull(); 1367 1368 // We are looking at an edge. Is the destination within a larger 1369 // expression? 1370 PathDiagnosticLocation DstContext = 1371 getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true); 1372 if (!DstContext.isValid() || DstContext.asStmt() == Dst) 1373 break; 1374 1375 // If the source is in the same context, we're already good. 1376 if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) != 1377 SrcContexts.end()) 1378 break; 1379 1380 // Update the subexpression node to point to the context edge. 1381 Piece->setStartLocation(DstContext); 1382 1383 // Try to extend the previous edge if it's at the same level as the source 1384 // context. 1385 if (Prev != E) { 1386 auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get()); 1387 1388 if (PrevPiece) { 1389 if (const Stmt *PrevSrc = 1390 PrevPiece->getStartLocation().getStmtOrNull()) { 1391 const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM); 1392 if (PrevSrcParent == 1393 getStmtParent(DstContext.getStmtOrNull(), PM)) { 1394 PrevPiece->setEndLocation(DstContext); 1395 break; 1396 } 1397 } 1398 } 1399 } 1400 1401 // Otherwise, split the current edge into a context edge and a 1402 // subexpression edge. Note that the context statement may itself have 1403 // context. 1404 auto P = 1405 std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext); 1406 Piece = P.get(); 1407 I = pieces.insert(I, std::move(P)); 1408 } 1409 } 1410} 1411 1412/// Move edges from a branch condition to a branch target 1413/// when the condition is simple. 1414/// 1415/// This restructures some of the work of addContextEdges. That function 1416/// creates edges this may destroy, but they work together to create a more 1417/// aesthetically set of edges around branches. After the call to 1418/// addContextEdges, we may have (1) an edge to the branch, (2) an edge from 1419/// the branch to the branch condition, and (3) an edge from the branch 1420/// condition to the branch target. We keep (1), but may wish to remove (2) 1421/// and move the source of (3) to the branch if the branch condition is simple. 1422static void simplifySimpleBranches(PathPieces &pieces) { 1423 for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) { 1424 const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1425 1426 if (!PieceI) 1427 continue; 1428 1429 const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull(); 1430 const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull(); 1431 1432 if (!s1Start || !s1End) 1433 continue; 1434 1435 PathPieces::iterator NextI = I; ++NextI; 1436 if (NextI == E) 1437 break; 1438 1439 PathDiagnosticControlFlowPiece *PieceNextI = nullptr; 1440 1441 while (true) { 1442 if (NextI == E) 1443 break; 1444 1445 const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get()); 1446 if (EV) { 1447 StringRef S = EV->getString(); 1448 if (S == StrEnteringLoop || S == StrLoopBodyZero || 1449 S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) { 1450 ++NextI; 1451 continue; 1452 } 1453 break; 1454 } 1455 1456 PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1457 break; 1458 } 1459 1460 if (!PieceNextI) 1461 continue; 1462 1463 const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull(); 1464 const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull(); 1465 1466 if (!s2Start || !s2End || s1End != s2Start) 1467 continue; 1468 1469 // We only perform this transformation for specific branch kinds. 1470 // We don't want to do this for do..while, for example. 1471 if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) || 1472 isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) || 1473 isa<CXXForRangeStmt>(s1Start))) 1474 continue; 1475 1476 // Is s1End the branch condition? 1477 if (!isConditionForTerminator(s1Start, s1End)) 1478 continue; 1479 1480 // Perform the hoisting by eliminating (2) and changing the start 1481 // location of (3). 1482 PieceNextI->setStartLocation(PieceI->getStartLocation()); 1483 I = pieces.erase(I); 1484 } 1485} 1486 1487/// Returns the number of bytes in the given (character-based) SourceRange. 1488/// 1489/// If the locations in the range are not on the same line, returns None. 1490/// 1491/// Note that this does not do a precise user-visible character or column count. 1492static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 1493 SourceRange Range) { 1494 SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()), 1495 SM.getExpansionRange(Range.getEnd()).getEnd()); 1496 1497 FileID FID = SM.getFileID(ExpansionRange.getBegin()); 1498 if (FID != SM.getFileID(ExpansionRange.getEnd())) 1499 return None; 1500 1501 bool Invalid; 1502 const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid); 1503 if (Invalid) 1504 return None; 1505 1506 unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin()); 1507 unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd()); 1508 StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset); 1509 1510 // We're searching the raw bytes of the buffer here, which might include 1511 // escaped newlines and such. That's okay; we're trying to decide whether the 1512 // SourceRange is covering a large or small amount of space in the user's 1513 // editor. 1514 if (Snippet.find_first_of("\r\n") != StringRef::npos) 1515 return None; 1516 1517 // This isn't Unicode-aware, but it doesn't need to be. 1518 return Snippet.size(); 1519} 1520 1521/// \sa getLengthOnSingleLine(SourceManager, SourceRange) 1522static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 1523 const Stmt *S) { 1524 return getLengthOnSingleLine(SM, S->getSourceRange()); 1525} 1526 1527/// Eliminate two-edge cycles created by addContextEdges(). 1528/// 1529/// Once all the context edges are in place, there are plenty of cases where 1530/// there's a single edge from a top-level statement to a subexpression, 1531/// followed by a single path note, and then a reverse edge to get back out to 1532/// the top level. If the statement is simple enough, the subexpression edges 1533/// just add noise and make it harder to understand what's going on. 1534/// 1535/// This function only removes edges in pairs, because removing only one edge 1536/// might leave other edges dangling. 1537/// 1538/// This will not remove edges in more complicated situations: 1539/// - if there is more than one "hop" leading to or from a subexpression. 1540/// - if there is an inlined call between the edges instead of a single event. 1541/// - if the whole statement is large enough that having subexpression arrows 1542/// might be helpful. 1543static void removeContextCycles(PathPieces &Path, SourceManager &SM, 1544 ParentMap &PM) { 1545 for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) { 1546 // Pattern match the current piece and its successor. 1547 const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1548 1549 if (!PieceI) { 1550 ++I; 1551 continue; 1552 } 1553 1554 const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull(); 1555 const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull(); 1556 1557 PathPieces::iterator NextI = I; ++NextI; 1558 if (NextI == E) 1559 break; 1560 1561 const auto *PieceNextI = 1562 dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1563 1564 if (!PieceNextI) { 1565 if (isa<PathDiagnosticEventPiece>(NextI->get())) { 1566 ++NextI; 1567 if (NextI == E) 1568 break; 1569 PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1570 } 1571 1572 if (!PieceNextI) { 1573 ++I; 1574 continue; 1575 } 1576 } 1577 1578 const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull(); 1579 const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull(); 1580 1581 if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) { 1582 const size_t MAX_SHORT_LINE_LENGTH = 80; 1583 Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start); 1584 if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) { 1585 Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start); 1586 if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) { 1587 Path.erase(I); 1588 I = Path.erase(NextI); 1589 continue; 1590 } 1591 } 1592 } 1593 1594 ++I; 1595 } 1596} 1597 1598/// Return true if X is contained by Y. 1599static bool lexicalContains(ParentMap &PM, const Stmt *X, const Stmt *Y) { 1600 while (X) { 1601 if (X == Y) 1602 return true; 1603 X = PM.getParent(X); 1604 } 1605 return false; 1606} 1607 1608// Remove short edges on the same line less than 3 columns in difference. 1609static void removePunyEdges(PathPieces &path, SourceManager &SM, 1610 ParentMap &PM) { 1611 bool erased = false; 1612 1613 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; 1614 erased ? I : ++I) { 1615 erased = false; 1616 1617 const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1618 1619 if (!PieceI) 1620 continue; 1621 1622 const Stmt *start = PieceI->getStartLocation().getStmtOrNull(); 1623 const Stmt *end = PieceI->getEndLocation().getStmtOrNull(); 1624 1625 if (!start || !end) 1626 continue; 1627 1628 const Stmt *endParent = PM.getParent(end); 1629 if (!endParent) 1630 continue; 1631 1632 if (isConditionForTerminator(end, endParent)) 1633 continue; 1634 1635 SourceLocation FirstLoc = start->getLocStart(); 1636 SourceLocation SecondLoc = end->getLocStart(); 1637 1638 if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc)) 1639 continue; 1640 if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc)) 1641 std::swap(SecondLoc, FirstLoc); 1642 1643 SourceRange EdgeRange(FirstLoc, SecondLoc); 1644 Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange); 1645 1646 // If the statements are on different lines, continue. 1647 if (!ByteWidth) 1648 continue; 1649 1650 const size_t MAX_PUNY_EDGE_LENGTH = 2; 1651 if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) { 1652 // FIXME: There are enough /bytes/ between the endpoints of the edge, but 1653 // there might not be enough /columns/. A proper user-visible column count 1654 // is probably too expensive, though. 1655 I = path.erase(I); 1656 erased = true; 1657 continue; 1658 } 1659 } 1660} 1661 1662static void removeIdenticalEvents(PathPieces &path) { 1663 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) { 1664 const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get()); 1665 1666 if (!PieceI) 1667 continue; 1668 1669 PathPieces::iterator NextI = I; ++NextI; 1670 if (NextI == E) 1671 return; 1672 1673 const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get()); 1674 1675 if (!PieceNextI) 1676 continue; 1677 1678 // Erase the second piece if it has the same exact message text. 1679 if (PieceI->getString() == PieceNextI->getString()) { 1680 path.erase(NextI); 1681 } 1682 } 1683} 1684 1685static bool optimizeEdges(PathPieces &path, SourceManager &SM, 1686 OptimizedCallsSet &OCS, 1687 LocationContextMap &LCM) { 1688 bool hasChanges = false; 1689 const LocationContext *LC = LCM[&path]; 1690 assert(LC); 1691 ParentMap &PM = LC->getParentMap(); 1692 1693 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) { 1694 // Optimize subpaths. 1695 if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) { 1696 // Record the fact that a call has been optimized so we only do the 1697 // effort once. 1698 if (!OCS.count(CallI)) { 1699 while (optimizeEdges(CallI->path, SM, OCS, LCM)) {} 1700 OCS.insert(CallI); 1701 } 1702 ++I; 1703 continue; 1704 } 1705 1706 // Pattern match the current piece and its successor. 1707 auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1708 1709 if (!PieceI) { 1710 ++I; 1711 continue; 1712 } 1713 1714 const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull(); 1715 const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull(); 1716 const Stmt *level1 = getStmtParent(s1Start, PM); 1717 const Stmt *level2 = getStmtParent(s1End, PM); 1718 1719 PathPieces::iterator NextI = I; ++NextI; 1720 if (NextI == E) 1721 break; 1722 1723 const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1724 1725 if (!PieceNextI) { 1726 ++I; 1727 continue; 1728 } 1729 1730 const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull(); 1731 const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull(); 1732 const Stmt *level3 = getStmtParent(s2Start, PM); 1733 const Stmt *level4 = getStmtParent(s2End, PM); 1734 1735 // Rule I. 1736 // 1737 // If we have two consecutive control edges whose end/begin locations 1738 // are at the same level (e.g. statements or top-level expressions within 1739 // a compound statement, or siblings share a single ancestor expression), 1740 // then merge them if they have no interesting intermediate event. 1741 // 1742 // For example: 1743 // 1744 // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common 1745 // parent is '1'. Here 'x.y.z' represents the hierarchy of statements. 1746 // 1747 // NOTE: this will be limited later in cases where we add barriers 1748 // to prevent this optimization. 1749 if (level1 && level1 == level2 && level1 == level3 && level1 == level4) { 1750 PieceI->setEndLocation(PieceNextI->getEndLocation()); 1751 path.erase(NextI); 1752 hasChanges = true; 1753 continue; 1754 } 1755 1756 // Rule II. 1757 // 1758 // Eliminate edges between subexpressions and parent expressions 1759 // when the subexpression is consumed. 1760 // 1761 // NOTE: this will be limited later in cases where we add barriers 1762 // to prevent this optimization. 1763 if (s1End && s1End == s2Start && level2) { 1764 bool removeEdge = false; 1765 // Remove edges into the increment or initialization of a 1766 // loop that have no interleaving event. This means that 1767 // they aren't interesting. 1768 if (isIncrementOrInitInForLoop(s1End, level2)) 1769 removeEdge = true; 1770 // Next only consider edges that are not anchored on 1771 // the condition of a terminator. This are intermediate edges 1772 // that we might want to trim. 1773 else if (!isConditionForTerminator(level2, s1End)) { 1774 // Trim edges on expressions that are consumed by 1775 // the parent expression. 1776 if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) { 1777 removeEdge = true; 1778 } 1779 // Trim edges where a lexical containment doesn't exist. 1780 // For example: 1781 // 1782 // X -> Y -> Z 1783 // 1784 // If 'Z' lexically contains Y (it is an ancestor) and 1785 // 'X' does not lexically contain Y (it is a descendant OR 1786 // it has no lexical relationship at all) then trim. 1787 // 1788 // This can eliminate edges where we dive into a subexpression 1789 // and then pop back out, etc. 1790 else if (s1Start && s2End && 1791 lexicalContains(PM, s2Start, s2End) && 1792 !lexicalContains(PM, s1End, s1Start)) { 1793 removeEdge = true; 1794 } 1795 // Trim edges from a subexpression back to the top level if the 1796 // subexpression is on a different line. 1797 // 1798 // A.1 -> A -> B 1799 // becomes 1800 // A.1 -> B 1801 // 1802 // These edges just look ugly and don't usually add anything. 1803 else if (s1Start && s2End && 1804 lexicalContains(PM, s1Start, s1End)) { 1805 SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), 1806 PieceI->getStartLocation().asLocation()); 1807 if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) 1808 removeEdge = true; 1809 } 1810 } 1811 1812 if (removeEdge) { 1813 PieceI->setEndLocation(PieceNextI->getEndLocation()); 1814 path.erase(NextI); 1815 hasChanges = true; 1816 continue; 1817 } 1818 } 1819 1820 // Optimize edges for ObjC fast-enumeration loops. 1821 // 1822 // (X -> collection) -> (collection -> element) 1823 // 1824 // becomes: 1825 // 1826 // (X -> element) 1827 if (s1End == s2Start) { 1828 const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3); 1829 if (FS && FS->getCollection()->IgnoreParens() == s2Start && 1830 s2End == FS->getElement()) { 1831 PieceI->setEndLocation(PieceNextI->getEndLocation()); 1832 path.erase(NextI); 1833 hasChanges = true; 1834 continue; 1835 } 1836 } 1837 1838 // No changes at this index? Move to the next one. 1839 ++I; 1840 } 1841 1842 if (!hasChanges) { 1843 // Adjust edges into subexpressions to make them more uniform 1844 // and aesthetically pleasing. 1845 addContextEdges(path, SM, PM, LC); 1846 // Remove "cyclical" edges that include one or more context edges. 1847 removeContextCycles(path, SM, PM); 1848 // Hoist edges originating from branch conditions to branches 1849 // for simple branches. 1850 simplifySimpleBranches(path); 1851 // Remove any puny edges left over after primary optimization pass. 1852 removePunyEdges(path, SM, PM); 1853 // Remove identical events. 1854 removeIdenticalEvents(path); 1855 } 1856 1857 return hasChanges; 1858} 1859 1860/// Drop the very first edge in a path, which should be a function entry edge. 1861/// 1862/// If the first edge is not a function entry edge (say, because the first 1863/// statement had an invalid source location), this function does nothing. 1864// FIXME: We should just generate invalid edges anyway and have the optimizer 1865// deal with them. 1866static void dropFunctionEntryEdge(PathPieces &Path, LocationContextMap &LCM, 1867 SourceManager &SM) { 1868 const auto *FirstEdge = 1869 dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get()); 1870 if (!FirstEdge) 1871 return; 1872 1873 const Decl *D = LCM[&Path]->getDecl(); 1874 PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM); 1875 if (FirstEdge->getStartLocation() != EntryLoc) 1876 return; 1877 1878 Path.pop_front(); 1879} 1880 1881using VisitorsDiagnosticsTy = llvm::DenseMap<const ExplodedNode *, 1882 std::vector<std::shared_ptr<PathDiagnosticPiece>>>; 1883 1884/// This function is responsible for generating diagnostic pieces that are 1885/// *not* provided by bug report visitors. 1886/// These diagnostics may differ depending on the consumer's settings, 1887/// and are therefore constructed separately for each consumer. 1888/// 1889/// There are two path diagnostics generation modes: with adding edges (used 1890/// for plists) and without (used for HTML and text). 1891/// When edges are added (\p ActiveScheme is Extensive), 1892/// the path is modified to insert artificially generated 1893/// edges. 1894/// Otherwise, more detailed diagnostics is emitted for block edges, explaining 1895/// the transitions in words. 1896static std::unique_ptr<PathDiagnostic> generatePathDiagnosticForConsumer( 1897 PathDiagnosticConsumer::PathGenerationScheme ActiveScheme, 1898 PathDiagnosticBuilder &PDB, 1899 const ExplodedNode *ErrorNode, 1900 const VisitorsDiagnosticsTy &VisitorsDiagnostics) { 1901 1902 bool GenerateDiagnostics = (ActiveScheme != PathDiagnosticConsumer::None); 1903 bool AddPathEdges = (ActiveScheme == PathDiagnosticConsumer::Extensive); 1904 SourceManager &SM = PDB.getSourceManager(); 1905 BugReport *R = PDB.getBugReport(); 1906 AnalyzerOptions &Opts = PDB.getBugReporter().getAnalyzerOptions(); 1907 StackDiagVector CallStack; 1908 InterestingExprs IE; 1909 LocationContextMap LCM; 1910 std::unique_ptr<PathDiagnostic> PD = generateEmptyDiagnosticForReport(R, SM); 1911 1912 if (GenerateDiagnostics) { 1913 auto EndNotes = VisitorsDiagnostics.find(ErrorNode); 1914 std::shared_ptr<PathDiagnosticPiece> LastPiece; 1915 if (EndNotes != VisitorsDiagnostics.end()) { 1916 assert(!EndNotes->second.empty()); 1917 LastPiece = EndNotes->second[0]; 1918 } else { 1919 LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, ErrorNode, *R); 1920 } 1921 PD->setEndOfPath(LastPiece); 1922 } 1923 1924 PathDiagnosticLocation PrevLoc = PD->getLocation(); 1925 const ExplodedNode *NextNode = ErrorNode->getFirstPred(); 1926 while (NextNode) { 1927 if (GenerateDiagnostics) 1928 generatePathDiagnosticsForNode( 1929 NextNode, *PD, PrevLoc, PDB, LCM, CallStack, IE, AddPathEdges); 1930 1931 auto VisitorNotes = VisitorsDiagnostics.find(NextNode); 1932 NextNode = NextNode->getFirstPred(); 1933 if (!GenerateDiagnostics || VisitorNotes == VisitorsDiagnostics.end()) 1934 continue; 1935 1936 // This is a workaround due to inability to put shared PathDiagnosticPiece 1937 // into a FoldingSet. 1938 std::set<llvm::FoldingSetNodeID> DeduplicationSet; 1939 1940 // Add pieces from custom visitors. 1941 for (const auto &Note : VisitorNotes->second) { 1942 llvm::FoldingSetNodeID ID; 1943 Note->Profile(ID); 1944 auto P = DeduplicationSet.insert(ID); 1945 if (!P.second) 1946 continue; 1947 1948 if (AddPathEdges) 1949 addEdgeToPath(PD->getActivePath(), PrevLoc, Note->getLocation(), 1950 PDB.LC); 1951 updateStackPiecesWithMessage(*Note, CallStack); 1952 PD->getActivePath().push_front(Note); 1953 } 1954 } 1955 1956 if (AddPathEdges) { 1957 // Add an edge to the start of the function. 1958 // We'll prune it out later, but it helps make diagnostics more uniform. 1959 const StackFrameContext *CalleeLC = PDB.LC->getStackFrame(); 1960 const Decl *D = CalleeLC->getDecl(); 1961 addEdgeToPath(PD->getActivePath(), PrevLoc, 1962 PathDiagnosticLocation::createBegin(D, SM), CalleeLC); 1963 } 1964 1965 if (!AddPathEdges && GenerateDiagnostics) 1966 CompactPathDiagnostic(PD->getMutablePieces(), SM); 1967 1968 // Finally, prune the diagnostic path of uninteresting stuff. 1969 if (!PD->path.empty()) { 1970 if (R->shouldPrunePath() && Opts.shouldPrunePaths()) { 1971 bool stillHasNotes = 1972 removeUnneededCalls(PD->getMutablePieces(), R, LCM); 1973 assert(stillHasNotes); 1974 (void)stillHasNotes; 1975 } 1976 1977 // Redirect all call pieces to have valid locations. 1978 adjustCallLocations(PD->getMutablePieces()); 1979 removePiecesWithInvalidLocations(PD->getMutablePieces()); 1980 1981 if (AddPathEdges) { 1982 1983 // Reduce the number of edges from a very conservative set 1984 // to an aesthetically pleasing subset that conveys the 1985 // necessary information. 1986 OptimizedCallsSet OCS; 1987 while (optimizeEdges(PD->getMutablePieces(), SM, OCS, LCM)) {} 1988 1989 // Drop the very first function-entry edge. It's not really necessary 1990 // for top-level functions. 1991 dropFunctionEntryEdge(PD->getMutablePieces(), LCM, SM); 1992 } 1993 1994 // Remove messages that are basically the same, and edges that may not 1995 // make sense. 1996 // We have to do this after edge optimization in the Extensive mode. 1997 removeRedundantMsgs(PD->getMutablePieces()); 1998 removeEdgesToDefaultInitializers(PD->getMutablePieces()); 1999 } 2000 return PD; 2001} 2002 2003 2004//===----------------------------------------------------------------------===// 2005// Methods for BugType and subclasses. 2006//===----------------------------------------------------------------------===// 2007 2008void BugType::anchor() {} 2009 2010void BugType::FlushReports(BugReporter &BR) {} 2011 2012void BuiltinBug::anchor() {} 2013 2014//===----------------------------------------------------------------------===// 2015// Methods for BugReport and subclasses. 2016//===----------------------------------------------------------------------===// 2017 2018void BugReport::NodeResolver::anchor() {} 2019 2020void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) { 2021 if (!visitor) 2022 return; 2023 2024 llvm::FoldingSetNodeID ID; 2025 visitor->Profile(ID); 2026 2027 void *InsertPos = nullptr; 2028 if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 2029 return; 2030 } 2031 2032 Callbacks.push_back(std::move(visitor)); 2033} 2034 2035void BugReport::clearVisitors() { 2036 Callbacks.clear(); 2037} 2038 2039BugReport::~BugReport() { 2040 while (!interestingSymbols.empty()) { 2041 popInterestingSymbolsAndRegions(); 2042 } 2043} 2044 2045const Decl *BugReport::getDeclWithIssue() const { 2046 if (DeclWithIssue) 2047 return DeclWithIssue; 2048 2049 const ExplodedNode *N = getErrorNode(); 2050 if (!N) 2051 return nullptr; 2052 2053 const LocationContext *LC = N->getLocationContext(); 2054 return LC->getStackFrame()->getDecl(); 2055} 2056 2057void BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 2058 hash.AddPointer(&BT); 2059 hash.AddString(Description); 2060 PathDiagnosticLocation UL = getUniqueingLocation(); 2061 if (UL.isValid()) { 2062 UL.Profile(hash); 2063 } else if (Location.isValid()) { 2064 Location.Profile(hash); 2065 } else { 2066 assert(ErrorNode); 2067 hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode)); 2068 } 2069 2070 for (SourceRange range : Ranges) { 2071 if (!range.isValid()) 2072 continue; 2073 hash.AddInteger(range.getBegin().getRawEncoding()); 2074 hash.AddInteger(range.getEnd().getRawEncoding()); 2075 } 2076} 2077 2078void BugReport::markInteresting(SymbolRef sym) { 2079 if (!sym) 2080 return; 2081 2082 getInterestingSymbols().insert(sym); 2083 2084 if (const auto *meta = dyn_cast<SymbolMetadata>(sym)) 2085 getInterestingRegions().insert(meta->getRegion()); 2086} 2087 2088void BugReport::markInteresting(const MemRegion *R) { 2089 if (!R) 2090 return; 2091 2092 R = R->getBaseRegion(); 2093 getInterestingRegions().insert(R); 2094 2095 if (const auto *SR = dyn_cast<SymbolicRegion>(R)) 2096 getInterestingSymbols().insert(SR->getSymbol()); 2097} 2098 2099void BugReport::markInteresting(SVal V) { 2100 markInteresting(V.getAsRegion()); 2101 markInteresting(V.getAsSymbol()); 2102} 2103 2104void BugReport::markInteresting(const LocationContext *LC) { 2105 if (!LC) 2106 return; 2107 InterestingLocationContexts.insert(LC); 2108} 2109 2110bool BugReport::isInteresting(SVal V) { 2111 return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); 2112} 2113 2114bool BugReport::isInteresting(SymbolRef sym) { 2115 if (!sym) 2116 return false; 2117 // We don't currently consider metadata symbols to be interesting 2118 // even if we know their region is interesting. Is that correct behavior? 2119 return getInterestingSymbols().count(sym); 2120} 2121 2122bool BugReport::isInteresting(const MemRegion *R) { 2123 if (!R) 2124 return false; 2125 R = R->getBaseRegion(); 2126 bool b = getInterestingRegions().count(R); 2127 if (b) 2128 return true; 2129 if (const auto *SR = dyn_cast<SymbolicRegion>(R)) 2130 return getInterestingSymbols().count(SR->getSymbol()); 2131 return false; 2132} 2133 2134bool BugReport::isInteresting(const LocationContext *LC) { 2135 if (!LC) 2136 return false; 2137 return InterestingLocationContexts.count(LC); 2138} 2139 2140void BugReport::lazyInitializeInterestingSets() { 2141 if (interestingSymbols.empty()) { 2142 interestingSymbols.push_back(new Symbols()); 2143 interestingRegions.push_back(new Regions()); 2144 } 2145} 2146 2147BugReport::Symbols &BugReport::getInterestingSymbols() { 2148 lazyInitializeInterestingSets(); 2149 return *interestingSymbols.back(); 2150} 2151 2152BugReport::Regions &BugReport::getInterestingRegions() { 2153 lazyInitializeInterestingSets(); 2154 return *interestingRegions.back(); 2155} 2156 2157void BugReport::pushInterestingSymbolsAndRegions() { 2158 interestingSymbols.push_back(new Symbols(getInterestingSymbols())); 2159 interestingRegions.push_back(new Regions(getInterestingRegions())); 2160} 2161 2162void BugReport::popInterestingSymbolsAndRegions() { 2163 delete interestingSymbols.pop_back_val(); 2164 delete interestingRegions.pop_back_val(); 2165} 2166 2167const Stmt *BugReport::getStmt() const { 2168 if (!ErrorNode) 2169 return nullptr; 2170 2171 ProgramPoint ProgP = ErrorNode->getLocation(); 2172 const Stmt *S = nullptr; 2173 2174 if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) { 2175 CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 2176 if (BE->getBlock() == &Exit) 2177 S = GetPreviousStmt(ErrorNode); 2178 } 2179 if (!S) 2180 S = PathDiagnosticLocation::getStmt(ErrorNode); 2181 2182 return S; 2183} 2184 2185llvm::iterator_range<BugReport::ranges_iterator> BugReport::getRanges() { 2186 // If no custom ranges, add the range of the statement corresponding to 2187 // the error node. 2188 if (Ranges.empty()) { 2189 if (const auto *E = dyn_cast_or_null<Expr>(getStmt())) 2190 addRange(E->getSourceRange()); 2191 else 2192 return llvm::make_range(ranges_iterator(), ranges_iterator()); 2193 } 2194 2195 // User-specified absence of range info. 2196 if (Ranges.size() == 1 && !Ranges.begin()->isValid()) 2197 return llvm::make_range(ranges_iterator(), ranges_iterator()); 2198 2199 return llvm::make_range(Ranges.begin(), Ranges.end()); 2200} 2201 2202PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const { 2203 if (ErrorNode) { 2204 assert(!Location.isValid() && 2205 "Either Location or ErrorNode should be specified but not both."); 2206 return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM); 2207 } 2208 2209 assert(Location.isValid()); 2210 return Location; 2211} 2212 2213//===----------------------------------------------------------------------===// 2214// Methods for BugReporter and subclasses. 2215//===----------------------------------------------------------------------===// 2216 2217BugReportEquivClass::~BugReportEquivClass() = default; 2218 2219GRBugReporter::~GRBugReporter() = default; 2220 2221BugReporterData::~BugReporterData() = default; 2222 2223ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 2224 2225ProgramStateManager& 2226GRBugReporter::getStateManager() { return Eng.getStateManager(); } 2227 2228BugReporter::~BugReporter() { 2229 FlushReports(); 2230 2231 // Free the bug reports we are tracking. 2232 for (const auto I : EQClassesVector) 2233 delete I; 2234} 2235 2236void BugReporter::FlushReports() { 2237 if (BugTypes.isEmpty()) 2238 return; 2239 2240 // First flush the warnings for each BugType. This may end up creating new 2241 // warnings and new BugTypes. 2242 // FIXME: Only NSErrorChecker needs BugType's FlushReports. 2243 // Turn NSErrorChecker into a proper checker and remove this. 2244 SmallVector<const BugType *, 16> bugTypes(BugTypes.begin(), BugTypes.end()); 2245 for (const auto I : bugTypes) 2246 const_cast<BugType*>(I)->FlushReports(*this); 2247 2248 // We need to flush reports in deterministic order to ensure the order 2249 // of the reports is consistent between runs. 2250 for (const auto EQ : EQClassesVector) 2251 FlushReport(*EQ); 2252 2253 // BugReporter owns and deletes only BugTypes created implicitly through 2254 // EmitBasicReport. 2255 // FIXME: There are leaks from checkers that assume that the BugTypes they 2256 // create will be destroyed by the BugReporter. 2257 llvm::DeleteContainerSeconds(StrBugTypes); 2258 2259 // Remove all references to the BugType objects. 2260 BugTypes = F.getEmptySet(); 2261} 2262 2263//===----------------------------------------------------------------------===// 2264// PathDiagnostics generation. 2265//===----------------------------------------------------------------------===// 2266 2267namespace { 2268 2269/// A wrapper around a report graph, which contains only a single path, and its 2270/// node maps. 2271class ReportGraph { 2272public: 2273 InterExplodedGraphMap BackMap; 2274 std::unique_ptr<ExplodedGraph> Graph; 2275 const ExplodedNode *ErrorNode; 2276 size_t Index; 2277}; 2278 2279/// A wrapper around a trimmed graph and its node maps. 2280class TrimmedGraph { 2281 InterExplodedGraphMap InverseMap; 2282 2283 using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>; 2284 2285 PriorityMapTy PriorityMap; 2286 2287 using NodeIndexPair = std::pair<const ExplodedNode *, size_t>; 2288 2289 SmallVector<NodeIndexPair, 32> ReportNodes; 2290 2291 std::unique_ptr<ExplodedGraph> G; 2292 2293 /// A helper class for sorting ExplodedNodes by priority. 2294 template <bool Descending> 2295 class PriorityCompare { 2296 const PriorityMapTy &PriorityMap; 2297 2298 public: 2299 PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {} 2300 2301 bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const { 2302 PriorityMapTy::const_iterator LI = PriorityMap.find(LHS); 2303 PriorityMapTy::const_iterator RI = PriorityMap.find(RHS); 2304 PriorityMapTy::const_iterator E = PriorityMap.end(); 2305 2306 if (LI == E) 2307 return Descending; 2308 if (RI == E) 2309 return !Descending; 2310 2311 return Descending ? LI->second > RI->second 2312 : LI->second < RI->second; 2313 } 2314 2315 bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const { 2316 return (*this)(LHS.first, RHS.first); 2317 } 2318 }; 2319 2320public: 2321 TrimmedGraph(const ExplodedGraph *OriginalGraph, 2322 ArrayRef<const ExplodedNode *> Nodes); 2323 2324 bool popNextReportGraph(ReportGraph &GraphWrapper); 2325}; 2326 2327} // namespace 2328 2329TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph, 2330 ArrayRef<const ExplodedNode *> Nodes) { 2331 // The trimmed graph is created in the body of the constructor to ensure 2332 // that the DenseMaps have been initialized already. 2333 InterExplodedGraphMap ForwardMap; 2334 G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap); 2335 2336 // Find the (first) error node in the trimmed graph. We just need to consult 2337 // the node map which maps from nodes in the original graph to nodes 2338 // in the new graph. 2339 llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes; 2340 2341 for (unsigned i = 0, count = Nodes.size(); i < count; ++i) { 2342 if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) { 2343 ReportNodes.push_back(std::make_pair(NewNode, i)); 2344 RemainingNodes.insert(NewNode); 2345 } 2346 } 2347 2348 assert(!RemainingNodes.empty() && "No error node found in the trimmed graph"); 2349 2350 // Perform a forward BFS to find all the shortest paths. 2351 std::queue<const ExplodedNode *> WS; 2352 2353 assert(G->num_roots() == 1); 2354 WS.push(*G->roots_begin()); 2355 unsigned Priority = 0; 2356 2357 while (!WS.empty()) { 2358 const ExplodedNode *Node = WS.front(); 2359 WS.pop(); 2360 2361 PriorityMapTy::iterator PriorityEntry; 2362 bool IsNew; 2363 std::tie(PriorityEntry, IsNew) = 2364 PriorityMap.insert(std::make_pair(Node, Priority)); 2365 ++Priority; 2366 2367 if (!IsNew) { 2368 assert(PriorityEntry->second <= Priority); 2369 continue; 2370 } 2371 2372 if (RemainingNodes.erase(Node)) 2373 if (RemainingNodes.empty()) 2374 break; 2375 2376 for (ExplodedNode::const_pred_iterator I = Node->succ_begin(), 2377 E = Node->succ_end(); 2378 I != E; ++I) 2379 WS.push(*I); 2380 } 2381 2382 // Sort the error paths from longest to shortest. 2383 llvm::sort(ReportNodes.begin(), ReportNodes.end(), 2384 PriorityCompare<true>(PriorityMap)); 2385} 2386 2387bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) { 2388 if (ReportNodes.empty()) 2389 return false; 2390 2391 const ExplodedNode *OrigN; 2392 std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val(); 2393 assert(PriorityMap.find(OrigN) != PriorityMap.end() && 2394 "error node not accessible from root"); 2395 2396 // Create a new graph with a single path. This is the graph 2397 // that will be returned to the caller. 2398 auto GNew = llvm::make_unique<ExplodedGraph>(); 2399 GraphWrapper.BackMap.clear(); 2400 2401 // Now walk from the error node up the BFS path, always taking the 2402 // predeccessor with the lowest number. 2403 ExplodedNode *Succ = nullptr; 2404 while (true) { 2405 // Create the equivalent node in the new graph with the same state 2406 // and location. 2407 ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(), 2408 OrigN->isSink()); 2409 2410 // Store the mapping to the original node. 2411 InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN); 2412 assert(IMitr != InverseMap.end() && "No mapping to original node."); 2413 GraphWrapper.BackMap[NewN] = IMitr->second; 2414 2415 // Link up the new node with the previous node. 2416 if (Succ) 2417 Succ->addPredecessor(NewN, *GNew); 2418 else 2419 GraphWrapper.ErrorNode = NewN; 2420 2421 Succ = NewN; 2422 2423 // Are we at the final node? 2424 if (OrigN->pred_empty()) { 2425 GNew->addRoot(NewN); 2426 break; 2427 } 2428 2429 // Find the next predeccessor node. We choose the node that is marked 2430 // with the lowest BFS number. 2431 OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(), 2432 PriorityCompare<false>(PriorityMap)); 2433 } 2434 2435 GraphWrapper.Graph = std::move(GNew); 2436 2437 return true; 2438} 2439 2440/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 2441/// and collapses PathDiagosticPieces that are expanded by macros. 2442static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { 2443 using MacroStackTy = 2444 std::vector< 2445 std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>; 2446 2447 using PiecesTy = std::vector<std::shared_ptr<PathDiagnosticPiece>>; 2448 2449 MacroStackTy MacroStack; 2450 PiecesTy Pieces; 2451 2452 for (PathPieces::const_iterator I = path.begin(), E = path.end(); 2453 I != E; ++I) { 2454 const auto &piece = *I; 2455 2456 // Recursively compact calls. 2457 if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) { 2458 CompactPathDiagnostic(call->path, SM); 2459 } 2460 2461 // Get the location of the PathDiagnosticPiece. 2462 const FullSourceLoc Loc = piece->getLocation().asLocation(); 2463 2464 // Determine the instantiation location, which is the location we group 2465 // related PathDiagnosticPieces. 2466 SourceLocation InstantiationLoc = Loc.isMacroID() ? 2467 SM.getExpansionLoc(Loc) : 2468 SourceLocation(); 2469 2470 if (Loc.isFileID()) { 2471 MacroStack.clear(); 2472 Pieces.push_back(piece); 2473 continue; 2474 } 2475 2476 assert(Loc.isMacroID()); 2477 2478 // Is the PathDiagnosticPiece within the same macro group? 2479 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 2480 MacroStack.back().first->subPieces.push_back(piece); 2481 continue; 2482 } 2483 2484 // We aren't in the same group. Are we descending into a new macro 2485 // or are part of an old one? 2486 std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup; 2487 2488 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 2489 SM.getExpansionLoc(Loc) : 2490 SourceLocation(); 2491 2492 // Walk the entire macro stack. 2493 while (!MacroStack.empty()) { 2494 if (InstantiationLoc == MacroStack.back().second) { 2495 MacroGroup = MacroStack.back().first; 2496 break; 2497 } 2498 2499 if (ParentInstantiationLoc == MacroStack.back().second) { 2500 MacroGroup = MacroStack.back().first; 2501 break; 2502 } 2503 2504 MacroStack.pop_back(); 2505 } 2506 2507 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 2508 // Create a new macro group and add it to the stack. 2509 auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>( 2510 PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 2511 2512 if (MacroGroup) 2513 MacroGroup->subPieces.push_back(NewGroup); 2514 else { 2515 assert(InstantiationLoc.isFileID()); 2516 Pieces.push_back(NewGroup); 2517 } 2518 2519 MacroGroup = NewGroup; 2520 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 2521 } 2522 2523 // Finally, add the PathDiagnosticPiece to the group. 2524 MacroGroup->subPieces.push_back(piece); 2525 } 2526 2527 // Now take the pieces and construct a new PathDiagnostic. 2528 path.clear(); 2529 2530 path.insert(path.end(), Pieces.begin(), Pieces.end()); 2531} 2532 2533/// Generate notes from all visitors. 2534/// Notes associated with {@code ErrorNode} are generated using 2535/// {@code getEndPath}, and the rest are generated with {@code VisitNode}. 2536static std::unique_ptr<VisitorsDiagnosticsTy> 2537generateVisitorsDiagnostics(BugReport *R, const ExplodedNode *ErrorNode, 2538 BugReporterContext &BRC) { 2539 auto Notes = llvm::make_unique<VisitorsDiagnosticsTy>(); 2540 BugReport::VisitorList visitors; 2541 2542 // Run visitors on all nodes starting from the node *before* the last one. 2543 // The last node is reserved for notes generated with {@code getEndPath}. 2544 const ExplodedNode *NextNode = ErrorNode->getFirstPred(); 2545 while (NextNode) { 2546 2547 // At each iteration, move all visitors from report to visitor list. 2548 for (BugReport::visitor_iterator I = R->visitor_begin(), 2549 E = R->visitor_end(); 2550 I != E; ++I) { 2551 visitors.push_back(std::move(*I)); 2552 } 2553 R->clearVisitors(); 2554 2555 const ExplodedNode *Pred = NextNode->getFirstPred(); 2556 if (!Pred) { 2557 std::shared_ptr<PathDiagnosticPiece> LastPiece; 2558 for (auto &V : visitors) { 2559 V->finalizeVisitor(BRC, ErrorNode, *R); 2560 2561 if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) { 2562 assert(!LastPiece && 2563 "There can only be one final piece in a diagnostic."); 2564 LastPiece = std::move(Piece); 2565 (*Notes)[ErrorNode].push_back(LastPiece); 2566 } 2567 } 2568 break; 2569 } 2570 2571 for (auto &V : visitors) { 2572 auto P = V->VisitNode(NextNode, Pred, BRC, *R); 2573 if (P) 2574 (*Notes)[NextNode].push_back(std::move(P)); 2575 } 2576 2577 if (!R->isValid()) 2578 break; 2579 2580 NextNode = Pred; 2581 } 2582 2583 return Notes; 2584} 2585 2586/// Find a non-invalidated report for a given equivalence class, 2587/// and return together with a cache of visitors notes. 2588/// If none found, return a nullptr paired with an empty cache. 2589static 2590std::pair<BugReport*, std::unique_ptr<VisitorsDiagnosticsTy>> findValidReport( 2591 TrimmedGraph &TrimG, 2592 ReportGraph &ErrorGraph, 2593 ArrayRef<BugReport *> &bugReports, 2594 AnalyzerOptions &Opts, 2595 GRBugReporter &Reporter) { 2596 2597 while (TrimG.popNextReportGraph(ErrorGraph)) { 2598 // Find the BugReport with the original location. 2599 assert(ErrorGraph.Index < bugReports.size()); 2600 BugReport *R = bugReports[ErrorGraph.Index]; 2601 assert(R && "No original report found for sliced graph."); 2602 assert(R->isValid() && "Report selected by trimmed graph marked invalid."); 2603 const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode; 2604 2605 // Register refutation visitors first, if they mark the bug invalid no 2606 // further analysis is required 2607 R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>()); 2608 2609 // Register additional node visitors. 2610 R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>()); 2611 R->addVisitor(llvm::make_unique<ConditionBRVisitor>()); 2612 R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>()); 2613 2614 BugReporterContext BRC(Reporter, ErrorGraph.BackMap); 2615 2616 // Run all visitors on a given graph, once. 2617 std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes = 2618 generateVisitorsDiagnostics(R, ErrorNode, BRC); 2619 2620 if (R->isValid()) { 2621 if (Opts.shouldCrosscheckWithZ3()) { 2622 // If crosscheck is enabled, remove all visitors, add the refutation 2623 // visitor and check again 2624 R->clearVisitors(); 2625 R->addVisitor(llvm::make_unique<FalsePositiveRefutationBRVisitor>()); 2626 2627 // We don't overrite the notes inserted by other visitors because the 2628 // refutation manager does not add any new note to the path 2629 generateVisitorsDiagnostics(R, ErrorGraph.ErrorNode, BRC); 2630 } 2631 2632 // Check if the bug is still valid 2633 if (R->isValid()) 2634 return std::make_pair(R, std::move(visitorNotes)); 2635 } 2636 } 2637 2638 return std::make_pair(nullptr, llvm::make_unique<VisitorsDiagnosticsTy>()); 2639} 2640 2641std::unique_ptr<DiagnosticForConsumerMapTy> 2642GRBugReporter::generatePathDiagnostics( 2643 ArrayRef<PathDiagnosticConsumer *> consumers, 2644 ArrayRef<BugReport *> &bugReports) { 2645 assert(!bugReports.empty()); 2646 2647 auto Out = llvm::make_unique<DiagnosticForConsumerMapTy>(); 2648 bool HasValid = false; 2649 SmallVector<const ExplodedNode *, 32> errorNodes; 2650 for (const auto I : bugReports) { 2651 if (I->isValid()) { 2652 HasValid = true; 2653 errorNodes.push_back(I->getErrorNode()); 2654 } else { 2655 // Keep the errorNodes list in sync with the bugReports list. 2656 errorNodes.push_back(nullptr); 2657 } 2658 } 2659 2660 // If all the reports have been marked invalid by a previous path generation, 2661 // we're done. 2662 if (!HasValid) 2663 return Out; 2664 2665 TrimmedGraph TrimG(&getGraph(), errorNodes); 2666 ReportGraph ErrorGraph; 2667 auto ReportInfo = findValidReport(TrimG, ErrorGraph, bugReports, 2668 getAnalyzerOptions(), *this); 2669 BugReport *R = ReportInfo.first; 2670 2671 if (R && R->isValid()) { 2672 const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode; 2673 for (PathDiagnosticConsumer *PC : consumers) { 2674 PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, PC); 2675 std::unique_ptr<PathDiagnostic> PD = generatePathDiagnosticForConsumer( 2676 PC->getGenerationScheme(), PDB, ErrorNode, *ReportInfo.second); 2677 (*Out)[PC] = std::move(PD); 2678 } 2679 } 2680 2681 return Out; 2682} 2683 2684void BugReporter::Register(BugType *BT) { 2685 BugTypes = F.add(BugTypes, BT); 2686} 2687 2688void BugReporter::emitReport(std::unique_ptr<BugReport> R) { 2689 if (const ExplodedNode *E = R->getErrorNode()) { 2690 // An error node must either be a sink or have a tag, otherwise 2691 // it could get reclaimed before the path diagnostic is created. 2692 assert((E->isSink() || E->getLocation().getTag()) && 2693 "Error node must either be a sink or have a tag"); 2694 2695 const AnalysisDeclContext *DeclCtx = 2696 E->getLocationContext()->getAnalysisDeclContext(); 2697 // The source of autosynthesized body can be handcrafted AST or a model 2698 // file. The locations from handcrafted ASTs have no valid source locations 2699 // and have to be discarded. Locations from model files should be preserved 2700 // for processing and reporting. 2701 if (DeclCtx->isBodyAutosynthesized() && 2702 !DeclCtx->isBodyAutosynthesizedFromModelFile()) 2703 return; 2704 } 2705 2706 bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid(); 2707 assert(ValidSourceLoc); 2708 // If we mess up in a release build, we'd still prefer to just drop the bug 2709 // instead of trying to go on. 2710 if (!ValidSourceLoc) 2711 return; 2712 2713 // Compute the bug report's hash to determine its equivalence class. 2714 llvm::FoldingSetNodeID ID; 2715 R->Profile(ID); 2716 2717 // Lookup the equivance class. If there isn't one, create it. 2718 BugType& BT = R->getBugType(); 2719 Register(&BT); 2720 void *InsertPos; 2721 BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 2722 2723 if (!EQ) { 2724 EQ = new BugReportEquivClass(std::move(R)); 2725 EQClasses.InsertNode(EQ, InsertPos); 2726 EQClassesVector.push_back(EQ); 2727 } else 2728 EQ->AddReport(std::move(R)); 2729} 2730 2731//===----------------------------------------------------------------------===// 2732// Emitting reports in equivalence classes. 2733//===----------------------------------------------------------------------===// 2734 2735namespace { 2736 2737struct FRIEC_WLItem { 2738 const ExplodedNode *N; 2739 ExplodedNode::const_succ_iterator I, E; 2740 2741 FRIEC_WLItem(const ExplodedNode *n) 2742 : N(n), I(N->succ_begin()), E(N->succ_end()) {} 2743}; 2744 2745} // namespace 2746 2747static const CFGBlock *findBlockForNode(const ExplodedNode *N) { 2748 ProgramPoint P = N->getLocation(); 2749 if (auto BEP = P.getAs<BlockEntrance>()) 2750 return BEP->getBlock(); 2751 2752 // Find the node's current statement in the CFG. 2753 if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 2754 return N->getLocationContext()->getAnalysisDeclContext() 2755 ->getCFGStmtMap()->getBlock(S); 2756 2757 return nullptr; 2758} 2759 2760// Returns true if by simply looking at the block, we can be sure that it 2761// results in a sink during analysis. This is useful to know when the analysis 2762// was interrupted, and we try to figure out if it would sink eventually. 2763// There may be many more reasons why a sink would appear during analysis 2764// (eg. checkers may generate sinks arbitrarily), but here we only consider 2765// sinks that would be obvious by looking at the CFG. 2766static bool isImmediateSinkBlock(const CFGBlock *Blk) { 2767 if (Blk->hasNoReturnElement()) 2768 return true; 2769 2770 // FIXME: Throw-expressions are currently generating sinks during analysis: 2771 // they're not supported yet, and also often used for actually terminating 2772 // the program. So we should treat them as sinks in this analysis as well, 2773 // at least for now, but once we have better support for exceptions, 2774 // we'd need to carefully handle the case when the throw is being 2775 // immediately caught. 2776 if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) { 2777 if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>()) 2778 if (isa<CXXThrowExpr>(StmtElm->getStmt())) 2779 return true; 2780 return false; 2781 })) 2782 return true; 2783 2784 return false; 2785} 2786 2787// Returns true if by looking at the CFG surrounding the node's program 2788// point, we can be sure that any analysis starting from this point would 2789// eventually end with a sink. We scan the child CFG blocks in a depth-first 2790// manner and see if all paths eventually end up in an immediate sink block. 2791static bool isInevitablySinking(const ExplodedNode *N) { 2792 const CFG &Cfg = N->getCFG(); 2793 2794 const CFGBlock *StartBlk = findBlockForNode(N); 2795 if (!StartBlk) 2796 return false; 2797 if (isImmediateSinkBlock(StartBlk)) 2798 return true; 2799 2800 llvm::SmallVector<const CFGBlock *, 32> DFSWorkList; 2801 llvm::SmallPtrSet<const CFGBlock *, 32> Visited; 2802 2803 DFSWorkList.push_back(StartBlk); 2804 while (!DFSWorkList.empty()) { 2805 const CFGBlock *Blk = DFSWorkList.back(); 2806 DFSWorkList.pop_back(); 2807 Visited.insert(Blk); 2808 2809 for (const auto &Succ : Blk->succs()) { 2810 if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) { 2811 if (SuccBlk == &Cfg.getExit()) { 2812 // If at least one path reaches the CFG exit, it means that control is 2813 // returned to the caller. For now, say that we are not sure what 2814 // happens next. If necessary, this can be improved to analyze 2815 // the parent StackFrameContext's call site in a similar manner. 2816 return false; 2817 } 2818 2819 if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) { 2820 // If the block has reachable child blocks that aren't no-return, 2821 // add them to the worklist. 2822 DFSWorkList.push_back(SuccBlk); 2823 } 2824 } 2825 } 2826 } 2827 2828 // Nothing reached the exit. It can only mean one thing: there's no return. 2829 return true; 2830} 2831 2832static BugReport * 2833FindReportInEquivalenceClass(BugReportEquivClass& EQ, 2834 SmallVectorImpl<BugReport*> &bugReports) { 2835 BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 2836 assert(I != E); 2837 BugType& BT = I->getBugType(); 2838 2839 // If we don't need to suppress any of the nodes because they are 2840 // post-dominated by a sink, simply add all the nodes in the equivalence class 2841 // to 'Nodes'. Any of the reports will serve as a "representative" report. 2842 if (!BT.isSuppressOnSink()) { 2843 BugReport *R = &*I; 2844 for (auto &I : EQ) { 2845 const ExplodedNode *N = I.getErrorNode(); 2846 if (N) { 2847 R = &I; 2848 bugReports.push_back(R); 2849 } 2850 } 2851 return R; 2852 } 2853 2854 // For bug reports that should be suppressed when all paths are post-dominated 2855 // by a sink node, iterate through the reports in the equivalence class 2856 // until we find one that isn't post-dominated (if one exists). We use a 2857 // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 2858 // this as a recursive function, but we don't want to risk blowing out the 2859 // stack for very long paths. 2860 BugReport *exampleReport = nullptr; 2861 2862 for (; I != E; ++I) { 2863 const ExplodedNode *errorNode = I->getErrorNode(); 2864 2865 if (!errorNode) 2866 continue; 2867 if (errorNode->isSink()) { 2868 llvm_unreachable( 2869 "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 2870 } 2871 // No successors? By definition this nodes isn't post-dominated by a sink. 2872 if (errorNode->succ_empty()) { 2873 bugReports.push_back(&*I); 2874 if (!exampleReport) 2875 exampleReport = &*I; 2876 continue; 2877 } 2878 2879 // See if we are in a no-return CFG block. If so, treat this similarly 2880 // to being post-dominated by a sink. This works better when the analysis 2881 // is incomplete and we have never reached the no-return function call(s) 2882 // that we'd inevitably bump into on this path. 2883 if (isInevitablySinking(errorNode)) 2884 continue; 2885 2886 // At this point we know that 'N' is not a sink and it has at least one 2887 // successor. Use a DFS worklist to find a non-sink end-of-path node. 2888 using WLItem = FRIEC_WLItem; 2889 using DFSWorkList = SmallVector<WLItem, 10>; 2890 2891 llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 2892 2893 DFSWorkList WL; 2894 WL.push_back(errorNode); 2895 Visited[errorNode] = 1; 2896 2897 while (!WL.empty()) { 2898 WLItem &WI = WL.back(); 2899 assert(!WI.N->succ_empty()); 2900 2901 for (; WI.I != WI.E; ++WI.I) { 2902 const ExplodedNode *Succ = *WI.I; 2903 // End-of-path node? 2904 if (Succ->succ_empty()) { 2905 // If we found an end-of-path node that is not a sink. 2906 if (!Succ->isSink()) { 2907 bugReports.push_back(&*I); 2908 if (!exampleReport) 2909 exampleReport = &*I; 2910 WL.clear(); 2911 break; 2912 } 2913 // Found a sink? Continue on to the next successor. 2914 continue; 2915 } 2916 // Mark the successor as visited. If it hasn't been explored, 2917 // enqueue it to the DFS worklist. 2918 unsigned &mark = Visited[Succ]; 2919 if (!mark) { 2920 mark = 1; 2921 WL.push_back(Succ); 2922 break; 2923 } 2924 } 2925 2926 // The worklist may have been cleared at this point. First 2927 // check if it is empty before checking the last item. 2928 if (!WL.empty() && &WL.back() == &WI) 2929 WL.pop_back(); 2930 } 2931 } 2932 2933 // ExampleReport will be NULL if all the nodes in the equivalence class 2934 // were post-dominated by sinks. 2935 return exampleReport; 2936} 2937 2938void BugReporter::FlushReport(BugReportEquivClass& EQ) { 2939 SmallVector<BugReport*, 10> bugReports; 2940 BugReport *report = FindReportInEquivalenceClass(EQ, bugReports); 2941 if (!report) 2942 return; 2943 2944 ArrayRef<PathDiagnosticConsumer*> Consumers = getPathDiagnosticConsumers(); 2945 std::unique_ptr<DiagnosticForConsumerMapTy> Diagnostics = 2946 generateDiagnosticForConsumerMap(report, Consumers, bugReports); 2947 2948 for (auto &P : *Diagnostics) { 2949 PathDiagnosticConsumer *Consumer = P.first; 2950 std::unique_ptr<PathDiagnostic> &PD = P.second; 2951 2952 // If the path is empty, generate a single step path with the location 2953 // of the issue. 2954 if (PD->path.empty()) { 2955 PathDiagnosticLocation L = report->getLocation(getSourceManager()); 2956 auto piece = llvm::make_unique<PathDiagnosticEventPiece>( 2957 L, report->getDescription()); 2958 for (SourceRange Range : report->getRanges()) 2959 piece->addRange(Range); 2960 PD->setEndOfPath(std::move(piece)); 2961 } 2962 2963 PathPieces &Pieces = PD->getMutablePieces(); 2964 if (getAnalyzerOptions().shouldDisplayNotesAsEvents()) { 2965 // For path diagnostic consumers that don't support extra notes, 2966 // we may optionally convert those to path notes. 2967 for (auto I = report->getNotes().rbegin(), 2968 E = report->getNotes().rend(); I != E; ++I) { 2969 PathDiagnosticNotePiece *Piece = I->get(); 2970 auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>( 2971 Piece->getLocation(), Piece->getString()); 2972 for (const auto &R: Piece->getRanges()) 2973 ConvertedPiece->addRange(R); 2974 2975 Pieces.push_front(std::move(ConvertedPiece)); 2976 } 2977 } else { 2978 for (auto I = report->getNotes().rbegin(), 2979 E = report->getNotes().rend(); I != E; ++I) 2980 Pieces.push_front(*I); 2981 } 2982 2983 // Get the meta data. 2984 const BugReport::ExtraTextList &Meta = report->getExtraText(); 2985 for (const auto &i : Meta) 2986 PD->addMeta(i); 2987 2988 Consumer->HandlePathDiagnostic(std::move(PD)); 2989 } 2990} 2991 2992/// Insert all lines participating in the function signature \p Signature 2993/// into \p ExecutedLines. 2994static void populateExecutedLinesWithFunctionSignature( 2995 const Decl *Signature, SourceManager &SM, 2996 std::unique_ptr<FilesToLineNumsMap> &ExecutedLines) { 2997 SourceRange SignatureSourceRange; 2998 const Stmt* Body = Signature->getBody(); 2999 if (const auto FD = dyn_cast<FunctionDecl>(Signature)) { 3000 SignatureSourceRange = FD->getSourceRange(); 3001 } else if (const auto OD = dyn_cast<ObjCMethodDecl>(Signature)) { 3002 SignatureSourceRange = OD->getSourceRange(); 3003 } else { 3004 return; 3005 } 3006 SourceLocation Start = SignatureSourceRange.getBegin(); 3007 SourceLocation End = Body ? Body->getSourceRange().getBegin() 3008 : SignatureSourceRange.getEnd(); 3009 unsigned StartLine = SM.getExpansionLineNumber(Start); 3010 unsigned EndLine = SM.getExpansionLineNumber(End); 3011 3012 FileID FID = SM.getFileID(SM.getExpansionLoc(Start)); 3013 for (unsigned Line = StartLine; Line <= EndLine; Line++) 3014 ExecutedLines->operator[](FID.getHashValue()).insert(Line); 3015} 3016 3017static void populateExecutedLinesWithStmt( 3018 const Stmt *S, SourceManager &SM, 3019 std::unique_ptr<FilesToLineNumsMap> &ExecutedLines) { 3020 SourceLocation Loc = S->getSourceRange().getBegin(); 3021 SourceLocation ExpansionLoc = SM.getExpansionLoc(Loc); 3022 FileID FID = SM.getFileID(ExpansionLoc); 3023 unsigned LineNo = SM.getExpansionLineNumber(ExpansionLoc); 3024 ExecutedLines->operator[](FID.getHashValue()).insert(LineNo); 3025} 3026 3027/// \return all executed lines including function signatures on the path 3028/// starting from \p N. 3029static std::unique_ptr<FilesToLineNumsMap> 3030findExecutedLines(SourceManager &SM, const ExplodedNode *N) { 3031 auto ExecutedLines = llvm::make_unique<FilesToLineNumsMap>(); 3032 3033 while (N) { 3034 if (N->getFirstPred() == nullptr) { 3035 // First node: show signature of the entrance point. 3036 const Decl *D = N->getLocationContext()->getDecl(); 3037 populateExecutedLinesWithFunctionSignature(D, SM, ExecutedLines); 3038 } else if (auto CE = N->getLocationAs<CallEnter>()) { 3039 // Inlined function: show signature. 3040 const Decl* D = CE->getCalleeContext()->getDecl(); 3041 populateExecutedLinesWithFunctionSignature(D, SM, ExecutedLines); 3042 } else if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) { 3043 populateExecutedLinesWithStmt(S, SM, ExecutedLines); 3044 3045 // Show extra context for some parent kinds. 3046 const Stmt *P = N->getParentMap().getParent(S); 3047 3048 // The path exploration can die before the node with the associated 3049 // return statement is generated, but we do want to show the whole 3050 // return. 3051 if (const auto *RS = dyn_cast_or_null<ReturnStmt>(P)) { 3052 populateExecutedLinesWithStmt(RS, SM, ExecutedLines); 3053 P = N->getParentMap().getParent(RS); 3054 } 3055 3056 if (P && (isa<SwitchCase>(P) || isa<LabelStmt>(P))) 3057 populateExecutedLinesWithStmt(P, SM, ExecutedLines); 3058 } 3059 3060 N = N->getFirstPred(); 3061 } 3062 return ExecutedLines; 3063} 3064 3065std::unique_ptr<DiagnosticForConsumerMapTy> 3066BugReporter::generateDiagnosticForConsumerMap( 3067 BugReport *report, ArrayRef<PathDiagnosticConsumer *> consumers, 3068 ArrayRef<BugReport *> bugReports) { 3069 3070 if (!report->isPathSensitive()) { 3071 auto Out = llvm::make_unique<DiagnosticForConsumerMapTy>(); 3072 for (auto *Consumer : consumers) 3073 (*Out)[Consumer] = generateEmptyDiagnosticForReport(report, 3074 getSourceManager()); 3075 return Out; 3076 } 3077 3078 // Generate the full path sensitive diagnostic, using the generation scheme 3079 // specified by the PathDiagnosticConsumer. Note that we have to generate 3080 // path diagnostics even for consumers which do not support paths, because 3081 // the BugReporterVisitors may mark this bug as a false positive. 3082 assert(!bugReports.empty()); 3083 MaxBugClassSize.updateMax(bugReports.size()); 3084 std::unique_ptr<DiagnosticForConsumerMapTy> Out = 3085 generatePathDiagnostics(consumers, bugReports); 3086 3087 if (Out->empty()) 3088 return Out; 3089 3090 MaxValidBugClassSize.updateMax(bugReports.size()); 3091 3092 // Examine the report and see if the last piece is in a header. Reset the 3093 // report location to the last piece in the main source file. 3094 AnalyzerOptions &Opts = getAnalyzerOptions(); 3095 for (auto const &P : *Out) 3096 if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll) 3097 P.second->resetDiagnosticLocationToMainFile(); 3098 3099 return Out; 3100} 3101 3102void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3103 const CheckerBase *Checker, 3104 StringRef Name, StringRef Category, 3105 StringRef Str, PathDiagnosticLocation Loc, 3106 ArrayRef<SourceRange> Ranges) { 3107 EmitBasicReport(DeclWithIssue, Checker->getCheckName(), Name, Category, Str, 3108 Loc, Ranges); 3109} 3110 3111void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3112 CheckName CheckName, 3113 StringRef name, StringRef category, 3114 StringRef str, PathDiagnosticLocation Loc, 3115 ArrayRef<SourceRange> Ranges) { 3116 // 'BT' is owned by BugReporter. 3117 BugType *BT = getBugTypeForName(CheckName, name, category); 3118 auto R = llvm::make_unique<BugReport>(*BT, str, Loc); 3119 R->setDeclWithIssue(DeclWithIssue); 3120 for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end(); 3121 I != E; ++I) 3122 R->addRange(*I); 3123 emitReport(std::move(R)); 3124} 3125 3126BugType *BugReporter::getBugTypeForName(CheckName CheckName, StringRef name, 3127 StringRef category) { 3128 SmallString<136> fullDesc; 3129 llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name 3130 << ":" << category; 3131 BugType *&BT = StrBugTypes[fullDesc]; 3132 if (!BT) 3133 BT = new BugType(CheckName, name, category); 3134 return BT; 3135} 3136