blob: 32998e1c4256950ada78bba6e3176db2ff0edb44 [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
11// PathDiagnostics for analyses based on GRSimpleVals.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/Analysis/PathSensitive/BugReporter.h"
Ted Kremenek50a6d0c2008-04-09 21:41:14 +000016#include "clang/Analysis/PathSensitive/GRExprEngine.h"
Ted Kremenek61f3e052008-04-03 04:42:52 +000017#include "clang/AST/ASTContext.h"
18#include "clang/AST/CFG.h"
19#include "clang/AST/Expr.h"
Ted Kremenek00605e02009-03-27 20:55:39 +000020#include "clang/AST/ParentMap.h"
Chris Lattner16f00492009-04-26 01:32:48 +000021#include "clang/AST/StmtObjC.h"
22#include "clang/Basic/SourceManager.h"
Ted Kremenek61f3e052008-04-03 04:42:52 +000023#include "clang/Analysis/ProgramPoint.h"
24#include "clang/Analysis/PathDiagnostic.h"
Chris Lattner405674c2008-08-23 22:23:37 +000025#include "llvm/Support/raw_ostream.h"
Ted Kremenek331b0ac2008-06-18 05:34:07 +000026#include "llvm/ADT/DenseMap.h"
Ted Kremenekcf118d42009-02-04 23:49:09 +000027#include "llvm/ADT/STLExtras.h"
Ted Kremenek00605e02009-03-27 20:55:39 +000028#include "llvm/ADT/OwningPtr.h"
Ted Kremenek10aa5542009-03-12 23:41:59 +000029#include <queue>
Ted Kremenek61f3e052008-04-03 04:42:52 +000030
31using namespace clang;
32
Ted Kremenek8966bc12009-05-06 21:39:49 +000033BugReporterVisitor::~BugReporterVisitor() {}
34BugReporterContext::~BugReporterContext() {
35 for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I)
36 if ((*I)->isOwnedByReporterContext()) delete *I;
37}
38
Ted Kremenekcf118d42009-02-04 23:49:09 +000039//===----------------------------------------------------------------------===//
Ted Kremenek31061982009-03-31 23:00:32 +000040// Helper routines for walking the ExplodedGraph and fetching statements.
Ted Kremenekcf118d42009-02-04 23:49:09 +000041//===----------------------------------------------------------------------===//
Ted Kremenek61f3e052008-04-03 04:42:52 +000042
Ted Kremenekb697b102009-02-23 22:44:26 +000043static inline Stmt* GetStmt(ProgramPoint P) {
44 if (const PostStmt* PS = dyn_cast<PostStmt>(&P))
Ted Kremenek61f3e052008-04-03 04:42:52 +000045 return PS->getStmt();
Ted Kremenekb697b102009-02-23 22:44:26 +000046 else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P))
Ted Kremenek61f3e052008-04-03 04:42:52 +000047 return BE->getSrc()->getTerminator();
Ted Kremenek61f3e052008-04-03 04:42:52 +000048
Ted Kremenekb697b102009-02-23 22:44:26 +000049 return 0;
Ted Kremenek706e3cf2008-04-07 23:35:17 +000050}
51
Ted Kremenek3148eb42009-01-24 00:55:43 +000052static inline const ExplodedNode<GRState>*
Ted Kremenekb697b102009-02-23 22:44:26 +000053GetPredecessorNode(const ExplodedNode<GRState>* N) {
Ted Kremenekbd7efa82008-04-17 23:44:37 +000054 return N->pred_empty() ? NULL : *(N->pred_begin());
55}
Ted Kremenek2673c9f2008-04-25 19:01:27 +000056
Ted Kremenekb697b102009-02-23 22:44:26 +000057static inline const ExplodedNode<GRState>*
58GetSuccessorNode(const ExplodedNode<GRState>* N) {
59 return N->succ_empty() ? NULL : *(N->succ_begin());
Ted Kremenekbd7efa82008-04-17 23:44:37 +000060}
61
Ted Kremenekb697b102009-02-23 22:44:26 +000062static Stmt* GetPreviousStmt(const ExplodedNode<GRState>* N) {
63 for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
64 if (Stmt *S = GetStmt(N->getLocation()))
65 return S;
66
67 return 0;
Ted Kremenek3148eb42009-01-24 00:55:43 +000068}
69
Ted Kremenekb697b102009-02-23 22:44:26 +000070static Stmt* GetNextStmt(const ExplodedNode<GRState>* N) {
71 for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
Ted Kremenekf5ab8e62009-03-28 17:33:57 +000072 if (Stmt *S = GetStmt(N->getLocation())) {
73 // Check if the statement is '?' or '&&'/'||'. These are "merges",
74 // not actual statement points.
75 switch (S->getStmtClass()) {
76 case Stmt::ChooseExprClass:
77 case Stmt::ConditionalOperatorClass: continue;
78 case Stmt::BinaryOperatorClass: {
79 BinaryOperator::Opcode Op = cast<BinaryOperator>(S)->getOpcode();
80 if (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr)
81 continue;
82 break;
83 }
84 default:
85 break;
86 }
Ted Kremenekb697b102009-02-23 22:44:26 +000087 return S;
Ted Kremenekf5ab8e62009-03-28 17:33:57 +000088 }
Ted Kremenekb697b102009-02-23 22:44:26 +000089
90 return 0;
91}
92
93static inline Stmt* GetCurrentOrPreviousStmt(const ExplodedNode<GRState>* N) {
94 if (Stmt *S = GetStmt(N->getLocation()))
95 return S;
96
97 return GetPreviousStmt(N);
98}
99
100static inline Stmt* GetCurrentOrNextStmt(const ExplodedNode<GRState>* N) {
101 if (Stmt *S = GetStmt(N->getLocation()))
102 return S;
103
104 return GetNextStmt(N);
105}
106
107//===----------------------------------------------------------------------===//
Ted Kremenek31061982009-03-31 23:00:32 +0000108// PathDiagnosticBuilder and its associated routines and helper objects.
Ted Kremenekb697b102009-02-23 22:44:26 +0000109//===----------------------------------------------------------------------===//
Ted Kremenekb479dad2009-02-23 23:13:51 +0000110
Ted Kremenek7dc86642009-03-31 20:22:36 +0000111typedef llvm::DenseMap<const ExplodedNode<GRState>*,
112const ExplodedNode<GRState>*> NodeBackMap;
113
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000114namespace {
Ted Kremenek7dc86642009-03-31 20:22:36 +0000115class VISIBILITY_HIDDEN NodeMapClosure : public BugReport::NodeResolver {
116 NodeBackMap& M;
117public:
118 NodeMapClosure(NodeBackMap *m) : M(*m) {}
119 ~NodeMapClosure() {}
120
121 const ExplodedNode<GRState>* getOriginalNode(const ExplodedNode<GRState>* N) {
122 NodeBackMap::iterator I = M.find(N);
123 return I == M.end() ? 0 : I->second;
124 }
125};
126
Ted Kremenek8966bc12009-05-06 21:39:49 +0000127class VISIBILITY_HIDDEN PathDiagnosticBuilder : public BugReporterContext {
Ted Kremenek7dc86642009-03-31 20:22:36 +0000128 BugReport *R;
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000129 PathDiagnosticClient *PDC;
Ted Kremenek00605e02009-03-27 20:55:39 +0000130 llvm::OwningPtr<ParentMap> PM;
Ted Kremenek7dc86642009-03-31 20:22:36 +0000131 NodeMapClosure NMC;
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000132public:
Ted Kremenek8966bc12009-05-06 21:39:49 +0000133 PathDiagnosticBuilder(GRBugReporter &br,
Ted Kremenek7dc86642009-03-31 20:22:36 +0000134 BugReport *r, NodeBackMap *Backmap,
Ted Kremenek8966bc12009-05-06 21:39:49 +0000135 PathDiagnosticClient *pdc)
136 : BugReporterContext(br),
137 R(r), PDC(pdc), NMC(Backmap)
138 {
139 addVisitor(R);
140 }
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000141
Ted Kremenek00605e02009-03-27 20:55:39 +0000142 PathDiagnosticLocation ExecutionContinues(const ExplodedNode<GRState>* N);
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000143
Ted Kremenek00605e02009-03-27 20:55:39 +0000144 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream& os,
145 const ExplodedNode<GRState>* N);
146
147 ParentMap& getParentMap() {
Ted Kremenek8966bc12009-05-06 21:39:49 +0000148 if (PM.get() == 0)
149 PM.reset(new ParentMap(getCodeDecl().getBody(getASTContext())));
Ted Kremenek00605e02009-03-27 20:55:39 +0000150 return *PM.get();
151 }
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000152
Ted Kremenekc3f83ad2009-04-01 17:18:21 +0000153 const Stmt *getParent(const Stmt *S) {
154 return getParentMap().getParent(S);
155 }
Ted Kremenek8966bc12009-05-06 21:39:49 +0000156
157 virtual NodeMapClosure& getNodeResolver() { return NMC; }
Ted Kremenek7dc86642009-03-31 20:22:36 +0000158 BugReport& getReport() { return *R; }
Douglas Gregor72971342009-04-18 00:02:19 +0000159
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000160 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
161
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000162 PathDiagnosticLocation
163 getEnclosingStmtLocation(const PathDiagnosticLocation &L) {
164 if (const Stmt *S = L.asStmt())
165 return getEnclosingStmtLocation(S);
166
167 return L;
168 }
169
Ted Kremenek7dc86642009-03-31 20:22:36 +0000170 PathDiagnosticClient::PathGenerationScheme getGenerationScheme() const {
171 return PDC ? PDC->getGenerationScheme() : PathDiagnosticClient::Extensive;
172 }
173
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000174 bool supportsLogicalOpControlFlow() const {
175 return PDC ? PDC->supportsLogicalOpControlFlow() : true;
176 }
177};
178} // end anonymous namespace
179
Ted Kremenek00605e02009-03-27 20:55:39 +0000180PathDiagnosticLocation
181PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode<GRState>* N) {
182 if (Stmt *S = GetNextStmt(N))
Ted Kremenek8966bc12009-05-06 21:39:49 +0000183 return PathDiagnosticLocation(S, getSourceManager());
Ted Kremenek00605e02009-03-27 20:55:39 +0000184
Ted Kremenek8966bc12009-05-06 21:39:49 +0000185 return FullSourceLoc(getCodeDecl().getBodyRBrace(getASTContext()),
186 getSourceManager());
Ted Kremenek082cb8d2009-03-12 18:41:53 +0000187}
188
Ted Kremenek00605e02009-03-27 20:55:39 +0000189PathDiagnosticLocation
Ted Kremenekbabdd7b2009-03-27 05:06:10 +0000190PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream& os,
191 const ExplodedNode<GRState>* N) {
192
Ted Kremenek143ca222008-05-06 18:11:09 +0000193 // Slow, but probably doesn't matter.
Ted Kremenekb697b102009-02-23 22:44:26 +0000194 if (os.str().empty())
195 os << ' ';
Ted Kremenek143ca222008-05-06 18:11:09 +0000196
Ted Kremenek00605e02009-03-27 20:55:39 +0000197 const PathDiagnosticLocation &Loc = ExecutionContinues(N);
Ted Kremenek082cb8d2009-03-12 18:41:53 +0000198
Ted Kremenek00605e02009-03-27 20:55:39 +0000199 if (Loc.asStmt())
Ted Kremenekb697b102009-02-23 22:44:26 +0000200 os << "Execution continues on line "
Ted Kremenek8966bc12009-05-06 21:39:49 +0000201 << getSourceManager().getInstantiationLineNumber(Loc.asLocation())
202 << '.';
Ted Kremenekb697b102009-02-23 22:44:26 +0000203 else
Ted Kremenekb479dad2009-02-23 23:13:51 +0000204 os << "Execution jumps to the end of the "
Ted Kremenek8966bc12009-05-06 21:39:49 +0000205 << (isa<ObjCMethodDecl>(getCodeDecl()) ? "method" : "function") << '.';
Ted Kremenek082cb8d2009-03-12 18:41:53 +0000206
207 return Loc;
Ted Kremenek143ca222008-05-06 18:11:09 +0000208}
209
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000210static bool IsNested(const Stmt *S, ParentMap &PM) {
211 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
212 return true;
213
214 const Stmt *Parent = PM.getParentIgnoreParens(S);
215
216 if (Parent)
217 switch (Parent->getStmtClass()) {
218 case Stmt::ForStmtClass:
219 case Stmt::DoStmtClass:
220 case Stmt::WhileStmtClass:
221 return true;
222 default:
223 break;
224 }
225
226 return false;
227}
228
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000229PathDiagnosticLocation
230PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
231 assert(S && "Null Stmt* passed to getEnclosingStmtLocation");
Ted Kremenekc42e07e2009-05-05 22:19:17 +0000232 ParentMap &P = getParentMap();
Ted Kremenek8966bc12009-05-06 21:39:49 +0000233 SourceManager &SMgr = getSourceManager();
Ted Kremeneke88a1702009-05-11 22:19:32 +0000234
Ted Kremenekddb7bab2009-05-15 01:50:15 +0000235 while (IsNested(S, P)) {
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000236 const Stmt *Parent = P.getParentIgnoreParens(S);
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000237
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000238 if (!Parent)
239 break;
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000240
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000241 switch (Parent->getStmtClass()) {
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000242 case Stmt::BinaryOperatorClass: {
243 const BinaryOperator *B = cast<BinaryOperator>(Parent);
244 if (B->isLogicalOp())
245 return PathDiagnosticLocation(S, SMgr);
246 break;
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000247 }
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000248 case Stmt::CompoundStmtClass:
249 case Stmt::StmtExprClass:
Ted Kremenek1d9a23a2009-03-28 04:08:14 +0000250 return PathDiagnosticLocation(S, SMgr);
251 case Stmt::ChooseExprClass:
252 // Similar to '?' if we are referring to condition, just have the edge
253 // point to the entire choose expression.
254 if (cast<ChooseExpr>(Parent)->getCond() == S)
255 return PathDiagnosticLocation(Parent, SMgr);
256 else
257 return PathDiagnosticLocation(S, SMgr);
258 case Stmt::ConditionalOperatorClass:
259 // For '?', if we are referring to condition, just have the edge point
260 // to the entire '?' expression.
261 if (cast<ConditionalOperator>(Parent)->getCond() == S)
262 return PathDiagnosticLocation(Parent, SMgr);
263 else
264 return PathDiagnosticLocation(S, SMgr);
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000265 case Stmt::DoStmtClass:
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000266 return PathDiagnosticLocation(S, SMgr);
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000267 case Stmt::ForStmtClass:
268 if (cast<ForStmt>(Parent)->getBody() == S)
269 return PathDiagnosticLocation(S, SMgr);
270 break;
271 case Stmt::IfStmtClass:
272 if (cast<IfStmt>(Parent)->getCond() != S)
273 return PathDiagnosticLocation(S, SMgr);
Ted Kremenek8bd4d032009-04-28 04:23:15 +0000274 break;
Ted Kremenekaf3e3d52009-03-28 03:37:59 +0000275 case Stmt::ObjCForCollectionStmtClass:
276 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
277 return PathDiagnosticLocation(S, SMgr);
278 break;
279 case Stmt::WhileStmtClass:
280 if (cast<WhileStmt>(Parent)->getCond() != S)
281 return PathDiagnosticLocation(S, SMgr);
282 break;
283 default:
284 break;
285 }
286
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000287 S = Parent;
288 }
289
290 assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
Ted Kremeneke88a1702009-05-11 22:19:32 +0000291
292 // Special case: DeclStmts can appear in for statement declarations, in which
293 // case the ForStmt is the context.
294 if (isa<DeclStmt>(S)) {
295 if (const Stmt *Parent = P.getParent(S)) {
296 switch (Parent->getStmtClass()) {
297 case Stmt::ForStmtClass:
298 case Stmt::ObjCForCollectionStmtClass:
299 return PathDiagnosticLocation(Parent, SMgr);
300 default:
301 break;
302 }
303 }
304 }
305 else if (isa<BinaryOperator>(S)) {
306 // Special case: the binary operator represents the initialization
307 // code in a for statement (this can happen when the variable being
308 // initialized is an old variable.
309 if (const ForStmt *FS =
310 dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
311 if (FS->getInit() == S)
312 return PathDiagnosticLocation(FS, SMgr);
313 }
314 }
315
Ted Kremenekd8c938b2009-03-27 21:16:25 +0000316 return PathDiagnosticLocation(S, SMgr);
317}
318
Ted Kremenekcf118d42009-02-04 23:49:09 +0000319//===----------------------------------------------------------------------===//
Ted Kremenek31061982009-03-31 23:00:32 +0000320// ScanNotableSymbols: closure-like callback for scanning Store bindings.
321//===----------------------------------------------------------------------===//
322
323static const VarDecl*
324GetMostRecentVarDeclBinding(const ExplodedNode<GRState>* N,
325 GRStateManager& VMgr, SVal X) {
326
327 for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
328
329 ProgramPoint P = N->getLocation();
330
331 if (!isa<PostStmt>(P))
332 continue;
333
334 DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
335
336 if (!DR)
337 continue;
338
339 SVal Y = VMgr.GetSVal(N->getState(), DR);
340
341 if (X != Y)
342 continue;
343
344 VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl());
345
346 if (!VD)
347 continue;
348
349 return VD;
350 }
351
352 return 0;
353}
354
355namespace {
356class VISIBILITY_HIDDEN NotableSymbolHandler
357: public StoreManager::BindingsHandler {
358
359 SymbolRef Sym;
360 const GRState* PrevSt;
361 const Stmt* S;
362 GRStateManager& VMgr;
363 const ExplodedNode<GRState>* Pred;
364 PathDiagnostic& PD;
365 BugReporter& BR;
366
367public:
368
369 NotableSymbolHandler(SymbolRef sym, const GRState* prevst, const Stmt* s,
370 GRStateManager& vmgr, const ExplodedNode<GRState>* pred,
371 PathDiagnostic& pd, BugReporter& br)
372 : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
373
374 bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
375 SVal V) {
376
377 SymbolRef ScanSym = V.getAsSymbol();
378
379 if (ScanSym != Sym)
380 return true;
381
382 // Check if the previous state has this binding.
383 SVal X = VMgr.GetSVal(PrevSt, loc::MemRegionVal(R));
384
385 if (X == V) // Same binding?
386 return true;
387
388 // Different binding. Only handle assignments for now. We don't pull
389 // this check out of the loop because we will eventually handle other
390 // cases.
391
392 VarDecl *VD = 0;
393
394 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
395 if (!B->isAssignmentOp())
396 return true;
397
398 // What variable did we assign to?
399 DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
400
401 if (!DR)
402 return true;
403
404 VD = dyn_cast<VarDecl>(DR->getDecl());
405 }
406 else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
407 // FIXME: Eventually CFGs won't have DeclStmts. Right now we
408 // assume that each DeclStmt has a single Decl. This invariant
409 // holds by contruction in the CFG.
410 VD = dyn_cast<VarDecl>(*DS->decl_begin());
411 }
412
413 if (!VD)
414 return true;
415
416 // What is the most recently referenced variable with this binding?
417 const VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
418
419 if (!MostRecent)
420 return true;
421
422 // Create the diagnostic.
423 FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
424
425 if (Loc::IsLocType(VD->getType())) {
426 std::string msg = "'" + std::string(VD->getNameAsString()) +
427 "' now aliases '" + MostRecent->getNameAsString() + "'";
428
429 PD.push_front(new PathDiagnosticEventPiece(L, msg));
430 }
431
432 return true;
433 }
434};
435}
436
437static void HandleNotableSymbol(const ExplodedNode<GRState>* N,
438 const Stmt* S,
439 SymbolRef Sym, BugReporter& BR,
440 PathDiagnostic& PD) {
441
442 const ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin();
443 const GRState* PrevSt = Pred ? Pred->getState() : 0;
444
445 if (!PrevSt)
446 return;
447
448 // Look at the region bindings of the current state that map to the
449 // specified symbol. Are any of them not in the previous state?
450 GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
451 NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
452 cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
453}
454
455namespace {
456class VISIBILITY_HIDDEN ScanNotableSymbols
457: public StoreManager::BindingsHandler {
458
459 llvm::SmallSet<SymbolRef, 10> AlreadyProcessed;
460 const ExplodedNode<GRState>* N;
461 Stmt* S;
462 GRBugReporter& BR;
463 PathDiagnostic& PD;
464
465public:
466 ScanNotableSymbols(const ExplodedNode<GRState>* n, Stmt* s, GRBugReporter& br,
467 PathDiagnostic& pd)
468 : N(n), S(s), BR(br), PD(pd) {}
469
470 bool HandleBinding(StoreManager& SMgr, Store store,
471 const MemRegion* R, SVal V) {
472
473 SymbolRef ScanSym = V.getAsSymbol();
474
475 if (!ScanSym)
476 return true;
477
478 if (!BR.isNotable(ScanSym))
479 return true;
480
481 if (AlreadyProcessed.count(ScanSym))
482 return true;
483
484 AlreadyProcessed.insert(ScanSym);
485
486 HandleNotableSymbol(N, S, ScanSym, BR, PD);
487 return true;
488 }
489};
490} // end anonymous namespace
491
492//===----------------------------------------------------------------------===//
493// "Minimal" path diagnostic generation algorithm.
494//===----------------------------------------------------------------------===//
495
Ted Kremenek14856d72009-04-06 23:06:54 +0000496static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM);
497
Ted Kremenek31061982009-03-31 23:00:32 +0000498static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
499 PathDiagnosticBuilder &PDB,
500 const ExplodedNode<GRState> *N) {
Ted Kremenek8966bc12009-05-06 21:39:49 +0000501
Ted Kremenek31061982009-03-31 23:00:32 +0000502 SourceManager& SMgr = PDB.getSourceManager();
503 const ExplodedNode<GRState>* NextNode = N->pred_empty()
504 ? NULL : *(N->pred_begin());
505 while (NextNode) {
506 N = NextNode;
507 NextNode = GetPredecessorNode(N);
508
509 ProgramPoint P = N->getLocation();
510
511 if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
512 CFGBlock* Src = BE->getSrc();
513 CFGBlock* Dst = BE->getDst();
514 Stmt* T = Src->getTerminator();
515
516 if (!T)
517 continue;
518
519 FullSourceLoc Start(T->getLocStart(), SMgr);
520
521 switch (T->getStmtClass()) {
522 default:
523 break;
524
525 case Stmt::GotoStmtClass:
526 case Stmt::IndirectGotoStmtClass: {
527 Stmt* S = GetNextStmt(N);
528
529 if (!S)
530 continue;
531
532 std::string sbuf;
533 llvm::raw_string_ostream os(sbuf);
534 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
535
536 os << "Control jumps to line "
537 << End.asLocation().getInstantiationLineNumber();
538 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
539 os.str()));
540 break;
541 }
542
543 case Stmt::SwitchStmtClass: {
544 // Figure out what case arm we took.
545 std::string sbuf;
546 llvm::raw_string_ostream os(sbuf);
547
548 if (Stmt* S = Dst->getLabel()) {
549 PathDiagnosticLocation End(S, SMgr);
550
551 switch (S->getStmtClass()) {
552 default:
553 os << "No cases match in the switch statement. "
554 "Control jumps to line "
555 << End.asLocation().getInstantiationLineNumber();
556 break;
557 case Stmt::DefaultStmtClass:
558 os << "Control jumps to the 'default' case at line "
559 << End.asLocation().getInstantiationLineNumber();
560 break;
561
562 case Stmt::CaseStmtClass: {
563 os << "Control jumps to 'case ";
564 CaseStmt* Case = cast<CaseStmt>(S);
565 Expr* LHS = Case->getLHS()->IgnoreParenCasts();
566
567 // Determine if it is an enum.
568 bool GetRawInt = true;
569
570 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
571 // FIXME: Maybe this should be an assertion. Are there cases
572 // were it is not an EnumConstantDecl?
573 EnumConstantDecl* D =
574 dyn_cast<EnumConstantDecl>(DR->getDecl());
575
576 if (D) {
577 GetRawInt = false;
578 os << D->getNameAsString();
579 }
580 }
Eli Friedman9ec64d62009-04-26 19:04:51 +0000581
582 if (GetRawInt)
Ted Kremenek8966bc12009-05-06 21:39:49 +0000583 os << LHS->EvaluateAsInt(PDB.getASTContext());
Eli Friedman9ec64d62009-04-26 19:04:51 +0000584
Ted Kremenek31061982009-03-31 23:00:32 +0000585 os << ":' at line "
586 << End.asLocation().getInstantiationLineNumber();
587 break;
588 }
589 }
590 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
591 os.str()));
592 }
593 else {
594 os << "'Default' branch taken. ";
595 const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
596 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
597 os.str()));
598 }
599
600 break;
601 }
602
603 case Stmt::BreakStmtClass:
604 case Stmt::ContinueStmtClass: {
605 std::string sbuf;
606 llvm::raw_string_ostream os(sbuf);
607 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
608 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
609 os.str()));
610 break;
611 }
612
613 // Determine control-flow for ternary '?'.
614 case Stmt::ConditionalOperatorClass: {
615 std::string sbuf;
616 llvm::raw_string_ostream os(sbuf);
617 os << "'?' condition is ";
618
619 if (*(Src->succ_begin()+1) == Dst)
620 os << "false";
621 else
622 os << "true";
623
624 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
625
626 if (const Stmt *S = End.asStmt())
627 End = PDB.getEnclosingStmtLocation(S);
628
629 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
630 os.str()));
631 break;
632 }
633
634 // Determine control-flow for short-circuited '&&' and '||'.
635 case Stmt::BinaryOperatorClass: {
636 if (!PDB.supportsLogicalOpControlFlow())
637 break;
638
639 BinaryOperator *B = cast<BinaryOperator>(T);
640 std::string sbuf;
641 llvm::raw_string_ostream os(sbuf);
642 os << "Left side of '";
643
644 if (B->getOpcode() == BinaryOperator::LAnd) {
645 os << "&&" << "' is ";
646
647 if (*(Src->succ_begin()+1) == Dst) {
648 os << "false";
649 PathDiagnosticLocation End(B->getLHS(), SMgr);
650 PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
651 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
652 os.str()));
653 }
654 else {
655 os << "true";
656 PathDiagnosticLocation Start(B->getLHS(), SMgr);
657 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
658 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
659 os.str()));
660 }
661 }
662 else {
663 assert(B->getOpcode() == BinaryOperator::LOr);
664 os << "||" << "' is ";
665
666 if (*(Src->succ_begin()+1) == Dst) {
667 os << "false";
668 PathDiagnosticLocation Start(B->getLHS(), SMgr);
669 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
670 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
671 os.str()));
672 }
673 else {
674 os << "true";
675 PathDiagnosticLocation End(B->getLHS(), SMgr);
676 PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
677 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
678 os.str()));
679 }
680 }
681
682 break;
683 }
684
685 case Stmt::DoStmtClass: {
686 if (*(Src->succ_begin()) == Dst) {
687 std::string sbuf;
688 llvm::raw_string_ostream os(sbuf);
689
690 os << "Loop condition is true. ";
691 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
692
693 if (const Stmt *S = End.asStmt())
694 End = PDB.getEnclosingStmtLocation(S);
695
696 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
697 os.str()));
698 }
699 else {
700 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
701
702 if (const Stmt *S = End.asStmt())
703 End = PDB.getEnclosingStmtLocation(S);
704
705 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
706 "Loop condition is false. Exiting loop"));
707 }
708
709 break;
710 }
711
712 case Stmt::WhileStmtClass:
713 case Stmt::ForStmtClass: {
714 if (*(Src->succ_begin()+1) == Dst) {
715 std::string sbuf;
716 llvm::raw_string_ostream os(sbuf);
717
718 os << "Loop condition is false. ";
719 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
720 if (const Stmt *S = End.asStmt())
721 End = PDB.getEnclosingStmtLocation(S);
722
723 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
724 os.str()));
725 }
726 else {
727 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
728 if (const Stmt *S = End.asStmt())
729 End = PDB.getEnclosingStmtLocation(S);
730
731 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000732 "Loop condition is true. Entering loop body"));
Ted Kremenek31061982009-03-31 23:00:32 +0000733 }
734
735 break;
736 }
737
738 case Stmt::IfStmtClass: {
739 PathDiagnosticLocation End = PDB.ExecutionContinues(N);
740
741 if (const Stmt *S = End.asStmt())
742 End = PDB.getEnclosingStmtLocation(S);
743
744 if (*(Src->succ_begin()+1) == Dst)
745 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000746 "Taking false branch"));
Ted Kremenek31061982009-03-31 23:00:32 +0000747 else
748 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000749 "Taking true branch"));
Ted Kremenek31061982009-03-31 23:00:32 +0000750
751 break;
752 }
753 }
754 }
755
Ted Kremenekdd986cc2009-05-07 00:45:33 +0000756 if (NextNode) {
757 for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
758 E = PDB.visitor_end(); I!=E; ++I) {
759 if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB))
760 PD.push_front(p);
761 }
Ted Kremenek8966bc12009-05-06 21:39:49 +0000762 }
Ted Kremenek31061982009-03-31 23:00:32 +0000763
764 if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
765 // Scan the region bindings, and see if a "notable" symbol has a new
766 // lval binding.
767 ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD);
768 PDB.getStateManager().iterBindings(N->getState(), SNS);
769 }
770 }
Ted Kremenek14856d72009-04-06 23:06:54 +0000771
772 // After constructing the full PathDiagnostic, do a pass over it to compact
773 // PathDiagnosticPieces that occur within a macro.
774 CompactPathDiagnostic(PD, PDB.getSourceManager());
Ted Kremenek31061982009-03-31 23:00:32 +0000775}
776
777//===----------------------------------------------------------------------===//
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000778// "Extensive" PathDiagnostic generation.
779//===----------------------------------------------------------------------===//
780
781static bool IsControlFlowExpr(const Stmt *S) {
782 const Expr *E = dyn_cast<Expr>(S);
Ted Kremenek14856d72009-04-06 23:06:54 +0000783
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +0000784 if (!E)
785 return false;
786
787 E = E->IgnoreParenCasts();
788
789 if (isa<ConditionalOperator>(E))
790 return true;
791
792 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
793 if (B->isLogicalOp())
794 return true;
795
796 return false;
797}
798
Ted Kremenek14856d72009-04-06 23:06:54 +0000799namespace {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000800class VISIBILITY_HIDDEN ContextLocation : public PathDiagnosticLocation {
801 bool IsDead;
802public:
803 ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
804 : PathDiagnosticLocation(L), IsDead(isdead) {}
805
806 void markDead() { IsDead = true; }
807 bool isDead() const { return IsDead; }
808};
809
Ted Kremenek14856d72009-04-06 23:06:54 +0000810class VISIBILITY_HIDDEN EdgeBuilder {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000811 std::vector<ContextLocation> CLocs;
812 typedef std::vector<ContextLocation>::iterator iterator;
Ted Kremenek14856d72009-04-06 23:06:54 +0000813 PathDiagnostic &PD;
814 PathDiagnosticBuilder &PDB;
815 PathDiagnosticLocation PrevLoc;
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000816
817 bool IsConsumedExpr(const PathDiagnosticLocation &L);
818
Ted Kremenek14856d72009-04-06 23:06:54 +0000819 bool containsLocation(const PathDiagnosticLocation &Container,
820 const PathDiagnosticLocation &Containee);
821
822 PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
Ted Kremenek14856d72009-04-06 23:06:54 +0000823
Ted Kremenek9650cf32009-05-11 21:42:34 +0000824 PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
825 bool firstCharOnly = false) {
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000826 if (const Stmt *S = L.asStmt()) {
Ted Kremenek9650cf32009-05-11 21:42:34 +0000827 const Stmt *Original = S;
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000828 while (1) {
829 // Adjust the location for some expressions that are best referenced
830 // by one of their subexpressions.
Ted Kremenek9650cf32009-05-11 21:42:34 +0000831 switch (S->getStmtClass()) {
832 default:
833 break;
834 case Stmt::ParenExprClass:
835 S = cast<ParenExpr>(S)->IgnoreParens();
836 firstCharOnly = true;
837 continue;
838 case Stmt::ConditionalOperatorClass:
839 S = cast<ConditionalOperator>(S)->getCond();
840 firstCharOnly = true;
841 continue;
842 case Stmt::ChooseExprClass:
843 S = cast<ChooseExpr>(S)->getCond();
844 firstCharOnly = true;
845 continue;
846 case Stmt::BinaryOperatorClass:
847 S = cast<BinaryOperator>(S)->getLHS();
848 firstCharOnly = true;
849 continue;
850 }
851
852 break;
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000853 }
854
Ted Kremenek9650cf32009-05-11 21:42:34 +0000855 if (S != Original)
856 L = PathDiagnosticLocation(S, L.getManager());
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000857 }
858
Ted Kremenek9650cf32009-05-11 21:42:34 +0000859 if (firstCharOnly)
860 L = PathDiagnosticLocation(L.asLocation());
861
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000862 return L;
863 }
864
Ted Kremenek14856d72009-04-06 23:06:54 +0000865 void popLocation() {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +0000866 if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
Ted Kremenek5c7168c2009-04-22 20:36:26 +0000867 // For contexts, we only one the first character as the range.
Ted Kremenek07c015c2009-05-15 02:46:13 +0000868 rawAddEdge(cleanUpLocation(CLocs.back(), true));
Ted Kremenek5c7168c2009-04-22 20:36:26 +0000869 }
Ted Kremenek14856d72009-04-06 23:06:54 +0000870 CLocs.pop_back();
871 }
872
873 PathDiagnosticLocation IgnoreParens(const PathDiagnosticLocation &L);
874
875public:
876 EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
877 : PD(pd), PDB(pdb) {
Ted Kremeneka301a672009-04-22 18:16:20 +0000878
879 // If the PathDiagnostic already has pieces, add the enclosing statement
880 // of the first piece as a context as well.
Ted Kremenek14856d72009-04-06 23:06:54 +0000881 if (!PD.empty()) {
882 PrevLoc = PD.begin()->getLocation();
883
884 if (const Stmt *S = PrevLoc.asStmt())
Ted Kremeneke1baed32009-05-05 23:13:38 +0000885 addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
Ted Kremenek14856d72009-04-06 23:06:54 +0000886 }
887 }
888
889 ~EdgeBuilder() {
890 while (!CLocs.empty()) popLocation();
Ted Kremeneka301a672009-04-22 18:16:20 +0000891
892 // Finally, add an initial edge from the start location of the first
893 // statement (if it doesn't already exist).
Sebastian Redld3a413d2009-04-26 20:35:05 +0000894 // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
895 if (const CompoundStmt *CS =
Ted Kremenek8966bc12009-05-06 21:39:49 +0000896 PDB.getCodeDecl().getCompoundBody(PDB.getASTContext()))
Ted Kremeneka301a672009-04-22 18:16:20 +0000897 if (!CS->body_empty()) {
898 SourceLocation Loc = (*CS->body_begin())->getLocStart();
899 rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager()));
900 }
901
Ted Kremenek14856d72009-04-06 23:06:54 +0000902 }
903
904 void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
905
906 void addEdge(const Stmt *S, bool alwaysAdd = false) {
907 addEdge(PathDiagnosticLocation(S, PDB.getSourceManager()), alwaysAdd);
908 }
909
Ted Kremenek8bd4d032009-04-28 04:23:15 +0000910 void rawAddEdge(PathDiagnosticLocation NewLoc);
911
Ted Kremenek14856d72009-04-06 23:06:54 +0000912 void addContext(const Stmt *S);
Ted Kremeneke1baed32009-05-05 23:13:38 +0000913 void addExtendedContext(const Stmt *S);
Ted Kremenek14856d72009-04-06 23:06:54 +0000914};
915} // end anonymous namespace
916
917
918PathDiagnosticLocation
919EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
920 if (const Stmt *S = L.asStmt()) {
921 if (IsControlFlowExpr(S))
922 return L;
923
924 return PDB.getEnclosingStmtLocation(S);
925 }
926
927 return L;
928}
929
930bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
931 const PathDiagnosticLocation &Containee) {
932
933 if (Container == Containee)
934 return true;
935
936 if (Container.asDecl())
937 return true;
938
939 if (const Stmt *S = Containee.asStmt())
940 if (const Stmt *ContainerS = Container.asStmt()) {
941 while (S) {
942 if (S == ContainerS)
943 return true;
944 S = PDB.getParent(S);
945 }
946 return false;
947 }
948
949 // Less accurate: compare using source ranges.
950 SourceRange ContainerR = Container.asRange();
951 SourceRange ContaineeR = Containee.asRange();
952
953 SourceManager &SM = PDB.getSourceManager();
954 SourceLocation ContainerRBeg = SM.getInstantiationLoc(ContainerR.getBegin());
955 SourceLocation ContainerREnd = SM.getInstantiationLoc(ContainerR.getEnd());
956 SourceLocation ContaineeRBeg = SM.getInstantiationLoc(ContaineeR.getBegin());
957 SourceLocation ContaineeREnd = SM.getInstantiationLoc(ContaineeR.getEnd());
958
959 unsigned ContainerBegLine = SM.getInstantiationLineNumber(ContainerRBeg);
960 unsigned ContainerEndLine = SM.getInstantiationLineNumber(ContainerREnd);
961 unsigned ContaineeBegLine = SM.getInstantiationLineNumber(ContaineeRBeg);
962 unsigned ContaineeEndLine = SM.getInstantiationLineNumber(ContaineeREnd);
963
964 assert(ContainerBegLine <= ContainerEndLine);
965 assert(ContaineeBegLine <= ContaineeEndLine);
966
967 return (ContainerBegLine <= ContaineeBegLine &&
968 ContainerEndLine >= ContaineeEndLine &&
969 (ContainerBegLine != ContaineeBegLine ||
970 SM.getInstantiationColumnNumber(ContainerRBeg) <=
971 SM.getInstantiationColumnNumber(ContaineeRBeg)) &&
972 (ContainerEndLine != ContaineeEndLine ||
973 SM.getInstantiationColumnNumber(ContainerREnd) >=
974 SM.getInstantiationColumnNumber(ContainerREnd)));
975}
976
977PathDiagnosticLocation
978EdgeBuilder::IgnoreParens(const PathDiagnosticLocation &L) {
979 if (const Expr* E = dyn_cast_or_null<Expr>(L.asStmt()))
980 return PathDiagnosticLocation(E->IgnoreParenCasts(),
981 PDB.getSourceManager());
982 return L;
983}
984
985void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
986 if (!PrevLoc.isValid()) {
987 PrevLoc = NewLoc;
988 return;
989 }
990
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000991 const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
992 const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
993
994 if (NewLocClean.asLocation() == PrevLocClean.asLocation())
Ted Kremenek14856d72009-04-06 23:06:54 +0000995 return;
996
997 // FIXME: Ignore intra-macro edges for now.
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +0000998 if (NewLocClean.asLocation().getInstantiationLoc() ==
999 PrevLocClean.asLocation().getInstantiationLoc())
Ted Kremenek14856d72009-04-06 23:06:54 +00001000 return;
1001
Ted Kremenek8c8b0ad2009-05-11 19:50:47 +00001002 PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1003 PrevLoc = NewLoc;
Ted Kremenek14856d72009-04-06 23:06:54 +00001004}
1005
1006void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
Ted Kremeneka301a672009-04-22 18:16:20 +00001007
1008 if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1009 return;
1010
Ted Kremenek14856d72009-04-06 23:06:54 +00001011 const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1012
1013 while (!CLocs.empty()) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001014 ContextLocation &TopContextLoc = CLocs.back();
Ted Kremenek14856d72009-04-06 23:06:54 +00001015
1016 // Is the top location context the same as the one for the new location?
1017 if (TopContextLoc == CLoc) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001018 if (alwaysAdd) {
Ted Kremenek4c6f8d32009-05-04 18:15:17 +00001019 if (IsConsumedExpr(TopContextLoc) &&
1020 !IsControlFlowExpr(TopContextLoc.asStmt()))
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001021 TopContextLoc.markDead();
1022
Ted Kremenek14856d72009-04-06 23:06:54 +00001023 rawAddEdge(NewLoc);
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001024 }
Ted Kremenek14856d72009-04-06 23:06:54 +00001025
1026 return;
1027 }
1028
1029 if (containsLocation(TopContextLoc, CLoc)) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001030 if (alwaysAdd) {
Ted Kremenek14856d72009-04-06 23:06:54 +00001031 rawAddEdge(NewLoc);
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001032
Ted Kremenek4c6f8d32009-05-04 18:15:17 +00001033 if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) {
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001034 CLocs.push_back(ContextLocation(CLoc, true));
1035 return;
1036 }
1037 }
1038
Ted Kremenek14856d72009-04-06 23:06:54 +00001039 CLocs.push_back(CLoc);
1040 return;
1041 }
1042
1043 // Context does not contain the location. Flush it.
1044 popLocation();
1045 }
Ted Kremenek5c7168c2009-04-22 20:36:26 +00001046
1047 // If we reach here, there is no enclosing context. Just add the edge.
1048 rawAddEdge(NewLoc);
Ted Kremenek14856d72009-04-06 23:06:54 +00001049}
1050
Ted Kremenek8f9b1b32009-05-01 16:08:09 +00001051bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1052 if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
1053 return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1054
1055 return false;
1056}
1057
Ted Kremeneke1baed32009-05-05 23:13:38 +00001058void EdgeBuilder::addExtendedContext(const Stmt *S) {
1059 if (!S)
1060 return;
1061
1062 const Stmt *Parent = PDB.getParent(S);
1063 while (Parent) {
1064 if (isa<CompoundStmt>(Parent))
1065 Parent = PDB.getParent(Parent);
1066 else
1067 break;
1068 }
1069
1070 if (Parent) {
1071 switch (Parent->getStmtClass()) {
1072 case Stmt::DoStmtClass:
1073 case Stmt::ObjCAtSynchronizedStmtClass:
1074 addContext(Parent);
1075 default:
1076 break;
1077 }
1078 }
1079
1080 addContext(S);
1081}
1082
Ted Kremenek14856d72009-04-06 23:06:54 +00001083void EdgeBuilder::addContext(const Stmt *S) {
1084 if (!S)
1085 return;
1086
1087 PathDiagnosticLocation L(S, PDB.getSourceManager());
1088
1089 while (!CLocs.empty()) {
1090 const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1091
1092 // Is the top location context the same as the one for the new location?
1093 if (TopContextLoc == L)
1094 return;
1095
1096 if (containsLocation(TopContextLoc, L)) {
Ted Kremenek14856d72009-04-06 23:06:54 +00001097 CLocs.push_back(L);
1098 return;
1099 }
1100
1101 // Context does not contain the location. Flush it.
1102 popLocation();
1103 }
1104
1105 CLocs.push_back(L);
1106}
1107
1108static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1109 PathDiagnosticBuilder &PDB,
1110 const ExplodedNode<GRState> *N) {
1111
1112
1113 EdgeBuilder EB(PD, PDB);
1114
1115 const ExplodedNode<GRState>* NextNode = N->pred_empty()
1116 ? NULL : *(N->pred_begin());
Ted Kremenek14856d72009-04-06 23:06:54 +00001117 while (NextNode) {
1118 N = NextNode;
1119 NextNode = GetPredecessorNode(N);
1120 ProgramPoint P = N->getLocation();
1121
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001122 do {
1123 // Block edges.
1124 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
1125 const CFGBlock &Blk = *BE->getSrc();
1126 const Stmt *Term = Blk.getTerminator();
1127
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001128 // Are we jumping to the head of a loop? Add a special diagnostic.
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001129 if (const Stmt *Loop = BE->getDst()->getLoopTarget()) {
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001130 PathDiagnosticLocation L(Loop, PDB.getSourceManager());
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001131 const CompoundStmt *CS = NULL;
1132
1133 if (!Term) {
1134 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1135 CS = dyn_cast<CompoundStmt>(FS->getBody());
1136 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1137 CS = dyn_cast<CompoundStmt>(WS->getBody());
1138 }
1139
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001140 PathDiagnosticEventPiece *p =
1141 new PathDiagnosticEventPiece(L,
Ted Kremenek07c015c2009-05-15 02:46:13 +00001142 "Looping back to the head of the loop");
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001143
1144 EB.addEdge(p->getLocation(), true);
1145 PD.push_front(p);
1146
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001147 if (CS) {
Ted Kremenek07c015c2009-05-15 02:46:13 +00001148 PathDiagnosticLocation BL(CS->getRBracLoc(),
1149 PDB.getSourceManager());
1150 BL = PathDiagnosticLocation(BL.asLocation());
1151 EB.addEdge(BL);
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001152 }
Ted Kremenek8bd4d032009-04-28 04:23:15 +00001153 }
Ted Kremenekddb7bab2009-05-15 01:50:15 +00001154
1155 if (Term)
1156 EB.addContext(Term);
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001157
1158 break;
Ted Kremenek14856d72009-04-06 23:06:54 +00001159 }
1160
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001161 if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
1162 if (const Stmt* S = BE->getFirstStmt()) {
1163 if (IsControlFlowExpr(S)) {
1164 // Add the proper context for '&&', '||', and '?'.
1165 EB.addContext(S);
1166 }
1167 else
1168 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1169 }
1170
1171 break;
1172 }
1173 } while (0);
1174
1175 if (!NextNode)
Ted Kremenek14856d72009-04-06 23:06:54 +00001176 continue;
Ted Kremenek14856d72009-04-06 23:06:54 +00001177
Ted Kremenek8966bc12009-05-06 21:39:49 +00001178 for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
1179 E = PDB.visitor_end(); I!=E; ++I) {
1180 if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) {
1181 const PathDiagnosticLocation &Loc = p->getLocation();
1182 EB.addEdge(Loc, true);
1183 PD.push_front(p);
1184 if (const Stmt *S = Loc.asStmt())
1185 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1186 }
1187 }
Ted Kremenek14856d72009-04-06 23:06:54 +00001188 }
1189}
1190
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +00001191//===----------------------------------------------------------------------===//
Ted Kremenekcf118d42009-02-04 23:49:09 +00001192// Methods for BugType and subclasses.
1193//===----------------------------------------------------------------------===//
1194BugType::~BugType() {}
1195void BugType::FlushReports(BugReporter &BR) {}
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001196
Ted Kremenekcf118d42009-02-04 23:49:09 +00001197//===----------------------------------------------------------------------===//
1198// Methods for BugReport and subclasses.
1199//===----------------------------------------------------------------------===//
1200BugReport::~BugReport() {}
1201RangedBugReport::~RangedBugReport() {}
1202
1203Stmt* BugReport::getStmt(BugReporter& BR) const {
Ted Kremenek200ed922008-05-02 23:21:21 +00001204 ProgramPoint ProgP = EndNode->getLocation();
Ted Kremenekbd7efa82008-04-17 23:44:37 +00001205 Stmt *S = NULL;
1206
Ted Kremenekcf118d42009-02-04 23:49:09 +00001207 if (BlockEntrance* BE = dyn_cast<BlockEntrance>(&ProgP)) {
Ted Kremenekb697b102009-02-23 22:44:26 +00001208 if (BE->getBlock() == &BR.getCFG()->getExit()) S = GetPreviousStmt(EndNode);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001209 }
1210 if (!S) S = GetStmt(ProgP);
1211
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001212 return S;
1213}
1214
1215PathDiagnosticPiece*
Ted Kremenek8966bc12009-05-06 21:39:49 +00001216BugReport::getEndPath(BugReporterContext& BRC,
Ted Kremenek3148eb42009-01-24 00:55:43 +00001217 const ExplodedNode<GRState>* EndPathNode) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001218
Ted Kremenek8966bc12009-05-06 21:39:49 +00001219 Stmt* S = getStmt(BRC.getBugReporter());
Ted Kremenek61f3e052008-04-03 04:42:52 +00001220
1221 if (!S)
1222 return NULL;
Ted Kremenek3ef538d2009-05-11 23:50:59 +00001223
Ted Kremenekde7161f2008-04-03 18:00:37 +00001224 const SourceRange *Beg, *End;
Ted Kremenek3ef538d2009-05-11 23:50:59 +00001225 getRanges(BRC.getBugReporter(), Beg, End);
1226 PathDiagnosticLocation L(S, BRC.getSourceManager());
Ted Kremenekcf118d42009-02-04 23:49:09 +00001227
Ted Kremenek3ef538d2009-05-11 23:50:59 +00001228 // Only add the statement itself as a range if we didn't specify any
1229 // special ranges for this report.
1230 PathDiagnosticPiece* P = new PathDiagnosticEventPiece(L, getDescription(),
1231 Beg == End);
1232
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001233 for (; Beg != End; ++Beg)
1234 P->addRange(*Beg);
Ted Kremenek61f3e052008-04-03 04:42:52 +00001235
1236 return P;
1237}
1238
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001239void BugReport::getRanges(BugReporter& BR, const SourceRange*& beg,
1240 const SourceRange*& end) {
1241
1242 if (Expr* E = dyn_cast_or_null<Expr>(getStmt(BR))) {
1243 R = E->getSourceRange();
Ted Kremenek9b5e5052009-02-27 20:05:10 +00001244 assert(R.isValid());
Ted Kremenekbb77e9b2008-05-01 22:50:36 +00001245 beg = &R;
1246 end = beg+1;
1247 }
1248 else
1249 beg = end = 0;
Ted Kremenekf1ae7052008-04-03 17:57:38 +00001250}
1251
Ted Kremenekcf118d42009-02-04 23:49:09 +00001252SourceLocation BugReport::getLocation() const {
1253 if (EndNode)
Ted Kremenek9b5e5052009-02-27 20:05:10 +00001254 if (Stmt* S = GetCurrentOrPreviousStmt(EndNode)) {
1255 // For member expressions, return the location of the '.' or '->'.
1256 if (MemberExpr* ME = dyn_cast<MemberExpr>(S))
1257 return ME->getMemberLoc();
1258
Ted Kremenekcf118d42009-02-04 23:49:09 +00001259 return S->getLocStart();
Ted Kremenek9b5e5052009-02-27 20:05:10 +00001260 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001261
1262 return FullSourceLoc();
Ted Kremenekd2f642b2008-04-14 17:39:48 +00001263}
1264
Ted Kremenek3148eb42009-01-24 00:55:43 +00001265PathDiagnosticPiece* BugReport::VisitNode(const ExplodedNode<GRState>* N,
1266 const ExplodedNode<GRState>* PrevN,
Ted Kremenek8966bc12009-05-06 21:39:49 +00001267 BugReporterContext &BRC) {
Ted Kremenek50a6d0c2008-04-09 21:41:14 +00001268 return NULL;
1269}
1270
Ted Kremenekcf118d42009-02-04 23:49:09 +00001271//===----------------------------------------------------------------------===//
1272// Methods for BugReporter and subclasses.
1273//===----------------------------------------------------------------------===//
1274
1275BugReportEquivClass::~BugReportEquivClass() {
Ted Kremenek8966bc12009-05-06 21:39:49 +00001276 for (iterator I=begin(), E=end(); I!=E; ++I) delete *I;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001277}
1278
1279GRBugReporter::~GRBugReporter() { FlushReports(); }
1280BugReporterData::~BugReporterData() {}
1281
1282ExplodedGraph<GRState>&
1283GRBugReporter::getGraph() { return Eng.getGraph(); }
1284
1285GRStateManager&
1286GRBugReporter::getStateManager() { return Eng.getStateManager(); }
1287
1288BugReporter::~BugReporter() { FlushReports(); }
1289
1290void BugReporter::FlushReports() {
1291 if (BugTypes.isEmpty())
1292 return;
1293
1294 // First flush the warnings for each BugType. This may end up creating new
1295 // warnings and new BugTypes. Because ImmutableSet is a functional data
1296 // structure, we do not need to worry about the iterators being invalidated.
1297 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
1298 const_cast<BugType*>(*I)->FlushReports(*this);
1299
1300 // Iterate through BugTypes a second time. BugTypes may have been updated
1301 // with new BugType objects and new warnings.
1302 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) {
1303 BugType *BT = const_cast<BugType*>(*I);
1304
1305 typedef llvm::FoldingSet<BugReportEquivClass> SetTy;
1306 SetTy& EQClasses = BT->EQClasses;
1307
1308 for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){
1309 BugReportEquivClass& EQ = *EI;
1310 FlushReport(EQ);
1311 }
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001312
Ted Kremenekcf118d42009-02-04 23:49:09 +00001313 // Delete the BugType object. This will also delete the equivalence
1314 // classes.
1315 delete BT;
Ted Kremenek94826a72008-04-03 04:59:14 +00001316 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001317
1318 // Remove all references to the BugType objects.
1319 BugTypes = F.GetEmptySet();
1320}
1321
1322//===----------------------------------------------------------------------===//
1323// PathDiagnostics generation.
1324//===----------------------------------------------------------------------===//
1325
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001326static std::pair<std::pair<ExplodedGraph<GRState>*, NodeBackMap*>,
Ted Kremenekcf118d42009-02-04 23:49:09 +00001327 std::pair<ExplodedNode<GRState>*, unsigned> >
1328MakeReportGraph(const ExplodedGraph<GRState>* G,
1329 const ExplodedNode<GRState>** NStart,
1330 const ExplodedNode<GRState>** NEnd) {
Ted Kremenek94826a72008-04-03 04:59:14 +00001331
Ted Kremenekcf118d42009-02-04 23:49:09 +00001332 // Create the trimmed graph. It will contain the shortest paths from the
1333 // error nodes to the root. In the new graph we should only have one
1334 // error node unless there are two or more error nodes with the same minimum
1335 // path length.
1336 ExplodedGraph<GRState>* GTrim;
1337 InterExplodedGraphMap<GRState>* NMap;
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001338
1339 llvm::DenseMap<const void*, const void*> InverseMap;
1340 llvm::tie(GTrim, NMap) = G->Trim(NStart, NEnd, &InverseMap);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001341
1342 // Create owning pointers for GTrim and NMap just to ensure that they are
1343 // released when this function exists.
1344 llvm::OwningPtr<ExplodedGraph<GRState> > AutoReleaseGTrim(GTrim);
1345 llvm::OwningPtr<InterExplodedGraphMap<GRState> > AutoReleaseNMap(NMap);
1346
1347 // Find the (first) error node in the trimmed graph. We just need to consult
1348 // the node map (NMap) which maps from nodes in the original graph to nodes
1349 // in the new graph.
Ted Kremenek938332c2009-05-16 01:11:58 +00001350
1351 std::queue<const ExplodedNode<GRState>*> WS;
1352 typedef llvm::DenseMap<const ExplodedNode<GRState>*,unsigned> IndexMapTy;
1353 IndexMapTy IndexMap;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001354
1355 for (const ExplodedNode<GRState>** I = NStart; I != NEnd; ++I)
Ted Kremenek938332c2009-05-16 01:11:58 +00001356 if (const ExplodedNode<GRState> *N = NMap->getMappedNode(*I)) {
1357 unsigned NodeIndex = (I - NStart) / sizeof(*I);
1358 WS.push(N);
1359 IndexMap[*I] = NodeIndex;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001360 }
1361
Ted Kremenek938332c2009-05-16 01:11:58 +00001362 assert(!WS.empty() && "No error node found in the trimmed graph.");
Ted Kremenekcf118d42009-02-04 23:49:09 +00001363
1364 // Create a new (third!) graph with a single path. This is the graph
1365 // that will be returned to the caller.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001366 ExplodedGraph<GRState> *GNew =
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001367 new ExplodedGraph<GRState>(GTrim->getCFG(), GTrim->getCodeDecl(),
1368 GTrim->getContext());
Ted Kremenekcf118d42009-02-04 23:49:09 +00001369
Ted Kremenek10aa5542009-03-12 23:41:59 +00001370 // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001371 // to the root node, and then construct a new graph that contains only
1372 // a single path.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001373 llvm::DenseMap<const void*,unsigned> Visited;
Ted Kremenek10aa5542009-03-12 23:41:59 +00001374
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001375 unsigned cnt = 0;
Ted Kremenek3148eb42009-01-24 00:55:43 +00001376 const ExplodedNode<GRState>* Root = 0;
Ted Kremenekc1da4412008-06-17 19:14:06 +00001377
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001378 while (!WS.empty()) {
Ted Kremenek10aa5542009-03-12 23:41:59 +00001379 const ExplodedNode<GRState>* Node = WS.front();
1380 WS.pop();
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001381
1382 if (Visited.find(Node) != Visited.end())
1383 continue;
1384
1385 Visited[Node] = cnt++;
1386
1387 if (Node->pred_empty()) {
1388 Root = Node;
1389 break;
1390 }
1391
Ted Kremenek3148eb42009-01-24 00:55:43 +00001392 for (ExplodedNode<GRState>::const_pred_iterator I=Node->pred_begin(),
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001393 E=Node->pred_end(); I!=E; ++I)
Ted Kremenek10aa5542009-03-12 23:41:59 +00001394 WS.push(*I);
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001395 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001396
Ted Kremenek938332c2009-05-16 01:11:58 +00001397 assert(Root);
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001398
Ted Kremenek10aa5542009-03-12 23:41:59 +00001399 // Now walk from the root down the BFS path, always taking the successor
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001400 // with the lowest number.
Ted Kremenek4adc81e2008-08-13 04:27:00 +00001401 ExplodedNode<GRState> *Last = 0, *First = 0;
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001402 NodeBackMap *BM = new NodeBackMap();
Ted Kremenek938332c2009-05-16 01:11:58 +00001403 unsigned NodeIndex = 0;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001404
Ted Kremenek938332c2009-05-16 01:11:58 +00001405 for ( const ExplodedNode<GRState> *N = Root ;;) {
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001406 // Lookup the number associated with the current node.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001407 llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
Ted Kremenek938332c2009-05-16 01:11:58 +00001408 assert(I != Visited.end());
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001409
1410 // Create the equivalent node in the new graph with the same state
1411 // and location.
Ted Kremenek4adc81e2008-08-13 04:27:00 +00001412 ExplodedNode<GRState>* NewN =
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001413 GNew->getNode(N->getLocation(), N->getState());
1414
1415 // Store the mapping to the original node.
1416 llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
1417 assert(IMitr != InverseMap.end() && "No mapping to original node.");
1418 (*BM)[NewN] = (const ExplodedNode<GRState>*) IMitr->second;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001419
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001420 // Link up the new node with the previous node.
1421 if (Last)
1422 NewN->addPredecessor(Last);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001423
1424 Last = NewN;
Ted Kremenekcf118d42009-02-04 23:49:09 +00001425
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001426 // Are we at the final node?
Ted Kremenek938332c2009-05-16 01:11:58 +00001427 IndexMapTy::iterator IMI =
1428 IndexMap.find((const ExplodedNode<GRState>*)(IMitr->second));
1429 if (IMI != IndexMap.end()) {
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001430 First = NewN;
Ted Kremenek938332c2009-05-16 01:11:58 +00001431 NodeIndex = IMI->second;
Ted Kremenekc1da4412008-06-17 19:14:06 +00001432 break;
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001433 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001434
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001435 // Find the next successor node. We choose the node that is marked
1436 // with the lowest DFS number.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001437 ExplodedNode<GRState>::const_succ_iterator SI = N->succ_begin();
1438 ExplodedNode<GRState>::const_succ_iterator SE = N->succ_end();
Ted Kremenekc1da4412008-06-17 19:14:06 +00001439 N = 0;
1440
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001441 for (unsigned MinVal = 0; SI != SE; ++SI) {
Ted Kremenekcf118d42009-02-04 23:49:09 +00001442
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001443 I = Visited.find(*SI);
1444
1445 if (I == Visited.end())
1446 continue;
1447
1448 if (!N || I->second < MinVal) {
1449 N = *SI;
1450 MinVal = I->second;
Ted Kremenekc1da4412008-06-17 19:14:06 +00001451 }
Ted Kremenek331b0ac2008-06-18 05:34:07 +00001452 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001453
Ted Kremenek938332c2009-05-16 01:11:58 +00001454 assert(N);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001455 }
Ted Kremenekcf118d42009-02-04 23:49:09 +00001456
Ted Kremenek938332c2009-05-16 01:11:58 +00001457 assert(First);
1458
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001459 return std::make_pair(std::make_pair(GNew, BM),
1460 std::make_pair(First, NodeIndex));
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001461}
1462
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001463/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
1464/// and collapses PathDiagosticPieces that are expanded by macros.
1465static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM) {
1466 typedef std::vector<std::pair<PathDiagnosticMacroPiece*, SourceLocation> >
1467 MacroStackTy;
1468
1469 typedef std::vector<PathDiagnosticPiece*>
1470 PiecesTy;
1471
1472 MacroStackTy MacroStack;
1473 PiecesTy Pieces;
1474
1475 for (PathDiagnostic::iterator I = PD.begin(), E = PD.end(); I!=E; ++I) {
1476 // Get the location of the PathDiagnosticPiece.
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +00001477 const FullSourceLoc Loc = I->getLocation().asLocation();
Ted Kremenek0e5c8d42009-03-10 05:16:17 +00001478
1479 // Determine the instantiation location, which is the location we group
1480 // related PathDiagnosticPieces.
1481 SourceLocation InstantiationLoc = Loc.isMacroID() ?
1482 SM.getInstantiationLoc(Loc) :
1483 SourceLocation();
1484
1485 if (Loc.isFileID()) {
1486 MacroStack.clear();
1487 Pieces.push_back(&*I);
1488 continue;
1489 }
1490
1491 assert(Loc.isMacroID());
1492
1493 // Is the PathDiagnosticPiece within the same macro group?
1494 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
1495 MacroStack.back().first->push_back(&*I);
1496 continue;
1497 }
1498
1499 // We aren't in the same group. Are we descending into a new macro
1500 // or are part of an old one?
1501 PathDiagnosticMacroPiece *MacroGroup = 0;
1502
1503 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
1504 SM.getInstantiationLoc(Loc) :
1505 SourceLocation();
1506
1507 // Walk the entire macro stack.
1508 while (!MacroStack.empty()) {
1509 if (InstantiationLoc == MacroStack.back().second) {
1510 MacroGroup = MacroStack.back().first;
1511 break;
1512 }
1513
1514 if (ParentInstantiationLoc == MacroStack.back().second) {
1515 MacroGroup = MacroStack.back().first;
1516 break;
1517 }
1518
1519 MacroStack.pop_back();
1520 }
1521
1522 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
1523 // Create a new macro group and add it to the stack.
1524 PathDiagnosticMacroPiece *NewGroup = new PathDiagnosticMacroPiece(Loc);
1525
1526 if (MacroGroup)
1527 MacroGroup->push_back(NewGroup);
1528 else {
1529 assert(InstantiationLoc.isFileID());
1530 Pieces.push_back(NewGroup);
1531 }
1532
1533 MacroGroup = NewGroup;
1534 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
1535 }
1536
1537 // Finally, add the PathDiagnosticPiece to the group.
1538 MacroGroup->push_back(&*I);
1539 }
1540
1541 // Now take the pieces and construct a new PathDiagnostic.
1542 PD.resetPath(false);
1543
1544 for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) {
1545 if (PathDiagnosticMacroPiece *MP=dyn_cast<PathDiagnosticMacroPiece>(*I))
1546 if (!MP->containsEvent()) {
1547 delete MP;
1548 continue;
1549 }
1550
1551 PD.push_back(*I);
1552 }
1553}
1554
Ted Kremenek7dc86642009-03-31 20:22:36 +00001555void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
Ted Kremenek8966bc12009-05-06 21:39:49 +00001556 BugReportEquivClass& EQ) {
Ted Kremenek7dc86642009-03-31 20:22:36 +00001557
1558 std::vector<const ExplodedNode<GRState>*> Nodes;
1559
Ted Kremenekcf118d42009-02-04 23:49:09 +00001560 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
1561 const ExplodedNode<GRState>* N = I->getEndNode();
1562 if (N) Nodes.push_back(N);
1563 }
1564
1565 if (Nodes.empty())
1566 return;
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001567
1568 // Construct a new graph that contains only a single path from the error
Ted Kremenekcf118d42009-02-04 23:49:09 +00001569 // node to a root.
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001570 const std::pair<std::pair<ExplodedGraph<GRState>*, NodeBackMap*>,
Ted Kremenek7dc86642009-03-31 20:22:36 +00001571 std::pair<ExplodedNode<GRState>*, unsigned> >&
1572 GPair = MakeReportGraph(&getGraph(), &Nodes[0], &Nodes[0] + Nodes.size());
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001573
Ted Kremenekcf118d42009-02-04 23:49:09 +00001574 // Find the BugReport with the original location.
1575 BugReport *R = 0;
1576 unsigned i = 0;
1577 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I, ++i)
1578 if (i == GPair.second.second) { R = *I; break; }
1579
1580 assert(R && "No original report found for sliced graph.");
Ted Kremeneka43a1eb2008-04-23 23:02:12 +00001581
Ted Kremenekfe9e5432009-02-18 03:48:14 +00001582 llvm::OwningPtr<ExplodedGraph<GRState> > ReportGraph(GPair.first.first);
1583 llvm::OwningPtr<NodeBackMap> BackMap(GPair.first.second);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001584 const ExplodedNode<GRState> *N = GPair.second.first;
Ted Kremenek7dc86642009-03-31 20:22:36 +00001585
Ted Kremenek8966bc12009-05-06 21:39:49 +00001586 // Start building the path diagnostic...
1587 PathDiagnosticBuilder PDB(*this, R, BackMap.get(), getPathDiagnosticClient());
1588
1589 if (PathDiagnosticPiece* Piece = R->getEndPath(PDB, N))
Ted Kremenekbd7efa82008-04-17 23:44:37 +00001590 PD.push_back(Piece);
1591 else
1592 return;
Ted Kremenekdd986cc2009-05-07 00:45:33 +00001593
1594 R->registerInitialVisitors(PDB, N);
Ted Kremenekbd7efa82008-04-17 23:44:37 +00001595
Ted Kremenek7dc86642009-03-31 20:22:36 +00001596 switch (PDB.getGenerationScheme()) {
1597 case PathDiagnosticClient::Extensive:
Ted Kremenek8966bc12009-05-06 21:39:49 +00001598 GenerateExtensivePathDiagnostic(PD, PDB, N);
Ted Kremenek5fb5dfb2009-04-01 06:13:56 +00001599 break;
Ted Kremenek7dc86642009-03-31 20:22:36 +00001600 case PathDiagnosticClient::Minimal:
1601 GenerateMinimalPathDiagnostic(PD, PDB, N);
1602 break;
1603 }
Ted Kremenek7dc86642009-03-31 20:22:36 +00001604}
1605
Ted Kremenekcf118d42009-02-04 23:49:09 +00001606void BugReporter::Register(BugType *BT) {
1607 BugTypes = F.Add(BugTypes, BT);
Ted Kremenek76d90c82008-05-16 18:33:14 +00001608}
1609
Ted Kremenekcf118d42009-02-04 23:49:09 +00001610void BugReporter::EmitReport(BugReport* R) {
1611 // Compute the bug report's hash to determine its equivalence class.
1612 llvm::FoldingSetNodeID ID;
1613 R->Profile(ID);
Ted Kremenek61f3e052008-04-03 04:42:52 +00001614
Ted Kremenekcf118d42009-02-04 23:49:09 +00001615 // Lookup the equivance class. If there isn't one, create it.
1616 BugType& BT = R->getBugType();
1617 Register(&BT);
1618 void *InsertPos;
1619 BugReportEquivClass* EQ = BT.EQClasses.FindNodeOrInsertPos(ID, InsertPos);
1620
1621 if (!EQ) {
1622 EQ = new BugReportEquivClass(R);
1623 BT.EQClasses.InsertNode(EQ, InsertPos);
1624 }
1625 else
1626 EQ->AddReport(R);
Ted Kremenek61f3e052008-04-03 04:42:52 +00001627}
1628
Ted Kremenekcf118d42009-02-04 23:49:09 +00001629void BugReporter::FlushReport(BugReportEquivClass& EQ) {
1630 assert(!EQ.Reports.empty());
1631 BugReport &R = **EQ.begin();
Ted Kremenekd49967f2009-04-29 21:58:13 +00001632 PathDiagnosticClient* PD = getPathDiagnosticClient();
Ted Kremenekcf118d42009-02-04 23:49:09 +00001633
1634 // FIXME: Make sure we use the 'R' for the path that was actually used.
1635 // Probably doesn't make a difference in practice.
1636 BugType& BT = R.getBugType();
1637
Ted Kremenekd49967f2009-04-29 21:58:13 +00001638 llvm::OwningPtr<PathDiagnostic>
1639 D(new PathDiagnostic(R.getBugType().getName(),
Ted Kremenekda0e8422009-04-29 22:05:03 +00001640 !PD || PD->useVerboseDescription()
Ted Kremenekd49967f2009-04-29 21:58:13 +00001641 ? R.getDescription() : R.getShortDescription(),
1642 BT.getCategory()));
1643
Ted Kremenekcf118d42009-02-04 23:49:09 +00001644 GeneratePathDiagnostic(*D.get(), EQ);
Ted Kremenek072192b2008-04-30 23:47:44 +00001645
1646 // Get the meta data.
Ted Kremenek072192b2008-04-30 23:47:44 +00001647 std::pair<const char**, const char**> Meta = R.getExtraDescriptiveText();
Ted Kremenek3148eb42009-01-24 00:55:43 +00001648 for (const char** s = Meta.first; s != Meta.second; ++s) D->addMeta(*s);
Ted Kremenek75840e12008-04-18 01:56:37 +00001649
Ted Kremenek3148eb42009-01-24 00:55:43 +00001650 // Emit a summary diagnostic to the regular Diagnostics engine.
Ted Kremenek3148eb42009-01-24 00:55:43 +00001651 const SourceRange *Beg = 0, *End = 0;
1652 R.getRanges(*this, Beg, End);
1653 Diagnostic& Diag = getDiagnostic();
Ted Kremenekcf118d42009-02-04 23:49:09 +00001654 FullSourceLoc L(R.getLocation(), getSourceManager());
Ted Kremenekd90e7082009-02-07 22:36:41 +00001655 unsigned ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning,
Ted Kremenekeaedfea2009-05-10 05:11:21 +00001656 R.getShortDescription().c_str());
Ted Kremenek57202072008-07-14 17:40:50 +00001657
Ted Kremenek3148eb42009-01-24 00:55:43 +00001658 switch (End-Beg) {
Chris Lattner0a14eee2008-11-18 07:04:44 +00001659 default: assert(0 && "Don't handle this many ranges yet!");
1660 case 0: Diag.Report(L, ErrorDiag); break;
1661 case 1: Diag.Report(L, ErrorDiag) << Beg[0]; break;
1662 case 2: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1]; break;
1663 case 3: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1] << Beg[2]; break;
Ted Kremenek2f0e89e2008-04-18 22:56:53 +00001664 }
Ted Kremenek3148eb42009-01-24 00:55:43 +00001665
1666 // Emit a full diagnostic for the path if we have a PathDiagnosticClient.
1667 if (!PD)
1668 return;
1669
1670 if (D->empty()) {
Ted Kremenek1fbfd5b2009-03-06 23:58:11 +00001671 PathDiagnosticPiece* piece =
1672 new PathDiagnosticEventPiece(L, R.getDescription());
1673
Ted Kremenek3148eb42009-01-24 00:55:43 +00001674 for ( ; Beg != End; ++Beg) piece->addRange(*Beg);
1675 D->push_back(piece);
1676 }
1677
1678 PD->HandlePathDiagnostic(D.take());
Ted Kremenek61f3e052008-04-03 04:42:52 +00001679}
Ted Kremenek57202072008-07-14 17:40:50 +00001680
Ted Kremenek8c036c72008-09-20 04:23:38 +00001681void BugReporter::EmitBasicReport(const char* name, const char* str,
1682 SourceLocation Loc,
1683 SourceRange* RBeg, unsigned NumRanges) {
1684 EmitBasicReport(name, "", str, Loc, RBeg, NumRanges);
1685}
Ted Kremenekcf118d42009-02-04 23:49:09 +00001686
Ted Kremenek8c036c72008-09-20 04:23:38 +00001687void BugReporter::EmitBasicReport(const char* name, const char* category,
1688 const char* str, SourceLocation Loc,
1689 SourceRange* RBeg, unsigned NumRanges) {
1690
Ted Kremenekcf118d42009-02-04 23:49:09 +00001691 // 'BT' will be owned by BugReporter as soon as we call 'EmitReport'.
1692 BugType *BT = new BugType(name, category);
Chris Lattner0a14eee2008-11-18 07:04:44 +00001693 FullSourceLoc L = getContext().getFullLoc(Loc);
Ted Kremenekcf118d42009-02-04 23:49:09 +00001694 RangedBugReport *R = new DiagBugReport(*BT, str, L);
1695 for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
1696 EmitReport(R);
Ted Kremenek57202072008-07-14 17:40:50 +00001697}