Avoid repeated replacements on loop-convert check.

[angelgarcia]

Summary

The InitListExpr subtree is visited twice, this caused the check to do multiple replacements. Added a set to avoid it.

[alexfh]

clang-tidy/modernize/LoopConvertUtils.cpp

465

Do you need both Usages and UsageSet?

clang-tidy/modernize/LoopConvertUtils.h

211

Please use std::tie instead of std::make_tuple to avoid copies.

217

Looks like you can use std::tie here as well.

[angelgarcia]

Anyway, I just found that this needs a few more changes (it still does duplicated replacementes inside some macros, and I have to find out why), so don't bother with this for now.

clang-tidy/modernize/LoopConvertUtils.cpp

465

Yes, because SmallSet doesn't provide a way to iterate over its members.

clang-tidy/modernize/LoopConvertUtils.h

211

I used std::tie here at first, but it didn't work because it tries to bind a RValue to a non-const ref.

[angelgarcia]

I think this solves the duplication problem. And I think is clearer and cheaper than what I was trying to do before.

[klimek]

clang-tidy/modernize/LoopConvertUtils.cpp

465

There should be no need for a while() getExpansionLoc should always go to the most expanded location location.

clang-tidy/modernize/LoopConvertUtils.h

292–293

The result seems to be never used?

354

I don't think putting Set into the name helps. UsageLocations perhaps?

[angelgarcia]

Ok! I wasn't sure, and a while would be correct in both cases :)

[klimek]

clang-tidy/modernize/LoopConvertUtils.cpp

463–470

Now that I take a step back - shouldn't we go to the *spelling* location to deduplicate? The spelling location is the location that will be edited, after all.

[angelgarcia]

Yes, with SpellingLoc works as well, and it should be better.

[alexfh]

Looks good with a comment.

clang-tidy/modernize/LoopConvertUtils.h

223

You're right. I missed that getBegin()/getEnd() return values, not const references. Anyway, it's irrelevant now.

292

The "Returns true" part is wrong now.

[angelgarcia]

Wooops, solved.

[klimek]

Note that I think we should add a regression test that will work with the spelling loc but not with the expansion loc.
Something like:
#define A \

<loop1> \
<loop2>

A

clang-tidy/modernize/LoopConvertUtils.h

struct Usage {
   const Expr *Expression;
   bool IsArrow;
   SourceRange Range;
 
