1//===--- SortJavaScriptImports.cpp - Sort ES6 Imports -----------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements a sort operation for JavaScript ES6 imports.
11///
12//===----------------------------------------------------------------------===//
13
14#include "SortJavaScriptImports.h"
15#include "TokenAnalyzer.h"
16#include "TokenAnnotator.h"
17#include "clang/Basic/Diagnostic.h"
18#include "clang/Basic/LLVM.h"
19#include "clang/Basic/SourceLocation.h"
20#include "clang/Basic/SourceManager.h"
21#include "clang/Basic/TokenKinds.h"
22#include "clang/Format/Format.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/Support/Debug.h"
26#include <string>
27
28#define DEBUG_TYPE "format-formatter"
29
30namespace clang {
31namespace format {
32
33class FormatTokenLexer;
34
35// An imported symbol in a JavaScript ES6 import/export, possibly aliased.
36struct JsImportedSymbol {
37 StringRef Symbol;
38 StringRef Alias;
39 SourceRange Range;
40
41 bool operator==(const JsImportedSymbol &RHS) const {
42 // Ignore Range for comparison, it is only used to stitch code together,
43 // but imports at different code locations are still conceptually the same.
44 return Symbol == RHS.Symbol && Alias == RHS.Alias;
45 }
46};
47
48// An ES6 module reference.
49//
50// ES6 implements a module system, where individual modules (~= source files)
51// can reference other modules, either importing symbols from them, or exporting
52// symbols from them:
53// import {foo} from 'foo';
54// export {foo};
55// export {bar} from 'bar';
56//
57// `export`s with URLs are syntactic sugar for an import of the symbol from the
58// URL, followed by an export of the symbol, allowing this code to treat both
59// statements more or less identically, with the exception being that `export`s
60// are sorted last.
61//
62// imports and exports support individual symbols, but also a wildcard syntax:
63// import * as prefix from 'foo';
64// export * from 'bar';
65//
66// This struct represents both exports and imports to build up the information
67// required for sorting module references.
68struct JsModuleReference {
69 bool FormattingOff = false;
70 bool IsExport = false;
71 bool IsTypeOnly = false;
72 // Module references are sorted into these categories, in order.
73 enum ReferenceCategory {
74 SIDE_EFFECT, // "import 'something';"
75 ABSOLUTE, // from 'something'
76 RELATIVE_PARENT, // from '../*'
77 RELATIVE, // from './*'
78 ALIAS, // import X = A.B;
79 };
80 ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;
81 // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
82 StringRef URL;
83 // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
84 // Implies an empty names list.
85 StringRef Prefix;
86 // Default import from "import DefaultName from '...';".
87 StringRef DefaultImport;
88 // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.
89 SmallVector<JsImportedSymbol, 1> Symbols;
90 // Whether some symbols were merged into this one. Controls if the module
91 // reference needs re-formatting.
92 bool SymbolsMerged = false;
93 // The source location just after { and just before } in the import.
94 // Extracted eagerly to allow modification of Symbols later on.
95 SourceLocation SymbolsStart, SymbolsEnd;
96 // Textual position of the import/export, including preceding and trailing
97 // comments.
98 SourceRange Range;
99};
100
101bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS) {
102 if (LHS.IsExport != RHS.IsExport)
103 return LHS.IsExport < RHS.IsExport;
104 if (LHS.Category != RHS.Category)
105 return LHS.Category < RHS.Category;
106 if (LHS.Category == JsModuleReference::ReferenceCategory::SIDE_EFFECT ||
107 LHS.Category == JsModuleReference::ReferenceCategory::ALIAS) {
108 // Side effect imports and aliases might be ordering sensitive. Consider
109 // them equal so that they maintain their relative order in the stable sort
110 // below. This retains transitivity because LHS.Category == RHS.Category
111 // here.
112 return false;
113 }
114 // Empty URLs sort *last* (for export {...};).
115 if (LHS.URL.empty() != RHS.URL.empty())
116 return LHS.URL.empty() < RHS.URL.empty();
117 if (int Res = LHS.URL.compare_insensitive(RHS: RHS.URL))
118 return Res < 0;
119 // '*' imports (with prefix) sort before {a, b, ...} imports.
120 if (LHS.Prefix.empty() != RHS.Prefix.empty())
121 return LHS.Prefix.empty() < RHS.Prefix.empty();
122 if (LHS.Prefix != RHS.Prefix)
123 return LHS.Prefix > RHS.Prefix;
124 return false;
125}
126
127// JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is
128// implemented as a TokenAnalyzer because ES6 imports have substantial syntactic
129// structure, making it messy to sort them using regular expressions.
130class JavaScriptImportSorter : public TokenAnalyzer {
131public:
132 JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)
133 : TokenAnalyzer(Env, Style),
134 FileContents(Env.getSourceManager().getBufferData(FID: Env.getFileID())) {
135 // FormatToken.Tok starts out in an uninitialized state.
136 invalidToken.Tok.startToken();
137 }
138
139 std::pair<tooling::Replacements, unsigned>
140 analyze(TokenAnnotator &Annotator,
141 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
142 FormatTokenLexer &Tokens) override {
143 tooling::Replacements Result;
144 AffectedRangeMgr.computeAffectedLines(Lines&: AnnotatedLines);
145
146 const AdditionalKeywords &Keywords = Tokens.getKeywords();
147 SmallVector<JsModuleReference, 16> References;
148 AnnotatedLine *FirstNonImportLine;
149 std::tie(args&: References, args&: FirstNonImportLine) =
150 parseModuleReferences(Keywords, AnnotatedLines);
151
152 if (References.empty())
153 return {Result, 0};
154
155 // The text range of all parsed imports, to be replaced later.
156 SourceRange InsertionPoint = References[0].Range;
157 InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());
158
159 References = sortModuleReferences(References);
160
161 std::string ReferencesText;
162 for (unsigned I = 0, E = References.size(); I != E; ++I) {
163 JsModuleReference Reference = References[I];
164 appendReference(Buffer&: ReferencesText, Reference);
165 if (I + 1 < E) {
166 // Insert breaks between imports and exports.
167 ReferencesText += "\n";
168 // Separate imports groups with two line breaks, but keep all exports
169 // in a single group.
170 if (!Reference.IsExport &&
171 (Reference.IsExport != References[I + 1].IsExport ||
172 Reference.Category != References[I + 1].Category)) {
173 ReferencesText += "\n";
174 }
175 }
176 }
177 StringRef PreviousText = getSourceText(Range: InsertionPoint);
178 if (ReferencesText == PreviousText)
179 return {Result, 0};
180
181 // The loop above might collapse previously existing line breaks between
182 // import blocks, and thus shrink the file. SortIncludes must not shrink
183 // overall source length as there is currently no re-calculation of ranges
184 // after applying source sorting.
185 // This loop just backfills trailing spaces after the imports, which are
186 // harmless and will be stripped by the subsequent formatting pass.
187 // FIXME: A better long term fix is to re-calculate Ranges after sorting.
188 unsigned PreviousSize = PreviousText.size();
189 while (ReferencesText.size() < PreviousSize)
190 ReferencesText += " ";
191
192 // Separate references from the main code body of the file.
193 if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2 &&
194 !(FirstNonImportLine->First->is(Kind: tok::comment) &&
195 isClangFormatOn(Comment: FirstNonImportLine->First->TokenText.trim()))) {
196 ReferencesText += "\n";
197 }
198
199 LLVM_DEBUG(llvm::dbgs() << "Replacing imports:\n"
200 << PreviousText << "\nwith:\n"
201 << ReferencesText << "\n");
202 auto Err = Result.add(R: tooling::Replacement(
203 Env.getSourceManager(), CharSourceRange::getCharRange(R: InsertionPoint),
204 ReferencesText));
205 // FIXME: better error handling. For now, just print error message and skip
206 // the replacement for the release version.
207 if (Err) {
208 llvm::errs() << toString(E: std::move(Err)) << "\n";
209 assert(false);
210 }
211
212 return {Result, 0};
213 }
214
215private:
216 FormatToken *Current = nullptr;
217 FormatToken *LineEnd = nullptr;
218
219 FormatToken invalidToken;
220
221 StringRef FileContents;
222
223 void skipComments() { Current = skipComments(Tok: Current); }
224
225 FormatToken *skipComments(FormatToken *Tok) {
226 while (Tok && Tok->is(Kind: tok::comment))
227 Tok = Tok->Next;
228 return Tok;
229 }
230
231 void nextToken() {
232 Current = Current->Next;
233 skipComments();
234 if (!Current || Current == LineEnd->Next) {
235 // Set the current token to an invalid token, so that further parsing on
236 // this line fails.
237 Current = &invalidToken;
238 }
239 }
240
241 StringRef getSourceText(SourceRange Range) {
242 return getSourceText(Begin: Range.getBegin(), End: Range.getEnd());
243 }
244
245 StringRef getSourceText(SourceLocation Begin, SourceLocation End) {
246 const SourceManager &SM = Env.getSourceManager();
247 return FileContents.substr(Start: SM.getFileOffset(SpellingLoc: Begin),
248 N: SM.getFileOffset(SpellingLoc: End) - SM.getFileOffset(SpellingLoc: Begin));
249 }
250
251 // Sorts the given module references.
252 // Imports can have formatting disabled (FormattingOff), so the code below
253 // skips runs of "no-formatting" module references, and sorts/merges the
254 // references that have formatting enabled in individual chunks.
255 SmallVector<JsModuleReference, 16>
256 sortModuleReferences(const SmallVector<JsModuleReference, 16> &References) {
257 // Sort module references.
258 // Imports can have formatting disabled (FormattingOff), so the code below
259 // skips runs of "no-formatting" module references, and sorts other
260 // references per group.
261 const auto *Start = References.begin();
262 SmallVector<JsModuleReference, 16> ReferencesSorted;
263 while (Start != References.end()) {
264 while (Start != References.end() && Start->FormattingOff) {
265 // Skip over all imports w/ disabled formatting.
266 ReferencesSorted.push_back(Elt: *Start);
267 ++Start;
268 }
269 SmallVector<JsModuleReference, 16> SortChunk;
270 while (Start != References.end() && !Start->FormattingOff) {
271 // Skip over all imports w/ disabled formatting.
272 SortChunk.push_back(Elt: *Start);
273 ++Start;
274 }
275 stable_sort(Range&: SortChunk);
276 mergeModuleReferences(References&: SortChunk);
277 llvm::append_range(C&: ReferencesSorted, R&: SortChunk);
278 }
279 return ReferencesSorted;
280 }
281
282 // Merge module references.
283 // After sorting, find all references that import named symbols from the
284 // same URL and merge their names. E.g.
285 // import {X} from 'a';
286 // import {Y} from 'a';
287 // should be rewritten to:
288 // import {X, Y} from 'a';
289 // Note: this modifies the passed in ``References`` vector (by removing no
290 // longer needed references).
291 void mergeModuleReferences(SmallVector<JsModuleReference, 16> &References) {
292 if (References.empty())
293 return;
294 JsModuleReference *PreviousReference = References.begin();
295 auto *Reference = std::next(x: References.begin());
296 while (Reference != References.end()) {
297 // Skip:
298 // import 'foo';
299 // import * as foo from 'foo'; on either previous or this.
300 // import Default from 'foo'; on either previous or this.
301 // mismatching
302 if (Reference->Category == JsModuleReference::SIDE_EFFECT ||
303 PreviousReference->Category == JsModuleReference::SIDE_EFFECT ||
304 Reference->IsExport != PreviousReference->IsExport ||
305 Reference->IsTypeOnly != PreviousReference->IsTypeOnly ||
306 !PreviousReference->Prefix.empty() || !Reference->Prefix.empty() ||
307 !PreviousReference->DefaultImport.empty() ||
308 !Reference->DefaultImport.empty() || Reference->Symbols.empty() ||
309 PreviousReference->URL != Reference->URL) {
310 PreviousReference = Reference;
311 ++Reference;
312 continue;
313 }
314 // Merge symbols from identical imports.
315 PreviousReference->Symbols.append(RHS: Reference->Symbols);
316 PreviousReference->SymbolsMerged = true;
317 // Remove the merged import.
318 Reference = References.erase(CI: Reference);
319 }
320 }
321
322 // Appends ``Reference`` to ``Buffer``.
323 void appendReference(std::string &Buffer, JsModuleReference &Reference) {
324 if (Reference.FormattingOff) {
325 Buffer +=
326 getSourceText(Begin: Reference.Range.getBegin(), End: Reference.Range.getEnd());
327 return;
328 }
329 // Sort the individual symbols within the import.
330 // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`
331 SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols;
332 stable_sort(Range&: Symbols,
333 C: [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
334 return LHS.Symbol.compare_insensitive(RHS: RHS.Symbol) < 0;
335 });
336 if (!Reference.SymbolsMerged && Symbols == Reference.Symbols) {
337 // Symbols didn't change, just emit the entire module reference.
338 StringRef ReferenceStmt = getSourceText(Range: Reference.Range);
339 Buffer += ReferenceStmt;
340 return;
341 }
342 // Stitch together the module reference start...
343 Buffer += getSourceText(Begin: Reference.Range.getBegin(), End: Reference.SymbolsStart);
344 // ... then the references in order ...
345 if (!Symbols.empty()) {
346 Buffer += getSourceText(Range: Symbols.front().Range);
347 for (const JsImportedSymbol &Symbol : drop_begin(RangeOrContainer&: Symbols)) {
348 Buffer += ",";
349 Buffer += getSourceText(Range: Symbol.Range);
350 }
351 }
352 // ... followed by the module reference end.
353 Buffer += getSourceText(Begin: Reference.SymbolsEnd, End: Reference.Range.getEnd());
354 }
355
356 // Parses module references in the given lines. Returns the module references,
357 // and a pointer to the first "main code" line if that is adjacent to the
358 // affected lines of module references, nullptr otherwise.
359 std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine *>
360 parseModuleReferences(const AdditionalKeywords &Keywords,
361 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
362 SmallVector<JsModuleReference, 16> References;
363 SourceLocation Start;
364 AnnotatedLine *FirstNonImportLine = nullptr;
365 bool AnyImportAffected = false;
366 bool FormattingOff = false;
367 for (auto *Line : AnnotatedLines) {
368 assert(Line->First);
369 Current = Line->First;
370 LineEnd = Line->Last;
371 // clang-format comments toggle formatting on/off.
372 // This is tracked in FormattingOff here and on JsModuleReference.
373 while (Current && Current->is(Kind: tok::comment)) {
374 StringRef CommentText = Current->TokenText.trim();
375 if (isClangFormatOff(Comment: CommentText)) {
376 FormattingOff = true;
377 } else if (isClangFormatOn(Comment: CommentText)) {
378 FormattingOff = false;
379 // Special case: consider a trailing "clang-format on" line to be part
380 // of the module reference, so that it gets moved around together with
381 // it (as opposed to the next module reference, which might get sorted
382 // around).
383 if (!References.empty()) {
384 References.back().Range.setEnd(Current->Tok.getEndLoc());
385 Start = Current->Tok.getEndLoc().getLocWithOffset(Offset: 1);
386 }
387 }
388 // Handle all clang-format comments on a line, e.g. for an empty block.
389 Current = Current->Next;
390 }
391 skipComments();
392 if (Start.isInvalid() || References.empty()) {
393 // After the first file level comment, consider line comments to be part
394 // of the import that immediately follows them by using the previously
395 // set Start.
396 Start = Line->First->Tok.getLocation();
397 }
398 if (!Current) {
399 // Only comments on this line. Could be the first non-import line.
400 FirstNonImportLine = Line;
401 continue;
402 }
403 JsModuleReference Reference;
404 Reference.FormattingOff = FormattingOff;
405 Reference.Range.setBegin(Start);
406 // References w/o a URL, e.g. export {A}, groups with RELATIVE.
407 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
408 if (!parseModuleReference(Keywords, Reference)) {
409 if (!FirstNonImportLine)
410 FirstNonImportLine = Line; // if no comment before.
411 break;
412 }
413 FirstNonImportLine = nullptr;
414 AnyImportAffected = AnyImportAffected || Line->Affected;
415 Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
416 LLVM_DEBUG({
417 llvm::dbgs() << "JsModuleReference: {"
418 << "formatting_off: " << Reference.FormattingOff
419 << ", is_export: " << Reference.IsExport
420 << ", cat: " << Reference.Category
421 << ", url: " << Reference.URL
422 << ", prefix: " << Reference.Prefix;
423 for (const JsImportedSymbol &Symbol : Reference.Symbols)
424 llvm::dbgs() << ", " << Symbol.Symbol << " as " << Symbol.Alias;
425 llvm::dbgs() << ", text: " << getSourceText(Reference.Range);
426 llvm::dbgs() << "}\n";
427 });
428 References.push_back(Elt: Reference);
429 Start = SourceLocation();
430 }
431 // Sort imports if any import line was affected.
432 if (!AnyImportAffected)
433 References.clear();
434 return std::make_pair(x&: References, y&: FirstNonImportLine);
435 }
436
437 // Parses a JavaScript/ECMAScript 6 module reference.
438 // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules
439 // for grammar EBNF (production ModuleItem).
440 bool parseModuleReference(const AdditionalKeywords &Keywords,
441 JsModuleReference &Reference) {
442 if (!Current || !Current->isOneOf(K1: Keywords.kw_import, K2: tok::kw_export))
443 return false;
444 Reference.IsExport = Current->is(Kind: tok::kw_export);
445
446 nextToken();
447 if (Current->isStringLiteral() && !Reference.IsExport) {
448 // "import 'side-effect';"
449 Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
450 Reference.URL =
451 Current->TokenText.substr(Start: 1, N: Current->TokenText.size() - 2);
452 return true;
453 }
454
455 if (!parseModuleBindings(Keywords, Reference))
456 return false;
457
458 if (Current->is(II: Keywords.kw_from)) {
459 // imports have a 'from' clause, exports might not.
460 nextToken();
461 if (!Current->isStringLiteral())
462 return false;
463 // URL = TokenText without the quotes.
464 Reference.URL =
465 Current->TokenText.substr(Start: 1, N: Current->TokenText.size() - 2);
466 if (Reference.URL.starts_with(Prefix: "..")) {
467 Reference.Category =
468 JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
469 } else if (Reference.URL.starts_with(Prefix: ".")) {
470 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
471 } else {
472 Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
473 }
474 }
475 return true;
476 }
477
478 bool parseModuleBindings(const AdditionalKeywords &Keywords,
479 JsModuleReference &Reference) {
480 if (parseStarBinding(Keywords, Reference))
481 return true;
482 return parseNamedBindings(Keywords, Reference);
483 }
484
485 bool parseStarBinding(const AdditionalKeywords &Keywords,
486 JsModuleReference &Reference) {
487 // * as prefix from '...';
488 if (Current->is(II: Keywords.kw_type) && Current->Next &&
489 Current->Next->is(Kind: tok::star)) {
490 Reference.IsTypeOnly = true;
491 nextToken();
492 }
493 if (Current->isNot(Kind: tok::star))
494 return false;
495 nextToken();
496 if (Current->isNot(Kind: Keywords.kw_as))
497 return false;
498 nextToken();
499 if (Current->isNot(Kind: tok::identifier))
500 return false;
501 Reference.Prefix = Current->TokenText;
502 nextToken();
503 return true;
504 }
505
506 bool parseNamedBindings(const AdditionalKeywords &Keywords,
507 JsModuleReference &Reference) {
508 if (Current->is(II: Keywords.kw_type) && Current->Next &&
509 Current->Next->isOneOf(K1: tok::identifier, K2: tok::l_brace)) {
510 Reference.IsTypeOnly = true;
511 nextToken();
512 }
513
514 // eat a potential "import X, " prefix.
515 if (!Reference.IsExport && Current->is(Kind: tok::identifier)) {
516 Reference.DefaultImport = Current->TokenText;
517 nextToken();
518 if (Current->is(II: Keywords.kw_from))
519 return true;
520 // import X = A.B.C;
521 if (Current->is(Kind: tok::equal)) {
522 Reference.Category = JsModuleReference::ReferenceCategory::ALIAS;
523 nextToken();
524 while (Current->is(Kind: tok::identifier)) {
525 nextToken();
526 if (Current->is(Kind: tok::semi))
527 return true;
528 if (Current->isNot(Kind: tok::period))
529 return false;
530 nextToken();
531 }
532 }
533 if (Current->isNot(Kind: tok::comma))
534 return false;
535 nextToken(); // eat comma.
536 }
537 if (Current->isNot(Kind: tok::l_brace))
538 return false;
539
540 // {sym as alias, sym2 as ...} from '...';
541 Reference.SymbolsStart = Current->Tok.getEndLoc();
542 while (Current->isNot(Kind: tok::r_brace)) {
543 nextToken();
544 if (Current->is(Kind: tok::r_brace))
545 break;
546 auto IsIdentifier = [](const auto *Tok) {
547 return Tok->isOneOf(tok::identifier, tok::kw_default, tok::kw_template);
548 };
549 bool isTypeOnly = Current->is(II: Keywords.kw_type) && Current->Next &&
550 IsIdentifier(Current->Next);
551 if (!isTypeOnly && !IsIdentifier(Current))
552 return false;
553
554 JsImportedSymbol Symbol;
555 // Make sure to include any preceding comments.
556 Symbol.Range.setBegin(
557 Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());
558 if (isTypeOnly)
559 nextToken();
560 Symbol.Symbol = Current->TokenText;
561 nextToken();
562
563 if (Current->is(II: Keywords.kw_as)) {
564 nextToken();
565 if (!IsIdentifier(Current))
566 return false;
567 Symbol.Alias = Current->TokenText;
568 nextToken();
569 }
570 Symbol.Range.setEnd(Current->Tok.getLocation());
571 Reference.Symbols.push_back(Elt: Symbol);
572
573 if (!Current->isOneOf(K1: tok::r_brace, K2: tok::comma))
574 return false;
575 }
576 Reference.SymbolsEnd = Current->Tok.getLocation();
577 // For named imports with a trailing comma ("import {X,}"), consider the
578 // comma to be the end of the import list, so that it doesn't get removed.
579 if (Current->Previous->is(Kind: tok::comma))
580 Reference.SymbolsEnd = Current->Previous->Tok.getLocation();
581 nextToken(); // consume r_brace
582 return true;
583 }
584};
585
586tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
587 StringRef Code,
588 ArrayRef<tooling::Range> Ranges,
589 StringRef FileName) {
590 // FIXME: Cursor support.
591 auto Env = Environment::make(Code, FileName, Ranges);
592 if (!Env)
593 return {};
594 return JavaScriptImportSorter(*Env, Style).process().first;
595}
596
597} // end namespace format
598} // end namespace clang
599