[clang] New warning for for-loops where the iteration does not match the loop condition

[rtrieu]

Summary

This is a warning for when the increment/decrement in a for loop does not match the condition in the loop. If the condition has a relational operator, one operand can be deduced to be the larger value and the other operand the smaller value when the loop is run. For the loop to terminate, the smaller value needs to increase or the larger value needs to decrease, while the opposite will cause the loop to not terminate.

Correct:

for (...; x < y; ++x) {}
for (...; x < y; --y) {}

Incorrect:

for (...; x < y; --x) {}
for (...; x < y; ++y) {}

The warning comes with two attached notes. One is to flip the direction of the comparison (">" to "<", etc) and other is to change the increment decrement step ("--" to "++" or vice versa).

An exception is made for unsigned values, since some code uses the unsigned overflow/underflow characteristics.

[Eugene.Zelenko]

It's good question where this check belongs. There are two loop related checks in CLang-tidy: bugprone-infinite-loop and bugprone-too-small-loop-variable.

clang/lib/Sema/SemaStmt.cpp

1754

Please don't use auto unless type is spelled in same statement or iterator.

1760

Please use const auto *, because type is spelled in same statement.

1764

Please use const auto *, because type is spelled in same statement.

1780

Please use const auto *, because type is spelled in same statement.

Please run clang-format over patch.

1784

Please use const auto *, because type is spelled in same statement.

1813

Please don't use auto unless type is spelled in same statement or iterator.

[Eugene.Zelenko]

Check should also consider cases like: i += 2; i = i + 2; i -= 2; i = i - 2. Probably same with multiplications, divisions and shifts.

clang/include/clang/Basic/DiagnosticSemaKinds.td

def warn_variables_not_in_loop_body : Warning<
   "variable%select{s| %1|s %1 and %2|s %1, %2, and %3|s %1, %2, %3, and %4}0 "
   "used in loop condition not modified in loop body">,
   InGroup<ForLoopAnalysis>, DefaultIgnore;
 def warn_redundant_loop_iteration : Warning<
   "variable %0 is %select{decremented|incremented}1 both in the loop header "
   "and in the loop body">,
   InGroup<ForLoopAnalysis>, DefaultIgnore;
 def note_loop_iteration_here : Note<"%select{decremented|incremented}0 here">;
+def warn_loop_wrong_iteration : Warning<
+  "for-loop comparison has a %select{less|greater}0 than "
+  "%select{|or equal to }1operator (%2) but the loop step "
+  "%select{decrements|increments}3 the %select{left|right}4-hand side of the "
+  "comparison">, InGroup<ForLoopAnalysis>, DefaultIgnore;
+def note_loop_wrong_iteration_flip_condition : Note<
+  "flip comparison to %select{greater than|less than}0%select{| or equal to}1">;
+def note_loop_wrong_iteration_flip_step : Note<
+  "or use %select{increment|decrement}0">;
 
 def warn_duplicate_enum_values : Warning<
   "element %0 has been implicitly assigned %1 which another element has "
   "been assigned">, InGroup<DiagGroup<"duplicate-enum">>, DefaultIgnore;
 def note_duplicate_element : Note<"element %0 also has value %1">;
 
 // Absolute value functions
 def warn_unsigned_abs : Warning<

clang/lib/Sema/SemaStmt.cpp

void CheckForRedundantIteration(Sema &S, Expr *Third, Stmt *Body) {
     if (BreakContinueFinder(S, Body).ContinueFound()) return;
 
     S.Diag(LastDRE->getLocation(), diag::warn_redundant_loop_iteration)
          << LastDRE->getDecl() << LastIncrement;
     S.Diag(LoopDRE->getLocation(), diag::note_loop_iteration_here)
          << LoopIncrement;
   }
 
