[clang-format] SortIncludes should support "@import" lines in Objective-C

[kwk]

Summary

[clang-format] SortIncludes should support "@import" lines in Objective-C

Fixes #38995

This is an attempt to modify the regular expression to identify
@import and import alongside the regular #include. The challenging
part was not to support @ in addition to # but how to handle
everything that comes after the include|import keywords. Previously
everything that wasn't " or < was consumed. But as you can see in
this example from the issue #38995, there is no " or < following the
keyword:

@import Foundation;

I experimented with a lot of fancy and useful expressions in this online regex tool only to find out that some
things are simply not supported by the regex implementation in LLVM.

• For example the beginning [\t\ ]* should be replacable by the horizontal whitespace character \h* but this will break the SortIncludesTest.LeadingWhitespace test.

That's why I've chosen to come back to the basic building blocks.

The essential change in this patch is the change from this regular
expression:

^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">])
        ~                              ~~~~~~~~~~~~~~
        ^                              ^
        |                              |
        only support # prefix not @    |
                                       only support "" and <> as delimiters
                                       no support for C++ modules and ;
                                       ending. Also this allows for ">
                                       or <" or "" or <> which all seems
                                       either off or wrong.

to this:

^[\t\ ]*[@#][\t\ ]*(import|include)([^"/]*("[^"]+")|[^</]*(<[^>]+>)|[\t/\ ]*([^;]+;))
        ~~~~                        ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~
        ^                                 ^           ^       ^       ^
        |                                 |           |       |       |
        Now support @ and #.            Clearly support "" and <> as ell as an
                                        include name without enclosing characters.
                                        Allows for no mixture of "> or <" or
                                        empty include names. Trailing
                                        comments on include lines as shown in
                                        D124513 are ignored now by
                                        ignoring slashes in the characters that
                                        lead up to a match group.

Here is how I've tested this patch:

ninja clang-Format
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

One side effect of this change is it should partially support
C++20 Module
import lines without the optional export in front. Adding
this can be a change on its own that shouldn't be too hard. I say
partially because the @ or # are currently *NOT* optional in the
regular expression.

I see an opportunity to optimized the matching to exclude @include for
example. But eventually these should be caught by the compiler, so...

With my change, the matching group is not at a fixed position any
longer. I decided to choose the last match (group) that is not empty.

[HazardyKnusperkeks]

clang/lib/Format/Format.cpp

2795

How does that not go out of scope and I have a dangling reference?

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

171–172

I don't see why this is needed. It should match with the previous stuff.

171–172

Do we want that optional?

clang/unittests/Format/SortIncludesTest.cpp

471

I've no idea about obj-c, is it feasible to mix # and @? If so please add a test where the @ is between #s.

[curdeius]

clang/lib/Format/Format.cpp

2724–2725

I'd rather see handling separately the #import/#include case on one hand and @import on the other.
IIUC, @import is followed by ns1.ns2.something without quotes nor <>. And it ends with a ;.
Trying to put everything together is IMO error-prone and not very readable.

You could just do (pseudo-code):

CppIncludeRegexPattern = (current_regex) | "@\s*import\s+[^;]+;"

(\s is probably not supported, but we could use character class [:space:] for clarity, cf. llvm\lib\Support\regcomp.c)

Not sure whether whitespace is allowed after @.
Could you please post a link to the specification of @import syntax?

Not sure fixing <" / "> issue is worth it, but in all cases I'd prefer seeing it in a different patch.

2795

Why not doing it the other way round, i.e. trimming <>" from include name?

[curdeius]

clang/lib/Format/Format.cpp

2724–2725

[:space:] would match newlines and we don't want this in all cases, but [:blank:] should be a good replacement for [\t ].

On a different note, why there's a new line \n and backslash \\ in [\t\n\ \\]?

[kwk]

• Make @ or # not optional again
• Remove [\t\n\ \\]*
• Properly concat string

[kwk]

Thank you for your comments! I've addressed many of them and now address the rest.

clang/lib/Format/Format.cpp

2795

Why not doing it the other way round, i.e. trimming <>" from include name?

Because the include name is used for sorting later and if the <> is removed from the name, the <> included will be mixed with the "". That's undesirable.

2795

How does that not go out of scope and I have a dangling reference?

Sorry I was a bit lost with this but with some help I found other places in which concat was used and toStringRef. I hope everything is fine now.

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

171–172

I don't see why this is needed. It should match with the previous stuff.

That's why I thought too. I swear I ran the tests before and I wouldn't work without this. But I re-ran the tests and now it works. Thanks for bringing up this very obvious part.

171–172

Do we want that optional?

We don't need it optional for the tests to pass. Only for C++20 Modules, we need it optional. But this is *not* part of this change. I've removed the optional part of this.

clang/unittests/Format/SortIncludesTest.cpp

471

I've no idea about obj-c, is it feasible to mix # and @? If so please add a test where the @ is between #s.

This test is copied from the issue itself. I have no idea about Obj-c as well. The @ already *is* between the #. Did I miss something?

[kwk]

A test if failing. Need to address this first.

[kwk]

Changed the strategy of how includes are sorted by increasing the priority if an include is of the "new" type: @import Foundation;. This will sort these includes after everything else just as requested in https://github.com/llvm/llvm-project/issues/38995.

[kwk]

• Fix formatting

[HazardyKnusperkeks]

Some test with a main header and blocks would be nice.

clang/lib/Format/Format.cpp

2810–2813

I don't know about the others, but I prefer C++: std::numeric_limits

[kwk]

• Use std::numeric_limits<int>::max() instead of INT_MAX

[kwk]

Addressed review comments.

clang/lib/Format/Format.cpp

2810–2813

Sure. That's done now.

[HazardyKnusperkeks]

In D121370#3383574, @HazardyKnusperkeks wrote:

Some test with a main header and blocks would be nice.

This one please. :)

