1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| //== PointerIterationChecker.cpp ------------------------------- -*- C++ -*--=//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines PointerIterationChecker which checks for non-determinism
// caused due to iteration of unordered containers of pointer elements.
//
//===----------------------------------------------------------------------===//
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
using namespace clang;
using namespace ento;
using namespace ast_matchers;
namespace {
// ID of a node at which the diagnostic would be emitted.
constexpr llvm::StringLiteral WarnAtNode = "iter";
class PointerIterationChecker : public Checker<check::ASTCodeBody> {
public:
void checkASTCodeBody(const Decl *D,
AnalysisManager &AM,
BugReporter &BR) const;
};
static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
BugReporter &BR, AnalysisManager &AM,
const PointerIterationChecker *Checker) {
auto *ADC = AM.getAnalysisDeclContext(D);
const auto *MarkedStmt = Match.getNodeAs<Stmt>(WarnAtNode);
assert(MarkedStmt);
auto Range = MarkedStmt->getSourceRange();
auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
BR.getSourceManager(),
ADC);
std::string Diagnostics;
llvm::raw_string_ostream OS(Diagnostics);
OS << "Iteration of pointer-like elements "
<< "can result in non-deterministic ordering";
BR.EmitBasicReport(ADC->getDecl(), Checker,
"Iteration of pointer-like elements", "Non-determinism",
OS.str(), Location, Range);
}
// Assumption: Iteration of ordered containers of pointers is deterministic.
// TODO: Currently, we only check for std::unordered_set. Other unordered
// containers like std::unordered_map also need to be handled.
// TODO: Currently, we do not check what the for loop does with the iterated
// pointer values. Not all iterations may cause non-determinism. For example,
// counting or summing up the elements should not be non-deterministic.
auto matchUnorderedIterWithPointers() -> decltype(decl()) {
auto UnorderedContainerM = declRefExpr(to(varDecl(hasType(
recordDecl(hasName("std::unordered_set")
)))));
auto PointerTypeM = varDecl(hasType(hasCanonicalType(pointerType())));
auto PointerIterM = stmt(cxxForRangeStmt(
hasLoopVariable(PointerTypeM),
hasRangeInit(UnorderedContainerM)
)).bind(WarnAtNode);
return decl(forEachDescendant(PointerIterM));
}
void PointerIterationChecker::checkASTCodeBody(const Decl *D,
AnalysisManager &AM,
BugReporter &BR) const {
auto MatcherM = matchUnorderedIterWithPointers();
auto Matches = match(MatcherM, *D, AM.getASTContext());
for (const auto &Match : Matches)
emitDiagnostics(Match, D, BR, AM, this);
}
} // end of anonymous namespace
void ento::registerPointerIterationChecker(CheckerManager &Mgr) {
Mgr.registerChecker<PointerIterationChecker>();
}
bool ento::shouldRegisterPointerIterationChecker(const LangOptions &LO) {
return LO.CPlusPlus;
}
|