A new clang-tidy module to find calls to `std::swap`, and change them to use ADL

[mclow.lists]

Summary

Motivation: LLVM has many overloads of std::swap for its own types. This is technically forbidden by the standard, but is pervasive in the LLVM code base. The correct fix for this is to put them in the same namespace as the thing that they are swapping - but do do this, we have to find (and fix) all the places where we call std::swap explicitly, and let ADL do the finding instead.

The basic transform is:

std::swap(x, y) --> { using std::swap; swap(x, y); }

It would be better if the checking for builtin types and pointers were in the matcher instead of the code.

Thanks to Manuel and Aaron for helping with this

[mclow.lists]

Also, even though the --fix done by the tool is (almost) correct, the display of the fixit hint by clang is really confusing, even wrong

[mclow.lists]

Suggestions from @AaronBallman; now does the substitution correctly, and passes the tests.

Note: The diagnostics that clang emits are still whacko.

[LegalizeAdulthood]

I'm wondering if there isn't an existing module that would be a good fit for this check. Why not in the modernize module?

[rsmith]

In D15121#300033, @LegalizeAdulthood wrote:

I'm wondering if there isn't an existing module that would be a good fit for this check. Why not in the modernize module?

This isn't really modernization, it's a bug fix. ADL has always been the right way to find swap.

clang-tidy/misc/StdSwapCheck.cpp

25

Is there somewhere more central where this can live?

68

I think the two callee checks can be folded into one. Can you put the check that the namespace name is "std" in here too?

68

Ignoring parens here will lead to your fixit not working. Instead of trying to replace the "std::" with "{ using std::swap; ", maybe it'd be better and safer to replace the entire callee with "{ using std::swap; swap"?

78

Presumably this should also be checking that the parent of nsNode is the translation unit; we're not looking for a std nested within some other namespace here.

79–83

These lines seem underindented.

85–92

This will do bad things if the std::swap is not at the start of the enclosing statement (or if there is no enclosing statement).

docs/clang-tidy/checks/list.rst

35

Why is it called StdSwap here and std-swap below?

docs/clang-tidy/checks/misc-StdSwap.rst

6 ↗

