clang 19.0.0git
PointerSortingChecker.cpp
Go to the documentation of this file.
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
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,
32 BugReporter &BR) const;
33};
34
35static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
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,
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
57decltype(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.
69auto 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
96void PointerSortingChecker::checkASTCodeBody(const Decl *D,
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
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}
static void emitDiagnostics(BoundNodes &Match, const Decl *D, BugReporter &BR, AnalysisManager &AM, const ObjCAutoreleaseWriteChecker *Checker)
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2820
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:85
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:449
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:109
const T * getNodeAs(StringRef ID) const
Returns the AST node bound to ID.
Definition: ASTMatchers.h:116
ASTContext & getASTContext() override
AnalysisDeclContext * getAnalysisDeclContext(const Decl *D)
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:585
const SourceManager & getSourceManager()
Definition: BugReporter.h:623
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=std::nullopt, ArrayRef< FixItHint > Fixits=std::nullopt)
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
const LangOptions & getLangOpts() const
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
A Range represents the closed range [from, to].
const AstTypeMatcher< PointerType > pointerType
Matches pointer types, but does not match Objective-C object pointer types.
internal::Matcher< NamedDecl > hasName(StringRef Name)
Matches NamedDecl nodes that have the specified name.
Definition: ASTMatchers.h:3078
const internal::VariadicDynCastAllOfMatcher< Stmt, CallExpr > callExpr
Matches call expressions.
const internal::ArgumentAdaptingMatcherFunc< internal::ForEachDescendantMatcher > forEachDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher.
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
const internal::ArgumentAdaptingMatcherFunc< internal::HasMatcher > has
Matches AST nodes that have child AST nodes that match the provided matcher.
const internal::VariadicDynCastAllOfMatcher< Decl, FieldDecl > fieldDecl
Matches field declarations.
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> allOf
Matches if all given matchers match.
const internal::VariadicDynCastAllOfMatcher< Decl, FunctionDecl > functionDecl
Matches function declarations.
const internal::VariadicDynCastAllOfMatcher< Decl, CXXRecordDecl > cxxRecordDecl
Matches C++ class declarations.
internal::Matcher< T > traverse(TraversalKind TK, const internal::Matcher< T > &InnerMatcher)
Causes all nested matchers to be matched with the specified traversal kind.
Definition: ASTMatchers.h:817
const internal::VariadicAllOfMatcher< Decl > decl
Matches declarations.
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> anyOf
Matches if any of the given matchers matches.
The JSON file list parser is used to communicate input to InstallAPI.
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:40