+  // Emit a warning when the increment is the opposite of what is implied
+  // by the condition.  For instance, the condition 'x < y' implies the correct
+  // increment is either '++x' or '--y' and will generate a warning with
+  // 'for (; x < y; --x)' or for '(; x < y; ++y)'
+  void CheckWrongIterationDirection(Sema &SemaRef, const Expr *Second,
+                                    const Expr *Third) {
+    if (!Second || !Third) return;
+
+    // Only check relational comparisons
+    const BinaryOperator *Cond = dyn_cast<BinaryOperator>(Second);
+    if (!Cond) return;
+    if (!Cond->isRelationalOp()) return;
+    const auto Opcode = Cond->getOpcode();
+
+    // Extract the operands of the comparison.  At least one needs to simple
+    // Decl.
+    const VarDecl *LeftOperand = nullptr;
+    const VarDecl *RightOperand = nullptr;
+    if (const DeclRefExpr *DRE =
+            dyn_cast<DeclRefExpr>(Cond->getLHS()->IgnoreParenImpCasts())) {
+      LeftOperand = dyn_cast<VarDecl>(DRE->getDecl());
+    }
+    if (const DeclRefExpr *DRE =
+            dyn_cast<DeclRefExpr>(Cond->getRHS()->IgnoreParenImpCasts())) {
+      RightOperand = dyn_cast<VarDecl>(DRE->getDecl());
+    }
+    if (!LeftOperand || !RightOperand) return;
+    if (LeftOperand == RightOperand) return;
+
+    // Unsigned types have well-defined overflow and underflow behaviors,
+    // so skip checking them.
+    if (LeftOperand->getType()->isUnsignedIntegerType() ||
+        RightOperand->getType()->isUnsignedIntegerType())
+      return;
+    const bool IsConditionGreaterThan = Opcode == BO_GT || Opcode == BO_GE;
+    const bool IsOrEqual = Opcode == BO_GE || Opcode == BO_LE;
+
+    // Check that the loop step is an increment/decrement operation.
+    const UnaryOperator* Increment = dyn_cast<UnaryOperator>(Third);
+    if (!Increment) return;
+    if (!Increment->isIncrementDecrementOp()) return;
+    const VarDecl *IncrementOperand = nullptr;
+    if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(
+            Increment->getSubExpr()->IgnoreParenImpCasts())) {
+      IncrementOperand = dyn_cast<VarDecl>(DRE->getDecl());
+    }
+    if (!IncrementOperand) return;
+    const bool IsIncrement = Increment->isIncrementOp();
+
+    const bool IsLHSInIncrement = IncrementOperand == LeftOperand;
+    const bool IsRHSInIncrement = IncrementOperand == RightOperand;
+
+    if (!IsLHSInIncrement && !IsRHSInIncrement) return;
+
+    // for (; x > ...; x--)
+    if (IsLHSInIncrement && IsConditionGreaterThan && !IsIncrement) return;
+    // for (; x < ...; x++)
+    if (IsLHSInIncrement && !IsConditionGreaterThan && IsIncrement) return;
+    // for (; ... > y; y++)
+    if (IsRHSInIncrement && IsConditionGreaterThan && IsIncrement) return;
+    // for (; ... < y; y--)
+    if (IsRHSInIncrement && !IsConditionGreaterThan && !IsIncrement) return;
+
+    // The actual warning.
+    const StringRef Operator = BinaryOperator::getOpcodeStr(Opcode);
+    SemaRef.Diag(Cond->getExprLoc(), diag::warn_loop_wrong_iteration)
+        << IsConditionGreaterThan << IsOrEqual << Operator << IsIncrement
+        << IsRHSInIncrement << Cond->getSourceRange()
+        << Increment->getSourceRange();
+
+    // One fix-it to reverse the condition operator.
+    const auto ReverseOpcode = BinaryOperator::reverseComparisonOp(Opcode);
+    const StringRef OperatorFixIt =
+        BinaryOperator::getOpcodeStr(ReverseOpcode);
+    SemaRef.Diag(Cond->getExprLoc(),
+                 diag::note_loop_wrong_iteration_flip_condition)
+        << IsConditionGreaterThan << IsOrEqual
+        << FixItHint::CreateReplacement(Cond->getOperatorLoc(), OperatorFixIt);
+
+    // Other fix-it to flip increment operator.
+    const StringRef IncrementFixIt = IsIncrement ? "--" : "++";
+    SemaRef.Diag(Increment->getExprLoc(),
+                 diag::note_loop_wrong_iteration_flip_step)
+        << IsIncrement
+        << FixItHint::CreateReplacement(Increment->getOperatorLoc(),
+                                        IncrementFixIt);
+  }
 } // end namespace
 
 
 void Sema::CheckBreakContinueBinding(Expr *E) {
   if (!E || getLangOpts().CPlusPlus)
     return;
   BreakContinueFinder BCFinder(*this, E);
   Scope *BreakParent = CurScope->getBreakParent();
StmtResult Sema::ActOnForStmt(SourceLocation ForLoc, SourceLocation LParenLoc,
 
   CheckBreakContinueBinding(Second.get().second);
   CheckBreakContinueBinding(third.get());
 
   if (!Second.get().first)
     CheckForLoopConditionalStatement(*this, Second.get().second, third.get(),
                                      Body);
   CheckForRedundantIteration(*this, third.get(), Body);
+  CheckWrongIterationDirection(*this, Second.get().second, third.get());
 
   if (Second.get().second &&
       !Diags.isIgnored(diag::warn_comma_operator,
                        Second.get().second->getExprLoc()))
     CommaVisitor(*this).Visit(Second.get().second);
 
   Expr *Third  = third.release().getAs<Expr>();
   if (isa<NullStmt>(Body))

clang/test/SemaCXX/warn-loop-analysis.cpp

void test10() {
   for (auto[i, j, k] = arr; i < j;) { }
   for (auto[i, j, k] = arr; i < j; ++arr[0]) { }
 
   int a = 1, b = 2;
   for (auto[i, j, k] = arr; a < b;) { }  // expected-warning{{variables 'a' and 'b' used in loop condition not modified in loop body}}
   for (auto[i, j, k] = arr; a < b; ++a) { }
 
   for (auto [i, j, k] = arr; i < a;) { }
-  for (auto[i, j, k] = arr; i < a; ++a) { }
+  for (auto[i, j, k] = arr; i < a; --a) { }
   for (auto[i, j, k] = arr; i < a; ++i) { }
   for (auto[i, j, k] = arr; i < a; ++arr[0]) { }
 };
+
+void test11(int a, int b, unsigned c, unsigned d) {
+  // Wrong increment
+  for (; a < b; --a) {}
+  // expected-warning@-1 {{for-loop comparison has a less than operator (<) but the loop step decrements the left-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to greater than}}
+  // expected-note@-3 {{or use increment}}
+  for (; a <= b; a--) {}
+  // expected-warning@-1 {{for-loop comparison has a less than or equal to operator (<=) but the loop step decrements the left-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to greater than or equal to}}
+  // expected-note@-3 {{or use increment}}
+  for (; a < b; ++b) {}
+  // expected-warning@-1 {{for-loop comparison has a less than operator (<) but the loop step increments the right-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to greater than}}
+  // expected-note@-3 {{or use decrement}}
+  for (; a <= b; b++) {}
+  // expected-warning@-1 {{for-loop comparison has a less than or equal to operator (<=) but the loop step increments the right-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to greater than or equal to}}
+  // expected-note@-3 {{or use decrement}}
+  for (; a > b; ++a) {}
+  // expected-warning@-1 {{for-loop comparison has a greater than operator (>) but the loop step increments the left-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to less than}}
+  // expected-note@-3 {{or use decrement}}
+  for (; a >= b; a++) {}
+  // expected-warning@-1 {{for-loop comparison has a greater than or equal to operator (>=) but the loop step increments the left-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to less than or equal to}}
+  // expected-note@-3 {{or use decrement}}
+  for (; a > b; --b) {}
+  // expected-warning@-1 {{for-loop comparison has a greater than operator (>) but the loop step decrements the right-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to less than}}
+  // expected-note@-3 {{or use increment}}
+  for (; a >= b; b--) {}
+  // expected-warning@-1 {{for-loop comparison has a greater than or equal to operator (>=) but the loop step decrements the right-hand side of the comparison}}
+  // expected-note@-2 {{flip comparison to less than or equal to}}
+  // expected-note@-3 {{or use increment}}
+
+  // Correct
+  for (; a < b; ++a) {}
+  for (; a <= b; a++) {}
+  for (; a < b; --b) {}
+  for (; a <= b; b--) {}
+  for (; a > b; --a) {}
+  for (; a >= b; a--) {}
+  for (; a > b; ++b) {}
+  for (; a >= b; b++) {}
+
+  // Unsigned underflow and overlow are well-defined.
+  for (; c < d; ++c) {}
+  for (; c < d; --c) {}
+  for (; c < d; d++) {}
+  for (; c < d; d--) {}
+
+  class vector {
+   public:
+    unsigned size() { return 1; };
+  };
+
+  vector v;
+  for (unsigned i = v.size() - 1; i < v.size(); --i) {
+    // Intentionally using an underflow to allow i to equal 0.
+  }
+}