[MyDeveloperDay]

clang/lib/Format/Format.cpp

2798

int false?

[kwk]

• Address review comments on grouping and main headers

[kwk]

• Fix: int -> bool

[kwk]

In D121370#3387175, @HazardyKnusperkeks wrote:

In D121370#3383574, @HazardyKnusperkeks wrote:

Some test with a main header and blocks would be nice.

This one please. :)

Done.

clang/lib/Format/Format.cpp

2798

int false?

Yes, this was just to see if everybody is awake ;). Just kiddin'. Good catch.

[kwk]

This comment was removed by kwk.

[kwk]

• Fix tests

[HazardyKnusperkeks]

But please fix the format. :)

[kwk]

• introduce getIncludeNameFromMatches
• Fix format

[kwk]

@HazardyKnusperkeks thank you for the approval. Can you have one last view please? I've introduced a function to get the match instead of repeating the for loop two times.

[kwk]

• Remove left-over comment

[kwk]

• Remove duplicate assert

[kwk]

@MyDeveloperDay can you please have another look now that the patch has additional tests and most comments that still apply have been addressed?

[HazardyKnusperkeks]

clang/lib/Format/Format.cpp

2730–2733

2735

Is there something like LLVM_UNREACHABLE?

[kwk]

• Address review comment

[kwk]

@HazardyKnusperkeks I've addressed your comments and did an early return together with llvm_unreachable() which is used in the clang/lib/Format in other places as well. I hope this is to your liking. There's no longer an assert. Do you want that as well?

[owenpan]

clang/lib/Format/Format.cpp

2728–2731

I think you missed Matches[0].

3080

We should make it static if it's only used in this file.

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

171–172

If these are the same as in Format.cpp above, we should move the definitions to HeaderIncludes.h.

[owenpan]

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

171–172

If these are the same as in Format.cpp above, we should move the definitions to HeaderIncludes.h.

I meant we should remove the definitions from Format.cpp and add the declarations to HeaderIncludes.h.

[kwk]

• Put shared code for finding include names HeaderIncludes

[kwk]

• Added llvm:: namespace

[kwk]

• Use proposed reverse loop

[kwk]

• Make function static

[kwk]

clang/lib/Format/Format.cpp

2728–2731

I did miss it and fixed it but it doesn't make much sense to use the first match because that's always the overall string that's being matched. Nevertheless, I've used your porposed reverse loop and the logic is better if it includes even the first match.

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

171–172

I think I've done what you intended me to do.

[owenpan]

Should we handle #import and @import for Object-C only so as to simply the regex for C++?

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

136

I think you meant @import bar;, which is valid in Objective-C only. So is #import btw.

139–147

Function names should start with a lowercase letter.

[kwk]

• Make functions lowercase

[kwk]

In D121370#3456223, @owenpan wrote:

Should we handle #import and @import for Object-C only so as to simply the regex for C++?

