[clang-format] Modified SortIncludes and IncludeCategories to priority for sorting #includes within the Group Category.

[Manikishan]

Summary

This new Style rule is made as a part of adding support for NetBSD KNF in clang-format. NetBSD have it's own priority of includes which should be followed while formatting NetBSD code. This style sorts the Cpp Includes according to the priorities of NetBSD, as mentioned in the Style Guide
The working of this Style rule shown below:

Configuration:
This revision introduces a new field under IncludeCategories named SortPriority which defines the priority of ordering the #includes and the Priority will define the categories for grouping the #include blocks.

Here is an example how this Style sorts cpp includes according to NetBSD KNF.
Before Formatting:

#include <sys/param.h>		
#include <sys/types.h>		
#include <sys/ioctl.h>		
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>
#include <sys/socket.h>		
#include <sys/stat.h>
#include <sys/wait.h>		
#include <net/if.h>
#include <protocols/rwhod.h>
#include <assert.h>
#include <paths.h>
#include "pathnames.h"		
#include <errno.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

After Formatting:

#include <sys/param.h>
#include <sys/types.h>
#include <sys/ioctl.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/wait.h>

#include <net/if.h>
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>
#include <protocols/rwhod.h>

#include <assert.h>
#include <errno.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

#include <paths.h>

#include "pathnames.h"

[Manikishan]

This is the squashed commit of both Adding NetBSD Style and adding sortNetBSDIncludes

[MyDeveloperDay]

Do you think there is anything about this algorithm that could be parameterized so that other projects could utilize it? I guess its not completely clear how this differs from just using the IncludeCategories?

[Manikishan]

In D64695#1584630, @MyDeveloperDay wrote:

Do you think there is anything about this algorithm that could be parameterized so that other projects could utilize it?

I think we can take input from users the header files which should be grouped together and pass them to regex searches which then sets up priority.
But I dob the feasibility of this approach. Will come up with one.

I guess its not completely clear how this differs from just using the IncludeCategories?

This style works only via NetBSD includes order instead of alphabetical .

[MyDeveloperDay]

There also seems like alot of duplication between the existing sortCppIncludes

I think the only difference here is really just

SmallVector<unsigned, 16> Indices;
  SmallVector<unsigned, 16> Includes_p;
  for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
    unsigned pl = getNetBSDIncludePriority(Includes[i].Filename);
    Includes_p.push_back(pl);
    Indices.push_back(i);
  }

vs the original

SmallVector<unsigned, 16> Indices;
for (unsigned i = 0, e = Includes.size(); i != e; ++i)
  Indices.push_back(i);

plus way the sorting is performed, are we sure we couldn't have just made the original sorting more powerful based on style settings?

lib/Format/Format.cpp

1878 ↗

(On Diff #209685)

_p? I don't understand what it stands for?

IncludesPriority?

[Manikishan]

In D64695#1584706, @MyDeveloperDay wrote:

There also seems like alot of duplication between the existing sortCppIncludes

I think the only difference here is really just

SmallVector<unsigned, 16> Indices;
  SmallVector<unsigned, 16> Includes_p;
  for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
    unsigned pl = getNetBSDIncludePriority(Includes[i].Filename);
    Includes_p.push_back(pl);
    Indices.push_back(i);
  }

vs the original

SmallVector<unsigned, 16> Indices;
for (unsigned i = 0, e = Includes.size(); i != e; ++i)
  Indices.push_back(i);

plus way the sorting is performed, are we sure we couldn't have just made the original sorting more powerful based on style settings?

Does it mean that adding the priority to sort based on style?
like this:

if (Style== NetBSD)
   // set priority to netbsd's priority
else if(Style == X)
  // set X's priority

I didn't want to mess up the original sorting and made up this patch, if we have parameterise this solution, I will go for it.

lib/Format/Format.cpp

1878 ↗

