Coverage Report

Created: 2020-10-24 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp
Line
Count
Source
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
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
7
                            const PointerSortingChecker *Checker) {
38
7
  auto *ADC = AM.getAnalysisDeclContext(D);
39
40
7
  const auto *MarkedStmt = Match.getNodeAs<CallExpr>(WarnAtNode);
41
7
  assert(MarkedStmt);
42
43
7
  auto Range = MarkedStmt->getSourceRange();
44
7
  auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
45
7
                                                      BR.getSourceManager(),
46
7
                                                      ADC);
47
7
  std::string Diagnostics;
48
7
  llvm::raw_string_ostream OS(Diagnostics);
49
7
  OS << "Sorting pointer-like elements "
50
7
     << "can result in non-deterministic ordering";
51
52
7
  BR.EmitBasicReport(ADC->getDecl(), Checker,
53
7
                     "Sorting of pointer-like elements", "Non-determinism",
54
7
                     OS.str(), Location, Range);
55
7
}
56
57
21
decltype(auto) callsName(const char *FunctionName) {
58
21
  return callee(functionDecl(hasName(FunctionName)));
59
21
}
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
3
auto matchSortWithPointers() -> decltype(decl()) {
70
  // Match any of these function calls.
71
3
  auto SortFuncM = anyOf(
72
3
                     callsName("std::is_sorted"),
73
3
                     callsName("std::nth_element"),
74
3
                     callsName("std::partial_sort"),
75
3
                     callsName("std::partition"),
76
3
                     callsName("std::sort"),
77
3
                     callsName("std::stable_partition"),
78
3
                     callsName("std::stable_sort")
79
3
                    );
80
81
  // Match only if the container has pointer-type elements.
82
3
  auto IteratesPointerEltsM = hasArgument(0,
83
3
                                hasType(cxxRecordDecl(has(
84
3
                                  fieldDecl(hasType(hasCanonicalType(
85
3
                                    pointsTo(hasCanonicalType(pointerType()))
86
3
                                  )))
87
3
                              ))));
88
89
3
  auto PointerSortM = traverse(
90
3
      TK_AsIs,
91
3
      stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM))).bind(WarnAtNode));
92
93
3
  return decl(forEachDescendant(PointerSortM));
94
3
}
95
96
void PointerSortingChecker::checkASTCodeBody(const Decl *D,
97
                                             AnalysisManager &AM,
98
3
                                             BugReporter &BR) const {
99
3
  auto MatcherM = matchSortWithPointers();
100
101
3
  auto Matches = match(MatcherM, *D, AM.getASTContext());
102
3
  for (const auto &Match : Matches)
103
7
    emitDiagnostics(Match, D, BR, AM, this);
104
3
}
105
106
} // end of anonymous namespace
107
108
1
void ento::registerPointerSortingChecker(CheckerManager &Mgr) {
109
1
  Mgr.registerChecker<PointerSortingChecker>();
110
1
}
111
112
2
bool ento::shouldRegisterPointerSortingChecker(const CheckerManager &mgr) {
113
2
  const LangOptions &LO = mgr.getLangOpts();
114
2
  return LO.CPlusPlus;
115
2
}