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