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