contrib/llvm/tools/clang/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 /// 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   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);
 132
 133     const AdditionalKeywords &Keywords = Tokens.getKeywords();
 134     SmallVector<JsModuleReference, 16> References;
 135     AnnotatedLine *FirstNonImportLine;
 136     std::tie(References, FirstNonImportLine) =
 137         parseModuleReferences(Keywords, AnnotatedLines);
 138
 139     if (References.empty())
 140       return {Result, 0};
 141
 142     SmallVector<unsigned, 16> Indices;
 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) {
 282     SmallVector<JsModuleReference, 16> References;
 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
 418       JsImportedSymbol Symbol;
 419       Symbol.Symbol = Current->TokenText;
 420       // Make sure to include any preceding comments.
 421       Symbol.Range.setBegin(
 422           Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());
 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
 443 tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
 444                                             StringRef Code,
 445                                             ArrayRef<tooling::Range> Ranges,
 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