clang-tools-extra/clang-tidy/bugprone/TooSmallLoopVariableCheck.cpp

   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