Clang Project

clang_source_code/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp
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>(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
57auto callsName(const char *FunctionName) -> decltype(callee(functionDecl())) {
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 = stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM))
90                      ).bind(WarnAtNode);
91
92  return decl(forEachDescendant(PointerSortM));
93}
94
95void PointerSortingChecker::checkASTCodeBody(const Decl *D,
96                                             AnalysisManager &AM,
97                                             BugReporter &BR) const {
98  auto MatcherM = matchSortWithPointers();
99
100  auto Matches = match(MatcherM, *D, AM.getASTContext());
101  for (const auto &Match : Matches)
102    emitDiagnostics(Match, D, BR, AM, this);
103}
104
105} // end of anonymous namespace
106
107void ento::registerPointerSortingChecker(CheckerManager &Mgr) {
108  Mgr.registerChecker<PointerSortingChecker>();
109}
110
111bool ento::shouldRegisterPointerSortingChecker(const LangOptions &LO) {
112  return LO.CPlusPlus;
113}
114
CodeThinker, Enjoy your reading code