clang 20.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 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>(Call.getDecl());
56 if (!Func)
57 return;
58
59 if (Func->isOverloadedOperator() &&
60 isComparisonOperator(Func->getOverloadedOperator())) {
61 // Check for comparisons of iterators of different containers
62 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
63 if (Call.getNumArgs() < 1)
64 return;
65
66 if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
67 !isIteratorType(Call.getArgExpr(0)->getType()))
68 return;
69
70 verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
71 } else {
72 if (Call.getNumArgs() < 2)
73 return;
74
75 if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
76 !isIteratorType(Call.getArgExpr(1)->getType()))
77 return;
78
79 verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
80 }
81 } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&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
87 verifyMatch(C, Call.getArgSVal(0),
88 InstCall->getCXXThisVal().getAsRegion());
89 if (Call.getNumArgs() == 2) {
90 verifyMatch(C, Call.getArgSVal(1),
91 InstCall->getCXXThisVal().getAsRegion());
92 }
93 } else if (isInsertCall(Func)) {
94 verifyMatch(C, Call.getArgSVal(0),
95 InstCall->getCXXThisVal().getAsRegion());
96 if (Call.getNumArgs() == 3 &&
97 isIteratorType(Call.getArgExpr(1)->getType()) &&
98 isIteratorType(Call.getArgExpr(2)->getType())) {
99 verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
100 }
101 } else if (isEmplaceCall(Func)) {
102 verifyMatch(C, Call.getArgSVal(0),
103 InstCall->getCXXThisVal().getAsRegion());
104 }
105 } else if (isa<CXXConstructorCall>(&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>(Call.getDecl());
111 if (Ctr->getNumParams() < 2)
112 return;
113
114 if (Ctr->getParamDecl(0)->getName() != "first" ||
115 Ctr->getParamDecl(1)->getName() != "last")
116 return;
117
118 if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
119 !isIteratorType(Call.getArgExpr(1)->getType()))
120 return;
121
122 verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(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>(TParams->getParam(I));
150 if (!TPDecl)
151 continue;
152
153 if (TPDecl->isParameterPack())
154 continue;
155
156 const auto TAType = TArgs->get(I).getAsType();
157 if (!isIteratorType(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(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(J);
176 } else {
177 verifyMatch(C, LHS, Call.getArgSVal(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(BO->getLHS(), C.getLocationContext());
191 SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
192 verifyMatch(C, LVal, 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>(ContSym->getSymbol()))
202 return;
203 }
204
205 auto State = C.getState();
206 const auto *Pos = getIteratorPosition(State, 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>(ContSym->getSymbol()))
218 return;
219 }
220
221 if (IterCont != Cont) {
222 auto *N = C.generateNonFatalErrorNode(State);
223 if (!N) {
224 return;
225 }
226 reportBug("Container accessed using foreign iterator argument.",
227 Iter, Cont, C, 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, 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>(ContSym->getSymbol()))
247 return;
248 }
249
250 const auto *Pos2 = getIteratorPosition(State, Iter2);
251 if (!Pos2)
252 return;
253
254 const auto *IterCont2 = Pos2->getContainer();
255 if (const auto *ContSym = IterCont2->getSymbolicBase()) {
256 if (isa<SymbolConjured>(ContSym->getSymbol()))
257 return;
258 }
259
260 if (IterCont1 != IterCont2) {
261 auto *N = C.generateNonFatalErrorNode(State);
262 if (!N)
263 return;
264 reportBug("Iterators of different containers used where the "
265 "same container is expected.", Iter1, Iter2, C, 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>(MismatchedBugType, Message,
273 ErrNode);
274 R->markInteresting(Val1);
275 R->markInteresting(Val2);
276 C.emitReport(std::move(R));
277}
278
279void MismatchedIteratorChecker::reportBug(StringRef Message, SVal Val,
280 const MemRegion *Reg,
282 ExplodedNode *ErrNode) const {
283 auto R = std::make_unique<PathSensitiveBugReport>(MismatchedBugType, Message,
284 ErrNode);
285 R->markInteresting(Val);
286 R->markInteresting(Reg);
287 C.emitReport(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}
const Decl * D
unsigned Iter
Definition: HTMLLogger.cpp:154
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3860
Expr * getLHS() const
Definition: Expr.h:3909
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3959
Expr * getRHS() const
Definition: Expr.h:3911
Represents the result of substituting a type for a template type parameter.
Definition: Type.h:6213
Declaration of a template type parameter.
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:153
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:97
const SymbolicRegion * getSymbolicBase() const
If this is a symbolic region, returns the region.
Definition: MemRegion.cpp:1412
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:1374
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
const IteratorPosition * getIteratorPosition(ProgramStateRef State, SVal Val)
Definition: Iterator.cpp:184
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
bool isEraseAfterCall(const FunctionDecl *Func)
Definition: Iterator.cpp:112
bool isComparisonOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:71
The JSON file list parser is used to communicate input to InstallAPI.