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