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