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