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