1 //===-- MismatchedIteratorChecker.cpp -----------------------------*- C++ -*--//
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
7 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
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"
24 using namespace clang;
26 using namespace iterator;
30 class MismatchedIteratorChecker
31 : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
33 std::unique_ptr<BugType> MismatchedBugType;
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;
47 MismatchedIteratorChecker();
49 void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
50 void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
56 MismatchedIteratorChecker::MismatchedIteratorChecker() {
57 MismatchedBugType.reset(
58 new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
59 /*SuppressOnSink=*/true));
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());
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)
76 if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
77 !isIteratorType(Call.getArgExpr(0)->getType()))
80 verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
82 if (Call.getNumArgs() < 2)
85 if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
86 !isIteratorType(Call.getArgExpr(1)->getType()))
89 verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
91 } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
92 const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
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());
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));
111 } else if (isEmplaceCall(Func)) {
112 verifyMatch(C, Call.getArgSVal(0),
113 InstCall->getCXXThisVal().getAsRegion());
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)
120 const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
121 if (Ctr->getNumParams() < 2)
124 if (Ctr->getParamDecl(0)->getName() != "first" ||
125 Ctr->getParamDecl(1)->getName() != "last")
128 if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
129 !isIteratorType(Call.getArgExpr(1)->getType()))
132 verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
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.
143 // template<typename I1, typename I2>
144 // void f(I1 first1, I1 last1, I2 first2, I2 last2);
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.
150 const auto *Templ = Func->getPrimaryTemplate();
154 const auto *TParams = Templ->getTemplateParameters();
155 const auto *TArgs = Func->getTemplateSpecializationArgs();
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));
163 if (TPDecl->isParameterPack())
166 const auto TAType = TArgs->get(I).getAsType();
167 if (!isIteratorType(TAType))
170 SVal LHS = UndefinedVal();
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>();
180 ParamType->getReplacedParameter()->getDecl() != TPDecl)
183 LHS = Call.getArgSVal(J);
185 verifyMatch(C, LHS, Call.getArgSVal(J));
192 void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
193 CheckerContext &C) const {
194 if (!BO->isComparisonOp())
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);
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();
208 if (const auto *ContSym = Cont->getSymbolicBase()) {
209 if (isa<SymbolConjured>(ContSym->getSymbol()))
213 auto State = C.getState();
214 const auto *Pos = getIteratorPosition(State, Iter);
218 const auto *IterCont = Pos->getContainer();
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()))
229 if (IterCont != Cont) {
230 auto *N = C.generateNonFatalErrorNode(State);
234 reportBug("Container accessed using foreign iterator argument.",
239 void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
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);
248 const auto *IterCont1 = Pos1->getContainer();
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()))
259 const auto *Pos2 = getIteratorPosition(State, Iter2);
263 const auto *IterCont2 = Pos2->getContainer();
264 if (const auto *ContSym = IterCont2->getSymbolicBase()) {
265 if (isa<SymbolConjured>(ContSym->getSymbol()))
269 if (IterCont1 != IterCont2) {
270 auto *N = C.generateNonFatalErrorNode(State);
273 reportBug("Iterators of different containers used where the "
274 "same container is expected.", Iter1, Iter2, C, N);
278 void MismatchedIteratorChecker::reportBug(const StringRef &Message,
282 ExplodedNode *ErrNode) const {
283 auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
285 R->markInteresting(Val1);
286 R->markInteresting(Val2);
287 C.emitReport(std::move(R));
290 void MismatchedIteratorChecker::reportBug(const StringRef &Message,
291 const SVal &Val, const MemRegion *Reg,
293 ExplodedNode *ErrNode) const {
294 auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
296 R->markInteresting(Val);
297 R->markInteresting(Reg);
298 C.emitReport(std::move(R));
301 void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
302 mgr.registerChecker<MismatchedIteratorChecker>();
305 bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {