blob: 94368b5f4e83e651281487ee893d48f60700752a [file] [log] [blame]
Ted Kremenek61f3e052008-04-03 04:42:52 +00001// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines BugReporter, a utility class for generating
Ted Kremenek6c07bdb2009-06-26 00:05:51 +000011// PathDiagnostics.
Ted Kremenek61f3e052008-04-03 04:42:52 +000012//
13//===----------------------------------------------------------------------===//
14
Ted Kremenek9b663712011-02-10 01:03:03 +000015#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
16#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
Ted Kremenek61f3e052008-04-03 04:42:52 +000018#include "clang/AST/ASTContext.h"
Ted Kremeneke41611a2009-07-16 18:13:04 +000019#include "clang/Analysis/CFG.h"
Benjamin Kramerc35fb7d2012-01-28 12:06:22 +000020#include "clang/AST/DeclObjC.h"
Ted Kremenek61f3e052008-04-03 04:42:52 +000021#include "clang/AST/Expr.h"
Ted Kremenek00605e02009-03-27 20:55:39 +000022#include "clang/AST/ParentMap.h"
Chris Lattner16f00492009-04-26 01:32:48 +000023#include "clang/AST/StmtObjC.h"
Benjamin Kramer00bd44d2012-02-04 12:31:12 +000024#include "clang/Basic/Diagnostic.h"
Chris Lattner16f00492009-04-26 01:32:48 +000025#include "clang/Basic/SourceManager.h"
Ted Kremenek61f3e052008-04-03 04:42:52 +000026#include "clang/Analysis/ProgramPoint.h"
Ted Kremenek9b663712011-02-10 01:03:03 +000027#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
Chris Lattner405674c2008-08-23 22:23:37 +000028#include "llvm/Support/raw_ostream.h"
Ted Kremenek331b0ac2008-06-18 05:34:07 +000029#include "llvm/ADT/DenseMap.h"
Benjamin Kramer8fe83e12012-02-04 13:45:25 +000030#include "llvm/ADT/SmallString.h"
Ted Kremenekcf118d42009-02-04 23:49:09 +000031#include "llvm/ADT/STLExtras.h"
Ted Kremenek00605e02009-03-27 20:55:39 +000032#include "llvm/ADT/OwningPtr.h"
Ted Kremenek10aa5542009-03-12 23:41:59 +000033#include <queue>
Ted Kremenek61f3e052008-04-03 04:42:52 +000034
35using namespace clang;
Ted Kremenek9ef65372010-12-23 07:20:52 +000036using namespace ento;
Ted Kremenek61f3e052008-04-03 04:42:52 +000037
Ted Kremenek8966bc12009-05-06 21:39:49 +000038BugReporterVisitor::~BugReporterVisitor() {}
Ted Kremenek1b431022010-03-20 18:01:57 +000039
David Blaikie99ba9e32011-12-20 02:48:34 +000040void BugReporterContext::anchor() {}
41
Ted Kremenekcf118d42009-02-04 23:49:09 +000042//===----------------------------------------------------------------------===//
Ted Kremenek31061982009-03-31 23:00:32 +000043// Helper routines for walking the ExplodedGraph and fetching statements.
Ted Kremenekcf118d42009-02-04 23:49:09 +000044//===----------------------------------------------------------------------===//
Ted Kremenek61f3e052008-04-03 04:42:52 +000045
Ted Kremenek9c378f72011-08-12 23:37:29 +000046static inline const Stmt *GetStmt(const ProgramPoint &P) {
Ted Kremenek592362b2009-08-18 01:05:30 +000047 if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P))
48 return SP->getStmt();
Ted Kremenek9c378f72011-08-12 23:37:29 +000049 else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P))
Ted Kremenek61f3e052008-04-03 04:42:52 +000050 return BE->getSrc()->getTerminator();
Mike Stump1eb44332009-09-09 15:08:12 +000051
Ted Kremenekb697b102009-02-23 22:44:26 +000052 return 0;
Ted Kremenek706e3cf2008-04-07 23:35:17 +000053}
54
Zhongxing Xuc5619d92009-08-06 01:32:16 +000055static inline const ExplodedNode*
Ted Kremenek9c378f72011-08-12 23:37:29 +000056GetPredecessorNode(const ExplodedNode *N) {
Ted Kremenekbd7efa82008-04-17 23:44:37 +000057 return N->pred_empty() ? NULL : *(N->pred_begin());
58}
Ted Kremenek2673c9f2008-04-25 19:01:27 +000059
Zhongxing Xuc5619d92009-08-06 01:32:16 +000060static inline const ExplodedNode*
Ted Kremenek9c378f72011-08-12 23:37:29 +000061GetSuccessorNode(const ExplodedNode *N) {
Ted Kremenekb697b102009-02-23 22:44:26 +000062 return N->succ_empty() ? NULL : *(N->succ_begin());
Ted Kremenekbd7efa82008-04-17 23:44:37 +000063}
64
Ted Kremenek9c378f72011-08-12 23:37:29 +000065static const Stmt *GetPreviousStmt(const ExplodedNode *N) {
Ted Kremenekb697b102009-02-23 22:44:26 +000066 for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
Ted Kremenek5f85e172009-07-22 22:35:28 +000067 if (const Stmt *S = GetStmt(N->getLocation()))
Ted Kremenekb697b102009-02-23 22:44:26 +000068 return S;
Mike Stump1eb44332009-09-09 15:08:12 +000069
Ted Kremenekb697b102009-02-23 22:44:26 +000070 return 0;
Ted Kremenek3148eb42009-01-24 00:55:43 +000071}
72
Ted Kremenek9c378f72011-08-12 23:37:29 +000073static const Stmt *GetNextStmt(const ExplodedNode *N) {
Ted Kremenekb697b102009-02-23 22:44:26 +000074 for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
Ted Kremenek5f85e172009-07-22 22:35:28 +000075 if (const Stmt *S = GetStmt(N->getLocation())) {
Ted Kremenekf5ab8e62009-03-28 17:33:57 +000076 // Check if the statement is '?' or '&&'/'||'. These are "merges",
77 // not actual statement points.
78 switch (S->getStmtClass()) {
79 case Stmt::ChooseExprClass:
John McCall56ca35d2011-02-17 10:25:35 +000080 case Stmt::BinaryConditionalOperatorClass: continue;
Ted Kremenekf5ab8e62009-03-28 17:33:57 +000081 case Stmt::ConditionalOperatorClass: continue;
82 case Stmt::BinaryOperatorClass: {
John McCall2de56d12010-08-25 11:45:40 +000083 BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
84 if (Op == BO_LAnd || Op == BO_LOr)
Ted Kremenekf5ab8e62009-03-28 17:33:57 +000085 continue;
86 break;
87 }
88 default:
89 break;
90 }
Ted Kremenekb697b102009-02-23 22:44:26 +000091 return S;
Ted Kremenekf5ab8e62009-03-28 17:33:57 +000092 }
Mike Stump1eb44332009-09-09 15:08:12 +000093
Ted Kremenekb697b102009-02-23 22:44:26 +000094 return 0;
95}
96
Ted Kremenek5f85e172009-07-22 22:35:28 +000097static inline const Stmt*
Ted Kremenek9c378f72011-08-12 23:37:29 +000098GetCurrentOrPreviousStmt(const ExplodedNode *N) {
Ted Kremenek5f85e172009-07-22 22:35:28 +000099 if (const Stmt *S = GetStmt(N->getLocation()))
Ted Kremenekb697b102009-02-23 22:44:26 +0000100 return S;
Mike Stump1eb44332009-09-09 15:08:12 +0000101
Ted Kremenekb697b102009-02-23 22:44:26 +0000102 return GetPreviousStmt(N);
103}
Mike Stump1eb44332009-09-09 15:08:12 +0000104
Ted Kremenek5f85e172009-07-22 22:35:28 +0000105static inline const Stmt*
Ted Kremenek9c378f72011-08-12 23:37:29 +0000106GetCurrentOrNextStmt(const ExplodedNode *N) {
Ted Kremenek5f85e172009-07-22 22:35:28 +0000107 if (const Stmt *S = GetStmt(N->getLocation()))
Ted Kremenekb697b102009-02-23 22:44:26 +0000108 return S;
Mike Stump1eb44332009-09-09 15:08:12 +0000109
Ted Kremenekb697b102009-02-23 22:44:26 +0000110 return GetNextStmt(N);
111}
112
113//===----------------------------------------------------------------------===//
Ted Kremenek31061982009-03-31 23:00:32 +0000114// PathDiagnosticBuilder and its associated routines and helper objects.
Ted Kremenekb697b102009-02-23 22:44:26 +0000115//===----------------------------------------------------------------------===//
Ted Kremenekb479dad2009-02-23 23:13:51 +0000116
Zhongxing Xuc5619d92009-08-06 01:32:16 +0000117typedef llvm::DenseMap<const ExplodedNode*,
118const ExplodedNode*> NodeBackMap;
Ted Kremenek7dc86642009-03-31 20:22:36 +0000119
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000120namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000121class NodeMapClosure : public BugReport::NodeResolver {
Ted Kremenek7dc86642009-03-31 20:22:36 +0000122 NodeBackMap& M;
123public:
124 NodeMapClosure(NodeBackMap *m) : M(*m) {}
125 ~NodeMapClosure() {}
Mike Stump1eb44332009-09-09 15:08:12 +0000126
Ted Kremenek9c378f72011-08-12 23:37:29 +0000127 const ExplodedNode *getOriginalNode(const ExplodedNode *N) {
Ted Kremenek7dc86642009-03-31 20:22:36 +0000128 NodeBackMap::iterator I = M.find(N);
129 return I == M.end() ? 0 : I->second;
130 }
131};
Mike Stump1eb44332009-09-09 15:08:12 +0000132
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000133class PathDiagnosticBuilder : public BugReporterContext {
Ted Kremenek7dc86642009-03-31 20:22:36 +0000134 BugReport *R;
David Blaikieef3643f2011-09-26 00:51:36 +0000135 PathDiagnosticConsumer *PDC;
Dylan Noblesmith6f42b622012-02-05 02:12:40 +0000136 OwningPtr<ParentMap> PM;
Ted Kremenek7dc86642009-03-31 20:22:36 +0000137 NodeMapClosure NMC;
Mike Stump1eb44332009-09-09 15:08:12 +0000138public:
Ted Kremenek8966bc12009-05-06 21:39:49 +0000139 PathDiagnosticBuilder(GRBugReporter &br,
Mike Stump1eb44332009-09-09 15:08:12 +0000140 BugReport *r, NodeBackMap *Backmap,
David Blaikieef3643f2011-09-26 00:51:36 +0000141 PathDiagnosticConsumer *pdc)
Ted Kremenek8966bc12009-05-06 21:39:49 +0000142 : BugReporterContext(br),
Anna Zaks8e6431a2011-08-18 22:37:56 +0000143 R(r), PDC(pdc), NMC(Backmap) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000144
Ted Kremenek9c378f72011-08-12 23:37:29 +0000145 PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
Mike Stump1eb44332009-09-09 15:08:12 +0000146
Ted Kremenek9c378f72011-08-12 23:37:29 +0000147 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
148 const ExplodedNode *N);
Mike Stump1eb44332009-09-09 15:08:12 +0000149
Anna Zaks8e6431a2011-08-18 22:37:56 +0000150 BugReport *getBugReport() { return R; }
151
Tom Care212f6d32010-09-16 03:50:38 +0000152 Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
Zhongxing Xub317f8f2009-09-10 05:44:00 +0000153
Anna Zaks220ac8c2011-09-15 01:08:34 +0000154 const LocationContext* getLocationContext() {
155 return R->getErrorNode()->getLocationContext();
156 }
157
Tom Care212f6d32010-09-16 03:50:38 +0000158 ParentMap& getParentMap() { return R->getErrorNode()->getParentMap(); }
Mike Stump1eb44332009-09-09 15:08:12 +0000159
Ted Kremenekc3f83ad2009-04-01 17:18:21 +0000160 const Stmt *getParent(const Stmt *S) {
161 return getParentMap().getParent(S);
162 }
Mike Stump1eb44332009-09-09 15:08:12 +0000163
Ted Kremenek8966bc12009-05-06 21:39:49 +0000164 virtual NodeMapClosure& getNodeResolver() { return NMC; }
Douglas Gregor72971342009-04-18 00:02:19 +0000165
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000166 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
Mike Stump1eb44332009-09-09 15:08:12 +0000167
David Blaikieef3643f2011-09-26 00:51:36 +0000168 PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
169 return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive;
Ted Kremenek7dc86642009-03-31 20:22:36 +0000170 }
171
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000172 bool supportsLogicalOpControlFlow() const {
173 return PDC ? PDC->supportsLogicalOpControlFlow() : true;
Mike Stump1eb44332009-09-09 15:08:12 +0000174 }
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000175};
176} // end anonymous namespace
177
Ted Kremenek00605e02009-03-27 20:55:39 +0000178PathDiagnosticLocation
Ted Kremenek9c378f72011-08-12 23:37:29 +0000179PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
Ted Kremenek5f85e172009-07-22 22:35:28 +0000180 if (const Stmt *S = GetNextStmt(N))
Anna Zaks220ac8c2011-09-15 01:08:34 +0000181 return PathDiagnosticLocation(S, getSourceManager(), getLocationContext());
Ted Kremenek00605e02009-03-27 20:55:39 +0000182
Anna Zaks0cd59482011-09-16 19:18:30 +0000183 return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(),
184 getSourceManager());
Ted Kremenek082cb8d2009-03-12 18:41:53 +0000185}
Mike Stump1eb44332009-09-09 15:08:12 +0000186
Ted Kremenek00605e02009-03-27 20:55:39 +0000187PathDiagnosticLocation
Ted Kremenek9c378f72011-08-12 23:37:29 +0000188PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
189 const ExplodedNode *N) {
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000190
Ted Kremenek143ca222008-05-06 18:11:09 +0000191 // Slow, but probably doesn't matter.
Ted Kremenekb697b102009-02-23 22:44:26 +0000192 if (os.str().empty())
193 os << ' ';
Mike Stump1eb44332009-09-09 15:08:12 +0000194
Ted Kremenek00605e02009-03-27 20:55:39 +0000195 const PathDiagnosticLocation &Loc = ExecutionContinues(N);
Mike Stump1eb44332009-09-09 15:08:12 +0000196
Ted Kremenek00605e02009-03-27 20:55:39 +0000197 if (Loc.asStmt())
Ted Kremenekb697b102009-02-23 22:44:26 +0000198 os << "Execution continues on line "
Chandler Carruth64211622011-07-25 21:09:52 +0000199 << getSourceManager().getExpansionLineNumber(Loc.asLocation())
Ted Kremenek8966bc12009-05-06 21:39:49 +0000200 << '.';
Ted Kremenek4f1db532009-12-04 20:34:31 +0000201 else {
202 os << "Execution jumps to the end of the ";
203 const Decl *D = N->getLocationContext()->getDecl();
204 if (isa<ObjCMethodDecl>(D))
205 os << "method";
206 else if (isa<FunctionDecl>(D))
207 os << "function";
208 else {
209 assert(isa<BlockDecl>(D));
210 os << "anonymous block";
211 }
212 os << '.';
213 }
Mike Stump1eb44332009-09-09 15:08:12 +0000214
Ted Kremenek082cb8d2009-03-12 18:41:53 +0000215 return Loc;
Ted Kremenek143ca222008-05-06 18:11:09 +0000216}
217
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000218static bool IsNested(const Stmt *S, ParentMap &PM) {
219 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
220 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000221
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000222 const Stmt *Parent = PM.getParentIgnoreParens(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000223
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000224 if (Parent)
225 switch (Parent->getStmtClass()) {
226 case Stmt::ForStmtClass:
227 case Stmt::DoStmtClass:
228 case Stmt::WhileStmtClass:
229 return true;
230 default:
231 break;
232 }
Mike Stump1eb44332009-09-09 15:08:12 +0000233
234 return false;
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000235}
236
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000237PathDiagnosticLocation
238PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
Ted Kremenek9c378f72011-08-12 23:37:29 +0000239 assert(S && "Null Stmt *passed to getEnclosingStmtLocation");
Mike Stump1eb44332009-09-09 15:08:12 +0000240 ParentMap &P = getParentMap();
Ted Kremenek8966bc12009-05-06 21:39:49 +0000241 SourceManager &SMgr = getSourceManager();
Anna Zaks220ac8c2011-09-15 01:08:34 +0000242 const LocationContext *LC = getLocationContext();
Ted Kremeneke88a1702009-05-11 22:19:32 +0000243
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000244 while (IsNested(S, P)) {
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000245 const Stmt *Parent = P.getParentIgnoreParens(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000246
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000247 if (!Parent)
248 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000249
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000250 switch (Parent->getStmtClass()) {
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000251 case Stmt::BinaryOperatorClass: {
252 const BinaryOperator *B = cast<BinaryOperator>(Parent);
253 if (B->isLogicalOp())
Anna Zaks220ac8c2011-09-15 01:08:34 +0000254 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000255 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000256 }
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000257 case Stmt::CompoundStmtClass:
258 case Stmt::StmtExprClass:
Anna Zaks220ac8c2011-09-15 01:08:34 +0000259 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenek1d9a23a2009-03-28 04:08:14 +0000260 case Stmt::ChooseExprClass:
261 // Similar to '?' if we are referring to condition, just have the edge
262 // point to the entire choose expression.
263 if (cast<ChooseExpr>(Parent)->getCond() == S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000264 return PathDiagnosticLocation(Parent, SMgr, LC);
Ted Kremenek1d9a23a2009-03-28 04:08:14 +0000265 else
Anna Zaks220ac8c2011-09-15 01:08:34 +0000266 return PathDiagnosticLocation(S, SMgr, LC);
John McCall56ca35d2011-02-17 10:25:35 +0000267 case Stmt::BinaryConditionalOperatorClass:
Ted Kremenek1d9a23a2009-03-28 04:08:14 +0000268 case Stmt::ConditionalOperatorClass:
269 // For '?', if we are referring to condition, just have the edge point
270 // to the entire '?' expression.
John McCall56ca35d2011-02-17 10:25:35 +0000271 if (cast<AbstractConditionalOperator>(Parent)->getCond() == S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000272 return PathDiagnosticLocation(Parent, SMgr, LC);
Ted Kremenek1d9a23a2009-03-28 04:08:14 +0000273 else
Anna Zaks220ac8c2011-09-15 01:08:34 +0000274 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000275 case Stmt::DoStmtClass:
Anna Zaks220ac8c2011-09-15 01:08:34 +0000276 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000277 case Stmt::ForStmtClass:
278 if (cast<ForStmt>(Parent)->getBody() == S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000279 return PathDiagnosticLocation(S, SMgr, LC);
Mike Stump1eb44332009-09-09 15:08:12 +0000280 break;
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000281 case Stmt::IfStmtClass:
282 if (cast<IfStmt>(Parent)->getCond() != S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000283 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenek8bd4d032009-04-28 04:23:15 +0000284 break;
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000285 case Stmt::ObjCForCollectionStmtClass:
286 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000287 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000288 break;
289 case Stmt::WhileStmtClass:
290 if (cast<WhileStmt>(Parent)->getCond() != S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000291 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000292 break;
293 default:
294 break;
295 }
296
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000297 S = Parent;
298 }
Mike Stump1eb44332009-09-09 15:08:12 +0000299
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000300 assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
Ted Kremeneke88a1702009-05-11 22:19:32 +0000301
302 // Special case: DeclStmts can appear in for statement declarations, in which
303 // case the ForStmt is the context.
304 if (isa<DeclStmt>(S)) {
305 if (const Stmt *Parent = P.getParent(S)) {
306 switch (Parent->getStmtClass()) {
307 case Stmt::ForStmtClass:
308 case Stmt::ObjCForCollectionStmtClass:
Anna Zaks220ac8c2011-09-15 01:08:34 +0000309 return PathDiagnosticLocation(Parent, SMgr, LC);
Ted Kremeneke88a1702009-05-11 22:19:32 +0000310 default:
311 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000312 }
313 }
Ted Kremeneke88a1702009-05-11 22:19:32 +0000314 }
315 else if (isa<BinaryOperator>(S)) {
316 // Special case: the binary operator represents the initialization
317 // code in a for statement (this can happen when the variable being
318 // initialized is an old variable.
319 if (const ForStmt *FS =
320 dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
321 if (FS->getInit() == S)
Anna Zaks220ac8c2011-09-15 01:08:34 +0000322 return PathDiagnosticLocation(FS, SMgr, LC);
Ted Kremeneke88a1702009-05-11 22:19:32 +0000323 }
324 }
325
Anna Zaks220ac8c2011-09-15 01:08:34 +0000326 return PathDiagnosticLocation(S, SMgr, LC);
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000327}
328
Ted Kremenekcf118d42009-02-04 23:49:09 +0000329//===----------------------------------------------------------------------===//
Ted Kremenek31061982009-03-31 23:00:32 +0000330// ScanNotableSymbols: closure-like callback for scanning Store bindings.
331//===----------------------------------------------------------------------===//
332
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000333static const VarDecl* GetMostRecentVarDeclBinding(const ExplodedNode *N,
334 ProgramStateManager& VMgr,
335 SVal X) {
Mike Stump1eb44332009-09-09 15:08:12 +0000336
Ted Kremenek31061982009-03-31 23:00:32 +0000337 for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
Mike Stump1eb44332009-09-09 15:08:12 +0000338
Ted Kremenek31061982009-03-31 23:00:32 +0000339 ProgramPoint P = N->getLocation();
Mike Stump1eb44332009-09-09 15:08:12 +0000340
Ted Kremenek31061982009-03-31 23:00:32 +0000341 if (!isa<PostStmt>(P))
342 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000343
Ted Kremenek9c378f72011-08-12 23:37:29 +0000344 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
Mike Stump1eb44332009-09-09 15:08:12 +0000345
Ted Kremenek31061982009-03-31 23:00:32 +0000346 if (!DR)
347 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000348
Ted Kremenek5eca4822012-01-06 22:09:28 +0000349 SVal Y = N->getState()->getSVal(DR, N->getLocationContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000350
Ted Kremenek31061982009-03-31 23:00:32 +0000351 if (X != Y)
352 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000353
Ted Kremenek9c378f72011-08-12 23:37:29 +0000354 const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
Mike Stump1eb44332009-09-09 15:08:12 +0000355
Ted Kremenek31061982009-03-31 23:00:32 +0000356 if (!VD)
357 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000358
Ted Kremenek31061982009-03-31 23:00:32 +0000359 return VD;
360 }
Mike Stump1eb44332009-09-09 15:08:12 +0000361
Ted Kremenek31061982009-03-31 23:00:32 +0000362 return 0;
363}
364
365namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000366class NotableSymbolHandler
Ted Kremenek31061982009-03-31 23:00:32 +0000367: public StoreManager::BindingsHandler {
Mike Stump1eb44332009-09-09 15:08:12 +0000368
Ted Kremenek31061982009-03-31 23:00:32 +0000369 SymbolRef Sym;
Ted Kremenek8bef8232012-01-26 21:29:00 +0000370 ProgramStateRef PrevSt;
Ted Kremenek9c378f72011-08-12 23:37:29 +0000371 const Stmt *S;
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000372 ProgramStateManager& VMgr;
Ted Kremenek9c378f72011-08-12 23:37:29 +0000373 const ExplodedNode *Pred;
Mike Stump1eb44332009-09-09 15:08:12 +0000374 PathDiagnostic& PD;
Ted Kremenek31061982009-03-31 23:00:32 +0000375 BugReporter& BR;
Mike Stump1eb44332009-09-09 15:08:12 +0000376
Ted Kremenek31061982009-03-31 23:00:32 +0000377public:
Mike Stump1eb44332009-09-09 15:08:12 +0000378
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000379 NotableSymbolHandler(SymbolRef sym,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000380 ProgramStateRef prevst,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000381 const Stmt *s,
382 ProgramStateManager& vmgr,
383 const ExplodedNode *pred,
384 PathDiagnostic& pd,
385 BugReporter& br)
386 : Sym(sym),
387 PrevSt(prevst),
388 S(s),
389 VMgr(vmgr),
390 Pred(pred),
391 PD(pd),
392 BR(br) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000393
Ted Kremenek31061982009-03-31 23:00:32 +0000394 bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
395 SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +0000396
Ted Kremenek31061982009-03-31 23:00:32 +0000397 SymbolRef ScanSym = V.getAsSymbol();
Mike Stump1eb44332009-09-09 15:08:12 +0000398
Ted Kremenek31061982009-03-31 23:00:32 +0000399 if (ScanSym != Sym)
400 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000401
402 // Check if the previous state has this binding.
Ted Kremenek13976632010-02-08 16:18:51 +0000403 SVal X = PrevSt->getSVal(loc::MemRegionVal(R));
Mike Stump1eb44332009-09-09 15:08:12 +0000404
Ted Kremenek31061982009-03-31 23:00:32 +0000405 if (X == V) // Same binding?
406 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000407
Ted Kremenek31061982009-03-31 23:00:32 +0000408 // Different binding. Only handle assignments for now. We don't pull
Mike Stump1eb44332009-09-09 15:08:12 +0000409 // this check out of the loop because we will eventually handle other
Ted Kremenek31061982009-03-31 23:00:32 +0000410 // cases.
Mike Stump1eb44332009-09-09 15:08:12 +0000411
Ted Kremenek31061982009-03-31 23:00:32 +0000412 VarDecl *VD = 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000413
Ted Kremenek31061982009-03-31 23:00:32 +0000414 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
415 if (!B->isAssignmentOp())
416 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000417
Ted Kremenek31061982009-03-31 23:00:32 +0000418 // What variable did we assign to?
Ted Kremenek9c378f72011-08-12 23:37:29 +0000419 DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
Mike Stump1eb44332009-09-09 15:08:12 +0000420
Ted Kremenek31061982009-03-31 23:00:32 +0000421 if (!DR)
422 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000423
Ted Kremenek31061982009-03-31 23:00:32 +0000424 VD = dyn_cast<VarDecl>(DR->getDecl());
425 }
Ted Kremenek9c378f72011-08-12 23:37:29 +0000426 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
Ted Kremenek31061982009-03-31 23:00:32 +0000427 // FIXME: Eventually CFGs won't have DeclStmts. Right now we
428 // assume that each DeclStmt has a single Decl. This invariant
Chris Lattnerfc8f0e12011-04-15 05:22:18 +0000429 // holds by construction in the CFG.
Ted Kremenek31061982009-03-31 23:00:32 +0000430 VD = dyn_cast<VarDecl>(*DS->decl_begin());
431 }
Mike Stump1eb44332009-09-09 15:08:12 +0000432
Ted Kremenek31061982009-03-31 23:00:32 +0000433 if (!VD)
434 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000435
Ted Kremenek31061982009-03-31 23:00:32 +0000436 // What is the most recently referenced variable with this binding?
Ted Kremenek9c378f72011-08-12 23:37:29 +0000437 const VarDecl *MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
Mike Stump1eb44332009-09-09 15:08:12 +0000438
Ted Kremenek31061982009-03-31 23:00:32 +0000439 if (!MostRecent)
440 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000441
Ted Kremenek31061982009-03-31 23:00:32 +0000442 // Create the diagnostic.
Zhanyong Wan7dfc9422011-02-16 21:13:32 +0000443 if (Loc::isLocType(VD->getType())) {
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000444 SmallString<64> buf;
Jordy Rose7df12342011-08-21 05:25:15 +0000445 llvm::raw_svector_ostream os(buf);
Benjamin Kramerb8989f22011-10-14 18:45:37 +0000446 os << '\'' << *VD << "' now aliases '" << *MostRecent << '\'';
Anna Zaks590dd8e2011-09-20 21:38:35 +0000447 PathDiagnosticLocation L =
448 PathDiagnosticLocation::createBegin(S, BR.getSourceManager(),
449 Pred->getLocationContext());
Jordy Rose7df12342011-08-21 05:25:15 +0000450 PD.push_front(new PathDiagnosticEventPiece(L, os.str()));
Ted Kremenek31061982009-03-31 23:00:32 +0000451 }
Mike Stump1eb44332009-09-09 15:08:12 +0000452
Ted Kremenek31061982009-03-31 23:00:32 +0000453 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000454 }
Ted Kremenek31061982009-03-31 23:00:32 +0000455};
456}
457
Ted Kremenek9c378f72011-08-12 23:37:29 +0000458static void HandleNotableSymbol(const ExplodedNode *N,
459 const Stmt *S,
Ted Kremenek31061982009-03-31 23:00:32 +0000460 SymbolRef Sym, BugReporter& BR,
461 PathDiagnostic& PD) {
Mike Stump1eb44332009-09-09 15:08:12 +0000462
Ted Kremenek9c378f72011-08-12 23:37:29 +0000463 const ExplodedNode *Pred = N->pred_empty() ? 0 : *N->pred_begin();
Ted Kremenek8bef8232012-01-26 21:29:00 +0000464 ProgramStateRef PrevSt = Pred ? Pred->getState() : 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000465
Ted Kremenek31061982009-03-31 23:00:32 +0000466 if (!PrevSt)
467 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000468
Ted Kremenek31061982009-03-31 23:00:32 +0000469 // Look at the region bindings of the current state that map to the
470 // specified symbol. Are any of them not in the previous state?
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000471 ProgramStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
Ted Kremenek31061982009-03-31 23:00:32 +0000472 NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
473 cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
474}
475
476namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000477class ScanNotableSymbols
Ted Kremenek31061982009-03-31 23:00:32 +0000478: public StoreManager::BindingsHandler {
Mike Stump1eb44332009-09-09 15:08:12 +0000479
Ted Kremenek31061982009-03-31 23:00:32 +0000480 llvm::SmallSet<SymbolRef, 10> AlreadyProcessed;
Ted Kremenek9c378f72011-08-12 23:37:29 +0000481 const ExplodedNode *N;
482 const Stmt *S;
Ted Kremenek31061982009-03-31 23:00:32 +0000483 GRBugReporter& BR;
484 PathDiagnostic& PD;
Mike Stump1eb44332009-09-09 15:08:12 +0000485
Ted Kremenek31061982009-03-31 23:00:32 +0000486public:
Ted Kremenek9c378f72011-08-12 23:37:29 +0000487 ScanNotableSymbols(const ExplodedNode *n, const Stmt *s,
Ted Kremenek5f85e172009-07-22 22:35:28 +0000488 GRBugReporter& br, PathDiagnostic& pd)
Ted Kremenek31061982009-03-31 23:00:32 +0000489 : N(n), S(s), BR(br), PD(pd) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000490
Ted Kremenek31061982009-03-31 23:00:32 +0000491 bool HandleBinding(StoreManager& SMgr, Store store,
492 const MemRegion* R, SVal V) {
Mike Stump1eb44332009-09-09 15:08:12 +0000493
Ted Kremenek31061982009-03-31 23:00:32 +0000494 SymbolRef ScanSym = V.getAsSymbol();
Mike Stump1eb44332009-09-09 15:08:12 +0000495
Ted Kremenek31061982009-03-31 23:00:32 +0000496 if (!ScanSym)
497 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000498
Ted Kremenek31061982009-03-31 23:00:32 +0000499 if (!BR.isNotable(ScanSym))
500 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000501
Ted Kremenek31061982009-03-31 23:00:32 +0000502 if (AlreadyProcessed.count(ScanSym))
503 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000504
Ted Kremenek31061982009-03-31 23:00:32 +0000505 AlreadyProcessed.insert(ScanSym);
Mike Stump1eb44332009-09-09 15:08:12 +0000506
Ted Kremenek31061982009-03-31 23:00:32 +0000507 HandleNotableSymbol(N, S, ScanSym, BR, PD);
508 return true;
509 }
510};
511} // end anonymous namespace
512
513//===----------------------------------------------------------------------===//
514// "Minimal" path diagnostic generation algorithm.
515//===----------------------------------------------------------------------===//
516
Ted Kremenek14856d72009-04-06 23:06:54 +0000517static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM);
518
Ted Kremenek31061982009-03-31 23:00:32 +0000519static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
520 PathDiagnosticBuilder &PDB,
Zhongxing Xuc5619d92009-08-06 01:32:16 +0000521 const ExplodedNode *N) {
Ted Kremenek8966bc12009-05-06 21:39:49 +0000522
Ted Kremenek31061982009-03-31 23:00:32 +0000523 SourceManager& SMgr = PDB.getSourceManager();
Anna Zaks220ac8c2011-09-15 01:08:34 +0000524 const LocationContext *LC = PDB.getLocationContext();
Ted Kremenek9c378f72011-08-12 23:37:29 +0000525 const ExplodedNode *NextNode = N->pred_empty()
Ted Kremenek31061982009-03-31 23:00:32 +0000526 ? NULL : *(N->pred_begin());
527 while (NextNode) {
Mike Stump1eb44332009-09-09 15:08:12 +0000528 N = NextNode;
Ted Kremenek31061982009-03-31 23:00:32 +0000529 NextNode = GetPredecessorNode(N);
Mike Stump1eb44332009-09-09 15:08:12 +0000530
Ted Kremenek31061982009-03-31 23:00:32 +0000531 ProgramPoint P = N->getLocation();
Mike Stump1eb44332009-09-09 15:08:12 +0000532
Ted Kremenek9c378f72011-08-12 23:37:29 +0000533 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
534 const CFGBlock *Src = BE->getSrc();
535 const CFGBlock *Dst = BE->getDst();
536 const Stmt *T = Src->getTerminator();
Mike Stump1eb44332009-09-09 15:08:12 +0000537
Ted Kremenek31061982009-03-31 23:00:32 +0000538 if (!T)
539 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000540
Anna Zaks590dd8e2011-09-20 21:38:35 +0000541 PathDiagnosticLocation Start =
542 PathDiagnosticLocation::createBegin(T, SMgr,
543 N->getLocationContext());
Mike Stump1eb44332009-09-09 15:08:12 +0000544
Ted Kremenek31061982009-03-31 23:00:32 +0000545 switch (T->getStmtClass()) {
546 default:
547 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000548
Ted Kremenek31061982009-03-31 23:00:32 +0000549 case Stmt::GotoStmtClass:
Mike Stump1eb44332009-09-09 15:08:12 +0000550 case Stmt::IndirectGotoStmtClass: {
Ted Kremenek9c378f72011-08-12 23:37:29 +0000551 const Stmt *S = GetNextStmt(N);
Mike Stump1eb44332009-09-09 15:08:12 +0000552
Ted Kremenek31061982009-03-31 23:00:32 +0000553 if (!S)
554 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000555
Ted Kremenek31061982009-03-31 23:00:32 +0000556 std::string sbuf;
Mike Stump1eb44332009-09-09 15:08:12 +0000557 llvm::raw_string_ostream os(sbuf);
Ted Kremenek31061982009-03-31 23:00:32 +0000558 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000559
Ted Kremenek31061982009-03-31 23:00:32 +0000560 os << "Control jumps to line "
Chandler Carruth64211622011-07-25 21:09:52 +0000561 << End.asLocation().getExpansionLineNumber();
Ted Kremenek31061982009-03-31 23:00:32 +0000562 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
563 os.str()));
564 break;
565 }
Mike Stump1eb44332009-09-09 15:08:12 +0000566
567 case Stmt::SwitchStmtClass: {
Ted Kremenek31061982009-03-31 23:00:32 +0000568 // Figure out what case arm we took.
569 std::string sbuf;
570 llvm::raw_string_ostream os(sbuf);
Mike Stump1eb44332009-09-09 15:08:12 +0000571
Ted Kremenek9c378f72011-08-12 23:37:29 +0000572 if (const Stmt *S = Dst->getLabel()) {
Anna Zaks220ac8c2011-09-15 01:08:34 +0000573 PathDiagnosticLocation End(S, SMgr, LC);
Mike Stump1eb44332009-09-09 15:08:12 +0000574
Ted Kremenek31061982009-03-31 23:00:32 +0000575 switch (S->getStmtClass()) {
576 default:
577 os << "No cases match in the switch statement. "
578 "Control jumps to line "
Chandler Carruth64211622011-07-25 21:09:52 +0000579 << End.asLocation().getExpansionLineNumber();
Ted Kremenek31061982009-03-31 23:00:32 +0000580 break;
581 case Stmt::DefaultStmtClass:
582 os << "Control jumps to the 'default' case at line "
Chandler Carruth64211622011-07-25 21:09:52 +0000583 << End.asLocation().getExpansionLineNumber();
Ted Kremenek31061982009-03-31 23:00:32 +0000584 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000585
Ted Kremenek31061982009-03-31 23:00:32 +0000586 case Stmt::CaseStmtClass: {
Mike Stump1eb44332009-09-09 15:08:12 +0000587 os << "Control jumps to 'case ";
Ted Kremenek9c378f72011-08-12 23:37:29 +0000588 const CaseStmt *Case = cast<CaseStmt>(S);
589 const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
Mike Stump1eb44332009-09-09 15:08:12 +0000590
591 // Determine if it is an enum.
Ted Kremenek31061982009-03-31 23:00:32 +0000592 bool GetRawInt = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000593
Ted Kremenek9c378f72011-08-12 23:37:29 +0000594 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
Ted Kremenek31061982009-03-31 23:00:32 +0000595 // FIXME: Maybe this should be an assertion. Are there cases
596 // were it is not an EnumConstantDecl?
Ted Kremenek9c378f72011-08-12 23:37:29 +0000597 const EnumConstantDecl *D =
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000598 dyn_cast<EnumConstantDecl>(DR->getDecl());
Mike Stump1eb44332009-09-09 15:08:12 +0000599
Ted Kremenek31061982009-03-31 23:00:32 +0000600 if (D) {
601 GetRawInt = false;
Benjamin Kramerb8989f22011-10-14 18:45:37 +0000602 os << *D;
Ted Kremenek31061982009-03-31 23:00:32 +0000603 }
604 }
Eli Friedman9ec64d62009-04-26 19:04:51 +0000605
606 if (GetRawInt)
Richard Smitha6b8b2c2011-10-10 18:28:20 +0000607 os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
Eli Friedman9ec64d62009-04-26 19:04:51 +0000608
Ted Kremenek31061982009-03-31 23:00:32 +0000609 os << ":' at line "
Chandler Carruth64211622011-07-25 21:09:52 +0000610 << End.asLocation().getExpansionLineNumber();
Ted Kremenek31061982009-03-31 23:00:32 +0000611 break;
612 }
613 }
614 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
615 os.str()));
616 }
617 else {
618 os << "'Default' branch taken. ";
Mike Stump1eb44332009-09-09 15:08:12 +0000619 const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
Ted Kremenek31061982009-03-31 23:00:32 +0000620 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
621 os.str()));
622 }
Mike Stump1eb44332009-09-09 15:08:12 +0000623
Ted Kremenek31061982009-03-31 23:00:32 +0000624 break;
625 }
Mike Stump1eb44332009-09-09 15:08:12 +0000626
Ted Kremenek31061982009-03-31 23:00:32 +0000627 case Stmt::BreakStmtClass:
628 case Stmt::ContinueStmtClass: {
629 std::string sbuf;
630 llvm::raw_string_ostream os(sbuf);
631 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
632 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
633 os.str()));
634 break;
635 }
Mike Stump1eb44332009-09-09 15:08:12 +0000636
Ted Kremenek31061982009-03-31 23:00:32 +0000637 // Determine control-flow for ternary '?'.
John McCall56ca35d2011-02-17 10:25:35 +0000638 case Stmt::BinaryConditionalOperatorClass:
Ted Kremenek31061982009-03-31 23:00:32 +0000639 case Stmt::ConditionalOperatorClass: {
640 std::string sbuf;
641 llvm::raw_string_ostream os(sbuf);
642 os << "'?' condition is ";
Mike Stump1eb44332009-09-09 15:08:12 +0000643
Ted Kremenek31061982009-03-31 23:00:32 +0000644 if (*(Src->succ_begin()+1) == Dst)
645 os << "false";
646 else
647 os << "true";
Mike Stump1eb44332009-09-09 15:08:12 +0000648
Ted Kremenek31061982009-03-31 23:00:32 +0000649 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
Mike Stump1eb44332009-09-09 15:08:12 +0000650
Ted Kremenek31061982009-03-31 23:00:32 +0000651 if (const Stmt *S = End.asStmt())
652 End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000653
Ted Kremenek31061982009-03-31 23:00:32 +0000654 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
655 os.str()));
656 break;
657 }
Mike Stump1eb44332009-09-09 15:08:12 +0000658
Ted Kremenek31061982009-03-31 23:00:32 +0000659 // Determine control-flow for short-circuited '&&' and '||'.
660 case Stmt::BinaryOperatorClass: {
661 if (!PDB.supportsLogicalOpControlFlow())
662 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000663
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000664 const BinaryOperator *B = cast<BinaryOperator>(T);
Ted Kremenek31061982009-03-31 23:00:32 +0000665 std::string sbuf;
666 llvm::raw_string_ostream os(sbuf);
667 os << "Left side of '";
Mike Stump1eb44332009-09-09 15:08:12 +0000668
John McCall2de56d12010-08-25 11:45:40 +0000669 if (B->getOpcode() == BO_LAnd) {
Ted Kremenek31061982009-03-31 23:00:32 +0000670 os << "&&" << "' is ";
Mike Stump1eb44332009-09-09 15:08:12 +0000671
Ted Kremenek31061982009-03-31 23:00:32 +0000672 if (*(Src->succ_begin()+1) == Dst) {
673 os << "false";
Anna Zaks220ac8c2011-09-15 01:08:34 +0000674 PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
Anna Zaks0cd59482011-09-16 19:18:30 +0000675 PathDiagnosticLocation Start =
676 PathDiagnosticLocation::createOperatorLoc(B, SMgr);
Ted Kremenek31061982009-03-31 23:00:32 +0000677 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
678 os.str()));
Mike Stump1eb44332009-09-09 15:08:12 +0000679 }
Ted Kremenek31061982009-03-31 23:00:32 +0000680 else {
681 os << "true";
Anna Zaks220ac8c2011-09-15 01:08:34 +0000682 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
Ted Kremenek31061982009-03-31 23:00:32 +0000683 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
684 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
685 os.str()));
Mike Stump1eb44332009-09-09 15:08:12 +0000686 }
Ted Kremenek31061982009-03-31 23:00:32 +0000687 }
688 else {
John McCall2de56d12010-08-25 11:45:40 +0000689 assert(B->getOpcode() == BO_LOr);
Ted Kremenek31061982009-03-31 23:00:32 +0000690 os << "||" << "' is ";
Mike Stump1eb44332009-09-09 15:08:12 +0000691
Ted Kremenek31061982009-03-31 23:00:32 +0000692 if (*(Src->succ_begin()+1) == Dst) {
693 os << "false";
Anna Zaks220ac8c2011-09-15 01:08:34 +0000694 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
Ted Kremenek31061982009-03-31 23:00:32 +0000695 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
696 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Mike Stump1eb44332009-09-09 15:08:12 +0000697 os.str()));
Ted Kremenek31061982009-03-31 23:00:32 +0000698 }
699 else {
700 os << "true";
Anna Zaks220ac8c2011-09-15 01:08:34 +0000701 PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
Anna Zaks0cd59482011-09-16 19:18:30 +0000702 PathDiagnosticLocation Start =
703 PathDiagnosticLocation::createOperatorLoc(B, SMgr);
Ted Kremenek31061982009-03-31 23:00:32 +0000704 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Mike Stump1eb44332009-09-09 15:08:12 +0000705 os.str()));
Ted Kremenek31061982009-03-31 23:00:32 +0000706 }
707 }
Mike Stump1eb44332009-09-09 15:08:12 +0000708
Ted Kremenek31061982009-03-31 23:00:32 +0000709 break;
710 }
Mike Stump1eb44332009-09-09 15:08:12 +0000711
712 case Stmt::DoStmtClass: {
Ted Kremenek31061982009-03-31 23:00:32 +0000713 if (*(Src->succ_begin()) == Dst) {
714 std::string sbuf;
715 llvm::raw_string_ostream os(sbuf);
Mike Stump1eb44332009-09-09 15:08:12 +0000716
Ted Kremenek31061982009-03-31 23:00:32 +0000717 os << "Loop condition is true. ";
718 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
Mike Stump1eb44332009-09-09 15:08:12 +0000719
Ted Kremenek31061982009-03-31 23:00:32 +0000720 if (const Stmt *S = End.asStmt())
721 End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000722
Ted Kremenek31061982009-03-31 23:00:32 +0000723 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
724 os.str()));
725 }
726 else {
727 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
Mike Stump1eb44332009-09-09 15:08:12 +0000728
Ted Kremenek31061982009-03-31 23:00:32 +0000729 if (const Stmt *S = End.asStmt())
730 End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000731
Ted Kremenek31061982009-03-31 23:00:32 +0000732 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
733 "Loop condition is false. Exiting loop"));
734 }
Mike Stump1eb44332009-09-09 15:08:12 +0000735
Ted Kremenek31061982009-03-31 23:00:32 +0000736 break;
737 }
Mike Stump1eb44332009-09-09 15:08:12 +0000738
Ted Kremenek31061982009-03-31 23:00:32 +0000739 case Stmt::WhileStmtClass:
Mike Stump1eb44332009-09-09 15:08:12 +0000740 case Stmt::ForStmtClass: {
Ted Kremenek31061982009-03-31 23:00:32 +0000741 if (*(Src->succ_begin()+1) == Dst) {
742 std::string sbuf;
743 llvm::raw_string_ostream os(sbuf);
Mike Stump1eb44332009-09-09 15:08:12 +0000744
Ted Kremenek31061982009-03-31 23:00:32 +0000745 os << "Loop condition is false. ";
746 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
747 if (const Stmt *S = End.asStmt())
748 End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000749
Ted Kremenek31061982009-03-31 23:00:32 +0000750 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
751 os.str()));
752 }
753 else {
754 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
755 if (const Stmt *S = End.asStmt())
756 End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000757
Ted Kremenek31061982009-03-31 23:00:32 +0000758 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000759 "Loop condition is true. Entering loop body"));
Ted Kremenek31061982009-03-31 23:00:32 +0000760 }
Mike Stump1eb44332009-09-09 15:08:12 +0000761
Ted Kremenek31061982009-03-31 23:00:32 +0000762 break;
763 }
Mike Stump1eb44332009-09-09 15:08:12 +0000764
Ted Kremenek31061982009-03-31 23:00:32 +0000765 case Stmt::IfStmtClass: {
766 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
Mike Stump1eb44332009-09-09 15:08:12 +0000767
Ted Kremenek31061982009-03-31 23:00:32 +0000768 if (const Stmt *S = End.asStmt())
769 End = PDB.getEnclosingStmtLocation(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000770
Ted Kremenek31061982009-03-31 23:00:32 +0000771 if (*(Src->succ_begin()+1) == Dst)
772 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000773 "Taking false branch"));
Mike Stump1eb44332009-09-09 15:08:12 +0000774 else
Ted Kremenek31061982009-03-31 23:00:32 +0000775 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000776 "Taking true branch"));
Mike Stump1eb44332009-09-09 15:08:12 +0000777
Ted Kremenek31061982009-03-31 23:00:32 +0000778 break;
779 }
780 }
781 }
Mike Stump1eb44332009-09-09 15:08:12 +0000782
Ted Kremenekdd986cc2009-05-07 00:45:33 +0000783 if (NextNode) {
Anna Zaks8e6431a2011-08-18 22:37:56 +0000784 // Add diagnostic pieces from custom visitors.
785 BugReport *R = PDB.getBugReport();
786 for (BugReport::visitor_iterator I = R->visitor_begin(),
787 E = R->visitor_end(); I!=E; ++I) {
788 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R))
Ted Kremenekdd986cc2009-05-07 00:45:33 +0000789 PD.push_front(p);
790 }
Ted Kremenek8966bc12009-05-06 21:39:49 +0000791 }
Mike Stump1eb44332009-09-09 15:08:12 +0000792
Ted Kremenek9c378f72011-08-12 23:37:29 +0000793 if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) {
Ted Kremenek31061982009-03-31 23:00:32 +0000794 // Scan the region bindings, and see if a "notable" symbol has a new
795 // lval binding.
796 ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD);
797 PDB.getStateManager().iterBindings(N->getState(), SNS);
798 }
799 }
Mike Stump1eb44332009-09-09 15:08:12 +0000800
Ted Kremenek14856d72009-04-06 23:06:54 +0000801 // After constructing the full PathDiagnostic, do a pass over it to compact
802 // PathDiagnosticPieces that occur within a macro.
803 CompactPathDiagnostic(PD, PDB.getSourceManager());
Ted Kremenek31061982009-03-31 23:00:32 +0000804}
805
806//===----------------------------------------------------------------------===//
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000807// "Extensive" PathDiagnostic generation.
808//===----------------------------------------------------------------------===//
809
810static bool IsControlFlowExpr(const Stmt *S) {
811 const Expr *E = dyn_cast<Expr>(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000812
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000813 if (!E)
814 return false;
Mike Stump1eb44332009-09-09 15:08:12 +0000815
816 E = E->IgnoreParenCasts();
817
John McCall56ca35d2011-02-17 10:25:35 +0000818 if (isa<AbstractConditionalOperator>(E))
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000819 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000820
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000821 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
822 if (B->isLogicalOp())
823 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000824
825 return false;
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000826}
827
Ted Kremenek14856d72009-04-06 23:06:54 +0000828namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000829class ContextLocation : public PathDiagnosticLocation {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000830 bool IsDead;
831public:
832 ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
833 : PathDiagnosticLocation(L), IsDead(isdead) {}
Mike Stump1eb44332009-09-09 15:08:12 +0000834
835 void markDead() { IsDead = true; }
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000836 bool isDead() const { return IsDead; }
837};
Mike Stump1eb44332009-09-09 15:08:12 +0000838
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000839class EdgeBuilder {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000840 std::vector<ContextLocation> CLocs;
841 typedef std::vector<ContextLocation>::iterator iterator;
Ted Kremenek14856d72009-04-06 23:06:54 +0000842 PathDiagnostic &PD;
843 PathDiagnosticBuilder &PDB;
844 PathDiagnosticLocation PrevLoc;
Mike Stump1eb44332009-09-09 15:08:12 +0000845
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000846 bool IsConsumedExpr(const PathDiagnosticLocation &L);
Mike Stump1eb44332009-09-09 15:08:12 +0000847
Ted Kremenek14856d72009-04-06 23:06:54 +0000848 bool containsLocation(const PathDiagnosticLocation &Container,
849 const PathDiagnosticLocation &Containee);
Mike Stump1eb44332009-09-09 15:08:12 +0000850
Ted Kremenek14856d72009-04-06 23:06:54 +0000851 PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
Mike Stump1eb44332009-09-09 15:08:12 +0000852
Ted Kremenek9650cf32009-05-11 21:42:34 +0000853 PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
854 bool firstCharOnly = false) {
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000855 if (const Stmt *S = L.asStmt()) {
Ted Kremenek9650cf32009-05-11 21:42:34 +0000856 const Stmt *Original = S;
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000857 while (1) {
858 // Adjust the location for some expressions that are best referenced
859 // by one of their subexpressions.
Ted Kremenek9650cf32009-05-11 21:42:34 +0000860 switch (S->getStmtClass()) {
861 default:
862 break;
863 case Stmt::ParenExprClass:
Peter Collingbournef111d932011-04-15 00:35:48 +0000864 case Stmt::GenericSelectionExprClass:
865 S = cast<Expr>(S)->IgnoreParens();
Ted Kremenek9650cf32009-05-11 21:42:34 +0000866 firstCharOnly = true;
867 continue;
John McCall56ca35d2011-02-17 10:25:35 +0000868 case Stmt::BinaryConditionalOperatorClass:
Ted Kremenek9650cf32009-05-11 21:42:34 +0000869 case Stmt::ConditionalOperatorClass:
John McCall56ca35d2011-02-17 10:25:35 +0000870 S = cast<AbstractConditionalOperator>(S)->getCond();
Ted Kremenek9650cf32009-05-11 21:42:34 +0000871 firstCharOnly = true;
872 continue;
873 case Stmt::ChooseExprClass:
874 S = cast<ChooseExpr>(S)->getCond();
875 firstCharOnly = true;
876 continue;
877 case Stmt::BinaryOperatorClass:
878 S = cast<BinaryOperator>(S)->getLHS();
879 firstCharOnly = true;
880 continue;
881 }
Mike Stump1eb44332009-09-09 15:08:12 +0000882
Ted Kremenek9650cf32009-05-11 21:42:34 +0000883 break;
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000884 }
Mike Stump1eb44332009-09-09 15:08:12 +0000885
Ted Kremenek9650cf32009-05-11 21:42:34 +0000886 if (S != Original)
Anna Zaks23803372011-09-20 16:23:37 +0000887 L = PathDiagnosticLocation(S, L.getManager(), PDB.getLocationContext());
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000888 }
Mike Stump1eb44332009-09-09 15:08:12 +0000889
Ted Kremenek9650cf32009-05-11 21:42:34 +0000890 if (firstCharOnly)
Anna Zaks1531bb02011-09-20 01:38:47 +0000891 L = PathDiagnosticLocation::createSingleLocation(L);
Ted Kremenek9650cf32009-05-11 21:42:34 +0000892
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000893 return L;
894 }
Mike Stump1eb44332009-09-09 15:08:12 +0000895
Ted Kremenek14856d72009-04-06 23:06:54 +0000896 void popLocation() {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000897 if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
Ted Kremenek5c7168c2009-04-22 20:36:26 +0000898 // For contexts, we only one the first character as the range.
Ted Kremenek07c015c2009-05-15 02:46:13 +0000899 rawAddEdge(cleanUpLocation(CLocs.back(), true));
Ted Kremenek5c7168c2009-04-22 20:36:26 +0000900 }
Ted Kremenek14856d72009-04-06 23:06:54 +0000901 CLocs.pop_back();
902 }
Mike Stump1eb44332009-09-09 15:08:12 +0000903
Ted Kremenek14856d72009-04-06 23:06:54 +0000904public:
905 EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
906 : PD(pd), PDB(pdb) {
Mike Stump1eb44332009-09-09 15:08:12 +0000907
Ted Kremeneka301a672009-04-22 18:16:20 +0000908 // If the PathDiagnostic already has pieces, add the enclosing statement
909 // of the first piece as a context as well.
Ted Kremenek14856d72009-04-06 23:06:54 +0000910 if (!PD.empty()) {
911 PrevLoc = PD.begin()->getLocation();
Mike Stump1eb44332009-09-09 15:08:12 +0000912
Ted Kremenek14856d72009-04-06 23:06:54 +0000913 if (const Stmt *S = PrevLoc.asStmt())
Ted Kremeneke1baed32009-05-05 23:13:38 +0000914 addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
Ted Kremenek14856d72009-04-06 23:06:54 +0000915 }
916 }
917
918 ~EdgeBuilder() {
919 while (!CLocs.empty()) popLocation();
Anna Zaks0cd59482011-09-16 19:18:30 +0000920
Ted Kremeneka301a672009-04-22 18:16:20 +0000921 // Finally, add an initial edge from the start location of the first
922 // statement (if it doesn't already exist).
Anna Zaks0cd59482011-09-16 19:18:30 +0000923 PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin(
924 PDB.getLocationContext(),
925 PDB.getSourceManager());
926 if (L.isValid())
927 rawAddEdge(L);
Ted Kremenek14856d72009-04-06 23:06:54 +0000928 }
929
930 void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
Mike Stump1eb44332009-09-09 15:08:12 +0000931
Ted Kremenek8bd4d032009-04-28 04:23:15 +0000932 void rawAddEdge(PathDiagnosticLocation NewLoc);
Mike Stump1eb44332009-09-09 15:08:12 +0000933
Ted Kremenek14856d72009-04-06 23:06:54 +0000934 void addContext(const Stmt *S);
Ted Kremeneke1baed32009-05-05 23:13:38 +0000935 void addExtendedContext(const Stmt *S);
Mike Stump1eb44332009-09-09 15:08:12 +0000936};
Ted Kremenek14856d72009-04-06 23:06:54 +0000937} // end anonymous namespace
938
939
940PathDiagnosticLocation
941EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
942 if (const Stmt *S = L.asStmt()) {
943 if (IsControlFlowExpr(S))
944 return L;
Mike Stump1eb44332009-09-09 15:08:12 +0000945
946 return PDB.getEnclosingStmtLocation(S);
Ted Kremenek14856d72009-04-06 23:06:54 +0000947 }
Mike Stump1eb44332009-09-09 15:08:12 +0000948
Ted Kremenek14856d72009-04-06 23:06:54 +0000949 return L;
950}
951
952bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
953 const PathDiagnosticLocation &Containee) {
954
955 if (Container == Containee)
956 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000957
Ted Kremenek14856d72009-04-06 23:06:54 +0000958 if (Container.asDecl())
959 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000960
Ted Kremenek14856d72009-04-06 23:06:54 +0000961 if (const Stmt *S = Containee.asStmt())
962 if (const Stmt *ContainerS = Container.asStmt()) {
963 while (S) {
964 if (S == ContainerS)
965 return true;
966 S = PDB.getParent(S);
967 }
968 return false;
969 }
970
971 // Less accurate: compare using source ranges.
972 SourceRange ContainerR = Container.asRange();
973 SourceRange ContaineeR = Containee.asRange();
Mike Stump1eb44332009-09-09 15:08:12 +0000974
Ted Kremenek14856d72009-04-06 23:06:54 +0000975 SourceManager &SM = PDB.getSourceManager();
Chandler Carruth40278532011-07-25 16:49:02 +0000976 SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin());
977 SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd());
978 SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin());
979 SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd());
Mike Stump1eb44332009-09-09 15:08:12 +0000980
Chandler Carruth64211622011-07-25 21:09:52 +0000981 unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg);
982 unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd);
983 unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg);
984 unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd);
Mike Stump1eb44332009-09-09 15:08:12 +0000985
Ted Kremenek14856d72009-04-06 23:06:54 +0000986 assert(ContainerBegLine <= ContainerEndLine);
Mike Stump1eb44332009-09-09 15:08:12 +0000987 assert(ContaineeBegLine <= ContaineeEndLine);
988
Ted Kremenek14856d72009-04-06 23:06:54 +0000989 return (ContainerBegLine <= ContaineeBegLine &&
990 ContainerEndLine >= ContaineeEndLine &&
991 (ContainerBegLine != ContaineeBegLine ||
Chandler Carrutha77c0312011-07-25 20:57:57 +0000992 SM.getExpansionColumnNumber(ContainerRBeg) <=
993 SM.getExpansionColumnNumber(ContaineeRBeg)) &&
Ted Kremenek14856d72009-04-06 23:06:54 +0000994 (ContainerEndLine != ContaineeEndLine ||
Chandler Carrutha77c0312011-07-25 20:57:57 +0000995 SM.getExpansionColumnNumber(ContainerREnd) >=
996 SM.getExpansionColumnNumber(ContainerREnd)));
Ted Kremenek14856d72009-04-06 23:06:54 +0000997}
998
Ted Kremenek14856d72009-04-06 23:06:54 +0000999void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
1000 if (!PrevLoc.isValid()) {
1001 PrevLoc = NewLoc;
1002 return;
1003 }
Mike Stump1eb44332009-09-09 15:08:12 +00001004
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +00001005 const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
1006 const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
Mike Stump1eb44332009-09-09 15:08:12 +00001007
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +00001008 if (NewLocClean.asLocation() == PrevLocClean.asLocation())
Ted Kremenek14856d72009-04-06 23:06:54 +00001009 return;
Mike Stump1eb44332009-09-09 15:08:12 +00001010
Ted Kremenek14856d72009-04-06 23:06:54 +00001011 // FIXME: Ignore intra-macro edges for now.
Chandler Carruth40278532011-07-25 16:49:02 +00001012 if (NewLocClean.asLocation().getExpansionLoc() ==
1013 PrevLocClean.asLocation().getExpansionLoc())
Ted Kremenek14856d72009-04-06 23:06:54 +00001014 return;
1015
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +00001016 PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1017 PrevLoc = NewLoc;
Ted Kremenek14856d72009-04-06 23:06:54 +00001018}
1019
1020void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
Mike Stump1eb44332009-09-09 15:08:12 +00001021
Ted Kremeneka301a672009-04-22 18:16:20 +00001022 if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1023 return;
Mike Stump1eb44332009-09-09 15:08:12 +00001024
Ted Kremenek14856d72009-04-06 23:06:54 +00001025 const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1026
1027 while (!CLocs.empty()) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001028 ContextLocation &TopContextLoc = CLocs.back();
Mike Stump1eb44332009-09-09 15:08:12 +00001029
Ted Kremenek14856d72009-04-06 23:06:54 +00001030 // Is the top location context the same as the one for the new location?
1031 if (TopContextLoc == CLoc) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001032 if (alwaysAdd) {
Ted Kremenek4c6f8d32009-05-04 18:15:17 +00001033 if (IsConsumedExpr(TopContextLoc) &&
1034 !IsControlFlowExpr(TopContextLoc.asStmt()))
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001035 TopContextLoc.markDead();
1036
Ted Kremenek14856d72009-04-06 23:06:54 +00001037 rawAddEdge(NewLoc);
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001038 }
Ted Kremenek14856d72009-04-06 23:06:54 +00001039
1040 return;
1041 }
1042
1043 if (containsLocation(TopContextLoc, CLoc)) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001044 if (alwaysAdd) {
Ted Kremenek14856d72009-04-06 23:06:54 +00001045 rawAddEdge(NewLoc);
Mike Stump1eb44332009-09-09 15:08:12 +00001046
Ted Kremenek4c6f8d32009-05-04 18:15:17 +00001047 if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001048 CLocs.push_back(ContextLocation(CLoc, true));
1049 return;
1050 }
1051 }
Mike Stump1eb44332009-09-09 15:08:12 +00001052
Ted Kremenek14856d72009-04-06 23:06:54 +00001053 CLocs.push_back(CLoc);
Mike Stump1eb44332009-09-09 15:08:12 +00001054 return;
Ted Kremenek14856d72009-04-06 23:06:54 +00001055 }
1056
1057 // Context does not contain the location. Flush it.
1058 popLocation();
1059 }
Mike Stump1eb44332009-09-09 15:08:12 +00001060
Ted Kremenek5c7168c2009-04-22 20:36:26 +00001061 // If we reach here, there is no enclosing context. Just add the edge.
1062 rawAddEdge(NewLoc);
Ted Kremenek14856d72009-04-06 23:06:54 +00001063}
1064
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001065bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1066 if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
1067 return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
Mike Stump1eb44332009-09-09 15:08:12 +00001068
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001069 return false;
1070}
Mike Stump1eb44332009-09-09 15:08:12 +00001071
Ted Kremeneke1baed32009-05-05 23:13:38 +00001072void EdgeBuilder::addExtendedContext(const Stmt *S) {
1073 if (!S)
1074 return;
Mike Stump1eb44332009-09-09 15:08:12 +00001075
1076 const Stmt *Parent = PDB.getParent(S);
Ted Kremeneke1baed32009-05-05 23:13:38 +00001077 while (Parent) {
1078 if (isa<CompoundStmt>(Parent))
1079 Parent = PDB.getParent(Parent);
1080 else
1081 break;
1082 }
1083
1084 if (Parent) {
1085 switch (Parent->getStmtClass()) {
1086 case Stmt::DoStmtClass:
1087 case Stmt::ObjCAtSynchronizedStmtClass:
1088 addContext(Parent);
1089 default:
1090 break;
1091 }
1092 }
Mike Stump1eb44332009-09-09 15:08:12 +00001093
Ted Kremeneke1baed32009-05-05 23:13:38 +00001094 addContext(S);
1095}
Mike Stump1eb44332009-09-09 15:08:12 +00001096
Ted Kremenek14856d72009-04-06 23:06:54 +00001097void EdgeBuilder::addContext(const Stmt *S) {
1098 if (!S)
1099 return;
1100
Anna Zaks220ac8c2011-09-15 01:08:34 +00001101 PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.getLocationContext());
Mike Stump1eb44332009-09-09 15:08:12 +00001102
Ted Kremenek14856d72009-04-06 23:06:54 +00001103 while (!CLocs.empty()) {
1104 const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1105
1106 // Is the top location context the same as the one for the new location?
1107 if (TopContextLoc == L)
1108 return;
1109
1110 if (containsLocation(TopContextLoc, L)) {
Ted Kremenek14856d72009-04-06 23:06:54 +00001111 CLocs.push_back(L);
Mike Stump1eb44332009-09-09 15:08:12 +00001112 return;
Ted Kremenek14856d72009-04-06 23:06:54 +00001113 }
1114
1115 // Context does not contain the location. Flush it.
1116 popLocation();
1117 }
1118
1119 CLocs.push_back(L);
1120}
1121
1122static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1123 PathDiagnosticBuilder &PDB,
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001124 const ExplodedNode *N) {
Ted Kremenek14856d72009-04-06 23:06:54 +00001125 EdgeBuilder EB(PD, PDB);
Anna Zaks0cd59482011-09-16 19:18:30 +00001126 const SourceManager& SM = PDB.getSourceManager();
Ted Kremenek14856d72009-04-06 23:06:54 +00001127
Ted Kremenek9c378f72011-08-12 23:37:29 +00001128 const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin());
Ted Kremenek14856d72009-04-06 23:06:54 +00001129 while (NextNode) {
1130 N = NextNode;
1131 NextNode = GetPredecessorNode(N);
1132 ProgramPoint P = N->getLocation();
1133
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001134 do {
1135 // Block edges.
1136 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
1137 const CFGBlock &Blk = *BE->getSrc();
1138 const Stmt *Term = Blk.getTerminator();
Mike Stump1eb44332009-09-09 15:08:12 +00001139
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001140 // Are we jumping to the head of a loop? Add a special diagnostic.
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001141 if (const Stmt *Loop = BE->getDst()->getLoopTarget()) {
Anna Zaks0cd59482011-09-16 19:18:30 +00001142 PathDiagnosticLocation L(Loop, SM, PDB.getLocationContext());
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001143 const CompoundStmt *CS = NULL;
Mike Stump1eb44332009-09-09 15:08:12 +00001144
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001145 if (!Term) {
1146 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1147 CS = dyn_cast<CompoundStmt>(FS->getBody());
1148 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
Mike Stump1eb44332009-09-09 15:08:12 +00001149 CS = dyn_cast<CompoundStmt>(WS->getBody());
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001150 }
Mike Stump1eb44332009-09-09 15:08:12 +00001151
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001152 PathDiagnosticEventPiece *p =
1153 new PathDiagnosticEventPiece(L,
Ted Kremenek07c015c2009-05-15 02:46:13 +00001154 "Looping back to the head of the loop");
Mike Stump1eb44332009-09-09 15:08:12 +00001155
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001156 EB.addEdge(p->getLocation(), true);
1157 PD.push_front(p);
Mike Stump1eb44332009-09-09 15:08:12 +00001158
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001159 if (CS) {
Anna Zaks0cd59482011-09-16 19:18:30 +00001160 PathDiagnosticLocation BL =
1161 PathDiagnosticLocation::createEndBrace(CS, SM);
Ted Kremenek07c015c2009-05-15 02:46:13 +00001162 EB.addEdge(BL);
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001163 }
Ted Kremenek8bd4d032009-04-28 04:23:15 +00001164 }
Mike Stump1eb44332009-09-09 15:08:12 +00001165
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001166 if (Term)
1167 EB.addContext(Term);
Mike Stump1eb44332009-09-09 15:08:12 +00001168
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001169 break;
Ted Kremenek14856d72009-04-06 23:06:54 +00001170 }
1171
Mike Stump1eb44332009-09-09 15:08:12 +00001172 if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
Ted Kremenek3c0349e2011-03-01 03:15:10 +00001173 if (const CFGStmt *S = BE->getFirstElement().getAs<CFGStmt>()) {
1174 const Stmt *stmt = S->getStmt();
1175 if (IsControlFlowExpr(stmt)) {
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00001176 // Add the proper context for '&&', '||', and '?'.
Ted Kremenek3c0349e2011-03-01 03:15:10 +00001177 EB.addContext(stmt);
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00001178 }
1179 else
Ted Kremenek3c0349e2011-03-01 03:15:10 +00001180 EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt());
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001181 }
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00001182
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001183 break;
1184 }
1185 } while (0);
Mike Stump1eb44332009-09-09 15:08:12 +00001186
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001187 if (!NextNode)
Ted Kremenek14856d72009-04-06 23:06:54 +00001188 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001189
Anna Zaks8e6431a2011-08-18 22:37:56 +00001190 // Add pieces from custom visitors.
1191 BugReport *R = PDB.getBugReport();
1192 for (BugReport::visitor_iterator I = R->visitor_begin(),
1193 E = R->visitor_end(); I!=E; ++I) {
1194 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
Ted Kremenek8966bc12009-05-06 21:39:49 +00001195 const PathDiagnosticLocation &Loc = p->getLocation();
1196 EB.addEdge(Loc, true);
1197 PD.push_front(p);
1198 if (const Stmt *S = Loc.asStmt())
Mike Stump1eb44332009-09-09 15:08:12 +00001199 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
Ted Kremenek8966bc12009-05-06 21:39:49 +00001200 }
Mike Stump1eb44332009-09-09 15:08:12 +00001201 }
Ted Kremenek14856d72009-04-06 23:06:54 +00001202 }
1203}
1204
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +00001205//===----------------------------------------------------------------------===//
Ted Kremenekcf118d42009-02-04 23:49:09 +00001206// Methods for BugType and subclasses.
1207//===----------------------------------------------------------------------===//
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001208BugType::~BugType() { }
1209
Ted Kremenekcf118d42009-02-04 23:49:09 +00001210void BugType::FlushReports(BugReporter &BR) {}
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001211
David Blaikie99ba9e32011-12-20 02:48:34 +00001212void BuiltinBug::anchor() {}
1213
Ted Kremenekcf118d42009-02-04 23:49:09 +00001214//===----------------------------------------------------------------------===//
1215// Methods for BugReport and subclasses.
1216//===----------------------------------------------------------------------===//
Anna Zakse172e8b2011-08-17 23:00:25 +00001217
David Blaikie99ba9e32011-12-20 02:48:34 +00001218void BugReport::NodeResolver::anchor() {}
1219
Anna Zaks8e6431a2011-08-18 22:37:56 +00001220void BugReport::addVisitor(BugReporterVisitor* visitor) {
1221 if (!visitor)
1222 return;
1223
1224 llvm::FoldingSetNodeID ID;
1225 visitor->Profile(ID);
1226 void *InsertPos;
1227
1228 if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
1229 delete visitor;
1230 return;
1231 }
1232
1233 CallbacksSet.InsertNode(visitor, InsertPos);
1234 Callbacks = F.add(visitor, Callbacks);
1235}
1236
1237BugReport::~BugReport() {
1238 for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) {
Anna Zaksdc757b02011-08-19 23:21:56 +00001239 delete *I;
Anna Zaks8e6431a2011-08-18 22:37:56 +00001240 }
1241}
Anna Zakse172e8b2011-08-17 23:00:25 +00001242
1243void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
1244 hash.AddPointer(&BT);
Anna Zakse172e8b2011-08-17 23:00:25 +00001245 hash.AddString(Description);
Anna Zaks590dd8e2011-09-20 21:38:35 +00001246 if (Location.isValid()) {
1247 Location.Profile(hash);
1248 } else {
1249 assert(ErrorNode);
1250 hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
1251 }
Anna Zakse172e8b2011-08-17 23:00:25 +00001252
1253 for (SmallVectorImpl<SourceRange>::const_iterator I =
1254 Ranges.begin(), E = Ranges.end(); I != E; ++I) {
1255 const SourceRange range = *I;
1256 if (!range.isValid())
1257 continue;
1258 hash.AddInteger(range.getBegin().getRawEncoding());
1259 hash.AddInteger(range.getEnd().getRawEncoding());
1260 }
1261}
Ted Kremenekcf118d42009-02-04 23:49:09 +00001262
Ted Kremenek9c378f72011-08-12 23:37:29 +00001263const Stmt *BugReport::getStmt() const {
Anna Zakse172e8b2011-08-17 23:00:25 +00001264 if (!ErrorNode)
1265 return 0;
1266
Tom Care212f6d32010-09-16 03:50:38 +00001267 ProgramPoint ProgP = ErrorNode->getLocation();
Ted Kremenek5f85e172009-07-22 22:35:28 +00001268 const Stmt *S = NULL;
Mike Stump1eb44332009-09-09 15:08:12 +00001269
Ted Kremenek9c378f72011-08-12 23:37:29 +00001270 if (BlockEntrance *BE = dyn_cast<BlockEntrance>(&ProgP)) {
Zhongxing Xufafd3832009-08-20 01:23:34 +00001271 CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
Zhongxing Xu50d5bc42009-08-18 08:46:04 +00001272 if (BE->getBlock() == &Exit)
Tom Care212f6d32010-09-16 03:50:38 +00001273 S = GetPreviousStmt(ErrorNode);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001274 }
Ted Kremenek5f85e172009-07-22 22:35:28 +00001275 if (!S)
Mike Stump1eb44332009-09-09 15:08:12 +00001276 S = GetStmt(ProgP);
1277
1278 return S;
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001279}
1280
Argyrios Kyrtzidis640ccf02010-12-04 01:12:15 +00001281std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
Anna Zakse172e8b2011-08-17 23:00:25 +00001282BugReport::getRanges() {
1283 // If no custom ranges, add the range of the statement corresponding to
1284 // the error node.
1285 if (Ranges.empty()) {
1286 if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
1287 addRange(E->getSourceRange());
1288 else
1289 return std::make_pair(ranges_iterator(), ranges_iterator());
1290 }
1291
Anna Zaks14924262011-08-24 20:31:06 +00001292 // User-specified absence of range info.
1293 if (Ranges.size() == 1 && !Ranges.begin()->isValid())
1294 return std::make_pair(ranges_iterator(), ranges_iterator());
1295
Anna Zakse172e8b2011-08-17 23:00:25 +00001296 return std::make_pair(Ranges.begin(), Ranges.end());
Ted Kremenekf1ae7052008-04-03 17:57:38 +00001297}
1298
Anna Zaks590dd8e2011-09-20 21:38:35 +00001299PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const {
Anna Zaksb7530a42011-08-17 23:21:23 +00001300 if (ErrorNode) {
Anna Zaks590dd8e2011-09-20 21:38:35 +00001301 assert(!Location.isValid() &&
Anna Zaksb7530a42011-08-17 23:21:23 +00001302 "Either Location or ErrorNode should be specified but not both.");
1303
Ted Kremenek9c378f72011-08-12 23:37:29 +00001304 if (const Stmt *S = GetCurrentOrPreviousStmt(ErrorNode)) {
Anna Zaks590dd8e2011-09-20 21:38:35 +00001305 const LocationContext *LC = ErrorNode->getLocationContext();
1306
Ted Kremenek9b5e5052009-02-27 20:05:10 +00001307 // For member expressions, return the location of the '.' or '->'.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001308 if (const MemberExpr *ME = dyn_cast<MemberExpr>(S))
Anna Zaks590dd8e2011-09-20 21:38:35 +00001309 return PathDiagnosticLocation::createMemberLoc(ME, SM);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001310 // For binary operators, return the location of the operator.
1311 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S))
Anna Zaks590dd8e2011-09-20 21:38:35 +00001312 return PathDiagnosticLocation::createOperatorLoc(B, SM);
Ted Kremenek9b5e5052009-02-27 20:05:10 +00001313
Anna Zaks590dd8e2011-09-20 21:38:35 +00001314 return PathDiagnosticLocation::createBegin(S, SM, LC);
Ted Kremenek9b5e5052009-02-27 20:05:10 +00001315 }
Anna Zaksb7530a42011-08-17 23:21:23 +00001316 } else {
1317 assert(Location.isValid());
1318 return Location;
1319 }
1320
Anna Zaks590dd8e2011-09-20 21:38:35 +00001321 return PathDiagnosticLocation();
Ted Kremenekd2f642b2008-04-14 17:39:48 +00001322}
1323
Ted Kremenekcf118d42009-02-04 23:49:09 +00001324//===----------------------------------------------------------------------===//
1325// Methods for BugReporter and subclasses.
1326//===----------------------------------------------------------------------===//
1327
1328BugReportEquivClass::~BugReportEquivClass() {
Ted Kremenek8966bc12009-05-06 21:39:49 +00001329 for (iterator I=begin(), E=end(); I!=E; ++I) delete *I;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001330}
1331
Zhongxing Xua2f4ec02009-09-05 06:06:49 +00001332GRBugReporter::~GRBugReporter() { }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001333BugReporterData::~BugReporterData() {}
1334
Zhongxing Xu38b02b92009-08-06 06:28:40 +00001335ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001336
Ted Kremenek18c66fd2011-08-15 22:09:50 +00001337ProgramStateManager&
Ted Kremenekcf118d42009-02-04 23:49:09 +00001338GRBugReporter::getStateManager() { return Eng.getStateManager(); }
1339
Anna Zaks3b030a22011-08-19 01:57:09 +00001340BugReporter::~BugReporter() {
1341 FlushReports();
1342
1343 // Free the bug reports we are tracking.
1344 typedef std::vector<BugReportEquivClass *> ContTy;
1345 for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
1346 I != E; ++I) {
1347 delete *I;
1348 }
1349}
Ted Kremenekcf118d42009-02-04 23:49:09 +00001350
1351void BugReporter::FlushReports() {
1352 if (BugTypes.isEmpty())
1353 return;
1354
1355 // First flush the warnings for each BugType. This may end up creating new
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001356 // warnings and new BugTypes.
1357 // FIXME: Only NSErrorChecker needs BugType's FlushReports.
1358 // Turn NSErrorChecker into a proper checker and remove this.
Chris Lattner5f9e2722011-07-23 10:55:15 +00001359 SmallVector<const BugType*, 16> bugTypes;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001360 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001361 bugTypes.push_back(*I);
Chris Lattner5f9e2722011-07-23 10:55:15 +00001362 for (SmallVector<const BugType*, 16>::iterator
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001363 I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
Ted Kremenekcf118d42009-02-04 23:49:09 +00001364 const_cast<BugType*>(*I)->FlushReports(*this);
1365
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001366 typedef llvm::FoldingSet<BugReportEquivClass> SetTy;
1367 for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){
1368 BugReportEquivClass& EQ = *EI;
1369 FlushReport(EQ);
Ted Kremenek94826a72008-04-03 04:59:14 +00001370 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001371
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001372 // BugReporter owns and deletes only BugTypes created implicitly through
1373 // EmitBasicReport.
1374 // FIXME: There are leaks from checkers that assume that the BugTypes they
1375 // create will be destroyed by the BugReporter.
1376 for (llvm::StringMap<BugType*>::iterator
1377 I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I)
1378 delete I->second;
1379
Ted Kremenekcf118d42009-02-04 23:49:09 +00001380 // Remove all references to the BugType objects.
Ted Kremenek3baf6722010-11-24 00:54:37 +00001381 BugTypes = F.getEmptySet();
Ted Kremenekcf118d42009-02-04 23:49:09 +00001382}
1383
1384//===----------------------------------------------------------------------===//
1385// PathDiagnostics generation.
1386//===----------------------------------------------------------------------===//
1387
Zhongxing Xu38b02b92009-08-06 06:28:40 +00001388static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001389 std::pair<ExplodedNode*, unsigned> >
Zhongxing Xu38b02b92009-08-06 06:28:40 +00001390MakeReportGraph(const ExplodedGraph* G,
Chris Lattner5f9e2722011-07-23 10:55:15 +00001391 SmallVectorImpl<const ExplodedNode*> &nodes) {
Mike Stump1eb44332009-09-09 15:08:12 +00001392
Ted Kremenekcf118d42009-02-04 23:49:09 +00001393 // Create the trimmed graph. It will contain the shortest paths from the
Mike Stump1eb44332009-09-09 15:08:12 +00001394 // error nodes to the root. In the new graph we should only have one
Ted Kremenekcf118d42009-02-04 23:49:09 +00001395 // error node unless there are two or more error nodes with the same minimum
1396 // path length.
Zhongxing Xu38b02b92009-08-06 06:28:40 +00001397 ExplodedGraph* GTrim;
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001398 InterExplodedGraphMap* NMap;
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001399
1400 llvm::DenseMap<const void*, const void*> InverseMap;
Ted Kremenek40406fe2010-12-03 06:52:30 +00001401 llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(),
1402 &InverseMap);
Mike Stump1eb44332009-09-09 15:08:12 +00001403
Ted Kremenekcf118d42009-02-04 23:49:09 +00001404 // Create owning pointers for GTrim and NMap just to ensure that they are
1405 // released when this function exists.
Dylan Noblesmith6f42b622012-02-05 02:12:40 +00001406 OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim);
1407 OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap);
Mike Stump1eb44332009-09-09 15:08:12 +00001408
Ted Kremenekcf118d42009-02-04 23:49:09 +00001409 // Find the (first) error node in the trimmed graph. We just need to consult
1410 // the node map (NMap) which maps from nodes in the original graph to nodes
1411 // in the new graph.
Ted Kremenek938332c2009-05-16 01:11:58 +00001412
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001413 std::queue<const ExplodedNode*> WS;
Zhongxing Xu38b02b92009-08-06 06:28:40 +00001414 typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy;
Ted Kremenek938332c2009-05-16 01:11:58 +00001415 IndexMapTy IndexMap;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001416
Ted Kremenek40406fe2010-12-03 06:52:30 +00001417 for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) {
1418 const ExplodedNode *originalNode = nodes[nodeIndex];
1419 if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) {
Ted Kremenek938332c2009-05-16 01:11:58 +00001420 WS.push(N);
Ted Kremenek40406fe2010-12-03 06:52:30 +00001421 IndexMap[originalNode] = nodeIndex;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001422 }
Ted Kremenek40406fe2010-12-03 06:52:30 +00001423 }
Mike Stump1eb44332009-09-09 15:08:12 +00001424
Ted Kremenek938332c2009-05-16 01:11:58 +00001425 assert(!WS.empty() && "No error node found in the trimmed graph.");
Ted Kremenekcf118d42009-02-04 23:49:09 +00001426
1427 // Create a new (third!) graph with a single path. This is the graph
1428 // that will be returned to the caller.
Zhongxing Xuc77a5512010-07-01 07:10:59 +00001429 ExplodedGraph *GNew = new ExplodedGraph();
Mike Stump1eb44332009-09-09 15:08:12 +00001430
Ted Kremenek10aa5542009-03-12 23:41:59 +00001431 // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001432 // to the root node, and then construct a new graph that contains only
1433 // a single path.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001434 llvm::DenseMap<const void*,unsigned> Visited;
Mike Stump1eb44332009-09-09 15:08:12 +00001435
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001436 unsigned cnt = 0;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001437 const ExplodedNode *Root = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001438
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001439 while (!WS.empty()) {
Ted Kremenek9c378f72011-08-12 23:37:29 +00001440 const ExplodedNode *Node = WS.front();
Ted Kremenek10aa5542009-03-12 23:41:59 +00001441 WS.pop();
Mike Stump1eb44332009-09-09 15:08:12 +00001442
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001443 if (Visited.find(Node) != Visited.end())
1444 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001445
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001446 Visited[Node] = cnt++;
Mike Stump1eb44332009-09-09 15:08:12 +00001447
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001448 if (Node->pred_empty()) {
1449 Root = Node;
1450 break;
1451 }
Mike Stump1eb44332009-09-09 15:08:12 +00001452
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001453 for (ExplodedNode::const_pred_iterator I=Node->pred_begin(),
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001454 E=Node->pred_end(); I!=E; ++I)
Ted Kremenek10aa5542009-03-12 23:41:59 +00001455 WS.push(*I);
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001456 }
Mike Stump1eb44332009-09-09 15:08:12 +00001457
Ted Kremenek938332c2009-05-16 01:11:58 +00001458 assert(Root);
Mike Stump1eb44332009-09-09 15:08:12 +00001459
Ted Kremenek10aa5542009-03-12 23:41:59 +00001460 // Now walk from the root down the BFS path, always taking the successor
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001461 // with the lowest number.
Mike Stump1eb44332009-09-09 15:08:12 +00001462 ExplodedNode *Last = 0, *First = 0;
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001463 NodeBackMap *BM = new NodeBackMap();
Ted Kremenek938332c2009-05-16 01:11:58 +00001464 unsigned NodeIndex = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001465
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001466 for ( const ExplodedNode *N = Root ;;) {
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001467 // Lookup the number associated with the current node.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001468 llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
Ted Kremenek938332c2009-05-16 01:11:58 +00001469 assert(I != Visited.end());
Mike Stump1eb44332009-09-09 15:08:12 +00001470
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001471 // Create the equivalent node in the new graph with the same state
1472 // and location.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001473 ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState());
Mike Stump1eb44332009-09-09 15:08:12 +00001474
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001475 // Store the mapping to the original node.
1476 llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
1477 assert(IMitr != InverseMap.end() && "No mapping to original node.");
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001478 (*BM)[NewN] = (const ExplodedNode*) IMitr->second;
Mike Stump1eb44332009-09-09 15:08:12 +00001479
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001480 // Link up the new node with the previous node.
1481 if (Last)
Ted Kremenek5fe4d9d2009-10-07 00:42:52 +00001482 NewN->addPredecessor(Last, *GNew);
Mike Stump1eb44332009-09-09 15:08:12 +00001483
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001484 Last = NewN;
Mike Stump1eb44332009-09-09 15:08:12 +00001485
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001486 // Are we at the final node?
Ted Kremenek938332c2009-05-16 01:11:58 +00001487 IndexMapTy::iterator IMI =
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001488 IndexMap.find((const ExplodedNode*)(IMitr->second));
Ted Kremenek938332c2009-05-16 01:11:58 +00001489 if (IMI != IndexMap.end()) {
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001490 First = NewN;
Ted Kremenek938332c2009-05-16 01:11:58 +00001491 NodeIndex = IMI->second;
Ted Kremenekc1da4412008-06-17 19:14:06 +00001492 break;
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001493 }
Mike Stump1eb44332009-09-09 15:08:12 +00001494
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001495 // Find the next successor node. We choose the node that is marked
1496 // with the lowest DFS number.
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001497 ExplodedNode::const_succ_iterator SI = N->succ_begin();
1498 ExplodedNode::const_succ_iterator SE = N->succ_end();
Ted Kremenekc1da4412008-06-17 19:14:06 +00001499 N = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001500
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001501 for (unsigned MinVal = 0; SI != SE; ++SI) {
Mike Stump1eb44332009-09-09 15:08:12 +00001502
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001503 I = Visited.find(*SI);
Mike Stump1eb44332009-09-09 15:08:12 +00001504
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001505 if (I == Visited.end())
1506 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001507
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001508 if (!N || I->second < MinVal) {
1509 N = *SI;
1510 MinVal = I->second;
Ted Kremenekc1da4412008-06-17 19:14:06 +00001511 }
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001512 }
Mike Stump1eb44332009-09-09 15:08:12 +00001513
Ted Kremenek938332c2009-05-16 01:11:58 +00001514 assert(N);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001515 }
Mike Stump1eb44332009-09-09 15:08:12 +00001516
Ted Kremenek938332c2009-05-16 01:11:58 +00001517 assert(First);
1518
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001519 return std::make_pair(std::make_pair(GNew, BM),
1520 std::make_pair(First, NodeIndex));
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001521}
1522
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001523/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
1524/// and collapses PathDiagosticPieces that are expanded by macros.
1525static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM) {
1526 typedef std::vector<std::pair<PathDiagnosticMacroPiece*, SourceLocation> >
1527 MacroStackTy;
Mike Stump1eb44332009-09-09 15:08:12 +00001528
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001529 typedef std::vector<PathDiagnosticPiece*>
1530 PiecesTy;
Mike Stump1eb44332009-09-09 15:08:12 +00001531
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001532 MacroStackTy MacroStack;
1533 PiecesTy Pieces;
Mike Stump1eb44332009-09-09 15:08:12 +00001534
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001535 for (PathDiagnostic::iterator I = PD.begin(), E = PD.end(); I!=E; ++I) {
1536 // Get the location of the PathDiagnosticPiece.
Mike Stump1eb44332009-09-09 15:08:12 +00001537 const FullSourceLoc Loc = I->getLocation().asLocation();
1538
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001539 // Determine the instantiation location, which is the location we group
1540 // related PathDiagnosticPieces.
Mike Stump1eb44332009-09-09 15:08:12 +00001541 SourceLocation InstantiationLoc = Loc.isMacroID() ?
Chandler Carruth40278532011-07-25 16:49:02 +00001542 SM.getExpansionLoc(Loc) :
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001543 SourceLocation();
Mike Stump1eb44332009-09-09 15:08:12 +00001544
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001545 if (Loc.isFileID()) {
1546 MacroStack.clear();
1547 Pieces.push_back(&*I);
1548 continue;
1549 }
1550
1551 assert(Loc.isMacroID());
Mike Stump1eb44332009-09-09 15:08:12 +00001552
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001553 // Is the PathDiagnosticPiece within the same macro group?
1554 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
1555 MacroStack.back().first->push_back(&*I);
1556 continue;
1557 }
1558
1559 // We aren't in the same group. Are we descending into a new macro
1560 // or are part of an old one?
1561 PathDiagnosticMacroPiece *MacroGroup = 0;
1562
1563 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
Chandler Carruth40278532011-07-25 16:49:02 +00001564 SM.getExpansionLoc(Loc) :
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001565 SourceLocation();
Mike Stump1eb44332009-09-09 15:08:12 +00001566
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001567 // Walk the entire macro stack.
1568 while (!MacroStack.empty()) {
1569 if (InstantiationLoc == MacroStack.back().second) {
1570 MacroGroup = MacroStack.back().first;
1571 break;
1572 }
Mike Stump1eb44332009-09-09 15:08:12 +00001573
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001574 if (ParentInstantiationLoc == MacroStack.back().second) {
1575 MacroGroup = MacroStack.back().first;
1576 break;
1577 }
Mike Stump1eb44332009-09-09 15:08:12 +00001578
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001579 MacroStack.pop_back();
1580 }
Mike Stump1eb44332009-09-09 15:08:12 +00001581
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001582 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
1583 // Create a new macro group and add it to the stack.
Anna Zaks590dd8e2011-09-20 21:38:35 +00001584 PathDiagnosticMacroPiece *NewGroup =
1585 new PathDiagnosticMacroPiece(
1586 PathDiagnosticLocation::createSingleLocation(I->getLocation()));
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001587
1588 if (MacroGroup)
1589 MacroGroup->push_back(NewGroup);
1590 else {
1591 assert(InstantiationLoc.isFileID());
1592 Pieces.push_back(NewGroup);
1593 }
Mike Stump1eb44332009-09-09 15:08:12 +00001594
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001595 MacroGroup = NewGroup;
1596 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
1597 }
1598
1599 // Finally, add the PathDiagnosticPiece to the group.
1600 MacroGroup->push_back(&*I);
1601 }
Mike Stump1eb44332009-09-09 15:08:12 +00001602
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001603 // Now take the pieces and construct a new PathDiagnostic.
1604 PD.resetPath(false);
Mike Stump1eb44332009-09-09 15:08:12 +00001605
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001606 for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) {
1607 if (PathDiagnosticMacroPiece *MP=dyn_cast<PathDiagnosticMacroPiece>(*I))
1608 if (!MP->containsEvent()) {
1609 delete MP;
1610 continue;
1611 }
Mike Stump1eb44332009-09-09 15:08:12 +00001612
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001613 PD.push_back(*I);
1614 }
1615}
1616
Ted Kremenek7dc86642009-03-31 20:22:36 +00001617void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
Chris Lattner5f9e2722011-07-23 10:55:15 +00001618 SmallVectorImpl<BugReport *> &bugReports) {
Mike Stump1eb44332009-09-09 15:08:12 +00001619
Ted Kremenek40406fe2010-12-03 06:52:30 +00001620 assert(!bugReports.empty());
Chris Lattner5f9e2722011-07-23 10:55:15 +00001621 SmallVector<const ExplodedNode *, 10> errorNodes;
1622 for (SmallVectorImpl<BugReport*>::iterator I = bugReports.begin(),
Ted Kremenek40406fe2010-12-03 06:52:30 +00001623 E = bugReports.end(); I != E; ++I) {
1624 errorNodes.push_back((*I)->getErrorNode());
1625 }
Mike Stump1eb44332009-09-09 15:08:12 +00001626
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001627 // Construct a new graph that contains only a single path from the error
Mike Stump1eb44332009-09-09 15:08:12 +00001628 // node to a root.
Zhongxing Xu38b02b92009-08-06 06:28:40 +00001629 const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001630 std::pair<ExplodedNode*, unsigned> >&
Ted Kremenek40406fe2010-12-03 06:52:30 +00001631 GPair = MakeReportGraph(&getGraph(), errorNodes);
Mike Stump1eb44332009-09-09 15:08:12 +00001632
Ted Kremenekcf118d42009-02-04 23:49:09 +00001633 // Find the BugReport with the original location.
Ted Kremenek40406fe2010-12-03 06:52:30 +00001634 assert(GPair.second.second < bugReports.size());
1635 BugReport *R = bugReports[GPair.second.second];
Ted Kremenekcf118d42009-02-04 23:49:09 +00001636 assert(R && "No original report found for sliced graph.");
Mike Stump1eb44332009-09-09 15:08:12 +00001637
Dylan Noblesmith6f42b622012-02-05 02:12:40 +00001638 OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first);
1639 OwningPtr<NodeBackMap> BackMap(GPair.first.second);
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001640 const ExplodedNode *N = GPair.second.first;
Mike Stump1eb44332009-09-09 15:08:12 +00001641
1642 // Start building the path diagnostic...
David Blaikieef3643f2011-09-26 00:51:36 +00001643 PathDiagnosticBuilder PDB(*this, R, BackMap.get(),
1644 getPathDiagnosticConsumer());
Mike Stump1eb44332009-09-09 15:08:12 +00001645
Anna Zaks8e6431a2011-08-18 22:37:56 +00001646 // Register additional node visitors.
Anna Zaks50bbc162011-08-19 22:33:38 +00001647 R->addVisitor(new NilReceiverBRVisitor());
1648 R->addVisitor(new ConditionBRVisitor());
Mike Stump1eb44332009-09-09 15:08:12 +00001649
Anna Zaks23f395e2011-08-20 01:27:22 +00001650 // Generate the very last diagnostic piece - the piece is visible before
1651 // the trace is expanded.
1652 PathDiagnosticPiece *LastPiece = 0;
1653 for (BugReport::visitor_iterator I = R->visitor_begin(),
1654 E = R->visitor_end(); I!=E; ++I) {
1655 if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) {
1656 assert (!LastPiece &&
1657 "There can only be one final piece in a diagnostic.");
1658 LastPiece = Piece;
1659 }
1660 }
1661 if (!LastPiece)
1662 LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
1663 if (LastPiece)
1664 PD.push_back(LastPiece);
1665 else
1666 return;
1667
Ted Kremenek7dc86642009-03-31 20:22:36 +00001668 switch (PDB.getGenerationScheme()) {
David Blaikieef3643f2011-09-26 00:51:36 +00001669 case PathDiagnosticConsumer::Extensive:
Ted Kremenek8966bc12009-05-06 21:39:49 +00001670 GenerateExtensivePathDiagnostic(PD, PDB, N);
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +00001671 break;
David Blaikieef3643f2011-09-26 00:51:36 +00001672 case PathDiagnosticConsumer::Minimal:
Ted Kremenek7dc86642009-03-31 20:22:36 +00001673 GenerateMinimalPathDiagnostic(PD, PDB, N);
1674 break;
1675 }
Ted Kremenek7dc86642009-03-31 20:22:36 +00001676}
1677
Ted Kremenekcf118d42009-02-04 23:49:09 +00001678void BugReporter::Register(BugType *BT) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001679 BugTypes = F.add(BugTypes, BT);
Ted Kremenek76d90c82008-05-16 18:33:14 +00001680}
1681
Mike Stump1eb44332009-09-09 15:08:12 +00001682void BugReporter::EmitReport(BugReport* R) {
Ted Kremenekcf118d42009-02-04 23:49:09 +00001683 // Compute the bug report's hash to determine its equivalence class.
1684 llvm::FoldingSetNodeID ID;
1685 R->Profile(ID);
Mike Stump1eb44332009-09-09 15:08:12 +00001686
1687 // Lookup the equivance class. If there isn't one, create it.
Ted Kremenekcf118d42009-02-04 23:49:09 +00001688 BugType& BT = R->getBugType();
1689 Register(&BT);
1690 void *InsertPos;
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001691 BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
Mike Stump1eb44332009-09-09 15:08:12 +00001692
Ted Kremenekcf118d42009-02-04 23:49:09 +00001693 if (!EQ) {
1694 EQ = new BugReportEquivClass(R);
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001695 EQClasses.InsertNode(EQ, InsertPos);
Anna Zaks3b030a22011-08-19 01:57:09 +00001696 EQClassesVector.push_back(EQ);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001697 }
1698 else
1699 EQ->AddReport(R);
Ted Kremenek61f3e052008-04-03 04:42:52 +00001700}
1701
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001702
1703//===----------------------------------------------------------------------===//
1704// Emitting reports in equivalence classes.
1705//===----------------------------------------------------------------------===//
1706
1707namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00001708struct FRIEC_WLItem {
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001709 const ExplodedNode *N;
1710 ExplodedNode::const_succ_iterator I, E;
1711
1712 FRIEC_WLItem(const ExplodedNode *n)
1713 : N(n), I(N->succ_begin()), E(N->succ_end()) {}
1714};
1715}
1716
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001717static BugReport *
1718FindReportInEquivalenceClass(BugReportEquivClass& EQ,
Chris Lattner5f9e2722011-07-23 10:55:15 +00001719 SmallVectorImpl<BugReport*> &bugReports) {
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001720
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001721 BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
1722 assert(I != E);
1723 BugReport *R = *I;
1724 BugType& BT = R->getBugType();
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001725
Ted Kremenek40406fe2010-12-03 06:52:30 +00001726 // If we don't need to suppress any of the nodes because they are
1727 // post-dominated by a sink, simply add all the nodes in the equivalence class
1728 // to 'Nodes'. Any of the reports will serve as a "representative" report.
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001729 if (!BT.isSuppressOnSink()) {
1730 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
Ted Kremenek9c378f72011-08-12 23:37:29 +00001731 const ExplodedNode *N = I->getErrorNode();
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001732 if (N) {
1733 R = *I;
Ted Kremenek40406fe2010-12-03 06:52:30 +00001734 bugReports.push_back(R);
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001735 }
1736 }
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001737 return R;
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001738 }
1739
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001740 // For bug reports that should be suppressed when all paths are post-dominated
1741 // by a sink node, iterate through the reports in the equivalence class
1742 // until we find one that isn't post-dominated (if one exists). We use a
1743 // DFS traversal of the ExplodedGraph to find a non-sink node. We could write
1744 // this as a recursive function, but we don't want to risk blowing out the
1745 // stack for very long paths.
Ted Kremenek40406fe2010-12-03 06:52:30 +00001746 BugReport *exampleReport = 0;
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001747
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001748 for (; I != E; ++I) {
1749 R = *I;
Ted Kremenek40406fe2010-12-03 06:52:30 +00001750 const ExplodedNode *errorNode = R->getErrorNode();
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001751
Ted Kremenek40406fe2010-12-03 06:52:30 +00001752 if (!errorNode)
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001753 continue;
Ted Kremenek40406fe2010-12-03 06:52:30 +00001754 if (errorNode->isSink()) {
David Blaikieb219cfc2011-09-23 05:06:16 +00001755 llvm_unreachable(
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001756 "BugType::isSuppressSink() should not be 'true' for sink end nodes");
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001757 }
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001758 // No successors? By definition this nodes isn't post-dominated by a sink.
Ted Kremenek40406fe2010-12-03 06:52:30 +00001759 if (errorNode->succ_empty()) {
1760 bugReports.push_back(R);
1761 if (!exampleReport)
1762 exampleReport = R;
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001763 continue;
1764 }
1765
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001766 // At this point we know that 'N' is not a sink and it has at least one
1767 // successor. Use a DFS worklist to find a non-sink end-of-path node.
1768 typedef FRIEC_WLItem WLItem;
Chris Lattner5f9e2722011-07-23 10:55:15 +00001769 typedef SmallVector<WLItem, 10> DFSWorkList;
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001770 llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
1771
1772 DFSWorkList WL;
Ted Kremenek40406fe2010-12-03 06:52:30 +00001773 WL.push_back(errorNode);
1774 Visited[errorNode] = 1;
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001775
1776 while (!WL.empty()) {
1777 WLItem &WI = WL.back();
1778 assert(!WI.N->succ_empty());
1779
1780 for (; WI.I != WI.E; ++WI.I) {
1781 const ExplodedNode *Succ = *WI.I;
1782 // End-of-path node?
1783 if (Succ->succ_empty()) {
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001784 // If we found an end-of-path node that is not a sink.
1785 if (!Succ->isSink()) {
Ted Kremenek40406fe2010-12-03 06:52:30 +00001786 bugReports.push_back(R);
1787 if (!exampleReport)
1788 exampleReport = R;
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001789 WL.clear();
1790 break;
1791 }
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001792 // Found a sink? Continue on to the next successor.
1793 continue;
1794 }
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001795 // Mark the successor as visited. If it hasn't been explored,
1796 // enqueue it to the DFS worklist.
1797 unsigned &mark = Visited[Succ];
1798 if (!mark) {
1799 mark = 1;
1800 WL.push_back(Succ);
1801 break;
1802 }
1803 }
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001804
1805 // The worklist may have been cleared at this point. First
1806 // check if it is empty before checking the last item.
1807 if (!WL.empty() && &WL.back() == &WI)
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001808 WL.pop_back();
1809 }
1810 }
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001811
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001812 // ExampleReport will be NULL if all the nodes in the equivalence class
1813 // were post-dominated by sinks.
Ted Kremenek40406fe2010-12-03 06:52:30 +00001814 return exampleReport;
Ted Kremenek61f52bd2010-09-09 19:05:34 +00001815}
Ted Kremeneke0a58072009-09-18 22:37:37 +00001816
1817//===----------------------------------------------------------------------===//
1818// DiagnosticCache. This is a hack to cache analyzer diagnostics. It
1819// uses global state, which eventually should go elsewhere.
1820//===----------------------------------------------------------------------===//
1821namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00001822class DiagCacheItem : public llvm::FoldingSetNode {
Ted Kremeneke0a58072009-09-18 22:37:37 +00001823 llvm::FoldingSetNodeID ID;
1824public:
1825 DiagCacheItem(BugReport *R, PathDiagnostic *PD) {
Anna Zaks4522e2a2011-09-19 23:44:31 +00001826 R->Profile(ID);
1827 PD->Profile(ID);
Ted Kremeneke0a58072009-09-18 22:37:37 +00001828 }
1829
1830 void Profile(llvm::FoldingSetNodeID &id) {
1831 id = ID;
1832 }
1833
1834 llvm::FoldingSetNodeID &getID() { return ID; }
1835};
1836}
1837
1838static bool IsCachedDiagnostic(BugReport *R, PathDiagnostic *PD) {
1839 // FIXME: Eventually this diagnostic cache should reside in something
1840 // like AnalysisManager instead of being a static variable. This is
1841 // really unsafe in the long term.
1842 typedef llvm::FoldingSet<DiagCacheItem> DiagnosticCache;
1843 static DiagnosticCache DC;
1844
1845 void *InsertPos;
1846 DiagCacheItem *Item = new DiagCacheItem(R, PD);
1847
1848 if (DC.FindNodeOrInsertPos(Item->getID(), InsertPos)) {
1849 delete Item;
1850 return true;
1851 }
1852
1853 DC.InsertNode(Item, InsertPos);
1854 return false;
1855}
1856
Ted Kremenekcf118d42009-02-04 23:49:09 +00001857void BugReporter::FlushReport(BugReportEquivClass& EQ) {
Chris Lattner5f9e2722011-07-23 10:55:15 +00001858 SmallVector<BugReport*, 10> bugReports;
Ted Kremenek40406fe2010-12-03 06:52:30 +00001859 BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
1860 if (!exampleReport)
Ted Kremenek06c9cb42009-09-14 22:01:32 +00001861 return;
1862
David Blaikieef3643f2011-09-26 00:51:36 +00001863 PathDiagnosticConsumer* PD = getPathDiagnosticConsumer();
Mike Stump1eb44332009-09-09 15:08:12 +00001864
Ted Kremenekcf118d42009-02-04 23:49:09 +00001865 // FIXME: Make sure we use the 'R' for the path that was actually used.
Mike Stump1eb44332009-09-09 15:08:12 +00001866 // Probably doesn't make a difference in practice.
Ted Kremenek40406fe2010-12-03 06:52:30 +00001867 BugType& BT = exampleReport->getBugType();
Mike Stump1eb44332009-09-09 15:08:12 +00001868
Dylan Noblesmith6f42b622012-02-05 02:12:40 +00001869 OwningPtr<PathDiagnostic>
Ted Kremenek40406fe2010-12-03 06:52:30 +00001870 D(new PathDiagnostic(exampleReport->getBugType().getName(),
Ted Kremenekda0e8422009-04-29 22:05:03 +00001871 !PD || PD->useVerboseDescription()
Ted Kremenek40406fe2010-12-03 06:52:30 +00001872 ? exampleReport->getDescription()
1873 : exampleReport->getShortDescription(),
Ted Kremenekd49967f2009-04-29 21:58:13 +00001874 BT.getCategory()));
1875
Ted Kremenek40406fe2010-12-03 06:52:30 +00001876 if (!bugReports.empty())
1877 GeneratePathDiagnostic(*D.get(), bugReports);
Mike Stump1eb44332009-09-09 15:08:12 +00001878
Ted Kremenek40406fe2010-12-03 06:52:30 +00001879 if (IsCachedDiagnostic(exampleReport, D.get()))
Ted Kremeneke0a58072009-09-18 22:37:37 +00001880 return;
1881
Ted Kremenek072192b2008-04-30 23:47:44 +00001882 // Get the meta data.
Anna Zaks7f2531c2011-08-22 20:31:28 +00001883 const BugReport::ExtraTextList &Meta =
1884 exampleReport->getExtraText();
1885 for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
1886 e = Meta.end(); i != e; ++i) {
1887 D->addMeta(*i);
1888 }
Ted Kremenek75840e12008-04-18 01:56:37 +00001889
Ted Kremenek3148eb42009-01-24 00:55:43 +00001890 // Emit a summary diagnostic to the regular Diagnostics engine.
Argyrios Kyrtzidis640ccf02010-12-04 01:12:15 +00001891 BugReport::ranges_iterator Beg, End;
1892 llvm::tie(Beg, End) = exampleReport->getRanges();
David Blaikied6471f72011-09-25 23:23:43 +00001893 DiagnosticsEngine &Diag = getDiagnostic();
Ted Kremenekc213b482010-01-15 07:56:51 +00001894
1895 // Search the description for '%', as that will be interpretted as a
1896 // format character by FormatDiagnostics.
Chris Lattner5f9e2722011-07-23 10:55:15 +00001897 StringRef desc = exampleReport->getShortDescription();
Ted Kremenekc213b482010-01-15 07:56:51 +00001898 unsigned ErrorDiag;
1899 {
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +00001900 SmallString<512> TmpStr;
Ted Kremenekc213b482010-01-15 07:56:51 +00001901 llvm::raw_svector_ostream Out(TmpStr);
Chris Lattner5f9e2722011-07-23 10:55:15 +00001902 for (StringRef::iterator I=desc.begin(), E=desc.end(); I!=E; ++I)
Ted Kremenekc213b482010-01-15 07:56:51 +00001903 if (*I == '%')
1904 Out << "%%";
1905 else
1906 Out << *I;
1907
1908 Out.flush();
David Blaikied6471f72011-09-25 23:23:43 +00001909 ErrorDiag = Diag.getCustomDiagID(DiagnosticsEngine::Warning, TmpStr);
Ted Kremenekc213b482010-01-15 07:56:51 +00001910 }
Ted Kremenek57202072008-07-14 17:40:50 +00001911
Argyrios Kyrtzidisb6b7e7b2010-12-03 00:58:10 +00001912 {
Anna Zaks590dd8e2011-09-20 21:38:35 +00001913 DiagnosticBuilder diagBuilder = Diag.Report(
1914 exampleReport->getLocation(getSourceManager()).asLocation(), ErrorDiag);
Argyrios Kyrtzidis640ccf02010-12-04 01:12:15 +00001915 for (BugReport::ranges_iterator I = Beg; I != End; ++I)
Argyrios Kyrtzidisb6b7e7b2010-12-03 00:58:10 +00001916 diagBuilder << *I;
Ted Kremenek2f0e89e2008-04-18 22:56:53 +00001917 }
Ted Kremenek3148eb42009-01-24 00:55:43 +00001918
David Blaikieef3643f2011-09-26 00:51:36 +00001919 // Emit a full diagnostic for the path if we have a PathDiagnosticConsumer.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001920 if (!PD)
1921 return;
Mike Stump1eb44332009-09-09 15:08:12 +00001922
1923 if (D->empty()) {
Anna Zaks590dd8e2011-09-20 21:38:35 +00001924 PathDiagnosticPiece *piece = new PathDiagnosticEventPiece(
1925 exampleReport->getLocation(getSourceManager()),
1926 exampleReport->getDescription());
Ted Kremenek1fbfd5b2009-03-06 23:58:11 +00001927
Ted Kremenek3148eb42009-01-24 00:55:43 +00001928 for ( ; Beg != End; ++Beg) piece->addRange(*Beg);
1929 D->push_back(piece);
1930 }
Mike Stump1eb44332009-09-09 15:08:12 +00001931
Ted Kremenek3148eb42009-01-24 00:55:43 +00001932 PD->HandlePathDiagnostic(D.take());
Ted Kremenek61f3e052008-04-03 04:42:52 +00001933}
Ted Kremenek57202072008-07-14 17:40:50 +00001934
Chris Lattner5f9e2722011-07-23 10:55:15 +00001935void BugReporter::EmitBasicReport(StringRef name, StringRef str,
Anna Zaks590dd8e2011-09-20 21:38:35 +00001936 PathDiagnosticLocation Loc,
Ted Kremenek8c036c72008-09-20 04:23:38 +00001937 SourceRange* RBeg, unsigned NumRanges) {
1938 EmitBasicReport(name, "", str, Loc, RBeg, NumRanges);
1939}
Ted Kremenekcf118d42009-02-04 23:49:09 +00001940
Chris Lattner5f9e2722011-07-23 10:55:15 +00001941void BugReporter::EmitBasicReport(StringRef name,
1942 StringRef category,
Anna Zaks590dd8e2011-09-20 21:38:35 +00001943 StringRef str, PathDiagnosticLocation Loc,
Ted Kremenek8c036c72008-09-20 04:23:38 +00001944 SourceRange* RBeg, unsigned NumRanges) {
Mike Stump1eb44332009-09-09 15:08:12 +00001945
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001946 // 'BT' is owned by BugReporter.
1947 BugType *BT = getBugTypeForName(name, category);
Anna Zaks590dd8e2011-09-20 21:38:35 +00001948 BugReport *R = new BugReport(*BT, str, Loc);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001949 for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
1950 EmitReport(R);
Ted Kremenek57202072008-07-14 17:40:50 +00001951}
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001952
Chris Lattner5f9e2722011-07-23 10:55:15 +00001953BugType *BugReporter::getBugTypeForName(StringRef name,
1954 StringRef category) {
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +00001955 SmallString<136> fullDesc;
Argyrios Kyrtzidis404fc3a2011-02-23 00:16:01 +00001956 llvm::raw_svector_ostream(fullDesc) << name << ":" << category;
1957 llvm::StringMapEntry<BugType *> &
1958 entry = StrBugTypes.GetOrCreateValue(fullDesc);
1959 BugType *BT = entry.getValue();
1960 if (!BT) {
1961 BT = new BugType(name, category);
1962 entry.setValue(BT);
1963 }
1964 return BT;
1965}