1 //===--- SortJavaScriptImports.cpp - Sort ES6 Imports -----------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This file implements a sort operation for JavaScript ES6 imports.
12 //===----------------------------------------------------------------------===//
14 #include "SortJavaScriptImports.h"
15 #include "TokenAnalyzer.h"
16 #include "TokenAnnotator.h"
17 #include "clang/Basic/Diagnostic.h"
18 #include "clang/Basic/DiagnosticOptions.h"
19 #include "clang/Basic/LLVM.h"
20 #include "clang/Basic/SourceLocation.h"
21 #include "clang/Basic/SourceManager.h"
22 #include "clang/Basic/TokenKinds.h"
23 #include "clang/Format/Format.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/Support/Debug.h"
30 #define DEBUG_TYPE "format-formatter"
35 class FormatTokenLexer
;
37 using clang::format::FormatStyle
;
39 // An imported symbol in a JavaScript ES6 import/export, possibly aliased.
40 struct JsImportedSymbol
{
45 bool operator==(const JsImportedSymbol
&RHS
) const {
46 // Ignore Range for comparison, it is only used to stitch code together,
47 // but imports at different code locations are still conceptually the same.
48 return Symbol
== RHS
.Symbol
&& Alias
== RHS
.Alias
;
52 // An ES6 module reference.
54 // ES6 implements a module system, where individual modules (~= source files)
55 // can reference other modules, either importing symbols from them, or exporting
57 // import {foo} from 'foo';
59 // export {bar} from 'bar';
61 // `export`s with URLs are syntactic sugar for an import of the symbol from the
62 // URL, followed by an export of the symbol, allowing this code to treat both
63 // statements more or less identically, with the exception being that `export`s
66 // imports and exports support individual symbols, but also a wildcard syntax:
67 // import * as prefix from 'foo';
68 // export * from 'bar';
70 // This struct represents both exports and imports to build up the information
71 // required for sorting module references.
72 struct JsModuleReference
{
73 bool FormattingOff
= false;
74 bool IsExport
= false;
75 bool IsTypeOnly
= false;
76 // Module references are sorted into these categories, in order.
77 enum ReferenceCategory
{
78 SIDE_EFFECT
, // "import 'something';"
79 ABSOLUTE
, // from 'something'
80 RELATIVE_PARENT
, // from '../*'
81 RELATIVE
, // from './*'
82 ALIAS
, // import X = A.B;
84 ReferenceCategory Category
= ReferenceCategory::SIDE_EFFECT
;
85 // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
87 // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
88 // Implies an empty names list.
90 // Default import from "import DefaultName from '...';".
91 StringRef DefaultImport
;
92 // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.
93 SmallVector
<JsImportedSymbol
, 1> Symbols
;
94 // Whether some symbols were merged into this one. Controls if the module
95 // reference needs re-formatting.
96 bool SymbolsMerged
= false;
97 // The source location just after { and just before } in the import.
98 // Extracted eagerly to allow modification of Symbols later on.
99 SourceLocation SymbolsStart
, SymbolsEnd
;
100 // Textual position of the import/export, including preceding and trailing
105 bool operator<(const JsModuleReference
&LHS
, const JsModuleReference
&RHS
) {
106 if (LHS
.IsExport
!= RHS
.IsExport
)
107 return LHS
.IsExport
< RHS
.IsExport
;
108 if (LHS
.Category
!= RHS
.Category
)
109 return LHS
.Category
< RHS
.Category
;
110 if (LHS
.Category
== JsModuleReference::ReferenceCategory::SIDE_EFFECT
||
111 LHS
.Category
== JsModuleReference::ReferenceCategory::ALIAS
) {
112 // Side effect imports and aliases might be ordering sensitive. Consider
113 // them equal so that they maintain their relative order in the stable sort
114 // below. This retains transitivity because LHS.Category == RHS.Category
118 // Empty URLs sort *last* (for export {...};).
119 if (LHS
.URL
.empty() != RHS
.URL
.empty())
120 return LHS
.URL
.empty() < RHS
.URL
.empty();
121 if (int Res
= LHS
.URL
.compare_insensitive(RHS
.URL
))
123 // '*' imports (with prefix) sort before {a, b, ...} imports.
124 if (LHS
.Prefix
.empty() != RHS
.Prefix
.empty())
125 return LHS
.Prefix
.empty() < RHS
.Prefix
.empty();
126 if (LHS
.Prefix
!= RHS
.Prefix
)
127 return LHS
.Prefix
> RHS
.Prefix
;
131 // JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is
132 // implemented as a TokenAnalyzer because ES6 imports have substantial syntactic
133 // structure, making it messy to sort them using regular expressions.
134 class JavaScriptImportSorter
: public TokenAnalyzer
{
136 JavaScriptImportSorter(const Environment
&Env
, const FormatStyle
&Style
)
137 : TokenAnalyzer(Env
, Style
),
138 FileContents(Env
.getSourceManager().getBufferData(Env
.getFileID())) {
139 // FormatToken.Tok starts out in an uninitialized state.
140 invalidToken
.Tok
.startToken();
143 std::pair
<tooling::Replacements
, unsigned>
144 analyze(TokenAnnotator
&Annotator
,
145 SmallVectorImpl
<AnnotatedLine
*> &AnnotatedLines
,
146 FormatTokenLexer
&Tokens
) override
{
147 tooling::Replacements Result
;
148 AffectedRangeMgr
.computeAffectedLines(AnnotatedLines
);
150 const AdditionalKeywords
&Keywords
= Tokens
.getKeywords();
151 SmallVector
<JsModuleReference
, 16> References
;
152 AnnotatedLine
*FirstNonImportLine
;
153 std::tie(References
, FirstNonImportLine
) =
154 parseModuleReferences(Keywords
, AnnotatedLines
);
156 if (References
.empty())
159 // The text range of all parsed imports, to be replaced later.
160 SourceRange InsertionPoint
= References
[0].Range
;
161 InsertionPoint
.setEnd(References
[References
.size() - 1].Range
.getEnd());
163 References
= sortModuleReferences(References
);
165 std::string ReferencesText
;
166 for (unsigned I
= 0, E
= References
.size(); I
!= E
; ++I
) {
167 JsModuleReference Reference
= References
[I
];
168 appendReference(ReferencesText
, Reference
);
170 // Insert breaks between imports and exports.
171 ReferencesText
+= "\n";
172 // Separate imports groups with two line breaks, but keep all exports
173 // in a single group.
174 if (!Reference
.IsExport
&&
175 (Reference
.IsExport
!= References
[I
+ 1].IsExport
||
176 Reference
.Category
!= References
[I
+ 1].Category
)) {
177 ReferencesText
+= "\n";
181 llvm::StringRef PreviousText
= getSourceText(InsertionPoint
);
182 if (ReferencesText
== PreviousText
)
185 // The loop above might collapse previously existing line breaks between
186 // import blocks, and thus shrink the file. SortIncludes must not shrink
187 // overall source length as there is currently no re-calculation of ranges
188 // after applying source sorting.
189 // This loop just backfills trailing spaces after the imports, which are
190 // harmless and will be stripped by the subsequent formatting pass.
191 // FIXME: A better long term fix is to re-calculate Ranges after sorting.
192 unsigned PreviousSize
= PreviousText
.size();
193 while (ReferencesText
.size() < PreviousSize
)
194 ReferencesText
+= " ";
196 // Separate references from the main code body of the file.
197 if (FirstNonImportLine
&& FirstNonImportLine
->First
->NewlinesBefore
< 2 &&
198 !(FirstNonImportLine
->First
->is(tok::comment
) &&
199 isClangFormatOn(FirstNonImportLine
->First
->TokenText
.trim()))) {
200 ReferencesText
+= "\n";
203 LLVM_DEBUG(llvm::dbgs() << "Replacing imports:\n"
204 << PreviousText
<< "\nwith:\n"
205 << ReferencesText
<< "\n");
206 auto Err
= Result
.add(tooling::Replacement(
207 Env
.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint
),
209 // FIXME: better error handling. For now, just print error message and skip
210 // the replacement for the release version.
212 llvm::errs() << llvm::toString(std::move(Err
)) << "\n";
220 FormatToken
*Current
= nullptr;
221 FormatToken
*LineEnd
= nullptr;
223 FormatToken invalidToken
;
225 StringRef FileContents
;
227 void skipComments() { Current
= skipComments(Current
); }
229 FormatToken
*skipComments(FormatToken
*Tok
) {
230 while (Tok
&& Tok
->is(tok::comment
))
236 Current
= Current
->Next
;
238 if (!Current
|| Current
== LineEnd
->Next
) {
239 // Set the current token to an invalid token, so that further parsing on
241 Current
= &invalidToken
;
245 StringRef
getSourceText(SourceRange Range
) {
246 return getSourceText(Range
.getBegin(), Range
.getEnd());
249 StringRef
getSourceText(SourceLocation Begin
, SourceLocation End
) {
250 const SourceManager
&SM
= Env
.getSourceManager();
251 return FileContents
.substr(SM
.getFileOffset(Begin
),
252 SM
.getFileOffset(End
) - SM
.getFileOffset(Begin
));
255 // Sorts the given module references.
256 // Imports can have formatting disabled (FormattingOff), so the code below
257 // skips runs of "no-formatting" module references, and sorts/merges the
258 // references that have formatting enabled in individual chunks.
259 SmallVector
<JsModuleReference
, 16>
260 sortModuleReferences(const SmallVector
<JsModuleReference
, 16> &References
) {
261 // Sort module references.
262 // Imports can have formatting disabled (FormattingOff), so the code below
263 // skips runs of "no-formatting" module references, and sorts other
264 // references per group.
265 const auto *Start
= References
.begin();
266 SmallVector
<JsModuleReference
, 16> ReferencesSorted
;
267 while (Start
!= References
.end()) {
268 while (Start
!= References
.end() && Start
->FormattingOff
) {
269 // Skip over all imports w/ disabled formatting.
270 ReferencesSorted
.push_back(*Start
);
273 SmallVector
<JsModuleReference
, 16> SortChunk
;
274 while (Start
!= References
.end() && !Start
->FormattingOff
) {
275 // Skip over all imports w/ disabled formatting.
276 SortChunk
.push_back(*Start
);
279 llvm::stable_sort(SortChunk
);
280 mergeModuleReferences(SortChunk
);
281 ReferencesSorted
.insert(ReferencesSorted
.end(), SortChunk
.begin(),
284 return ReferencesSorted
;
287 // Merge module references.
288 // After sorting, find all references that import named symbols from the
289 // same URL and merge their names. E.g.
290 // import {X} from 'a';
291 // import {Y} from 'a';
292 // should be rewritten to:
293 // import {X, Y} from 'a';
294 // Note: this modifies the passed in ``References`` vector (by removing no
295 // longer needed references).
296 void mergeModuleReferences(SmallVector
<JsModuleReference
, 16> &References
) {
297 if (References
.empty())
299 JsModuleReference
*PreviousReference
= References
.begin();
300 auto *Reference
= std::next(References
.begin());
301 while (Reference
!= References
.end()) {
304 // import * as foo from 'foo'; on either previous or this.
305 // import Default from 'foo'; on either previous or this.
307 if (Reference
->Category
== JsModuleReference::SIDE_EFFECT
||
308 PreviousReference
->Category
== JsModuleReference::SIDE_EFFECT
||
309 Reference
->IsExport
!= PreviousReference
->IsExport
||
310 Reference
->IsTypeOnly
!= PreviousReference
->IsTypeOnly
||
311 !PreviousReference
->Prefix
.empty() || !Reference
->Prefix
.empty() ||
312 !PreviousReference
->DefaultImport
.empty() ||
313 !Reference
->DefaultImport
.empty() || Reference
->Symbols
.empty() ||
314 PreviousReference
->URL
!= Reference
->URL
) {
315 PreviousReference
= Reference
;
319 // Merge symbols from identical imports.
320 PreviousReference
->Symbols
.append(Reference
->Symbols
);
321 PreviousReference
->SymbolsMerged
= true;
322 // Remove the merged import.
323 Reference
= References
.erase(Reference
);
327 // Appends ``Reference`` to ``Buffer``.
328 void appendReference(std::string
&Buffer
, JsModuleReference
&Reference
) {
329 if (Reference
.FormattingOff
) {
331 getSourceText(Reference
.Range
.getBegin(), Reference
.Range
.getEnd());
334 // Sort the individual symbols within the import.
335 // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`
336 SmallVector
<JsImportedSymbol
, 1> Symbols
= Reference
.Symbols
;
338 Symbols
, [&](const JsImportedSymbol
&LHS
, const JsImportedSymbol
&RHS
) {
339 return LHS
.Symbol
.compare_insensitive(RHS
.Symbol
) < 0;
341 if (!Reference
.SymbolsMerged
&& Symbols
== Reference
.Symbols
) {
342 // Symbols didn't change, just emit the entire module reference.
343 StringRef ReferenceStmt
= getSourceText(Reference
.Range
);
344 Buffer
+= ReferenceStmt
;
347 // Stitch together the module reference start...
348 Buffer
+= getSourceText(Reference
.Range
.getBegin(), Reference
.SymbolsStart
);
349 // ... then the references in order ...
350 if (!Symbols
.empty()) {
351 Buffer
+= getSourceText(Symbols
.front().Range
);
352 for (const JsImportedSymbol
&Symbol
: llvm::drop_begin(Symbols
)) {
354 Buffer
+= getSourceText(Symbol
.Range
);
357 // ... followed by the module reference end.
358 Buffer
+= getSourceText(Reference
.SymbolsEnd
, Reference
.Range
.getEnd());
361 // Parses module references in the given lines. Returns the module references,
362 // and a pointer to the first "main code" line if that is adjacent to the
363 // affected lines of module references, nullptr otherwise.
364 std::pair
<SmallVector
<JsModuleReference
, 16>, AnnotatedLine
*>
365 parseModuleReferences(const AdditionalKeywords
&Keywords
,
366 SmallVectorImpl
<AnnotatedLine
*> &AnnotatedLines
) {
367 SmallVector
<JsModuleReference
, 16> References
;
368 SourceLocation Start
;
369 AnnotatedLine
*FirstNonImportLine
= nullptr;
370 bool AnyImportAffected
= false;
371 bool FormattingOff
= false;
372 for (auto *Line
: AnnotatedLines
) {
374 Current
= Line
->First
;
375 LineEnd
= Line
->Last
;
376 // clang-format comments toggle formatting on/off.
377 // This is tracked in FormattingOff here and on JsModuleReference.
378 while (Current
&& Current
->is(tok::comment
)) {
379 StringRef CommentText
= Current
->TokenText
.trim();
380 if (isClangFormatOff(CommentText
)) {
381 FormattingOff
= true;
382 } else if (isClangFormatOn(CommentText
)) {
383 FormattingOff
= false;
384 // Special case: consider a trailing "clang-format on" line to be part
385 // of the module reference, so that it gets moved around together with
386 // it (as opposed to the next module reference, which might get sorted
388 if (!References
.empty()) {
389 References
.back().Range
.setEnd(Current
->Tok
.getEndLoc());
390 Start
= Current
->Tok
.getEndLoc().getLocWithOffset(1);
393 // Handle all clang-format comments on a line, e.g. for an empty block.
394 Current
= Current
->Next
;
397 if (Start
.isInvalid() || References
.empty()) {
398 // After the first file level comment, consider line comments to be part
399 // of the import that immediately follows them by using the previously
401 Start
= Line
->First
->Tok
.getLocation();
404 // Only comments on this line. Could be the first non-import line.
405 FirstNonImportLine
= Line
;
408 JsModuleReference Reference
;
409 Reference
.FormattingOff
= FormattingOff
;
410 Reference
.Range
.setBegin(Start
);
411 // References w/o a URL, e.g. export {A}, groups with RELATIVE.
412 Reference
.Category
= JsModuleReference::ReferenceCategory::RELATIVE
;
413 if (!parseModuleReference(Keywords
, Reference
)) {
414 if (!FirstNonImportLine
)
415 FirstNonImportLine
= Line
; // if no comment before.
418 FirstNonImportLine
= nullptr;
419 AnyImportAffected
= AnyImportAffected
|| Line
->Affected
;
420 Reference
.Range
.setEnd(LineEnd
->Tok
.getEndLoc());
422 llvm::dbgs() << "JsModuleReference: {"
423 << "formatting_off: " << Reference
.FormattingOff
424 << ", is_export: " << Reference
.IsExport
425 << ", cat: " << Reference
.Category
426 << ", url: " << Reference
.URL
427 << ", prefix: " << Reference
.Prefix
;
428 for (const JsImportedSymbol
&Symbol
: Reference
.Symbols
)
429 llvm::dbgs() << ", " << Symbol
.Symbol
<< " as " << Symbol
.Alias
;
430 llvm::dbgs() << ", text: " << getSourceText(Reference
.Range
);
431 llvm::dbgs() << "}\n";
433 References
.push_back(Reference
);
434 Start
= SourceLocation();
436 // Sort imports if any import line was affected.
437 if (!AnyImportAffected
)
439 return std::make_pair(References
, FirstNonImportLine
);
442 // Parses a JavaScript/ECMAScript 6 module reference.
443 // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules
444 // for grammar EBNF (production ModuleItem).
445 bool parseModuleReference(const AdditionalKeywords
&Keywords
,
446 JsModuleReference
&Reference
) {
447 if (!Current
|| !Current
->isOneOf(Keywords
.kw_import
, tok::kw_export
))
449 Reference
.IsExport
= Current
->is(tok::kw_export
);
452 if (Current
->isStringLiteral() && !Reference
.IsExport
) {
453 // "import 'side-effect';"
454 Reference
.Category
= JsModuleReference::ReferenceCategory::SIDE_EFFECT
;
456 Current
->TokenText
.substr(1, Current
->TokenText
.size() - 2);
460 if (!parseModuleBindings(Keywords
, Reference
))
463 if (Current
->is(Keywords
.kw_from
)) {
464 // imports have a 'from' clause, exports might not.
466 if (!Current
->isStringLiteral())
468 // URL = TokenText without the quotes.
470 Current
->TokenText
.substr(1, Current
->TokenText
.size() - 2);
471 if (Reference
.URL
.startswith("..")) {
473 JsModuleReference::ReferenceCategory::RELATIVE_PARENT
;
474 } else if (Reference
.URL
.startswith(".")) {
475 Reference
.Category
= JsModuleReference::ReferenceCategory::RELATIVE
;
477 Reference
.Category
= JsModuleReference::ReferenceCategory::ABSOLUTE
;
483 bool parseModuleBindings(const AdditionalKeywords
&Keywords
,
484 JsModuleReference
&Reference
) {
485 if (parseStarBinding(Keywords
, Reference
))
487 return parseNamedBindings(Keywords
, Reference
);
490 bool parseStarBinding(const AdditionalKeywords
&Keywords
,
491 JsModuleReference
&Reference
) {
492 // * as prefix from '...';
493 if (Current
->is(Keywords
.kw_type
) && Current
->Next
&&
494 Current
->Next
->is(tok::star
)) {
495 Reference
.IsTypeOnly
= true;
498 if (Current
->isNot(tok::star
))
501 if (Current
->isNot(Keywords
.kw_as
))
504 if (Current
->isNot(tok::identifier
))
506 Reference
.Prefix
= Current
->TokenText
;
511 bool parseNamedBindings(const AdditionalKeywords
&Keywords
,
512 JsModuleReference
&Reference
) {
513 if (Current
->is(Keywords
.kw_type
) && Current
->Next
&&
514 Current
->Next
->isOneOf(tok::identifier
, tok::l_brace
)) {
515 Reference
.IsTypeOnly
= true;
519 // eat a potential "import X, " prefix.
520 if (!Reference
.IsExport
&& Current
->is(tok::identifier
)) {
521 Reference
.DefaultImport
= Current
->TokenText
;
523 if (Current
->is(Keywords
.kw_from
))
526 if (Current
->is(tok::equal
)) {
527 Reference
.Category
= JsModuleReference::ReferenceCategory::ALIAS
;
529 while (Current
->is(tok::identifier
)) {
531 if (Current
->is(tok::semi
))
533 if (Current
->isNot(tok::period
))
538 if (Current
->isNot(tok::comma
))
540 nextToken(); // eat comma.
542 if (Current
->isNot(tok::l_brace
))
545 // {sym as alias, sym2 as ...} from '...';
546 Reference
.SymbolsStart
= Current
->Tok
.getEndLoc();
547 while (Current
->isNot(tok::r_brace
)) {
549 if (Current
->is(tok::r_brace
))
551 auto IsIdentifier
= [](const auto *Tok
) {
552 return Tok
->isOneOf(tok::identifier
, tok::kw_default
, tok::kw_template
);
554 bool isTypeOnly
= Current
->is(Keywords
.kw_type
) && Current
->Next
&&
555 IsIdentifier(Current
->Next
);
556 if (!isTypeOnly
&& !IsIdentifier(Current
))
559 JsImportedSymbol Symbol
;
560 // Make sure to include any preceding comments.
561 Symbol
.Range
.setBegin(
562 Current
->getPreviousNonComment()->Next
->WhitespaceRange
.getBegin());
565 Symbol
.Symbol
= Current
->TokenText
;
568 if (Current
->is(Keywords
.kw_as
)) {
570 if (!IsIdentifier(Current
))
572 Symbol
.Alias
= Current
->TokenText
;
575 Symbol
.Range
.setEnd(Current
->Tok
.getLocation());
576 Reference
.Symbols
.push_back(Symbol
);
578 if (!Current
->isOneOf(tok::r_brace
, tok::comma
))
581 Reference
.SymbolsEnd
= Current
->Tok
.getLocation();
582 // For named imports with a trailing comma ("import {X,}"), consider the
583 // comma to be the end of the import list, so that it doesn't get removed.
584 if (Current
->Previous
->is(tok::comma
))
585 Reference
.SymbolsEnd
= Current
->Previous
->Tok
.getLocation();
586 nextToken(); // consume r_brace
591 tooling::Replacements
sortJavaScriptImports(const FormatStyle
&Style
,
593 ArrayRef
<tooling::Range
> Ranges
,
594 StringRef FileName
) {
595 // FIXME: Cursor support.
596 auto Env
= Environment::make(Code
, FileName
, Ranges
);
599 return JavaScriptImportSorter(*Env
, Style
).process().first
;
602 } // end namespace format
603 } // end namespace clang