lib/Format/SortJavaScriptImports.cpp

   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 /// \brief 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"
  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"
  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
  37 using clang::format::FormatStyle;
  38
  39 // An imported symbol in a JavaScript ES6 import/export, possibly aliased.
  40 struct 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.
  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 './*'
  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 ...;`.
  88   SmallVector<JsImportedSymbol, 1> Symbols;
  89   // Textual position of the import/export, including preceding and trailing
  90   // comments.
  91   SourceRange Range;
  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.
 120 class JavaScriptImportSorter : public TokenAnalyzer {
 121 public:
 122   JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)
 123       : TokenAnalyzer(Env, Style),
 124         FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) {}
 125
 126   tooling::Replacements
 127   analyze(TokenAnnotator &Annotator,
 128           SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
 129           FormatTokenLexer &Tokens) override {
 130     tooling::Replacements Result;
 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     auto Err = Result.add(tooling::Replacement(
 196         Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),
 197         ReferencesText));
 198     // FIXME: better error handling. For now, just print error message and skip
 199     // the replacement for the release version.
 200     if (Err) {
 201       llvm::errs() << llvm::toString(std::move(Err)) << "\n";
 202       assert(false);
 203     }
 204
 205     return Result;
 206   }
 207
 208 private:
 209   FormatToken *Current;
 210   FormatToken *LineEnd;
 211
 212   FormatToken invalidToken;
 213
 214   StringRef FileContents;
 215
 216   void skipComments() { Current = skipComments(Current); }
 217
 218   FormatToken *skipComments(FormatToken *Tok) {
 219     while (Tok && Tok->is(tok::comment))
 220       Tok = Tok->Next;
 221     return Tok;
 222   }
 223
 224   void nextToken() {
 225     Current = Current->Next;
 226     skipComments();
 227     if (!Current || Current == LineEnd->Next) {
 228       // Set the current token to an invalid token, so that further parsing on
 229       // this line fails.
 230       invalidToken.Tok.setKind(tok::unknown);
 231       Current = &invalidToken;
 232     }
 233   }
 234
 235   StringRef getSourceText(SourceRange Range) {
 236     return getSourceText(Range.getBegin(), Range.getEnd());
 237   }
 238
 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));
 243   }
 244
 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;
 251     std::stable_sort(
 252         Symbols.begin(), Symbols.end(),
 253         [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {
 254           return LHS.Symbol.compare_lower(RHS.Symbol) < 0;
 255         });
 256     if (Symbols == Reference.Symbols) {
 257       // No change in symbol order.
 258       StringRef ReferenceStmt = getSourceText(Reference.Range);
 259       Buffer += ReferenceStmt;
 260       return false;
 261     }
 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())
 269         Buffer += ",";
 270       Buffer += getSourceText(I->Range);
 271     }
 272     // ... followed by the module reference end.
 273     Buffer += getSourceText(SymbolsEnd, Reference.Range.getEnd());
 274     return true;
 275   }
 276
 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;
 290       skipComments();
 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
 294         // set Start.
 295         Start = Line->First->Tok.getLocation();
 296       if (!Current) {
 297         // Only comments on this line. Could be the first non-import line.
 298         FirstNonImportLine = Line;
 299         continue;
 300       }
 301       JsModuleReference Reference;
 302       Reference.Range.setBegin(Start);
 303       if (!parseModuleReference(Keywords, Reference)) {
 304         if (!FirstNonImportLine)
 305           FirstNonImportLine = Line; // if no comment before.
 306         break;
 307       }
 308       FirstNonImportLine = nullptr;
 309       AnyImportAffected = AnyImportAffected || Line->Affected;
 310       Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
 311       DEBUG({
 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";
 322       });
 323       References.push_back(Reference);
 324       Start = SourceLocation();
 325     }
 326     // Sort imports if any import line was affected.
 327     if (!AnyImportAffected)
 328       References.clear();
 329     return std::make_pair(References, FirstNonImportLine);
 330   }
 331
 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))
 338       return false;
 339     Reference.IsExport = Current->is(tok::kw_export);
 340
 341     nextToken();
 342     if (Current->isStringLiteral() && !Reference.IsExport) {
 343       // "import 'side-effect';"
 344       Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
 345       Reference.URL =
 346           Current->TokenText.substr(1, Current->TokenText.size() - 2);
 347       return true;
 348     }
 349
 350     if (!parseModuleBindings(Keywords, Reference))
 351       return false;
 352
 353     if (Current->is(Keywords.kw_from)) {
 354       // imports have a 'from' clause, exports might not.
 355       nextToken();
 356       if (!Current->isStringLiteral())
 357         return false;
 358       // URL = TokenText without the quotes.
 359       Reference.URL =
 360           Current->TokenText.substr(1, Current->TokenText.size() - 2);
 361       if (Reference.URL.startswith(".."))
 362         Reference.Category =
 363             JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
 364       else if (Reference.URL.startswith("."))
 365         Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
 366       else
 367         Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
 368     } else {
 369       // w/o URL groups with "empty".
 370       Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
 371     }
 372     return true;
 373   }
 374
 375   bool parseModuleBindings(const AdditionalKeywords &Keywords,
 376                            JsModuleReference &Reference) {
 377     if (parseStarBinding(Keywords, Reference))
 378       return true;
 379     return parseNamedBindings(Keywords, Reference);
 380   }
 381
 382   bool parseStarBinding(const AdditionalKeywords &Keywords,
 383                         JsModuleReference &Reference) {
 384     // * as prefix from '...';
 385     if (Current->isNot(tok::star))
 386       return false;
 387     nextToken();
 388     if (Current->isNot(Keywords.kw_as))
 389       return false;
 390     nextToken();
 391     if (Current->isNot(tok::identifier))
 392       return false;
 393     Reference.Prefix = Current->TokenText;
 394     nextToken();
 395     return true;
 396   }
 397
 398   bool parseNamedBindings(const AdditionalKeywords &Keywords,
 399                           JsModuleReference &Reference) {
 400     if (Current->is(tok::identifier)) {
 401       nextToken();
 402       if (Current->is(Keywords.kw_from))
 403         return true;
 404       if (Current->isNot(tok::comma))
 405         return false;
 406       nextToken(); // eat comma.
 407     }
 408     if (Current->isNot(tok::l_brace))
 409       return false;
 410
 411     // {sym as alias, sym2 as ...} from '...';
 412     while (Current->isNot(tok::r_brace)) {
 413       nextToken();
 414       if (Current->is(tok::r_brace))
 415         break;
 416       if (Current->isNot(tok::identifier))
 417         return false;
 418
 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());
 424       nextToken();
 425
 426       if (Current->is(Keywords.kw_as)) {
 427         nextToken();
 428         if (Current->isNot(tok::identifier))
 429           return false;
 430         Symbol.Alias = Current->TokenText;
 431         nextToken();
 432       }
 433       Symbol.Range.setEnd(Current->Tok.getLocation());
 434       Reference.Symbols.push_back(Symbol);
 435
 436       if (!Current->isOneOf(tok::r_brace, tok::comma))
 437         return false;
 438     }
 439     nextToken(); // consume r_brace
 440     return true;
 441   }
 442 };
 443
 444 tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
 445                                             StringRef Code,
 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();
 453 }
 454
 455 } // end namespace format
 456 } // end namespace clang