1480093f4SDimitry Andric //===-- MismatchedIteratorChecker.cpp -----------------------------*- C++ -*--//
2480093f4SDimitry Andric //
3480093f4SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4480093f4SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5480093f4SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6480093f4SDimitry Andric //
7480093f4SDimitry Andric //===----------------------------------------------------------------------===//
8480093f4SDimitry Andric //
9480093f4SDimitry Andric // Defines a checker for mistakenly applying a foreign iterator on a container
10480093f4SDimitry Andric // and for using iterators of two different containers in a context where
11480093f4SDimitry Andric // iterators of the same container should be used.
12480093f4SDimitry Andric //
13480093f4SDimitry Andric //===----------------------------------------------------------------------===//
14480093f4SDimitry Andric
15480093f4SDimitry Andric #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/Checker.h"
18480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
19480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20480093f4SDimitry Andric
21480093f4SDimitry Andric
22480093f4SDimitry Andric #include "Iterator.h"
23480093f4SDimitry Andric
24480093f4SDimitry Andric using namespace clang;
25480093f4SDimitry Andric using namespace ento;
26480093f4SDimitry Andric using namespace iterator;
27480093f4SDimitry Andric
28480093f4SDimitry Andric namespace {
29480093f4SDimitry Andric
30480093f4SDimitry Andric class MismatchedIteratorChecker
315ffd83dbSDimitry Andric : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
32480093f4SDimitry Andric
33*647cbc5dSDimitry Andric const BugType MismatchedBugType{this, "Iterator(s) mismatched",
34*647cbc5dSDimitry Andric "Misuse of STL APIs",
35*647cbc5dSDimitry Andric /*SuppressOnSink=*/true};
36480093f4SDimitry Andric
37*647cbc5dSDimitry Andric void verifyMatch(CheckerContext &C, SVal Iter, const MemRegion *Cont) const;
38*647cbc5dSDimitry Andric void verifyMatch(CheckerContext &C, SVal Iter1, SVal Iter2) const;
39*647cbc5dSDimitry Andric void reportBug(StringRef Message, SVal Val1, SVal Val2, CheckerContext &C,
40480093f4SDimitry Andric ExplodedNode *ErrNode) const;
41*647cbc5dSDimitry Andric void reportBug(StringRef Message, SVal Val, const MemRegion *Reg,
42*647cbc5dSDimitry Andric CheckerContext &C, ExplodedNode *ErrNode) const;
43480093f4SDimitry Andric
44480093f4SDimitry Andric public:
45480093f4SDimitry Andric void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
465ffd83dbSDimitry Andric void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
47480093f4SDimitry Andric
48480093f4SDimitry Andric };
49480093f4SDimitry Andric
50480093f4SDimitry Andric } // namespace
51480093f4SDimitry Andric
checkPreCall(const CallEvent & Call,CheckerContext & C) const52480093f4SDimitry Andric void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
53480093f4SDimitry Andric CheckerContext &C) const {
54480093f4SDimitry Andric // Check for iterator mismatches
55480093f4SDimitry Andric const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
56480093f4SDimitry Andric if (!Func)
57480093f4SDimitry Andric return;
58480093f4SDimitry Andric
59480093f4SDimitry Andric if (Func->isOverloadedOperator() &&
60480093f4SDimitry Andric isComparisonOperator(Func->getOverloadedOperator())) {
61480093f4SDimitry Andric // Check for comparisons of iterators of different containers
62480093f4SDimitry Andric if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
63480093f4SDimitry Andric if (Call.getNumArgs() < 1)
64480093f4SDimitry Andric return;
65480093f4SDimitry Andric
66480093f4SDimitry Andric if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
67480093f4SDimitry Andric !isIteratorType(Call.getArgExpr(0)->getType()))
68480093f4SDimitry Andric return;
69480093f4SDimitry Andric
70480093f4SDimitry Andric verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
71480093f4SDimitry Andric } else {
72480093f4SDimitry Andric if (Call.getNumArgs() < 2)
73480093f4SDimitry Andric return;
74480093f4SDimitry Andric
75480093f4SDimitry Andric if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
76480093f4SDimitry Andric !isIteratorType(Call.getArgExpr(1)->getType()))
77480093f4SDimitry Andric return;
78480093f4SDimitry Andric
79480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
80480093f4SDimitry Andric }
81480093f4SDimitry Andric } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
82480093f4SDimitry Andric const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
83480093f4SDimitry Andric if (!ContReg)
84480093f4SDimitry Andric return;
85480093f4SDimitry Andric // Check for erase, insert and emplace using iterator of another container
86480093f4SDimitry Andric if (isEraseCall(Func) || isEraseAfterCall(Func)) {
87480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(0),
88480093f4SDimitry Andric InstCall->getCXXThisVal().getAsRegion());
89480093f4SDimitry Andric if (Call.getNumArgs() == 2) {
90480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(1),
91480093f4SDimitry Andric InstCall->getCXXThisVal().getAsRegion());
92480093f4SDimitry Andric }
93480093f4SDimitry Andric } else if (isInsertCall(Func)) {
94480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(0),
95480093f4SDimitry Andric InstCall->getCXXThisVal().getAsRegion());
96480093f4SDimitry Andric if (Call.getNumArgs() == 3 &&
97480093f4SDimitry Andric isIteratorType(Call.getArgExpr(1)->getType()) &&
98480093f4SDimitry Andric isIteratorType(Call.getArgExpr(2)->getType())) {
99480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
100480093f4SDimitry Andric }
101480093f4SDimitry Andric } else if (isEmplaceCall(Func)) {
102480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(0),
103480093f4SDimitry Andric InstCall->getCXXThisVal().getAsRegion());
104480093f4SDimitry Andric }
105480093f4SDimitry Andric } else if (isa<CXXConstructorCall>(&Call)) {
106480093f4SDimitry Andric // Check match of first-last iterator pair in a constructor of a container
107480093f4SDimitry Andric if (Call.getNumArgs() < 2)
108480093f4SDimitry Andric return;
109480093f4SDimitry Andric
110480093f4SDimitry Andric const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
111480093f4SDimitry Andric if (Ctr->getNumParams() < 2)
112480093f4SDimitry Andric return;
113480093f4SDimitry Andric
114480093f4SDimitry Andric if (Ctr->getParamDecl(0)->getName() != "first" ||
115480093f4SDimitry Andric Ctr->getParamDecl(1)->getName() != "last")
116480093f4SDimitry Andric return;
117480093f4SDimitry Andric
118480093f4SDimitry Andric if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
119480093f4SDimitry Andric !isIteratorType(Call.getArgExpr(1)->getType()))
120480093f4SDimitry Andric return;
121480093f4SDimitry Andric
122480093f4SDimitry Andric verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
123480093f4SDimitry Andric } else {
124480093f4SDimitry Andric // The main purpose of iterators is to abstract away from different
125480093f4SDimitry Andric // containers and provide a (maybe limited) uniform access to them.
126480093f4SDimitry Andric // This implies that any correctly written template function that
127480093f4SDimitry Andric // works on multiple containers using iterators takes different
128480093f4SDimitry Andric // template parameters for different containers. So we can safely
129480093f4SDimitry Andric // assume that passing iterators of different containers as arguments
130480093f4SDimitry Andric // whose type replaces the same template parameter is a bug.
131480093f4SDimitry Andric //
132480093f4SDimitry Andric // Example:
133480093f4SDimitry Andric // template<typename I1, typename I2>
134480093f4SDimitry Andric // void f(I1 first1, I1 last1, I2 first2, I2 last2);
135480093f4SDimitry Andric //
136480093f4SDimitry Andric // In this case the first two arguments to f() must be iterators must belong
137480093f4SDimitry Andric // to the same container and the last to also to the same container but
138480093f4SDimitry Andric // not necessarily to the same as the first two.
139480093f4SDimitry Andric
140480093f4SDimitry Andric const auto *Templ = Func->getPrimaryTemplate();
141480093f4SDimitry Andric if (!Templ)
142480093f4SDimitry Andric return;
143480093f4SDimitry Andric
144480093f4SDimitry Andric const auto *TParams = Templ->getTemplateParameters();
145480093f4SDimitry Andric const auto *TArgs = Func->getTemplateSpecializationArgs();
146480093f4SDimitry Andric
147480093f4SDimitry Andric // Iterate over all the template parameters
148480093f4SDimitry Andric for (size_t I = 0; I < TParams->size(); ++I) {
149480093f4SDimitry Andric const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
150480093f4SDimitry Andric if (!TPDecl)
151480093f4SDimitry Andric continue;
152480093f4SDimitry Andric
153480093f4SDimitry Andric if (TPDecl->isParameterPack())
154480093f4SDimitry Andric continue;
155480093f4SDimitry Andric
156480093f4SDimitry Andric const auto TAType = TArgs->get(I).getAsType();
157480093f4SDimitry Andric if (!isIteratorType(TAType))
158480093f4SDimitry Andric continue;
159480093f4SDimitry Andric
160480093f4SDimitry Andric SVal LHS = UndefinedVal();
161480093f4SDimitry Andric
162480093f4SDimitry Andric // For every template parameter which is an iterator type in the
163480093f4SDimitry Andric // instantiation look for all functions' parameters' type by it and
164480093f4SDimitry Andric // check whether they belong to the same container
165480093f4SDimitry Andric for (auto J = 0U; J < Func->getNumParams(); ++J) {
166480093f4SDimitry Andric const auto *Param = Func->getParamDecl(J);
167480093f4SDimitry Andric const auto *ParamType =
168480093f4SDimitry Andric Param->getType()->getAs<SubstTemplateTypeParmType>();
169bdd1243dSDimitry Andric if (!ParamType)
170bdd1243dSDimitry Andric continue;
171bdd1243dSDimitry Andric const TemplateTypeParmDecl *D = ParamType->getReplacedParameter();
172bdd1243dSDimitry Andric if (D != TPDecl)
173480093f4SDimitry Andric continue;
174480093f4SDimitry Andric if (LHS.isUndef()) {
175480093f4SDimitry Andric LHS = Call.getArgSVal(J);
176480093f4SDimitry Andric } else {
177480093f4SDimitry Andric verifyMatch(C, LHS, Call.getArgSVal(J));
178480093f4SDimitry Andric }
179480093f4SDimitry Andric }
180480093f4SDimitry Andric }
181480093f4SDimitry Andric }
182480093f4SDimitry Andric }
183480093f4SDimitry Andric
checkPreStmt(const BinaryOperator * BO,CheckerContext & C) const1845ffd83dbSDimitry Andric void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
1855ffd83dbSDimitry Andric CheckerContext &C) const {
1865ffd83dbSDimitry Andric if (!BO->isComparisonOp())
1875ffd83dbSDimitry Andric return;
1885ffd83dbSDimitry Andric
1895ffd83dbSDimitry Andric ProgramStateRef State = C.getState();
1905ffd83dbSDimitry Andric SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
1915ffd83dbSDimitry Andric SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
1925ffd83dbSDimitry Andric verifyMatch(C, LVal, RVal);
1935ffd83dbSDimitry Andric }
1945ffd83dbSDimitry Andric
verifyMatch(CheckerContext & C,SVal Iter,const MemRegion * Cont) const195*647cbc5dSDimitry Andric void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter,
196480093f4SDimitry Andric const MemRegion *Cont) const {
197480093f4SDimitry Andric // Verify match between a container and the container of an iterator
198480093f4SDimitry Andric Cont = Cont->getMostDerivedObjectRegion();
199480093f4SDimitry Andric
200480093f4SDimitry Andric if (const auto *ContSym = Cont->getSymbolicBase()) {
201480093f4SDimitry Andric if (isa<SymbolConjured>(ContSym->getSymbol()))
202480093f4SDimitry Andric return;
203480093f4SDimitry Andric }
204480093f4SDimitry Andric
205480093f4SDimitry Andric auto State = C.getState();
206480093f4SDimitry Andric const auto *Pos = getIteratorPosition(State, Iter);
207480093f4SDimitry Andric if (!Pos)
208480093f4SDimitry Andric return;
209480093f4SDimitry Andric
210480093f4SDimitry Andric const auto *IterCont = Pos->getContainer();
211480093f4SDimitry Andric
212480093f4SDimitry Andric // Skip symbolic regions based on conjured symbols. Two conjured symbols
213480093f4SDimitry Andric // may or may not be the same. For example, the same function can return
214480093f4SDimitry Andric // the same or a different container but we get different conjured symbols
215480093f4SDimitry Andric // for each call. This may cause false positives so omit them from the check.
216480093f4SDimitry Andric if (const auto *ContSym = IterCont->getSymbolicBase()) {
217480093f4SDimitry Andric if (isa<SymbolConjured>(ContSym->getSymbol()))
218480093f4SDimitry Andric return;
219480093f4SDimitry Andric }
220480093f4SDimitry Andric
221480093f4SDimitry Andric if (IterCont != Cont) {
222480093f4SDimitry Andric auto *N = C.generateNonFatalErrorNode(State);
223480093f4SDimitry Andric if (!N) {
224480093f4SDimitry Andric return;
225480093f4SDimitry Andric }
226480093f4SDimitry Andric reportBug("Container accessed using foreign iterator argument.",
227480093f4SDimitry Andric Iter, Cont, C, N);
228480093f4SDimitry Andric }
229480093f4SDimitry Andric }
230480093f4SDimitry Andric
verifyMatch(CheckerContext & C,SVal Iter1,SVal Iter2) const231*647cbc5dSDimitry Andric void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter1,
232*647cbc5dSDimitry Andric SVal Iter2) const {
233480093f4SDimitry Andric // Verify match between the containers of two iterators
234480093f4SDimitry Andric auto State = C.getState();
235480093f4SDimitry Andric const auto *Pos1 = getIteratorPosition(State, Iter1);
236480093f4SDimitry Andric if (!Pos1)
237480093f4SDimitry Andric return;
238480093f4SDimitry Andric
239480093f4SDimitry Andric const auto *IterCont1 = Pos1->getContainer();
240480093f4SDimitry Andric
241480093f4SDimitry Andric // Skip symbolic regions based on conjured symbols. Two conjured symbols
242480093f4SDimitry Andric // may or may not be the same. For example, the same function can return
243480093f4SDimitry Andric // the same or a different container but we get different conjured symbols
244480093f4SDimitry Andric // for each call. This may cause false positives so omit them from the check.
245480093f4SDimitry Andric if (const auto *ContSym = IterCont1->getSymbolicBase()) {
246480093f4SDimitry Andric if (isa<SymbolConjured>(ContSym->getSymbol()))
247480093f4SDimitry Andric return;
248480093f4SDimitry Andric }
249480093f4SDimitry Andric
250480093f4SDimitry Andric const auto *Pos2 = getIteratorPosition(State, Iter2);
251480093f4SDimitry Andric if (!Pos2)
252480093f4SDimitry Andric return;
253480093f4SDimitry Andric
254480093f4SDimitry Andric const auto *IterCont2 = Pos2->getContainer();
255480093f4SDimitry Andric if (const auto *ContSym = IterCont2->getSymbolicBase()) {
256480093f4SDimitry Andric if (isa<SymbolConjured>(ContSym->getSymbol()))
257480093f4SDimitry Andric return;
258480093f4SDimitry Andric }
259480093f4SDimitry Andric
260480093f4SDimitry Andric if (IterCont1 != IterCont2) {
261480093f4SDimitry Andric auto *N = C.generateNonFatalErrorNode(State);
262480093f4SDimitry Andric if (!N)
263480093f4SDimitry Andric return;
264480093f4SDimitry Andric reportBug("Iterators of different containers used where the "
265480093f4SDimitry Andric "same container is expected.", Iter1, Iter2, C, N);
266480093f4SDimitry Andric }
267480093f4SDimitry Andric }
268480093f4SDimitry Andric
reportBug(StringRef Message,SVal Val1,SVal Val2,CheckerContext & C,ExplodedNode * ErrNode) const269*647cbc5dSDimitry Andric void MismatchedIteratorChecker::reportBug(StringRef Message, SVal Val1,
270*647cbc5dSDimitry Andric SVal Val2, CheckerContext &C,
271480093f4SDimitry Andric ExplodedNode *ErrNode) const {
272*647cbc5dSDimitry Andric auto R = std::make_unique<PathSensitiveBugReport>(MismatchedBugType, Message,
273480093f4SDimitry Andric ErrNode);
274480093f4SDimitry Andric R->markInteresting(Val1);
275480093f4SDimitry Andric R->markInteresting(Val2);
276480093f4SDimitry Andric C.emitReport(std::move(R));
277480093f4SDimitry Andric }
278480093f4SDimitry Andric
reportBug(StringRef Message,SVal Val,const MemRegion * Reg,CheckerContext & C,ExplodedNode * ErrNode) const279*647cbc5dSDimitry Andric void MismatchedIteratorChecker::reportBug(StringRef Message, SVal Val,
280*647cbc5dSDimitry Andric const MemRegion *Reg,
281480093f4SDimitry Andric CheckerContext &C,
282480093f4SDimitry Andric ExplodedNode *ErrNode) const {
283*647cbc5dSDimitry Andric auto R = std::make_unique<PathSensitiveBugReport>(MismatchedBugType, Message,
284480093f4SDimitry Andric ErrNode);
285480093f4SDimitry Andric R->markInteresting(Val);
286480093f4SDimitry Andric R->markInteresting(Reg);
287480093f4SDimitry Andric C.emitReport(std::move(R));
288480093f4SDimitry Andric }
289480093f4SDimitry Andric
registerMismatchedIteratorChecker(CheckerManager & mgr)290480093f4SDimitry Andric void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
291480093f4SDimitry Andric mgr.registerChecker<MismatchedIteratorChecker>();
292480093f4SDimitry Andric }
293480093f4SDimitry Andric
shouldRegisterMismatchedIteratorChecker(const CheckerManager & mgr)2945ffd83dbSDimitry Andric bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
295480093f4SDimitry Andric return true;
296480093f4SDimitry Andric }
297