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