 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
51.8% |
350 / 676 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
67.6% |
457 / 676 |
| |
|
Line Coverage: |
65.9% |
563 / 854 |
| |
 |
|
 |
1 : // 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.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "clang/Checker/BugReporter/BugReporter.h"
16 : #include "clang/Checker/PathSensitive/GRExprEngine.h"
17 : #include "clang/AST/ASTContext.h"
18 : #include "clang/Analysis/CFG.h"
19 : #include "clang/AST/Expr.h"
20 : #include "clang/AST/ParentMap.h"
21 : #include "clang/AST/StmtObjC.h"
22 : #include "clang/Basic/SourceManager.h"
23 : #include "clang/Analysis/ProgramPoint.h"
24 : #include "clang/Checker/BugReporter/PathDiagnostic.h"
25 : #include "llvm/Support/raw_ostream.h"
26 : #include "llvm/ADT/DenseMap.h"
27 : #include "llvm/ADT/STLExtras.h"
28 : #include "llvm/ADT/OwningPtr.h"
29 : #include <queue>
30 :
31 : using namespace clang;
32 :
946: branch 0 taken
946: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
946: branch 7 taken
33 946: BugReporterVisitor::~BugReporterVisitor() {}
34 580: BugReporterContext::~BugReporterContext() {
0: branch 4 not taken
0: branch 5 not taken
0: branch 10 not taken
0: branch 11 not taken
792: branch 16 taken
580: branch 17 taken
35 1372: for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I)
0: branch 2 not taken
0: branch 3 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 10 not taken
0: branch 11 not taken
0: branch 13 not taken
0: branch 14 not taken
212: branch 18 taken
580: branch 19 taken
212: branch 21 taken
0: branch 22 not taken
36 792: if ((*I)->isOwnedByReporterContext()) delete *I;
0: branch 1 not taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 9 not taken
580: branch 10 taken
37 580: }
38 :
39 : //===----------------------------------------------------------------------===//
40 : // Helper routines for walking the ExplodedGraph and fetching statements.
41 : //===----------------------------------------------------------------------===//
42 :
43 1615: static inline const Stmt* GetStmt(ProgramPoint P) {
1476: branch 1 taken
139: branch 2 taken
44 1615: if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P))
45 1476: return SP->getStmt();
128: branch 1 taken
11: branch 2 taken
46 139: else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P))
47 128: return BE->getSrc()->getTerminator();
48 :
49 11: return 0;
50 : }
51 :
52 : static inline const ExplodedNode*
53 7875: GetPredecessorNode(const ExplodedNode* N) {
580: branch 1 taken
7295: branch 2 taken
54 7875: return N->pred_empty() ? NULL : *(N->pred_begin());
55 : }
56 :
57 : static inline const ExplodedNode*
58 4: GetSuccessorNode(const ExplodedNode* N) {
0: branch 1 not taken
4: branch 2 taken
59 4: return N->succ_empty() ? NULL : *(N->succ_begin());
60 : }
61 :
62 14: static const Stmt* GetPreviousStmt(const ExplodedNode* N) {
28: branch 2 taken
0: branch 3 not taken
63 28: for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
14: branch 2 taken
14: branch 3 taken
64 28: if (const Stmt *S = GetStmt(N->getLocation()))
65 14: return S;
66 :
67 0: return 0;
68 : }
69 :
70 2: static const Stmt* GetNextStmt(const ExplodedNode* N) {
4: branch 2 taken
0: branch 3 not taken
71 4: for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
2: branch 2 taken
2: branch 3 taken
72 4: if (const Stmt *S = GetStmt(N->getLocation())) {
73 : // Check if the statement is '?' or '&&'/'||'. These are "merges",
74 : // not actual statement points.
0: branch 1 not taken
0: branch 2 not taken
2: branch 3 taken
75 2: switch (S->getStmtClass()) {
76 : case Stmt::ChooseExprClass:
77 0: case Stmt::ConditionalOperatorClass: continue;
78 : case Stmt::BinaryOperatorClass: {
79 0: BinaryOperator::Opcode Op = cast<BinaryOperator>(S)->getOpcode();
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
80 0: if (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr)
81 0: continue;
82 : break;
83 : }
84 : default:
85 : break;
86 : }
87 :
88 : // Some expressions don't have locations.
2: branch 2 taken
0: branch 3 not taken
89 2: if (S->getLocStart().isInvalid())
90 0: continue;
91 :
92 2: return S;
93 : }
94 :
95 0: return 0;
96 : }
97 :
98 : static inline const Stmt*
99 1168: GetCurrentOrPreviousStmt(const ExplodedNode* N) {
1159: branch 2 taken
9: branch 3 taken
100 1168: if (const Stmt *S = GetStmt(N->getLocation()))
101 1159: return S;
102 :
103 9: return GetPreviousStmt(N);
104 : }
105 :
106 : static inline const Stmt*
107 : GetCurrentOrNextStmt(const ExplodedNode* N) {
108 : if (const Stmt *S = GetStmt(N->getLocation()))
109 : return S;
110 :
111 : return GetNextStmt(N);
112 : }
113 :
114 : //===----------------------------------------------------------------------===//
115 : // PathDiagnosticBuilder and its associated routines and helper objects.
116 : //===----------------------------------------------------------------------===//
117 :
118 : typedef llvm::DenseMap<const ExplodedNode*,
119 : const ExplodedNode*> NodeBackMap;
120 :
121 : namespace {
122 : class NodeMapClosure : public BugReport::NodeResolver {
123 : NodeBackMap& M;
124 : public:
125 580: NodeMapClosure(NodeBackMap *m) : M(*m) {}
0: branch 1 not taken
580: branch 2 taken
0: branch 5 not taken
0: branch 6 not taken
126 580: ~NodeMapClosure() {}
127 :
128 1713: const ExplodedNode* getOriginalNode(const ExplodedNode* N) {
129 1713: NodeBackMap::iterator I = M.find(N);
0: branch 3 not taken
1713: branch 4 taken
130 1713: return I == M.end() ? 0 : I->second;
131 : }
132 : };
133 :
0: branch 3 not taken
0: branch 4 not taken
0: branch 9 not taken
580: branch 10 taken
134 580: class PathDiagnosticBuilder : public BugReporterContext {
135 : BugReport *R;
136 : PathDiagnosticClient *PDC;
137 : llvm::OwningPtr<ParentMap> PM;
138 : NodeMapClosure NMC;
139 : public:
140 : PathDiagnosticBuilder(GRBugReporter &br,
141 : BugReport *r, NodeBackMap *Backmap,
142 580: PathDiagnosticClient *pdc)
143 : : BugReporterContext(br),
144 580: R(r), PDC(pdc), NMC(Backmap) {
145 580: addVisitor(R);
146 580: }
147 :
148 : PathDiagnosticLocation ExecutionContinues(const ExplodedNode* N);
149 :
150 : PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream& os,
151 : const ExplodedNode* N);
152 :
153 579: Decl const &getCodeDecl() { return R->getEndNode()->getCodeDecl(); }
154 :
155 8113: ParentMap& getParentMap() { return R->getEndNode()->getParentMap(); }
156 :
157 5518: const Stmt *getParent(const Stmt *S) {
158 5518: return getParentMap().getParent(S);
159 : }
160 :
161 1713: virtual NodeMapClosure& getNodeResolver() { return NMC; }
162 : BugReport& getReport() { return *R; }
163 :
164 : PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
165 :
166 : PathDiagnosticLocation
167 : getEnclosingStmtLocation(const PathDiagnosticLocation &L) {
168 : if (const Stmt *S = L.asStmt())
169 : return getEnclosingStmtLocation(S);
170 :
171 : return L;
172 : }
173 :
174 580: PathDiagnosticClient::PathGenerationScheme getGenerationScheme() const {
7: branch 0 taken
573: branch 1 taken
175 580: return PDC ? PDC->getGenerationScheme() : PathDiagnosticClient::Extensive;
176 : }
177 :
178 0: bool supportsLogicalOpControlFlow() const {
0: branch 0 not taken
0: branch 1 not taken
179 0: return PDC ? PDC->supportsLogicalOpControlFlow() : true;
180 : }
181 : };
182 : } // end anonymous namespace
183 :
184 : PathDiagnosticLocation
185 2: PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode* N) {
2: branch 1 taken
0: branch 2 not taken
186 2: if (const Stmt *S = GetNextStmt(N))
187 2: return PathDiagnosticLocation(S, getSourceManager());
188 :
189 : return FullSourceLoc(N->getLocationContext()->getDecl()->getBodyRBrace(),
190 0: getSourceManager());
191 : }
192 :
193 : PathDiagnosticLocation
194 : PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream& os,
195 0: const ExplodedNode* N) {
196 :
197 : // Slow, but probably doesn't matter.
0: branch 2 not taken
0: branch 3 not taken
198 0: if (os.str().empty())
199 0: os << ' ';
200 :
201 0: const PathDiagnosticLocation &Loc = ExecutionContinues(N);
202 :
0: branch 1 not taken
0: branch 2 not taken
203 0: if (Loc.asStmt())
204 : os << "Execution continues on line "
205 : << getSourceManager().getInstantiationLineNumber(Loc.asLocation())
206 0: << '.';
207 : else {
208 0: os << "Execution jumps to the end of the ";
209 0: const Decl *D = N->getLocationContext()->getDecl();
0: branch 1 not taken
0: branch 2 not taken
210 0: if (isa<ObjCMethodDecl>(D))
211 0: os << "method";
0: branch 1 not taken
0: branch 2 not taken
212 0: else if (isa<FunctionDecl>(D))
213 0: os << "function";
214 : else {
0: branch 1 not taken
0: branch 2 not taken
215 0: assert(isa<BlockDecl>(D));
216 0: os << "anonymous block";
217 : }
218 0: os << '.';
219 : }
220 :
221 0: return Loc;
222 : }
223 :
224 4041: static bool IsNested(const Stmt *S, ParentMap &PM) {
2346: branch 1 taken
1695: branch 2 taken
1598: branch 5 taken
748: branch 6 taken
1598: branch 7 taken
2443: branch 8 taken
225 4041: if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
226 1598: return true;
227 :
228 2443: const Stmt *Parent = PM.getParentIgnoreParens(S);
229 :
2408: branch 0 taken
35: branch 1 taken
230 2443: if (Parent)
2: branch 1 taken
2406: branch 2 taken
231 2408: switch (Parent->getStmtClass()) {
232 : case Stmt::ForStmtClass:
233 : case Stmt::DoStmtClass:
234 : case Stmt::WhileStmtClass:
235 2: return true;
236 : default:
237 : break;
238 : }
239 :
240 2441: return false;
241 : }
242 :
243 : PathDiagnosticLocation
244 2549: PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
0: branch 0 not taken
2549: branch 1 taken
245 2549: assert(S && "Null Stmt* passed to getEnclosingStmtLocation");
246 2549: ParentMap &P = getParentMap();
247 2549: SourceManager &SMgr = getSourceManager();
248 :
1600: branch 1 taken
2441: branch 2 taken
249 6590: while (IsNested(S, P)) {
250 1600: const Stmt *Parent = P.getParentIgnoreParens(S);
251 :
0: branch 0 not taken
1600: branch 1 taken
252 1600: if (!Parent)
253 0: break;
254 :
168: branch 1 taken
0: branch 2 not taken
0: branch 3 not taken
90: branch 4 taken
0: branch 5 not taken
4: branch 6 taken
145: branch 7 taken
0: branch 8 not taken
0: branch 9 not taken
1193: branch 10 taken
255 1600: switch (Parent->getStmtClass()) {
256 : case Stmt::BinaryOperatorClass: {
257 168: const BinaryOperator *B = cast<BinaryOperator>(Parent);
18: branch 1 taken
150: branch 2 taken
258 168: if (B->isLogicalOp())
259 18: return PathDiagnosticLocation(S, SMgr);
260 150: break;
261 : }
262 : case Stmt::CompoundStmtClass:
263 : case Stmt::StmtExprClass:
264 0: return PathDiagnosticLocation(S, SMgr);
265 : case Stmt::ChooseExprClass:
266 : // Similar to '?' if we are referring to condition, just have the edge
267 : // point to the entire choose expression.
0: branch 2 not taken
0: branch 3 not taken
268 0: if (cast<ChooseExpr>(Parent)->getCond() == S)
269 0: return PathDiagnosticLocation(Parent, SMgr);
270 : else
271 0: return PathDiagnosticLocation(S, SMgr);
272 : case Stmt::ConditionalOperatorClass:
273 : // For '?', if we are referring to condition, just have the edge point
274 : // to the entire '?' expression.
40: branch 2 taken
50: branch 3 taken
275 90: if (cast<ConditionalOperator>(Parent)->getCond() == S)
276 40: return PathDiagnosticLocation(Parent, SMgr);
277 : else
278 50: return PathDiagnosticLocation(S, SMgr);
279 : case Stmt::DoStmtClass:
280 0: return PathDiagnosticLocation(S, SMgr);
281 : case Stmt::ForStmtClass:
0: branch 2 not taken
4: branch 3 taken
282 4: if (cast<ForStmt>(Parent)->getBody() == S)
283 0: return PathDiagnosticLocation(S, SMgr);
284 4: break;
285 : case Stmt::IfStmtClass:
0: branch 2 not taken
145: branch 3 taken
286 145: if (cast<IfStmt>(Parent)->getCond() != S)
287 0: return PathDiagnosticLocation(S, SMgr);
288 145: break;
289 : case Stmt::ObjCForCollectionStmtClass:
0: branch 2 not taken
0: branch 3 not taken
290 0: if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
291 0: return PathDiagnosticLocation(S, SMgr);
292 0: break;
293 : case Stmt::WhileStmtClass:
0: branch 2 not taken
0: branch 3 not taken
294 0: if (cast<WhileStmt>(Parent)->getCond() != S)
295 0: return PathDiagnosticLocation(S, SMgr);
296 : break;
297 : default:
298 : break;
299 : }
300 :
301 1492: S = Parent;
302 : }
303 :
0: branch 0 not taken
2441: branch 1 taken
304 2441: assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
305 :
306 : // Special case: DeclStmts can appear in for statement declarations, in which
307 : // case the ForStmt is the context.
1216: branch 1 taken
1225: branch 2 taken
308 2441: if (isa<DeclStmt>(S)) {
1181: branch 1 taken
35: branch 2 taken
309 1216: if (const Stmt *Parent = P.getParent(S)) {
0: branch 1 not taken
1181: branch 2 taken
310 1181: switch (Parent->getStmtClass()) {
311 : case Stmt::ForStmtClass:
312 : case Stmt::ObjCForCollectionStmtClass:
313 0: return PathDiagnosticLocation(Parent, SMgr);
314 : default:
315 : break;
316 : }
317 : }
318 : }
199: branch 1 taken
1026: branch 2 taken
319 1225: else if (isa<BinaryOperator>(S)) {
320 : // Special case: the binary operator represents the initialization
321 : // code in a for statement (this can happen when the variable being
322 : // initialized is an old variable.
0: branch 0 not taken
199: branch 1 taken
323 199: if (const ForStmt *FS =
324 199: dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
0: branch 1 not taken
0: branch 2 not taken
325 0: if (FS->getInit() == S)
326 0: return PathDiagnosticLocation(FS, SMgr);
327 : }
328 : }
329 :
330 2441: return PathDiagnosticLocation(S, SMgr);
331 : }
332 :
333 : //===----------------------------------------------------------------------===//
334 : // ScanNotableSymbols: closure-like callback for scanning Store bindings.
335 : //===----------------------------------------------------------------------===//
336 :
337 : static const VarDecl*
338 : GetMostRecentVarDeclBinding(const ExplodedNode* N,
339 0: GRStateManager& VMgr, SVal X) {
340 :
0: branch 1 not taken
0: branch 2 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 7 not taken
0: branch 8 not taken
341 0: for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
342 :
343 0: ProgramPoint P = N->getLocation();
344 :
0: branch 1 not taken
0: branch 2 not taken
345 0: if (!isa<PostStmt>(P))
346 0: continue;
347 :
348 0: const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
349 :
0: branch 0 not taken
0: branch 1 not taken
350 0: if (!DR)
351 0: continue;
352 :
353 0: SVal Y = N->getState()->getSVal(DR);
354 :
0: branch 1 not taken
0: branch 2 not taken
355 0: if (X != Y)
356 0: continue;
357 :
358 0: const VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl());
359 :
0: branch 0 not taken
0: branch 1 not taken
360 0: if (!VD)
361 : continue;
362 :
363 0: return VD;
364 : }
365 :
366 0: return 0;
367 : }
368 :
369 : namespace {
370 : class NotableSymbolHandler
0: branch 1 not taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
371 0: : public StoreManager::BindingsHandler {
372 :
373 : SymbolRef Sym;
374 : const GRState* PrevSt;
375 : const Stmt* S;
376 : GRStateManager& VMgr;
377 : const ExplodedNode* Pred;
378 : PathDiagnostic& PD;
379 : BugReporter& BR;
380 :
381 : public:
382 :
383 : NotableSymbolHandler(SymbolRef sym, const GRState* prevst, const Stmt* s,
384 : GRStateManager& vmgr, const ExplodedNode* pred,
385 0: PathDiagnostic& pd, BugReporter& br)
386 0: : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
387 :
388 : bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
389 0: SVal V) {
390 :
391 0: SymbolRef ScanSym = V.getAsSymbol();
392 :
0: branch 0 not taken
0: branch 1 not taken
393 0: if (ScanSym != Sym)
394 0: return true;
395 :
396 : // Check if the previous state has this binding.
397 0: SVal X = PrevSt->getSVal(loc::MemRegionVal(R));
398 :
0: branch 1 not taken
0: branch 2 not taken
399 0: if (X == V) // Same binding?
400 0: return true;
401 :
402 : // Different binding. Only handle assignments for now. We don't pull
403 : // this check out of the loop because we will eventually handle other
404 : // cases.
405 :
406 0: VarDecl *VD = 0;
407 :
0: branch 1 not taken
0: branch 2 not taken
408 0: if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
0: branch 1 not taken
0: branch 2 not taken
409 0: if (!B->isAssignmentOp())
410 0: return true;
411 :
412 : // What variable did we assign to?
413 0: DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
414 :
0: branch 0 not taken
0: branch 1 not taken
415 0: if (!DR)
416 0: return true;
417 :
418 0: VD = dyn_cast<VarDecl>(DR->getDecl());
419 : }
0: branch 1 not taken
0: branch 2 not taken
420 0: else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
421 : // FIXME: Eventually CFGs won't have DeclStmts. Right now we
422 : // assume that each DeclStmt has a single Decl. This invariant
423 : // holds by contruction in the CFG.
424 0: VD = dyn_cast<VarDecl>(*DS->decl_begin());
425 : }
426 :
0: branch 0 not taken
0: branch 1 not taken
427 0: if (!VD)
428 0: return true;
429 :
430 : // What is the most recently referenced variable with this binding?
431 0: const VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
432 :
0: branch 0 not taken
0: branch 1 not taken
433 0: if (!MostRecent)
434 0: return true;
435 :
436 : // Create the diagnostic.
437 0: FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
438 :
0: branch 2 not taken
0: branch 3 not taken
439 0: if (Loc::IsLocType(VD->getType())) {
440 : std::string msg = "'" + std::string(VD->getNameAsString()) +
441 0: "' now aliases '" + MostRecent->getNameAsString() + "'";
442 :
443 0: PD.push_front(new PathDiagnosticEventPiece(L, msg));
444 : }
445 :
446 0: return true;
447 : }
448 : };
449 : }
450 :
451 : static void HandleNotableSymbol(const ExplodedNode* N,
452 : const Stmt* S,
453 : SymbolRef Sym, BugReporter& BR,
454 0: PathDiagnostic& PD) {
455 :
0: branch 1 not taken
0: branch 2 not taken
456 0: const ExplodedNode* Pred = N->pred_empty() ? 0 : *N->pred_begin();
0: branch 0 not taken
0: branch 1 not taken
457 0: const GRState* PrevSt = Pred ? Pred->getState() : 0;
458 :
0: branch 0 not taken
0: branch 1 not taken
459 0: if (!PrevSt)
460 0: return;
461 :
462 : // Look at the region bindings of the current state that map to the
463 : // specified symbol. Are any of them not in the previous state?
464 0: GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
465 0: NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
466 0: cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
467 : }
468 :
469 : namespace {
470 : class ScanNotableSymbols
0: branch 2 not taken
0: branch 3 not taken
0: branch 7 not taken
15: branch 8 taken
471 15: : public StoreManager::BindingsHandler {
472 :
473 : llvm::SmallSet<SymbolRef, 10> AlreadyProcessed;
474 : const ExplodedNode* N;
475 : const Stmt* S;
476 : GRBugReporter& BR;
477 : PathDiagnostic& PD;
478 :
479 : public:
480 : ScanNotableSymbols(const ExplodedNode* n, const Stmt* s,
481 15: GRBugReporter& br, PathDiagnostic& pd)
482 15: : N(n), S(s), BR(br), PD(pd) {}
483 :
484 : bool HandleBinding(StoreManager& SMgr, Store store,
485 17: const MemRegion* R, SVal V) {
486 :
487 17: SymbolRef ScanSym = V.getAsSymbol();
488 :
10: branch 0 taken
7: branch 1 taken
489 17: if (!ScanSym)
490 10: return true;
491 :
7: branch 1 taken
0: branch 2 not taken
492 7: if (!BR.isNotable(ScanSym))
493 7: return true;
494 :
0: branch 1 not taken
0: branch 2 not taken
495 0: if (AlreadyProcessed.count(ScanSym))
496 0: return true;
497 :
498 0: AlreadyProcessed.insert(ScanSym);
499 :
500 0: HandleNotableSymbol(N, S, ScanSym, BR, PD);
501 0: return true;
502 : }
503 : };
504 : } // end anonymous namespace
505 :
506 : //===----------------------------------------------------------------------===//
507 : // "Minimal" path diagnostic generation algorithm.
508 : //===----------------------------------------------------------------------===//
509 :
510 : static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM);
511 :
512 : static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
513 : PathDiagnosticBuilder &PDB,
514 1: const ExplodedNode *N) {
515 :
516 1: SourceManager& SMgr = PDB.getSourceManager();
517 : const ExplodedNode* NextNode = N->pred_empty()
0: branch 1 not taken
1: branch 2 taken
518 1: ? NULL : *(N->pred_begin());
23: branch 0 taken
1: branch 1 taken
519 25: while (NextNode) {
520 23: N = NextNode;
521 23: NextNode = GetPredecessorNode(N);
522 :
523 23: ProgramPoint P = N->getLocation();
524 :
4: branch 1 taken
19: branch 2 taken
525 23: if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
526 4: CFGBlock* Src = BE->getSrc();
527 4: CFGBlock* Dst = BE->getDst();
528 4: Stmt* T = Src->getTerminator();
529 :
2: branch 0 taken
2: branch 1 taken
530 4: if (!T)
531 2: continue;
532 :
533 2: FullSourceLoc Start(T->getLocStart(), SMgr);
534 :
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
0: branch 8 not taken
2: branch 9 taken
535 2: switch (T->getStmtClass()) {
536 : default:
537 0: break;
538 :
539 : case Stmt::GotoStmtClass:
540 : case Stmt::IndirectGotoStmtClass: {
541 0: const Stmt* S = GetNextStmt(N);
542 :
0: branch 0 not taken
0: branch 1 not taken
543 0: if (!S)
544 0: continue;
545 :
546 0: std::string sbuf;
547 0: llvm::raw_string_ostream os(sbuf);
548 0: const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
549 :
550 : os << "Control jumps to line "
551 0: << End.asLocation().getInstantiationLineNumber();
552 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
553 0: os.str()));
554 0: break;
555 : }
556 :
557 : case Stmt::SwitchStmtClass: {
558 : // Figure out what case arm we took.
559 0: std::string sbuf;
560 0: llvm::raw_string_ostream os(sbuf);
561 :
0: branch 1 not taken
0: branch 2 not taken
562 0: if (Stmt* S = Dst->getLabel()) {
563 0: PathDiagnosticLocation End(S, SMgr);
564 :
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
565 0: switch (S->getStmtClass()) {
566 : default:
567 : os << "No cases match in the switch statement. "
568 : "Control jumps to line "
569 0: << End.asLocation().getInstantiationLineNumber();
570 0: break;
571 : case Stmt::DefaultStmtClass:
572 : os << "Control jumps to the 'default' case at line "
573 0: << End.asLocation().getInstantiationLineNumber();
574 0: break;
575 :
576 : case Stmt::CaseStmtClass: {
577 0: os << "Control jumps to 'case ";
578 0: CaseStmt* Case = cast<CaseStmt>(S);
579 0: Expr* LHS = Case->getLHS()->IgnoreParenCasts();
580 :
581 : // Determine if it is an enum.
582 0: bool GetRawInt = true;
583 :
0: branch 1 not taken
0: branch 2 not taken
584 0: if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
585 : // FIXME: Maybe this should be an assertion. Are there cases
586 : // were it is not an EnumConstantDecl?
587 : EnumConstantDecl* D =
588 0: dyn_cast<EnumConstantDecl>(DR->getDecl());
589 :
0: branch 0 not taken
0: branch 1 not taken
590 0: if (D) {
591 0: GetRawInt = false;
592 0: os << D->getNameAsString();
593 : }
594 : }
595 :
0: branch 0 not taken
0: branch 1 not taken
596 0: if (GetRawInt)
597 0: os << LHS->EvaluateAsInt(PDB.getASTContext());
598 :
599 : os << ":' at line "
600 0: << End.asLocation().getInstantiationLineNumber();
601 : break;
602 : }
603 : }
604 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
605 0: os.str()));
606 : }
607 : else {
608 0: os << "'Default' branch taken. ";
609 0: const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
610 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
611 0: os.str()));
612 : }
613 :
614 0: break;
615 : }
616 :
617 : case Stmt::BreakStmtClass:
618 : case Stmt::ContinueStmtClass: {
619 0: std::string sbuf;
620 0: llvm::raw_string_ostream os(sbuf);
621 0: PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
622 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
623 0: os.str()));
624 0: break;
625 : }
626 :
627 : // Determine control-flow for ternary '?'.
628 : case Stmt::ConditionalOperatorClass: {
629 0: std::string sbuf;
630 0: llvm::raw_string_ostream os(sbuf);
631 0: os << "'?' condition is ";
632 :
0: branch 1 not taken
0: branch 2 not taken
633 0: if (*(Src->succ_begin()+1) == Dst)
634 0: os << "false";
635 : else
636 0: os << "true";
637 :
638 0: PathDiagnosticLocation End = PDB.ExecutionContinues(N);
639 :
0: branch 1 not taken
0: branch 2 not taken
640 0: if (const Stmt *S = End.asStmt())
641 0: End = PDB.getEnclosingStmtLocation(S);
642 :
643 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
644 0: os.str()));
645 0: break;
646 : }
647 :
648 : // Determine control-flow for short-circuited '&&' and '||'.
649 : case Stmt::BinaryOperatorClass: {
0: branch 1 not taken
0: branch 2 not taken
650 0: if (!PDB.supportsLogicalOpControlFlow())
651 0: break;
652 :
653 0: BinaryOperator *B = cast<BinaryOperator>(T);
654 0: std::string sbuf;
655 0: llvm::raw_string_ostream os(sbuf);
656 0: os << "Left side of '";
657 :
0: branch 1 not taken
0: branch 2 not taken
658 0: if (B->getOpcode() == BinaryOperator::LAnd) {
659 0: os << "&&" << "' is ";
660 :
0: branch 1 not taken
0: branch 2 not taken
661 0: if (*(Src->succ_begin()+1) == Dst) {
662 0: os << "false";
663 0: PathDiagnosticLocation End(B->getLHS(), SMgr);
664 0: PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
665 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
666 0: os.str()));
667 : }
668 : else {
669 0: os << "true";
670 0: PathDiagnosticLocation Start(B->getLHS(), SMgr);
671 0: PathDiagnosticLocation End = PDB.ExecutionContinues(N);
672 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
673 0: os.str()));
674 : }
675 : }
676 : else {
0: branch 1 not taken
0: branch 2 not taken
677 0: assert(B->getOpcode() == BinaryOperator::LOr);
678 0: os << "||" << "' is ";
679 :
0: branch 1 not taken
0: branch 2 not taken
680 0: if (*(Src->succ_begin()+1) == Dst) {
681 0: os << "false";
682 0: PathDiagnosticLocation Start(B->getLHS(), SMgr);
683 0: PathDiagnosticLocation End = PDB.ExecutionContinues(N);
684 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
685 0: os.str()));
686 : }
687 : else {
688 0: os << "true";
689 0: PathDiagnosticLocation End(B->getLHS(), SMgr);
690 0: PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
691 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
692 0: os.str()));
693 : }
694 : }
695 :
696 0: break;
697 : }
698 :
699 : case Stmt::DoStmtClass: {
0: branch 1 not taken
0: branch 2 not taken
700 0: if (*(Src->succ_begin()) == Dst) {
701 0: std::string sbuf;
702 0: llvm::raw_string_ostream os(sbuf);
703 :
704 0: os << "Loop condition is true. ";
705 0: PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
706 :
0: branch 1 not taken
0: branch 2 not taken
707 0: if (const Stmt *S = End.asStmt())
708 0: End = PDB.getEnclosingStmtLocation(S);
709 :
710 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
711 0: os.str()));
712 : }
713 : else {
714 0: PathDiagnosticLocation End = PDB.ExecutionContinues(N);
715 :
0: branch 1 not taken
0: branch 2 not taken
716 0: if (const Stmt *S = End.asStmt())
717 0: End = PDB.getEnclosingStmtLocation(S);
718 :
719 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
720 0: "Loop condition is false. Exiting loop"));
721 : }
722 :
723 0: break;
724 : }
725 :
726 : case Stmt::WhileStmtClass:
727 : case Stmt::ForStmtClass: {
0: branch 1 not taken
0: branch 2 not taken
728 0: if (*(Src->succ_begin()+1) == Dst) {
729 0: std::string sbuf;
730 0: llvm::raw_string_ostream os(sbuf);
731 :
732 0: os << "Loop condition is false. ";
733 0: PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
0: branch 1 not taken
0: branch 2 not taken
734 0: if (const Stmt *S = End.asStmt())
735 0: End = PDB.getEnclosingStmtLocation(S);
736 :
737 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
738 0: os.str()));
739 : }
740 : else {
741 0: PathDiagnosticLocation End = PDB.ExecutionContinues(N);
0: branch 1 not taken
0: branch 2 not taken
742 0: if (const Stmt *S = End.asStmt())
743 0: End = PDB.getEnclosingStmtLocation(S);
744 :
745 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
746 0: "Loop condition is true. Entering loop body"));
747 : }
748 :
749 0: break;
750 : }
751 :
752 : case Stmt::IfStmtClass: {
753 2: PathDiagnosticLocation End = PDB.ExecutionContinues(N);
754 :
2: branch 1 taken
0: branch 2 not taken
755 2: if (const Stmt *S = End.asStmt())
756 2: End = PDB.getEnclosingStmtLocation(S);
757 :
0: branch 1 not taken
2: branch 2 taken
758 2: if (*(Src->succ_begin()+1) == Dst)
759 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
760 0: "Taking false branch"));
761 : else
762 : PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
763 2: "Taking true branch"));
764 :
765 : break;
766 : }
767 : }
768 : }
769 :
21: branch 0 taken
0: branch 1 not taken
770 21: if (NextNode) {
42: branch 3 taken
21: branch 4 taken
771 84: for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
772 21: E = PDB.visitor_end(); I!=E; ++I) {
1: branch 2 taken
41: branch 3 taken
773 42: if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB))
774 1: PD.push_front(p);
775 : }
776 : }
777 :
15: branch 1 taken
6: branch 2 taken
778 21: if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
779 : // Scan the region bindings, and see if a "notable" symbol has a new
780 : // lval binding.
781 15: ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD);
782 15: PDB.getStateManager().iterBindings(N->getState(), SNS);
783 : }
784 : }
785 :
786 : // After constructing the full PathDiagnostic, do a pass over it to compact
787 : // PathDiagnosticPieces that occur within a macro.
788 1: CompactPathDiagnostic(PD, PDB.getSourceManager());
789 1: }
790 :
791 : //===----------------------------------------------------------------------===//
792 : // "Extensive" PathDiagnostic generation.
793 : //===----------------------------------------------------------------------===//
794 :
795 1531: static bool IsControlFlowExpr(const Stmt *S) {
796 1531: const Expr *E = dyn_cast<Expr>(S);
797 :
432: branch 0 taken
1099: branch 1 taken
798 1531: if (!E)
799 432: return false;
800 :
801 1099: E = E->IgnoreParenCasts();
802 :
14: branch 1 taken
1085: branch 2 taken
803 1099: if (isa<ConditionalOperator>(E))
804 14: return true;
805 :
127: branch 1 taken
958: branch 2 taken
806 1085: if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
6: branch 1 taken
121: branch 2 taken
807 127: if (B->isLogicalOp())
808 6: return true;
809 :
810 1079: return false;
811 : }
812 :
813 : namespace {
814 1476: class ContextLocation : public PathDiagnosticLocation {
815 : bool IsDead;
816 : public:
817 1476: ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
818 1476: : PathDiagnosticLocation(L), IsDead(isdead) {}
819 :
820 0: void markDead() { IsDead = true; }
821 1476: bool isDead() const { return IsDead; }
822 : };
823 :
824 : class EdgeBuilder {
825 : std::vector<ContextLocation> CLocs;
826 : typedef std::vector<ContextLocation>::iterator iterator;
827 : PathDiagnostic &PD;
828 : PathDiagnosticBuilder &PDB;
829 : PathDiagnosticLocation PrevLoc;
830 :
831 : bool IsConsumedExpr(const PathDiagnosticLocation &L);
832 :
833 : bool containsLocation(const PathDiagnosticLocation &Container,
834 : const PathDiagnosticLocation &Containee);
835 :
836 : PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
837 :
838 : PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
839 6810: bool firstCharOnly = false) {
3718: branch 1 taken
3092: branch 2 taken
840 6810: if (const Stmt *S = L.asStmt()) {
841 3718: const Stmt *Original = S;
842 216: while (1) {
843 : // Adjust the location for some expressions that are best referenced
844 : // by one of their subexpressions.
3718: branch 1 taken
6: branch 2 taken
26: branch 3 taken
0: branch 4 not taken
184: branch 5 taken
845 3934: switch (S->getStmtClass()) {
846 : default:
847 : break;
848 : case Stmt::ParenExprClass:
849 6: S = cast<ParenExpr>(S)->IgnoreParens();
850 6: firstCharOnly = true;
851 6: continue;
852 : case Stmt::ConditionalOperatorClass:
853 26: S = cast<ConditionalOperator>(S)->getCond();
854 26: firstCharOnly = true;
855 26: continue;
856 : case Stmt::ChooseExprClass:
857 0: S = cast<ChooseExpr>(S)->getCond();
858 0: firstCharOnly = true;
859 0: continue;
860 : case Stmt::BinaryOperatorClass:
861 184: S = cast<BinaryOperator>(S)->getLHS();
862 184: firstCharOnly = true;
863 184: continue;
864 : }
865 :
866 : break;
867 : }
868 :
200: branch 0 taken
3518: branch 1 taken
869 3718: if (S != Original)
870 200: L = PathDiagnosticLocation(S, L.getManager());
871 : }
872 :
1486: branch 0 taken
5324: branch 1 taken
873 6810: if (firstCharOnly)
874 1486: L = PathDiagnosticLocation(L.asLocation());
875 :
876 6810: return L;
877 : }
878 :
879 1476: void popLocation() {
1464: branch 2 taken
12: branch 3 taken
1442: branch 7 taken
22: branch 8 taken
1442: branch 9 taken
34: branch 10 taken
880 1476: if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
881 : // For contexts, we only one the first character as the range.
882 1442: rawAddEdge(cleanUpLocation(CLocs.back(), true));
883 : }
884 1476: CLocs.pop_back();
885 1476: }
886 :
887 : PathDiagnosticLocation IgnoreParens(const PathDiagnosticLocation &L);
888 :
889 : public:
890 579: EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
891 579: : PD(pd), PDB(pdb) {
892 :
893 : // If the PathDiagnostic already has pieces, add the enclosing statement
894 : // of the first piece as a context as well.
579: branch 1 taken
0: branch 2 not taken
895 579: if (!PD.empty()) {
896 579: PrevLoc = PD.begin()->getLocation();
897 :
397: branch 1 taken
182: branch 2 taken
898 579: if (const Stmt *S = PrevLoc.asStmt())
899 397: addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
900 : }
901 579: }
902 :
903 579: ~EdgeBuilder() {
591: branch 2 taken
579: branch 3 taken
904 579: while (!CLocs.empty()) popLocation();
905 :
906 : // Finally, add an initial edge from the start location of the first
907 : // statement (if it doesn't already exist).
908 : // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
579: branch 0 taken
0: branch 1 not taken
909 579: if (const CompoundStmt *CS =
910 579: PDB.getCodeDecl().getCompoundBody())
579: branch 1 taken
0: branch 2 not taken
911 579: if (!CS->body_empty()) {
912 579: SourceLocation Loc = (*CS->body_begin())->getLocStart();
913 579: rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager()));
914 : }
915 :
916 579: }
917 :
918 : void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
919 :
920 : void addEdge(const Stmt *S, bool alwaysAdd = false) {
921 : addEdge(PathDiagnosticLocation(S, PDB.getSourceManager()), alwaysAdd);
922 : }
923 :
924 : void rawAddEdge(PathDiagnosticLocation NewLoc);
925 :
926 : void addContext(const Stmt *S);
927 : void addExtendedContext(const Stmt *S);
928 : };
929 : } // end anonymous namespace
930 :
931 :
932 : PathDiagnosticLocation
933 663: EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
663: branch 1 taken
0: branch 2 not taken
934 663: if (const Stmt *S = L.asStmt()) {
0: branch 1 not taken
663: branch 2 taken
935 663: if (IsControlFlowExpr(S))
936 0: return L;
937 :
938 663: return PDB.getEnclosingStmtLocation(S);
939 : }
940 :
941 0: return L;
942 : }
943 :
944 : bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
945 927: const PathDiagnosticLocation &Containee) {
946 :
0: branch 1 not taken
927: branch 2 taken
947 927: if (Container == Containee)
948 0: return true;
949 :
0: branch 1 not taken
927: branch 2 taken
950 927: if (Container.asDecl())
951 0: return true;
952 :
927: branch 1 taken
0: branch 2 not taken
953 927: if (const Stmt *S = Containee.asStmt())
927: branch 1 taken
0: branch 2 not taken
954 927: if (const Stmt *ContainerS = Container.asStmt()) {
1957: branch 0 taken
885: branch 1 taken
955 3769: while (S) {
42: branch 0 taken
1915: branch 1 taken
956 1957: if (S == ContainerS)
957 42: return true;
958 1915: S = PDB.getParent(S);
959 : }
960 885: return false;
961 : }
962 :
963 : // Less accurate: compare using source ranges.
964 0: SourceRange ContainerR = Container.asRange();
965 0: SourceRange ContaineeR = Containee.asRange();
966 :
967 0: SourceManager &SM = PDB.getSourceManager();
968 0: SourceLocation ContainerRBeg = SM.getInstantiationLoc(ContainerR.getBegin());
969 0: SourceLocation ContainerREnd = SM.getInstantiationLoc(ContainerR.getEnd());
970 0: SourceLocation ContaineeRBeg = SM.getInstantiationLoc(ContaineeR.getBegin());
971 0: SourceLocation ContaineeREnd = SM.getInstantiationLoc(ContaineeR.getEnd());
972 :
973 0: unsigned ContainerBegLine = SM.getInstantiationLineNumber(ContainerRBeg);
974 0: unsigned ContainerEndLine = SM.getInstantiationLineNumber(ContainerREnd);
975 0: unsigned ContaineeBegLine = SM.getInstantiationLineNumber(ContaineeRBeg);
976 0: unsigned ContaineeEndLine = SM.getInstantiationLineNumber(ContaineeREnd);
977 :
0: branch 0 not taken
0: branch 1 not taken
978 0: assert(ContainerBegLine <= ContainerEndLine);
0: branch 0 not taken
0: branch 1 not taken
979 0: assert(ContaineeBegLine <= ContaineeEndLine);
980 :
981 : return (ContainerBegLine <= ContaineeBegLine &&
982 : ContainerEndLine >= ContaineeEndLine &&
983 : (ContainerBegLine != ContaineeBegLine ||
984 : SM.getInstantiationColumnNumber(ContainerRBeg) <=
985 : SM.getInstantiationColumnNumber(ContaineeRBeg)) &&
986 : (ContainerEndLine != ContaineeEndLine ||
987 : SM.getInstantiationColumnNumber(ContainerREnd) >=
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 8 not taken
0: branch 9 not taken
0: branch 10 not taken
0: branch 11 not taken
0: branch 14 not taken
0: branch 15 not taken
988 0: SM.getInstantiationColumnNumber(ContainerREnd)));
989 : }
990 :
991 : PathDiagnosticLocation
992 0: EdgeBuilder::IgnoreParens(const PathDiagnosticLocation &L) {
0: branch 2 not taken
0: branch 3 not taken
993 0: if (const Expr* E = dyn_cast_or_null<Expr>(L.asStmt()))
994 : return PathDiagnosticLocation(E->IgnoreParenCasts(),
995 0: PDB.getSourceManager());
996 0: return L;
997 : }
998 :
999 2684: void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
0: branch 1 not taken
2684: branch 2 taken
1000 2684: if (!PrevLoc.isValid()) {
1001 0: PrevLoc = NewLoc;
1002 0: return;
1003 : }
1004 :
1005 2684: const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
1006 2684: const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
1007 :
1197: branch 3 taken
1487: branch 4 taken
1008 2684: if (NewLocClean.asLocation() == PrevLocClean.asLocation())
1009 1197: return;
1010 :
1011 : // FIXME: Ignore intra-macro edges for now.
8: branch 5 taken
1479: branch 6 taken
1012 1487: if (NewLocClean.asLocation().getInstantiationLoc() ==
1013 : PrevLocClean.asLocation().getInstantiationLoc())
1014 8: return;
1015 :
1016 1479: PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1017 1479: PrevLoc = NewLoc;
1018 : }
1019 :
1020 663: void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
1021 :
0: branch 0 not taken
663: branch 1 taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
663: branch 7 taken
1022 663: if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1023 0: return;
1024 :
1025 663: const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1026 :
511: branch 1 taken
547: branch 2 taken
1027 1721: while (!CLocs.empty()) {
1028 511: ContextLocation &TopContextLoc = CLocs.back();
1029 :
1030 : // Is the top location context the same as the one for the new location?
104: branch 1 taken
407: branch 2 taken
1031 511: if (TopContextLoc == CLoc) {
104: branch 0 taken
0: branch 1 not taken
1032 104: if (alwaysAdd) {
0: branch 1 not taken
104: branch 2 taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
104: branch 8 taken
1033 104: if (IsConsumedExpr(TopContextLoc) &&
1034 : !IsControlFlowExpr(TopContextLoc.asStmt()))
1035 0: TopContextLoc.markDead();
1036 :
1037 104: rawAddEdge(NewLoc);
1038 : }
1039 :
1040 104: return;
1041 : }
1042 :
12: branch 1 taken
395: branch 2 taken
1043 407: if (containsLocation(TopContextLoc, CLoc)) {
12: branch 0 taken
0: branch 1 not taken
1044 12: if (alwaysAdd) {
1045 12: rawAddEdge(NewLoc);
1046 :
12: branch 1 taken
0: branch 2 not taken
12: branch 5 taken
0: branch 6 not taken
12: branch 7 taken
0: branch 8 not taken
1047 12: if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) {
1048 12: CLocs.push_back(ContextLocation(CLoc, true));
1049 12: return;
1050 : }
1051 : }
1052 :
1053 0: CLocs.push_back(CLoc);
1054 0: return;
1055 : }
1056 :
1057 : // Context does not contain the location. Flush it.
1058 395: popLocation();
1059 : }
1060 :
1061 : // If we reach here, there is no enclosing context. Just add the edge.
1062 547: rawAddEdge(NewLoc);
1063 : }
1064 :
1065 116: bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
46: branch 2 taken
70: branch 3 taken
1066 116: if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
24: branch 2 taken
22: branch 3 taken
12: branch 5 taken
12: branch 6 taken
1067 46: return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1068 :
1069 70: return false;
1070 : }
1071 :
1072 1884: void EdgeBuilder::addExtendedContext(const Stmt *S) {
0: branch 0 not taken
1884: branch 1 taken
1073 1884: if (!S)
1074 0: return;
1075 :
1076 1884: const Stmt *Parent = PDB.getParent(S);
1906: branch 0 taken
1697: branch 1 taken
1077 5487: while (Parent) {
187: branch 1 taken
1719: branch 2 taken
1078 1906: if (isa<CompoundStmt>(Parent))
1079 1719: Parent = PDB.getParent(Parent);
1080 : else
1081 187: break;
1082 : }
1083 :
187: branch 0 taken
1697: branch 1 taken
1084 1884: if (Parent) {
16: branch 1 taken
171: branch 2 taken
1085 187: switch (Parent->getStmtClass()) {
1086 : case Stmt::DoStmtClass:
1087 : case Stmt::ObjCAtSynchronizedStmtClass:
1088 16: addContext(Parent);
1089 : default:
1090 : break;
1091 : }
1092 : }
1093 :
1094 1884: addContext(S);
1095 : }
1096 :
1097 2135: void EdgeBuilder::addContext(const Stmt *S) {
0: branch 0 not taken
2135: branch 1 taken
1098 2135: if (!S)
1099 0: return;
1100 :
1101 2135: PathDiagnosticLocation L(S, PDB.getSourceManager());
1102 :
1191: branch 1 taken
1434: branch 2 taken
1103 4760: while (!CLocs.empty()) {
1104 1191: const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1105 :
1106 : // Is the top location context the same as the one for the new location?
671: branch 1 taken
520: branch 2 taken
1107 1191: if (TopContextLoc == L)
1108 671: return;
1109 :
30: branch 1 taken
490: branch 2 taken
1110 520: if (containsLocation(TopContextLoc, L)) {
1111 30: CLocs.push_back(L);
1112 30: return;
1113 : }
1114 :
1115 : // Context does not contain the location. Flush it.
1116 490: popLocation();
1117 : }
1118 :
1119 1434: CLocs.push_back(L);
1120 : }
1121 :
1122 : static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1123 : PathDiagnosticBuilder &PDB,
1124 579: const ExplodedNode *N) {
1125 :
1126 :
1127 579: EdgeBuilder EB(PD, PDB);
1128 :
1129 : const ExplodedNode* NextNode = N->pred_empty()
0: branch 1 not taken
579: branch 2 taken
1130 579: ? NULL : *(N->pred_begin());
7824: branch 0 taken
579: branch 1 taken
1131 8982: while (NextNode) {
1132 7824: N = NextNode;
1133 7824: NextNode = GetPredecessorNode(N);
1134 7824: ProgramPoint P = N->getLocation();
1135 :
1136 : do {
1137 : // Block edges.
958: branch 1 taken
6866: branch 2 taken
1138 7824: if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
1139 958: const CFGBlock &Blk = *BE->getSrc();
1140 958: const Stmt *Term = Blk.getTerminator();
1141 :
1142 : // Are we jumping to the head of a loop? Add a special diagnostic.
0: branch 2 not taken
958: branch 3 taken
1143 958: if (const Stmt *Loop = BE->getDst()->getLoopTarget()) {
1144 0: PathDiagnosticLocation L(Loop, PDB.getSourceManager());
1145 0: const CompoundStmt *CS = NULL;
1146 :
0: branch 0 not taken
0: branch 1 not taken
1147 0: if (!Term) {
0: branch 1 not taken
0: branch 2 not taken
1148 0: if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1149 0: CS = dyn_cast<CompoundStmt>(FS->getBody());
0: branch 1 not taken
0: branch 2 not taken
1150 0: else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1151 0: CS = dyn_cast<CompoundStmt>(WS->getBody());
1152 : }
1153 :
1154 : PathDiagnosticEventPiece *p =
1155 : new PathDiagnosticEventPiece(L,
1156 0: "Looping back to the head of the loop");
1157 :
1158 0: EB.addEdge(p->getLocation(), true);
1159 0: PD.push_front(p);
1160 :
0: branch 0 not taken
0: branch 1 not taken
1161 0: if (CS) {
1162 : PathDiagnosticLocation BL(CS->getRBracLoc(),
1163 0: PDB.getSourceManager());
1164 0: BL = PathDiagnosticLocation(BL.asLocation());
1165 0: EB.addEdge(BL);
1166 : }
1167 : }
1168 :
227: branch 0 taken
731: branch 1 taken
1169 958: if (Term)
1170 227: EB.addContext(Term);
1171 :
1172 958: break;
1173 : }
1174 :
832: branch 1 taken
6034: branch 2 taken
1175 6866: if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
832: branch 1 taken
0: branch 2 not taken
1176 832: if (const Stmt* S = BE->getFirstStmt()) {
8: branch 1 taken
824: branch 2 taken
1177 832: if (IsControlFlowExpr(S)) {
1178 : // Add the proper context for '&&', '||', and '?'.
1179 8: EB.addContext(S);
1180 : }
1181 : else
1182 824: EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1183 : }
1184 :
1185 832: break;
1186 : }
1187 : } while (0);
1188 :
579: branch 0 taken
7245: branch 1 taken
1189 7824: if (!NextNode)
1190 579: continue;
1191 :
9133: branch 3 taken
7245: branch 4 taken
1192 23623: for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
1193 7245: E = PDB.visitor_end(); I!=E; ++I) {
663: branch 2 taken
8470: branch 3 taken
1194 9133: if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) {
1195 663: const PathDiagnosticLocation &Loc = p->getLocation();
1196 663: EB.addEdge(Loc, true);
1197 663: PD.push_front(p);
663: branch 1 taken
0: branch 2 not taken
1198 663: if (const Stmt *S = Loc.asStmt())
1199 663: EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1200 : }
1201 : }
1202 579: }
1203 579: }
1204 :
1205 : //===----------------------------------------------------------------------===//
1206 : // Methods for BugType and subclasses.
1207 : //===----------------------------------------------------------------------===//
1208 21849: BugType::~BugType() {
1209 : // Free up the equivalence class objects. Observe that we get a pointer to
1210 : // the object first before incrementing the iterator, as destroying the
1211 : // node before doing so means we will read from freed memory.
158: branch 3 taken
158: branch 4 taken
0: branch 8 not taken
0: branch 9 not taken
572: branch 13 taken
21691: branch 14 taken
1212 44428: for (iterator I = begin(), E = end(); I !=E; ) {
1213 730: BugReportEquivClass *EQ = &*I;
1214 730: ++I;
158: branch 0 taken
0: branch 1 not taken
158: branch 4 taken
158: branch 5 taken
572: branch 8 taken
0: branch 9 not taken
1215 730: delete EQ;
1216 : }
158: branch 3 taken
0: branch 4 not taken
0: branch 9 not taken
0: branch 10 not taken
0: branch 15 not taken
21691: branch 16 taken
1217 21849: }
1218 17565: void BugType::FlushReports(BugReporter &BR) {}
1219 :
1220 : //===----------------------------------------------------------------------===//
1221 : // Methods for BugReport and subclasses.
1222 : //===----------------------------------------------------------------------===//
11: branch 3 taken
0: branch 4 not taken
0: branch 9 not taken
0: branch 10 not taken
0: branch 15 not taken
723: branch 16 taken
1223 734: BugReport::~BugReport() {}
95: branch 2 taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
0: branch 12 not taken
628: branch 13 taken
1224 723: RangedBugReport::~RangedBugReport() {}
1225 :
1226 420: const Stmt* BugReport::getStmt() const {
1227 420: ProgramPoint ProgP = EndNode->getLocation();
1228 420: const Stmt *S = NULL;
1229 :
5: branch 1 taken
415: branch 2 taken
1230 420: if (BlockEntrance* BE = dyn_cast<BlockEntrance>(&ProgP)) {
1231 5: CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
5: branch 1 taken
0: branch 2 not taken
1232 5: if (BE->getBlock() == &Exit)
1233 5: S = GetPreviousStmt(EndNode);
1234 : }
415: branch 0 taken
5: branch 1 taken
1235 420: if (!S)
1236 415: S = GetStmt(ProgP);
1237 :
1238 420: return S;
1239 : }
1240 :
1241 : PathDiagnosticPiece*
1242 : BugReport::getEndPath(BugReporterContext& BRC,
1243 398: const ExplodedNode* EndPathNode) {
1244 :
1245 398: const Stmt* S = getStmt();
1246 :
0: branch 0 not taken
398: branch 1 taken
1247 398: if (!S)
1248 0: return NULL;
1249 :
1250 : const SourceRange *Beg, *End;
1251 398: getRanges(Beg, End);
1252 398: PathDiagnosticLocation L(S, BRC.getSourceManager());
1253 :
1254 : // Only add the statement itself as a range if we didn't specify any
1255 : // special ranges for this report.
1256 : PathDiagnosticPiece* P = new PathDiagnosticEventPiece(L, getDescription(),
1257 398: Beg == End);
1258 :
312: branch 0 taken
398: branch 1 taken
1259 710: for (; Beg != End; ++Beg)
1260 312: P->addRange(*Beg);
1261 :
1262 398: return P;
1263 : }
1264 :
1265 22: void BugReport::getRanges(const SourceRange*& beg, const SourceRange*& end) {
18: branch 2 taken
4: branch 3 taken
1266 22: if (const Expr* E = dyn_cast_or_null<Expr>(getStmt())) {
1267 18: R = E->getSourceRange();
0: branch 1 not taken
18: branch 2 taken
1268 18: assert(R.isValid());
1269 18: beg = &R;
1270 18: end = beg+1;
1271 : }
1272 : else
1273 4: beg = end = 0;
1274 22: }
1275 :
1276 1168: SourceLocation BugReport::getLocation() const {
1168: branch 0 taken
0: branch 1 not taken
1277 1168: if (EndNode)
1168: branch 1 taken
0: branch 2 not taken
1278 1168: if (const Stmt* S = GetCurrentOrPreviousStmt(EndNode)) {
1279 : // For member expressions, return the location of the '.' or '->'.
15: branch 1 taken
1153: branch 2 taken
1280 1168: if (const MemberExpr *ME = dyn_cast<MemberExpr>(S))
1281 15: return ME->getMemberLoc();
1282 : // For binary operators, return the location of the operator.
88: branch 1 taken
1065: branch 2 taken
1283 1153: if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S))
1284 88: return B->getOperatorLoc();
1285 :
1286 1065: return S->getLocStart();
1287 : }
1288 :
1289 0: return FullSourceLoc();
1290 : }
1291 :
1292 : PathDiagnosticPiece* BugReport::VisitNode(const ExplodedNode* N,
1293 : const ExplodedNode* PrevN,
1294 2886: BugReporterContext &BRC) {
1295 2886: return NULL;
1296 : }
1297 :
1298 : //===----------------------------------------------------------------------===//
1299 : // Methods for BugReporter and subclasses.
1300 : //===----------------------------------------------------------------------===//
1301 :
1302 730: BugReportEquivClass::~BugReportEquivClass() {
734: branch 3 taken
0: branch 4 not taken
734: branch 8 taken
730: branch 9 taken
0: branch 13 not taken
0: branch 14 not taken
0: branch 18 not taken
0: branch 19 not taken
1303 730: for (iterator I=begin(), E=end(); I!=E; ++I) delete *I;
1304 730: }
1305 :
0: branch 2 not taken
0: branch 3 not taken
0: branch 7 not taken
2138: branch 8 taken
0: branch 12 not taken
0: branch 13 not taken
1306 2138: GRBugReporter::~GRBugReporter() { }
188: branch 0 taken
188: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
188: branch 7 taken
1307 188: BugReporterData::~BugReporterData() {}
1308 :
1309 580: ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
1310 :
1311 : GRStateManager&
1312 434: GRBugReporter::getStateManager() { return Eng.getStateManager(); }
1313 :
0: branch 2 not taken
0: branch 3 not taken
0: branch 7 not taken
272: branch 8 taken
0: branch 12 not taken
2138: branch 13 taken
1314 2410: BugReporter::~BugReporter() { FlushReports(); }
1315 :
1316 6686: void BugReporter::FlushReports() {
4448: branch 1 taken
2238: branch 2 taken
1317 6686: if (BugTypes.isEmpty())
1318 4448: return;
1319 :
1320 : // First flush the warnings for each BugType. This may end up creating new
1321 : // warnings and new BugTypes. Because ImmutableSet is a functional data
1322 : // structure, we do not need to worry about the iterators being invalidated.
21841: branch 4 taken
2238: branch 5 taken
1323 24079: for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
1324 24079: const_cast<BugType*>(*I)->FlushReports(*this);
1325 :
1326 : // Iterate through BugTypes a second time. BugTypes may have been updated
1327 : // with new BugType objects and new warnings.
21849: branch 4 taken
2238: branch 5 taken
1328 24087: for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) {
1329 21849: BugType *BT = const_cast<BugType*>(*I);
1330 :
1331 : typedef llvm::FoldingSet<BugReportEquivClass> SetTy;
1332 21849: SetTy& EQClasses = BT->EQClasses;
1333 :
730: branch 4 taken
21849: branch 5 taken
1334 22579: for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){
1335 730: BugReportEquivClass& EQ = *EI;
1336 730: FlushReport(EQ);
1337 : }
1338 :
1339 : // Delete the BugType object.
21849: branch 0 taken
0: branch 1 not taken
1340 21849: delete BT;
1341 2238: }
1342 :
1343 : // Remove all references to the BugType objects.
1344 2238: BugTypes = F.GetEmptySet();
1345 : }
1346 :
1347 : //===----------------------------------------------------------------------===//
1348 : // PathDiagnostics generation.
1349 : //===----------------------------------------------------------------------===//
1350 :
1351 : static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1352 : std::pair<ExplodedNode*, unsigned> >
1353 : MakeReportGraph(const ExplodedGraph* G,
1354 : const ExplodedNode** NStart,
1355 580: const ExplodedNode** NEnd) {
1356 :
1357 : // Create the trimmed graph. It will contain the shortest paths from the
1358 : // error nodes to the root. In the new graph we should only have one
1359 : // error node unless there are two or more error nodes with the same minimum
1360 : // path length.
1361 : ExplodedGraph* GTrim;
1362 : InterExplodedGraphMap* NMap;
1363 :
1364 580: llvm::DenseMap<const void*, const void*> InverseMap;
1365 580: llvm::tie(GTrim, NMap) = G->Trim(NStart, NEnd, &InverseMap);
1366 :
1367 : // Create owning pointers for GTrim and NMap just to ensure that they are
1368 : // released when this function exists.
1369 580: llvm::OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim);
1370 580: llvm::OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap);
1371 :
1372 : // Find the (first) error node in the trimmed graph. We just need to consult
1373 : // the node map (NMap) which maps from nodes in the original graph to nodes
1374 : // in the new graph.
1375 :
1376 580: std::queue<const ExplodedNode*> WS;
1377 : typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy;
1378 580: IndexMapTy IndexMap;
1379 :
584: branch 0 taken
580: branch 1 taken
1380 1164: for (const ExplodedNode** I = NStart; I != NEnd; ++I)
584: branch 1 taken
0: branch 2 not taken
1381 584: if (const ExplodedNode *N = NMap->getMappedNode(*I)) {
1382 584: unsigned NodeIndex = (I - NStart) / sizeof(*I);
1383 584: WS.push(N);
1384 584: IndexMap[*I] = NodeIndex;
1385 : }
1386 :
580: branch 1 taken
0: branch 2 not taken
1387 580: assert(!WS.empty() && "No error node found in the trimmed graph.");
1388 :
1389 : // Create a new (third!) graph with a single path. This is the graph
1390 : // that will be returned to the caller.
1391 580: ExplodedGraph *GNew = new ExplodedGraph(GTrim->getContext());
1392 :
1393 : // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS
1394 : // to the root node, and then construct a new graph that contains only
1395 : // a single path.
1396 580: llvm::DenseMap<const void*,unsigned> Visited;
1397 :
1398 580: unsigned cnt = 0;
1399 580: const ExplodedNode* Root = 0;
1400 :
8793: branch 1 taken
0: branch 2 not taken
1401 9373: while (!WS.empty()) {
1402 8793: const ExplodedNode* Node = WS.front();
1403 8793: WS.pop();
1404 :
32: branch 4 taken
8761: branch 5 taken
1405 8793: if (Visited.find(Node) != Visited.end())
1406 32: continue;
1407 :
1408 8761: Visited[Node] = cnt++;
1409 :
580: branch 1 taken
8181: branch 2 taken
1410 8761: if (Node->pred_empty()) {
1411 580: Root = Node;
1412 580: break;
1413 : }
1414 :
8211: branch 1 taken
8181: branch 2 taken
1415 24573: for (ExplodedNode::const_pred_iterator I=Node->pred_begin(),
1416 8181: E=Node->pred_end(); I!=E; ++I)
1417 8211: WS.push(*I);
1418 : }
1419 :
0: branch 0 not taken
580: branch 1 taken
1420 580: assert(Root);
1421 :
1422 : // Now walk from the root down the BFS path, always taking the successor
1423 : // with the lowest number.
1424 580: ExplodedNode *Last = 0, *First = 0;
1425 580: NodeBackMap *BM = new NodeBackMap();
1426 580: unsigned NodeIndex = 0;
1427 :
1428 8427: for ( const ExplodedNode *N = Root ;;) {
1429 : // Lookup the number associated with the current node.
1430 8427: llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
0: branch 3 not taken
8427: branch 4 taken
1431 8427: assert(I != Visited.end());
1432 :
1433 : // Create the equivalent node in the new graph with the same state
1434 : // and location.
1435 8427: ExplodedNode* NewN = GNew->getNode(N->getLocation(), N->getState());
1436 :
1437 : // Store the mapping to the original node.
1438 8427: llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
8427: branch 3 taken
0: branch 4 not taken
1439 8427: assert(IMitr != InverseMap.end() && "No mapping to original node.");
1440 8427: (*BM)[NewN] = (const ExplodedNode*) IMitr->second;
1441 :
1442 : // Link up the new node with the previous node.
7847: branch 0 taken
580: branch 1 taken
1443 8427: if (Last)
1444 7847: NewN->addPredecessor(Last, *GNew);
1445 :
1446 8427: Last = NewN;
1447 :
1448 : // Are we at the final node?
1449 : IndexMapTy::iterator IMI =
1450 8427: IndexMap.find((const ExplodedNode*)(IMitr->second));
580: branch 3 taken
7847: branch 4 taken
1451 8427: if (IMI != IndexMap.end()) {
1452 580: First = NewN;
1453 580: NodeIndex = IMI->second;
1454 : break;
1455 : }
1456 :
1457 : // Find the next successor node. We choose the node that is marked
1458 : // with the lowest DFS number.
1459 7847: ExplodedNode::const_succ_iterator SI = N->succ_begin();
1460 7847: ExplodedNode::const_succ_iterator SE = N->succ_end();
1461 7847: N = 0;
1462 :
7879: branch 0 taken
7847: branch 1 taken
1463 15726: for (unsigned MinVal = 0; SI != SE; ++SI) {
1464 :
1465 7879: I = Visited.find(*SI);
1466 :
2: branch 3 taken
7877: branch 4 taken
1467 7879: if (I == Visited.end())
1468 2: continue;
1469 :
30: branch 0 taken
7847: branch 1 taken
0: branch 3 not taken
30: branch 4 taken
7847: branch 5 taken
30: branch 6 taken
1470 7877: if (!N || I->second < MinVal) {
1471 7847: N = *SI;
1472 7847: MinVal = I->second;
1473 : }
1474 : }
1475 :
0: branch 0 not taken
7847: branch 1 taken
1476 7847: assert(N);
1477 : }
1478 :
0: branch 0 not taken
580: branch 1 taken
1479 580: assert(First);
1480 :
1481 : return std::make_pair(std::make_pair(GNew, BM),
1482 580: std::make_pair(First, NodeIndex));
1483 : }
1484 :
1485 : /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
1486 : /// and collapses PathDiagosticPieces that are expanded by macros.
1487 1: static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM) {
1488 : typedef std::vector<std::pair<PathDiagnosticMacroPiece*, SourceLocation> >
1489 : MacroStackTy;
1490 :
1491 : typedef std::vector<PathDiagnosticPiece*>
1492 : PiecesTy;
1493 :
1494 1: MacroStackTy MacroStack;
1495 1: PiecesTy Pieces;
1496 :
4: branch 4 taken
1: branch 5 taken
1497 5: for (PathDiagnostic::iterator I = PD.begin(), E = PD.end(); I!=E; ++I) {
1498 : // Get the location of the PathDiagnosticPiece.
1499 4: const FullSourceLoc Loc = I->getLocation().asLocation();
1500 :
1501 : // Determine the instantiation location, which is the location we group
1502 : // related PathDiagnosticPieces.
1503 : SourceLocation InstantiationLoc = Loc.isMacroID() ?
1504 : SM.getInstantiationLoc(Loc) :
0: branch 1 not taken
4: branch 2 taken
1505 4: SourceLocation();
1506 :
4: branch 1 taken
0: branch 2 not taken
1507 4: if (Loc.isFileID()) {
1508 4: MacroStack.clear();
1509 4: Pieces.push_back(&*I);
1510 4: continue;
1511 : }
1512 :
0: branch 1 not taken
0: branch 2 not taken
1513 0: assert(Loc.isMacroID());
1514 :
1515 : // Is the PathDiagnosticPiece within the same macro group?
0: branch 1 not taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
0: branch 8 not taken
1516 0: if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
1517 0: MacroStack.back().first->push_back(&*I);
1518 0: continue;
1519 : }
1520 :
1521 : // We aren't in the same group. Are we descending into a new macro
1522 : // or are part of an old one?
1523 0: PathDiagnosticMacroPiece *MacroGroup = 0;
1524 :
1525 : SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
1526 : SM.getInstantiationLoc(Loc) :
0: branch 1 not taken
0: branch 2 not taken
1527 0: SourceLocation();
1528 :
1529 : // Walk the entire macro stack.
0: branch 1 not taken
0: branch 2 not taken
1530 0: while (!MacroStack.empty()) {
0: branch 2 not taken
0: branch 3 not taken
1531 0: if (InstantiationLoc == MacroStack.back().second) {
1532 0: MacroGroup = MacroStack.back().first;
1533 0: break;
1534 : }
1535 :
0: branch 2 not taken
0: branch 3 not taken
1536 0: if (ParentInstantiationLoc == MacroStack.back().second) {
1537 0: MacroGroup = MacroStack.back().first;
1538 0: break;
1539 : }
1540 :
1541 0: MacroStack.pop_back();
1542 : }
1543 :
0: branch 0 not taken
0: branch 1 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
1544 0: if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
1545 : // Create a new macro group and add it to the stack.
1546 0: PathDiagnosticMacroPiece *NewGroup = new PathDiagnosticMacroPiece(Loc);
1547 :
0: branch 0 not taken
0: branch 1 not taken
1548 0: if (MacroGroup)
1549 0: MacroGroup->push_back(NewGroup);
1550 : else {
0: branch 1 not taken
0: branch 2 not taken
1551 0: assert(InstantiationLoc.isFileID());
1552 0: Pieces.push_back(NewGroup);
1553 : }
1554 :
1555 0: MacroGroup = NewGroup;
1556 0: MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
1557 : }
1558 :
1559 : // Finally, add the PathDiagnosticPiece to the group.
1560 0: MacroGroup->push_back(&*I);
1561 : }
1562 :
1563 : // Now take the pieces and construct a new PathDiagnostic.
1564 1: PD.resetPath(false);
1565 :
4: branch 4 taken
1: branch 5 taken
1566 5: for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) {
0: branch 2 not taken
4: branch 3 taken
1567 4: if (PathDiagnosticMacroPiece *MP=dyn_cast<PathDiagnosticMacroPiece>(*I))
0: branch 1 not taken
0: branch 2 not taken
1568 0: if (!MP->containsEvent()) {
0: branch 0 not taken
0: branch 1 not taken
1569 0: delete MP;
1570 0: continue;
1571 : }
1572 :
1573 4: PD.push_back(*I);
1574 1: }
1575 1: }
1576 :
1577 : void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
1578 590: BugReportEquivClass& EQ) {
1579 :
1580 590: std::vector<const ExplodedNode*> Nodes;
1581 :
594: branch 4 taken
590: branch 5 taken
1582 1184: for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
1583 594: const ExplodedNode* N = I->getEndNode();
584: branch 0 taken
10: branch 1 taken
1584 594: if (N) Nodes.push_back(N);
1585 : }
1586 :
10: branch 1 taken
580: branch 2 taken
1587 590: if (Nodes.empty())
1588 10: return;
1589 :
1590 : // Construct a new graph that contains only a single path from the error
1591 : // node to a root.
1592 : const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1593 : std::pair<ExplodedNode*, unsigned> >&
1594 580: GPair = MakeReportGraph(&getGraph(), &Nodes[0], &Nodes[0] + Nodes.size());
1595 :
1596 : // Find the BugReport with the original location.
1597 580: BugReport *R = 0;
1598 580: unsigned i = 0;
580: branch 4 taken
0: branch 5 not taken
1599 580: for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I, ++i)
580: branch 0 taken
0: branch 1 not taken
1600 580: if (i == GPair.second.second) { R = *I; break; }
1601 :
0: branch 0 not taken
580: branch 1 taken
1602 580: assert(R && "No original report found for sliced graph.");
1603 :
1604 580: llvm::OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first);
1605 580: llvm::OwningPtr<NodeBackMap> BackMap(GPair.first.second);
1606 580: const ExplodedNode *N = GPair.second.first;
1607 :
1608 : // Start building the path diagnostic...
1609 580: PathDiagnosticBuilder PDB(*this, R, BackMap.get(), getPathDiagnosticClient());
1610 :
0: branch 1 not taken
580: branch 2 taken
1611 580: if (PathDiagnosticPiece* Piece = R->getEndPath(PDB, N))
1612 580: PD.push_back(Piece);
1613 : else
1614 : return;
1615 :
1616 580: R->registerInitialVisitors(PDB, N);
1617 :
579: branch 1 taken
1: branch 2 taken
0: branch 3 not taken
1618 580: switch (PDB.getGenerationScheme()) {
1619 : case PathDiagnosticClient::Extensive:
1620 579: GenerateExtensivePathDiagnostic(PD, PDB, N);
1621 579: break;
1622 : case PathDiagnosticClient::Minimal:
1623 1: GenerateMinimalPathDiagnostic(PD, PDB, N);
1624 : break;
580: branch 1 taken
0: branch 2 not taken
580: branch 4 taken
0: branch 5 not taken
580: branch 7 taken
0: branch 8 not taken
580: branch 10 taken
10: branch 11 taken
1625 580: }
1626 : }
1627 :
1628 22114: void BugReporter::Register(BugType *BT) {
1629 22114: BugTypes = F.Add(BugTypes, BT);
1630 22114: }
1631 :
1632 734: void BugReporter::EmitReport(BugReport* R) {
1633 : // Compute the bug report's hash to determine its equivalence class.
1634 734: llvm::FoldingSetNodeID ID;
1635 734: R->Profile(ID);
1636 :
1637 : // Lookup the equivance class. If there isn't one, create it.
1638 734: BugType& BT = R->getBugType();
1639 734: Register(&BT);
1640 : void *InsertPos;
1641 734: BugReportEquivClass* EQ = BT.EQClasses.FindNodeOrInsertPos(ID, InsertPos);
1642 :
730: branch 0 taken
4: branch 1 taken
1643 734: if (!EQ) {
1644 730: EQ = new BugReportEquivClass(R);
1645 730: BT.EQClasses.InsertNode(EQ, InsertPos);
1646 : }
1647 : else
1648 4: EQ->AddReport(R);
1649 734: }
1650 :
1651 :
1652 : //===----------------------------------------------------------------------===//
1653 : // Emitting reports in equivalence classes.
1654 : //===----------------------------------------------------------------------===//
1655 :
1656 : namespace {
1657 2869: struct FRIEC_WLItem {
1658 : const ExplodedNode *N;
1659 : ExplodedNode::const_succ_iterator I, E;
1660 :
1661 1419: FRIEC_WLItem(const ExplodedNode *n)
1662 1419: : N(n), I(N->succ_begin()), E(N->succ_end()) {}
1663 : };
1664 : }
1665 :
1666 730: static BugReport *FindReportInEquivalenceClass(BugReportEquivClass& EQ) {
1667 730: BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
0: branch 1 not taken
730: branch 2 taken
1668 730: assert(I != E);
1669 730: BugReport *R = *I;
1670 730: BugType& BT = R->getBugType();
1671 :
544: branch 1 taken
186: branch 2 taken
1672 730: if (!BT.isSuppressOnSink())
1673 544: return R;
1674 :
1675 : // For bug reports that should be suppressed when all paths are post-dominated
1676 : // by a sink node, iterate through the reports in the equivalence class
1677 : // until we find one that isn't post-dominated (if one exists). We use a
1678 : // DFS traversal of the ExplodedGraph to find a non-sink node. We could write
1679 : // this as a recursive function, but we don't want to risk blowing out the
1680 : // stack for very long paths.
4: branch 1 taken
59: branch 2 taken
4: branch 4 taken
59: branch 5 taken
186: branch 8 taken
4: branch 9 taken
1681 253: for (; I != E; ++I) {
1682 186: R = *I;
1683 186: const ExplodedNode *N = R->getEndNode();
1684 :
186: branch 0 taken
0: branch 1 not taken
1685 186: if (!N)
1686 0: continue;
1687 :
0: branch 1 not taken
186: branch 2 taken
1688 186: if (N->isSink()) {
1689 : assert(false &&
1690 0: "BugType::isSuppressSink() should not be 'true' for sink end nodes");
1691 : return R;
1692 : }
1693 :
123: branch 1 taken
63: branch 2 taken
1694 186: if (N->succ_empty())
1695 123: return R;
1696 :
1697 : // At this point we know that 'N' is not a sink and it has at least one
1698 : // successor. Use a DFS worklist to find a non-sink end-of-path node.
1699 : typedef FRIEC_WLItem WLItem;
1700 : typedef llvm::SmallVector<WLItem, 10> DFSWorkList;
1701 63: llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
1702 :
1703 63: DFSWorkList WL;
1704 63: WL.push_back(N);
1705 63: Visited[N] = 1;
1706 :
1463: branch 1 taken
4: branch 2 taken
1707 1530: while (!WL.empty()) {
1708 1463: WLItem &WI = WL.back();
0: branch 1 not taken
1463: branch 2 taken
1709 1463: assert(!WI.N->succ_empty());
1710 :
1467: branch 0 taken
48: branch 1 taken
1711 1515: for (; WI.I != WI.E; ++WI.I) {
1712 1467: const ExplodedNode *Succ = *WI.I;
1713 : // End-of-path node?
67: branch 1 taken
1400: branch 2 taken
1714 1467: if (Succ->succ_empty()) {
1715 : // If we found an end-of-path node that is not a sink, then return
1716 : // this report.
59: branch 1 taken
8: branch 2 taken
1717 67: if (!Succ->isSink())
1718 118: return R;
1719 :
1720 : // Found a sink? Continue on to the next successor.
1721 8: continue;
1722 : }
1723 :
1724 : // Mark the successor as visited. If it hasn't been explored,
1725 : // enqueue it to the DFS worklist.
1726 1400: unsigned &mark = Visited[Succ];
1356: branch 0 taken
44: branch 1 taken
1727 1400: if (!mark) {
1728 1356: mark = 1;
1729 1356: WL.push_back(Succ);
1730 1356: break;
1731 : }
1732 : }
1733 :
48: branch 1 taken
1356: branch 2 taken
1734 1404: if (&WL.back() == &WI)
1735 48: WL.pop_back();
1736 : }
1737 : }
1738 :
1739 : // If we reach here, the end nodes for all reports in the equivalence
1740 : // class are post-dominated by a sink node.
1741 4: return NULL;
1742 : }
1743 :
1744 :
1745 : //===----------------------------------------------------------------------===//
1746 : // DiagnosticCache. This is a hack to cache analyzer diagnostics. It
1747 : // uses global state, which eventually should go elsewhere.
1748 : //===----------------------------------------------------------------------===//
1749 : namespace {
1750 26: class DiagCacheItem : public llvm::FoldingSetNode {
1751 : llvm::FoldingSetNodeID ID;
1752 : public:
1753 726: DiagCacheItem(BugReport *R, PathDiagnostic *PD) {
1754 726: ID.AddString(R->getBugType().getName());
1755 726: ID.AddString(R->getBugType().getCategory());
1756 726: ID.AddString(R->getDescription());
1757 726: ID.AddInteger(R->getLocation().getRawEncoding());
1758 726: PD->Profile(ID);
1759 726: }
1760 :
1761 155: void Profile(llvm::FoldingSetNodeID &id) {
1762 155: id = ID;
1763 155: }
1764 :
1765 726: llvm::FoldingSetNodeID &getID() { return ID; }
1766 : };
1767 : }
1768 :
1769 726: static bool IsCachedDiagnostic(BugReport *R, PathDiagnostic *PD) {
1770 : // FIXME: Eventually this diagnostic cache should reside in something
1771 : // like AnalysisManager instead of being a static variable. This is
1772 : // really unsafe in the long term.
1773 : typedef llvm::FoldingSet<DiagCacheItem> DiagnosticCache;
106: branch 0 taken
620: branch 1 taken
106: branch 3 taken
0: branch 4 not taken
1774 726: static DiagnosticCache DC;
1775 :
1776 : void *InsertPos;
1777 726: DiagCacheItem *Item = new DiagCacheItem(R, PD);
1778 :
26: branch 2 taken
700: branch 3 taken
1779 726: if (DC.FindNodeOrInsertPos(Item->getID(), InsertPos)) {
26: branch 0 taken
0: branch 1 not taken
1780 26: delete Item;
1781 26: return true;
1782 : }
1783 :
1784 700: DC.InsertNode(Item, InsertPos);
1785 700: return false;
1786 : }
1787 :
1788 730: void BugReporter::FlushReport(BugReportEquivClass& EQ) {
1789 730: BugReport *R = FindReportInEquivalenceClass(EQ);
1790 :
4: branch 0 taken
726: branch 1 taken
1791 730: if (!R)
1792 4: return;
1793 :
1794 726: PathDiagnosticClient* PD = getPathDiagnosticClient();
1795 :
1796 : // FIXME: Make sure we use the 'R' for the path that was actually used.
1797 : // Probably doesn't make a difference in practice.
1798 726: BugType& BT = R->getBugType();
1799 :
1800 : llvm::OwningPtr<PathDiagnostic>
1801 : D(new PathDiagnostic(R->getBugType().getName(),
1802 : !PD || PD->useVerboseDescription()
1803 : ? R->getDescription() : R->getShortDescription(),
7: branch 2 taken
719: branch 3 taken
1: branch 5 taken
6: branch 6 taken
1804 726: BT.getCategory()));
1805 :
1806 726: GeneratePathDiagnostic(*D.get(), EQ);
1807 :
26: branch 2 taken
700: branch 3 taken
1808 726: if (IsCachedDiagnostic(R, D.get()))
1809 719: return;
1810 :
1811 : // Get the meta data.
1812 700: std::pair<const char**, const char**> Meta = R->getExtraDescriptiveText();
237: branch 0 taken
700: branch 1 taken
1813 937: for (const char** s = Meta.first; s != Meta.second; ++s)
1814 237: D->addMeta(*s);
1815 :
1816 : // Emit a summary diagnostic to the regular Diagnostics engine.
1817 700: const SourceRange *Beg = 0, *End = 0;
1818 700: R->getRanges(Beg, End);
1819 700: Diagnostic& Diag = getDiagnostic();
1820 700: FullSourceLoc L(R->getLocation(), getSourceManager());
1821 :
1822 : // Search the description for '%', as that will be interpretted as a
1823 : // format character by FormatDiagnostics.
1824 700: llvm::StringRef desc = R->getShortDescription();
1825 : unsigned ErrorDiag;
1826 : {
1827 700: llvm::SmallString<512> TmpStr;
1828 700: llvm::raw_svector_ostream Out(TmpStr);
44718: branch 2 taken
700: branch 3 taken
1829 45418: for (llvm::StringRef::iterator I=desc.begin(), E=desc.end(); I!=E; ++I)
8: branch 0 taken
44710: branch 1 taken
1830 44718: if (*I == '%')
1831 8: Out << "%%";
1832 : else
1833 44710: Out << *I;
1834 :
1835 700: Out.flush();
1836 700: ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, TmpStr);
1837 : }
1838 :
0: branch 0 not taken
293: branch 1 taken
381: branch 2 taken
26: branch 3 taken
0: branch 4 not taken
1839 700: switch (End-Beg) {
1840 0: default: assert(0 && "Don't handle this many ranges yet!");
1841 293: case 0: Diag.Report(L, ErrorDiag); break;
1842 381: case 1: Diag.Report(L, ErrorDiag) << Beg[0]; break;
1843 26: case 2: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1]; break;
1844 0: case 3: Diag.Report(L, ErrorDiag) << Beg[0] << Beg[1] << Beg[2]; break;
1845 : }
1846 :
1847 : // Emit a full diagnostic for the path if we have a PathDiagnosticClient.
693: branch 0 taken
7: branch 1 taken
1848 700: if (!PD)
1849 : return;
1850 :
0: branch 2 not taken
7: branch 3 taken
1851 7: if (D->empty()) {
1852 : PathDiagnosticPiece* piece =
1853 0: new PathDiagnosticEventPiece(L, R->getDescription());
1854 :
0: branch 1 not taken
0: branch 2 not taken
1855 0: for ( ; Beg != End; ++Beg) piece->addRange(*Beg);
1856 0: D->push_back(piece);
1857 : }
1858 :
7: branch 3 taken
719: branch 4 taken
1859 7: PD->HandlePathDiagnostic(D.take());
1860 : }
1861 :
1862 : void BugReporter::EmitBasicReport(llvm::StringRef name, llvm::StringRef str,
1863 : SourceLocation Loc,
1864 1: SourceRange* RBeg, unsigned NumRanges) {
1865 1: EmitBasicReport(name, "", str, Loc, RBeg, NumRanges);
1866 1: }
1867 :
1868 : void BugReporter::EmitBasicReport(llvm::StringRef name,
1869 : llvm::StringRef category,
1870 : llvm::StringRef str, SourceLocation Loc,
1871 146: SourceRange* RBeg, unsigned NumRanges) {
1872 :
1873 : // 'BT' will be owned by BugReporter as soon as we call 'EmitReport'.
1874 146: BugType *BT = new BugType(name, category);
1875 146: FullSourceLoc L = getContext().getFullLoc(Loc);
1876 146: RangedBugReport *R = new DiagBugReport(*BT, str, L);
141: branch 1 taken
146: branch 2 taken
1877 146: for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
1878 146: EmitReport(R);
1879 146: }
Generated: 2010-02-10 01:31 by zcov