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