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