1 //===--- SortJavaScriptImports.cpp - Sort ES6 Imports -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file implements a sort operation for JavaScript ES6 imports.
13 //===----------------------------------------------------------------------===//
15 #include "SortJavaScriptImports.h"
16 #include "TokenAnalyzer.h"
17 #include "TokenAnnotator.h"
18 #include "clang/Basic/Diagnostic.h"
19 #include "clang/Basic/DiagnosticOptions.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/Basic/SourceLocation.h"
22 #include "clang/Basic/SourceManager.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 IsExport = false;
74 // Module references are sorted into these categories, in order.
75 enum ReferenceCategory {
76 SIDE_EFFECT, // "import 'something';"
77 ABSOLUTE, // from 'something'
78 RELATIVE_PARENT, // from '../*'
79 RELATIVE, // from './*'
81 ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;
82 // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
84 // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
85 // Implies an empty names list.
87 // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.
88 SmallVector<JsImportedSymbol, 1> Symbols;
89 // Textual position of the import/export, including preceding and trailing
94 bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS) {
95 if (LHS.IsExport != RHS.IsExport)
96 return LHS.IsExport < RHS.IsExport;
97 if (LHS.Category != RHS.Category)
98 return LHS.Category < RHS.Category;
99 if (LHS.Category == JsModuleReference::ReferenceCategory::SIDE_EFFECT)
100 // Side effect imports might be ordering sensitive. Consider them equal so
101 // that they maintain their relative order in the stable sort below.
102 // This retains transitivity because LHS.Category == RHS.Category here.
104 // Empty URLs sort *last* (for export {...};).
105 if (LHS.URL.empty() != RHS.URL.empty())
106 return LHS.URL.empty() < RHS.URL.empty();
107 if (int Res = LHS.URL.compare_lower(RHS.URL))
109 // '*' imports (with prefix) sort before {a, b, ...} imports.
110 if (LHS.Prefix.empty() != RHS.Prefix.empty())
111 return LHS.Prefix.empty() < RHS.Prefix.empty();
112 if (LHS.Prefix != RHS.Prefix)
113 return LHS.Prefix > RHS.Prefix;
117 // JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is
118 // implemented as a TokenAnalyzer because ES6 imports have substantial syntactic
119 // structure, making it messy to sort them using regular expressions.
120 class JavaScriptImportSorter : public TokenAnalyzer {
122 JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)
123 : TokenAnalyzer(Env, Style),
124 FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) {}
126 std::pair<tooling::Replacements, unsigned>
127 analyze(TokenAnnotator &Annotator,
128 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
129 FormatTokenLexer &Tokens) override {
130 tooling::Replacements Result;
131 AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
132 AnnotatedLines.end());
134 const AdditionalKeywords &Keywords = Tokens.getKeywords();
135 SmallVector<JsModuleReference, 16> References;
136 AnnotatedLine *FirstNonImportLine;
137 std::tie(References, FirstNonImportLine) =
138 parseModuleReferences(Keywords, AnnotatedLines);
140 if (References.empty())
143 SmallVector<unsigned, 16> Indices;
144 for (unsigned i = 0, e = References.size(); i != e; ++i)
145 Indices.push_back(i);
146 std::stable_sort(Indices.begin(), Indices.end(),
147 [&](unsigned LHSI, unsigned RHSI) {
148 return References[LHSI] < References[RHSI];
150 bool ReferencesInOrder = std::is_sorted(Indices.begin(), Indices.end());
152 std::string ReferencesText;
153 bool SymbolsInOrder = true;
154 for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
155 JsModuleReference Reference = References[Indices[i]];
156 if (appendReference(ReferencesText, Reference))
157 SymbolsInOrder = false;
159 // Insert breaks between imports and exports.
160 ReferencesText += "\n";
161 // Separate imports groups with two line breaks, but keep all exports
162 // in a single group.
163 if (!Reference.IsExport &&
164 (Reference.IsExport != References[Indices[i + 1]].IsExport ||
165 Reference.Category != References[Indices[i + 1]].Category))
166 ReferencesText += "\n";
170 if (ReferencesInOrder && SymbolsInOrder)
173 SourceRange InsertionPoint = References[0].Range;
174 InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());
176 // The loop above might collapse previously existing line breaks between
177 // import blocks, and thus shrink the file. SortIncludes must not shrink
178 // overall source length as there is currently no re-calculation of ranges
179 // after applying source sorting.
180 // This loop just backfills trailing spaces after the imports, which are
181 // harmless and will be stripped by the subsequent formatting pass.
182 // FIXME: A better long term fix is to re-calculate Ranges after sorting.
183 unsigned PreviousSize = getSourceText(InsertionPoint).size();
184 while (ReferencesText.size() < PreviousSize) {
185 ReferencesText += " ";
188 // Separate references from the main code body of the file.
189 if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2)
190 ReferencesText += "\n";
192 DEBUG(llvm::dbgs() << "Replacing imports:\n"
193 << getSourceText(InsertionPoint) << "\nwith:\n"
194 << ReferencesText << "\n");
195 auto Err = Result.add(tooling::Replacement(
196 Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),
198 // FIXME: better error handling. For now, just print error message and skip
199 // the replacement for the release version.
201 llvm::errs() << llvm::toString(std::move(Err)) << "\n";
209 FormatToken *Current;
210 FormatToken *LineEnd;
212 FormatToken invalidToken;
214 StringRef FileContents;
216 void skipComments() { Current = skipComments(Current); }
218 FormatToken *skipComments(FormatToken *Tok) {
219 while (Tok && Tok->is(tok::comment))
225 Current = Current->Next;
227 if (!Current || Current == LineEnd->Next) {
228 // Set the current token to an invalid token, so that further parsing on
230 invalidToken.Tok.setKind(tok::unknown);
231 Current = &invalidToken;
235 StringRef getSourceText(SourceRange Range) {
236 return getSourceText(Range.getBegin(), Range.getEnd());
239 StringRef getSourceText(SourceLocation Begin, SourceLocation End) {
240 const SourceManager &SM = Env.getSourceManager();
241 return FileContents.substr(SM.getFileOffset(Begin),
242 SM.getFileOffset(End) - SM.getFileOffset(Begin));
245 // Appends ``Reference`` to ``Buffer``, returning true if text within the
246 // ``Reference`` changed (e.g. symbol order).
247 bool appendReference(std::string &Buffer, JsModuleReference &Reference) {
248 // Sort the individual symbols within the import.
249 // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`
250 SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols;
252 Symbols.begin(), Symbols.end(),
253 [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
254 return LHS.Symbol.compare_lower(RHS.Symbol) < 0;
256 if (Symbols == Reference.Symbols) {
257 // No change in symbol order.
258 StringRef ReferenceStmt = getSourceText(Reference.Range);
259 Buffer += ReferenceStmt;
262 // Stitch together the module reference start...
263 SourceLocation SymbolsStart = Reference.Symbols.front().Range.getBegin();
264 SourceLocation SymbolsEnd = Reference.Symbols.back().Range.getEnd();
265 Buffer += getSourceText(Reference.Range.getBegin(), SymbolsStart);
266 // ... then the references in order ...
267 for (auto I = Symbols.begin(), E = Symbols.end(); I != E; ++I) {
268 if (I != Symbols.begin())
270 Buffer += getSourceText(I->Range);
272 // ... followed by the module reference end.
273 Buffer += getSourceText(SymbolsEnd, Reference.Range.getEnd());
277 // Parses module references in the given lines. Returns the module references,
278 // and a pointer to the first "main code" line if that is adjacent to the
279 // affected lines of module references, nullptr otherwise.
280 std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine *>
281 parseModuleReferences(const AdditionalKeywords &Keywords,
282 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
283 SmallVector<JsModuleReference, 16> References;
284 SourceLocation Start;
285 AnnotatedLine *FirstNonImportLine = nullptr;
286 bool AnyImportAffected = false;
287 for (auto Line : AnnotatedLines) {
288 Current = Line->First;
289 LineEnd = Line->Last;
291 if (Start.isInvalid() || References.empty())
292 // After the first file level comment, consider line comments to be part
293 // of the import that immediately follows them by using the previously
295 Start = Line->First->Tok.getLocation();
297 // Only comments on this line. Could be the first non-import line.
298 FirstNonImportLine = Line;
301 JsModuleReference Reference;
302 Reference.Range.setBegin(Start);
303 if (!parseModuleReference(Keywords, Reference)) {
304 if (!FirstNonImportLine)
305 FirstNonImportLine = Line; // if no comment before.
308 FirstNonImportLine = nullptr;
309 AnyImportAffected = AnyImportAffected || Line->Affected;
310 Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
312 llvm::dbgs() << "JsModuleReference: {"
313 << "is_export: " << Reference.IsExport
314 << ", cat: " << Reference.Category
315 << ", url: " << Reference.URL
316 << ", prefix: " << Reference.Prefix;
317 for (size_t i = 0; i < Reference.Symbols.size(); ++i)
318 llvm::dbgs() << ", " << Reference.Symbols[i].Symbol << " as "
319 << Reference.Symbols[i].Alias;
320 llvm::dbgs() << ", text: " << getSourceText(Reference.Range);
321 llvm::dbgs() << "}\n";
323 References.push_back(Reference);
324 Start = SourceLocation();
326 // Sort imports if any import line was affected.
327 if (!AnyImportAffected)
329 return std::make_pair(References, FirstNonImportLine);
332 // Parses a JavaScript/ECMAScript 6 module reference.
333 // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules
334 // for grammar EBNF (production ModuleItem).
335 bool parseModuleReference(const AdditionalKeywords &Keywords,
336 JsModuleReference &Reference) {
337 if (!Current || !Current->isOneOf(Keywords.kw_import, tok::kw_export))
339 Reference.IsExport = Current->is(tok::kw_export);
342 if (Current->isStringLiteral() && !Reference.IsExport) {
343 // "import 'side-effect';"
344 Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
346 Current->TokenText.substr(1, Current->TokenText.size() - 2);
350 if (!parseModuleBindings(Keywords, Reference))
353 if (Current->is(Keywords.kw_from)) {
354 // imports have a 'from' clause, exports might not.
356 if (!Current->isStringLiteral())
358 // URL = TokenText without the quotes.
360 Current->TokenText.substr(1, Current->TokenText.size() - 2);
361 if (Reference.URL.startswith(".."))
363 JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
364 else if (Reference.URL.startswith("."))
365 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
367 Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
369 // w/o URL groups with "empty".
370 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
375 bool parseModuleBindings(const AdditionalKeywords &Keywords,
376 JsModuleReference &Reference) {
377 if (parseStarBinding(Keywords, Reference))
379 return parseNamedBindings(Keywords, Reference);
382 bool parseStarBinding(const AdditionalKeywords &Keywords,
383 JsModuleReference &Reference) {
384 // * as prefix from '...';
385 if (Current->isNot(tok::star))
388 if (Current->isNot(Keywords.kw_as))
391 if (Current->isNot(tok::identifier))
393 Reference.Prefix = Current->TokenText;
398 bool parseNamedBindings(const AdditionalKeywords &Keywords,
399 JsModuleReference &Reference) {
400 if (Current->is(tok::identifier)) {
402 if (Current->is(Keywords.kw_from))
404 if (Current->isNot(tok::comma))
406 nextToken(); // eat comma.
408 if (Current->isNot(tok::l_brace))
411 // {sym as alias, sym2 as ...} from '...';
412 while (Current->isNot(tok::r_brace)) {
414 if (Current->is(tok::r_brace))
416 if (!Current->isOneOf(tok::identifier, tok::kw_default))
419 JsImportedSymbol Symbol;
420 Symbol.Symbol = Current->TokenText;
421 // Make sure to include any preceding comments.
422 Symbol.Range.setBegin(
423 Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());
426 if (Current->is(Keywords.kw_as)) {
428 if (!Current->isOneOf(tok::identifier, tok::kw_default))
430 Symbol.Alias = Current->TokenText;
433 Symbol.Range.setEnd(Current->Tok.getLocation());
434 Reference.Symbols.push_back(Symbol);
436 if (!Current->isOneOf(tok::r_brace, tok::comma))
439 nextToken(); // consume r_brace
444 tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
446 ArrayRef<tooling::Range> Ranges,
447 StringRef FileName) {
448 // FIXME: Cursor support.
449 std::unique_ptr<Environment> Env =
450 Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
451 JavaScriptImportSorter Sorter(*Env, Style);
452 return Sorter.process().first;
455 } // end namespace format
456 } // end namespace clang