1 //===--- TooSmallLoopVariableCheck.cpp - clang-tidy -----------------------===//
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 #include "TooSmallLoopVariableCheck.h"
10 #include "clang/AST/ASTContext.h"
11 #include "clang/ASTMatchers/ASTMatchFinder.h"
12
13 using namespace clang::ast_matchers;
14
15 namespace clang {
16 namespace tidy {
17 namespace bugprone {
18
19 static constexpr llvm::StringLiteral LoopName =
20 llvm::StringLiteral("forLoopName");
21 static constexpr llvm::StringLiteral LoopVarName =
22 llvm::StringLiteral("loopVar");
23 static constexpr llvm::StringLiteral LoopVarCastName =
24 llvm::StringLiteral("loopVarCast");
25 static constexpr llvm::StringLiteral LoopUpperBoundName =
26 llvm::StringLiteral("loopUpperBound");
27 static constexpr llvm::StringLiteral LoopIncrementName =
28 llvm::StringLiteral("loopIncrement");
29
TooSmallLoopVariableCheck(StringRef Name,ClangTidyContext * Context)30 TooSmallLoopVariableCheck::TooSmallLoopVariableCheck(StringRef Name,
31 ClangTidyContext *Context)
32 : ClangTidyCheck(Name, Context),
33 MagnitudeBitsUpperLimit(Options.get("MagnitudeBitsUpperLimit", 16U)) {}
34
storeOptions(ClangTidyOptions::OptionMap & Opts)35 void TooSmallLoopVariableCheck::storeOptions(
36 ClangTidyOptions::OptionMap &Opts) {
37 Options.store(Opts, "MagnitudeBitsUpperLimit", MagnitudeBitsUpperLimit);
38 }
39
40 /// The matcher for loops with suspicious integer loop variable.
41 ///
42 /// In this general example, assuming 'j' and 'k' are of integral type:
43 /// \code
44 /// for (...; j < 3 + 2; ++k) { ... }
45 /// \endcode
46 /// The following string identifiers are bound to these parts of the AST:
47 /// LoopVarName: 'j' (as a VarDecl)
48 /// LoopVarCastName: 'j' (after implicit conversion)
49 /// LoopUpperBoundName: '3 + 2' (as an Expr)
50 /// LoopIncrementName: 'k' (as an Expr)
51 /// LoopName: The entire for loop (as a ForStmt)
52 ///
registerMatchers(MatchFinder * Finder)53 void TooSmallLoopVariableCheck::registerMatchers(MatchFinder *Finder) {
54 StatementMatcher LoopVarMatcher =
55 expr(
56 ignoringParenImpCasts(declRefExpr(to(varDecl(hasType(isInteger()))))))
57 .bind(LoopVarName);
58
59 // We need to catch only those comparisons which contain any integer cast.
60 StatementMatcher LoopVarConversionMatcher = traverse(
61 TK_AsIs, implicitCastExpr(hasImplicitDestinationType(isInteger()),
62 has(ignoringParenImpCasts(LoopVarMatcher)))
63 .bind(LoopVarCastName));
64
65 // We are interested in only those cases when the loop bound is a variable
66 // value (not const, enum, etc.).
67 StatementMatcher LoopBoundMatcher =
68 expr(ignoringParenImpCasts(allOf(hasType(isInteger()),
69 unless(integerLiteral()),
70 unless(hasType(isConstQualified())),
71 unless(hasType(enumType())))))
72 .bind(LoopUpperBoundName);
73
74 // We use the loop increment expression only to make sure we found the right
75 // loop variable.
76 StatementMatcher IncrementMatcher =
77 expr(ignoringParenImpCasts(hasType(isInteger()))).bind(LoopIncrementName);
78
79 Finder->addMatcher(
80 forStmt(
81 hasCondition(anyOf(
82 binaryOperator(hasOperatorName("<"),
83 hasLHS(LoopVarConversionMatcher),
84 hasRHS(LoopBoundMatcher)),
85 binaryOperator(hasOperatorName("<="),
86 hasLHS(LoopVarConversionMatcher),
87 hasRHS(LoopBoundMatcher)),
88 binaryOperator(hasOperatorName(">"), hasLHS(LoopBoundMatcher),
89 hasRHS(LoopVarConversionMatcher)),
90 binaryOperator(hasOperatorName(">="), hasLHS(LoopBoundMatcher),
91 hasRHS(LoopVarConversionMatcher)))),
92 hasIncrement(IncrementMatcher))
93 .bind(LoopName),
94 this);
95 }
96
97 /// Returns the magnitude bits of an integer type.
calcMagnitudeBits(const ASTContext & Context,const QualType & IntExprType)98 static unsigned calcMagnitudeBits(const ASTContext &Context,
99 const QualType &IntExprType) {
100 assert(IntExprType->isIntegerType());
101
102 return IntExprType->isUnsignedIntegerType()
103 ? Context.getIntWidth(IntExprType)
104 : Context.getIntWidth(IntExprType) - 1;
105 }
106
107 /// Calculate the upper bound expression's magnitude bits, but ignore
108 /// constant like values to reduce false positives.
calcUpperBoundMagnitudeBits(const ASTContext & Context,const Expr * UpperBound,const QualType & UpperBoundType)109 static unsigned calcUpperBoundMagnitudeBits(const ASTContext &Context,
110 const Expr *UpperBound,
111 const QualType &UpperBoundType) {
112 // Ignore casting caused by constant values inside a binary operator.
113 // We are interested in variable values' magnitude bits.
114 if (const auto *BinOperator = dyn_cast<BinaryOperator>(UpperBound)) {
115 const Expr *RHSE = BinOperator->getRHS()->IgnoreParenImpCasts();
116 const Expr *LHSE = BinOperator->getLHS()->IgnoreParenImpCasts();
117
118 QualType RHSEType = RHSE->getType();
119 QualType LHSEType = LHSE->getType();
120
121 if (!RHSEType->isIntegerType() || !LHSEType->isIntegerType())
122 return 0;
123
124 bool RHSEIsConstantValue = RHSEType->isEnumeralType() ||
125 RHSEType.isConstQualified() ||
126 isa<IntegerLiteral>(RHSE);
127 bool LHSEIsConstantValue = LHSEType->isEnumeralType() ||
128 LHSEType.isConstQualified() ||
129 isa<IntegerLiteral>(LHSE);
130
131 // Avoid false positives produced by two constant values.
132 if (RHSEIsConstantValue && LHSEIsConstantValue)
133 return 0;
134 if (RHSEIsConstantValue)
135 return calcMagnitudeBits(Context, LHSEType);
136 if (LHSEIsConstantValue)
137 return calcMagnitudeBits(Context, RHSEType);
138
139 return std::max(calcMagnitudeBits(Context, LHSEType),
140 calcMagnitudeBits(Context, RHSEType));
141 }
142
143 return calcMagnitudeBits(Context, UpperBoundType);
144 }
145
check(const MatchFinder::MatchResult & Result)146 void TooSmallLoopVariableCheck::check(const MatchFinder::MatchResult &Result) {
147 const auto *LoopVar = Result.Nodes.getNodeAs<Expr>(LoopVarName);
148 const auto *UpperBound =
149 Result.Nodes.getNodeAs<Expr>(LoopUpperBoundName)->IgnoreParenImpCasts();
150 const auto *LoopIncrement =
151 Result.Nodes.getNodeAs<Expr>(LoopIncrementName)->IgnoreParenImpCasts();
152
153 // We matched the loop variable incorrectly.
154 if (LoopVar->getType() != LoopIncrement->getType())
155 return;
156
157 QualType LoopVarType = LoopVar->getType();
158 QualType UpperBoundType = UpperBound->getType();
159
160 ASTContext &Context = *Result.Context;
161
162 unsigned LoopVarMagnitudeBits = calcMagnitudeBits(Context, LoopVarType);
163 unsigned UpperBoundMagnitudeBits =
164 calcUpperBoundMagnitudeBits(Context, UpperBound, UpperBoundType);
165
166 if (UpperBoundMagnitudeBits == 0)
167 return;
168
169 if (LoopVarMagnitudeBits > MagnitudeBitsUpperLimit)
170 return;
171
172 if (LoopVarMagnitudeBits < UpperBoundMagnitudeBits)
173 diag(LoopVar->getBeginLoc(), "loop variable has narrower type %0 than "
174 "iteration's upper bound %1")
175 << LoopVarType << UpperBoundType;
176 }
177
178 } // namespace bugprone
179 } // namespace tidy
180 } // namespace clang
181