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(); 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 225