1//== PointerIterationChecker.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 PointerIterationChecker which checks for non-determinism
10// caused due to iteration of unordered containers of pointer 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 = "iter";
27
28class PointerIterationChecker : 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 PointerIterationChecker *Checker) {
38  auto *ADC = AM.getAnalysisDeclContext(D);
39
40  const auto *MarkedStmt = Match.getNodeAs<Stmt>(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 << "Iteration of pointer-like elements "
50     << "can result in non-deterministic ordering";
51
52  BR.EmitBasicReport(ADC->getDecl(), Checker,
53                     "Iteration of pointer-like elements", "Non-determinism",
54                     OS.str(), Location, Range);
55}
56
57// Assumption: Iteration of ordered containers of pointers is deterministic.
58
59// TODO: Currently, we only check for std::unordered_set. Other unordered
60// containers like std::unordered_map also need to be handled.
61
62// TODO: Currently, we do not check what the for loop does with the iterated
63// pointer values. Not all iterations may cause non-determinism. For example,
64// counting or summing up the elements should not be non-deterministic.
65
66auto matchUnorderedIterWithPointers() -> decltype(decl()) {
67
68  auto UnorderedContainerM = declRefExpr(to(varDecl(hasType(
69                               recordDecl(hasName("std::unordered_set")
70                             )))));
71
72  auto PointerTypeM = varDecl(hasType(hasCanonicalType(pointerType())));
73
74  auto PointerIterM = stmt(cxxForRangeStmt(
75                             hasLoopVariable(PointerTypeM),
76                             hasRangeInit(UnorderedContainerM)
77                      )).bind(WarnAtNode);
78
79  return decl(forEachDescendant(PointerIterM));
80}
81
82void PointerIterationChecker::checkASTCodeBody(const Decl *D,
83                                             AnalysisManager &AM,
84                                             BugReporter &BR) const {
85  auto MatcherM = matchUnorderedIterWithPointers();
86
87  auto Matches = match(MatcherM, *D, AM.getASTContext());
88  for (const auto &Match : Matches)
89    emitDiagnostics(Match, D, BR, AM, this);
90}
91
92} // end of anonymous namespace
93
94void ento::registerPointerIterationChecker(CheckerManager &Mgr) {
95  Mgr.registerChecker<PointerIterationChecker>();
96}
97
98bool ento::shouldRegisterPointerIterationChecker(const LangOptions &LO) {
99  return LO.CPlusPlus;
100}
101