(On Diff #41559)

practices -> practice
ADL lookup -> ADL / argument dependent lookup / argument dependent name lookup
swap -> swap
std -> std
"using" statement -> using declaration

14 ↗

(On Diff #41559)

brackets -> braces [the term "brackets" is ambiguous and implies different things in different dialects]

[aaron.ballman]

clang-tidy/misc/StdSwapCheck.cpp

25

If it is useful to multiple checkers, it could live in clangTidyUtils, or were you thinking of something more general for clang itself?

87

Can we get an && message in here as to what is being asserted?

90

I wonder if there is a way to guard against code like:

SomeStruct S1, S2;

if (something) {  std::swap(S1, S2); }

from becoming:

SomeStruct S1, S2;

if (something) {{ using std::swap; swap(S3, S4); }}

Also, should the fixit be suppressed under some circumstances?

// Is the replacement always safe for all macro expansions?
#define SWAP(a, b) std::swap(a, b)

// I should probably be punished for considering this code
for (;;std::swap(a, b)) ;
if (std::swap(a, b), (bool)a) ;

clang-tidy/misc/StdSwapCheck.h

19

Can this FIXME be fixed? ;-)

docs/clang-tidy/checks/misc-StdSwap.rst

1 ↗

(On Diff #41559)

This is incorrect, as is the file name (at least, compared to the comments in StdSwapCheck.h. Can this (and the file) be renamed to misc-std-swap instead?

test/clang-tidy/misc-StdSwap.cpp

4

It would be good to not have the #include <utility> here -- for instance, I think that this test will fail on Windows with MSVC if the only MSVC STL headers that can be found are from VS 2015 because there's no -fms-compatibility-version=19 option being used.

62

It would also be good to have a test that checks bar::std::swap(a, b) doesn't get flagged.

[mclow.lists]

Fixed all the simple things that people commented on.

clang-tidy/misc/StdSwapCheck.cpp

25

I'd love to have this in a library somewhere; I found a discussion about this from a year ago; Manuel seemed to think that it was a good idea, but nothing apparently came of that. I lifted this code from llvm/tools/clang/lib/ARCMigrate/Transforms.cpp

test/clang-tidy/misc-StdSwap.cpp

4

The reason that <utility> is included here is that that is where swap is declared.

[klimek]

clang-tidy/misc/StdSwapCheck.cpp

26

We should put that somewhere into Tooling/Core. Adding Benjamin who is our master of Yaks :D

[aaron.ballman]

clang-tidy/misc/StdSwapCheck.cpp

87

Extra space at the end of the assert before the closing paren.

clang-tidy/misc/StdSwapCheck.h

20

Strange indentation on the second line of the comment.

test/clang-tidy/misc-StdSwap.cpp

5

The reason that <utility> is included here is that that is where swap is declared.

The usual approach we take in our tests is to declare the STL functionality inside of the source file being tested. For instance, see misc-move-constructor-init.cpp. Another approach, if you require the declaration to be in a header file (which you don't appear to from the checker) is to create a local test file and #include it with "header" instead of <header>. Relying on whatever STL happens to be found by header search logic makes the tests highly fragile (and bots will happily chirp at you when you do this).

[mclow.lists]

clang-tidy/misc/StdSwapCheck.cpp

69

I believe that if you do that, you lose the arguments as well.

std::swap(x,y);  -> { using ::std::swap; swap; }

clang-tidy/misc/StdSwapCheck.h

20

I like that indentation :-)
It indicates that this is a continuation of the previous line.

[mclow.lists]

More tests; incorporated some of the suggestions for making sure we don't step on other people's namespaces named std.

[mclow.lists]

Richard clued me in to the cool method isStdNamespace(), which made the code simpler.

[dblaikie]

(tangential: Should we just have a utility function llvm::adl_swap that we
could use everywhere rather than having to write two lines for every
caller? (& have a variant of this check that knows to suggest that in
LLVM?))

[mclow.lists]

I ran this on LLVM + clang, and it changed calls in 61 files. The changed LLVM codebase compiled successfully, and passed all the tests.

Re: @dblaikie's comment, I'd rather call such a beast llvm::swap, and it would have to go into a header file that everyone already includes.

[alexfh]

Found this accidentally, since I don't read all of cfe-commits normally. Would be nice if you could add me to reviewers on clang-tidy-related patches. Thanks!

In D15121#300837, @dblaikie wrote:

(tangential: Should we just have a utility function llvm::adl_swap that we
could use everywhere rather than having to write two lines for every
caller? (& have a variant of this check that knows to suggest that in
LLVM?))

FWIW, if this seems to be useful for other codebases, the name of this function could be made configurable (together with the header this function comes from - clang-tidy checks can use clang::tidy::IncludeInserter to insert includes in a proper way).

[mclow.lists]

ping?

[aaron.ballman]

I notice there are a few other comments from reviewers that have not been addressed -- is there a newer version of the patch that hasn't been uploaded yet, or are you looking for further information on some of the comments?

clang-tidy/misc/StdSwapCheck.cpp

27

We should put that somewhere into Tooling/Core. Adding Benjamin who is our master of Yaks :D

At the very least, this could live in clangTidyUtils, possibly in LexerUtils.h.

66

Please remove commented out code.

78

Please remove commented-out code (here and elsewhere).

clang-tidy/misc/StdSwapCheck.h

21

I like that indentation :-)
It indicates that this is a continuation of the previous line.

It's not the style of commenting that we use in the rest of the project, however.

[Prazek]

test/clang-tidy/misc-StdSwap.cpp

8–12

template thing

clang-tidy/misc/CMakeLists.txt

   NonCopyableObjects.cpp
   SizeofContainerCheck.cpp
   StaticAssertCheck.cpp
+  StdSwapCheck.cpp
   SwappedArgumentsCheck.cpp
   ThrowByValueCatchByReferenceCheck.cpp
   UndelegatedConstructor.cpp

clang-tidy/misc/MiscTidyModule.cpp

 #include "NonCopyableObjects.h"
 #include "SizeofContainerCheck.h"
 #include "StaticAssertCheck.h"
+#include "StdSwapCheck.h"
 #include "SwappedArgumentsCheck.h"
 #include "ThrowByValueCatchByReferenceCheck.h"
 #include "UndelegatedConstructor.h"

     CheckFactories.registerCheck<SizeofContainerCheck>("misc-sizeof-container");
     CheckFactories.registerCheck<StaticAssertCheck>(
         "misc-static-assert");
+    CheckFactories.registerCheck<StdSwapCheck>(
+        "misc-std-swap");
     CheckFactories.registerCheck<SwappedArgumentsCheck>(
         "misc-swapped-arguments");
     CheckFactories.registerCheck<ThrowByValueCatchByReferenceCheck>(

clang-tidy/misc/StdSwapCheck.h

+//===--- StdSwapCheck.h - clang-tidy-----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_STD_SWAP_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_STD_SWAP_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+
+/// A checker that finds ns-qualified calls to std::swap, and replaces them
+///    with calls that use ADL instead.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-std-swap.html
+class StdSwapCheck : public ClangTidyCheck {
+public:
+  StdSwapCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_STD_SWAP_H
+

clang-tidy/misc/StdSwapCheck.cpp

+//===--- StdSwapCheck.cpp - clang-tidy-------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "StdSwapCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Lex/Lexer.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+
+/// \brief \arg Loc is the end of a statement range. This returns the location
+/// of the semicolon following the statement.
+/// If no semicolon is found or the location is inside a macro, the returned
+/// source location will be invalid.
+static SourceLocation findSemiAfterLocation(SourceLocation loc,
+                                            ASTContext &Ctx,
+                                            bool IsDecl) {
+  SourceManager &SM = Ctx.getSourceManager();
+  if (loc.isMacroID()) {
+    if (!Lexer::isAtEndOfMacroExpansion(loc, SM, Ctx.getLangOpts(), &loc))
+      return SourceLocation();
+  }
+  loc = Lexer::getLocForEndOfToken(loc, /*Offset=*/0, SM, Ctx.getLangOpts());
+
+  // Break down the source location.
+  std::pair<FileID, unsigned> locInfo = SM.getDecomposedLoc(loc);
+
+  // Try to load the file buffer.
+  bool invalidTemp = false;
+  StringRef file = SM.getBufferData(locInfo.first, &invalidTemp);
+  if (invalidTemp)
+    return SourceLocation();
+
+  const char *tokenBegin = file.data() + locInfo.second;
+
+  // Lex from the start of the given location.
+  Lexer lexer(SM.getLocForStartOfFile(locInfo.first),
+              Ctx.getLangOpts(),
+              file.begin(), tokenBegin, file.end());
+  Token tok;
+  lexer.LexFromRawLexer(tok);
+  if (tok.isNot(tok::semi)) {
+    if (!IsDecl)
+      return SourceLocation();
+    // Declaration may be followed with other tokens; such as an __attribute,
+    // before ending with a semicolon.
+    return findSemiAfterLocation(tok.getLocation(), Ctx, /*IsDecl*/true);
+  }
+
+  return tok.getLocation();
+}
+
+
+void StdSwapCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(
+//    callExpr(callee(functionDecl(hasName("swap"))),
+    callExpr(callee(namedDecl(hasName("swap"))),
+    callee(expr(ignoringParenImpCasts(declRefExpr(has(nestedNameSpecifierLoc().bind("namespace"))))))).bind("swap"),
+    this);
+}
+
+void StdSwapCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *nsNode = Result.Nodes.getNodeAs<NestedNameSpecifierLoc>("namespace");
+  const CharSourceRange nsSourceRange = CharSourceRange::getCharRange(nsNode->getSourceRange());
+  const std::string nsStr = clang::Lexer::getSourceText(nsSourceRange,
+                                *Result.SourceManager, Result.Context->getLangOpts());
+
+  bool isGlobalNS = NamespaceDecl::castToDeclContext(nsNode->getNestedNameSpecifier()->getAsNamespace())->getParent()->isTranslationUnit();
+  if (isGlobalNS && (nsStr == "std" || nsStr == "::std")) {
+  const auto *swapNode = Result.Nodes.getNodeAs<CallExpr>("swap");
+  QualType argType = swapNode->getArg(0)->getType();
+        
+  if (!argType->isAnyPointerType() && !argType->isBuiltinType()) {
+    auto Diag = diag(nsNode->getBeginLoc(), "let the compiler find the right swap via ADL");
+
+      const CharSourceRange swapSourceRange = CharSourceRange::getCharRange(swapNode->getSourceRange());
+    const SourceLocation semiLoc = findSemiAfterLocation(swapSourceRange.getEnd(), *Result.Context, false);
+    assert(semiLoc != SourceLocation() && "Can't find the terminating semicolon");
+        
+//    SourceRange replaceRange{swapNode->getSourceRange()};
+    const SourceRange replaceRange{nsSourceRange.getBegin(), nsSourceRange.getEnd().getLocWithOffset(2)};
+    std::string usingText = std::string("{ using ") + nsStr + "::swap; swap";
+      Diag << FixItHint::CreateReplacement(replaceRange, usingText)
+           << FixItHint::CreateInsertion(semiLoc.getLocWithOffset(1), " }");
+    }
+  }
+}
+
+} // namespace tidy
+} // namespace clang
+

