clang  14.0.0git
MismatchedIteratorChecker.cpp
Go to the documentation of this file.
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 
20 
21 
22 #include "Iterator.h"
23 
24 using namespace clang;
25 using namespace ento;
26 using namespace iterator;
27 
28 namespace {
29 
30 class 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 
46 public:
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 
56 MismatchedIteratorChecker::MismatchedIteratorChecker() {
57  MismatchedBugType.reset(
58  new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
59  /*SuppressOnSink=*/true));
60 }
61 
62 void 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 
192 void 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 
203 void 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 
239 void 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 
278 void 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 
290 void 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 
301 void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
302  mgr.registerChecker<MismatchedIteratorChecker>();
303 }
304 
305 bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
306  return true;
307 }
clang::BinaryOperator::isComparisonOp
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3902
clang::ento::iterator::isIteratorType
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
clang::index::SymbolRole::Call
@ Call
CallEvent.h
U
BuiltinCheckerRegistration.h
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3803
clang::ento::iterator::isComparisonOperator
bool isComparisonOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:71
clang::ento::iterator::getIteratorPosition
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
clang::ento::iterator::isEraseCall
bool isEraseCall(const FunctionDecl *Func)
Definition: Iterator.cpp:98
clang::SubstTemplateTypeParmType
Represents the result of substituting a type for a template type parameter.
Definition: Type.h:4844
BugType.h
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3852
Iterator.h
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
CheckerContext.h
Checker.h
clang::ento::iterator::isEraseAfterCall
bool isEraseAfterCall(const FunctionDecl *Func)
Definition: Iterator.cpp:112
clang
Definition: CalledOnceCheck.h:17
clang::ento::iterator::isEmplaceCall
bool isEmplaceCall(const FunctionDecl *Func)
Definition: Iterator.cpp:87
clang::BinaryOperator::getRHS
Expr * getRHS() const
Definition: Expr.h:3854
clang::ento::iterator::isInsertCall
bool isInsertCall(const FunctionDecl *Func)
Definition: Iterator.cpp:76