PathDiagnostic.cpp revision bac341346f3c8e713a8f165120fd54b500ee3189 
1//===--- PathDiagnostic.cpp - Path-Specific Diagnostic Handling -*- 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 the PathDiagnostic-related interfaces.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
15#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/Decl.h"
18#include "clang/AST/DeclObjC.h"
19#include "clang/AST/ParentMap.h"
20#include "clang/AST/StmtCXX.h"
21#include "llvm/ADT/SmallString.h"
22
23using namespace clang;
24using namespace ento;
25
26bool PathDiagnosticMacroPiece::containsEvent() const {
27  for (const_iterator I = begin(), E = end(); I!=E; ++I) {
28    if (isa<PathDiagnosticEventPiece>(*I))
29      return true;
30
31    if (PathDiagnosticMacroPiece *MP = dyn_cast<PathDiagnosticMacroPiece>(*I))
32      if (MP->containsEvent())
33        return true;
34  }
35
36  return false;
37}
38
39static StringRef StripTrailingDots(StringRef s) {
40  for (StringRef::size_type i = s.size(); i != 0; --i)
41    if (s[i - 1] != '.')
42      return s.substr(0, i);
43  return "";
44}
45
46PathDiagnosticPiece::PathDiagnosticPiece(StringRef s,
47                                         Kind k, DisplayHint hint)
48  : str(StripTrailingDots(s)), kind(k), Hint(hint) {}
49
50PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint)
51  : kind(k), Hint(hint) {}
52
53PathDiagnosticPiece::~PathDiagnosticPiece() {}
54PathDiagnosticEventPiece::~PathDiagnosticEventPiece() {}
55PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() {}
56
57PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() {
58  for (iterator I = begin(), E = end(); I != E; ++I) delete *I;
59}
60
61PathDiagnostic::PathDiagnostic() : Size(0) {}
62
63PathDiagnostic::~PathDiagnostic() {
64  for (iterator I = begin(), E = end(); I != E; ++I) delete &*I;
65}
66
67void PathDiagnostic::resetPath(bool deletePieces) {
68  Size = 0;
69
70  if (deletePieces)
71    for (iterator I=begin(), E=end(); I!=E; ++I)
72      delete &*I;
73
74  path.clear();
75}
76
77
78PathDiagnostic::PathDiagnostic(StringRef bugtype, StringRef desc,
79                               StringRef category)
80  : Size(0),
81    BugType(StripTrailingDots(bugtype)),
82    Desc(StripTrailingDots(desc)),
83    Category(StripTrailingDots(category)) {}
84
85void PathDiagnosticConsumer::anchor() { }
86
87PathDiagnosticConsumer::~PathDiagnosticConsumer() {
88  // Delete the contents of the FoldingSet if it isn't empty already.
89  for (llvm::FoldingSet<PathDiagnostic>::iterator it =
90       Diags.begin(), et = Diags.end() ; it != et ; ++it) {
91    delete &*it;
92  }
93}
94
95void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) {
96  if (!D)
97    return;
98
99  if (D->empty()) {
100    delete D;
101    return;
102  }
103
104  // We need to flatten the locations (convert Stmt* to locations) because
105  // the referenced statements may be freed by the time the diagnostics
106  // are emitted.
107  D->flattenLocations();
108
109  // Profile the node to see if we already have something matching it
110  llvm::FoldingSetNodeID profile;
111  D->Profile(profile);
112  void *InsertPos = 0;
113
114  if (PathDiagnostic *orig = Diags.FindNodeOrInsertPos(profile, InsertPos)) {
115    // Keep the PathDiagnostic with the shorter path.
116    if (orig->size() <= D->size()) {
117      bool shouldKeepOriginal = true;
118      if (orig->size() == D->size()) {
119        // Here we break ties in a fairly arbitrary, but deterministic, way.
120        llvm::FoldingSetNodeID fullProfile, fullProfileOrig;
121        D->FullProfile(fullProfile);
122        orig->FullProfile(fullProfileOrig);
123        if (fullProfile.ComputeHash() < fullProfileOrig.ComputeHash())
124          shouldKeepOriginal = false;
125      }
126
127      if (shouldKeepOriginal) {
128        delete D;
129        return;
130      }
131    }
132    Diags.RemoveNode(orig);
133    delete orig;
134  }
135
136  Diags.InsertNode(D);
137}
138
139
140namespace {
141struct CompareDiagnostics {
142  // Compare if 'X' is "<" than 'Y'.
143  bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const {
144    // First compare by location
145    const FullSourceLoc &XLoc = X->getLocation().asLocation();
146    const FullSourceLoc &YLoc = Y->getLocation().asLocation();
147    if (XLoc < YLoc)
148      return true;
149    if (XLoc != YLoc)
150      return false;
151
152    // Next, compare by bug type.
153    StringRef XBugType = X->getBugType();
154    StringRef YBugType = Y->getBugType();
155    if (XBugType < YBugType)
156      return true;
157    if (XBugType != YBugType)
158      return false;
159
160    // Next, compare by bug description.
161    StringRef XDesc = X->getDescription();
162    StringRef YDesc = Y->getDescription();
163    if (XDesc < YDesc)
164      return true;
165    if (XDesc != YDesc)
166      return false;
167
168    // FIXME: Further refine by comparing PathDiagnosticPieces?
169    return false;
170  }
171};
172}
173
174void
175PathDiagnosticConsumer::FlushDiagnostics(SmallVectorImpl<std::string> *Files) {
176  if (flushed)
177    return;
178
179  flushed = true;
180
181  std::vector<const PathDiagnostic *> BatchDiags;
182  for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(),
183       et = Diags.end(); it != et; ++it) {
184    BatchDiags.push_back(&*it);
185  }
186
187  // Clear out the FoldingSet.
188  Diags.clear();
189
190  // Sort the diagnostics so that they are always emitted in a deterministic
191  // order.
192  if (!BatchDiags.empty())
193    std::sort(BatchDiags.begin(), BatchDiags.end(), CompareDiagnostics());
194
195  FlushDiagnosticsImpl(BatchDiags, Files);
196
197  // Delete the flushed diagnostics.
198  for (std::vector<const PathDiagnostic *>::iterator it = BatchDiags.begin(),
199       et = BatchDiags.end(); it != et; ++it) {
200    const PathDiagnostic *D = *it;
201    delete D;
202  }
203}
204
205//===----------------------------------------------------------------------===//
206// PathDiagnosticLocation methods.
207//===----------------------------------------------------------------------===//
208
209static SourceLocation getValidSourceLocation(const Stmt* S,
210                                             LocationOrAnalysisDeclContext LAC) {
211  SourceLocation L = S->getLocStart();
212  assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should "
213                          "be passed to PathDiagnosticLocation upon creation.");
214
215  // S might be a temporary statement that does not have a location in the
216  // source code, so find an enclosing statement and use it's location.
217  if (!L.isValid()) {
218
219    ParentMap *PM = 0;
220    if (LAC.is<const LocationContext*>())
221      PM = &LAC.get<const LocationContext*>()->getParentMap();
222    else
223      PM = &LAC.get<AnalysisDeclContext*>()->getParentMap();
224
225    while (!L.isValid()) {
226      S = PM->getParent(S);
227      L = S->getLocStart();
228    }
229  }
230
231  return L;
232}
233
234PathDiagnosticLocation
235  PathDiagnosticLocation::createBegin(const Decl *D,
236                                      const SourceManager &SM) {
237  return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
238}
239
240PathDiagnosticLocation
241  PathDiagnosticLocation::createBegin(const Stmt *S,
242                                      const SourceManager &SM,
243                                      LocationOrAnalysisDeclContext LAC) {
244  return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
245                                SM, SingleLocK);
246}
247
248PathDiagnosticLocation
249  PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
250                                            const SourceManager &SM) {
251  return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
252}
253
254PathDiagnosticLocation
255  PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
256                                          const SourceManager &SM) {
257  return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
258}
259
260PathDiagnosticLocation
261  PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
262                                           const SourceManager &SM) {
263  SourceLocation L = CS->getLBracLoc();
264  return PathDiagnosticLocation(L, SM, SingleLocK);
265}
266
267PathDiagnosticLocation
268  PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
269                                         const SourceManager &SM) {
270  SourceLocation L = CS->getRBracLoc();
271  return PathDiagnosticLocation(L, SM, SingleLocK);
272}
273
274PathDiagnosticLocation
275  PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
276                                          const SourceManager &SM) {
277  // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
278  if (const CompoundStmt *CS =
279        dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
280    if (!CS->body_empty()) {
281      SourceLocation Loc = (*CS->body_begin())->getLocStart();
282      return PathDiagnosticLocation(Loc, SM, SingleLocK);
283    }
284
285  return PathDiagnosticLocation();
286}
287
288PathDiagnosticLocation
289  PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
290                                        const SourceManager &SM) {
291  SourceLocation L = LC->getDecl()->getBodyRBrace();
292  return PathDiagnosticLocation(L, SM, SingleLocK);
293}
294
295PathDiagnosticLocation
296  PathDiagnosticLocation::create(const ProgramPoint& P,
297                                 const SourceManager &SMng) {
298
299  const Stmt* S = 0;
300  if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
301    const CFGBlock *BSrc = BE->getSrc();
302    S = BSrc->getTerminatorCondition();
303  }
304  else if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) {
305    S = PS->getStmt();
306  }
307
308  return PathDiagnosticLocation(S, SMng, P.getLocationContext());
309}
310
311PathDiagnosticLocation
312  PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N,
313                                          const SourceManager &SM) {
314  assert(N && "Cannot create a location with a null node.");
315
316  const ExplodedNode *NI = N;
317
318  while (NI) {
319    ProgramPoint P = NI->getLocation();
320    const LocationContext *LC = P.getLocationContext();
321    if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P))
322      return PathDiagnosticLocation(PS->getStmt(), SM, LC);
323    else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
324      const Stmt *Term = BE->getSrc()->getTerminator();
325      assert(Term);
326      return PathDiagnosticLocation(Term, SM, LC);
327    }
328    NI = NI->succ_empty() ? 0 : *(NI->succ_begin());
329  }
330
331  return createDeclEnd(N->getLocationContext(), SM);
332}
333
334PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
335                                           const PathDiagnosticLocation &PDL) {
336  FullSourceLoc L = PDL.asLocation();
337  return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
338}
339
340FullSourceLoc
341  PathDiagnosticLocation::genLocation(SourceLocation L,
342                                      LocationOrAnalysisDeclContext LAC) const {
343  assert(isValid());
344  // Note that we want a 'switch' here so that the compiler can warn us in
345  // case we add more cases.
346  switch (K) {
347    case SingleLocK:
348    case RangeK:
349      break;
350    case StmtK:
351      // Defensive checking.
352      if (!S)
353        break;
354      return FullSourceLoc(getValidSourceLocation(S, LAC),
355                           const_cast<SourceManager&>(*SM));
356    case DeclK:
357      // Defensive checking.
358      if (!D)
359        break;
360      return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
361  }
362
363  return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
364}
365
366PathDiagnosticRange
367  PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
368  assert(isValid());
369  // Note that we want a 'switch' here so that the compiler can warn us in
370  // case we add more cases.
371  switch (K) {
372    case SingleLocK:
373      return PathDiagnosticRange(SourceRange(Loc,Loc), true);
374    case RangeK:
375      break;
376    case StmtK: {
377      const Stmt *S = asStmt();
378      switch (S->getStmtClass()) {
379        default:
380          break;
381        case Stmt::DeclStmtClass: {
382          const DeclStmt *DS = cast<DeclStmt>(S);
383          if (DS->isSingleDecl()) {
384            // Should always be the case, but we'll be defensive.
385            return SourceRange(DS->getLocStart(),
386                               DS->getSingleDecl()->getLocation());
387          }
388          break;
389        }
390          // FIXME: Provide better range information for different
391          //  terminators.
392        case Stmt::IfStmtClass:
393        case Stmt::WhileStmtClass:
394        case Stmt::DoStmtClass:
395        case Stmt::ForStmtClass:
396        case Stmt::ChooseExprClass:
397        case Stmt::IndirectGotoStmtClass:
398        case Stmt::SwitchStmtClass:
399        case Stmt::BinaryConditionalOperatorClass:
400        case Stmt::ConditionalOperatorClass:
401        case Stmt::ObjCForCollectionStmtClass: {
402          SourceLocation L = getValidSourceLocation(S, LAC);
403          return SourceRange(L, L);
404        }
405      }
406      SourceRange R = S->getSourceRange();
407      if (R.isValid())
408        return R;
409      break;
410    }
411    case DeclK:
412      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
413        return MD->getSourceRange();
414      if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
415        if (Stmt *Body = FD->getBody())
416          return Body->getSourceRange();
417      }
418      else {
419        SourceLocation L = D->getLocation();
420        return PathDiagnosticRange(SourceRange(L, L), true);
421      }
422  }
423
424  return SourceRange(Loc,Loc);
425}
426
427void PathDiagnosticLocation::flatten() {
428  if (K == StmtK) {
429    K = RangeK;
430    S = 0;
431    D = 0;
432  }
433  else if (K == DeclK) {
434    K = SingleLocK;
435    S = 0;
436    D = 0;
437  }
438}
439
440//===----------------------------------------------------------------------===//
441// FoldingSet profiling methods.
442//===----------------------------------------------------------------------===//
443
444void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
445  ID.AddInteger(Range.getBegin().getRawEncoding());
446  ID.AddInteger(Range.getEnd().getRawEncoding());
447  ID.AddInteger(Loc.getRawEncoding());
448  return;
449}
450
451void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
452  ID.AddInteger((unsigned) getKind());
453  ID.AddString(str);
454  // FIXME: Add profiling support for code hints.
455  ID.AddInteger((unsigned) getDisplayHint());
456  for (range_iterator I = ranges_begin(), E = ranges_end(); I != E; ++I) {
457    ID.AddInteger(I->getBegin().getRawEncoding());
458    ID.AddInteger(I->getEnd().getRawEncoding());
459  }
460}
461
462void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
463  PathDiagnosticPiece::Profile(ID);
464  ID.Add(Pos);
465}
466
467void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
468  PathDiagnosticPiece::Profile(ID);
469  for (const_iterator I = begin(), E = end(); I != E; ++I)
470    ID.Add(*I);
471}
472
473void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
474  PathDiagnosticSpotPiece::Profile(ID);
475  for (const_iterator I = begin(), E = end(); I != E; ++I)
476    ID.Add(**I);
477}
478
479void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
480  if (Size)
481    getLocation().Profile(ID);
482  ID.AddString(BugType);
483  ID.AddString(Desc);
484  ID.AddString(Category);
485}
486
487void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
488  Profile(ID);
489  for (const_iterator I = begin(), E = end(); I != E; ++I)
490    ID.Add(*I);
491  for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
492    ID.AddString(*I);
493}
494