@owenpan my counter question probably reveals how few things I know about clang-format and how much I still have to learn. I only see sortCppIncludes but no sortObjCIncludes in the function list in Format.h. That said, do you want to introduce that or do you want to put logic in sortCppIncludes that knows about the programming language at hand and decides which regex to pick?

[kwk]

• typo: @include bar; -> @import bar;

[MyDeveloperDay]

The hard part about doing 2 separate cases is where we miss-interpret a .hpp or .h file as being the wrong language (C/C++/ObjC/ObjC++), I don't think I have a problem with a single regex (its not like we change it that often).

Is there a use case for having them separate or not?

[MyDeveloperDay]

Accepting but please wait for @owenpan

[owenpan]

LGTM as I defer to @MyDeveloperDay.

[krasimir]

It appears that this regressed include sorting in the following case, where the contents of test.h show the expected include order and the clang-format behavior before this patch:

% cat test.h
#include <cstdint>

#include "util/bar.h"
#include "util/foo/foo.h"  // foo<T>
% bin/clang-format --version; bin/clang-format -style=google test.h
clang-format version 15.0.0 (https://github.com/llvm/llvm-project.git d46fa023caa2db5a9f1e21dd038bcb626261d958)
#include "util/foo/foo.h"  // foo<T>
#include <cstdint>

#include "util/bar.h"

@kwk could you please take a look

[kwk]

In D121370#3471183, @krasimir wrote:

It appears that this regressed include sorting in the following case, where the contents of test.h show the expected include order and the clang-format behavior before this patch:

% cat test.h
#include <cstdint>

#include "util/bar.h"
#include "util/foo/foo.h"  // foo<T>
% bin/clang-format --version; bin/clang-format -style=google test.h
clang-format version 15.0.0 (https://github.com/llvm/llvm-project.git d46fa023caa2db5a9f1e21dd038bcb626261d958)
#include "util/foo/foo.h"  // foo<T>
#include <cstdint>

#include "util/bar.h"

@kwk could you please take a look

@krasimir I'm on sick leave and will have a look as soon as I'm back. Can it wait that long?

[krasimir]

@krasimir I'm on sick leave and will have a look as soon as I'm back. Can it wait that long?

I'm planning to revert this temporarily and add a regression test, you can proceed with this work without time pressure. We aim to release a new clang-format version weekly to ease the process of finding and reporting regressions.

[kwk]

Address trailing comments on include lines by ignoring slashes in
characters that lead up to the match groups.

^[\t\ ]*[@#][\t\ ]*(import|include)([^"/]*("[^"]+")|[^</]*(<[^>]+>)|[\t/\ ]*([^;]+;))
        ~~~~                        ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~
        ^                                 ^           ^       ^       ^
        |                                 |           |       |       |
        Now support @ and #.            Clearly support "" and <> as ell as an
                                        include name without enclosing characters.
                                        Allows for no mixture of "> or <" or
                                        empty include names. Trailing
                                        comments on include lines as shown in
                                        D124513 are ignored now by
                                        ignoring slashes in the characters that
                                        lead up to a match group.

[kwk]

@krasimir could you please test this patch on your side? I've reopened it and tested it with the following file that contains both // and /* ... */ trailing comments on include lines followed by foo<T> and alike. The includes use <...> and "..." notation to locate files.

*test.h*

#include <cstdint>

#include "util/bar.h"
#include "util/foo/foo.h"  // foo<T>
#include "util/bar/bar.h"  // bar
#include "utilzbar0.h"  // bar0<T>
#include <util/foo/foo3.h>  // foo3<T>
#include <util/bar/bar3.h>  // bar3
#include <util/foo/foo2.h>  // foo2<T>
#include <util/bar/bar2.h>  // bar2
#include "util/bar.h"
#include "util/foo/foo.h"  /* foo<T> */
#include "util/bar/bar.h"  /* bar */
#include "utilzbar0.h"  /* bar0<T> */
#include <util/foo/foo3.h>  /* foo3<T> */
#include <util/bar/bar3.h>  /* bar3 */
#include <util/foo/foo2.h>  /* foo2<T> */
#include <util/bar/bar2.h>  /* bar2 */

Run test with ninja clang-format && bin/clang-format -style=google test.h:

#include <util/bar/bar2.h>  // bar2
#include <util/bar/bar2.h>  /* bar2 */
#include <util/bar/bar3.h>  // bar3
#include <util/bar/bar3.h>  /* bar3 */
#include <util/foo/foo2.h>  // foo2<T>
#include <util/foo/foo2.h>  /* foo2<T> */
#include <util/foo/foo3.h>  // foo3<T>
#include <util/foo/foo3.h>  /* foo3<T> */

#include <cstdint>

#include "util/bar.h"
#include "util/bar/bar.h"  // bar
#include "util/bar/bar.h"  /* bar */
#include "util/foo/foo.h"  // foo<T>
#include "util/foo/foo.h"  /* foo<T> */
#include "utilzbar0.h"     // bar0<T>
#include "utilzbar0.h"     /* bar0<T> */

To me, this looks precisely how it should look like. What do you think?

[kwk]

Some thing that doesn't work at the moment is ordering an include like this:

#include /*some include*/ "wontwork.h"

I wonder if it worked before. Let's see. Yes it worked. Grrr. I guess I need to do more...

[kwk]

I found another problem with both regular expressions (pre mine and mine): They cannot find

/* a comment before */ #include <foo>

Is this a known problem @MyDeveloperDay @owenpan @krasimir ?

[krasimir]

In D121370#3488401, @kwk wrote:

@krasimir could you please test this patch on your side?

@kwk thank you! the new version of the patch looks good!

I didn't know before about the issue you found with the /* a comment before */ #include <foo> (and since it's preexisting, if it's tricky to address, it would be reasonable to just file a bug for it and omit fixing it by this work, I think).

[owenpan]

Now support @ and #.            Clearly support "" and <> as ell as an

as well as?

[owenpan]

In D121370#3489245, @krasimir wrote:

In D121370#3488401, @kwk wrote:

@krasimir could you please test this patch on your side?

@kwk thank you! the new version of the patch looks good!

I didn't know before about the issue you found with the /* a comment before */ #include <foo> (and since it's preexisting, if it's tricky to address, it would be reasonable to just file a bug for it and omit fixing it by this work, I think).

+1.

[MyDeveloperDay]

@kwk have we bottomed out on this issue? its been stale for a bit. If we are not going to work on it further can be "Abandon" the review to get it off our lists?

[kwk]

In D121370#3817753, @MyDeveloperDay wrote:

@kwk have we bottomed out on this issue? its been stale for a bit. If we are not going to work on it further can be "Abandon" the review to get it off our lists?

We can abandon this patch and I might look into it some other time. But I wanted to rescue bits from this patch that don't change the current behavior. That's why I've created: https://reviews.llvm.org/D134733 . I hope we can approve it to get the transparency in and make a patch like D121370 a bit smaller in the future.

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

private:
 
   // All possible priorities.
   std::set<int> Priorities;
 
   // Matches a whole #include directive.
   llvm::Regex IncludeRegex;
 };
 
+/// \returns a regex that can match various styles of C++ includes.
+/// For example:
+/// \code
+/// #include <foo.h>
+/// @include bar;
+/// #include "bar.h"
+/// \endcode
+llvm::Regex GetCppIncludeRegex();
+
+/// \returns the last match in the list of matches that is not empty.
+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;
auto Err = Replaces.add(tooling::Replacement(
       FileName, Includes.front().Offset, IncludesBlockSize, result));
   // 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);
+  llvm::Regex IncludeRegex(tooling::GetCppIncludeRegex());
   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).
   //
   // FIXME: Do some validation, e.g. edit distance of the base name, to fix
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];
+        StringRef IncludeName = tooling::GetIncludeNameFromMatches(Matches);
+        // This addresses https://github.com/llvm/llvm-project/issues/38995
+        bool WithSemicolon = false;
+        if (!IncludeName.startswith("\"") && !IncludeName.startswith("<") &&
+            IncludeName.endswith(";")) {
+          WithSemicolon = true;
+        }
+
         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);
         }
         int Category = Categories.getIncludePriority(
             IncludeName,
             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
-        int Priority = Categories.getSortIncludePriority(
-            IncludeName, !MainIncludeFound && FirstIncludeBlock);
+        int Priority = WithSemicolon ? std::numeric_limits<int>::max()
+                                     : Categories.getSortIncludePriority(
+                                           IncludeName, !MainIncludeFound &&
+                                                            FirstIncludeBlock);
         if (Category == 0)
           MainIncludeFound = true;
         IncludesInBlock.push_back(
             {IncludeName, Line, Prev, Category, Priority});
       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
                         Replaces, Cursor);
         IncludesInBlock.clear();
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::GetCppIncludeRegex().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::Regex IncludeRegex = tooling::GetCppIncludeRegex();
   llvm::SmallVector<StringRef, 4> Matches;
   for (const auto &R : HeaderInsertions) {
     auto IncludeDirective = R.getReplacementText();
     bool Matched = 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(
       [](const SourceManager &SM, Lexer &Lex, Token Tok) {
         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));
 }

 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), IncludeRegex(GetCppIncludeRegex()) {
   // 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)) {
+      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:
for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
     if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
 }
 
 // \p Offset: the start of the line following this include directive.
 void HeaderIncludes::addExistingInclude(Include IncludeToAdd,
                                         unsigned NextLineOffset) {
   auto Iter =
-      ExistingIncludes.try_emplace(trimInclude(IncludeToAdd.Name)).first;
+      ExistingIncludes.try_emplace(TrimInclude(IncludeToAdd.Name)).first;
   Iter->second.push_back(std::move(IncludeToAdd));
   auto &CurInclude = Iter->second.back();
   // The header name with quotes or angle brackets.
   // Only record the offset of current #include if we can insert after it.
   if (CurInclude.R.getOffset() <= MaxInsertOffset) {
     int Priority = Categories.getIncludePriority(
         CurInclude.Name, /*CheckMainHeader=*/FirstIncludeOffset < 0);
     CategoryEndOffsets[Priority] = NextLineOffset;
     IncludesByPriority[Priority].push_back(&CurInclude);
     if (FirstIncludeOffset < 0)
       FirstIncludeOffset = CurInclude.R.getOffset();
   }
 }
 
 llvm::Optional<tooling::Replacement>
 HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