   explicit Usage(const Expr *E)
       : Expression(E), IsArrow(false), Range(Expression->getSourceRange()) {}
   Usage(const Expr *E, bool IsArrow, SourceRange Range)
       : Expression(E), IsArrow(IsArrow), Range(std::move(Range)) {}
+
+  // Comparators for llvm::SmallSet.
+  bool operator<(const Usage &Other) const {
+    return std::make_tuple(Expression, IsArrow, Range.getBegin(),
+                           Range.getEnd()) <
+           std::make_tuple(Other.Expression, Other.IsArrow,
+                           Other.Range.getBegin(), Other.Range.getEnd());
+  }
+  bool operator==(const Usage &Other) const {
+    return Expression == Other.Expression && IsArrow == Other.IsArrow &&
+           Range == Other.Range;
+  }
 };
 
 /// \brief A class to encapsulate lowering of the tool's confidence level.
 class Confidence {
 public:
   enum Level {
     // Transformations that are likely to change semantics.
     CL_Risky,
 
     // Transformations that might change semantics.
     CL_Reasonable,
 
public:
 
   /// \brief Add a set of components that we should consider relevant to the
   /// container.
   void addComponents(const ComponentVector &Components);
 
   /// \brief Accessor for Usages.
   const UsageResult &getUsages() const { return Usages; }
 
+  /// \brief Returns true and adds the Usage if it was not added before.
+  bool addUsage(const Usage &U);
+
   /// \brief Get the container indexed by IndexVar, if any.
   const Expr *getContainerIndexed() const { return ContainerExpr; }
 
   /// \brief Returns the statement declaring the variable created as an alias
   /// for the loop element, if any.
   const DeclStmt *getAliasDecl() const { return AliasDecl; }
 
   /// \brief Accessor for ConfidenceLevel.
private:
   /// The Expr which refers to the terminating condition for array-based loops.
   const Expr *ArrayBoundExpr;
   bool ContainerNeedsDereference;
 
   // Output member variables:
   /// A container which holds all usages of IndexVar as the index of
   /// ArraySubscriptExpressions.
   UsageResult Usages;
+  llvm::SmallSet<Usage, 8> UsageSet;
   bool OnlyUsedAsIndex;
   /// The DeclStmt for an alias to the container element.
   const DeclStmt *AliasDecl;
   Confidence ConfidenceLevel;
   /// \brief A list of expressions on which ContainerExpr depends.
   ///
   /// If any of these expressions are encountered outside of an acceptable usage
   /// of the loop element, lower our confidence level.

clang-tidy/modernize/LoopConvertUtils.cpp

 
 void ForLoopIndexUseVisitor::addComponent(const Expr *E) {
   FoldingSetNodeID ID;
   const Expr *Node = E->IgnoreParenImpCasts();
   Node->Profile(ID, *Context, true);
   DependentExprs.push_back(std::make_pair(Node, ID));
 }
 
+bool ForLoopIndexUseVisitor::addUsage(const Usage &U) {
+  if (UsageSet.insert(U).second) {
+    Usages.push_back(U);
+    return true;
+  }
+  return false;
+}
+
 /// \brief If the unary operator is a dereference of IndexVar, include it
 /// as a valid usage and prune the traversal.
 ///
 /// For example, if container.begin() and container.end() both return pointers
 /// to int, this makes sure that the initialization for `k` is not counted as an
 /// unconvertible use of the iterator `i`.
 /// \code
 ///   for (int *i = container.begin(), *e = container.end(); i != e; ++i) {
 ///     int k = *i + 2;
 ///   }
 /// \endcode
 bool ForLoopIndexUseVisitor::TraverseUnaryDeref(UnaryOperator *Uop) {
   // If we dereference an iterator that's actually a pointer, count the
   // occurrence.
   if (isDereferenceOfUop(Uop, IndexVar)) {
-    Usages.push_back(Usage(Uop));
+    addUsage(Usage(Uop));
     return true;
   }
 
   return VisitorBase::TraverseUnaryOperator(Uop);
 }
 
 /// \brief If the member expression is operator-> (overloaded or not) on
 /// IndexVar, include it as a valid usage and prune the traversal.
if (Obj && exprReferencesVariable(IndexVar, Obj)) {
     // FIXME: This works around not having the location of the arrow operator.
     // Consider adding OperatorLoc to MemberExpr?
     SourceLocation ArrowLoc = Lexer::getLocForEndOfToken(
         Base->getExprLoc(), 0, Context->getSourceManager(),
         Context->getLangOpts());
     // If something complicated is happening (i.e. the next token isn't an
     // arrow), give up on making this work.
     if (!ArrowLoc.isInvalid()) {
-      Usages.push_back(Usage(ResultExpr, /*IsArrow=*/true,
-                             SourceRange(Base->getExprLoc(), ArrowLoc)));
+      addUsage(Usage(ResultExpr, /*IsArrow=*/true,
       return true;
     }
   }
   return VisitorBase::TraverseMemberExpr(Member);
 }
 
 /// \brief If a member function call is the at() accessor on the container with
 /// IndexVar as the single argument, include it as a valid usage and prune
bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr(
   // We specifically allow an accessor named "at" to let STL in, though
   // this is restricted to pseudo-arrays by requiring a single, integer
   // argument.
   const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier();
   if (Ident && Ident->isStr("at") && MemberCall->getNumArgs() == 1) {
     if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar,
                                Member->getBase(), ContainerExpr,
                                ContainerNeedsDereference)) {
-      Usages.push_back(Usage(MemberCall));
+      addUsage(Usage(MemberCall));
       return true;
     }
   }
 
   if (containsExpr(Context, &DependentExprs, Member->getBase()))
     ConfidenceLevel.lowerTo(Confidence::CL_Risky);
 
   return VisitorBase::TraverseCXXMemberCallExpr(MemberCall);

 ///      int i = v[i] + 1;
 ///   }
 /// \endcode
 bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
     CXXOperatorCallExpr *OpCall) {
   switch (OpCall->getOperator()) {
   case OO_Star:
     if (isDereferenceOfOpCall(OpCall, IndexVar)) {
-      Usages.push_back(Usage(OpCall));
+      addUsage(Usage(OpCall));
       return true;
     }
     break;
 
   case OO_Subscript:
     if (OpCall->getNumArgs() != 2)
       break;
     if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar,
                                OpCall->getArg(0), ContainerExpr,
                                ContainerNeedsDereference)) {
-      Usages.push_back(Usage(OpCall));
+      addUsage(Usage(OpCall));
       return true;
     }
     break;
 
   default:
     break;
   }
   return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
