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