blob: 0074a93b5bca314f5d8f3cb50778763ddc842d49 [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/Basic/SourceManager.h"
18#include "clang/Basic/SourceLocation.h"
19#include "clang/AST/ASTContext.h"
20#include "clang/AST/CFG.h"
21#include "clang/AST/Expr.h"
22#include "clang/Analysis/ProgramPoint.h"
23#include "clang/Analysis/PathDiagnostic.h"
Chris Lattner405674c2008-08-23 22:23:37 +000024#include "llvm/Support/raw_ostream.h"
Ted Kremenek331b0ac2008-06-18 05:34:07 +000025#include "llvm/ADT/DenseMap.h"
Ted Kremenek61f3e052008-04-03 04:42:52 +000026#include <sstream>
27
28using namespace clang;
29
30BugReporter::~BugReporter() {}
Ted Kremenekc0959972008-07-02 21:24:01 +000031GRBugReporter::~GRBugReporter() {}
32BugReporterData::~BugReporterData() {}
Ted Kremenek50a6d0c2008-04-09 21:41:14 +000033BugType::~BugType() {}
34BugReport::~BugReport() {}
Ted Kremenek5e55cda2008-04-11 18:40:29 +000035RangedBugReport::~RangedBugReport() {}
36
Ted Kremenek4adc81e2008-08-13 04:27:00 +000037ExplodedGraph<GRState>& GRBugReporter::getGraph() {
Ted Kremenek1aa44c72008-05-22 23:45:19 +000038 return Eng.getGraph();
39}
40
Ted Kremenek4adc81e2008-08-13 04:27:00 +000041GRStateManager& GRBugReporter::getStateManager() {
Ted Kremenek1aa44c72008-05-22 23:45:19 +000042 return Eng.getStateManager();
43}
Ted Kremenek61f3e052008-04-03 04:42:52 +000044
45static inline Stmt* GetStmt(const ProgramPoint& P) {
46 if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
47 return PS->getStmt();
48 }
49 else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
50 return BE->getSrc()->getTerminator();
51 }
52 else if (const BlockEntrance* BE = dyn_cast<BlockEntrance>(&P)) {
53 return BE->getFirstStmt();
54 }
55
56 assert (false && "Unsupported ProgramPoint.");
57 return NULL;
58}
59
Ted Kremenek706e3cf2008-04-07 23:35:17 +000060static inline Stmt* GetStmt(const CFGBlock* B) {
Ted Kremenek143ca222008-05-06 18:11:09 +000061 if (B->empty())
Ted Kremenek2673c9f2008-04-25 19:01:27 +000062 return const_cast<Stmt*>(B->getTerminator());
Ted Kremenek2673c9f2008-04-25 19:01:27 +000063 else
64 return (*B)[0];
Ted Kremenek706e3cf2008-04-07 23:35:17 +000065}
66
Ted Kremenek4adc81e2008-08-13 04:27:00 +000067static inline ExplodedNode<GRState>*
68GetNextNode(ExplodedNode<GRState>* N) {
Ted Kremenekbd7efa82008-04-17 23:44:37 +000069 return N->pred_empty() ? NULL : *(N->pred_begin());
70}
Ted Kremenek2673c9f2008-04-25 19:01:27 +000071
Ted Kremenek4adc81e2008-08-13 04:27:00 +000072static Stmt* GetLastStmt(ExplodedNode<GRState>* N) {
Ted Kremenekbd7efa82008-04-17 23:44:37 +000073 assert (isa<BlockEntrance>(N->getLocation()));
74
75 for (N = GetNextNode(N); N; N = GetNextNode(N)) {
76
77 ProgramPoint P = N->getLocation();
78
79 if (PostStmt* PS = dyn_cast<PostStmt>(&P))
80 return PS->getStmt();
81 }
82
83 return NULL;
84}
85
Ted Kremenek143ca222008-05-06 18:11:09 +000086static void ExecutionContinues(std::ostringstream& os, SourceManager& SMgr,
87 Stmt* S) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +000088
89 if (!S)
90 return;
Ted Kremenek143ca222008-05-06 18:11:09 +000091
92 // Slow, but probably doesn't matter.
93 if (os.str().empty())
94 os << ' ';
95
96 os << "Execution continues on line "
Ted Kremenekbb77e9b2008-05-01 22:50:36 +000097 << SMgr.getLogicalLineNumber(S->getLocStart()) << '.';
98}
Ted Kremenek143ca222008-05-06 18:11:09 +000099
100
101static inline void ExecutionContinues(std::ostringstream& os,
102 SourceManager& SMgr,
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000103 ExplodedNode<GRState>* N) {
Ted Kremenek143ca222008-05-06 18:11:09 +0000104
105 ExecutionContinues(os, SMgr, GetStmt(N->getLocation()));
106}
107
108static inline void ExecutionContinues(std::ostringstream& os,
109 SourceManager& SMgr,
110 const CFGBlock* B) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000111
Ted Kremenek143ca222008-05-06 18:11:09 +0000112 ExecutionContinues(os, SMgr, GetStmt(B));
113}
114
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000115
116Stmt* BugReport::getStmt(BugReporter& BR) const {
117
Ted Kremenek200ed922008-05-02 23:21:21 +0000118 ProgramPoint ProgP = EndNode->getLocation();
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000119 Stmt *S = NULL;
120
121 if (BlockEntrance* BE = dyn_cast<BlockEntrance>(&ProgP))
Ted Kremenek7032f462008-07-03 05:26:14 +0000122 if (BE->getBlock() == &BR.getCFG()->getExit())
Ted Kremenek200ed922008-05-02 23:21:21 +0000123 S = GetLastStmt(EndNode);
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000124 if (!S)
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000125 S = GetStmt(ProgP);
126
127 return S;
128}
129
130PathDiagnosticPiece*
131BugReport::getEndPath(BugReporter& BR,
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000132 ExplodedNode<GRState>* EndPathNode) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000133
134 Stmt* S = getStmt(BR);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000135
136 if (!S)
137 return NULL;
138
Ted Kremenekc9fa2f72008-05-01 23:13:35 +0000139 FullSourceLoc L(S->getLocStart(), BR.getContext().getSourceManager());
140 PathDiagnosticPiece* P = new PathDiagnosticPiece(L, getDescription());
Ted Kremenek61f3e052008-04-03 04:42:52 +0000141
Ted Kremenekde7161f2008-04-03 18:00:37 +0000142 const SourceRange *Beg, *End;
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000143 getRanges(BR, Beg, End);
144
145 for (; Beg != End; ++Beg)
146 P->addRange(*Beg);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000147
148 return P;
149}
150
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000151void BugReport::getRanges(BugReporter& BR, const SourceRange*& beg,
152 const SourceRange*& end) {
153
154 if (Expr* E = dyn_cast_or_null<Expr>(getStmt(BR))) {
155 R = E->getSourceRange();
156 beg = &R;
157 end = beg+1;
158 }
159 else
160 beg = end = 0;
Ted Kremenekf1ae7052008-04-03 17:57:38 +0000161}
162
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000163FullSourceLoc BugReport::getLocation(SourceManager& Mgr) {
164
Ted Kremenek200ed922008-05-02 23:21:21 +0000165 if (!EndNode)
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000166 return FullSourceLoc();
167
Ted Kremenek200ed922008-05-02 23:21:21 +0000168 Stmt* S = GetStmt(EndNode->getLocation());
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000169
170 if (!S)
171 return FullSourceLoc();
172
173 return FullSourceLoc(S->getLocStart(), Mgr);
174}
175
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000176PathDiagnosticPiece* BugReport::VisitNode(ExplodedNode<GRState>* N,
177 ExplodedNode<GRState>* PrevN,
178 ExplodedGraph<GRState>& G,
Ted Kremenek8dd56462008-04-18 03:39:05 +0000179 BugReporter& BR) {
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000180 return NULL;
181}
182
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000183static std::pair<ExplodedGraph<GRState>*, ExplodedNode<GRState>*>
184MakeReportGraph(ExplodedGraph<GRState>* G, ExplodedNode<GRState>* N) {
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000185
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000186 llvm::OwningPtr<ExplodedGraph<GRState> > GTrim(G->Trim(&N, &N+1));
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000187
Ted Kremenek910e9992008-04-25 01:25:15 +0000188 // Find the error node in the trimmed graph.
Ted Kremenek94826a72008-04-03 04:59:14 +0000189
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000190 ExplodedNode<GRState>* NOld = N;
Ted Kremenek910e9992008-04-25 01:25:15 +0000191 N = 0;
Ted Kremenek94826a72008-04-03 04:59:14 +0000192
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000193 for (ExplodedGraph<GRState>::node_iterator
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000194 I = GTrim->nodes_begin(), E = GTrim->nodes_end(); I != E; ++I) {
Ted Kremenek94826a72008-04-03 04:59:14 +0000195
Ted Kremenek910e9992008-04-25 01:25:15 +0000196 if (I->getState() == NOld->getState() &&
197 I->getLocation() == NOld->getLocation()) {
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000198 N = &*I;
Ted Kremenek94826a72008-04-03 04:59:14 +0000199 break;
200 }
201 }
202
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000203 assert(N);
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000204
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000205 // Create a new graph with a single path.
206
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000207 G = new ExplodedGraph<GRState>(GTrim->getCFG(), GTrim->getCodeDecl(),
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000208 GTrim->getContext());
209
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000210 // Sometimes TrimGraph can contain a cycle. Perform a reverse DFS
211 // to the root node, and then construct a new graph that contains only
212 // a single path.
213 llvm::DenseMap<void*,unsigned> Visited;
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000214 llvm::SmallVector<ExplodedNode<GRState>*, 10> WS;
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000215 WS.push_back(N);
216 unsigned cnt = 0;
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000217 ExplodedNode<GRState>* Root = 0;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000218
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000219 while (!WS.empty()) {
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000220 ExplodedNode<GRState>* Node = WS.back();
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000221 WS.pop_back();
222
223 if (Visited.find(Node) != Visited.end())
224 continue;
225
226 Visited[Node] = cnt++;
227
228 if (Node->pred_empty()) {
229 Root = Node;
230 break;
231 }
232
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000233 for (ExplodedNode<GRState>::pred_iterator I=Node->pred_begin(),
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000234 E=Node->pred_end(); I!=E; ++I)
235 WS.push_back(*I);
236 }
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000237
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000238 assert (Root);
239
240 // Now walk from the root down the DFS path, always taking the successor
241 // with the lowest number.
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000242 ExplodedNode<GRState> *Last = 0, *First = 0;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000243
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000244 for ( N = Root ;;) {
245
246 // Lookup the number associated with the current node.
247 llvm::DenseMap<void*,unsigned>::iterator I=Visited.find(N);
248 assert (I != Visited.end());
249
250 // Create the equivalent node in the new graph with the same state
251 // and location.
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000252 ExplodedNode<GRState>* NewN =
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000253 G->getNode(N->getLocation(), N->getState());
254
255 // Link up the new node with the previous node.
256 if (Last)
257 NewN->addPredecessor(Last);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000258
259 Last = NewN;
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000260
261 // Are we at the final node?
262 if (I->second == 0) {
263 First = NewN;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000264 break;
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000265 }
266
267 // Find the next successor node. We choose the node that is marked
268 // with the lowest DFS number.
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000269 ExplodedNode<GRState>::succ_iterator SI = N->succ_begin();
270 ExplodedNode<GRState>::succ_iterator SE = N->succ_end();
Ted Kremenekc1da4412008-06-17 19:14:06 +0000271 N = 0;
272
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000273 for (unsigned MinVal = 0; SI != SE; ++SI) {
Ted Kremenekc1da4412008-06-17 19:14:06 +0000274
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000275 I = Visited.find(*SI);
276
277 if (I == Visited.end())
278 continue;
279
280 if (!N || I->second < MinVal) {
281 N = *SI;
282 MinVal = I->second;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000283 }
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000284 }
285
286 assert (N);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000287 }
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000288
289 assert (First);
Ted Kremenek6aaca9c2008-04-23 23:04:32 +0000290 return std::make_pair(G, First);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000291}
292
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000293static VarDecl* GetMostRecentVarDeclBinding(ExplodedNode<GRState>* N,
294 GRStateManager& VMgr,
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000295 SVal X) {
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000296
297 for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
298
299 ProgramPoint P = N->getLocation();
300
301 if (!isa<PostStmt>(P))
302 continue;
303
304 DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
305
306 if (!DR)
307 continue;
308
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000309 SVal Y = VMgr.GetSVal(N->getState(), DR);
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000310
311 if (X != Y)
312 continue;
313
314 VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl());
315
316 if (!VD)
317 continue;
318
319 return VD;
320 }
321
322 return 0;
323}
324
Ted Kremenek9e240492008-10-04 05:50:14 +0000325namespace {
326class VISIBILITY_HIDDEN NotableSymbolHandler
327 : public StoreManager::BindingsHandler {
328
329 SymbolID Sym;
330 const GRState* PrevSt;
331 Stmt* S;
332 GRStateManager& VMgr;
333 ExplodedNode<GRState>* Pred;
334 PathDiagnostic& PD;
335 BugReporter& BR;
336
337public:
338
339 NotableSymbolHandler(SymbolID sym, const GRState* prevst, Stmt* s,
340 GRStateManager& vmgr, ExplodedNode<GRState>* pred,
341 PathDiagnostic& pd, BugReporter& br)
342 : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
343
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000344 bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, SVal V) {
Ted Kremenek9e240492008-10-04 05:50:14 +0000345
346 SymbolID ScanSym;
347
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000348 if (loc::SymbolVal* SV = dyn_cast<loc::SymbolVal>(&V))
Ted Kremenek9e240492008-10-04 05:50:14 +0000349 ScanSym = SV->getSymbol();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000350 else if (nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(&V))
Ted Kremenek9e240492008-10-04 05:50:14 +0000351 ScanSym = SV->getSymbol();
352 else
353 return true;
354
355 if (ScanSym != Sym)
356 return true;
357
358 // Check if the previous state has this binding.
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000359 SVal X = VMgr.GetSVal(PrevSt, loc::MemRegionVal(R));
Ted Kremenek9e240492008-10-04 05:50:14 +0000360
361 if (X == V) // Same binding?
362 return true;
363
364 // Different binding. Only handle assignments for now. We don't pull
365 // this check out of the loop because we will eventually handle other
366 // cases.
367
368 VarDecl *VD = 0;
369
370 if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
371 if (!B->isAssignmentOp())
372 return true;
373
374 // What variable did we assign to?
375 DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
376
377 if (!DR)
378 return true;
379
380 VD = dyn_cast<VarDecl>(DR->getDecl());
381 }
Ted Kremenekf21a4b42008-10-06 18:37:46 +0000382 else if (DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
383 // FIXME: Eventually CFGs won't have DeclStmts. Right now we
384 // assume that each DeclStmt has a single Decl. This invariant
385 // holds by contruction in the CFG.
386 VD = dyn_cast<VarDecl>(*DS->decl_begin());
387 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000388
389 if (!VD)
390 return true;
391
392 // What is the most recently referenced variable with this binding?
393 VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
394
395 if (!MostRecent)
396 return true;
397
398 // Create the diagnostic.
399
400 FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
401
402 if (VD->getType()->isPointerLikeType()) {
403 std::string msg = "'" + std::string(VD->getName()) +
404 "' now aliases '" + MostRecent->getName() + "'";
405
406 PD.push_front(new PathDiagnosticPiece(L, msg));
407 }
408
409 return true;
410 }
411};
412}
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000413
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000414static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S,
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000415 SymbolID Sym, BugReporter& BR,
416 PathDiagnostic& PD) {
417
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000418 ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin();
419 const GRState* PrevSt = Pred ? Pred->getState() : 0;
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000420
421 if (!PrevSt)
422 return;
423
Ted Kremenek9e240492008-10-04 05:50:14 +0000424 // Look at the region bindings of the current state that map to the
425 // specified symbol. Are any of them not in the previous state?
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000426 GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
Ted Kremenek9e240492008-10-04 05:50:14 +0000427 NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
428 cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
429}
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000430
Ted Kremenek9e240492008-10-04 05:50:14 +0000431namespace {
432class VISIBILITY_HIDDEN ScanNotableSymbols
433 : public StoreManager::BindingsHandler {
434
435 llvm::SmallSet<SymbolID, 10> AlreadyProcessed;
436 ExplodedNode<GRState>* N;
437 Stmt* S;
438 GRBugReporter& BR;
439 PathDiagnostic& PD;
440
441public:
442 ScanNotableSymbols(ExplodedNode<GRState>* n, Stmt* s, GRBugReporter& br,
443 PathDiagnostic& pd)
444 : N(n), S(s), BR(br), PD(pd) {}
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000445
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000446 bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, SVal V) {
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000447 SymbolID ScanSym;
Ted Kremenek9e240492008-10-04 05:50:14 +0000448
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000449 if (loc::SymbolVal* SV = dyn_cast<loc::SymbolVal>(&V))
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000450 ScanSym = SV->getSymbol();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000451 else if (nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(&V))
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000452 ScanSym = SV->getSymbol();
453 else
Ted Kremenek9e240492008-10-04 05:50:14 +0000454 return true;
455
456 assert (ScanSym.isInitialized());
457
458 if (!BR.isNotable(ScanSym))
459 return true;
460
461 if (AlreadyProcessed.count(ScanSym))
462 return true;
463
464 AlreadyProcessed.insert(ScanSym);
465
466 HandleNotableSymbol(N, S, ScanSym, BR, PD);
467 return true;
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000468 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000469};
470} // end anonymous namespace
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000471
Ted Kremenekc0959972008-07-02 21:24:01 +0000472void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
473 BugReport& R) {
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000474
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000475 ExplodedNode<GRState>* N = R.getEndNode();
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000476
477 if (!N) return;
478
479 // Construct a new graph that contains only a single path from the error
480 // node to a root.
481
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000482 const std::pair<ExplodedGraph<GRState>*,ExplodedNode<GRState>*>
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000483 GPair = MakeReportGraph(&getGraph(), N);
484
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000485 llvm::OwningPtr<ExplodedGraph<GRState> > ReportGraph(GPair.first);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000486 assert(GPair.second->getLocation() == N->getLocation());
487 N = GPair.second;
488
489 // Start building the path diagnostic...
490
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000491 if (PathDiagnosticPiece* Piece = R.getEndPath(*this, N))
492 PD.push_back(Piece);
493 else
494 return;
Ted Kremenek6837faa2008-04-09 00:20:43 +0000495
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000496 ExplodedNode<GRState>* NextNode = N->pred_empty()
Ted Kremenek6837faa2008-04-09 00:20:43 +0000497 ? NULL : *(N->pred_begin());
498
Ted Kremenekc0959972008-07-02 21:24:01 +0000499 ASTContext& Ctx = getContext();
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000500 SourceManager& SMgr = Ctx.getSourceManager();
501
Ted Kremenek6837faa2008-04-09 00:20:43 +0000502 while (NextNode) {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000503
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000504 ExplodedNode<GRState>* LastNode = N;
Ted Kremenek6837faa2008-04-09 00:20:43 +0000505 N = NextNode;
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000506 NextNode = GetNextNode(N);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000507
508 ProgramPoint P = N->getLocation();
509
510 if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
511
512 CFGBlock* Src = BE->getSrc();
513 CFGBlock* Dst = BE->getDst();
514
515 Stmt* T = Src->getTerminator();
516
517 if (!T)
518 continue;
519
520 FullSourceLoc L(T->getLocStart(), SMgr);
521
522 switch (T->getStmtClass()) {
523 default:
524 break;
525
526 case Stmt::GotoStmtClass:
527 case Stmt::IndirectGotoStmtClass: {
528
529 Stmt* S = GetStmt(LastNode->getLocation());
530
531 if (!S)
532 continue;
533
534 std::ostringstream os;
535
536 os << "Control jumps to line "
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000537 << SMgr.getLogicalLineNumber(S->getLocStart()) << ".\n";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000538
539 PD.push_front(new PathDiagnosticPiece(L, os.str()));
540 break;
541 }
542
543 case Stmt::SwitchStmtClass: {
544
545 // Figure out what case arm we took.
Ted Kremenek5a429952008-04-23 23:35:07 +0000546
Ted Kremenek61f3e052008-04-03 04:42:52 +0000547 std::ostringstream os;
Ted Kremenek5a429952008-04-23 23:35:07 +0000548
549 if (Stmt* S = Dst->getLabel())
550 switch (S->getStmtClass()) {
551
Ted Kremenek61f3e052008-04-03 04:42:52 +0000552 default:
Ted Kremenek5a429952008-04-23 23:35:07 +0000553 assert(false && "Not a valid switch label.");
554 continue;
555
Ted Kremenek8b904552008-04-22 22:29:46 +0000556 case Stmt::DefaultStmtClass: {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000557
558 os << "Control jumps to the 'default' case at line "
Ted Kremenek6837faa2008-04-09 00:20:43 +0000559 << SMgr.getLogicalLineNumber(S->getLocStart()) << ".\n";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000560
561 break;
562 }
563
564 case Stmt::CaseStmtClass: {
565
566 os << "Control jumps to 'case ";
567
Ted Kremenek5a429952008-04-23 23:35:07 +0000568 CaseStmt* Case = cast<CaseStmt>(S);
569 Expr* LHS = Case->getLHS()->IgnoreParenCasts();
Ted Kremenek61f3e052008-04-03 04:42:52 +0000570
Ted Kremenek5a429952008-04-23 23:35:07 +0000571 // Determine if it is an enum.
Ted Kremenek61f3e052008-04-03 04:42:52 +0000572
Ted Kremenek5a429952008-04-23 23:35:07 +0000573 bool GetRawInt = true;
Ted Kremenek61f3e052008-04-03 04:42:52 +0000574
Ted Kremenek5a429952008-04-23 23:35:07 +0000575 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
576
577 // FIXME: Maybe this should be an assertion. Are there cases
578 // were it is not an EnumConstantDecl?
Chris Lattner470e5fc2008-11-18 06:07:40 +0000579 EnumConstantDecl* D = dyn_cast<EnumConstantDecl>(DR->getDecl());
Ted Kremenek5a429952008-04-23 23:35:07 +0000580 if (D) {
581 GetRawInt = false;
582 os << D->getName();
583 }
Ted Kremenek61f3e052008-04-03 04:42:52 +0000584 }
Ted Kremenek5a429952008-04-23 23:35:07 +0000585
586 if (GetRawInt) {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000587
Ted Kremenek5a429952008-04-23 23:35:07 +0000588 // Not an enum.
589 Expr* CondE = cast<SwitchStmt>(T)->getCond();
590 unsigned bits = Ctx.getTypeSize(CondE->getType());
591 llvm::APSInt V(bits, false);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000592
Ted Kremenek5a429952008-04-23 23:35:07 +0000593 if (!LHS->isIntegerConstantExpr(V, Ctx, 0, true)) {
594 assert (false && "Case condition must be constant.");
Ted Kremenek61f3e052008-04-03 04:42:52 +0000595 continue;
596 }
597
Chris Lattner405674c2008-08-23 22:23:37 +0000598 llvm::raw_os_ostream OS(os);
599 OS << V;
Ted Kremenek2673c9f2008-04-25 19:01:27 +0000600 }
Ted Kremenek5a429952008-04-23 23:35:07 +0000601
Ted Kremenek61f3e052008-04-03 04:42:52 +0000602 os << ":' at line "
Ted Kremenek5a429952008-04-23 23:35:07 +0000603 << SMgr.getLogicalLineNumber(S->getLocStart()) << ".\n";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000604
605 break;
606
607 }
608 }
Ted Kremenek56783922008-04-25 01:29:56 +0000609 else {
Ted Kremenekc3517eb2008-09-12 18:17:46 +0000610 os << "'Default' branch taken. ";
Ted Kremenek2673c9f2008-04-25 19:01:27 +0000611 ExecutionContinues(os, SMgr, LastNode);
Ted Kremenek56783922008-04-25 01:29:56 +0000612 }
Ted Kremenek61f3e052008-04-03 04:42:52 +0000613
614 PD.push_front(new PathDiagnosticPiece(L, os.str()));
615 break;
616 }
Ted Kremenek2673c9f2008-04-25 19:01:27 +0000617
618 case Stmt::BreakStmtClass:
619 case Stmt::ContinueStmtClass: {
620 std::ostringstream os;
621 ExecutionContinues(os, SMgr, LastNode);
622 PD.push_front(new PathDiagnosticPiece(L, os.str()));
623 break;
624 }
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000625
626 case Stmt::ConditionalOperatorClass: {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000627
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000628 std::ostringstream os;
629 os << "'?' condition evaluates to ";
630
631 if (*(Src->succ_begin()+1) == Dst)
632 os << "false.";
633 else
634 os << "true.";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000635
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000636 PD.push_front(new PathDiagnosticPiece(L, os.str()));
637
638 break;
639 }
640
641 case Stmt::DoStmtClass: {
642
643 if (*(Src->succ_begin()) == Dst) {
644
645 std::ostringstream os;
646
Ted Kremenekc3517eb2008-09-12 18:17:46 +0000647 os << "Loop condition is true. ";
Ted Kremenek143ca222008-05-06 18:11:09 +0000648 ExecutionContinues(os, SMgr, Dst);
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000649
650 PD.push_front(new PathDiagnosticPiece(L, os.str()));
651 }
652 else
653 PD.push_front(new PathDiagnosticPiece(L,
654 "Loop condition is false. Exiting loop."));
655
656 break;
657 }
658
Ted Kremenek61f3e052008-04-03 04:42:52 +0000659 case Stmt::WhileStmtClass:
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000660 case Stmt::ForStmtClass: {
661
662 if (*(Src->succ_begin()+1) == Dst) {
663
664 std::ostringstream os;
665
Ted Kremenekc3517eb2008-09-12 18:17:46 +0000666 os << "Loop condition is false. ";
Ted Kremenek143ca222008-05-06 18:11:09 +0000667 ExecutionContinues(os, SMgr, Dst);
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000668
669 PD.push_front(new PathDiagnosticPiece(L, os.str()));
670 }
671 else
672 PD.push_front(new PathDiagnosticPiece(L,
673 "Loop condition is true. Entering loop body."));
674
675 break;
676 }
677
Ted Kremenek61f3e052008-04-03 04:42:52 +0000678 case Stmt::IfStmtClass: {
679
680 if (*(Src->succ_begin()+1) == Dst)
681 PD.push_front(new PathDiagnosticPiece(L, "Taking false branch."));
682 else
683 PD.push_front(new PathDiagnosticPiece(L, "Taking true branch."));
684
685 break;
686 }
687 }
Ted Kremenek6837faa2008-04-09 00:20:43 +0000688 }
Ted Kremenek5a429952008-04-23 23:35:07 +0000689
690 if (PathDiagnosticPiece* p = R.VisitNode(N, NextNode, *ReportGraph, *this))
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000691 PD.push_front(p);
692
Ted Kremenek9e240492008-10-04 05:50:14 +0000693 if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
694 // Scan the region bindings, and see if a "notable" symbol has a new
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000695 // lval binding.
Ted Kremenek9e240492008-10-04 05:50:14 +0000696 ScanNotableSymbols SNS(N, PS->getStmt(), *this, PD);
697 getStateManager().iterBindings(N->getState(), SNS);
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000698 }
Ted Kremenek61f3e052008-04-03 04:42:52 +0000699 }
700}
701
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000702
Ted Kremenek95cc1ba2008-04-18 20:54:29 +0000703bool BugTypeCacheLocation::isCached(BugReport& R) {
704
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000705 ExplodedNode<GRState>* N = R.getEndNode();
Ted Kremenek61f3e052008-04-03 04:42:52 +0000706
Ted Kremenek329d2cc2008-04-18 02:24:50 +0000707 if (!N)
708 return false;
Ted Kremenek95cc1ba2008-04-18 20:54:29 +0000709
710 // Cache the location of the error. Don't emit the same
Ted Kremenek61f3e052008-04-03 04:42:52 +0000711 // warning for the same error type that occurs at the same program
712 // location but along a different path.
713
Ted Kremenek76d90c82008-05-16 18:33:14 +0000714 return isCached(N->getLocation());
715}
716
717bool BugTypeCacheLocation::isCached(ProgramPoint P) {
Ted Kremenekd4527582008-09-16 18:44:52 +0000718 if (CachedErrors.count(P))
Ted Kremenek61f3e052008-04-03 04:42:52 +0000719 return true;
720
Ted Kremenekd4527582008-09-16 18:44:52 +0000721 CachedErrors.insert(P);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000722 return false;
723}
724
Ted Kremenek75840e12008-04-18 01:56:37 +0000725void BugReporter::EmitWarning(BugReport& R) {
726
Ted Kremenek95cc1ba2008-04-18 20:54:29 +0000727 if (R.getBugType().isCached(R))
Ted Kremenek61f3e052008-04-03 04:42:52 +0000728 return;
Ted Kremenek75840e12008-04-18 01:56:37 +0000729
Ted Kremenek8c036c72008-09-20 04:23:38 +0000730 llvm::OwningPtr<PathDiagnostic> D(new PathDiagnostic(R.getName(),
731 R.getCategory()));
Ted Kremenek55851142008-04-22 16:15:03 +0000732 GeneratePathDiagnostic(*D.get(), R);
Ted Kremenek072192b2008-04-30 23:47:44 +0000733
734 // Get the meta data.
735
736 std::pair<const char**, const char**> Meta = R.getExtraDescriptiveText();
737
738 for (const char** s = Meta.first; s != Meta.second; ++s)
739 D->addMeta(*s);
Ted Kremenek75840e12008-04-18 01:56:37 +0000740
741 // Emit a full diagnostic for the path if we have a PathDiagnosticClient.
Ted Kremenek70d17222008-04-03 07:33:55 +0000742
Ted Kremenekc0959972008-07-02 21:24:01 +0000743 PathDiagnosticClient* PD = getPathDiagnosticClient();
744
Ted Kremenek55851142008-04-22 16:15:03 +0000745 if (PD && !D->empty()) {
746 PD->HandlePathDiagnostic(D.take());
Ted Kremenek75840e12008-04-18 01:56:37 +0000747 return;
748 }
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000749
Ted Kremenek75840e12008-04-18 01:56:37 +0000750 // We don't have a PathDiagnosticClient, but we can still emit a single
751 // line diagnostic. Determine the location.
Ted Kremenek61f3e052008-04-03 04:42:52 +0000752
Ted Kremenekc0959972008-07-02 21:24:01 +0000753 FullSourceLoc L = D->empty() ? R.getLocation(getSourceManager())
Ted Kremenek55851142008-04-22 16:15:03 +0000754 : D->back()->getLocation();
Ted Kremenek75840e12008-04-18 01:56:37 +0000755
756
757 // Determine the range.
Ted Kremenek5fcca682008-04-14 18:06:42 +0000758
Ted Kremenek4bb6ac22008-04-10 16:12:38 +0000759 const SourceRange *Beg, *End;
Ted Kremenek57202072008-07-14 17:40:50 +0000760
Ted Kremenek55851142008-04-22 16:15:03 +0000761 if (!D->empty()) {
762 Beg = D->back()->ranges_begin();
763 End = D->back()->ranges_end();
Ted Kremenek75840e12008-04-18 01:56:37 +0000764 }
Ted Kremenek57202072008-07-14 17:40:50 +0000765 else
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000766 R.getRanges(*this, Beg, End);
Ted Kremenek75840e12008-04-18 01:56:37 +0000767
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000768 if (PD) {
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000769 PathDiagnosticPiece* piece = new PathDiagnosticPiece(L, R.getDescription());
770
771 for ( ; Beg != End; ++Beg)
772 piece->addRange(*Beg);
773
Ted Kremenek57202072008-07-14 17:40:50 +0000774 D->push_back(piece);
Ted Kremenek55851142008-04-22 16:15:03 +0000775 PD->HandlePathDiagnostic(D.take());
Chris Lattner0a14eee2008-11-18 07:04:44 +0000776 return;
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000777 }
778 else {
Chris Lattner0a14eee2008-11-18 07:04:44 +0000779 std::string str;
Ted Kremenek57202072008-07-14 17:40:50 +0000780
Ted Kremenek55851142008-04-22 16:15:03 +0000781 if (D->empty())
Chris Lattner0a14eee2008-11-18 07:04:44 +0000782 str = R.getDescription();
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000783 else
Chris Lattner0a14eee2008-11-18 07:04:44 +0000784 str = D->back()->getString();
Ted Kremenek57202072008-07-14 17:40:50 +0000785
Ted Kremenekc0959972008-07-02 21:24:01 +0000786 Diagnostic& Diag = getDiagnostic();
Chris Lattner0a14eee2008-11-18 07:04:44 +0000787 unsigned ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, str.c_str());
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000788
Chris Lattner0a14eee2008-11-18 07:04:44 +0000789 switch (End-Beg) {
790 default: assert(0 && "Don't handle this many ranges yet!");
791 case 0: Diag.Report(L, ErrorDiag); break;
792 case 1: Diag.Report(L, ErrorDiag) << Beg[0]; break;
793 case 2: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1]; break;
794 case 3: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1] << Beg[2]; break;
795 }
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000796 }
Ted Kremenek61f3e052008-04-03 04:42:52 +0000797}
Ted Kremenek57202072008-07-14 17:40:50 +0000798
Ted Kremenek8c036c72008-09-20 04:23:38 +0000799void BugReporter::EmitBasicReport(const char* name, const char* str,
800 SourceLocation Loc,
801 SourceRange* RBeg, unsigned NumRanges) {
802 EmitBasicReport(name, "", str, Loc, RBeg, NumRanges);
803}
Ted Kremenek57202072008-07-14 17:40:50 +0000804
Ted Kremenek8c036c72008-09-20 04:23:38 +0000805void BugReporter::EmitBasicReport(const char* name, const char* category,
806 const char* str, SourceLocation Loc,
807 SourceRange* RBeg, unsigned NumRanges) {
808
809 SimpleBugType BT(name, category, 0);
Ted Kremenek57202072008-07-14 17:40:50 +0000810 DiagCollector C(BT);
811 Diagnostic& Diag = getDiagnostic();
Chris Lattner470e5fc2008-11-18 06:07:40 +0000812
813 DiagnosticClient *OldClient = Diag.getClient();
814 Diag.setClient(&C);
Chris Lattner0a14eee2008-11-18 07:04:44 +0000815 FullSourceLoc L = getContext().getFullLoc(Loc);
816 unsigned DiagID = Diag.getCustomDiagID(Diagnostic::Warning, str);
817
818 switch (NumRanges) {
819 default: assert(0 && "Don't handle this many ranges yet!");
820 case 0: Diag.Report(L, DiagID); break;
821 case 1: Diag.Report(L, DiagID) << RBeg[0]; break;
822 case 2: Diag.Report(L, DiagID) << RBeg[0] << RBeg[1]; break;
823 case 3: Diag.Report(L, DiagID) << RBeg[0] << RBeg[1] << RBeg[2]; break;
824 }
825
Chris Lattner470e5fc2008-11-18 06:07:40 +0000826 Diag.setClient(OldClient);
Ted Kremenek57202072008-07-14 17:40:50 +0000827
828 for (DiagCollector::iterator I = C.begin(), E = C.end(); I != E; ++I)
829 EmitWarning(*I);
830}
831