1 //== PointerSortingChecker.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 PointerSortingChecker which checks for non-determinism 10 // caused due to sorting containers with pointer-like 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 = "sort"; 27 28 class PointerSortingChecker : 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 PointerSortingChecker *Checker) { 38 auto *ADC = AM.getAnalysisDeclContext(D); 39 40 const auto *MarkedStmt = Match.getNodeAs<CallExpr>(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 << "Sorting pointer-like elements " 50 << "can result in non-deterministic ordering"; 51 52 BR.EmitBasicReport(ADC->getDecl(), Checker, 53 "Sorting of pointer-like elements", "Non-determinism", 54 OS.str(), Location, Range); 55 } 56 57 auto callsName(const char *FunctionName) -> decltype(callee(functionDecl())) { 58 return callee(functionDecl(hasName(FunctionName))); 59 } 60 61 // FIXME: Currently we simply check if std::sort is used with pointer-like 62 // elements. This approach can have a big false positive rate. Using std::sort, 63 // std::unique and then erase is common technique for deduplicating a container 64 // (which in some cases might even be quicker than using, let's say std::set). 65 // In case a container contains arbitrary memory addresses (e.g. multiple 66 // things give different stuff but might give the same thing multiple times) 67 // which we don't want to do things with more than once, we might use 68 // sort-unique-erase and the sort call will emit a report. 69 auto matchSortWithPointers() -> decltype(decl()) { 70 // Match any of these function calls. 71 auto SortFuncM = anyOf( 72 callsName("std::is_sorted"), 73 callsName("std::nth_element"), 74 callsName("std::partial_sort"), 75 callsName("std::partition"), 76 callsName("std::sort"), 77 callsName("std::stable_partition"), 78 callsName("std::stable_sort") 79 ); 80 81 // Match only if the container has pointer-type elements. 82 auto IteratesPointerEltsM = hasArgument(0, 83 hasType(cxxRecordDecl(has( 84 fieldDecl(hasType(hasCanonicalType( 85 pointsTo(hasCanonicalType(pointerType())) 86 ))) 87 )))); 88 89 auto PointerSortM = stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM)) 90 ).bind(WarnAtNode); 91 92 return decl(forEachDescendant(PointerSortM)); 93 } 94 95 void PointerSortingChecker::checkASTCodeBody(const Decl *D, 96 AnalysisManager &AM, 97 BugReporter &BR) const { 98 auto MatcherM = matchSortWithPointers(); 99 100 auto Matches = match(MatcherM, *D, AM.getASTContext()); 101 for (const auto &Match : Matches) 102 emitDiagnostics(Match, D, BR, AM, this); 103 } 104 105 } // end of anonymous namespace 106 107 void ento::registerPointerSortingChecker(CheckerManager &Mgr) { 108 Mgr.registerChecker<PointerSortingChecker>(); 109 } 110 111 bool ento::shouldRegisterPointerSortingChecker(const LangOptions &LO) { 112 return LO.CPlusPlus; 113 } 114