(On Diff #209685)

Yes , it means priority

[MyDeveloperDay]

In D64695#1584740, @Manikishan wrote:

In D64695#1584706, @MyDeveloperDay wrote:

There also seems like alot of duplication between the existing sortCppIncludes

I think the only difference here is really just

SmallVector<unsigned, 16> Indices;
  SmallVector<unsigned, 16> Includes_p;
  for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
    unsigned pl = getNetBSDIncludePriority(Includes[i].Filename);
    Includes_p.push_back(pl);
    Indices.push_back(i);
  }

vs the original

SmallVector<unsigned, 16> Indices;
for (unsigned i = 0, e = Includes.size(); i != e; ++i)
  Indices.push_back(i);

plus way the sorting is performed, are we sure we couldn't have just made the original sorting more powerful based on style settings?

Does it mean that adding the priority to sort based on style?
like this:

if (Style== NetBSD)
   // set priority to netbsd's priority
else if(Style == X)
  // set X's priority

I didn't want to mess up the original sorting and made up this patch, if we have parameterise this solution, I will go for it.

We should be able to make changes without fear of breaking other code, if we can't then we don't have enough tests

I guess my comment was that you patche introduces a lot of code duplication, could the small amount of code you added be say put into a lambda and past in based on style?

lib/Format/Format.cpp

1878 ↗

