clang/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

   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 }