1//===-- MismatchedIteratorChecker.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 mistakenly applying a foreign iterator on a container
10// and for using iterators of two different containers in a context where
11// iterators of the same container should be used.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17#include "clang/StaticAnalyzer/Core/Checker.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20
21
22#include "Iterator.h"
23
24using namespace clang;
25using namespace ento;
26using namespace iterator;
27
28namespace {
29
30class MismatchedIteratorChecker
31  : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
32
33  std::unique_ptr<BugType> MismatchedBugType;
34
35  void verifyMatch(CheckerContext &C, const SVal &Iter,
36                   const MemRegion *Cont) const;
37  void verifyMatch(CheckerContext &C, const SVal &Iter1,
38                   const SVal &Iter2) const;
39  void reportBug(const StringRef &Message, const SVal &Val1,
40                 const SVal &Val2, CheckerContext &C,
41                 ExplodedNode *ErrNode) const;
42  void reportBug(const StringRef &Message, const SVal &Val,
43                 const MemRegion *Reg, CheckerContext &C,
44                 ExplodedNode *ErrNode) const;
45
46public:
47  MismatchedIteratorChecker();
48
49  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
50  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
51
52};
53
54} // namespace
55
56MismatchedIteratorChecker::MismatchedIteratorChecker() {
57  MismatchedBugType.reset(
58      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
59                  /*SuppressOnSink=*/true));
60}
61
62void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
63                                             CheckerContext &C) const {
64  // Check for iterator mismatches
65  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
66  if (!Func)
67    return;
68
69  if (Func->isOverloadedOperator() &&
70      isComparisonOperator(Func->getOverloadedOperator())) {
71    // Check for comparisons of iterators of different containers
72    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
73      if (Call.getNumArgs() < 1)
74        return;
75
76      if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
77          !isIteratorType(Call.getArgExpr(0)->getType()))
78        return;
79
80      verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
81    } else {
82      if (Call.getNumArgs() < 2)
83        return;
84
85      if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
86          !isIteratorType(Call.getArgExpr(1)->getType()))
87        return;
88
89      verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
90    }
91  } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
92    const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
93    if (!ContReg)
94      return;
95    // Check for erase, insert and emplace using iterator of another container
96    if (isEraseCall(Func) || isEraseAfterCall(Func)) {
97      verifyMatch(C, Call.getArgSVal(0),
98                  InstCall->getCXXThisVal().getAsRegion());
99      if (Call.getNumArgs() == 2) {
100        verifyMatch(C, Call.getArgSVal(1),
101                    InstCall->getCXXThisVal().getAsRegion());
102      }
103    } else if (isInsertCall(Func)) {
104      verifyMatch(C, Call.getArgSVal(0),
105                  InstCall->getCXXThisVal().getAsRegion());
106      if (Call.getNumArgs() == 3 &&
107          isIteratorType(Call.getArgExpr(1)->getType()) &&
108          isIteratorType(Call.getArgExpr(2)->getType())) {
109        verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
110      }
111    } else if (isEmplaceCall(Func)) {
112      verifyMatch(C, Call.getArgSVal(0),
113                  InstCall->getCXXThisVal().getAsRegion());
114    }
115  } else if (isa<CXXConstructorCall>(&Call)) {
116    // Check match of first-last iterator pair in a constructor of a container
117    if (Call.getNumArgs() < 2)
118      return;
119
120    const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
121    if (Ctr->getNumParams() < 2)
122      return;
123
124    if (Ctr->getParamDecl(0)->getName() != "first" ||
125        Ctr->getParamDecl(1)->getName() != "last")
126      return;
127
128    if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
129        !isIteratorType(Call.getArgExpr(1)->getType()))
130      return;
131
132    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
133  } else {
134    // The main purpose of iterators is to abstract away from different
135    // containers and provide a (maybe limited) uniform access to them.
136    // This implies that any correctly written template function that
137    // works on multiple containers using iterators takes different
138    // template parameters for different containers. So we can safely
139    // assume that passing iterators of different containers as arguments
140    // whose type replaces the same template parameter is a bug.
141    //
142    // Example:
143    // template<typename I1, typename I2>
144    // void f(I1 first1, I1 last1, I2 first2, I2 last2);
145    //
146    // In this case the first two arguments to f() must be iterators must belong
147    // to the same container and the last to also to the same container but
148    // not necessarily to the same as the first two.
149
150    const auto *Templ = Func->getPrimaryTemplate();
151    if (!Templ)
152      return;
153
154    const auto *TParams = Templ->getTemplateParameters();
155    const auto *TArgs = Func->getTemplateSpecializationArgs();
156
157    // Iterate over all the template parameters
158    for (size_t I = 0; I < TParams->size(); ++I) {
159      const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
160      if (!TPDecl)
161        continue;
162
163      if (TPDecl->isParameterPack())
164        continue;
165
166      const auto TAType = TArgs->get(I).getAsType();
167      if (!isIteratorType(TAType))
168        continue;
169
170      SVal LHS = UndefinedVal();
171
172      // For every template parameter which is an iterator type in the
173      // instantiation look for all functions' parameters' type by it and
174      // check whether they belong to the same container
175      for (auto J = 0U; J < Func->getNumParams(); ++J) {
176        const auto *Param = Func->getParamDecl(J);
177        const auto *ParamType =
178            Param->getType()->getAs<SubstTemplateTypeParmType>();
179        if (!ParamType ||
180            ParamType->getReplacedParameter()->getDecl() != TPDecl)
181          continue;
182        if (LHS.isUndef()) {
183          LHS = Call.getArgSVal(J);
184        } else {
185          verifyMatch(C, LHS, Call.getArgSVal(J));
186        }
187      }
188    }
189  }
190}
191
192void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
193                                             CheckerContext &C) const {
194  if (!BO->isComparisonOp())
195    return;
196
197  ProgramStateRef State = C.getState();
198  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
199  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
200  verifyMatch(C, LVal, RVal);
201}
202
203void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
204                                            const MemRegion *Cont) const {
205  // Verify match between a container and the container of an iterator
206  Cont = Cont->getMostDerivedObjectRegion();
207
208  if (const auto *ContSym = Cont->getSymbolicBase()) {
209    if (isa<SymbolConjured>(ContSym->getSymbol()))
210      return;
211  }
212
213  auto State = C.getState();
214  const auto *Pos = getIteratorPosition(State, Iter);
215  if (!Pos)
216    return;
217
218  const auto *IterCont = Pos->getContainer();
219
220  // Skip symbolic regions based on conjured symbols. Two conjured symbols
221  // may or may not be the same. For example, the same function can return
222  // the same or a different container but we get different conjured symbols
223  // for each call. This may cause false positives so omit them from the check.
224  if (const auto *ContSym = IterCont->getSymbolicBase()) {
225    if (isa<SymbolConjured>(ContSym->getSymbol()))
226      return;
227  }
228
229  if (IterCont != Cont) {
230    auto *N = C.generateNonFatalErrorNode(State);
231    if (!N) {
232      return;
233    }
234    reportBug("Container accessed using foreign iterator argument.",
235                        Iter, Cont, C, N);
236  }
237}
238
239void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
240                                            const SVal &Iter1,
241                                            const SVal &Iter2) const {
242  // Verify match between the containers of two iterators
243  auto State = C.getState();
244  const auto *Pos1 = getIteratorPosition(State, Iter1);
245  if (!Pos1)
246    return;
247
248  const auto *IterCont1 = Pos1->getContainer();
249
250  // Skip symbolic regions based on conjured symbols. Two conjured symbols
251  // may or may not be the same. For example, the same function can return
252  // the same or a different container but we get different conjured symbols
253  // for each call. This may cause false positives so omit them from the check.
254  if (const auto *ContSym = IterCont1->getSymbolicBase()) {
255    if (isa<SymbolConjured>(ContSym->getSymbol()))
256      return;
257  }
258
259  const auto *Pos2 = getIteratorPosition(State, Iter2);
260  if (!Pos2)
261    return;
262
263  const auto *IterCont2 = Pos2->getContainer();
264  if (const auto *ContSym = IterCont2->getSymbolicBase()) {
265    if (isa<SymbolConjured>(ContSym->getSymbol()))
266      return;
267  }
268
269  if (IterCont1 != IterCont2) {
270    auto *N = C.generateNonFatalErrorNode(State);
271    if (!N)
272      return;
273    reportBug("Iterators of different containers used where the "
274                        "same container is expected.", Iter1, Iter2, C, N);
275  }
276}
277
278void MismatchedIteratorChecker::reportBug(const StringRef &Message,
279                                          const SVal &Val1,
280                                          const SVal &Val2,
281                                          CheckerContext &C,
282                                          ExplodedNode *ErrNode) const {
283  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
284                                                    ErrNode);
285  R->markInteresting(Val1);
286  R->markInteresting(Val2);
287  C.emitReport(std::move(R));
288}
289
290void MismatchedIteratorChecker::reportBug(const StringRef &Message,
291                                          const SVal &Val, const MemRegion *Reg,
292                                          CheckerContext &C,
293                                          ExplodedNode *ErrNode) const {
294  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
295                                                    ErrNode);
296  R->markInteresting(Val);
297  R->markInteresting(Reg);
298  C.emitReport(std::move(R));
299}
300
301void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
302  mgr.registerChecker<MismatchedIteratorChecker>();
303}
304
305bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
306  return true;
307}
308