docs/clang-tidy/checks/list.rst

    misc-non-copyable-objects
    misc-sizeof-container
    misc-static-assert
+   misc-std-swap
    misc-swapped-arguments
    misc-throw-by-value-catch-by-reference
    misc-undelegated-constructor

docs/clang-tidy/checks/misc-std-swap.rst

+misc-std-swap
+============
+
+Adding an overload for `std:swap` (in the `std` namespace) is explicitly forbidden by the standard. 
+
+The best practice for implementing swap for user-defined data structures is to implement a non-member swap in the same namespace as the type. Then, when you wish to swap to values `x` and `y`, you call `swap(x,y)` without a namespace, and argument dependent lookup will find it. Unfortunately this will not work for types that have overloads of `swap` in namespace `std` (standard library types and primitive types). So you have to bring them into play with a `using` declaration.
+
+Instead of writing:
+> std::swap(x,y);
+
+you should write:
+> using std::swap; swap(x,y);
+
+This checker find this pattern and replaces it with the recommended usage; wrapping the call in a pair of braces to scope the using directive. For builtin types (such as `int` and `float`), as well as pointers, it leaves the calls to `std::swap` alone, because those are correct.
+
+FUTURE WORK: 
+
+Find overloads of `swap` in namespace std and put them in the correct namespace.
+

