1//===-- InvalidatedIteratorChecker.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// Defines a checker for access of invalidated iterators.
10//
11//===----------------------------------------------------------------------===//
12
13#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
14#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
15#include "clang/StaticAnalyzer/Core/Checker.h"
16#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
18
19
20#include "Iterator.h"
21
22using namespace clang;
23using namespace ento;
24using namespace iterator;
25
26namespace {
27
28class InvalidatedIteratorChecker
29  : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
30                   check::PreStmt<BinaryOperator>,
31                   check::PreStmt<ArraySubscriptExpr>,
32                   check::PreStmt<MemberExpr>> {
33
34  std::unique_ptr<BugType> InvalidatedBugType;
35
36  void verifyAccess(CheckerContext &C, const SVal &Val) const;
37  void reportBug(const StringRef &Message, const SVal &Val,
38                 CheckerContext &C, ExplodedNode *ErrNode) const;
39public:
40  InvalidatedIteratorChecker();
41
42  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
43  void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
44  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
45  void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
46  void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;
47
48};
49
50} //namespace
51
52InvalidatedIteratorChecker::InvalidatedIteratorChecker() {
53  InvalidatedBugType.reset(
54      new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
55}
56
57void InvalidatedIteratorChecker::checkPreCall(const CallEvent &Call,
58                                              CheckerContext &C) const {
59  // Check for access of invalidated position
60  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
61  if (!Func)
62    return;
63
64  if (Func->isOverloadedOperator() &&
65      isAccessOperator(Func->getOverloadedOperator())) {
66    // Check for any kind of access of invalidated iterator positions
67    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
68      verifyAccess(C, InstCall->getCXXThisVal());
69    } else {
70      verifyAccess(C, Call.getArgSVal(0));
71    }
72  }
73}
74
75void InvalidatedIteratorChecker::checkPreStmt(const UnaryOperator *UO,
76                                              CheckerContext &C) const {
77  if (isa<CXXThisExpr>(UO->getSubExpr()))
78    return;
79
80  ProgramStateRef State = C.getState();
81  UnaryOperatorKind OK = UO->getOpcode();
82  SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
83
84  if (isAccessOperator(OK)) {
85    verifyAccess(C, SubVal);
86  }
87}
88
89void InvalidatedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
90                                              CheckerContext &C) const {
91  ProgramStateRef State = C.getState();
92  BinaryOperatorKind OK = BO->getOpcode();
93  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
94
95  if (isAccessOperator(OK)) {
96    verifyAccess(C, LVal);
97  }
98}
99
100void InvalidatedIteratorChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
101                                              CheckerContext &C) const {
102  ProgramStateRef State = C.getState();
103  SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
104  verifyAccess(C, LVal);
105}
106
107void InvalidatedIteratorChecker::checkPreStmt(const MemberExpr *ME,
108                                              CheckerContext &C) const {
109  if (!ME->isArrow() || ME->isImplicitAccess())
110    return;
111
112  ProgramStateRef State = C.getState();
113  SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
114  verifyAccess(C, BaseVal);
115}
116
117void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
118  auto State = C.getState();
119  const auto *Pos = getIteratorPosition(State, Val);
120  if (Pos && !Pos->isValid()) {
121    auto *N = C.generateErrorNode(State);
122    if (!N) {
123      return;
124    }
125    reportBug("Invalidated iterator accessed.", Val, C, N);
126  }
127}
128
129void InvalidatedIteratorChecker::reportBug(const StringRef &Message,
130                                           const SVal &Val, CheckerContext &C,
131                                           ExplodedNode *ErrNode) const {
132  auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
133                                                    Message, ErrNode);
134  R->markInteresting(Val);
135  C.emitReport(std::move(R));
136}
137
138void ento::registerInvalidatedIteratorChecker(CheckerManager &mgr) {
139  mgr.registerChecker<InvalidatedIteratorChecker>();
140}
141
142bool ento::shouldRegisterInvalidatedIteratorChecker(const CheckerManager &mgr) {
143  return true;
144}
145