xref: /freebsd-src/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp (revision 647cbc5de815c5651677bf8582797f716ec7b48d)
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