599 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// 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/LLVM.h"19#include "clang/Basic/SourceLocation.h"20#include "clang/Basic/SourceManager.h"21#include "clang/Basic/TokenKinds.h"22#include "clang/Format/Format.h"23#include "llvm/ADT/STLExtras.h"24#include "llvm/ADT/SmallVector.h"25#include "llvm/Support/Debug.h"26#include <string>27 28#define DEBUG_TYPE "format-formatter"29 30namespace clang {31namespace format {32 33class FormatTokenLexer;34 35// An imported symbol in a JavaScript ES6 import/export, possibly aliased.36struct JsImportedSymbol {37 StringRef Symbol;38 StringRef Alias;39 SourceRange Range;40 41 bool operator==(const JsImportedSymbol &RHS) const {42 // Ignore Range for comparison, it is only used to stitch code together,43 // but imports at different code locations are still conceptually the same.44 return Symbol == RHS.Symbol && Alias == RHS.Alias;45 }46};47 48// An ES6 module reference.49//50// ES6 implements a module system, where individual modules (~= source files)51// can reference other modules, either importing symbols from them, or exporting52// symbols from them:53// import {foo} from 'foo';54// export {foo};55// export {bar} from 'bar';56//57// `export`s with URLs are syntactic sugar for an import of the symbol from the58// URL, followed by an export of the symbol, allowing this code to treat both59// statements more or less identically, with the exception being that `export`s60// are sorted last.61//62// imports and exports support individual symbols, but also a wildcard syntax:63// import * as prefix from 'foo';64// export * from 'bar';65//66// This struct represents both exports and imports to build up the information67// required for sorting module references.68struct JsModuleReference {69 bool FormattingOff = false;70 bool IsExport = false;71 bool IsTypeOnly = false;72 // Module references are sorted into these categories, in order.73 enum ReferenceCategory {74 SIDE_EFFECT, // "import 'something';"75 ABSOLUTE, // from 'something'76 RELATIVE_PARENT, // from '../*'77 RELATIVE, // from './*'78 ALIAS, // import X = A.B;79 };80 ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;81 // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.82 StringRef URL;83 // Prefix from "import * as prefix". Empty for symbol imports and `export *`.84 // Implies an empty names list.85 StringRef Prefix;86 // Default import from "import DefaultName from '...';".87 StringRef DefaultImport;88 // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.89 SmallVector<JsImportedSymbol, 1> Symbols;90 // Whether some symbols were merged into this one. Controls if the module91 // reference needs re-formatting.92 bool SymbolsMerged = false;93 // The source location just after { and just before } in the import.94 // Extracted eagerly to allow modification of Symbols later on.95 SourceLocation SymbolsStart, SymbolsEnd;96 // Textual position of the import/export, including preceding and trailing97 // comments.98 SourceRange Range;99};100 101bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS) {102 if (LHS.IsExport != RHS.IsExport)103 return LHS.IsExport < RHS.IsExport;104 if (LHS.Category != RHS.Category)105 return LHS.Category < RHS.Category;106 if (LHS.Category == JsModuleReference::ReferenceCategory::SIDE_EFFECT ||107 LHS.Category == JsModuleReference::ReferenceCategory::ALIAS) {108 // Side effect imports and aliases might be ordering sensitive. Consider109 // them equal so that they maintain their relative order in the stable sort110 // below. This retains transitivity because LHS.Category == RHS.Category111 // here.112 return false;113 }114 // Empty URLs sort *last* (for export {...};).115 if (LHS.URL.empty() != RHS.URL.empty())116 return LHS.URL.empty() < RHS.URL.empty();117 if (int Res = LHS.URL.compare_insensitive(RHS.URL))118 return Res < 0;119 // '*' imports (with prefix) sort before {a, b, ...} imports.120 if (LHS.Prefix.empty() != RHS.Prefix.empty())121 return LHS.Prefix.empty() < RHS.Prefix.empty();122 if (LHS.Prefix != RHS.Prefix)123 return LHS.Prefix > RHS.Prefix;124 return false;125}126 127// JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is128// implemented as a TokenAnalyzer because ES6 imports have substantial syntactic129// structure, making it messy to sort them using regular expressions.130class JavaScriptImportSorter : public TokenAnalyzer {131public:132 JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)133 : TokenAnalyzer(Env, Style),134 FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) {135 // FormatToken.Tok starts out in an uninitialized state.136 invalidToken.Tok.startToken();137 }138 139 std::pair<tooling::Replacements, unsigned>140 analyze(TokenAnnotator &Annotator,141 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,142 FormatTokenLexer &Tokens) override {143 tooling::Replacements Result;144 AffectedRangeMgr.computeAffectedLines(AnnotatedLines);145 146 const AdditionalKeywords &Keywords = Tokens.getKeywords();147 SmallVector<JsModuleReference, 16> References;148 AnnotatedLine *FirstNonImportLine;149 std::tie(References, FirstNonImportLine) =150 parseModuleReferences(Keywords, AnnotatedLines);151 152 if (References.empty())153 return {Result, 0};154 155 // The text range of all parsed imports, to be replaced later.156 SourceRange InsertionPoint = References[0].Range;157 InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());158 159 References = sortModuleReferences(References);160 161 std::string ReferencesText;162 for (unsigned I = 0, E = References.size(); I != E; ++I) {163 JsModuleReference Reference = References[I];164 appendReference(ReferencesText, Reference);165 if (I + 1 < E) {166 // Insert breaks between imports and exports.167 ReferencesText += "\n";168 // Separate imports groups with two line breaks, but keep all exports169 // in a single group.170 if (!Reference.IsExport &&171 (Reference.IsExport != References[I + 1].IsExport ||172 Reference.Category != References[I + 1].Category)) {173 ReferencesText += "\n";174 }175 }176 }177 StringRef PreviousText = getSourceText(InsertionPoint);178 if (ReferencesText == PreviousText)179 return {Result, 0};180 181 // The loop above might collapse previously existing line breaks between182 // import blocks, and thus shrink the file. SortIncludes must not shrink183 // overall source length as there is currently no re-calculation of ranges184 // after applying source sorting.185 // This loop just backfills trailing spaces after the imports, which are186 // harmless and will be stripped by the subsequent formatting pass.187 // FIXME: A better long term fix is to re-calculate Ranges after sorting.188 unsigned PreviousSize = PreviousText.size();189 while (ReferencesText.size() < PreviousSize)190 ReferencesText += " ";191 192 // Separate references from the main code body of the file.193 if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2 &&194 !(FirstNonImportLine->First->is(tok::comment) &&195 isClangFormatOn(FirstNonImportLine->First->TokenText.trim()))) {196 ReferencesText += "\n";197 }198 199 LLVM_DEBUG(llvm::dbgs() << "Replacing imports:\n"200 << PreviousText << "\nwith:\n"201 << ReferencesText << "\n");202 auto Err = Result.add(tooling::Replacement(203 Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),204 ReferencesText));205 // FIXME: better error handling. For now, just print error message and skip206 // the replacement for the release version.207 if (Err) {208 llvm::errs() << toString(std::move(Err)) << "\n";209 assert(false);210 }211 212 return {Result, 0};213 }214 215private:216 FormatToken *Current = nullptr;217 FormatToken *LineEnd = nullptr;218 219 FormatToken invalidToken;220 221 StringRef FileContents;222 223 void skipComments() { Current = skipComments(Current); }224 225 FormatToken *skipComments(FormatToken *Tok) {226 while (Tok && Tok->is(tok::comment))227 Tok = Tok->Next;228 return Tok;229 }230 231 void nextToken() {232 Current = Current->Next;233 skipComments();234 if (!Current || Current == LineEnd->Next) {235 // Set the current token to an invalid token, so that further parsing on236 // this line fails.237 Current = &invalidToken;238 }239 }240 241 StringRef getSourceText(SourceRange Range) {242 return getSourceText(Range.getBegin(), Range.getEnd());243 }244 245 StringRef getSourceText(SourceLocation Begin, SourceLocation End) {246 const SourceManager &SM = Env.getSourceManager();247 return FileContents.substr(SM.getFileOffset(Begin),248 SM.getFileOffset(End) - SM.getFileOffset(Begin));249 }250 251 // Sorts the given module references.252 // Imports can have formatting disabled (FormattingOff), so the code below253 // skips runs of "no-formatting" module references, and sorts/merges the254 // references that have formatting enabled in individual chunks.255 SmallVector<JsModuleReference, 16>256 sortModuleReferences(const SmallVector<JsModuleReference, 16> &References) {257 // Sort module references.258 // Imports can have formatting disabled (FormattingOff), so the code below259 // skips runs of "no-formatting" module references, and sorts other260 // references per group.261 const auto *Start = References.begin();262 SmallVector<JsModuleReference, 16> ReferencesSorted;263 while (Start != References.end()) {264 while (Start != References.end() && Start->FormattingOff) {265 // Skip over all imports w/ disabled formatting.266 ReferencesSorted.push_back(*Start);267 ++Start;268 }269 SmallVector<JsModuleReference, 16> SortChunk;270 while (Start != References.end() && !Start->FormattingOff) {271 // Skip over all imports w/ disabled formatting.272 SortChunk.push_back(*Start);273 ++Start;274 }275 stable_sort(SortChunk);276 mergeModuleReferences(SortChunk);277 llvm::append_range(ReferencesSorted, SortChunk);278 }279 return ReferencesSorted;280 }281 282 // Merge module references.283 // After sorting, find all references that import named symbols from the284 // same URL and merge their names. E.g.285 // import {X} from 'a';286 // import {Y} from 'a';287 // should be rewritten to:288 // import {X, Y} from 'a';289 // Note: this modifies the passed in ``References`` vector (by removing no290 // longer needed references).291 void mergeModuleReferences(SmallVector<JsModuleReference, 16> &References) {292 if (References.empty())293 return;294 JsModuleReference *PreviousReference = References.begin();295 auto *Reference = std::next(References.begin());296 while (Reference != References.end()) {297 // Skip:298 // import 'foo';299 // import * as foo from 'foo'; on either previous or this.300 // import Default from 'foo'; on either previous or this.301 // mismatching302 if (Reference->Category == JsModuleReference::SIDE_EFFECT ||303 PreviousReference->Category == JsModuleReference::SIDE_EFFECT ||304 Reference->IsExport != PreviousReference->IsExport ||305 Reference->IsTypeOnly != PreviousReference->IsTypeOnly ||306 !PreviousReference->Prefix.empty() || !Reference->Prefix.empty() ||307 !PreviousReference->DefaultImport.empty() ||308 !Reference->DefaultImport.empty() || Reference->Symbols.empty() ||309 PreviousReference->URL != Reference->URL) {310 PreviousReference = Reference;311 ++Reference;312 continue;313 }314 // Merge symbols from identical imports.315 PreviousReference->Symbols.append(Reference->Symbols);316 PreviousReference->SymbolsMerged = true;317 // Remove the merged import.318 Reference = References.erase(Reference);319 }320 }321 322 // Appends ``Reference`` to ``Buffer``.323 void appendReference(std::string &Buffer, JsModuleReference &Reference) {324 if (Reference.FormattingOff) {325 Buffer +=326 getSourceText(Reference.Range.getBegin(), Reference.Range.getEnd());327 return;328 }329 // Sort the individual symbols within the import.330 // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';`331 SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols;332 stable_sort(Symbols,333 [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) {334 return LHS.Symbol.compare_insensitive(RHS.Symbol) < 0;335 });336 if (!Reference.SymbolsMerged && Symbols == Reference.Symbols) {337 // Symbols didn't change, just emit the entire module reference.338 StringRef ReferenceStmt = getSourceText(Reference.Range);339 Buffer += ReferenceStmt;340 return;341 }342 // Stitch together the module reference start...343 Buffer += getSourceText(Reference.Range.getBegin(), Reference.SymbolsStart);344 // ... then the references in order ...345 if (!Symbols.empty()) {346 Buffer += getSourceText(Symbols.front().Range);347 for (const JsImportedSymbol &Symbol : drop_begin(Symbols)) {348 Buffer += ",";349 Buffer += getSourceText(Symbol.Range);350 }351 }352 // ... followed by the module reference end.353 Buffer += getSourceText(Reference.SymbolsEnd, Reference.Range.getEnd());354 }355 356 // Parses module references in the given lines. Returns the module references,357 // and a pointer to the first "main code" line if that is adjacent to the358 // affected lines of module references, nullptr otherwise.359 std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine *>360 parseModuleReferences(const AdditionalKeywords &Keywords,361 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {362 SmallVector<JsModuleReference, 16> References;363 SourceLocation Start;364 AnnotatedLine *FirstNonImportLine = nullptr;365 bool AnyImportAffected = false;366 bool FormattingOff = false;367 for (auto *Line : AnnotatedLines) {368 assert(Line->First);369 Current = Line->First;370 LineEnd = Line->Last;371 // clang-format comments toggle formatting on/off.372 // This is tracked in FormattingOff here and on JsModuleReference.373 while (Current && Current->is(tok::comment)) {374 StringRef CommentText = Current->TokenText.trim();375 if (isClangFormatOff(CommentText)) {376 FormattingOff = true;377 } else if (isClangFormatOn(CommentText)) {378 FormattingOff = false;379 // Special case: consider a trailing "clang-format on" line to be part380 // of the module reference, so that it gets moved around together with381 // it (as opposed to the next module reference, which might get sorted382 // around).383 if (!References.empty()) {384 References.back().Range.setEnd(Current->Tok.getEndLoc());385 Start = Current->Tok.getEndLoc().getLocWithOffset(1);386 }387 }388 // Handle all clang-format comments on a line, e.g. for an empty block.389 Current = Current->Next;390 }391 skipComments();392 if (Start.isInvalid() || References.empty()) {393 // After the first file level comment, consider line comments to be part394 // of the import that immediately follows them by using the previously395 // set Start.396 Start = Line->First->Tok.getLocation();397 }398 if (!Current) {399 // Only comments on this line. Could be the first non-import line.400 FirstNonImportLine = Line;401 continue;402 }403 JsModuleReference Reference;404 Reference.FormattingOff = FormattingOff;405 Reference.Range.setBegin(Start);406 // References w/o a URL, e.g. export {A}, groups with RELATIVE.407 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;408 if (!parseModuleReference(Keywords, Reference)) {409 if (!FirstNonImportLine)410 FirstNonImportLine = Line; // if no comment before.411 break;412 }413 FirstNonImportLine = nullptr;414 AnyImportAffected = AnyImportAffected || Line->Affected;415 Reference.Range.setEnd(LineEnd->Tok.getEndLoc());416 LLVM_DEBUG({417 llvm::dbgs() << "JsModuleReference: {"418 << "formatting_off: " << Reference.FormattingOff419 << ", is_export: " << Reference.IsExport420 << ", cat: " << Reference.Category421 << ", url: " << Reference.URL422 << ", prefix: " << Reference.Prefix;423 for (const JsImportedSymbol &Symbol : Reference.Symbols)424 llvm::dbgs() << ", " << Symbol.Symbol << " as " << Symbol.Alias;425 llvm::dbgs() << ", text: " << getSourceText(Reference.Range);426 llvm::dbgs() << "}\n";427 });428 References.push_back(Reference);429 Start = SourceLocation();430 }431 // Sort imports if any import line was affected.432 if (!AnyImportAffected)433 References.clear();434 return std::make_pair(References, FirstNonImportLine);435 }436 437 // Parses a JavaScript/ECMAScript 6 module reference.438 // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules439 // for grammar EBNF (production ModuleItem).440 bool parseModuleReference(const AdditionalKeywords &Keywords,441 JsModuleReference &Reference) {442 if (!Current || Current->isNoneOf(Keywords.kw_import, tok::kw_export))443 return false;444 Reference.IsExport = Current->is(tok::kw_export);445 446 nextToken();447 if (Current->isStringLiteral() && !Reference.IsExport) {448 // "import 'side-effect';"449 Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;450 Reference.URL =451 Current->TokenText.substr(1, Current->TokenText.size() - 2);452 return true;453 }454 455 if (!parseModuleBindings(Keywords, Reference))456 return false;457 458 if (Current->is(Keywords.kw_from)) {459 // imports have a 'from' clause, exports might not.460 nextToken();461 if (!Current->isStringLiteral())462 return false;463 // URL = TokenText without the quotes.464 Reference.URL =465 Current->TokenText.substr(1, Current->TokenText.size() - 2);466 if (Reference.URL.starts_with("..")) {467 Reference.Category =468 JsModuleReference::ReferenceCategory::RELATIVE_PARENT;469 } else if (Reference.URL.starts_with(".")) {470 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;471 } else {472 Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;473 }474 }475 return true;476 }477 478 bool parseModuleBindings(const AdditionalKeywords &Keywords,479 JsModuleReference &Reference) {480 if (parseStarBinding(Keywords, Reference))481 return true;482 return parseNamedBindings(Keywords, Reference);483 }484 485 bool parseStarBinding(const AdditionalKeywords &Keywords,486 JsModuleReference &Reference) {487 // * as prefix from '...';488 if (Current->is(Keywords.kw_type) && Current->Next &&489 Current->Next->is(tok::star)) {490 Reference.IsTypeOnly = true;491 nextToken();492 }493 if (Current->isNot(tok::star))494 return false;495 nextToken();496 if (Current->isNot(Keywords.kw_as))497 return false;498 nextToken();499 if (Current->isNot(tok::identifier))500 return false;501 Reference.Prefix = Current->TokenText;502 nextToken();503 return true;504 }505 506 bool parseNamedBindings(const AdditionalKeywords &Keywords,507 JsModuleReference &Reference) {508 if (Current->is(Keywords.kw_type) && Current->Next &&509 Current->Next->isOneOf(tok::identifier, tok::l_brace)) {510 Reference.IsTypeOnly = true;511 nextToken();512 }513 514 // eat a potential "import X, " prefix.515 if (!Reference.IsExport && Current->is(tok::identifier)) {516 Reference.DefaultImport = Current->TokenText;517 nextToken();518 if (Current->is(Keywords.kw_from))519 return true;520 // import X = A.B.C;521 if (Current->is(tok::equal)) {522 Reference.Category = JsModuleReference::ReferenceCategory::ALIAS;523 nextToken();524 while (Current->is(tok::identifier)) {525 nextToken();526 if (Current->is(tok::semi))527 return true;528 if (Current->isNot(tok::period))529 return false;530 nextToken();531 }532 }533 if (Current->isNot(tok::comma))534 return false;535 nextToken(); // eat comma.536 }537 if (Current->isNot(tok::l_brace))538 return false;539 540 // {sym as alias, sym2 as ...} from '...';541 Reference.SymbolsStart = Current->Tok.getEndLoc();542 while (Current->isNot(tok::r_brace)) {543 nextToken();544 if (Current->is(tok::r_brace))545 break;546 auto IsIdentifier = [](const auto *Tok) {547 return Tok->isOneOf(tok::identifier, tok::kw_default, tok::kw_template);548 };549 bool isTypeOnly = Current->is(Keywords.kw_type) && Current->Next &&550 IsIdentifier(Current->Next);551 if (!isTypeOnly && !IsIdentifier(Current))552 return false;553 554 JsImportedSymbol Symbol;555 // Make sure to include any preceding comments.556 Symbol.Range.setBegin(557 Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin());558 if (isTypeOnly)559 nextToken();560 Symbol.Symbol = Current->TokenText;561 nextToken();562 563 if (Current->is(Keywords.kw_as)) {564 nextToken();565 if (!IsIdentifier(Current))566 return false;567 Symbol.Alias = Current->TokenText;568 nextToken();569 }570 Symbol.Range.setEnd(Current->Tok.getLocation());571 Reference.Symbols.push_back(Symbol);572 573 if (Current->isNoneOf(tok::r_brace, tok::comma))574 return false;575 }576 Reference.SymbolsEnd = Current->Tok.getLocation();577 // For named imports with a trailing comma ("import {X,}"), consider the578 // comma to be the end of the import list, so that it doesn't get removed.579 if (Current->Previous->is(tok::comma))580 Reference.SymbolsEnd = Current->Previous->Tok.getLocation();581 nextToken(); // consume r_brace582 return true;583 }584};585 586tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,587 StringRef Code,588 ArrayRef<tooling::Range> Ranges,589 StringRef FileName) {590 // FIXME: Cursor support.591 auto Env = Environment::make(Code, FileName, Ranges);592 if (!Env)593 return {};594 return JavaScriptImportSorter(*Env, Style).process().first;595}596 597} // end namespace format598} // end namespace clang599