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  const BugType InvalidatedBugType{this, "Iterator invalidated",
35                                   "Misuse of STL APIs"};
36
37  void verifyAccess(CheckerContext &C, SVal Val) const;
38  void reportBug(StringRef Message, SVal Val, CheckerContext &C,
39                 ExplodedNode *ErrNode) const;
40
41public:
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
52void InvalidatedIteratorChecker::checkPreCall(const CallEvent &Call,
53                                              CheckerContext &C) const {
54  // Check for access of invalidated position
55  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
56  if (!Func)
57    return;
58
59  if (Func->isOverloadedOperator() &&
60      isAccessOperator(Func->getOverloadedOperator())) {
61    // Check for any kind of access of invalidated iterator positions
62    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
63      verifyAccess(C, InstCall->getCXXThisVal());
64    } else {
65      verifyAccess(C, Call.getArgSVal(0));
66    }
67  }
68}
69
70void InvalidatedIteratorChecker::checkPreStmt(const UnaryOperator *UO,
71                                              CheckerContext &C) const {
72  if (isa<CXXThisExpr>(UO->getSubExpr()))
73    return;
74
75  ProgramStateRef State = C.getState();
76  UnaryOperatorKind OK = UO->getOpcode();
77  SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
78
79  if (isAccessOperator(OK)) {
80    verifyAccess(C, SubVal);
81  }
82}
83
84void InvalidatedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
85                                              CheckerContext &C) const {
86  ProgramStateRef State = C.getState();
87  BinaryOperatorKind OK = BO->getOpcode();
88  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
89
90  if (isAccessOperator(OK)) {
91    verifyAccess(C, LVal);
92  }
93}
94
95void InvalidatedIteratorChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
96                                              CheckerContext &C) const {
97  ProgramStateRef State = C.getState();
98  SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
99  verifyAccess(C, LVal);
100}
101
102void InvalidatedIteratorChecker::checkPreStmt(const MemberExpr *ME,
103                                              CheckerContext &C) const {
104  if (!ME->isArrow() || ME->isImplicitAccess())
105    return;
106
107  ProgramStateRef State = C.getState();
108  SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
109  verifyAccess(C, BaseVal);
110}
111
112void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C,
113                                              SVal Val) const {
114  auto State = C.getState();
115  const auto *Pos = getIteratorPosition(State, Val);
116  if (Pos && !Pos->isValid()) {
117    auto *N = C.generateErrorNode(State);
118    if (!N) {
119      return;
120    }
121    reportBug("Invalidated iterator accessed.", Val, C, N);
122  }
123}
124
125void InvalidatedIteratorChecker::reportBug(StringRef Message, SVal Val,
126                                           CheckerContext &C,
127                                           ExplodedNode *ErrNode) const {
128  auto R = std::make_unique<PathSensitiveBugReport>(InvalidatedBugType, Message,
129                                                    ErrNode);
130  R->markInteresting(Val);
131  C.emitReport(std::move(R));
132}
133
134void ento::registerInvalidatedIteratorChecker(CheckerManager &mgr) {
135  mgr.registerChecker<InvalidatedIteratorChecker>();
136}
137
138bool ento::shouldRegisterInvalidatedIteratorChecker(const CheckerManager &mgr) {
139  return true;
140}
141