1 //=== PointerSortingChecker.cpp - Pointer sorting checker ------*- C++ -*--===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines PointerSortingChecker which checks for non-determinism
11 // caused due to sorting containers with pointer-like elements.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/ASTMatchers/ASTMatchFinder.h"
16 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
17 #include "clang/StaticAnalyzer/Core/Checker.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19 
20 using namespace clang;
21 using namespace ento;
22 using namespace ast_matchers;
23 
24 namespace {
25 
26 // ID of a node at which the diagnostic would be emitted.
27 constexpr llvm::StringLiteral WarnAtNode = "sort";
28 
29 class PointerSortingChecker : public Checker<check::ASTCodeBody> {
30 public:
31   void checkASTCodeBody(const Decl *D,
32                         AnalysisManager &AM,
33                         BugReporter &BR) const;
34 };
35 
36 static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
37                             BugReporter &BR, AnalysisManager &AM,
38                             const PointerSortingChecker *Checker) {
39   auto *ADC = AM.getAnalysisDeclContext(D);
40 
41   const auto *MarkedStmt = Match.getNodeAs<CallExpr>(WarnAtNode);
42   assert(MarkedStmt);
43 
44   auto Range = MarkedStmt->getSourceRange();
45   auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
46                                                       BR.getSourceManager(),
47                                                       ADC);
48   std::string Diagnostics;
49   llvm::raw_string_ostream OS(Diagnostics);
50   OS << "Sorting pointer-like elements "
51      << "can result in non-deterministic ordering";
52 
53   BR.EmitBasicReport(ADC->getDecl(), Checker,
54                      "Sorting of pointer-like elements", "Non-determinism",
55                      OS.str(), Location, Range);
56 }
57 
58 auto callsName(const char *FunctionName) -> decltype(callee(functionDecl())) {
59   return callee(functionDecl(hasName(FunctionName)));
60 }
61 
62 // FIXME: Currently we simply check if std::sort is used with pointer-like
63 // elements. This approach can have a big false positive rate. Using std::sort,
64 // std::unique and then erase is common technique for deduplicating a container
65 // (which in some cases might even be quicker than using, let's say std::set).
66 // In case a container contains arbitrary memory addresses (e.g. multiple
67 // things give different stuff but might give the same thing multiple times)
68 // which we don't want to do things with more than once, we might use
69 // sort-unique-erase and the sort call will emit a report.
70 auto matchSortWithPointers() -> decltype(decl()) {
71   // Match any of these function calls.
72   auto SortFuncM = anyOf(
73                      callsName("std::is_sorted"),
74                      callsName("std::nth_element"),
75                      callsName("std::partial_sort"),
76                      callsName("std::partition"),
77                      callsName("std::sort"),
78                      callsName("std::stable_partition"),
79                      callsName("std::stable_sort")
80                     );
81 
82   // Match only if the container has pointer-type elements.
83   auto IteratesPointerEltsM = hasArgument(0,
84                                 hasType(cxxRecordDecl(has(
85                                   fieldDecl(hasType(hasCanonicalType(
86                                     pointsTo(hasCanonicalType(pointerType()))
87                                   )))
88                               ))));
89 
90   auto PointerSortM = stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM))
91                       ).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 LangOptions &LO) {
113   return LO.CPlusPlus;
114 }
115