test/clang-tidy/misc-StdSwap.cpp

+// RUN: %check_clang_tidy %s misc-std-swap %t
+
+namespace std {
+  template <typename T> void swap(T&, T&) {}
+  }
+
+// FIXME: Add something that triggers the check here.
+// FIXME: Verify the applied fix.
+//   * Make the CHECK patterns specific enough and try to make verified lines
+//     unique to avoid incorrect matches.
+//   * Use {{}} for regular expressions.
+
+// Bad code; don't overload in namespace std
+struct S1 { int x; };
+namespace std { void swap(S1& x, S1 &y) { swap(x.x, y.x); } };
+
+// Swap in namespace with type
+namespace foo { struct S2 { int i; }; void swap(S2& x, S2& y) {std::swap(x.i, y.i); } }
+
+// Swap in namespace.
+namespace bar {
+  struct S3 { int i; };
+  void swap(int&, int&) {}
+  namespace std {
+    void swap(S3& x, S3& y) { ::std::swap(x.i, y.i); }
+  }
+}
+
+void test0()
+{
+  S1 i,j;
+  std::swap(i,j);
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: let the compiler find the right swap via ADL
+  // CHECK-FIXES: { using std::swap; swap(i,j); }
+}
+
+void test1(bool b)
+{
+  foo::S2 x,y;
+  if ( b )
+    std::swap(x,y);
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: let the compiler find the right swap via ADL
+  // CHECK-FIXES: { using std::swap; swap(x,y); }
+}
+
+namespace baz {
+  void test2()
+  {
+    ::S1 i,j;
+    ::std::swap(i,j);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: let the compiler find the right swap via ADL
+    // CHECK-FIXES: { using ::std::swap; swap(i,j); }
+  }
+}
+
+void test_neg0()    // Swap two builtins
+{
+    {
+    int i,j;
+    std::swap(i,j);
+    }
+    {
+    float i,j;
+    std::swap(i,j);
+    }
+}
+
+void test_neg1()    // std::swap two pointers
+{
+    S1 *i, *j;
+    std::swap(i,j);
+}
+
+void test_neg2()  // Call a namespace-qualified swap that isn't "std::"
+{
+    {
+    int i,j;
+    bar::swap(i,j);
+    ::bar::swap(i,j);
+    }
+    {
+    bar::S3 i,j;
+    bar::std::swap(i,j);
+    ::bar::std::swap(i,j);
+    }
+}
+
+namespace bar {
+  void test_neg3()  // calling a non-global std::swap
+  {
+    S3 x,y;
+    std::swap(x,y);
+  }
+}