225 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "TooSmallLoopVariableCheck.h"10#include "clang/AST/ASTContext.h"11#include "clang/ASTMatchers/ASTMatchFinder.h"12 13using namespace clang::ast_matchers;14 15namespace clang::tidy::bugprone {16 17static constexpr llvm::StringLiteral LoopName =18 llvm::StringLiteral("forLoopName");19static constexpr llvm::StringLiteral LoopVarName =20 llvm::StringLiteral("loopVar");21static constexpr llvm::StringLiteral LoopVarCastName =22 llvm::StringLiteral("loopVarCast");23static constexpr llvm::StringLiteral LoopUpperBoundName =24 llvm::StringLiteral("loopUpperBound");25static constexpr llvm::StringLiteral LoopIncrementName =26 llvm::StringLiteral("loopIncrement");27 28namespace {29 30struct 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} // namespace45 46TooSmallLoopVariableCheck::TooSmallLoopVariableCheck(StringRef Name,47 ClangTidyContext *Context)48 : ClangTidyCheck(Name, Context),49 MagnitudeBitsUpperLimit(Options.get("MagnitudeBitsUpperLimit", 16U)) {}50 51void 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/// \code60/// for (...; j < 3 + 2; ++k) { ... }61/// \endcode62/// 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///69void TooSmallLoopVariableCheck::registerMatchers(MatchFinder *Finder) {70 const 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 const 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 variable83 // value (not const, enum, etc.).84 const 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 right96 // loop variable.97 const 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.119static MagnitudeBits calcMagnitudeBits(const ASTContext &Context,120 const QualType &IntExprType,121 const Expr *IntExpr) {122 assert(IntExprType->isIntegerType());123 124 const unsigned SignedBits = IntExprType->isUnsignedIntegerType() ? 0U : 1U;125 126 if (const auto *BitField = IntExpr->getSourceBitField()) {127 const unsigned BitFieldWidth = BitField->getBitWidthValue();128 return {BitFieldWidth - SignedBits, BitFieldWidth};129 }130 131 const unsigned IntWidth = Context.getIntWidth(IntExprType);132 return {IntWidth - SignedBits, 0U};133}134 135/// Calculate the upper bound expression's magnitude bits, but ignore136/// constant like values to reduce false positives.137static MagnitudeBits138calcUpperBoundMagnitudeBits(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 const QualType RHSEType = RHSE->getType();147 const QualType LHSEType = LHSE->getType();148 149 if (!RHSEType->isIntegerType() || !LHSEType->isIntegerType())150 return {};151 152 const bool RHSEIsConstantValue = RHSEType->isEnumeralType() ||153 RHSEType.isConstQualified() ||154 isa<IntegerLiteral>(RHSE);155 const 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 174static 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 185void 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 const 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::bugprone225