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
19using namespace clang;
20using namespace ento;
21using namespace ast_matchers;
22
23namespace {
24
25// ID of a node at which the diagnostic would be emitted.
26constexpr llvm::StringLiteral WarnAtNode = "sort";
27
28class PointerSortingChecker : public Checker<check::ASTCodeBody> {
29public:
30 void checkASTCodeBody(const Decl *D,
31 AnalysisManager &AM,
32 BugReporter &BR) const;
33};
34
35static 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>(ID: WarnAtNode);
41 assert(MarkedStmt);
42
43 auto Range = MarkedStmt->getSourceRange();
44 auto Location = PathDiagnosticLocation::createBegin(S: MarkedStmt,
45 SM: BR.getSourceManager(),
46 LAC: 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(DeclWithIssue: ADC->getDecl(), Checker,
53 BugName: "Sorting of pointer-like elements", BugCategory: "Non-determinism",
54 BugStr: OS.str(), Loc: Location, Ranges: Range);
55}
56
57decltype(auto) callsName(const char *FunctionName) {
58 return callee(InnerMatcher: functionDecl(hasName(Name: 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.
69auto matchSortWithPointers() -> decltype(decl()) {
70 // Match any of these function calls.
71 auto SortFuncM = anyOf(
72 callsName(FunctionName: "std::is_sorted"),
73 callsName(FunctionName: "std::nth_element"),
74 callsName(FunctionName: "std::partial_sort"),
75 callsName(FunctionName: "std::partition"),
76 callsName(FunctionName: "std::sort"),
77 callsName(FunctionName: "std::stable_partition"),
78 callsName(FunctionName: "std::stable_sort")
79 );
80
81 // Match only if the container has pointer-type elements.
82 auto IteratesPointerEltsM = hasArgument(N: 0,
83 InnerMatcher: hasType(InnerMatcher: cxxRecordDecl(has(
84 fieldDecl(hasType(InnerMatcher: hasCanonicalType(
85 InnerMatcher: pointsTo(InnerMatcher: hasCanonicalType(InnerMatcher: pointerType()))
86 )))
87 ))));
88
89 auto PointerSortM = traverse(
90 TK: TK_AsIs,
91 InnerMatcher: stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM))).bind(ID: WarnAtNode));
92
93 return decl(forEachDescendant(PointerSortM));
94}
95
96void PointerSortingChecker::checkASTCodeBody(const Decl *D,
97 AnalysisManager &AM,
98 BugReporter &BR) const {
99 auto MatcherM = matchSortWithPointers();
100
101 auto Matches = match(Matcher: MatcherM, Node: *D, Context&: AM.getASTContext());
102 for (const auto &Match : Matches)
103 emitDiagnostics(Match, D, BR, AM, Checker: this);
104}
105
106} // end of anonymous namespace
107
108void ento::registerPointerSortingChecker(CheckerManager &Mgr) {
109 Mgr.registerChecker<PointerSortingChecker>();
110}
111
112bool ento::shouldRegisterPointerSortingChecker(const CheckerManager &mgr) {
113 const LangOptions &LO = mgr.getLangOpts();
114 return LO.CPlusPlus;
115}
116