-  assert(IncludeName == trimInclude(IncludeName));
+  assert(IncludeName == TrimInclude(IncludeName));
   // If a <header> ("header") already exists in code, "header" (<header>) with
   // different quotation will still be inserted.
   // FIXME: figure out if this is the best behavior.
   auto It = ExistingIncludes.find(IncludeName);
   if (It != ExistingIncludes.end())
     for (const auto &Inc : It->second)
       if ((IsAngled && StringRef(Inc.Name).startswith("<")) ||
           (!IsAngled && StringRef(Inc.Name).startswith("\"")))
HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
   // newline should be added.
   if (InsertOffset == Code.size() && (!Code.empty() && Code.back() != '\n'))
     NewInclude = "\n" + NewInclude;
   return tooling::Replacement(FileName, InsertOffset, 0, NewInclude);
 }
 
 tooling::Replacements HeaderIncludes::remove(llvm::StringRef IncludeName,
                                              bool IsAngled) const {
-  assert(IncludeName == trimInclude(IncludeName));
+  assert(IncludeName == TrimInclude(IncludeName));
   tooling::Replacements Result;
   auto Iter = ExistingIncludes.find(IncludeName);
   if (Iter == ExistingIncludes.end())
     return Result;
   for (const auto &Inc : Iter->second) {
     if ((IsAngled && StringRef(Inc.Name).startswith("\"")) ||
         (!IsAngled && StringRef(Inc.Name).startswith("<")))
       continue;
     llvm::Error Err = Result.add(tooling::Replacement(
         FileName, Inc.R.getOffset(), Inc.R.getLength(), ""));
     if (Err) {
       auto ErrMsg = "Unexpected conflicts in #include deletions: " +
                     llvm::toString(std::move(Err));
       llvm_unreachable(ErrMsg.c_str());
     }
   }
   return Result;
 }
 
