clang  8.0.0svn
SortJavaScriptImports.cpp
Go to the documentation of this file.
1 //===--- SortJavaScriptImports.cpp - 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 /// This file implements a sort operation for JavaScript ES6 imports.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "SortJavaScriptImports.h"
16 #include "TokenAnalyzer.h"
17 #include "TokenAnnotator.h"
18 #include "clang/Basic/Diagnostic.h"
20 #include "clang/Basic/LLVM.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"
27 #include <algorithm>
28 #include <string>
29 
30 #define DEBUG_TYPE "format-formatter"
31 
32 namespace clang {
33 namespace format {
34 
35 class FormatTokenLexer;
36 
38 
39 // An imported symbol in a JavaScript ES6 import/export, possibly aliased.
41  StringRef Symbol;
42  StringRef Alias;
44 
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;
49  }
50 };
51 
52 // An ES6 module reference.
53 //
54 // ES6 implements a module system, where individual modules (~= source files)
55 // can reference other modules, either importing symbols from them, or exporting
56 // symbols from them:
57 // import {foo} from 'foo';
58 // export {foo};
59 // export {bar} from 'bar';
60 //
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
64 // are sorted last.
65 //
66 // imports and exports support individual symbols, but also a wildcard syntax:
67 // import * as prefix from 'foo';
68 // export * from 'bar';
69 //
70 // This struct represents both exports and imports to build up the information
71 // required for sorting module references.
73  bool IsExport = false;
74  // Module references are sorted into these categories, in order.
76  SIDE_EFFECT, // "import 'something';"
77  ABSOLUTE, // from 'something'
78  RELATIVE_PARENT, // from '../*'
79  RELATIVE, // from './*'
80  };
81  ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;
82  // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
83  StringRef URL;
84  // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
85  // Implies an empty names list.
86  StringRef Prefix;
87  // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.
89  // Textual position of the import/export, including preceding and trailing
90  // comments.
92 };
93 
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.
103  return false;
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))
108  return Res < 0;
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;
114  return false;
115 }
116 
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.
121 public:
123  : TokenAnalyzer(Env, Style),
124  FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) {}
125 
126  std::pair<tooling::Replacements, unsigned>
128  SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
129  FormatTokenLexer &Tokens) override {
130  tooling::Replacements Result;
131  AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
132 
133  const AdditionalKeywords &Keywords = Tokens.getKeywords();
135  AnnotatedLine *FirstNonImportLine;
136  std::tie(References, FirstNonImportLine) =
137  parseModuleReferences(Keywords, AnnotatedLines);
138 
139  if (References.empty())
140  return {Result, 0};
141 
143  for (unsigned i = 0, e = References.size(); i != e; ++i)
144  Indices.push_back(i);
145  std::stable_sort(Indices.begin(), Indices.end(),
146  [&](unsigned LHSI, unsigned RHSI) {
147  return References[LHSI] < References[RHSI];
148  });
149  bool ReferencesInOrder = std::is_sorted(Indices.begin(), Indices.end());
150 
151  std::string ReferencesText;
152  bool SymbolsInOrder = true;
153  for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
154  JsModuleReference Reference = References[Indices[i]];
155  if (appendReference(ReferencesText, Reference))
156  SymbolsInOrder = false;
157  if (i + 1 < e) {
158  // Insert breaks between imports and exports.
159  ReferencesText += "\n";
160  // Separate imports groups with two line breaks, but keep all exports
161  // in a single group.
162  if (!Reference.IsExport &&
163  (Reference.IsExport != References[Indices[i + 1]].IsExport ||
164  Reference.Category != References[Indices[i + 1]].Category))
165  ReferencesText += "\n";
166  }
167  }
168 
169  if (ReferencesInOrder && SymbolsInOrder)
170  return {Result, 0};
171 
172  SourceRange InsertionPoint = References[0].Range;
173  InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());
174 
175  // The loop above might collapse previously existing line breaks between
176  // import blocks, and thus shrink the file. SortIncludes must not shrink
177  // overall source length as there is currently no re-calculation of ranges
178  // after applying source sorting.
179  // This loop just backfills trailing spaces after the imports, which are
180  // harmless and will be stripped by the subsequent formatting pass.
181  // FIXME: A better long term fix is to re-calculate Ranges after sorting.
182  unsigned PreviousSize = getSourceText(InsertionPoint).size();
183  while (ReferencesText.size() < PreviousSize) {
184  ReferencesText += " ";
185  }
186 
187  // Separate references from the main code body of the file.
188  if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2)
189  ReferencesText += "\n";
190 
191  LLVM_DEBUG(llvm::dbgs() << "Replacing imports:\n"
192  << getSourceText(InsertionPoint) << "\nwith:\n"
193  << ReferencesText << "\n");
194  auto Err = Result.add(tooling::Replacement(
195  Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),
196  ReferencesText));
197  // FIXME: better error handling. For now, just print error message and skip
198  // the replacement for the release version.
199  if (Err) {
200  llvm::errs() << llvm::toString(std::move(Err)) << "\n";
201  assert(false);
202  }
203 
204  return {Result, 0};
205  }
206 
207 private:
208  FormatToken *Current;
209  FormatToken *LineEnd;
210 
211  FormatToken invalidToken;
212 
213  StringRef FileContents;
214 
215  void skipComments() { Current = skipComments(Current); }
216 
217  FormatToken *skipComments(FormatToken *Tok) {
218  while (Tok && Tok->is(tok::comment))
219  Tok = Tok->Next;
220  return Tok;
221  }
222 
223  void nextToken() {
224  Current = Current->Next;
225  skipComments();
226  if (!Current || Current == LineEnd->Next) {
227  // Set the current token to an invalid token, so that further parsing on
228  // this line fails.
229  invalidToken.Tok.setKind(tok::unknown);
230  Current = &invalidToken;
231  }
232  }
233 
234  StringRef getSourceText(SourceRange Range) {
235  return getSourceText(Range.getBegin(), Range.getEnd());
236  }
237 
238  StringRef getSourceText(SourceLocation Begin, SourceLocation End) {
239  const SourceManager &SM = Env.getSourceManager();
240  return FileContents.substr(SM.getFileOffset(Begin),
241  SM.getFileOffset(End) - SM.getFileOffset(Begin));
242  }
243 
244  // Appends ``Reference`` to ``Buffer``, returning true if text within the
245  // ``Reference`` changed (e.g. symbol order).
246  bool appendReference(std::string &Buffer, JsModuleReference &Reference) {
247  // Sort the individual symbols within the import.
248  // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`
249  SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols;
250  std::stable_sort(
251  Symbols.begin(), Symbols.end(),
252  [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
253  return LHS.Symbol.compare_lower(RHS.Symbol) < 0;
254  });
255  if (Symbols == Reference.Symbols) {
256  // No change in symbol order.
257  StringRef ReferenceStmt = getSourceText(Reference.Range);
258  Buffer += ReferenceStmt;
259  return false;
260  }
261  // Stitch together the module reference start...
262  SourceLocation SymbolsStart = Reference.Symbols.front().Range.getBegin();
263  SourceLocation SymbolsEnd = Reference.Symbols.back().Range.getEnd();
264  Buffer += getSourceText(Reference.Range.getBegin(), SymbolsStart);
265  // ... then the references in order ...
266  for (auto I = Symbols.begin(), E = Symbols.end(); I != E; ++I) {
267  if (I != Symbols.begin())
268  Buffer += ",";
269  Buffer += getSourceText(I->Range);
270  }
271  // ... followed by the module reference end.
272  Buffer += getSourceText(SymbolsEnd, Reference.Range.getEnd());
273  return true;
274  }
275 
276  // Parses module references in the given lines. Returns the module references,
277  // and a pointer to the first "main code" line if that is adjacent to the
278  // affected lines of module references, nullptr otherwise.
279  std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine *>
280  parseModuleReferences(const AdditionalKeywords &Keywords,
281  SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
283  SourceLocation Start;
284  AnnotatedLine *FirstNonImportLine = nullptr;
285  bool AnyImportAffected = false;
286  for (auto Line : AnnotatedLines) {
287  Current = Line->First;
288  LineEnd = Line->Last;
289  skipComments();
290  if (Start.isInvalid() || References.empty())
291  // After the first file level comment, consider line comments to be part
292  // of the import that immediately follows them by using the previously
293  // set Start.
294  Start = Line->First->Tok.getLocation();
295  if (!Current) {
296  // Only comments on this line. Could be the first non-import line.
297  FirstNonImportLine = Line;
298  continue;
299  }
300  JsModuleReference Reference;
301  Reference.Range.setBegin(Start);
302  if (!parseModuleReference(Keywords, Reference)) {
303  if (!FirstNonImportLine)
304  FirstNonImportLine = Line; // if no comment before.
305  break;
306  }
307  FirstNonImportLine = nullptr;
308  AnyImportAffected = AnyImportAffected || Line->Affected;
309  Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
310  LLVM_DEBUG({
311  llvm::dbgs() << "JsModuleReference: {"
312  << "is_export: " << Reference.IsExport
313  << ", cat: " << Reference.Category
314  << ", url: " << Reference.URL
315  << ", prefix: " << Reference.Prefix;
316  for (size_t i = 0; i < Reference.Symbols.size(); ++i)
317  llvm::dbgs() << ", " << Reference.Symbols[i].Symbol << " as "
318  << Reference.Symbols[i].Alias;
319  llvm::dbgs() << ", text: " << getSourceText(Reference.Range);
320  llvm::dbgs() << "}\n";
321  });
322  References.push_back(Reference);
323  Start = SourceLocation();
324  }
325  // Sort imports if any import line was affected.
326  if (!AnyImportAffected)
327  References.clear();
328  return std::make_pair(References, FirstNonImportLine);
329  }
330 
331  // Parses a JavaScript/ECMAScript 6 module reference.
332  // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules
333  // for grammar EBNF (production ModuleItem).
334  bool parseModuleReference(const AdditionalKeywords &Keywords,
335  JsModuleReference &Reference) {
336  if (!Current || !Current->isOneOf(Keywords.kw_import, tok::kw_export))
337  return false;
338  Reference.IsExport = Current->is(tok::kw_export);
339 
340  nextToken();
341  if (Current->isStringLiteral() && !Reference.IsExport) {
342  // "import 'side-effect';"
343  Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
344  Reference.URL =
345  Current->TokenText.substr(1, Current->TokenText.size() - 2);
346  return true;
347  }
348 
349  if (!parseModuleBindings(Keywords, Reference))
350  return false;
351 
352  if (Current->is(Keywords.kw_from)) {
353  // imports have a 'from' clause, exports might not.
354  nextToken();
355  if (!Current->isStringLiteral())
356  return false;
357  // URL = TokenText without the quotes.
358  Reference.URL =
359  Current->TokenText.substr(1, Current->TokenText.size() - 2);
360  if (Reference.URL.startswith(".."))
361  Reference.Category =
362  JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
363  else if (Reference.URL.startswith("."))
364  Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
365  else
366  Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
367  } else {
368  // w/o URL groups with "empty".
369  Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
370  }
371  return true;
372  }
373 
374  bool parseModuleBindings(const AdditionalKeywords &Keywords,
375  JsModuleReference &Reference) {
376  if (parseStarBinding(Keywords, Reference))
377  return true;
378  return parseNamedBindings(Keywords, Reference);
379  }
380 
381  bool parseStarBinding(const AdditionalKeywords &Keywords,
382  JsModuleReference &Reference) {
383  // * as prefix from '...';
384  if (Current->isNot(tok::star))
385  return false;
386  nextToken();
387  if (Current->isNot(Keywords.kw_as))
388  return false;
389  nextToken();
390  if (Current->isNot(tok::identifier))
391  return false;
392  Reference.Prefix = Current->TokenText;
393  nextToken();
394  return true;
395  }
396 
397  bool parseNamedBindings(const AdditionalKeywords &Keywords,
398  JsModuleReference &Reference) {
399  if (Current->is(tok::identifier)) {
400  nextToken();
401  if (Current->is(Keywords.kw_from))
402  return true;
403  if (Current->isNot(tok::comma))
404  return false;
405  nextToken(); // eat comma.
406  }
407  if (Current->isNot(tok::l_brace))
408  return false;
409 
410  // {sym as alias, sym2 as ...} from '...';
411  while (Current->isNot(tok::r_brace)) {
412  nextToken();
413  if (Current->is(tok::r_brace))
414  break;
415  if (!Current->isOneOf(tok::identifier, tok::kw_default))
416  return false;
417 
419  Symbol.Symbol = Current->TokenText;
420  // Make sure to include any preceding comments.
421  Symbol.Range.setBegin(
423  nextToken();
424 
425  if (Current->is(Keywords.kw_as)) {
426  nextToken();
427  if (!Current->isOneOf(tok::identifier, tok::kw_default))
428  return false;
429  Symbol.Alias = Current->TokenText;
430  nextToken();
431  }
432  Symbol.Range.setEnd(Current->Tok.getLocation());
433  Reference.Symbols.push_back(Symbol);
434 
435  if (!Current->isOneOf(tok::r_brace, tok::comma))
436  return false;
437  }
438  nextToken(); // consume r_brace
439  return true;
440  }
441 };
442 
444  StringRef Code,
446  StringRef FileName) {
447  // FIXME: Cursor support.
448  return JavaScriptImportSorter(Environment(Code, FileName, Ranges), Style)
449  .process()
450  .first;
451 }
452 
453 } // end namespace format
454 } // end namespace clang
if(T->getSizeExpr()) TRY_TO(TraverseStmt(T -> getSizeExpr()))
Token Tok
The Token.
Definition: FormatToken.h:127
Defines the SourceManager interface.
llvm::Error add(const Replacement &R)
Adds a new replacement R to the current set of replacements.
const AdditionalKeywords & getKeywords()
Maintains a set of replacements that are conflict-free.
Definition: Replacement.h:210
void setBegin(SourceLocation b)
unsigned NewlinesBefore
The number of newlines immediately before the Token.
Definition: FormatToken.h:133
FormatToken * Next
The next token in the unwrapped line.
Definition: FormatToken.h:296
JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)
bool operator==(const JsImportedSymbol &RHS) const
This file implements a token annotator, i.e.
int Category
Definition: Format.cpp:1605
void setKind(tok::TokenKind K)
Definition: Token.h:91
bool isNot(T Kind) const
Definition: FormatToken.h:326
const FormatToken & Tok
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
Defines the Diagnostic-related interfaces.
std::pair< tooling::Replacements, unsigned > analyze(TokenAnnotator &Annotator, SmallVectorImpl< AnnotatedLine *> &AnnotatedLines, FormatTokenLexer &Tokens) override
FormatToken * getPreviousNonComment() const
Returns the previous token ignoring comments.
Definition: FormatToken.h:476
bool isOneOf(A K1, B K2) const
Definition: FormatToken.h:319
A text replacement.
Definition: Replacement.h:84
Determines extra information about the tokens comprising an UnwrappedLine.
SourceLocation End
const AnnotatedLine * Line
SourceLocation getLocation() const
Return a source location identifier for the specified offset in the current file. ...
Definition: Token.h:124
SourceLocation Begin
A wrapper around a Token storing information about the whitespace characters preceding it...
Definition: FormatToken.h:123
SourceLocation getEnd() const
const SourceManager & SM
Definition: Format.cpp:1472
static CharSourceRange getCharRange(SourceRange R)
unsigned getFileOffset(SourceLocation SpellingLoc) const
Returns the offset from the start of the file that the specified SourceLocation represents.
Encodes a location in the source.
bool is(tok::TokenKind Kind) const
Definition: FormatToken.h:310
Various functions to configurably format source code.
Encapsulates keywords that are context sensitive or for languages not properly supported by Clang&#39;s l...
Definition: FormatToken.h:663
SourceRange WhitespaceRange
The range of the whitespace immediately preceding the Token.
Definition: FormatToken.h:140
StringRef TokenText
The raw text of the token.
Definition: FormatToken.h:171
The FormatStyle is used to configure the formatting to follow specific guidelines.
Definition: Format.h:48
Dataflow Directional Tag Classes.
std::pair< tooling::Replacements, unsigned > process()
This file implements a sorter for JavaScript ES6 imports.
bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS)
std::string toString(const til::SExpr *E)
SmallVector< JsImportedSymbol, 1 > Symbols
This file declares an abstract TokenAnalyzer, and associated helper classes.
Defines the clang::SourceLocation class and associated facilities.
void setEnd(SourceLocation e)
A trivial tuple used to represent a source range.
tooling::Replacements sortJavaScriptImports(const FormatStyle &Style, StringRef Code, ArrayRef< tooling::Range > Ranges, StringRef FileName)
bool isStringLiteral() const
Definition: FormatToken.h:350
SourceLocation getBegin() const
This class handles loading and caching of source files into memory.
const FormatStyle & Style
SourceLocation getEndLoc() const
Definition: Token.h:151