clang  14.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 
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 }
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
clang::ast_matchers::stmt
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
Definition: ASTMatchersInternal.cpp:810
clang::ast_matchers::anyOf
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> anyOf
Matches if any of the given matchers matches.
Definition: ASTMatchersInternal.cpp:989
clang::ast_matchers::allOf
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> allOf
Matches if all given matchers match.
Definition: ASTMatchersInternal.cpp:992
ASTMatchFinder.h
emitDiagnostics
static void emitDiagnostics(BoundNodes &Match, const Decl *D, BugReporter &BR, AnalysisManager &AM, const ObjCAutoreleaseWriteChecker *Checker)
Definition: ObjCAutoreleaseWriteChecker.cpp:109
clang::ast_matchers::traverse
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:815
clang::ast_matchers::forEachDescendant
const internal::ArgumentAdaptingMatcherFunc< internal::ForEachDescendantMatcher > forEachDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher.
Definition: ASTMatchersInternal.cpp:1014
BuiltinCheckerRegistration.h
clang::transformer::EditKind::Range
@ Range
clang::ast_matchers::decl
const internal::VariadicAllOfMatcher< Decl > decl
Matches declarations.
Definition: ASTMatchersInternal.cpp:734
clang::TK_AsIs
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:40
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
clang::ast_matchers::callExpr
const internal::VariadicDynCastAllOfMatcher< Stmt, CallExpr > callExpr
Matches call expressions.
Definition: ASTMatchersInternal.cpp:817
CheckerContext.h
clang::LangOptions
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:58
clang::ast_matchers::functionDecl
const internal::VariadicDynCastAllOfMatcher< Decl, FunctionDecl > functionDecl
Matches function declarations.
Definition: ASTMatchersInternal.cpp:806
Checker.h
clang::ast_matchers::pointerType
const AstTypeMatcher< PointerType > pointerType
Matches pointer types, but does not match Objective-C object pointer types.
Definition: ASTMatchersInternal.cpp:1050
clang::ast_matchers::BoundNodes::getNodeAs
const T * getNodeAs(StringRef ID) const
Returns the AST node bound to ID.
Definition: ASTMatchers.h:114
clang
Definition: CalledOnceCheck.h:17
clang::ast_matchers::match
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
Definition: ASTMatchFinder.h:312
clang::ast_matchers::hasName
internal::Matcher< NamedDecl > hasName(StringRef Name)
Matches NamedDecl nodes that have the specified name.
Definition: ASTMatchers.h:2991
clang::ento::PathDiagnosticLocation::createBegin
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
Definition: PathDiagnostic.cpp:580
clang::ast_matchers::BoundNodes
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:107
clang::ast_matchers::cxxRecordDecl
const internal::VariadicDynCastAllOfMatcher< Decl, CXXRecordDecl > cxxRecordDecl
Matches C++ class declarations.
Definition: ASTMatchersInternal.cpp:745
clang::ast_matchers::has
const internal::ArgumentAdaptingMatcherFunc< internal::HasMatcher > has
Matches AST nodes that have child AST nodes that match the provided matcher.
Definition: ASTMatchersInternal.cpp:1008
clang::CallExpr
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2795
clang::ast_matchers::fieldDecl
const internal::VariadicDynCastAllOfMatcher< Decl, FieldDecl > fieldDecl
Matches field declarations.
Definition: ASTMatchersInternal.cpp:803
clang::ento::ObjKind::OS
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...