• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- SortJavaScriptImports.h - Sort ES6 Imports -------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file implements a sort operation for JavaScript ES6 imports.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "SortJavaScriptImports.h"
16 #include "SortJavaScriptImports.h"
17 #include "TokenAnalyzer.h"
18 #include "TokenAnnotator.h"
19 #include "clang/Basic/Diagnostic.h"
20 #include "clang/Basic/DiagnosticOptions.h"
21 #include "clang/Basic/LLVM.h"
22 #include "clang/Basic/SourceLocation.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Format/Format.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/Support/Debug.h"
28 #include <algorithm>
29 #include <string>
30 
31 #define DEBUG_TYPE "format-formatter"
32 
33 namespace clang {
34 namespace format {
35 
36 class FormatTokenLexer;
37 
38 using clang::format::FormatStyle;
39 
40 // An imported symbol in a JavaScript ES6 import/export, possibly aliased.
41 struct JsImportedSymbol {
42   StringRef Symbol;
43   StringRef Alias;
44   SourceRange Range;
45 
operator ==clang::format::JsImportedSymbol46   bool operator==(const JsImportedSymbol &RHS) const {
47     // Ignore Range for comparison, it is only used to stitch code together,
48     // but imports at different code locations are still conceptually the same.
49     return Symbol == RHS.Symbol && Alias == RHS.Alias;
50   }
51 };
52 
53 // An ES6 module reference.
54 //
55 // ES6 implements a module system, where individual modules (~= source files)
56 // can reference other modules, either importing symbols from them, or exporting
57 // symbols from them:
58 //   import {foo} from 'foo';
59 //   export {foo};
60 //   export {bar} from 'bar';
61 //
62 // `export`s with URLs are syntactic sugar for an import of the symbol from the
63 // URL, followed by an export of the symbol, allowing this code to treat both
64 // statements more or less identically, with the exception being that `export`s
65 // are sorted last.
66 //
67 // imports and exports support individual symbols, but also a wildcard syntax:
68 //   import * as prefix from 'foo';
69 //   export * from 'bar';
70 //
71 // This struct represents both exports and imports to build up the information
72 // required for sorting module references.
73 struct JsModuleReference {
74   bool IsExport = false;
75   // Module references are sorted into these categories, in order.
76   enum ReferenceCategory {
77     SIDE_EFFECT,     // "import 'something';"
78     ABSOLUTE,        // from 'something'
79     RELATIVE_PARENT, // from '../*'
80     RELATIVE,        // from './*'
81   };
82   ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;
83   // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
84   StringRef URL;
85   // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
86   // Implies an empty names list.
87   StringRef Prefix;
88   // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.
89   SmallVector<JsImportedSymbol, 1> Symbols;
90   // Textual position of the import/export, including preceding and trailing
91   // comments.
92   SourceRange Range;
93 };
94 
operator <(const JsModuleReference & LHS,const JsModuleReference & RHS)95 bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS) {
96   if (LHS.IsExport != RHS.IsExport)
97     return LHS.IsExport < RHS.IsExport;
98   if (LHS.Category != RHS.Category)
99     return LHS.Category < RHS.Category;
100   if (LHS.Category == JsModuleReference::ReferenceCategory::SIDE_EFFECT)
101     // Side effect imports might be ordering sensitive. Consider them equal so
102     // that they maintain their relative order in the stable sort below.
103     // This retains transitivity because LHS.Category == RHS.Category here.
104     return false;
105   // Empty URLs sort *last* (for export {...};).
106   if (LHS.URL.empty() != RHS.URL.empty())
107     return LHS.URL.empty() < RHS.URL.empty();
108   if (int Res = LHS.URL.compare_lower(RHS.URL))
109     return Res < 0;
110   // '*' imports (with prefix) sort before {a, b, ...} imports.
111   if (LHS.Prefix.empty() != RHS.Prefix.empty())
112     return LHS.Prefix.empty() < RHS.Prefix.empty();
113   if (LHS.Prefix != RHS.Prefix)
114     return LHS.Prefix > RHS.Prefix;
115   return false;
116 }
117 
118 // JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is
119 // implemented as a TokenAnalyzer because ES6 imports have substantial syntactic
120 // structure, making it messy to sort them using regular expressions.
121 class JavaScriptImportSorter : public TokenAnalyzer {
122 public:
JavaScriptImportSorter(const Environment & Env,const FormatStyle & Style)123   JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)
124       : TokenAnalyzer(Env, Style),
125         FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) {}
126 
127   tooling::Replacements
analyze(TokenAnnotator & Annotator,SmallVectorImpl<AnnotatedLine * > & AnnotatedLines,FormatTokenLexer & Tokens,tooling::Replacements & Result)128   analyze(TokenAnnotator &Annotator,
129           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
130           FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
131     AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
132                                           AnnotatedLines.end());
133 
134     const AdditionalKeywords &Keywords = Tokens.getKeywords();
135     SmallVector<JsModuleReference, 16> References;
136     AnnotatedLine *FirstNonImportLine;
137     std::tie(References, FirstNonImportLine) =
138         parseModuleReferences(Keywords, AnnotatedLines);
139 
140     if (References.empty())
141       return Result;
142 
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];
149                      });
150     bool ReferencesInOrder = std::is_sorted(Indices.begin(), Indices.end());
151 
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;
158       if (i + 1 < e) {
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";
167       }
168     }
169 
170     if (ReferencesInOrder && SymbolsInOrder)
171       return Result;
172 
173     SourceRange InsertionPoint = References[0].Range;
174     InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());
175 
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 += " ";
186     }
187 
188     // Separate references from the main code body of the file.
189     if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2)
190       ReferencesText += "\n";
191 
192     DEBUG(llvm::dbgs() << "Replacing imports:\n"
193                        << getSourceText(InsertionPoint) << "\nwith:\n"
194                        << ReferencesText << "\n");
195     Result.insert(tooling::Replacement(
196         Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),
197         ReferencesText));
198 
199     return Result;
200   }
201 
202 private:
203   FormatToken *Current;
204   FormatToken *LineEnd;
205 
206   FormatToken invalidToken;
207 
208   StringRef FileContents;
209 
skipComments()210   void skipComments() { Current = skipComments(Current); }
211 
skipComments(FormatToken * Tok)212   FormatToken *skipComments(FormatToken *Tok) {
213     while (Tok && Tok->is(tok::comment))
214       Tok = Tok->Next;
215     return Tok;
216   }
217 
nextToken()218   void nextToken() {
219     Current = Current->Next;
220     skipComments();
221     if (!Current || Current == LineEnd->Next) {
222       // Set the current token to an invalid token, so that further parsing on
223       // this line fails.
224       invalidToken.Tok.setKind(tok::unknown);
225       Current = &invalidToken;
226     }
227   }
228 
getSourceText(SourceRange Range)229   StringRef getSourceText(SourceRange Range) {
230     return getSourceText(Range.getBegin(), Range.getEnd());
231   }
232 
getSourceText(SourceLocation Begin,SourceLocation End)233   StringRef getSourceText(SourceLocation Begin, SourceLocation End) {
234     const SourceManager &SM = Env.getSourceManager();
235     return FileContents.substr(SM.getFileOffset(Begin),
236                                SM.getFileOffset(End) - SM.getFileOffset(Begin));
237   }
238 
239   // Appends ``Reference`` to ``Buffer``, returning true if text within the
240   // ``Reference`` changed (e.g. symbol order).
appendReference(std::string & Buffer,JsModuleReference & Reference)241   bool appendReference(std::string &Buffer, JsModuleReference &Reference) {
242     // Sort the individual symbols within the import.
243     // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`
244     SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols;
245     std::stable_sort(
246         Symbols.begin(), Symbols.end(),
247         [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
248           return LHS.Symbol.compare_lower(RHS.Symbol) < 0;
249         });
250     if (Symbols == Reference.Symbols) {
251       // No change in symbol order.
252       StringRef ReferenceStmt = getSourceText(Reference.Range);
253       Buffer += ReferenceStmt;
254       return false;
255     }
256     // Stitch together the module reference start...
257     SourceLocation SymbolsStart = Reference.Symbols.front().Range.getBegin();
258     SourceLocation SymbolsEnd = Reference.Symbols.back().Range.getEnd();
259     Buffer += getSourceText(Reference.Range.getBegin(), SymbolsStart);
260     // ... then the references in order ...
261     for (auto I = Symbols.begin(), E = Symbols.end(); I != E; ++I) {
262       if (I != Symbols.begin())
263         Buffer += ",";
264       Buffer += getSourceText(I->Range);
265     }
266     // ... followed by the module reference end.
267     Buffer += getSourceText(SymbolsEnd, Reference.Range.getEnd());
268     return true;
269   }
270 
271   // Parses module references in the given lines. Returns the module references,
272   // and a pointer to the first "main code" line if that is adjacent to the
273   // affected lines of module references, nullptr otherwise.
274   std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine*>
parseModuleReferences(const AdditionalKeywords & Keywords,SmallVectorImpl<AnnotatedLine * > & AnnotatedLines)275   parseModuleReferences(const AdditionalKeywords &Keywords,
276                         SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
277     SmallVector<JsModuleReference, 16> References;
278     SourceLocation Start;
279     bool FoundLines = false;
280     AnnotatedLine *FirstNonImportLine = nullptr;
281     for (auto Line : AnnotatedLines) {
282       if (!Line->Affected) {
283         // Only sort the first contiguous block of affected lines.
284         if (FoundLines)
285           break;
286         else
287           continue;
288       }
289       Current = Line->First;
290       LineEnd = Line->Last;
291       skipComments();
292       if (Start.isInvalid() || References.empty())
293         // After the first file level comment, consider line comments to be part
294         // of the import that immediately follows them by using the previously
295         // set Start.
296         Start = Line->First->Tok.getLocation();
297       if (!Current)
298         continue; // Only comments on this line.
299       FoundLines = true;
300       JsModuleReference Reference;
301       Reference.Range.setBegin(Start);
302       if (!parseModuleReference(Keywords, Reference)) {
303         FirstNonImportLine = Line;
304         break;
305       }
306       Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
307       DEBUG({
308         llvm::dbgs() << "JsModuleReference: {"
309                      << "is_export: " << Reference.IsExport
310                      << ", cat: " << Reference.Category
311                      << ", url: " << Reference.URL
312                      << ", prefix: " << Reference.Prefix;
313         for (size_t i = 0; i < Reference.Symbols.size(); ++i)
314           llvm::dbgs() << ", " << Reference.Symbols[i].Symbol << " as "
315                        << Reference.Symbols[i].Alias;
316         llvm::dbgs() << ", text: " << getSourceText(Reference.Range);
317         llvm::dbgs() << "}\n";
318       });
319       References.push_back(Reference);
320       Start = SourceLocation();
321     }
322     return std::make_pair(References, FirstNonImportLine);
323   }
324 
325   // Parses a JavaScript/ECMAScript 6 module reference.
326   // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules
327   // for grammar EBNF (production ModuleItem).
parseModuleReference(const AdditionalKeywords & Keywords,JsModuleReference & Reference)328   bool parseModuleReference(const AdditionalKeywords &Keywords,
329                             JsModuleReference &Reference) {
330     if (!Current || !Current->isOneOf(Keywords.kw_import, tok::kw_export))
331       return false;
332     Reference.IsExport = Current->is(tok::kw_export);
333 
334     nextToken();
335     if (Current->isStringLiteral() && !Reference.IsExport) {
336       // "import 'side-effect';"
337       Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
338       Reference.URL =
339           Current->TokenText.substr(1, Current->TokenText.size() - 2);
340       return true;
341     }
342 
343     if (!parseModuleBindings(Keywords, Reference))
344       return false;
345     nextToken();
346 
347     if (Current->is(Keywords.kw_from)) {
348       // imports have a 'from' clause, exports might not.
349       nextToken();
350       if (!Current->isStringLiteral())
351         return false;
352       // URL = TokenText without the quotes.
353       Reference.URL =
354           Current->TokenText.substr(1, Current->TokenText.size() - 2);
355       if (Reference.URL.startswith(".."))
356         Reference.Category =
357             JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
358       else if (Reference.URL.startswith("."))
359         Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
360       else
361         Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
362     } else {
363       // w/o URL groups with "empty".
364       Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
365     }
366     return true;
367   }
368 
parseModuleBindings(const AdditionalKeywords & Keywords,JsModuleReference & Reference)369   bool parseModuleBindings(const AdditionalKeywords &Keywords,
370                            JsModuleReference &Reference) {
371     if (parseStarBinding(Keywords, Reference))
372       return true;
373     return parseNamedBindings(Keywords, Reference);
374   }
375 
parseStarBinding(const AdditionalKeywords & Keywords,JsModuleReference & Reference)376   bool parseStarBinding(const AdditionalKeywords &Keywords,
377                         JsModuleReference &Reference) {
378     // * as prefix from '...';
379     if (Current->isNot(tok::star))
380       return false;
381     nextToken();
382     if (Current->isNot(Keywords.kw_as))
383       return false;
384     nextToken();
385     if (Current->isNot(tok::identifier))
386       return false;
387     Reference.Prefix = Current->TokenText;
388     return true;
389   }
390 
parseNamedBindings(const AdditionalKeywords & Keywords,JsModuleReference & Reference)391   bool parseNamedBindings(const AdditionalKeywords &Keywords,
392                           JsModuleReference &Reference) {
393     if (Current->isNot(tok::l_brace))
394       return false;
395 
396     // {sym as alias, sym2 as ...} from '...';
397     nextToken();
398     while (true) {
399       if (Current->is(tok::r_brace))
400         return true;
401       if (Current->isNot(tok::identifier))
402         return false;
403 
404       JsImportedSymbol Symbol;
405       Symbol.Symbol = Current->TokenText;
406       // Make sure to include any preceding comments.
407       Symbol.Range.setBegin(
408           Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());
409       nextToken();
410 
411       if (Current->is(Keywords.kw_as)) {
412         nextToken();
413         if (Current->isNot(tok::identifier))
414           return false;
415         Symbol.Alias = Current->TokenText;
416         nextToken();
417       }
418       Symbol.Range.setEnd(Current->Tok.getLocation());
419       Reference.Symbols.push_back(Symbol);
420 
421       if (Current->is(tok::r_brace))
422         return true;
423       if (Current->isNot(tok::comma))
424         return false;
425       nextToken();
426     }
427   }
428 };
429 
sortJavaScriptImports(const FormatStyle & Style,StringRef Code,ArrayRef<tooling::Range> Ranges,StringRef FileName)430 tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
431                                             StringRef Code,
432                                             ArrayRef<tooling::Range> Ranges,
433                                             StringRef FileName) {
434   // FIXME: Cursor support.
435   std::unique_ptr<Environment> Env =
436       Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
437   JavaScriptImportSorter Sorter(*Env, Style);
438   return Sorter.process();
439 }
440 
441 } // end namespace format
442 } // end namespace clang
443