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 /// 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       traverse(ast_type_traits::TK_AsIs,
63                implicitCastExpr(hasImplicitDestinationType(isInteger()),
64                                 has(ignoringParenImpCasts(LoopVarMatcher)))
65                    .bind(LoopVarCastName));
66 
67   // We are interested in only those cases when the loop bound is a variable
68   // value (not const, enum, etc.).
69   StatementMatcher LoopBoundMatcher =
70       expr(ignoringParenImpCasts(allOf(hasType(isInteger()),
71                                        unless(integerLiteral()),
72                                        unless(hasType(isConstQualified())),
73                                        unless(hasType(enumType())))))
74           .bind(LoopUpperBoundName);
75 
76   // We use the loop increment expression only to make sure we found the right
77   // loop variable.
78   StatementMatcher IncrementMatcher =
79       expr(ignoringParenImpCasts(hasType(isInteger()))).bind(LoopIncrementName);
80 
81   Finder->addMatcher(
82       forStmt(
83           hasCondition(anyOf(
84               binaryOperator(hasOperatorName("<"),
85                              hasLHS(LoopVarConversionMatcher),
86                              hasRHS(LoopBoundMatcher)),
87               binaryOperator(hasOperatorName("<="),
88                              hasLHS(LoopVarConversionMatcher),
89                              hasRHS(LoopBoundMatcher)),
90               binaryOperator(hasOperatorName(">"), hasLHS(LoopBoundMatcher),
91                              hasRHS(LoopVarConversionMatcher)),
92               binaryOperator(hasOperatorName(">="), hasLHS(LoopBoundMatcher),
93                              hasRHS(LoopVarConversionMatcher)))),
94           hasIncrement(IncrementMatcher))
95           .bind(LoopName),
96       this);
97 }
98 
99 /// Returns the magnitude bits of an integer type.
100 static unsigned calcMagnitudeBits(const ASTContext &Context,
101                                   const QualType &IntExprType) {
102   assert(IntExprType->isIntegerType());
103 
104   return IntExprType->isUnsignedIntegerType()
105              ? Context.getIntWidth(IntExprType)
106              : Context.getIntWidth(IntExprType) - 1;
107 }
108 
109 /// Calculate the upper bound expression's magnitude bits, but ignore
110 /// constant like values to reduce false positives.
111 static unsigned calcUpperBoundMagnitudeBits(const ASTContext &Context,
112                                             const Expr *UpperBound,
113                                             const QualType &UpperBoundType) {
114   // Ignore casting caused by constant values inside a binary operator.
115   // We are interested in variable values' magnitude bits.
116   if (const auto *BinOperator = dyn_cast<BinaryOperator>(UpperBound)) {
117     const Expr *RHSE = BinOperator->getRHS()->IgnoreParenImpCasts();
118     const Expr *LHSE = BinOperator->getLHS()->IgnoreParenImpCasts();
119 
120     QualType RHSEType = RHSE->getType();
121     QualType LHSEType = LHSE->getType();
122 
123     if (!RHSEType->isIntegerType() || !LHSEType->isIntegerType())
124       return 0;
125 
126     bool RHSEIsConstantValue = RHSEType->isEnumeralType() ||
127                                RHSEType.isConstQualified() ||
128                                isa<IntegerLiteral>(RHSE);
129     bool LHSEIsConstantValue = LHSEType->isEnumeralType() ||
130                                LHSEType.isConstQualified() ||
131                                isa<IntegerLiteral>(LHSE);
132 
133     // Avoid false positives produced by two constant values.
134     if (RHSEIsConstantValue && LHSEIsConstantValue)
135       return 0;
136     if (RHSEIsConstantValue)
137       return calcMagnitudeBits(Context, LHSEType);
138     if (LHSEIsConstantValue)
139       return calcMagnitudeBits(Context, RHSEType);
140 
141     return std::max(calcMagnitudeBits(Context, LHSEType),
142                     calcMagnitudeBits(Context, RHSEType));
143   }
144 
145   return calcMagnitudeBits(Context, UpperBoundType);
146 }
147 
148 void TooSmallLoopVariableCheck::check(const MatchFinder::MatchResult &Result) {
149   const auto *LoopVar = Result.Nodes.getNodeAs<Expr>(LoopVarName);
150   const auto *UpperBound =
151       Result.Nodes.getNodeAs<Expr>(LoopUpperBoundName)->IgnoreParenImpCasts();
152   const auto *LoopIncrement =
153       Result.Nodes.getNodeAs<Expr>(LoopIncrementName)->IgnoreParenImpCasts();
154 
155   // We matched the loop variable incorrectly.
156   if (LoopVar->getType() != LoopIncrement->getType())
157     return;
158 
159   QualType LoopVarType = LoopVar->getType();
160   QualType UpperBoundType = UpperBound->getType();
161 
162   ASTContext &Context = *Result.Context;
163 
164   unsigned LoopVarMagnitudeBits = calcMagnitudeBits(Context, LoopVarType);
165   unsigned UpperBoundMagnitudeBits =
166       calcUpperBoundMagnitudeBits(Context, UpperBound, UpperBoundType);
167 
168   if (UpperBoundMagnitudeBits == 0)
169     return;
170 
171   if (LoopVarMagnitudeBits > MagnitudeBitsUpperLimit)
172     return;
173 
174   if (LoopVarMagnitudeBits < UpperBoundMagnitudeBits)
175     diag(LoopVar->getBeginLoc(), "loop variable has narrower type %0 than "
176                                  "iteration's upper bound %1")
177         << LoopVarType << UpperBoundType;
178 }
179 
180 } // namespace bugprone
181 } // namespace tidy
182 } // namespace clang
183