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/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"
27#include <algorithm>
28#include <string>
29
30#define DEBUG_TYPE "format-formatter"
31
32namespace clang {
33namespace format {
34
35class FormatTokenLexer;
36
37using clang::format::FormatStyle;
38
39// An imported symbol in a JavaScript ES6 import/export, possibly aliased.
40struct JsImportedSymbol {
41  StringRef Symbol;
42  StringRef Alias;
43  SourceRange Range;
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.
72struct 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;
83  };
84  ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;
85  // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
86  StringRef URL;
87  // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
88  // Implies an empty names list.
89  StringRef Prefix;
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
101  // comments.
102  SourceRange Range;
103};
104
105bool 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
115    // here.
116    return false;
117  }
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))
122    return Res < 0;
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;
128  return false;
129}
130
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.
134class JavaScriptImportSorter : public TokenAnalyzer {
135public:
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();
141  }
142
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);
149
150    const AdditionalKeywords &Keywords = Tokens.getKeywords();
151    SmallVector<JsModuleReference, 16> References;
152    AnnotatedLine *FirstNonImportLine;
153    std::tie(References, FirstNonImportLine) =
154        parseModuleReferences(Keywords, AnnotatedLines);
155
156    if (References.empty())
157      return {Result, 0};
158
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());
162
163    References = sortModuleReferences(References);
164
165    std::string ReferencesText;
166    for (unsigned I = 0, E = References.size(); I != E; ++I) {
167      JsModuleReference Reference = References[I];
168      appendReference(ReferencesText, Reference);
169      if (I + 1 < E) {
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";
178        }
179      }
180    }
181    llvm::StringRef PreviousText = getSourceText(InsertionPoint);
182    if (ReferencesText == PreviousText)
183      return {Result, 0};
184
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 += " ";
195
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";
201    }
202
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),
208        ReferencesText));
209    // FIXME: better error handling. For now, just print error message and skip
210    // the replacement for the release version.
211    if (Err) {
212      llvm::errs() << llvm::toString(std::move(Err)) << "\n";
213      assert(false);
214    }
215
216    return {Result, 0};
217  }
218
219private:
220  FormatToken *Current = nullptr;
221  FormatToken *LineEnd = nullptr;
222
223  FormatToken invalidToken;
224
225  StringRef FileContents;
226
227  void skipComments() { Current = skipComments(Current); }
228
229  FormatToken *skipComments(FormatToken *Tok) {
230    while (Tok && Tok->is(tok::comment))
231      Tok = Tok->Next;
232    return Tok;
233  }
234
235  void nextToken() {
236    Current = Current->Next;
237    skipComments();
238    if (!Current || Current == LineEnd->Next) {
239      // Set the current token to an invalid token, so that further parsing on
240      // this line fails.
241      Current = &invalidToken;
242    }
243  }
244
245  StringRef getSourceText(SourceRange Range) {
246    return getSourceText(Range.getBegin(), Range.getEnd());
247  }
248
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));
253  }
254
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);
271        ++Start;
272      }
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);
277        ++Start;
278      }
279      llvm::stable_sort(SortChunk);
280      mergeModuleReferences(SortChunk);
281      ReferencesSorted.insert(ReferencesSorted.end(), SortChunk.begin(),
282                              SortChunk.end());
283    }
284    return ReferencesSorted;
285  }
286
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())
298      return;
299    JsModuleReference *PreviousReference = References.begin();
300    auto *Reference = std::next(References.begin());
301    while (Reference != References.end()) {
302      // Skip:
303      //   import 'foo';
304      //   import * as foo from 'foo'; on either previous or this.
305      //   import Default from 'foo'; on either previous or this.
306      //   mismatching
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;
316        ++Reference;
317        continue;
318      }
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);
324    }
325  }
326
327  // Appends ``Reference`` to ``Buffer``.
328  void appendReference(std::string &Buffer, JsModuleReference &Reference) {
329    if (Reference.FormattingOff) {
330      Buffer +=
331          getSourceText(Reference.Range.getBegin(), Reference.Range.getEnd());
332      return;
333    }
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;
337    llvm::stable_sort(
338        Symbols, [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
339          return LHS.Symbol.compare_insensitive(RHS.Symbol) < 0;
340        });
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;
345      return;
346    }
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)) {
353        Buffer += ",";
354        Buffer += getSourceText(Symbol.Range);
355      }
356    }
357    // ... followed by the module reference end.
358    Buffer += getSourceText(Reference.SymbolsEnd, Reference.Range.getEnd());
359  }
360
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) {
373      assert(Line->First);
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
387          // around).
388          if (!References.empty()) {
389            References.back().Range.setEnd(Current->Tok.getEndLoc());
390            Start = Current->Tok.getEndLoc().getLocWithOffset(1);
391          }
392        }
393        // Handle all clang-format comments on a line, e.g. for an empty block.
394        Current = Current->Next;
395      }
396      skipComments();
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
400        // set Start.
401        Start = Line->First->Tok.getLocation();
402      }
403      if (!Current) {
404        // Only comments on this line. Could be the first non-import line.
405        FirstNonImportLine = Line;
406        continue;
407      }
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.
416        break;
417      }
418      FirstNonImportLine = nullptr;
419      AnyImportAffected = AnyImportAffected || Line->Affected;
420      Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
421      LLVM_DEBUG({
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";
432      });
433      References.push_back(Reference);
434      Start = SourceLocation();
435    }
436    // Sort imports if any import line was affected.
437    if (!AnyImportAffected)
438      References.clear();
439    return std::make_pair(References, FirstNonImportLine);
440  }
441
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))
448      return false;
449    Reference.IsExport = Current->is(tok::kw_export);
450
451    nextToken();
452    if (Current->isStringLiteral() && !Reference.IsExport) {
453      // "import 'side-effect';"
454      Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
455      Reference.URL =
456          Current->TokenText.substr(1, Current->TokenText.size() - 2);
457      return true;
458    }
459
460    if (!parseModuleBindings(Keywords, Reference))
461      return false;
462
463    if (Current->is(Keywords.kw_from)) {
464      // imports have a 'from' clause, exports might not.
465      nextToken();
466      if (!Current->isStringLiteral())
467        return false;
468      // URL = TokenText without the quotes.
469      Reference.URL =
470          Current->TokenText.substr(1, Current->TokenText.size() - 2);
471      if (Reference.URL.starts_with("..")) {
472        Reference.Category =
473            JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
474      } else if (Reference.URL.starts_with(".")) {
475        Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
476      } else {
477        Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
478      }
479    }
480    return true;
481  }
482
483  bool parseModuleBindings(const AdditionalKeywords &Keywords,
484                           JsModuleReference &Reference) {
485    if (parseStarBinding(Keywords, Reference))
486      return true;
487    return parseNamedBindings(Keywords, Reference);
488  }
489
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;
496      nextToken();
497    }
498    if (Current->isNot(tok::star))
499      return false;
500    nextToken();
501    if (Current->isNot(Keywords.kw_as))
502      return false;
503    nextToken();
504    if (Current->isNot(tok::identifier))
505      return false;
506    Reference.Prefix = Current->TokenText;
507    nextToken();
508    return true;
509  }
510
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;
516      nextToken();
517    }
518
519    // eat a potential "import X, " prefix.
520    if (!Reference.IsExport && Current->is(tok::identifier)) {
521      Reference.DefaultImport = Current->TokenText;
522      nextToken();
523      if (Current->is(Keywords.kw_from))
524        return true;
525      // import X = A.B.C;
526      if (Current->is(tok::equal)) {
527        Reference.Category = JsModuleReference::ReferenceCategory::ALIAS;
528        nextToken();
529        while (Current->is(tok::identifier)) {
530          nextToken();
531          if (Current->is(tok::semi))
532            return true;
533          if (Current->isNot(tok::period))
534            return false;
535          nextToken();
536        }
537      }
538      if (Current->isNot(tok::comma))
539        return false;
540      nextToken(); // eat comma.
541    }
542    if (Current->isNot(tok::l_brace))
543      return false;
544
545    // {sym as alias, sym2 as ...} from '...';
546    Reference.SymbolsStart = Current->Tok.getEndLoc();
547    while (Current->isNot(tok::r_brace)) {
548      nextToken();
549      if (Current->is(tok::r_brace))
550        break;
551      auto IsIdentifier = [](const auto *Tok) {
552        return Tok->isOneOf(tok::identifier, tok::kw_default, tok::kw_template);
553      };
554      bool isTypeOnly = Current->is(Keywords.kw_type) && Current->Next &&
555                        IsIdentifier(Current->Next);
556      if (!isTypeOnly && !IsIdentifier(Current))
557        return false;
558
559      JsImportedSymbol Symbol;
560      // Make sure to include any preceding comments.
561      Symbol.Range.setBegin(
562          Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());
563      if (isTypeOnly)
564        nextToken();
565      Symbol.Symbol = Current->TokenText;
566      nextToken();
567
568      if (Current->is(Keywords.kw_as)) {
569        nextToken();
570        if (!IsIdentifier(Current))
571          return false;
572        Symbol.Alias = Current->TokenText;
573        nextToken();
574      }
575      Symbol.Range.setEnd(Current->Tok.getLocation());
576      Reference.Symbols.push_back(Symbol);
577
578      if (!Current->isOneOf(tok::r_brace, tok::comma))
579        return false;
580    }
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
587    return true;
588  }
589};
590
591tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
592                                            StringRef Code,
593                                            ArrayRef<tooling::Range> Ranges,
594                                            StringRef FileName) {
595  // FIXME: Cursor support.
596  auto Env = Environment::make(Code, FileName, Ranges);
597  if (!Env)
598    return {};
599  return JavaScriptImportSorter(*Env, Style).process().first;
600}
601
602} // end namespace format
603} // end namespace clang
604