+llvm::Regex GetCppIncludeRegex() {
+  static const char CppIncludeRegexPattern[] =
+      R"(^[\t\ ]*[@#][\t\ ]*(import|include)([^"]*("[^"]+")|[^<]*(<[^>]+>)|[\t\ ]*([^;]+;)))";
+  return llvm::Regex(CppIncludeRegexPattern);
+}
+
+llvm::StringRef GetIncludeNameFromMatches(
+    const llvm::SmallVectorImpl<llvm::StringRef> &Matches) {
+  for (auto Match : llvm::reverse(Matches)) {
+    if (!Match.empty())
+      return Match;
+  }
+  llvm_unreachable("No non-empty match group found in list of matches");
+  return llvm::StringRef();
+}
+
+llvm::StringRef TrimInclude(llvm::StringRef IncludeName) {
+  return IncludeName.trim("\"<>;");
+}
+
 } // namespace tooling
 } // namespace clang

clang/unittests/Format/SortIncludesTest.cpp

EXPECT_EQ("#include \"a.h\"\n"
             "#include \"b.h\"\n"
             "#include \"c.h\"\n",
             sort("#include \"a.h\"\n"
                  "#include \\\n"
                  "\"c.h\"\n"
                  "#include \"b.h\"\n"));
 }
 
