Debian Codegraph @

src/checks/manuallevel/reserve-candidates.cpp

raw
1 /*
2 SPDX-FileCopyrightText: 2015 Klarälvdalens Datakonsult AB a KDAB Group company [email protected]
3 SPDX-FileContributor: Sérgio Martins <[email protected]>
4 SPDX-FileCopyrightText: 2015-2016 Sergio Martins <[email protected]>
5 SPDX-FileCopyrightText: 2024 Alexander Lohnau <[email protected]>
6
7 SPDX-License-Identifier: LGPL-2.0-or-later
8 */
9
10 #include "reserve-candidates.h"
11 #include "ClazyContext.h"
12 #include "ContextUtils.h"
13 #include "HierarchyUtils.h"
14 #include "LoopUtils.h"
15 #include "MacroUtils.h"
16 #include "QtUtils.h"
17 #include "StringUtils.h"
18 #include "Utils.h"
19 #include "clazy_stl.h"
20
21 #include <clang/AST/Decl.h>
22 #include <clang/AST/DeclCXX.h>
23 #include <clang/AST/Expr.h>
24 #include <clang/AST/ExprCXX.h>
25 #include <clang/AST/Stmt.h>
26 #include <clang/AST/StmtCXX.h>
27 #include <clang/AST/Type.h>
28 #include <clang/Basic/LLVM.h>
29 #include <clang/Basic/SourceLocation.h>
30 #include <clang/Basic/SourceManager.h>
31 #include <llvm/ADT/StringRef.h>
32 #include <llvm/Support/Casting.h>
33
34 #include <vector>
35
36 using namespace clang;
37
38 static bool paramIsSameTypeAs(const Type *paramType, CXXRecordDecl *classDecl)
39 {
40 if (!paramType || !classDecl) {
41 return false;
42 }
43
44 if (paramType->getAsCXXRecordDecl() == classDecl) {
45 return true;
46 }
47
48 const CXXRecordDecl *paramClassDecl = paramType->getPointeeCXXRecordDecl();
49 return paramClassDecl && paramClassDecl == classDecl;
50 }
51
52 bool ReserveCandidates::isCandidateMethod(CXXMethodDecl *methodDecl)
53 {
54 if (!methodDecl) {
55 return false;
56 }
57
58 CXXRecordDecl *classDecl = methodDecl->getParent();
59 if (!classDecl) {
60 return false;
61 }
62
63 if (!clazy::equalsAny(clazy::name(methodDecl).str(), {"append", "push_back", "push", "operator<<", "operator+="})) {
64 return false;
65 }
66
67 if (!clazy::isAReserveClass(classDecl, m_context->qtNamespace())) {
68 return false;
69 }
70
71 // Catch cases like: QList<T>::append(const QList<T> &), which don't make sense to reserve.
72 // In this case, the parameter has the same type of the class
73 ParmVarDecl *param = methodDecl->getParamDecl(0);
74 return !paramIsSameTypeAs(param->getType().getTypePtrOrNull(), classDecl);
75 }
76
77 bool ReserveCandidates::isCandidate(CallExpr *oper)
78 {
79 if (!oper) {
80 return false;
81 }
82
83 return isCandidateMethod(dyn_cast_or_null<CXXMethodDecl>(oper->getDirectCallee()));
84 }
85
86 bool ReserveCandidates::containerWasReserved(clang::ValueDecl *valueDecl) const
87 {
88 return valueDecl && clazy::contains(m_foundReserves, valueDecl);
89 }
90
91 bool ReserveCandidates::acceptsValueDecl(ValueDecl *valueDecl) const
92 {
93 // Rules:
94 // 1. The container variable must have been defined inside a function. Too many false positives otherwise.
95 // free to comment that out and go through the results, maybe you'll find something.
96
97 // 2. If we found at least one reserve call, lets not warn about it.
98
99 if (!valueDecl || isa<ParmVarDecl>(valueDecl) || containerWasReserved(valueDecl)) {
100 return false;
101 }
102
103 if (clazy::isValueDeclInFunctionContext(valueDecl)) {
104 return true;
105 }
106
107 // Actually, lets allow for some member variables containers if they are being used inside CTORs or DTORs
108 // Those functions are only called once, so it's OK. For other member functions it's dangerous and needs
109 // human inspection, if such member function would be called in a loop we would be constantly calling reserve
110 // and in that case the built-in exponential growth is better.
111
112 if (!m_context->lastMethodDecl || !(isa<CXXConstructorDecl>(m_context->lastMethodDecl) || isa<CXXDestructorDecl>(m_context->lastMethodDecl))) {
113 return false;
114 }
115
116 const CXXRecordDecl *record = Utils::isMemberVariable(valueDecl);
117 return record && m_context->lastMethodDecl->getParent() == record;
118 }
119
120 bool ReserveCandidates::isReserveCandidate(ValueDecl *valueDecl, Stmt *loopBody, CallExpr *callExpr) const
121 {
122 if (!acceptsValueDecl(valueDecl)) {
123 return false;
124 }
125
126 const bool isMemberVariable = Utils::isMemberVariable(valueDecl);
127 // We only want containers defined outside of the loop we're examining
128 if (!isMemberVariable && sm().isBeforeInSLocAddrSpace(loopBody->getBeginLoc(), valueDecl->getBeginLoc())) {
129 return false;
130 }
131
132 if (isInComplexLoop(callExpr, valueDecl->getBeginLoc(), isMemberVariable)) {
133 return false;
134 }
135
136 if (clazy::loopCanBeInterrupted(loopBody, m_context->sm, callExpr->getBeginLoc())) {
137 return false;
138 }
139
140 return true;
141 }
142
143 void ReserveCandidates::VisitStmt(clang::Stmt *stm)
144 {
145 if (registerReserveStatement(stm)) {
146 return;
147 }
148
149 auto *body = clazy::bodyFromLoop(stm);
150 if (!body) {
151 return;
152 }
153
154 const bool isForeach = clazy::isInMacro(astContext(), stm->getBeginLoc(), "Q_FOREACH");
155
156 // If the body is another loop, we have nesting, ignore it now since the inner loops will be visited soon.
157 if (isa<DoStmt>(body) || isa<WhileStmt>(body) || (!isForeach && isa<ForStmt>(body))) {
158 return;
159 }
160
161 // TODO: Search in both branches of the if statement
162 if (isa<IfStmt>(body)) {
163 return;
164 }
165
166 // Get the list of member calls and operator<< that are direct children of the loop statements
167 // If it's inside an if statement we don't care.
168 auto callExprs = clazy::getStatements<CallExpr>(body,
169 nullptr,
170 {},
171 /*depth=*/1,
172 /*includeParent=*/true,
173 clazy::IgnoreExprWithCleanups);
174
175 for (CallExpr *callExpr : callExprs) {
176 if (!isCandidate(callExpr)) {
177 continue;
178 }
179
180 ValueDecl *valueDecl = Utils::valueDeclForCallExpr(callExpr);
181 if (isReserveCandidate(valueDecl, body, callExpr)) {
182 emitWarning(callExpr->getSourceRange().getBegin(), "Reserve candidate");
183 }
184 }
185 }
186
187 // Catch existing reserves
188 bool ReserveCandidates::registerReserveStatement(Stmt *stm)
189 {
190 auto *memberCall = dyn_cast<CXXMemberCallExpr>(stm);
191 if (!memberCall) {
192 return false;
193 }
194
195 CXXMethodDecl *methodDecl = memberCall->getMethodDecl();
196 if (!methodDecl || clazy::name(methodDecl) != "reserve") {
197 return false;
198 }
199
200 CXXRecordDecl *decl = methodDecl->getParent();
201 if (!clazy::isAReserveClass(decl, m_context->qtNamespace())) {
202 return false;
203 }
204
205 ValueDecl *valueDecl = Utils::valueDeclForMemberCall(memberCall);
206 if (!valueDecl) {
207 return false;
208 }
209
210 if (!clazy::contains(m_foundReserves, valueDecl)) {
211 m_foundReserves.push_back(valueDecl);
212 }
213
214 return true;
215 }
216
217 bool ReserveCandidates::expressionIsComplex(clang::Expr *expr) const
218 {
219 if (!expr) {
220 return false;
221 }
222
223 std::vector<CallExpr *> callExprs;
224 clazy::getChilds<CallExpr>(expr, callExprs);
225
226 for (CallExpr *callExpr : callExprs) {
227 // In Qt5, this would have been a BinaryOperator. Ignore iterator unequality checks here
228 if (auto operatorCall = dyn_cast<CXXOperatorCallExpr>(callExpr)) {
229 std::string name = operatorCall->getDirectCallee()->getAsFunction()->getQualifiedNameAsString();
230 if (clazy::contains(name, "iterator::operator")) {
231 continue;
232 }
233 }
234
235 if (clazy::isJavaIterator(dyn_cast<CXXMemberCallExpr>(callExpr))) {
236 continue;
237 }
238
239 QualType qt = callExpr->getType();
240 const Type *t = qt.getTypePtrOrNull();
241 if (t && (!t->isIntegerType() || t->isBooleanType())) {
242 return true;
243 }
244 }
245
246 std::vector<ArraySubscriptExpr *> subscriptExprs;
247 clazy::getChilds<ArraySubscriptExpr>(expr, subscriptExprs);
248 if (!subscriptExprs.empty()) {
249 return true;
250 }
251
252 auto *binary = dyn_cast<BinaryOperator>(expr);
253 if (binary && binary->isAssignmentOp()) { // Filter things like for ( ...; ...; next = node->next)
254
255 Expr *rhs = binary->getRHS();
256 if (isa<MemberExpr>(rhs) || (isa<ImplicitCastExpr>(rhs) && dyn_cast_or_null<MemberExpr>(clazy::getFirstChildAtDepth(rhs, 1)))) {
257 return true;
258 }
259 }
260
261 // llvm::errs() << expr->getStmtClassName() << "\n";
262 return false;
263 }
264
265 bool ReserveCandidates::loopIsComplex(clang::Stmt *stm, bool &isLoop) const
266 {
267 isLoop = false;
268
269 if (auto *forstm = dyn_cast<ForStmt>(stm)) {
270 isLoop = true;
271 return !forstm->getCond() || !forstm->getInc() || expressionIsComplex(forstm->getCond()) || expressionIsComplex(forstm->getInc());
272 }
273
274 if (isa<CXXForRangeStmt>(stm)) {
275 isLoop = true;
276 return false;
277 }
278
279 if (dyn_cast<DoStmt>(stm) || dyn_cast<WhileStmt>(stm)) {
280 // Too many false-positives with while statements. Ignore it.
281 isLoop = true;
282 return true;
283 }
284
285 return false;
286 }
287
288 bool ReserveCandidates::isInComplexLoop(clang::Stmt *s, SourceLocation declLocation, bool isMemberVariable) const
289 {
290 if (!s || declLocation.isInvalid()) {
291 return false;
292 }
293
294 int forCount = 0;
295 int foreachCount = 0;
296
297 static std::vector<unsigned int> nonComplexOnesCache;
298 static std::vector<unsigned int> complexOnesCache;
299 auto rawLoc = s->getBeginLoc().getRawEncoding();
300
301 // For some reason we generate two warnings on some foreaches, so cache the ones we processed
302 // and return true so we don't trigger a warning
303 if (clazy::contains(nonComplexOnesCache, rawLoc) || clazy::contains(complexOnesCache, rawLoc)) {
304 return true;
305 }
306
307 Stmt *parent = s;
308 PresumedLoc lastForeachForStm;
309 while ((parent = clazy::parent(m_context->parentMap, parent))) {
310 const SourceLocation parentStart = parent->getBeginLoc();
311 if (!isMemberVariable && sm().isBeforeInSLocAddrSpace(parentStart, declLocation)) {
312 nonComplexOnesCache.push_back(rawLoc);
313 return false;
314 }
315
316 bool isLoop = false;
317 if (loopIsComplex(parent, isLoop)) {
318 complexOnesCache.push_back(rawLoc);
319 return true;
320 }
321
322 if (clazy::isInForeach(astContext(), parentStart)) {
323 auto ploc = sm().getPresumedLoc(parentStart);
324 if (Utils::presumedLocationsEqual(ploc, lastForeachForStm)) {
325 // Q_FOREACH comes in pairs, because each has two for statements inside, so ignore one when counting
326 } else {
327 foreachCount++;
328 lastForeachForStm = ploc;
329 }
330 } else {
331 if (isLoop) {
332 forCount++;
333 }
334 }
335
336 if (foreachCount > 1 || forCount > 1) { // two foreaches are almost always a false-positve
337 complexOnesCache.push_back(rawLoc);
338 return true;
339 }
340 }
341
342 nonComplexOnesCache.push_back(rawLoc);
343 return false;
344 }