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