clang 18.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
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
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 continue;
181 const TemplateTypeParmDecl *D = ParamType->getReplacedParameter();
182 if (D != TPDecl)
183 continue;
184 if (LHS.isUndef()) {
185 LHS = Call.getArgSVal(J);
186 } else {
187 verifyMatch(C, LHS, Call.getArgSVal(J));
188 }
189 }
190 }
191 }
192}
193
194void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
195 CheckerContext &C) const {
196 if (!BO->isComparisonOp())
197 return;
198
199 ProgramStateRef State = C.getState();
200 SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
201 SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
202 verifyMatch(C, LVal, RVal);
203}
204
205void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
206 const MemRegion *Cont) const {
207 // Verify match between a container and the container of an iterator
208 Cont = Cont->getMostDerivedObjectRegion();
209
210 if (const auto *ContSym = Cont->getSymbolicBase()) {
211 if (isa<SymbolConjured>(ContSym->getSymbol()))
212 return;
213 }
214
215 auto State = C.getState();
216 const auto *Pos = getIteratorPosition(State, Iter);
217 if (!Pos)
218 return;
219
220 const auto *IterCont = Pos->getContainer();
221
222 // Skip symbolic regions based on conjured symbols. Two conjured symbols
223 // may or may not be the same. For example, the same function can return
224 // the same or a different container but we get different conjured symbols
225 // for each call. This may cause false positives so omit them from the check.
226 if (const auto *ContSym = IterCont->getSymbolicBase()) {
227 if (isa<SymbolConjured>(ContSym->getSymbol()))
228 return;
229 }
230
231 if (IterCont != Cont) {
232 auto *N = C.generateNonFatalErrorNode(State);
233 if (!N) {
234 return;
235 }
236 reportBug("Container accessed using foreign iterator argument.",
237 Iter, Cont, C, N);
238 }
239}
240
241void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
242 const SVal &Iter1,
243 const SVal &Iter2) const {
244 // Verify match between the containers of two iterators
245 auto State = C.getState();
246 const auto *Pos1 = getIteratorPosition(State, Iter1);
247 if (!Pos1)
248 return;
249
250 const auto *IterCont1 = Pos1->getContainer();
251
252 // Skip symbolic regions based on conjured symbols. Two conjured symbols
253 // may or may not be the same. For example, the same function can return
254 // the same or a different container but we get different conjured symbols
255 // for each call. This may cause false positives so omit them from the check.
256 if (const auto *ContSym = IterCont1->getSymbolicBase()) {
257 if (isa<SymbolConjured>(ContSym->getSymbol()))
258 return;
259 }
260
261 const auto *Pos2 = getIteratorPosition(State, Iter2);
262 if (!Pos2)
263 return;
264
265 const auto *IterCont2 = Pos2->getContainer();
266 if (const auto *ContSym = IterCont2->getSymbolicBase()) {
267 if (isa<SymbolConjured>(ContSym->getSymbol()))
268 return;
269 }
270
271 if (IterCont1 != IterCont2) {
272 auto *N = C.generateNonFatalErrorNode(State);
273 if (!N)
274 return;
275 reportBug("Iterators of different containers used where the "
276 "same container is expected.", Iter1, Iter2, C, N);
277 }
278}
279
280void MismatchedIteratorChecker::reportBug(const StringRef &Message,
281 const SVal &Val1,
282 const SVal &Val2,
284 ExplodedNode *ErrNode) const {
285 auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
286 ErrNode);
287 R->markInteresting(Val1);
288 R->markInteresting(Val2);
289 C.emitReport(std::move(R));
290}
291
292void MismatchedIteratorChecker::reportBug(const StringRef &Message,
293 const SVal &Val, const MemRegion *Reg,
295 ExplodedNode *ErrNode) const {
296 auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
297 ErrNode);
298 R->markInteresting(Val);
299 R->markInteresting(Reg);
300 C.emitReport(std::move(R));
301}
302
303void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
304 mgr.registerChecker<MismatchedIteratorChecker>();
305}
306
307bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
308 return true;
309}
unsigned Iter
Definition: HTMLLogger.cpp:150
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3862
Expr * getLHS() const
Definition: Expr.h:3911
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3961
Expr * getRHS() const
Definition: Expr.h:3913
Represents the result of substituting a type for a template type parameter.
Definition: Type.h:5241
Declaration of a template type parameter.
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:152
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:96
const SymbolicRegion * getSymbolicBase() const
If this is a symbolic region, returns the region.
Definition: MemRegion.cpp:1393
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getMostDerivedObjectRegion() const
Recursively retrieve the region of the most derived class instance of regions of C++ base class insta...
Definition: MemRegion.cpp:1355
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:55
bool isUndef() const
Definition: SVals.h:104
bool isEraseCall(const FunctionDecl *Func)
Definition: Iterator.cpp:98
bool isInsertCall(const FunctionDecl *Func)
Definition: Iterator.cpp:76
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
bool isEmplaceCall(const FunctionDecl *Func)
Definition: Iterator.cpp:87
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
bool isEraseAfterCall(const FunctionDecl *Func)
Definition: Iterator.cpp:112
bool isComparisonOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:71