if ((ContainerExpr &&
     // or this array doesn't match, mark this loop as unconvertible.
     OnlyUsedAsIndex = false;
     return VisitorBase::TraverseArraySubscriptExpr(E);
   }
 
   if (!ContainerExpr)
     ContainerExpr = Arr;
 
-  Usages.push_back(Usage(E));
+  addUsage(Usage(E));
   return true;
 }
 
 /// \brief If we encounter a reference to IndexVar in an unpruned branch of the
 /// traversal, mark this loop as unconvertible.
 ///
 /// This implements the whitelist for convertible loops: any usages of IndexVar
 /// not explicitly considered convertible by this traversal will be caught by

 ///       printf("%d\n", elem + k);
 ///     };
 ///     f(elem);
 ///   }
 /// \endcode
 bool ForLoopIndexUseVisitor::TraverseLambdaCapture(LambdaExpr *LE,
                                                    const LambdaCapture *C) {
   if (C->capturesVariable()) {
-    const VarDecl* VDecl = C->getCapturedVar();
+    const VarDecl *VDecl = C->getCapturedVar();
     if (areSameVariable(IndexVar, cast<ValueDecl>(VDecl))) {
       // FIXME: if the index is captured, it will count as an usage and the
       // alias (if any) won't work, because it is only used in case of having
       // exactly one usage.
-      Usages.push_back(Usage(nullptr, false, C->getLocation()));
+      addUsage(Usage(nullptr, false, C->getLocation()));
     }
   }
   return VisitorBase::TraverseLambdaCapture(LE, C);
 }
 
 /// \brief If we find that another variable is created just to refer to the loop
 /// element, note it for reuse as the loop variable.
 ///

test/clang-tidy/modernize-loop-convert-extra.cpp

for (dependent<int>::const_iterator I = dep.begin(), E = dep.end();
     auto H4 = [&]() { int R = *I + 1; };
 
   for (dependent<int>::const_iterator I = dep.begin(), E = dep.end();
        I != E; ++I)
     auto H5 = [=]() { int R = *I; };
 }
 
 } // namespace Lambdas
+
+namespace InitLists {
+
+struct D { int i; };
+struct E { D d; };
+int g(int b);
+
+void f() {
+  const unsigned N = 3;
+  int Array[N];
+
+  // Subtrees of InitListExpr are visited twice. Test that we do not do repeated
+  // replacements.
+  for (unsigned i = 0; i < N; ++i) {
+    int a{ Array[i] };
+    int b{ g(Array[i]) };
+    int c{ g( { Array[i] } ) };
+    D d{ { g( { Array[i] } ) } };
+    E e{ { { g( { Array[i] } ) } } };
+  }
+  // CHECK-MESSAGES: :[[@LINE-7]]:3: warning: use range-based for loop instead
+  // CHECK-FIXES: int a{ elem };
+  // CHECK-FIXES-NEXT: int b{ g(elem) };
+  // CHECK-FIXES-NEXT: int c{ g( { elem } ) };
+  // CHECK-FIXES-NEXT: D d{ { g( { elem } ) } };
+  // CHECK-FIXES-NEXT: E e{ { { g( { elem } ) } } };
+}
+
+} // namespace InitLists