clang/lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp

   1 //== PointerIterationChecker.cpp ------------------------------- -*- C++ -*--=//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines PointerIterationChecker which checks for non-determinism
  10 // caused due to iteration of unordered containers of pointer elements.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/ASTMatchers/ASTMatchFinder.h"
  15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  16 #include "clang/StaticAnalyzer/Core/Checker.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  18
  19 using namespace clang;
  20 using namespace ento;
  21 using namespace ast_matchers;
  22
  23 namespace {
  24
  25 // ID of a node at which the diagnostic would be emitted.
  26 constexpr llvm::StringLiteral WarnAtNode = "iter";
  27
  28 class PointerIterationChecker : public Checker<check::ASTCodeBody> {
  29 public:
  30   void checkASTCodeBody(const Decl *D,
  31                         AnalysisManager &AM,
  32                         BugReporter &BR) const;
  33 };
  34
  35 static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
  36                             BugReporter &BR, AnalysisManager &AM,
  37                             const PointerIterationChecker *Checker) {
  38   auto *ADC = AM.getAnalysisDeclContext(D);
  39
  40   const auto *MarkedStmt = Match.getNodeAs<Stmt>(WarnAtNode);
  41   assert(MarkedStmt);
  42
  43   auto Range = MarkedStmt->getSourceRange();
  44   auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
  45                                                       BR.getSourceManager(),
  46                                                       ADC);
  47   std::string Diagnostics;
  48   llvm::raw_string_ostream OS(Diagnostics);
  49   OS << "Iteration of pointer-like elements "
  50      << "can result in non-deterministic ordering";
  51
  52   BR.EmitBasicReport(ADC->getDecl(), Checker,
  53                      "Iteration of pointer-like elements", "Non-determinism",
  54                      OS.str(), Location, Range);
  55 }
  56
  57 // Assumption: Iteration of ordered containers of pointers is deterministic.
  58
  59 // TODO: Currently, we only check for std::unordered_set. Other unordered
  60 // containers like std::unordered_map also need to be handled.
  61
  62 // TODO: Currently, we do not check what the for loop does with the iterated
  63 // pointer values. Not all iterations may cause non-determinism. For example,
  64 // counting or summing up the elements should not be non-deterministic.
  65
  66 auto matchUnorderedIterWithPointers() -> decltype(decl()) {
  67
  68   auto UnorderedContainerM = declRefExpr(to(varDecl(hasType(
  69                                recordDecl(hasName("std::unordered_set")
  70                              )))));
  71
  72   auto PointerTypeM = varDecl(hasType(hasCanonicalType(pointerType())));
  73
  74   auto PointerIterM = stmt(cxxForRangeStmt(
  75                              hasLoopVariable(PointerTypeM),
  76                              hasRangeInit(UnorderedContainerM)
  77                       )).bind(WarnAtNode);
  78
  79   return decl(forEachDescendant(PointerIterM));
  80 }
  81
  82 void PointerIterationChecker::checkASTCodeBody(const Decl *D,
  83                                              AnalysisManager &AM,
  84                                              BugReporter &BR) const {
  85   auto MatcherM = matchUnorderedIterWithPointers();
  86
  87   auto Matches = match(MatcherM, *D, AM.getASTContext());
  88   for (const auto &Match : Matches)
  89     emitDiagnostics(Match, D, BR, AM, this);
  90 }
  91
  92 } // end of anonymous namespace
  93
  94 void ento::registerPointerIterationChecker(CheckerManager &Mgr) {
  95   Mgr.registerChecker<PointerIterationChecker>();
  96 }
  97
  98 bool ento::shouldRegisterPointerIterationChecker(const CheckerManager &mgr) {
  99   const LangOptions &LO = mgr.getLangOpts();
 100   return LO.CPlusPlus;
 101 }