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