+TEST_F(SortIncludesTest, SupportAtImportLines) {
+  // Test from https://github.com/llvm/llvm-project/issues/38995
+  EXPECT_EQ("#import \"a.h\"\n"
+            "#import \"b.h\"\n"
+            "#import \"c.h\"\n"
+            "#import <d/e.h>\n"
+            "@import Foundation;\n",
+            sort("#import \"b.h\"\n"
+                 "#import \"c.h\"\n"
+                 "#import <d/e.h>\n"
+                 "@import Foundation;\n"
+                 "#import \"a.h\"\n"));
+
+  // Slightly more complicated test that shows sorting in each priorities still
+  // works.
+  EXPECT_EQ("#import \"a.h\"\n"
+            "#import \"b.h\"\n"
+            "#import \"c.h\"\n"
+            "#import <d/e.h>\n"
+            "@import Base;\n"
+            "@import Foundation;\n"
+            "@import base;\n"
+            "@import foundation;\n",
+            sort("#import \"b.h\"\n"
+                 "#import \"c.h\"\n"
+                 "@import Base;\n"
+                 "#import <d/e.h>\n"
+                 "@import foundation;\n"
+                 "@import Foundation;\n"
+                 "@import base;\n"
+                 "#import \"a.h\"\n"));
+
+  // Test that shows main headers in two groups are still found and sorting
+  // still works. The @import's are kept in their respective group but are
+  // put at the end of each group.
+  FmtStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Preserve;
+  EXPECT_EQ("#import \"foo.hpp\"\n"
+            "#import \"b.h\"\n"
+            "#import \"c.h\"\n"
+            "#import <d/e.h>\n"
+            "@import Base;\n"
+            "@import Foundation;\n"
+            "@import foundation;\n"
+            "\n"
+            "#import \"foo.h\"\n"
+            "#include \"foobar\"\n"
+            "#import <f/g.h>\n"
+            "@import AAAA;\n"
+            "@import aaaa;\n",
+            sort("#import \"b.h\"\n"
+                 "@import Foundation;\n"
+                 "@import foundation;\n"
+                 "#import \"c.h\"\n"
+                 "#import <d/e.h>\n"
+                 "@import Base;\n"
+                 "#import \"foo.hpp\"\n"
+                 "\n"
+                 "@import aaaa;\n"
+                 "#import <f/g.h>\n"
+                 "@import AAAA;\n"
+                 "#include \"foobar\"\n"
+                 "#import \"foo.h\"\n",
+                 "foo.c", 2));
+
+  // Regrouping and putting @import's in the very last group
+  FmtStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
+  EXPECT_EQ("#import \"foo.hpp\"\n"
+            "\n"
+            "#import \"b.h\"\n"
+            "#import \"c.h\"\n"
+            "#import \"foo.h\"\n"
+            "#include \"foobar\"\n"
+            "\n"
+            "#import <d/e.h>\n"
+            "#import <f/g.h>\n"
+            "\n"
+            "@import AAAA;\n"
+            "@import Base;\n"
+            "@import Foundation;\n"
+            "@import aaaa;\n"
+            "@import foundation;\n",
+            sort("#import \"b.h\"\n"
+                 "@import Foundation;\n"
+                 "@import foundation;\n"
+                 "#import \"c.h\"\n"
+                 "#import <d/e.h>\n"
+                 "@import Base;\n"
+                 "#import \"foo.hpp\"\n"
+                 "\n"
+                 "@import aaaa;\n"
+                 "#import <f/g.h>\n"
+                 "@import AAAA;\n"
+                 "#include \"foobar\"\n"
+                 "#import \"foo.h\"\n",
+                 "foo.c"));
+}
+
 TEST_F(SortIncludesTest, LeavesMainHeaderFirst) {
   Style.IncludeIsMainRegex = "([-_](test|unittest))?$";
   EXPECT_EQ("#include \"llvm/a.h\"\n"
             "#include \"b.h\"\n"
             "#include \"c.h\"\n",
             sort("#include \"llvm/a.h\"\n"
                  "#include \"c.h\"\n"
                  "#include \"b.h\"\n",