[clang-tidy] Add check performance-faster-string-find

[sbenza]

Summary

Add check performance-faster-string-find.
It replaces single character string literals to character literals in calls to string::find and friends.

[alexfh]

Awesome! See a few comments inline.

clang-tidy/performance/FasterStringFindCheck.cpp

51 ↗

(On Diff #44780)

Probably out of scope of this patch, but I wonder how many times hasName is still more effective than one matchesName? Maybe we should add a matchesName variant for unqualified names or hasName taking a list of strings?

57 ↗

(On Diff #44780)

const auto & would be slightly clearer.

75 ↗

(On Diff #44780)

The message might be confusing in some situations (e.g. macros). I think, it should at least mention what method (and maybe of what class) is in question, e.g. "std::string::find() called with a string literal consisting of a single character; consider using the more effective overload accepting a character".

clang-tidy/performance/FasterStringFindCheck.h

15 ↗

(On Diff #44780)

Sort includes, please.

test/clang-tidy/performance-faster-string-find.cpp

8 ↗

(On Diff #44780)

Should we move stubs to a common header(s)?

9 ↗

(On Diff #44780)

Did you mean const T *?

31 ↗

(On Diff #44780)

As usual, please add tests with templates and macros ;)

32 ↗

(On Diff #44780)

Please add tests for std::wstring, std::u16string and std::u32string. At the very least, we should ensure we don't break the code using them.

50 ↗

(On Diff #44780)

"Some other methods." maybe?

[aaron.ballman]

clang-tidy/performance/FasterStringFindCheck.cpp

25 ↗

(On Diff #44780)

It might be nice for this to be more tolerant of whitespace around the commas.

47 ↗

(On Diff #44780)

Can you also disable registration of these matches outside of C++ mode?

[alexfh]

clang-tidy/performance/FasterStringFindCheck.cpp

25 ↗

(On Diff #44780)

I don't see much value in this, since it's not someone will change frequently (I guess, once per codebase on average).

[aaron.ballman]

clang-tidy/performance/FasterStringFindCheck.cpp

25 ↗

(On Diff #44780)

I don't see much value in this, since it's not someone will change frequently (I guess, once per codebase on average).

Anything that's user-facing should be fault tolerant and sanitized for a better user experience.

[alexfh]

clang-tidy/performance/FasterStringFindCheck.cpp

25 ↗

(On Diff #44780)

I also don't feel strongly about this. Trimming all strings after splitting should be a trivial 2-line addition to this patch.

[sbenza]

Added template and macro tests.
Fixed warning message.

[sbenza]

clang-tidy/performance/FasterStringFindCheck.cpp

51 ↗

(On Diff #44780)

I have no idea how much more expensive is the regex engine.
It also makes the code harder to read.
I would totally be in favor of a variadic hasAnyName(). It is shorter and can be much faster to run.

75 ↗

(On Diff #44780)

Used unqualified function name instead.
The qualified name for find is std::basic_string<blah, blah, blah>::find, which might be distracting.

[sbenza]

Added support for non 'char' chars.

[aaron.ballman]

clang-tidy/performance/FasterStringFindCheck.cpp

29 ↗

(On Diff #44889)

I think hasName() will assert if given an empty string, so this should probably also guard against a class list like ",basic_string".

test/clang-tidy/performance-faster-string-find.cpp

9 ↗

(On Diff #44889)

Should we move stubs to a common header(s)?

Yes, please. However, that can be a separate patch that does something more comprehensive.

[sbenza]

More checks in argument parsing.

clang-tidy/performance/FasterStringFindCheck.cpp

29 ↗

(On Diff #44889)

Also changed the separator to be ';' instead of ','.
The latter could be part of a type name. Eg. Foo<A,B>::Bar

[aaron.ballman]

clang-tidy/performance/FasterStringFindCheck.cpp

30 ↗

(On Diff #44901)

Also changed the separator to be ';' instead of ','.
The latter could be part of a type name. Eg. Foo<A,B>::Bar

That's a great catch!

@alexfh -- do you think we should try to get our checkers to be consistent with their choice of list separators? Specifically, I am thinking about D16113. It seems like it would improve the user experience to not have to wonder "do I use comma, or semi colon, for this list?"

[hokein]

clang-tidy/performance/FasterStringFindCheck.h

25 ↗

(On Diff #44901)

I think you need to add document about StringLikeClasses option here.

[alexfh]

clang-tidy/performance/FasterStringFindCheck.cpp

30 ↗

(On Diff #44901)

We can try to be consistent with the choice of delimiters, but I'm not sure we can use the same delimiter always without introducing more syntax complexities like escaping or the use of quotes (like in CSV). In any case, we should clearly document the format for each option and think how we can issue diagnostics when we suspect incorrect format used in the option value.

72 ↗

(On Diff #44901)

This has to use the same delimiter. Maybe pull it to a constant to avoid inconsistency?

clang-tidy/performance/FasterStringFindCheck.h

25 ↗

(On Diff #44901)

Not here, in the .rst file, please.

[aaron.ballman]

clang-tidy/performance/FasterStringFindCheck.cpp

30 ↗

(On Diff #44901)

I think we should strive for consistency with ";" for right now, and agree that documentation/assistance is a reasonable fallback.

[sbenza]

Added comment about StringLikeClasses

[sbenza]

Make the delimiter a constant and fix mismatch between parse/serialize of the option.

[sbenza]

Friendly ping.

[aaron.ballman]

LGTM with one tiny nit.

clang-tidy/performance/FasterStringFindCheck.cpp

44 ↗

(On Diff #46798)

Minor nit: missing punctuation for the comment.

[sbenza]

Minor fix on comment

clang-tools-extra/trunk/clang-tidy/performance/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyPerformanceModule
+  FasterStringFindCheck.cpp
   ForRangeCopyCheck.cpp
   ImplicitCastInLoopCheck.cpp
   PerformanceTidyModule.cpp
   UnnecessaryCopyInitialization.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy
   clangTidyUtils
   )

clang-tools-extra/trunk/clang-tidy/performance/FasterStringFindCheck.h

+//===--- FasterStringFindCheck.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_PERFORMANCE_FASTER_STRING_FIND_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_FASTER_STRING_FIND_H
+
+#include "../ClangTidy.h"
+
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Optimize calls to std::string::find() and friends when the needle passed is
+/// a single character string literal.
+/// The character literal overload is more efficient.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance-faster-string-find.html
+class FasterStringFindCheck : public ClangTidyCheck {
+public:
+  FasterStringFindCheck(StringRef Name, ClangTidyContext *Context);
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+
+private:
+  const std::vector<std::string> StringLikeClasses;
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_FASTER_STRING_FIND_H

clang-tools-extra/trunk/clang-tidy/performance/FasterStringFindCheck.cpp

+//===--- FasterStringFindCheck.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 "FasterStringFindCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+namespace {
+
+static const char StringLikeClassesDelimiter[] = ";";
+
+std::vector<std::string> ParseClasses(StringRef Option) {
+  SmallVector<StringRef, 4> Classes;
+  Option.split(Classes, StringLikeClassesDelimiter);
+  std::vector<std::string> Result;
+  for (StringRef &Class : Classes) {
+    Class = Class.trim();
+    if (!Class.empty())
+      Result.push_back(Class);
+  }
+  return Result;
+}
+
+llvm::Optional<std::string> MakeCharacterLiteral(const StringLiteral *Literal) {
+  std::string Result;
+  {
+    llvm::raw_string_ostream OS(Result);
+    Literal->outputString(OS);
+  }
+  // Now replace the " with '.
+  auto pos = Result.find_first_of('"');
+  if (pos == Result.npos) return llvm::None;
+  Result[pos] = '\'';
+  pos = Result.find_last_of('"');
+  if (pos == Result.npos) return llvm::None;
+  Result[pos] = '\'';
+  return Result;
+}
+
+AST_MATCHER(StringLiteral, lengthIsOne) { return Node.getLength() == 1; }
+
+AST_MATCHER_FUNCTION(ast_matchers::internal::Matcher<Expr>,
+                     hasSubstitutedType) {
+  return hasType(qualType(anyOf(substTemplateTypeParmType(),
+                                hasDescendant(substTemplateTypeParmType()))));
+}
+
+} // namespace
+
+FasterStringFindCheck::FasterStringFindCheck(StringRef Name,
+                                             ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      StringLikeClasses(
+          ParseClasses(Options.get("StringLikeClasses", "std::basic_string"))) {
+}
+
+void FasterStringFindCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "StringLikeClasses",
+                llvm::join(StringLikeClasses.begin(), StringLikeClasses.end(),
+                           StringLikeClassesDelimiter));
+}
+
+void FasterStringFindCheck::registerMatchers(MatchFinder *Finder) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  const auto SingleChar =
+      expr(ignoringParenCasts(stringLiteral(lengthIsOne()).bind("literal")));
+
+  const auto StringFindFunctions =
+      anyOf(hasName("find"), hasName("rfind"), hasName("find_first_of"),
+            hasName("find_first_not_of"), hasName("find_last_of"),
+            hasName("find_last_not_of"));
+
+  llvm::Optional<ast_matchers::internal::Matcher<NamedDecl>> IsStringClass;
+
+  for (const auto &ClassName : StringLikeClasses) {
+    const auto HasName = hasName(ClassName);
+    IsStringClass = IsStringClass ? anyOf(*IsStringClass, HasName) : HasName;
+  }
+
+  if (IsStringClass) {
+    Finder->addMatcher(
+        cxxMemberCallExpr(
+            callee(functionDecl(StringFindFunctions).bind("func")),
+            anyOf(argumentCountIs(1), argumentCountIs(2)),
+            hasArgument(0, SingleChar),
+            on(expr(hasType(recordDecl(*IsStringClass)),
+                    unless(hasSubstitutedType())))),
+        this);
+  }
+}
+
+void FasterStringFindCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *Literal = Result.Nodes.getNodeAs<StringLiteral>("literal");
+  const auto *FindFunc = Result.Nodes.getNodeAs<FunctionDecl>("func");
+
+  auto Replacement = MakeCharacterLiteral(Literal);
+  if (!Replacement)
+    return;
+
+  diag(Literal->getLocStart(), "%0 called with a string literal consisting of "
+                               "a single character; consider using the more "
+                               "effective overload accepting a character")
+      << FindFunc->getName()
+      << FixItHint::CreateReplacement(
+             CharSourceRange::getTokenRange(Literal->getLocStart(),
+                                            Literal->getLocEnd()),
+             *Replacement);
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang

clang-tools-extra/trunk/clang-tidy/performance/PerformanceTidyModule.cpp

 //===--- PeformanceTidyModule.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 "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 
+#include "FasterStringFindCheck.h"
 #include "ForRangeCopyCheck.h"
 #include "ImplicitCastInLoopCheck.h"
 #include "UnnecessaryCopyInitialization.h"
 
 namespace clang {
 namespace tidy {
 namespace performance {
 
 class PerformanceModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
+    CheckFactories.registerCheck<FasterStringFindCheck>(
+        "performance-faster-string-find");
     CheckFactories.registerCheck<ForRangeCopyCheck>(
         "performance-for-range-copy");
     CheckFactories.registerCheck<ImplicitCastInLoopCheck>(
         "performance-implicit-cast-in-loop");
     CheckFactories.registerCheck<UnnecessaryCopyInitialization>(
         "performance-unnecessary-copy-initialization");
   }
 };

clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst

.. toctree::
    modernize-pass-by-value
    modernize-redundant-void-arg
    modernize-replace-auto-ptr
    modernize-shrink-to-fit
    modernize-use-auto
    modernize-use-default
    modernize-use-nullptr
    modernize-use-override
+   performance-faster-string-find
    performance-for-range-copy
    performance-implicit-cast-in-loop
    readability-braces-around-statements
    readability-container-size-empty
    readability-else-after-return
    readability-function-size
    readability-identifier-naming
    readability-implicit-bool-cast
    readability-inconsistent-declaration-parameter-name
    readability-named-parameter
    readability-redundant-control-flow
    readability-redundant-smartptr-get
    readability-redundant-string-cstr
    readability-simplify-boolean-expr
    readability-uniqueptr-delete-release

clang-tools-extra/trunk/docs/clang-tidy/checks/performance-faster-string-find.rst

+.. title:: clang-tidy - performance-faster-string-find
+
+performance-faster-string-find
+==============================
+
+Optimize calls to std::string::find() and friends when the needle passed is
+a single character string literal.
+The character literal overload is more efficient.
+
+By default only `std::basic_string` is considered. This list can be modified by
+passing a `;` separated list of class names using the `StringLikeClasses`
+option. The methods to consired are fixed, though.
+
+Examples:
+
+.. code-block:: c++
+
+  str.find("A");
+
+  // becomes
+
+  str.find('A');

clang-tools-extra/trunk/test/clang-tidy/performance-faster-string-find.cpp

+// RUN: %check_clang_tidy %s performance-faster-string-find %t -- \
+// RUN:   -config="{CheckOptions: \
+// RUN:             [{key: performance-faster-string-find.StringLikeClasses, \
+// RUN:               value: 'std::basic_string; ::llvm::StringRef;'}]}" --
+
+namespace std {
+template <typename Char>
+struct basic_string {
+  int find(const Char *, int = 0) const;
+  int find(const Char *, int, int) const;
+  int rfind(const Char *) const;
+  int find_first_of(const Char *) const;
+  int find_first_not_of(const Char *) const;
+  int find_last_of(const Char *) const;
+  int find_last_not_of(const Char *) const;
+};
+
+typedef basic_string<char> string;
+typedef basic_string<wchar_t> wstring;
+}  // namespace std
+
+namespace llvm {
+struct StringRef {
+  int find(const char *) const;
+};
+}  // namespace llvm
+
+struct NotStringRef {
+  int find(const char *);
+};
+
+void StringFind() {
+  std::string Str;
+
+  Str.find("a");
+  // CHECK-MESSAGES: [[@LINE-1]]:12: warning: find called with a string literal consisting of a single character; consider using the more effective overload accepting a character [performance-faster-string-find]
+  // CHECK-FIXES: Str.find('a');
+
+  // Works with the pos argument.
+  Str.find("a", 1);
+  // CHECK-MESSAGES: [[@LINE-1]]:12: warning: find called with a string literal
+  // CHECK-FIXES: Str.find('a', 1);
+
+  // Doens't work with strings smaller or larger than 1 char.
+  Str.find("");
+  Str.find("ab");
+
+  // Doesn't do anything with the 3 argument overload.
+  Str.find("a", 1, 1);
+
+  // Other methods that can also be replaced
+  Str.rfind("a");
+  // CHECK-MESSAGES: [[@LINE-1]]:13: warning: rfind called with a string literal
+  // CHECK-FIXES: Str.rfind('a');
+  Str.find_first_of("a");
+  // CHECK-MESSAGES: [[@LINE-1]]:21: warning: find_first_of called with a string
+  // CHECK-FIXES: Str.find_first_of('a');
+  Str.find_first_not_of("a");
+  // CHECK-MESSAGES: [[@LINE-1]]:25: warning: find_first_not_of called with a
+  // CHECK-FIXES: Str.find_first_not_of('a');
+  Str.find_last_of("a");
+  // CHECK-MESSAGES: [[@LINE-1]]:20: warning: find_last_of called with a string
+  // CHECK-FIXES: Str.find_last_of('a');
+  Str.find_last_not_of("a");
+  // CHECK-MESSAGES: [[@LINE-1]]:24: warning: find_last_not_of called with a
+  // CHECK-FIXES: Str.find_last_not_of('a');
+
+  // std::wstring should work.
+  std::wstring WStr;
+  WStr.find(L"n");
+  // CHECK-MESSAGES: [[@LINE-1]]:13: warning: find called with a string literal
+  // CHECK-FIXES: Str.find(L'n');
+  // Even with unicode that fits in one wide char.
+  WStr.find(L"\x3A9");
+  // CHECK-MESSAGES: [[@LINE-1]]:13: warning: find called with a string literal
+  // CHECK-FIXES: Str.find(L'\x3A9');
+
+  // Also with other types, but only if it was specified in the options.
+  llvm::StringRef sr;
+  sr.find("x");
+  // CHECK-MESSAGES: [[@LINE-1]]:11: warning: find called with a string literal
+  // CHECK-FIXES: sr.find('x');
+  NotStringRef nsr;
+  nsr.find("x");
+}
+
+
+template <typename T>
+int FindTemplateDependant(T value) {
+  return value.find("A");
+}
+template <typename T>
+int FindTemplateNotDependant(T pos) {
+  return std::string().find("A", pos);
+  // CHECK-MESSAGES: [[@LINE-1]]:29: warning: find called with a string literal
+  // CHECK-FIXES: return std::string().find('A', pos);
+}
+
+int FindStr() {
+  return FindTemplateDependant(std::string()) + FindTemplateNotDependant(1);
+}
+
+#define STR_MACRO(str) str.find("A")
+#define POS_MACRO(pos) std::string().find("A",pos)
+
+int Macros() {
+  return STR_MACRO(std::string()) + POS_MACRO(1);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: find called with a string literal
+  // CHECK-MESSAGES: [[@LINE-2]]:37: warning: find called with a string literal
+}