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 }
102