[clang-format][NFC] more centric handling of include name matching

[kwk]

Summary

Histroy

The foundation for this patch was done in: https://reviews.llvm.org/D121370. I wanted to "rescue" some pieces from
it.

Unlike D121370, this patch doesn't modify the regular expression to identify an include name itself.

1. It simply provides one instead of two copies of regular expression patterns.
2. We also provide a function to get the include name from a group of match groups delivered by the shared regular expression that is only instantiated once now. Before when you experimented with the regex for identifying include matches, you'd have to change multiple locations and for example replace Matches[2] with Matches[3] in many locations. This way cumbersome and by having a function clang::tooling::getIncludeNameFromMatches() this makes it more concise and easy to modify.
3. The include name was trimmed from unwanted characters ("<>) before and this was done repeatedly in multiple places. Now we have: clang::tooling::trimIncludeName() which does it for you, again in one place and not scattered over the code.

Testing

Here's how I've tested this patch:

$ cd llvm-project
$ mkdir build && cd build
$ cmake ../llvm/ -DCMAKE_BUILD_TYPE=Release -DCLANG_BUILD_TOOLS=On -DLLVM_ENABLE_PROJECTS=clang -DCLANG_INCLUDE_TESTS=ON -DLLVM_BUILD_UTILS=ON -G Ninja
$ ninja clangFormat
$ ninja FormatTests
$ ./tools/clang/unittests/Format/FormatTests --gtest_filter=SortIncludesTest*

And if that worked I doubled checked that nothing else broke by running
all format checks:

$ ./tools/clang/unittests/Format/FormatTests

[MyDeveloperDay]

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

410

What if this was overridable via the Style we could experiment with changing the regex

417

‘>= 2’

[kwk]

@MyDeveloperDay please see my potentially uneducated comments.

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

410

Well, right now that was never a requirement and to be honest it isn't very worth exploring this because its not easy to determine which the correct matching group is for the include name.

For example, let's say you would allow this to be configurable from the config file and a user enters the regex from my previous patch (D121370):

^[\t\ ]*[@#][\t\ ]*(import|include)([^"/]*("[^"]+")|[^</]*(<[^>]+>)|[\t/\ ]*([^;]+;))

How would you determine which is the correct matching group? I first thought about taking the last one matching but then I found that my regex was not able to cope with trailing comments. And even in my case there's more than one matching group for the include name. All in all I really don't see any value in outsourcing this to the config file is not something I see value in.

The only thing valuable would be to have a regex for multiple languages. Sorry if this is what you intended. I just wouldn't want to move this out to the config file for the end-user to play with.

417

@MyDeveloperDay correct me if I'm wrong but if an array has size 3 it has indexes 0, 1 and 2. And an array of size 2 only has 0 and 1. So the case =2, which is implied by your suggested`>=2`, is actually an out of bounds access when going Matches[2]. Because that is effectively accessing the third element. The only valid change would be to check for Matches.size() > 2 IMHO and that is the same as Matches.size() >= 3.

I must admit that I had to look at the regex a few times only to realize that it has two non-optional matching groups (...). The third matching group at index 0 is the whole line. So in theory >=3 isn't possible with the current regex. I wanted to give my best to have this logic "survive" a change to the regex in which for example something is added after the matching group of the include name; let's say a comment or something.

I hope I haven't made myself a complete fool.

[MyDeveloperDay]

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

417

No foolery other than my own. I meant to say '> 2', actually the first time I wrote the comment it disappear because it didn't escape the '>'

So one though I had for the config was something like this (ignore regex itself I just put anything in it to show the principle)

---
Language Cpp
IncludeRegex:  ^[\t\ ]*[@#][\t\ ]*(import|include)([^"/]*("[^"]+")|[^</]*(<[^>]+>)|[\t/\ ]*([^;]+;)
IncludeRegexGroup: 1
---
Language: ObjectiveC
IncludeRegex:  ^[\t\ ]*[@#][\t\ ]*(import|include)([^"/]*("[^"]+")|[^</]*(<[^>]+>)|[\t/\ ]*([^;]+;)
IncludeRegexGroup: 2
---
Language: CSharp
IncludeRegex:  using  ([A-z])*
IncludeRegexGroup: 0
---
Language: Carbon
IncludeRegex:  package ([A-z])* api
IncludeRegexGroup: 0
---

Wouldn't this allow different languages to have their own Include/Import regex? Just thinking out loud

It could be more powerful than having 1 regex to rule them all.

[owenpan]

While attempting to review this patch, I came to the conclusion that we should first clean up the HeaderIncludes class and Format.cpp a little. I will submit a patch for review ASAP.

[owenpan]

See D134852.

[kwk]

• Remove ad-hoc instantiated IncludeRegex objects

[kwk]

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

417

@MyDeveloperDay I like the idea of this approach! But I also see that a single language alone, namely C++, is quite a tough nut to crack with the advent of Modules (https://en.cppreference.com/w/cpp/language/modules). I'm afraid the bit of IncludeRegexGroup would need to be expanded to be either a

• fixed number (wherever possible)
• a method as in: last-non-empty-matching-group

Only then I think that your solution would work. Can one have a setting in clang format that allows for mixed input as in number or string? A bit of a hacky solution but probably cutting 100% of all regexes would be to have an enum with these allowed strings: last-non-empty-matching-group,first-non-empty-matching-group,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20.

[kwk]

• Make include regex a static member and not a function (@owenpan did this in D134852)
• Run clang-format

[owenpan]

Can you rebase? I'll finish the review after that.

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

410

Use ArrayRef instead.

411–415

You can simply assert and return.

clang/include/clang/Tooling/Inclusions/HeaderIncludes.h

llvm::Optional<tooling::Replacement> insert(llvm::StringRef Header,
                                               bool IsAngled) const;
 
   /// Removes all existing #includes of \p Header quoted with <> if \p IsAngled
   /// is true or "" if \p IsAngled is false.
   /// This doesn't resolve the header file path; it only deletes #includes with
   /// exactly the same spelling.
   tooling::Replacements remove(llvm::StringRef Header, bool IsAngled) const;
 
+  // Matches a whole #include directive.
+  static const llvm::Regex IncludeRegex;
+
 private:
   struct Include {
     Include(StringRef Name, tooling::Range R) : Name(Name), R(R) {}
 
     // An include header quoted with either <> or "".
     std::string Name;
     // The range of the whole line of include directive including any leading
     // whitespaces and trailing comment.
private:
   // declaration).
   unsigned MaxInsertOffset;
   IncludeCategoryManager Categories;
   // Record the offset of the end of the last include in each category.
   std::unordered_map<int, int> CategoryEndOffsets;
 
   // All possible priorities.
   std::set<int> Priorities;
-
-  // Matches a whole #include directive.
-  llvm::Regex IncludeRegex;
 };
 
+/// \returns the include name from the list of match groups.
+/// \sa HeaderIncludes::IncludeRegex for the regular expression
+llvm::StringRef getIncludeNameFromMatches(
+    const llvm::SmallVectorImpl<llvm::StringRef> &Matches);
+
+/// \returns the given include name and removes the following symbols from the
+/// beginning and ending of the include name: " > < ;
+llvm::StringRef trimInclude(llvm::StringRef IncludeName);
+
 } // namespace tooling
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLING_INCLUSIONS_HEADERINCLUDES_H

clang/lib/Format/Format.cpp

 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include "llvm/Support/YAMLTraits.h"
 #include <algorithm>
+#include <limits>
 #include <memory>
 #include <mutex>
 #include <string>
 #include <unordered_map>
 
 #define DEBUG_TYPE "format-formatter"
 
 using clang::format::FormatStyle;
static void sortCppIncludes(const FormatStyle &Style,
   // FIXME: better error handling. For now, just skip the replacement for the
   // release version.
   if (Err) {
     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
     assert(false);
   }
 }
 
-namespace {
-
-const char CppIncludeRegexPattern[] =
-    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
-
-} // anonymous namespace
-
 tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
                                       ArrayRef<tooling::Range> Ranges,
                                       StringRef FileName,
                                       tooling::Replacements &Replaces,
                                       unsigned *Cursor) {
   unsigned Prev = llvm::StringSwitch<size_t>(Code)
                       .StartsWith("\xEF\xBB\xBF", 3) // UTF-8 BOM
                       .Default(0);
   unsigned SearchFrom = 0;
-  llvm::Regex IncludeRegex(CppIncludeRegexPattern);
   SmallVector<StringRef, 4> Matches;
   SmallVector<IncludeDirective, 16> IncludesInBlock;
 
   // In compiled files, consider the first #include to be the main #include of
   // the file if it is not a system #include. This ensures that the header
   // doesn't have hidden dependencies
   // (http://llvm.org/docs/CodingStandards.html#include-style).
   //
for (;;) {
     const bool EmptyLineSkipped =
         Trimmed.empty() &&
         (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
          Style.IncludeStyle.IncludeBlocks ==
              tooling::IncludeStyle::IBS_Regroup);
 
     bool MergeWithNextLine = Trimmed.endswith("\\");
     if (!FormattingOff && !MergeWithNextLine) {
-      if (IncludeRegex.match(Line, &Matches)) {
-        StringRef IncludeName = Matches[2];
+      if (tooling::HeaderIncludes::IncludeRegex.match(Line, &Matches)) {
+        StringRef IncludeName = tooling::getIncludeNameFromMatches(Matches);
+
         if (Line.contains("/*") && !Line.contains("*/")) {
           // #include with a start of a block comment, but without the end.
           // Need to keep all the lines until the end of the comment together.
           // FIXME: This is somehow simplified check that probably does not work
           // correctly if there are multiple comments on a line.
           Pos = Code.find("*/", SearchFrom);
           Line = Code.substr(
               Prev, (Pos != StringRef::npos ? Pos + 2 : Code.size()) - Prev);
formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
   };
   return processReplacements(Reformat, Code, *SortedReplaces, Style);
 }
 
 namespace {
 
 inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
-         llvm::Regex(CppIncludeRegexPattern)
-             .match(Replace.getReplacementText());
+         tooling::HeaderIncludes::IncludeRegex.match(
+             Replace.getReplacementText());
 }
 
 inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
   return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
 }
 
 // FIXME: insert empty lines between newly created blocks.
-tooling::Replacements
+static tooling::Replacements
 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
                         const FormatStyle &Style) {
   if (!Style.isCpp())
     return Replaces;
 
   tooling::Replacements HeaderInsertions;
   std::set<llvm::StringRef> HeadersToDelete;
   tooling::Replacements Result;
fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
   if (HeaderInsertions.empty() && HeadersToDelete.empty())
     return Replaces;
 
   StringRef FileName = Replaces.begin()->getFilePath();
   tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
 
   for (const auto &Header : HeadersToDelete) {
     tooling::Replacements Replaces =
-        Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
+        Includes.remove(tooling::trimInclude(Header), Header.startswith("<"));
     for (const auto &R : Replaces) {
       auto Err = Result.add(R);
       if (Err) {
         // Ignore the deletion on conflict.
         llvm::errs() << "Failed to add header deletion replacement for "
                      << Header << ": " << llvm::toString(std::move(Err))
                      << "\n";
       }
     }
   }
 
-  llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
   llvm::SmallVector<StringRef, 4> Matches;
   for (const auto &R : HeaderInsertions) {
     auto IncludeDirective = R.getReplacementText();
-    bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
+    bool Matched =
+        tooling::HeaderIncludes::IncludeRegex.match(IncludeDirective, &Matches);
     assert(Matched && "Header insertion replacement must have replacement text "
                       "'#include ...'");
     (void)Matched;
-    auto IncludeName = Matches[2];
-    auto Replace =
-        Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
+    StringRef IncludeName = tooling::getIncludeNameFromMatches(Matches);
+    auto Replace = Includes.insert(tooling::trimInclude(IncludeName),
+                                   IncludeName.startswith("<"));
     if (Replace) {
       auto Err = Result.add(*Replace);
       if (Err) {
         llvm::consumeError(std::move(Err));
         unsigned NewOffset =
             Result.getShiftedCodePosition(Replace->getOffset());
         auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
                                             Replace->getReplacementText());

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

return getOffsetAfterTokenSequence(
         skipComments(Lex, Tok);
         unsigned MaxOffset = SM.getFileOffset(Tok.getLocation());
         while (checkAndConsumeInclusiveDirective(Lex, Tok))
           MaxOffset = SM.getFileOffset(Tok.getLocation());
         return MaxOffset;
       });
 }
 
-inline StringRef trimInclude(StringRef IncludeName) {
-  return IncludeName.trim("\"<>");
-}
-
-const char IncludeRegexPattern[] =
-    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
-
 // The filename of Path excluding extension.
 // Used to match implementation with headers, this differs from sys::path::stem:
 //  - in names with multiple dots (foo.cu.cc) it terminates at the *first*
 //  - an empty stem is never returned: /foo/.bar.x => .bar
 //  - we don't bother to handle . and .. specially
 StringRef matchingStem(llvm::StringRef Path) {
   StringRef Name = llvm::sys::path::filename(Path);
   return Name.substr(0, Name.find('.', 1));
if (!Matching.empty()) {
     llvm::Regex MainIncludeRegex(HeaderStem.str() + Style.IncludeIsMainRegex,
                                  llvm::Regex::IgnoreCase);
     if (MainIncludeRegex.match(Matching))
       return true;
   }
   return false;
 }
 
+static const char IncludeRegexPattern[] =
+    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
+/// IncludeRegex ia regex that can match various styles of C++ includes.
+/// For example:
+/// \code
+/// #include <foo.h>
+/// #include "bar.h"
+/// \endcode
+const llvm::Regex HeaderIncludes::IncludeRegex(IncludeRegexPattern);
+
 HeaderIncludes::HeaderIncludes(StringRef FileName, StringRef Code,
                                const IncludeStyle &Style)
     : FileName(FileName), Code(Code), FirstIncludeOffset(-1),
       MinInsertOffset(
           getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style)),
       MaxInsertOffset(MinInsertOffset +
                       getMaxHeaderInsertionOffset(
                           FileName, Code.drop_front(MinInsertOffset), Style)),
-      Categories(Style, FileName),
-      IncludeRegex(llvm::Regex(IncludeRegexPattern)) {
+      Categories(Style, FileName) {
   // Add 0 for main header and INT_MAX for headers that are not in any
   // category.
   Priorities = {0, INT_MAX};
   for (const auto &Category : Style.IncludeCategories)
     Priorities.insert(Category.Priority);
   SmallVector<StringRef, 32> Lines;
   Code.drop_front(MinInsertOffset).split(Lines, "\n");
 
   unsigned Offset = MinInsertOffset;
   unsigned NextLineOffset;
   SmallVector<StringRef, 4> Matches;
   for (auto Line : Lines) {
     NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
-    if (IncludeRegex.match(Line, &Matches)) {
+    if (tooling::HeaderIncludes::IncludeRegex.match(Line, &Matches)) {
+      StringRef IncludeName = tooling::getIncludeNameFromMatches(Matches);
       // If this is the last line without trailing newline, we need to make
       // sure we don't delete across the file boundary.
       addExistingInclude(
-          Include(Matches[2],
+          Include(IncludeName,
                   tooling::Range(
                       Offset, std::min(Line.size() + 1, Code.size() - Offset))),
           NextLineOffset);
     }
     Offset = NextLineOffset;
   }
 
   // Populate CategoryEndOfssets:
if (Err) {
       auto ErrMsg = "Unexpected conflicts in #include deletions: " +
                     llvm::toString(std::move(Err));
       llvm_unreachable(ErrMsg.c_str());
     }
   }
   return Result;
 }
 
+llvm::StringRef getIncludeNameFromMatches(
+    const llvm::SmallVectorImpl<llvm::StringRef> &Matches) {
+  if (Matches.size() >= 3) {
+    return Matches[2];
+  }
+  llvm_unreachable("Matches is too small");
+  return llvm::StringRef();
+}
+
+llvm::StringRef trimInclude(llvm::StringRef IncludeName) {
+  return IncludeName.trim("\"<>;");
+}
+
 } // namespace tooling
 } // namespace clang