blob: b08f5cb793e37d7a115a3f15ee3ee44f06364a66 [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 Kremenek3148eb42009-01-24 00:55:43 +000067static inline const ExplodedNode<GRState>*
68GetNextNode(const 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 Kremenek3148eb42009-01-24 00:55:43 +000072static Stmt* GetLastStmt(const 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)) {
Ted Kremenekbd7efa82008-04-17 23:44:37 +000076 ProgramPoint P = N->getLocation();
Ted Kremenek3148eb42009-01-24 00:55:43 +000077 if (PostStmt* PS = dyn_cast<PostStmt>(&P)) return PS->getStmt();
Ted Kremenekbd7efa82008-04-17 23:44:37 +000078 }
79
80 return NULL;
81}
82
Ted Kremenek3148eb42009-01-24 00:55:43 +000083static inline Stmt* GetStmt(const ExplodedNode<GRState>* N) {
84 ProgramPoint ProgP = N->getLocation();
85 return isa<BlockEntrance>(ProgP) ? GetLastStmt(N) : GetStmt(ProgP);
86}
87
88
Ted Kremenek143ca222008-05-06 18:11:09 +000089static void ExecutionContinues(std::ostringstream& os, SourceManager& SMgr,
Ted Kremenek3148eb42009-01-24 00:55:43 +000090 const Stmt* S) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +000091
92 if (!S)
93 return;
Ted Kremenek143ca222008-05-06 18:11:09 +000094
95 // Slow, but probably doesn't matter.
96 if (os.str().empty())
97 os << ' ';
98
99 os << "Execution continues on line "
Chris Lattnerf7cf85b2009-01-16 07:36:28 +0000100 << SMgr.getInstantiationLineNumber(S->getLocStart()) << '.';
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000101}
Ted Kremenek143ca222008-05-06 18:11:09 +0000102
103
104static inline void ExecutionContinues(std::ostringstream& os,
105 SourceManager& SMgr,
Ted Kremenek3148eb42009-01-24 00:55:43 +0000106 const ExplodedNode<GRState>* N) {
Ted Kremenek143ca222008-05-06 18:11:09 +0000107
108 ExecutionContinues(os, SMgr, GetStmt(N->getLocation()));
109}
110
111static inline void ExecutionContinues(std::ostringstream& os,
112 SourceManager& SMgr,
113 const CFGBlock* B) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000114
Ted Kremenek143ca222008-05-06 18:11:09 +0000115 ExecutionContinues(os, SMgr, GetStmt(B));
116}
117
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000118
119Stmt* BugReport::getStmt(BugReporter& BR) const {
120
Ted Kremenek200ed922008-05-02 23:21:21 +0000121 ProgramPoint ProgP = EndNode->getLocation();
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000122 Stmt *S = NULL;
123
124 if (BlockEntrance* BE = dyn_cast<BlockEntrance>(&ProgP))
Ted Kremenek7032f462008-07-03 05:26:14 +0000125 if (BE->getBlock() == &BR.getCFG()->getExit())
Ted Kremenek200ed922008-05-02 23:21:21 +0000126 S = GetLastStmt(EndNode);
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000127 if (!S)
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000128 S = GetStmt(ProgP);
129
130 return S;
131}
132
133PathDiagnosticPiece*
134BugReport::getEndPath(BugReporter& BR,
Ted Kremenek3148eb42009-01-24 00:55:43 +0000135 const ExplodedNode<GRState>* EndPathNode) {
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000136
137 Stmt* S = getStmt(BR);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000138
139 if (!S)
140 return NULL;
141
Ted Kremenekc9fa2f72008-05-01 23:13:35 +0000142 FullSourceLoc L(S->getLocStart(), BR.getContext().getSourceManager());
143 PathDiagnosticPiece* P = new PathDiagnosticPiece(L, getDescription());
Ted Kremenek61f3e052008-04-03 04:42:52 +0000144
Ted Kremenekde7161f2008-04-03 18:00:37 +0000145 const SourceRange *Beg, *End;
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000146 getRanges(BR, Beg, End);
147
148 for (; Beg != End; ++Beg)
149 P->addRange(*Beg);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000150
151 return P;
152}
153
Ted Kremenekbb77e9b2008-05-01 22:50:36 +0000154void BugReport::getRanges(BugReporter& BR, const SourceRange*& beg,
155 const SourceRange*& end) {
156
157 if (Expr* E = dyn_cast_or_null<Expr>(getStmt(BR))) {
158 R = E->getSourceRange();
159 beg = &R;
160 end = beg+1;
161 }
162 else
163 beg = end = 0;
Ted Kremenekf1ae7052008-04-03 17:57:38 +0000164}
165
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000166FullSourceLoc BugReport::getLocation(SourceManager& Mgr) {
167
Ted Kremenek200ed922008-05-02 23:21:21 +0000168 if (!EndNode)
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000169 return FullSourceLoc();
170
Ted Kremenek3148eb42009-01-24 00:55:43 +0000171 Stmt* S = GetStmt(EndNode);
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000172
173 if (!S)
174 return FullSourceLoc();
175
176 return FullSourceLoc(S->getLocStart(), Mgr);
177}
178
Ted Kremenek3148eb42009-01-24 00:55:43 +0000179PathDiagnosticPiece* BugReport::VisitNode(const ExplodedNode<GRState>* N,
180 const ExplodedNode<GRState>* PrevN,
181 const ExplodedGraph<GRState>& G,
Ted Kremenek8dd56462008-04-18 03:39:05 +0000182 BugReporter& BR) {
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000183 return NULL;
184}
185
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000186static std::pair<ExplodedGraph<GRState>*, ExplodedNode<GRState>*>
Ted Kremenek3148eb42009-01-24 00:55:43 +0000187MakeReportGraph(const ExplodedGraph<GRState>* G,
188 const ExplodedNode<GRState>* N) {
Ted Kremenekd2f642b2008-04-14 17:39:48 +0000189
Ted Kremenek3148eb42009-01-24 00:55:43 +0000190 llvm::OwningPtr< ExplodedGraph<GRState> > GTrim(G->Trim(&N, &N+1));
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000191
Ted Kremenek910e9992008-04-25 01:25:15 +0000192 // Find the error node in the trimmed graph.
Ted Kremenek94826a72008-04-03 04:59:14 +0000193
Ted Kremenek3148eb42009-01-24 00:55:43 +0000194 const ExplodedNode<GRState>* NOld = N;
Ted Kremenek910e9992008-04-25 01:25:15 +0000195 N = 0;
Ted Kremenek94826a72008-04-03 04:59:14 +0000196
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000197 for (ExplodedGraph<GRState>::node_iterator
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000198 I = GTrim->nodes_begin(), E = GTrim->nodes_end(); I != E; ++I) {
Ted Kremenek94826a72008-04-03 04:59:14 +0000199
Ted Kremenek910e9992008-04-25 01:25:15 +0000200 if (I->getState() == NOld->getState() &&
201 I->getLocation() == NOld->getLocation()) {
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000202 N = &*I;
Ted Kremenek94826a72008-04-03 04:59:14 +0000203 break;
204 }
205 }
206
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000207 assert(N);
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000208
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000209 // Create a new graph with a single path.
Ted Kremenek3148eb42009-01-24 00:55:43 +0000210 ExplodedGraph<GRState> *GNew =
211 new ExplodedGraph<GRState>(GTrim->getCFG(), GTrim->getCodeDecl(),
212 GTrim->getContext());
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000213
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000214 // Sometimes TrimGraph can contain a cycle. Perform a reverse DFS
215 // to the root node, and then construct a new graph that contains only
216 // a single path.
Ted Kremenek3148eb42009-01-24 00:55:43 +0000217 llvm::DenseMap<const void*,unsigned> Visited;
218 llvm::SmallVector<const ExplodedNode<GRState>*, 10> WS;
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000219 WS.push_back(N);
220 unsigned cnt = 0;
Ted Kremenek3148eb42009-01-24 00:55:43 +0000221 const ExplodedNode<GRState>* Root = 0;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000222
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000223 while (!WS.empty()) {
Ted Kremenek3148eb42009-01-24 00:55:43 +0000224 const ExplodedNode<GRState>* Node = WS.back();
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000225 WS.pop_back();
226
227 if (Visited.find(Node) != Visited.end())
228 continue;
229
230 Visited[Node] = cnt++;
231
232 if (Node->pred_empty()) {
233 Root = Node;
234 break;
235 }
236
Ted Kremenek3148eb42009-01-24 00:55:43 +0000237 for (ExplodedNode<GRState>::const_pred_iterator I=Node->pred_begin(),
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000238 E=Node->pred_end(); I!=E; ++I)
239 WS.push_back(*I);
240 }
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000241
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000242 assert (Root);
243
244 // Now walk from the root down the DFS path, always taking the successor
245 // with the lowest number.
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000246 ExplodedNode<GRState> *Last = 0, *First = 0;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000247
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000248 for ( N = Root ;;) {
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000249 // Lookup the number associated with the current node.
Ted Kremenek3148eb42009-01-24 00:55:43 +0000250 llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000251 assert (I != Visited.end());
252
253 // Create the equivalent node in the new graph with the same state
254 // and location.
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000255 ExplodedNode<GRState>* NewN =
Ted Kremenek3148eb42009-01-24 00:55:43 +0000256 GNew->getNode(N->getLocation(), N->getState());
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000257
258 // Link up the new node with the previous node.
259 if (Last)
260 NewN->addPredecessor(Last);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000261
262 Last = NewN;
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000263
264 // Are we at the final node?
265 if (I->second == 0) {
266 First = NewN;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000267 break;
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000268 }
269
270 // Find the next successor node. We choose the node that is marked
271 // with the lowest DFS number.
Ted Kremenek3148eb42009-01-24 00:55:43 +0000272 ExplodedNode<GRState>::const_succ_iterator SI = N->succ_begin();
273 ExplodedNode<GRState>::const_succ_iterator SE = N->succ_end();
Ted Kremenekc1da4412008-06-17 19:14:06 +0000274 N = 0;
275
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000276 for (unsigned MinVal = 0; SI != SE; ++SI) {
Ted Kremenekc1da4412008-06-17 19:14:06 +0000277
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000278 I = Visited.find(*SI);
279
280 if (I == Visited.end())
281 continue;
282
283 if (!N || I->second < MinVal) {
284 N = *SI;
285 MinVal = I->second;
Ted Kremenekc1da4412008-06-17 19:14:06 +0000286 }
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000287 }
288
289 assert (N);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000290 }
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000291
292 assert (First);
Ted Kremenek3148eb42009-01-24 00:55:43 +0000293 return std::make_pair(GNew, First);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000294}
295
Ted Kremenek3148eb42009-01-24 00:55:43 +0000296static const VarDecl*
297GetMostRecentVarDeclBinding(const ExplodedNode<GRState>* N,
298 GRStateManager& VMgr, SVal X) {
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000299
300 for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
301
302 ProgramPoint P = N->getLocation();
303
304 if (!isa<PostStmt>(P))
305 continue;
306
307 DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
308
309 if (!DR)
310 continue;
311
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000312 SVal Y = VMgr.GetSVal(N->getState(), DR);
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000313
314 if (X != Y)
315 continue;
316
317 VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl());
318
319 if (!VD)
320 continue;
321
322 return VD;
323 }
324
325 return 0;
326}
327
Ted Kremenek9e240492008-10-04 05:50:14 +0000328namespace {
329class VISIBILITY_HIDDEN NotableSymbolHandler
330 : public StoreManager::BindingsHandler {
331
Ted Kremenek2dabd432008-12-05 02:27:51 +0000332 SymbolRef Sym;
Ted Kremenek9e240492008-10-04 05:50:14 +0000333 const GRState* PrevSt;
Ted Kremenek3148eb42009-01-24 00:55:43 +0000334 const Stmt* S;
Ted Kremenek9e240492008-10-04 05:50:14 +0000335 GRStateManager& VMgr;
Ted Kremenek3148eb42009-01-24 00:55:43 +0000336 const ExplodedNode<GRState>* Pred;
Ted Kremenek9e240492008-10-04 05:50:14 +0000337 PathDiagnostic& PD;
338 BugReporter& BR;
339
340public:
341
Ted Kremenek3148eb42009-01-24 00:55:43 +0000342 NotableSymbolHandler(SymbolRef sym, const GRState* prevst, const Stmt* s,
343 GRStateManager& vmgr, const ExplodedNode<GRState>* pred,
Ted Kremenek9e240492008-10-04 05:50:14 +0000344 PathDiagnostic& pd, BugReporter& br)
345 : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
346
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000347 bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, SVal V) {
Ted Kremenek9e240492008-10-04 05:50:14 +0000348
Ted Kremenek2dabd432008-12-05 02:27:51 +0000349 SymbolRef ScanSym;
Ted Kremenek9e240492008-10-04 05:50:14 +0000350
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000351 if (loc::SymbolVal* SV = dyn_cast<loc::SymbolVal>(&V))
Ted Kremenek9e240492008-10-04 05:50:14 +0000352 ScanSym = SV->getSymbol();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000353 else if (nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(&V))
Ted Kremenek9e240492008-10-04 05:50:14 +0000354 ScanSym = SV->getSymbol();
355 else
356 return true;
357
358 if (ScanSym != Sym)
359 return true;
360
361 // Check if the previous state has this binding.
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000362 SVal X = VMgr.GetSVal(PrevSt, loc::MemRegionVal(R));
Ted Kremenek9e240492008-10-04 05:50:14 +0000363
364 if (X == V) // Same binding?
365 return true;
366
367 // Different binding. Only handle assignments for now. We don't pull
368 // this check out of the loop because we will eventually handle other
369 // cases.
370
371 VarDecl *VD = 0;
372
Ted Kremenek3148eb42009-01-24 00:55:43 +0000373 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
Ted Kremenek9e240492008-10-04 05:50:14 +0000374 if (!B->isAssignmentOp())
375 return true;
376
377 // What variable did we assign to?
378 DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
379
380 if (!DR)
381 return true;
382
383 VD = dyn_cast<VarDecl>(DR->getDecl());
384 }
Ted Kremenek3148eb42009-01-24 00:55:43 +0000385 else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
Ted Kremenekf21a4b42008-10-06 18:37:46 +0000386 // FIXME: Eventually CFGs won't have DeclStmts. Right now we
387 // assume that each DeclStmt has a single Decl. This invariant
388 // holds by contruction in the CFG.
389 VD = dyn_cast<VarDecl>(*DS->decl_begin());
390 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000391
392 if (!VD)
393 return true;
394
395 // What is the most recently referenced variable with this binding?
Ted Kremenek3148eb42009-01-24 00:55:43 +0000396 const VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
Ted Kremenek9e240492008-10-04 05:50:14 +0000397
398 if (!MostRecent)
399 return true;
400
401 // Create the diagnostic.
402
403 FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
404
405 if (VD->getType()->isPointerLikeType()) {
Chris Lattnerd9d22dd2008-11-24 05:29:24 +0000406 std::string msg = "'" + std::string(VD->getNameAsString()) +
407 "' now aliases '" + MostRecent->getNameAsString() + "'";
Ted Kremenek9e240492008-10-04 05:50:14 +0000408
409 PD.push_front(new PathDiagnosticPiece(L, msg));
410 }
411
412 return true;
413 }
414};
415}
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000416
Ted Kremenek3148eb42009-01-24 00:55:43 +0000417static void HandleNotableSymbol(const ExplodedNode<GRState>* N,
418 const Stmt* S,
Ted Kremenek2dabd432008-12-05 02:27:51 +0000419 SymbolRef Sym, BugReporter& BR,
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000420 PathDiagnostic& PD) {
421
Ted Kremenek3148eb42009-01-24 00:55:43 +0000422 const ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin();
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000423 const GRState* PrevSt = Pred ? Pred->getState() : 0;
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000424
425 if (!PrevSt)
426 return;
427
Ted Kremenek9e240492008-10-04 05:50:14 +0000428 // Look at the region bindings of the current state that map to the
429 // specified symbol. Are any of them not in the previous state?
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000430 GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
Ted Kremenek9e240492008-10-04 05:50:14 +0000431 NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
432 cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
433}
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000434
Ted Kremenek9e240492008-10-04 05:50:14 +0000435namespace {
436class VISIBILITY_HIDDEN ScanNotableSymbols
437 : public StoreManager::BindingsHandler {
438
Ted Kremenek2dabd432008-12-05 02:27:51 +0000439 llvm::SmallSet<SymbolRef, 10> AlreadyProcessed;
Ted Kremenek3148eb42009-01-24 00:55:43 +0000440 const ExplodedNode<GRState>* N;
Ted Kremenek9e240492008-10-04 05:50:14 +0000441 Stmt* S;
442 GRBugReporter& BR;
443 PathDiagnostic& PD;
444
445public:
Ted Kremenek3148eb42009-01-24 00:55:43 +0000446 ScanNotableSymbols(const ExplodedNode<GRState>* n, Stmt* s, GRBugReporter& br,
Ted Kremenek9e240492008-10-04 05:50:14 +0000447 PathDiagnostic& pd)
448 : N(n), S(s), BR(br), PD(pd) {}
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000449
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000450 bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, SVal V) {
Ted Kremenek2dabd432008-12-05 02:27:51 +0000451 SymbolRef ScanSym;
Ted Kremenek9e240492008-10-04 05:50:14 +0000452
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000453 if (loc::SymbolVal* SV = dyn_cast<loc::SymbolVal>(&V))
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000454 ScanSym = SV->getSymbol();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000455 else if (nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(&V))
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000456 ScanSym = SV->getSymbol();
457 else
Ted Kremenek9e240492008-10-04 05:50:14 +0000458 return true;
459
460 assert (ScanSym.isInitialized());
461
462 if (!BR.isNotable(ScanSym))
463 return true;
464
465 if (AlreadyProcessed.count(ScanSym))
466 return true;
467
468 AlreadyProcessed.insert(ScanSym);
469
470 HandleNotableSymbol(N, S, ScanSym, BR, PD);
471 return true;
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000472 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000473};
474} // end anonymous namespace
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000475
Ted Kremenekc0959972008-07-02 21:24:01 +0000476void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
477 BugReport& R) {
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000478
Ted Kremenek3148eb42009-01-24 00:55:43 +0000479 const ExplodedNode<GRState>* N = R.getEndNode();
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000480
481 if (!N) return;
482
483 // Construct a new graph that contains only a single path from the error
484 // node to a root.
485
Ted Kremenek3148eb42009-01-24 00:55:43 +0000486 const std::pair<ExplodedGraph<GRState>*, ExplodedNode<GRState>*>
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000487 GPair = MakeReportGraph(&getGraph(), N);
488
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000489 llvm::OwningPtr<ExplodedGraph<GRState> > ReportGraph(GPair.first);
Ted Kremeneka43a1eb2008-04-23 23:02:12 +0000490 assert(GPair.second->getLocation() == N->getLocation());
491 N = GPair.second;
492
493 // Start building the path diagnostic...
494
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000495 if (PathDiagnosticPiece* Piece = R.getEndPath(*this, N))
496 PD.push_back(Piece);
497 else
498 return;
Ted Kremenek6837faa2008-04-09 00:20:43 +0000499
Ted Kremenek3148eb42009-01-24 00:55:43 +0000500 const ExplodedNode<GRState>* NextNode = N->pred_empty()
501 ? NULL : *(N->pred_begin());
Ted Kremenek6837faa2008-04-09 00:20:43 +0000502
Ted Kremenekc0959972008-07-02 21:24:01 +0000503 ASTContext& Ctx = getContext();
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000504 SourceManager& SMgr = Ctx.getSourceManager();
505
Ted Kremenek6837faa2008-04-09 00:20:43 +0000506 while (NextNode) {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000507
Ted Kremenek3148eb42009-01-24 00:55:43 +0000508 const ExplodedNode<GRState>* LastNode = N;
Ted Kremenek6837faa2008-04-09 00:20:43 +0000509 N = NextNode;
Ted Kremenekbd7efa82008-04-17 23:44:37 +0000510 NextNode = GetNextNode(N);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000511
512 ProgramPoint P = N->getLocation();
513
514 if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
515
516 CFGBlock* Src = BE->getSrc();
517 CFGBlock* Dst = BE->getDst();
518
519 Stmt* T = Src->getTerminator();
520
521 if (!T)
522 continue;
523
524 FullSourceLoc L(T->getLocStart(), SMgr);
525
526 switch (T->getStmtClass()) {
527 default:
528 break;
529
530 case Stmt::GotoStmtClass:
531 case Stmt::IndirectGotoStmtClass: {
532
533 Stmt* S = GetStmt(LastNode->getLocation());
534
535 if (!S)
536 continue;
537
538 std::ostringstream os;
539
540 os << "Control jumps to line "
Chris Lattnerf7cf85b2009-01-16 07:36:28 +0000541 << SMgr.getInstantiationLineNumber(S->getLocStart()) << ".\n";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000542
543 PD.push_front(new PathDiagnosticPiece(L, os.str()));
544 break;
545 }
546
547 case Stmt::SwitchStmtClass: {
548
549 // Figure out what case arm we took.
Ted Kremenek5a429952008-04-23 23:35:07 +0000550
Ted Kremenek61f3e052008-04-03 04:42:52 +0000551 std::ostringstream os;
Ted Kremenek5a429952008-04-23 23:35:07 +0000552
553 if (Stmt* S = Dst->getLabel())
554 switch (S->getStmtClass()) {
Chris Lattnerf7cf85b2009-01-16 07:36:28 +0000555 default:
Ted Kremenek3ddc4d52008-12-20 01:41:43 +0000556 os << "No cases match in the switch statement. "
557 "Control jumps to line "
Chris Lattnerf7cf85b2009-01-16 07:36:28 +0000558 << SMgr.getInstantiationLineNumber(S->getLocStart()) << ".\n";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000559 break;
Chris Lattnerf7cf85b2009-01-16 07:36:28 +0000560 case Stmt::DefaultStmtClass:
561 os << "Control jumps to the 'default' case at line "
562 << SMgr.getInstantiationLineNumber(S->getLocStart()) << ".\n";
563 break;
Ted Kremenek61f3e052008-04-03 04:42:52 +0000564
565 case Stmt::CaseStmtClass: {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000566 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;
Chris Lattnerd9d22dd2008-11-24 05:29:24 +0000582 os << D->getNameAsString();
Ted Kremenek5a429952008-04-23 23:35:07 +0000583 }
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 "
Chris Lattnerf7cf85b2009-01-16 07:36:28 +0000603 << SMgr.getInstantiationLineNumber(S->getLocStart()) << ".\n";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000604
605 break;
Ted Kremenek61f3e052008-04-03 04:42:52 +0000606 }
607 }
Ted Kremenek56783922008-04-25 01:29:56 +0000608 else {
Ted Kremenekc3517eb2008-09-12 18:17:46 +0000609 os << "'Default' branch taken. ";
Ted Kremenek2673c9f2008-04-25 19:01:27 +0000610 ExecutionContinues(os, SMgr, LastNode);
Ted Kremenek56783922008-04-25 01:29:56 +0000611 }
Ted Kremenek61f3e052008-04-03 04:42:52 +0000612
613 PD.push_front(new PathDiagnosticPiece(L, os.str()));
614 break;
615 }
Ted Kremenek2673c9f2008-04-25 19:01:27 +0000616
617 case Stmt::BreakStmtClass:
618 case Stmt::ContinueStmtClass: {
619 std::ostringstream os;
620 ExecutionContinues(os, SMgr, LastNode);
621 PD.push_front(new PathDiagnosticPiece(L, os.str()));
622 break;
623 }
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000624
625 case Stmt::ConditionalOperatorClass: {
Ted Kremenek61f3e052008-04-03 04:42:52 +0000626
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000627 std::ostringstream os;
628 os << "'?' condition evaluates to ";
629
630 if (*(Src->succ_begin()+1) == Dst)
631 os << "false.";
632 else
633 os << "true.";
Ted Kremenek61f3e052008-04-03 04:42:52 +0000634
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000635 PD.push_front(new PathDiagnosticPiece(L, os.str()));
636
637 break;
638 }
639
640 case Stmt::DoStmtClass: {
641
642 if (*(Src->succ_begin()) == Dst) {
643
644 std::ostringstream os;
645
Ted Kremenekc3517eb2008-09-12 18:17:46 +0000646 os << "Loop condition is true. ";
Ted Kremenek143ca222008-05-06 18:11:09 +0000647 ExecutionContinues(os, SMgr, Dst);
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000648
649 PD.push_front(new PathDiagnosticPiece(L, os.str()));
650 }
651 else
652 PD.push_front(new PathDiagnosticPiece(L,
653 "Loop condition is false. Exiting loop."));
654
655 break;
656 }
657
Ted Kremenek61f3e052008-04-03 04:42:52 +0000658 case Stmt::WhileStmtClass:
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000659 case Stmt::ForStmtClass: {
660
661 if (*(Src->succ_begin()+1) == Dst) {
662
663 std::ostringstream os;
664
Ted Kremenekc3517eb2008-09-12 18:17:46 +0000665 os << "Loop condition is false. ";
Ted Kremenek143ca222008-05-06 18:11:09 +0000666 ExecutionContinues(os, SMgr, Dst);
Ted Kremenek706e3cf2008-04-07 23:35:17 +0000667
668 PD.push_front(new PathDiagnosticPiece(L, os.str()));
669 }
670 else
671 PD.push_front(new PathDiagnosticPiece(L,
672 "Loop condition is true. Entering loop body."));
673
674 break;
675 }
676
Ted Kremenek61f3e052008-04-03 04:42:52 +0000677 case Stmt::IfStmtClass: {
678
679 if (*(Src->succ_begin()+1) == Dst)
680 PD.push_front(new PathDiagnosticPiece(L, "Taking false branch."));
681 else
682 PD.push_front(new PathDiagnosticPiece(L, "Taking true branch."));
683
684 break;
685 }
686 }
Ted Kremenek6837faa2008-04-09 00:20:43 +0000687 }
Ted Kremenek5a429952008-04-23 23:35:07 +0000688
689 if (PathDiagnosticPiece* p = R.VisitNode(N, NextNode, *ReportGraph, *this))
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000690 PD.push_front(p);
691
Ted Kremenek9e240492008-10-04 05:50:14 +0000692 if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
693 // Scan the region bindings, and see if a "notable" symbol has a new
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000694 // lval binding.
Ted Kremenek9e240492008-10-04 05:50:14 +0000695 ScanNotableSymbols SNS(N, PS->getStmt(), *this, PD);
696 getStateManager().iterBindings(N->getState(), SNS);
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000697 }
Ted Kremenek61f3e052008-04-03 04:42:52 +0000698 }
699}
700
Ted Kremenek1aa44c72008-05-22 23:45:19 +0000701
Ted Kremenek95cc1ba2008-04-18 20:54:29 +0000702bool BugTypeCacheLocation::isCached(BugReport& R) {
703
Ted Kremenek3148eb42009-01-24 00:55:43 +0000704 const ExplodedNode<GRState>* N = R.getEndNode();
Ted Kremenek61f3e052008-04-03 04:42:52 +0000705
Ted Kremenek329d2cc2008-04-18 02:24:50 +0000706 if (!N)
707 return false;
Ted Kremenek95cc1ba2008-04-18 20:54:29 +0000708
709 // Cache the location of the error. Don't emit the same
Ted Kremenek61f3e052008-04-03 04:42:52 +0000710 // warning for the same error type that occurs at the same program
711 // location but along a different path.
712
Ted Kremenek76d90c82008-05-16 18:33:14 +0000713 return isCached(N->getLocation());
714}
715
716bool BugTypeCacheLocation::isCached(ProgramPoint P) {
Ted Kremenekd4527582008-09-16 18:44:52 +0000717 if (CachedErrors.count(P))
Ted Kremenek61f3e052008-04-03 04:42:52 +0000718 return true;
719
Ted Kremenekd4527582008-09-16 18:44:52 +0000720 CachedErrors.insert(P);
Ted Kremenek61f3e052008-04-03 04:42:52 +0000721 return false;
722}
723
Ted Kremenek75840e12008-04-18 01:56:37 +0000724void BugReporter::EmitWarning(BugReport& R) {
725
Ted Kremenek95cc1ba2008-04-18 20:54:29 +0000726 if (R.getBugType().isCached(R))
Ted Kremenek61f3e052008-04-03 04:42:52 +0000727 return;
Ted Kremenek75840e12008-04-18 01:56:37 +0000728
Ted Kremenek8c036c72008-09-20 04:23:38 +0000729 llvm::OwningPtr<PathDiagnostic> D(new PathDiagnostic(R.getName(),
730 R.getCategory()));
Ted Kremenek55851142008-04-22 16:15:03 +0000731 GeneratePathDiagnostic(*D.get(), R);
Ted Kremenek072192b2008-04-30 23:47:44 +0000732
733 // Get the meta data.
Ted Kremenek072192b2008-04-30 23:47:44 +0000734 std::pair<const char**, const char**> Meta = R.getExtraDescriptiveText();
Ted Kremenek3148eb42009-01-24 00:55:43 +0000735 for (const char** s = Meta.first; s != Meta.second; ++s) D->addMeta(*s);
Ted Kremenek75840e12008-04-18 01:56:37 +0000736
Ted Kremenek3148eb42009-01-24 00:55:43 +0000737 // Emit a summary diagnostic to the regular Diagnostics engine.
Ted Kremenekc0959972008-07-02 21:24:01 +0000738 PathDiagnosticClient* PD = getPathDiagnosticClient();
Ted Kremenek3148eb42009-01-24 00:55:43 +0000739 const SourceRange *Beg = 0, *End = 0;
740 R.getRanges(*this, Beg, End);
741 Diagnostic& Diag = getDiagnostic();
742 FullSourceLoc L = R.getLocation(getSourceManager());
743 const char *msg = PD ? R.getBugType().getName() : R.getDescription();
744 unsigned ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, msg);
Ted Kremenek57202072008-07-14 17:40:50 +0000745
Ted Kremenek3148eb42009-01-24 00:55:43 +0000746 switch (End-Beg) {
Chris Lattner0a14eee2008-11-18 07:04:44 +0000747 default: assert(0 && "Don't handle this many ranges yet!");
748 case 0: Diag.Report(L, ErrorDiag); break;
749 case 1: Diag.Report(L, ErrorDiag) << Beg[0]; break;
750 case 2: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1]; break;
751 case 3: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1] << Beg[2]; break;
Ted Kremenek2f0e89e2008-04-18 22:56:53 +0000752 }
Ted Kremenek3148eb42009-01-24 00:55:43 +0000753
754 // Emit a full diagnostic for the path if we have a PathDiagnosticClient.
755 if (!PD)
756 return;
757
758 if (D->empty()) {
759 PathDiagnosticPiece* piece = new PathDiagnosticPiece(L, R.getDescription());
760 for ( ; Beg != End; ++Beg) piece->addRange(*Beg);
761 D->push_back(piece);
762 }
763
764 PD->HandlePathDiagnostic(D.take());
Ted Kremenek61f3e052008-04-03 04:42:52 +0000765}
Ted Kremenek57202072008-07-14 17:40:50 +0000766
Ted Kremenek8c036c72008-09-20 04:23:38 +0000767void BugReporter::EmitBasicReport(const char* name, const char* str,
768 SourceLocation Loc,
769 SourceRange* RBeg, unsigned NumRanges) {
770 EmitBasicReport(name, "", str, Loc, RBeg, NumRanges);
771}
Ted Kremenek57202072008-07-14 17:40:50 +0000772
Ted Kremenek8c036c72008-09-20 04:23:38 +0000773void BugReporter::EmitBasicReport(const char* name, const char* category,
774 const char* str, SourceLocation Loc,
775 SourceRange* RBeg, unsigned NumRanges) {
776
777 SimpleBugType BT(name, category, 0);
Ted Kremenek57202072008-07-14 17:40:50 +0000778 DiagCollector C(BT);
779 Diagnostic& Diag = getDiagnostic();
Chris Lattner470e5fc2008-11-18 06:07:40 +0000780
781 DiagnosticClient *OldClient = Diag.getClient();
782 Diag.setClient(&C);
Chris Lattner0a14eee2008-11-18 07:04:44 +0000783 FullSourceLoc L = getContext().getFullLoc(Loc);
784 unsigned DiagID = Diag.getCustomDiagID(Diagnostic::Warning, str);
785
786 switch (NumRanges) {
787 default: assert(0 && "Don't handle this many ranges yet!");
788 case 0: Diag.Report(L, DiagID); break;
789 case 1: Diag.Report(L, DiagID) << RBeg[0]; break;
790 case 2: Diag.Report(L, DiagID) << RBeg[0] << RBeg[1]; break;
791 case 3: Diag.Report(L, DiagID) << RBeg[0] << RBeg[1] << RBeg[2]; break;
792 }
793
Chris Lattner470e5fc2008-11-18 06:07:40 +0000794 Diag.setClient(OldClient);
Ted Kremenek57202072008-07-14 17:40:50 +0000795
796 for (DiagCollector::iterator I = C.begin(), E = C.end(); I != E; ++I)
797 EmitWarning(*I);
798}
Ted Kremenekcabe6682009-01-23 20:28:53 +0000799
800void DiagCollector::HandleDiagnostic(Diagnostic::Level DiagLevel,
801 const DiagnosticInfo &Info) {
802
803 // FIXME: Use a map from diag::kind to BugType, instead of having just
804 // one BugType.
805 const char *Desc = Info.getDiags()->getDescription(Info.getID());
806 Reports.push_back(DiagBugReport(Desc, D, Info.getLocation()));
807 DiagBugReport& R = Reports.back();
808
809 for (unsigned i = 0, e = Info.getNumRanges(); i != e; ++i)
810 R.addRange(Info.getRange(i));
811
812 // FIXME: This is losing/ignoring formatting.
813 for (unsigned i = 0, e = Info.getNumArgs(); i != e; ++i) {
814 switch (Info.getArgKind(i)) {
815 case Diagnostic::ak_std_string:
816 R.addString(Info.getArgStdStr(i));
817 break;
818 case Diagnostic::ak_c_string:
819 R.addString(Info.getArgCStr(i));
820 break;
821 case Diagnostic::ak_sint:
822 R.addString(llvm::itostr(Info.getArgSInt(i)));
823 break;
824 case Diagnostic::ak_uint:
825 R.addString(llvm::utostr_32(Info.getArgUInt(i)));
826 break;
827 case Diagnostic::ak_identifierinfo:
828 R.addString(Info.getArgIdentifier(i)->getName());
829 break;
830 case Diagnostic::ak_qualtype:
831 case Diagnostic::ak_declarationname: {
832 llvm::SmallString<64> Str;
833 Info.getDiags()->ConvertArgToString(Info.getArgKind(i),
834 Info.getRawArg(i), 0, 0, 0, 0, Str);
835 R.addString(std::string(Str.begin(), Str.end()));
836 break;
837 }
838 }
839 }
840}
Ted Kremenek57202072008-07-14 17:40:50 +0000841