(On Diff #209685)

I don't think Includes_p matches Clang naming conventions so I recommend changing it.

[MyDeveloperDay]

unittests/Format/SortIncludesTest.cpp

709 ↗

(On Diff #209685)

should you add a test which has groups defined already, I'm unclear as to how your algorithm works across groups?

[Manikishan]

unittests/Format/SortIncludesTest.cpp

709 ↗

(On Diff #209685)

The include groups in NetBSD files are made depending on the use, for example
Kernel headers, File systems headers, Network and protocol headers are grouped together.
My algorithm is to detect the include type by regex and assign a priority to them to sort. And to regroup I used IncludeCategories.

[Manikishan]

I guess my comment was that you patche introduces a lot of code duplication, could the small amount of code you added be say put into a lambda and past in based on style?

Yes, I will add that and submit a patch soon.

[Manikishan]

Is this change that was meant?

[rdwampler]

I am not quite sure why this change is required to sort the headers for NetBSD, you can set the priorities via IncludeStyle.IncludeCategories. Is that not sufficient?

[Manikishan]

In D64695#1585754, @rdwampler wrote:

I am not quite sure why this change is required to sort the headers for NetBSD, you can set the priorities via IncludeStyle.IncludeCategories. Is that not sufficient?

It can be done by setting priorities in IncludeCategories, but here we have nearly 40+ cases and categories to hardcode due to complex interdependencies between their headers. So, I have added this style reducing the cases using regex. And if this is fully parameterised any other related project can add their own header priorities.

[lebedev.ri]

In D64695#1585772, @Manikishan wrote:

In D64695#1585754, @rdwampler wrote:

I am not quite sure why this change is required to sort the headers for NetBSD, you can set the priorities via IncludeStyle.IncludeCategories. Is that not sufficient?

It can be done by setting priorities in IncludeCategories, but here we have nearly 40+ cases and categories to hardcode due to complex interdependencies between their headers. So, I have added this style reducing the cases using regex. And if this is fully parameterised any OS related project can add their own header priorities.

Note that IncludeCategories is already a regex - https://clang.llvm.org/docs/ClangFormatStyleOptions.html

[Manikishan]

In D64695#1585835, @lebedev.ri wrote:

In D64695#1585772, @Manikishan wrote:

In D64695#1585754, @rdwampler wrote:

I am not quite sure why this change is required to sort the headers for NetBSD, you can set the priorities via IncludeStyle.IncludeCategories. Is that not sufficient?

It can be done by setting priorities in IncludeCategories, but here we have nearly 40+ cases and categories to hardcode due to complex interdependencies between their headers. So, I have added this style reducing the cases using regex. And if this is fully parameterised any OS related project can add their own header priorities.

Note that IncludeCategories is already a regex - https://clang.llvm.org/docs/ClangFormatStyleOptions.html

Sorry, my mistake I meant that I have added Regex for priorities while sorting and If I am not wrong I think IncludeCategories are used while Regrouping after sorting the Includes. In addition to that in my case I have to sort the includes In a particular order then grouping them in different
For example:

#include <sys/param.h>		/* <sys/param.h> first, */
#include <sys/types.h>		/*   <sys/types.h> next, */
#include <sys/ioctl.h>		/*   and then the rest, */
#include <uvm/*.h>
#include <dev/*.h>

#include <net/if.h>
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>
#include <protocols/rwhod.h>

As shown in the above example <uvm> should follow <sys> then <dev> but while regrouping they should be in the same group.

[rdwampler]

Sorry, my mistake I meant that I have added Regex for priorities while sorting and If I am not wrong I think IncludeCategories are used while Regrouping after sorting the Includes. In addition to that in my case I have to sort the includes In a particular order then grouping them in different
For example:

#include <sys/param.h>		/* <sys/param.h> first, */
#include <sys/types.h>		/*   <sys/types.h> next, */
#include <sys/ioctl.h>		/*   and then the rest, */
#include <uvm/*.h>
#include <dev/*.h>

#include <net/if.h>
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>
#include <protocols/rwhod.h>

As shown in the above example <uvm> should follow <sys> then <dev> but while regrouping they should be in the same group.

OK. I think I understand. Since <sys/param.h> and <sys/types.h> have to come first we would need to set the regex and priorities for those individually. But then those will be treated as separate block and grouped like:

#include <sys/param.h>

#include <sys/types.h>

#include <sys/ioctl.h>
more <sys/*> includes

I wonder if a better approach would be to extend IncludeCatalog to allow the grouping to specified independent of the regex?

E.g., { "{<sys/param.h>", 0, 1 }, // priority 1, group 1

    {<sys/types.h>, 1, 1, }, // different priority, but same group
   {<sys/*>, 2, 1}  // more general headers with lower priority, but will still be grouped in group 1.
}

[MyDeveloperDay]

I appreciate what you've done to make this patch less duplicated code..but now you've almost got to the point where being able to control it all via configuration.

I'm with @rdwampler I think you should be able to extend the include categories...and then this becomes a very powerful capability. There are many people who use clang-format for a "non" standard style source trees, and they might like to use such a capability themselves without having to inherit from NetBSD type.

I agree it will be complex, but that is a good justification for adding hard coded a NetBSD style.

lib/Format/Format.cpp

1905 ↗

(On Diff #209873)

remove

[Manikishan]

In D64695#1586157, @MyDeveloperDay wrote:

I appreciate what you've done to make this patch less duplicated code..but now you've almost got to the point where being able to control it all via configuration.

I'm with @rdwampler I think you should be able to extend the include categories...and then this becomes a very powerful capability. There are many people who use clang-format for a "non" standard style source trees, and they might like to use such a capability themselves without having to inherit from NetBSD type.

I agree it will be complex, but that is a good justification for adding hard coded a NetBSD style.

Thanks, I will try to implement it as suggested.
This is my proposal algorithm:

1. Modify Include.Categories by adding one more field for grouping priority.
2. Add support for this third field in sortIncludes.

Am I missing anything?

[Manikishan]

In the following patch I have modified Include categories by adding a new field "sortInlcudes" which defines the priority of the sort. And priority field will now only be used for grouping.

[rdwampler]

Thanks! Can you update the documentation too?

lib/Tooling/Inclusions/HeaderIncludes.cpp

211 ↗

(On Diff #210218)

I think you can drop the else block and just return immediately from the for loop.

[Manikishan]

In D64695#1589497, @rdwampler wrote:

Thanks! Can you update the documentation too?

Thanks!
So, is this Implementation fine? But there is a thing, The values which we give two Priority does not really matter they need to be different to be in different groups. Is that ok? and should I Rename any options?.

[lebedev.ri]

Is there sufficient test coverage as to what happens if SortPriority is not set?

lib/Format/Format.cpp

455–456 ↗

(On Diff #210218)

Unrelated change

613–614 ↗

(On Diff #210218)

Unrelated change

692–693 ↗

(On Diff #210218)

Unrelated change

[Manikishan]

In D64695#1589508, @lebedev.ri wrote:

Is there sufficient test coverage as to what happens if SortPriority is not set?

If SortPriority is not set, the Includes will be grouped without sorting,

For example:

#include <sys/param.h>
#include <sys/types.h>
#include <sys/ioctl.h>
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <net/if.h>
#include <protocols/rwhod.h>
#include <assert.h>
#include <paths.h>
#include "pathnames.h"
#include <errno.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

will be grouped as

#include "pathnames.h"

#include <assert.h>
#include <errno.h>
#include <inttypes.h>

#include <net/if.h>
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>

#include <paths.h>

#include <protocols/rwhod.h>

#include <stdio.h>
#include <stdlib.h>

#include <sys/ioctl.h>
#include <sys/param.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/wait.h>

Can we add a test case for this and mention that users should set SortPriority, or handle this case some how?
One way can be when the values are not set their Priority value is set as SortPriority, but this is also a problem
when users give SortPriority as "0". Any comments on this issue?

[lebedev.ri]

In D64695#1589740, @Manikishan wrote:

In D64695#1589508, @lebedev.ri wrote:

Is there sufficient test coverage as to what happens if SortPriority is not set?

If SortPriority is not set, the Includes will be grouped without sorting,

Let me rephrase - for the exiting .clang-formats, that don't currently specify SortPriority,
this introduction of SortPriority should not change the header handling.
Is that the case, and if so is there sufficient test coverage for that?

[Manikishan]

In D64695#1589818, @lebedev.ri wrote:

In D64695#1589740, @Manikishan wrote:

In D64695#1589508, @lebedev.ri wrote:

Is there sufficient test coverage as to what happens if SortPriority is not set?

If SortPriority is not set, the Includes will be grouped without sorting,

Let me rephrase - for the exiting .clang-formats, that don't currently specify SortPriority,
this introduction of SortPriority should not change the header handling.
Is that the case, and if so is there sufficient test coverage for that?

I got your idea now.
No, there is no test coverage for that case, and with the current patch they have to add SortPriority.
To avoid this shall I set SortPriority as Priority as default if it is not defined? I think that will fix the issue.

[Manikishan]

In D64695#1590948, @Manikishan wrote:

In D64695#1589818, @lebedev.ri wrote:

In D64695#1589740, @Manikishan wrote:

In D64695#1589508, @lebedev.ri wrote:

Is there sufficient test coverage as to what happens if SortPriority is not set?

If SortPriority is not set, the Includes will be grouped without sorting,

Let me rephrase - for the exiting .clang-formats, that don't currently specify SortPriority,
this introduction of SortPriority should not change the header handling.
Is that the case, and if so is there sufficient test coverage for that?

I got your idea now.
No, there is no test coverage for that case, and with the current patch they have to add SortPriority.
To avoid this shall I set SortPriority as Priority as default if it is not defined? I think that will fix the issue.

any reviews on it ?

[rdwampler]

In D64695#1605676, @Manikishan wrote:

In D64695#1590948, @Manikishan wrote:

In D64695#1589818, @lebedev.ri wrote:

In D64695#1589740, @Manikishan wrote:

In D64695#1589508, @lebedev.ri wrote:

Is there sufficient test coverage as to what happens if SortPriority is not set?

If SortPriority is not set, the Includes will be grouped without sorting,

Let me rephrase - for the exiting .clang-formats, that don't currently specify SortPriority,
this introduction of SortPriority should not change the header handling.
Is that the case, and if so is there sufficient test coverage for that?

I got your idea now.
No, there is no test coverage for that case, and with the current patch they have to add SortPriority.
To avoid this shall I set SortPriority as Priority as default if it is not defined? I think that will fix the issue.

any reviews on it ?

That's sounds like it will work. Can you add some additional test cases around this in SortIncludesTest.cpp. Also, adding a test case specifically for sorting the NetBSD headers would be good.

[Manikishan]

In D64695#1606256, @rdwampler wrote:

In D64695#1605676, @Manikishan wrote:

In D64695#1590948, @Manikishan wrote:

In D64695#1589818, @lebedev.ri wrote:

In D64695#1589740, @Manikishan wrote:

In D64695#1589508, @lebedev.ri wrote:

Is there sufficient test coverage as to what happens if SortPriority is not set?

If SortPriority is not set, the Includes will be grouped without sorting,

Let me rephrase - for the exiting .clang-formats, that don't currently specify SortPriority,
this introduction of SortPriority should not change the header handling.
Is that the case, and if so is there sufficient test coverage for that?

I got your idea now.
No, there is no test coverage for that case, and with the current patch they have to add SortPriority.
To avoid this shall I set SortPriority as Priority as default if it is not defined? I think that will fix the issue.

any reviews on it ?

That's sounds like it will work. Can you add some additional test cases around this in SortIncludesTest.cpp. Also, adding a test case specifically for sorting the NetBSD headers would be good.

Sorry for the delay, I am facing issues with "NoCrash_Bug34236" will update the patch once I am able to fix it.

[Manikishan]

Added Tests for using and not using SortPriority Field, Now, even if the SortPriorityis not set it will be set to the value of Category by default

[MyDeveloperDay]

Assuming this works and the other unit tests don't show issues then this LGTM. Please consider running this on your NetBSD code base before committing, if possible please also run on clang code based to ensure existing sorted headers aren't sorted unexpectedly.

I do feel like there could be a documentation change missing really to explain to people how this really works and what if anything they have to change in their existing .clang-format files

[lebedev.ri]

In D64695#1614386, @MyDeveloperDay wrote:

Assuming this works and the other unit tests don't show issues then this LGTM.

Please consider running this on your NetBSD code base before committing, if possible please also run on clang code based to ensure existing sorted headers aren't sorted unexpectedly.

Before this gets committed, i feel like echoing this - did you ensure that this doesn't regress existing code/configs?

I do feel like there could be a documentation change missing really to explain to people how this really works and what if anything they have to change in their existing .clang-format files

Oh, indeed, docs are completely missing. I think it is best to resolve this right away rather than afterwards.

[Manikishan]

In D64695#1614386, @MyDeveloperDay wrote:

Assuming this works and the other unit tests don't show issues then this LGTM. Please consider running this on your NetBSD code base before committing, if possible please also run on clang code based to ensure existing sorted headers aren't sorted unexpectedly.

I do feel like there could be a documentation change missing really to explain to people how this really works and what if anything they have to change in their existing .clang-format files

I wIll update the documentation soon, within a day. And I will also run it over both the clang, and netbsd code to make sure nothing goes wrong.

[Manikishan]

I have removed the introduction to the NetBSDStyle, as there are some styles that are needed to implemented before launching the NetBSD style.

[MyDeveloperDay]

LGTM

[MyDeveloperDay]

Does this need landing? given that you have a number of patches in flight perhaps it would be good to request commit access

[Manikishan]

>>! In D64695#1667696, @MyDeveloperDay wrote:

Does this need landing? given that you have a number of patches in flight perhaps it would be good to request commit access

Yes, it would be good if it is landed. And can I know the procedure for getting commit access

[MyDeveloperDay]

Yes, it would be good if it is landed. And can I know the procedure for getting commit access

https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

cfe/trunk/docs/ClangFormatStyleOptions.rst

**IncludeCategories** (``std::vector<IncludeCategory>``)
 
   If none of the regular expressions match, INT_MAX is assigned as
   category. The main header for a source file automatically gets category 0.
   so that it is generally kept at the beginning of the ``#includes``
   (https://llvm.org/docs/CodingStandards.html#include-style). However, you
   can also assign negative priorities if you have certain headers that
   always need to be first.
 
+  There is a third and optional field ``SortPriority`` which can used while
+  ``IncludeBloks = IBS_Regroup`` to define the priority in which ``#includes``
+  should be ordered, and value of ``Priority`` defines the order of
+  ``#include blocks`` and also enables to group ``#includes`` of different
+  priority for order.``SortPriority`` is set to the value of ``Priority``
+  as default if it is not assigned.
+
   To configure this in the .clang-format file, use:
 
   .. code-block:: yaml
 
     IncludeCategories:
       - Regex:           '^"(llvm|llvm-c|clang|clang-c)/'
         Priority:        2
+        SortPriority:    2
       - Regex:           '^(<|"(gtest|gmock|isl|json)/)'
         Priority:        3
       - Regex:           '<[[:alnum:].]+>'
         Priority:        4
       - Regex:           '.*'
         Priority:        1
+        SortPriority:    0
 
 **IncludeIsMainRegex** (``std::string``)
   Specify a regular expression of suffixes that are allowed in the
   file-to-main-include mapping.
 
   When guessing whether a #include is the "main" include (to assign
   category 0, see above), use this regex of allowed suffixes to the header
   stem. A partial match is done, so that:

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

 public:
   IncludeCategoryManager(const IncludeStyle &Style, StringRef FileName);
 
   /// Returns the priority of the category which \p IncludeName belongs to.
   /// If \p CheckMainHeader is true and \p IncludeName is a main header, returns
   /// 0. Otherwise, returns the priority of the matching category or INT_MAX.
   /// NOTE: this API is not thread-safe!
   int getIncludePriority(StringRef IncludeName, bool CheckMainHeader) const;
+  int getSortIncludePriority(StringRef IncludeName, bool CheckMainHeader) const;
 
 private:
   bool isMainHeader(StringRef IncludeName) const;
 
   const IncludeStyle Style;
   bool IsMainFile;
   std::string FileName;
   // This refers to a substring in FileName.

cfe/trunk/include/clang/Tooling/Inclusions/IncludeStyle.h

struct IncludeStyle {
   IncludeBlocksStyle IncludeBlocks;
 
   /// See documentation of ``IncludeCategories``.
   struct IncludeCategory {
     /// The regular expression that this category matches.
     std::string Regex;
     /// The priority to assign to this category.
     int Priority;
+    /// The custom priority to sort before grouping.
+    int SortPriority;
     bool operator==(const IncludeCategory &Other) const {
       return Regex == Other.Regex && Priority == Other.Priority;
     }
   };
 
   /// Regular expressions denoting the different ``#include`` categories
   /// used for ordering ``#includes``.
   ///

cfe/trunk/lib/Format/Format.cpp

private:
   bool IsObjC;
 };
 
 struct IncludeDirective {
   StringRef Filename;
   StringRef Text;
   unsigned Offset;
   int Category;
+  int Priority;
 };
 
 struct JavaImportDirective {
   StringRef Identifier;
   StringRef Text;
   unsigned Offset;
   std::vector<StringRef> AssociatedCommentLines;
   bool IsStatic;

 // first #include in the duplicate #includes remains. If the `Cursor` is
 // provided and put on a deleted #include, it will be moved to the remaining
 // #include in the duplicate #includes.
 static void sortCppIncludes(const FormatStyle &Style,
                             const SmallVectorImpl<IncludeDirective> &Includes,
                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
                             StringRef Code, tooling::Replacements &Replaces,
                             unsigned *Cursor) {
+  tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
   unsigned IncludesBeginOffset = Includes.front().Offset;
   unsigned IncludesEndOffset =
       Includes.back().Offset + Includes.back().Text.size();
   unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
   if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
     return;
   SmallVector<unsigned, 16> Indices;
-  for (unsigned i = 0, e = Includes.size(); i != e; ++i)
+  for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
     Indices.push_back(i);
+  }
   llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
-    return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
-           std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
+    return std::tie(Includes[LHSI].Priority, Includes[LHSI].Filename) <
+           std::tie(Includes[RHSI].Priority, Includes[RHSI].Filename);
   });
   // The index of the include on which the cursor will be put after
   // sorting/deduplicating.
   unsigned CursorIndex;
   // The offset from cursor to the end of line.
   unsigned CursorToEOLOffset;
   if (Cursor)
     std::tie(CursorIndex, CursorToEOLOffset) =
const bool EmptyLineSkipped =
              tooling::IncludeStyle::IBS_Regroup);
 
     if (!FormattingOff && !Line.endswith("\\")) {
       if (IncludeRegex.match(Line, &Matches)) {
         StringRef IncludeName = Matches[2];
         int Category = Categories.getIncludePriority(
             IncludeName,
             /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
+        int Priority = Categories.getSortIncludePriority(
+            IncludeName, !MainIncludeFound && FirstIncludeBlock);
         if (Category == 0)
           MainIncludeFound = true;
-        IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
+        IncludesInBlock.push_back(
+            {IncludeName, Line, Prev, Category, Priority});
       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
         sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
                         Replaces, Cursor);
         IncludesInBlock.clear();
         FirstIncludeBlock = false;
       }
       Prev = Pos + 1;
     }

cfe/trunk/lib/Tooling/Inclusions/HeaderIncludes.cpp

if (CategoryRegexs[i].match(IncludeName)) {
       Ret = Style.IncludeCategories[i].Priority;
       break;
     }
   if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
     Ret = 0;
   return Ret;
 }
 
+int IncludeCategoryManager::getSortIncludePriority(StringRef IncludeName,
+                                                   bool CheckMainHeader) const {
+  int Ret = INT_MAX;
+  for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
+    if (CategoryRegexs[i].match(IncludeName)) {
+      Ret = Style.IncludeCategories[i].SortPriority;
+      if (Ret == 0)
+        Ret = Style.IncludeCategories[i].Priority;
+      break;
+    }
+  if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
+    Ret = 0;
+  return Ret;
+}
 bool IncludeCategoryManager::isMainHeader(StringRef IncludeName) const {
   if (!IncludeName.startswith("\""))
     return false;
   StringRef HeaderStem =
       llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
   if (FileStem.startswith(HeaderStem) ||
       FileStem.startswith_lower(HeaderStem)) {
     llvm::Regex MainIncludeRegex(HeaderStem.str() + Style.IncludeIsMainRegex,

cfe/trunk/lib/Tooling/Inclusions/IncludeStyle.cpp

 
 namespace llvm {
 namespace yaml {
 
 void MappingTraits<IncludeStyle::IncludeCategory>::mapping(
     IO &IO, IncludeStyle::IncludeCategory &Category) {
   IO.mapOptional("Regex", Category.Regex);
   IO.mapOptional("Priority", Category.Priority);
+  IO.mapOptional("SortPriority", Category.SortPriority);
 }
 
 void ScalarEnumerationTraits<IncludeStyle::IncludeBlocksStyle>::enumeration(
     IO &IO, IncludeStyle::IncludeBlocksStyle &Value) {
   IO.enumCase(Value, "Preserve", IncludeStyle::IBS_Preserve);
   IO.enumCase(Value, "Merge", IncludeStyle::IBS_Merge);
   IO.enumCase(Value, "Regroup", IncludeStyle::IBS_Regroup);
 }
 
 } // namespace yaml
 } // namespace llvm

cfe/trunk/unittests/Format/SortIncludesTest.cpp

EXPECT_EQ("// comment\n"
             "#include <a>\n"
             "#include <b>\n",
             sort("// comment\n"
                  "#include <b>\n"
                  "#include <a>\n",
                  {tooling::Range(25, 1)}));
 }
 
+TEST_F(SortIncludesTest, SortedIncludesUsingSortPriorityAttribute) {
+  FmtStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
+  FmtStyle.IncludeStyle.IncludeCategories = {
+      {"^<sys/param\\.h>", 1, 0},
+      {"^<sys/types\\.h>", 1, 1},
+      {"^<sys.*/", 1, 2},
+      {"^<uvm/", 2, 3},
+      {"^<machine/", 3, 4},
+      {"^<dev/", 4, 5},
+      {"^<net.*/", 5, 6},
+      {"^<protocols/", 5, 7},
+      {"^<(fs|miscfs|msdosfs|nfs|ntfs|ufs)/", 6, 8},
+      {"^<(x86|amd64|i386|xen)/", 7, 8},
+      {"<path", 9, 11},
+      {"^<[^/].*\\.h>", 8, 10},
+      {"^\".*\\.h\"", 10, 12}};
+  EXPECT_EQ("#include <sys/param.h>\n"
+            "#include <sys/types.h>\n"
+            "#include <sys/ioctl.h>\n"
+            "#include <sys/socket.h>\n"
+            "#include <sys/stat.h>\n"
+            "#include <sys/wait.h>\n"
+            "\n"
+            "#include <net/if.h>\n"
+            "#include <net/if_dl.h>\n"
+            "#include <net/route.h>\n"
+            "#include <netinet/in.h>\n"
+            "#include <protocols/rwhod.h>\n"
+            "\n"
+            "#include <assert.h>\n"
+            "#include <errno.h>\n"
+            "#include <inttypes.h>\n"
+            "#include <stdio.h>\n"
+            "#include <stdlib.h>\n"
+            "\n"
+            "#include <paths.h>\n"
+            "\n"
+            "#include \"pathnames.h\"\n",
+            sort("#include <sys/param.h>\n"
+                 "#include <sys/types.h>\n"
+                 "#include <sys/ioctl.h>\n"
+                 "#include <net/if_dl.h>\n"
+                 "#include <net/route.h>\n"
+                 "#include <netinet/in.h>\n"
+                 "#include <sys/socket.h>\n"
+                 "#include <sys/stat.h>\n"
+                 "#include <sys/wait.h>\n"
+                 "#include <net/if.h>\n"
+                 "#include <protocols/rwhod.h>\n"
+                 "#include <assert.h>\n"
+                 "#include <paths.h>\n"
+                 "#include \"pathnames.h\"\n"
+                 "#include <errno.h>\n"
+                 "#include <inttypes.h>\n"
+                 "#include <stdio.h>\n"
+                 "#include <stdlib.h>\n"));
+}
+TEST_F(SortIncludesTest, SortPriorityNotDefined) {
+  FmtStyle = getLLVMStyle();
+  EXPECT_EQ("#include \"FormatTestUtils.h\"\n"
+            "#include \"clang/Format/Format.h\"\n"
+            "#include \"llvm/ADT/None.h\"\n"
+            "#include \"llvm/Support/Debug.h\"\n"
+            "#include \"gtest/gtest.h\"\n",
+            sort("#include \"clang/Format/Format.h\"\n"
+                 "#include \"llvm/ADT/None.h\"\n"
+                 "#include \"FormatTestUtils.h\"\n"
+                 "#include \"gtest/gtest.h\"\n"
+                 "#include \"llvm/Support/Debug.h\"\n"));
+}
+
 TEST_F(SortIncludesTest, NoReplacementsForValidIncludes) {
   // Identical #includes have led to a failure with an unstable sort.
   std::string Code = "#include <a>\n"
                      "#include <b>\n"
                      "#include <c>\n"
                      "#include <d>\n"
                      "#include <e>\n"
                      "#include <f>\n";