Home | History | Annotate | Line # | Download | only in Checkers 
      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 decltype(auto) callsName(const char *FunctionName) {
     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 = traverse(
     90       TK_AsIs,
     91       stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM))).bind(WarnAtNode));
     92 
     93   return decl(forEachDescendant(PointerSortM));
     94 }
     95 
     96 void PointerSortingChecker::checkASTCodeBody(const Decl *D,
     97                                              AnalysisManager &AM,
     98                                              BugReporter &BR) const {
     99   auto MatcherM = matchSortWithPointers();
    100 
    101   auto Matches = match(MatcherM, *D, AM.getASTContext());
    102   for (const auto &Match : Matches)
    103     emitDiagnostics(Match, D, BR, AM, this);
    104 }
    105 
    106 } // end of anonymous namespace
    107 
    108 void ento::registerPointerSortingChecker(CheckerManager &Mgr) {
    109   Mgr.registerChecker<PointerSortingChecker>();
    110 }
    111 
    112 bool ento::shouldRegisterPointerSortingChecker(const CheckerManager &mgr) {
    113   const LangOptions &LO = mgr.getLangOpts();
    114   return LO.CPlusPlus;
    115 }
    116