clang-format: [JS] Sort imported symbols.

[mprobst]

Summary

E.g. sort import {b, a} from 'x'; into import {a, b} from 'x';.

[mprobst]

• extract method for readability

[djasper]

In general, this is lacking test cases for imports that are wrapped over multiple lines to start with. Should probably add those both for the old and for the new behavior.

lib/Format/Format.cpp

1229 ↗

(On Diff #59001)

I think it's not even worth storing this variable now.

lib/Format/SortJavaScriptImports.cpp

46 ↗

(On Diff #59001)

Maybe add a comment on why you are ignoring 'Range' for comparison.

168 ↗

(On Diff #59001)

nit: no braces

232 ↗

(On Diff #59001)

I think it's safe to pass the symbols as const reference here.

[mprobst]

Done regarding the tests. We do have an unrelated issue with formatting import {x as foo}, will send a fix later.

[mprobst]

• multiline tests, review comments

[mprobst]

Done regarding the tests. We do have an unrelated issue with formatting import {x as foo}, will send a fix later.

[djasper]

lib/Format/SortJavaScriptImports.cpp

248 ↗

(On Diff #59070)

It's an implementation detail that the iterator of a SmallVector is a JsImportedSymbol*. Use auto. Also, I find this more readable:

for (auto I = Symbols.begin(), E = Symbols.end(); I != E; ++I) {
  if (I != Symbols.begin())
    Buffer += ",";
  Buffer += getSourceText(I->Range);
}

cfe/trunk/lib/Format/Format.cpp

 #include "clang/Basic/VirtualFileSystem.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/YAMLTraits.h"
+#include <algorithm>
 #include <memory>
 #include <queue>
 #include <string>
 
 #define DEBUG_TYPE "format-formatter"
 
 using clang::format::FormatStyle;
 
static void sortCppIncludes(const FormatStyle &Style,
   std::stable_sort(
       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
       });
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
-  bool OutOfOrder = false;
-  for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
-    if (Indices[i] != i) {
-      OutOfOrder = true;
-      break;
-    }
-  }
-  if (!OutOfOrder)
+  if (std::is_sorted(Indices.begin(), Indices.end()))
     return;
 
   std::string result;
   bool CursorMoved = false;
   for (unsigned Index : Indices) {
     if (!result.empty())
       result += "\n";
     result += Includes[Index].Text;

cfe/trunk/lib/Format/SortJavaScriptImports.cpp

 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Format/Format.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
+#include <algorithm>
 #include <string>
 
 #define DEBUG_TYPE "format-formatter"
 
 namespace clang {
 namespace format {
 
 class FormatTokenLexer;
 
 using clang::format::FormatStyle;
 
 // An imported symbol in a JavaScript ES6 import/export, possibly aliased.
 struct JsImportedSymbol {
   StringRef Symbol;
   StringRef Alias;
+  SourceRange Range;
+
+  bool operator==(const JsImportedSymbol &RHS) const {
+    // Ignore Range for comparison, it is only used to stitch code together,
+    // but imports at different code locations are still conceptually the same.
+    return Symbol == RHS.Symbol && Alias == RHS.Alias;
+  }
 };
 
 // An ES6 module reference.
 //
 // ES6 implements a module system, where individual modules (~= source files)
 // can reference other modules, either importing symbols from them, or exporting
 // symbols from them:
 //   import {foo} from 'foo';
analyze(TokenAnnotator &Annotator,
 
     SmallVector<unsigned, 16> Indices;
     for (unsigned i = 0, e = References.size(); i != e; ++i)
       Indices.push_back(i);
     std::stable_sort(Indices.begin(), Indices.end(),
                      [&](unsigned LHSI, unsigned RHSI) {
                        return References[LHSI] < References[RHSI];
                      });
-    // FIXME: Pull this into a common function.
-    bool OutOfOrder = false;
-    for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
-      if (i != Indices[i]) {
-        OutOfOrder = true;
-        break;
-      }
-    }
-    if (!OutOfOrder)
-      return Result;
+    bool ReferencesInOrder = std::is_sorted(Indices.begin(), Indices.end());
 
-    // Replace all existing import/export statements.
     std::string ReferencesText;
+    bool SymbolsInOrder = true;
     for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
       JsModuleReference Reference = References[Indices[i]];
-      StringRef ReferenceStmt = getSourceText(Reference.Range);
-      ReferencesText += ReferenceStmt;
+      if (appendReference(ReferencesText, Reference))
+        SymbolsInOrder = false;
       if (i + 1 < e) {
         // Insert breaks between imports and exports.
         ReferencesText += "\n";
         // Separate imports groups with two line breaks, but keep all exports
         // in a single group.
         if (!Reference.IsExport &&
             (Reference.IsExport != References[Indices[i + 1]].IsExport ||
              Reference.Category != References[Indices[i + 1]].Category))
           ReferencesText += "\n";
       }
     }
+
+    if (ReferencesInOrder && SymbolsInOrder)
+      return Result;
+
     // Separate references from the main code body of the file.
     if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2)
       ReferencesText += "\n";
 
     SourceRange InsertionPoint = References[0].Range;
     InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());
     DEBUG(llvm::dbgs() << "Replacing imports:\n"
                        << getSourceText(InsertionPoint) << "\nwith:\n"
if (!Current || Current == LineEnd->Next) {
       // Set the current token to an invalid token, so that further parsing on
       // this line fails.
       invalidToken.Tok.setKind(tok::unknown);
       Current = &invalidToken;
     }
   }
 
   StringRef getSourceText(SourceRange Range) {
+    return getSourceText(Range.getBegin(), Range.getEnd());
+  }
+
+  StringRef getSourceText(SourceLocation Begin, SourceLocation End) {
     const SourceManager &SM = Env.getSourceManager();
-    return FileContents.substr(SM.getFileOffset(Range.getBegin()),
-                               SM.getFileOffset(Range.getEnd()) -
-                                   SM.getFileOffset(Range.getBegin()));
+    return FileContents.substr(SM.getFileOffset(Begin),
+                               SM.getFileOffset(End) - SM.getFileOffset(Begin));
+  }
+
+  // Appends ``Reference`` to ``Buffer``, returning true if text within the
+  // ``Reference`` changed (e.g. symbol order).
+  bool appendReference(std::string &Buffer, JsModuleReference &Reference) {
+    // Sort the individual symbols within the import.
+    // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`
+    SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols;
+    std::stable_sort(
+        Symbols.begin(), Symbols.end(),
+        [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
+          return LHS.Symbol < RHS.Symbol;
+        });
+    if (Symbols == Reference.Symbols) {
+      // No change in symbol order.
+      StringRef ReferenceStmt = getSourceText(Reference.Range);
+      Buffer += ReferenceStmt;
+      return false;
+    }
+    // Stitch together the module reference start...
+    SourceLocation SymbolsStart = Reference.Symbols.front().Range.getBegin();
+    SourceLocation SymbolsEnd = Reference.Symbols.back().Range.getEnd();
+    Buffer += getSourceText(Reference.Range.getBegin(), SymbolsStart);
+    // ... then the references in order ...
+    for (auto *I = Symbols.begin(), *E = Symbols.end(); I != E; ++I) {
+      if (I != Symbols.begin())
+        Buffer += ",";
+      Buffer += getSourceText(I->Range);
+    }
+    // ... followed by the module reference end.
+    Buffer += getSourceText(SymbolsEnd, Reference.Range.getEnd());
+    return true;
   }
 
   // Parses module references in the given lines. Returns the module references,
   // and a pointer to the first "main code" line if that is adjacent to the
   // affected lines of module references, nullptr otherwise.
   std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine*>
   parseModuleReferences(const AdditionalKeywords &Keywords,
                         SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
bool parseNamedBindings(const AdditionalKeywords &Keywords,
     // {sym as alias, sym2 as ...} from '...';
     nextToken();
     while (true) {
       if (Current->isNot(tok::identifier))
         return false;
 
       JsImportedSymbol Symbol;
       Symbol.Symbol = Current->TokenText;
+      // Make sure to include any preceding comments.
+      Symbol.Range.setBegin(
+          Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());
       nextToken();
 
       if (Current->is(Keywords.kw_as)) {
         nextToken();
         if (Current->isNot(tok::identifier))
           return false;
         Symbol.Alias = Current->TokenText;
         nextToken();
       }
+      Symbol.Range.setEnd(Current->Tok.getLocation());
       Reference.Symbols.push_back(Symbol);
 
       if (Current->is(tok::r_brace))
         return true;
       if (Current->isNot(tok::comma))
         return false;
       nextToken();
     }

cfe/trunk/unittests/Format/SortImportsTestJS.cpp

verifySort("import {sym} from 'a';\n"
              "\n"
              "let x = 1;",
              "import {sym} from 'a';\n"
              "import {sym} from 'c';\n"
              "import {sym} from 'b';\n"
              "let x = 1;");
 }
 
+TEST_F(SortImportsTestJS, WrappedImportStatements) {
+  verifySort("import {sym1, sym2} from 'a';\n"
+             "import {sym} from 'b';\n"
+             "\n"
+             "1;",
+             "import\n"
+             "  {sym}\n"
+             "  from 'b';\n"
+             "import {\n"
+             "  sym1,\n"
+             "  sym2\n"
+             "} from 'a';\n"
+             "1;");
+}
+
 TEST_F(SortImportsTestJS, SeparateMainCodeBody) {
   verifySort("import {sym} from 'a';"
              "\n"
              "let x = 1;\n",
              "import {sym} from 'a'; let x = 1;\n");
 }
 
 TEST_F(SortImportsTestJS, Comments) {

 
 TEST_F(SortImportsTestJS, AliasesSymbols) {
   verifySort("import {sym1 as alias1} from 'b';\n"
              "import {sym2 as alias2, sym3 as alias3} from 'c';\n",
              "import {sym2 as alias2, sym3 as alias3} from 'c';\n"
              "import {sym1 as alias1} from 'b';\n");
 }
 
+TEST_F(SortImportsTestJS, SortSymbols) {
+  verifySort("import {sym1, sym2 as a, sym3} from 'b';\n",
+             "import {sym2 as a, sym1, sym3} from 'b';\n");
+  verifySort("import {sym1 /* important! */, /*!*/ sym2 as a} from 'b';\n",
+             "import {/*!*/ sym2 as a, sym1 /* important! */} from 'b';\n");
+  verifySort("import {sym1, sym2} from 'b';\n", "import {\n"
+                                                "  sym2 \n"
+                                                ",\n"
+                                                " sym1 \n"
+                                                "} from 'b';\n");
+}
+
 TEST_F(SortImportsTestJS, GroupImports) {
   verifySort("import {a} from 'absolute';\n"
              "\n"
              "import {b} from '../parent';\n"
              "import {b} from '../parent/nested';\n"
              "\n"
              "import {b} from './relative/path';\n"
              "import {b} from './relative/path/nested';\n"