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 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 FormattingOff = false; 74 bool IsExport = false; 75 // Module references are sorted into these categories, in order. 76 enum ReferenceCategory { 77 SIDE_EFFECT, // "import 'something';" 78 ABSOLUTE, // from 'something' 79 RELATIVE_PARENT, // from '../*' 80 RELATIVE, // from './*' 81 ALIAS, // import X = A.B; 82 }; 83 ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT; 84 // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`. 85 StringRef URL; 86 // Prefix from "import * as prefix". Empty for symbol imports and `export *`. 87 // Implies an empty names list. 88 StringRef Prefix; 89 // Default import from "import DefaultName from '...';". 90 StringRef DefaultImport; 91 // Symbols from `import {SymbolA, SymbolB, ...} from ...;`. 92 SmallVector<JsImportedSymbol, 1> Symbols; 93 // Whether some symbols were merged into this one. Controls if the module 94 // reference needs re-formatting. 95 bool SymbolsMerged = false; 96 // The source location just after { and just before } in the import. 97 // Extracted eagerly to allow modification of Symbols later on. 98 SourceLocation SymbolsStart, SymbolsEnd; 99 // Textual position of the import/export, including preceding and trailing 100 // comments. 101 SourceRange Range; 102 }; 103 104 bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS) { 105 if (LHS.IsExport != RHS.IsExport) 106 return LHS.IsExport < RHS.IsExport; 107 if (LHS.Category != RHS.Category) 108 return LHS.Category < RHS.Category; 109 if (LHS.Category == JsModuleReference::ReferenceCategory::SIDE_EFFECT || 110 LHS.Category == JsModuleReference::ReferenceCategory::ALIAS) 111 // Side effect imports and aliases might be ordering sensitive. Consider 112 // them equal so that they maintain their relative order in the stable sort 113 // below. This retains transitivity because LHS.Category == RHS.Category 114 // here. 115 return false; 116 // Empty URLs sort *last* (for export {...};). 117 if (LHS.URL.empty() != RHS.URL.empty()) 118 return LHS.URL.empty() < RHS.URL.empty(); 119 if (int Res = LHS.URL.compare_insensitive(RHS.URL)) 120 return Res < 0; 121 // '*' imports (with prefix) sort before {a, b, ...} imports. 122 if (LHS.Prefix.empty() != RHS.Prefix.empty()) 123 return LHS.Prefix.empty() < RHS.Prefix.empty(); 124 if (LHS.Prefix != RHS.Prefix) 125 return LHS.Prefix > RHS.Prefix; 126 return false; 127 } 128 129 // JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is 130 // implemented as a TokenAnalyzer because ES6 imports have substantial syntactic 131 // structure, making it messy to sort them using regular expressions. 132 class JavaScriptImportSorter : public TokenAnalyzer { 133 public: 134 JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style) 135 : TokenAnalyzer(Env, Style), 136 FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) { 137 // FormatToken.Tok starts out in an uninitialized state. 138 invalidToken.Tok.startToken(); 139 } 140 141 std::pair<tooling::Replacements, unsigned> 142 analyze(TokenAnnotator &Annotator, 143 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines, 144 FormatTokenLexer &Tokens) override { 145 tooling::Replacements Result; 146 AffectedRangeMgr.computeAffectedLines(AnnotatedLines); 147 148 const AdditionalKeywords &Keywords = Tokens.getKeywords(); 149 SmallVector<JsModuleReference, 16> References; 150 AnnotatedLine *FirstNonImportLine; 151 std::tie(References, FirstNonImportLine) = 152 parseModuleReferences(Keywords, AnnotatedLines); 153 154 if (References.empty()) 155 return {Result, 0}; 156 157 // The text range of all parsed imports, to be replaced later. 158 SourceRange InsertionPoint = References[0].Range; 159 InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd()); 160 161 References = sortModuleReferences(References); 162 163 std::string ReferencesText; 164 for (unsigned I = 0, E = References.size(); I != E; ++I) { 165 JsModuleReference Reference = References[I]; 166 appendReference(ReferencesText, Reference); 167 if (I + 1 < E) { 168 // Insert breaks between imports and exports. 169 ReferencesText += "\n"; 170 // Separate imports groups with two line breaks, but keep all exports 171 // in a single group. 172 if (!Reference.IsExport && 173 (Reference.IsExport != References[I + 1].IsExport || 174 Reference.Category != References[I + 1].Category)) 175 ReferencesText += "\n"; 176 } 177 } 178 llvm::StringRef PreviousText = getSourceText(InsertionPoint); 179 if (ReferencesText == PreviousText) 180 return {Result, 0}; 181 182 // The loop above might collapse previously existing line breaks between 183 // import blocks, and thus shrink the file. SortIncludes must not shrink 184 // overall source length as there is currently no re-calculation of ranges 185 // after applying source sorting. 186 // This loop just backfills trailing spaces after the imports, which are 187 // harmless and will be stripped by the subsequent formatting pass. 188 // FIXME: A better long term fix is to re-calculate Ranges after sorting. 189 unsigned PreviousSize = PreviousText.size(); 190 while (ReferencesText.size() < PreviousSize) { 191 ReferencesText += " "; 192 } 193 194 // Separate references from the main code body of the file. 195 if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2 && 196 !(FirstNonImportLine->First->is(tok::comment) && 197 FirstNonImportLine->First->TokenText.trim() == "// clang-format on")) 198 ReferencesText += "\n"; 199 200 LLVM_DEBUG(llvm::dbgs() << "Replacing imports:\n" 201 << PreviousText << "\nwith:\n" 202 << ReferencesText << "\n"); 203 auto Err = Result.add(tooling::Replacement( 204 Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint), 205 ReferencesText)); 206 // FIXME: better error handling. For now, just print error message and skip 207 // the replacement for the release version. 208 if (Err) { 209 llvm::errs() << llvm::toString(std::move(Err)) << "\n"; 210 assert(false); 211 } 212 213 return {Result, 0}; 214 } 215 216 private: 217 FormatToken *Current; 218 FormatToken *LineEnd; 219 220 FormatToken invalidToken; 221 222 StringRef FileContents; 223 224 void skipComments() { Current = skipComments(Current); } 225 226 FormatToken *skipComments(FormatToken *Tok) { 227 while (Tok && Tok->is(tok::comment)) 228 Tok = Tok->Next; 229 return Tok; 230 } 231 232 void nextToken() { 233 Current = Current->Next; 234 skipComments(); 235 if (!Current || Current == LineEnd->Next) { 236 // Set the current token to an invalid token, so that further parsing on 237 // this line fails. 238 Current = &invalidToken; 239 } 240 } 241 242 StringRef getSourceText(SourceRange Range) { 243 return getSourceText(Range.getBegin(), Range.getEnd()); 244 } 245 246 StringRef getSourceText(SourceLocation Begin, SourceLocation End) { 247 const SourceManager &SM = Env.getSourceManager(); 248 return FileContents.substr(SM.getFileOffset(Begin), 249 SM.getFileOffset(End) - SM.getFileOffset(Begin)); 250 } 251 252 // Sorts the given module references. 253 // Imports can have formatting disabled (FormattingOff), so the code below 254 // skips runs of "no-formatting" module references, and sorts/merges the 255 // references that have formatting enabled in individual chunks. 256 SmallVector<JsModuleReference, 16> 257 sortModuleReferences(const SmallVector<JsModuleReference, 16> &References) { 258 // Sort module references. 259 // Imports can have formatting disabled (FormattingOff), so the code below 260 // skips runs of "no-formatting" module references, and sorts other 261 // references per group. 262 const auto *Start = References.begin(); 263 SmallVector<JsModuleReference, 16> ReferencesSorted; 264 while (Start != References.end()) { 265 while (Start != References.end() && Start->FormattingOff) { 266 // Skip over all imports w/ disabled formatting. 267 ReferencesSorted.push_back(*Start); 268 ++Start; 269 } 270 SmallVector<JsModuleReference, 16> SortChunk; 271 while (Start != References.end() && !Start->FormattingOff) { 272 // Skip over all imports w/ disabled formatting. 273 SortChunk.push_back(*Start); 274 ++Start; 275 } 276 llvm::stable_sort(SortChunk); 277 mergeModuleReferences(SortChunk); 278 ReferencesSorted.insert(ReferencesSorted.end(), SortChunk.begin(), 279 SortChunk.end()); 280 } 281 return ReferencesSorted; 282 } 283 284 // Merge module references. 285 // After sorting, find all references that import named symbols from the 286 // same URL and merge their names. E.g. 287 // import {X} from 'a'; 288 // import {Y} from 'a'; 289 // should be rewritten to: 290 // import {X, Y} from 'a'; 291 // Note: this modifies the passed in ``References`` vector (by removing no 292 // longer needed references). 293 void mergeModuleReferences(SmallVector<JsModuleReference, 16> &References) { 294 if (References.empty()) 295 return; 296 JsModuleReference *PreviousReference = References.begin(); 297 auto *Reference = std::next(References.begin()); 298 while (Reference != References.end()) { 299 // Skip: 300 // import 'foo'; 301 // import * as foo from 'foo'; on either previous or this. 302 // import Default from 'foo'; on either previous or this. 303 // mismatching 304 if (Reference->Category == JsModuleReference::SIDE_EFFECT || 305 PreviousReference->Category == JsModuleReference::SIDE_EFFECT || 306 Reference->IsExport != PreviousReference->IsExport || 307 !PreviousReference->Prefix.empty() || !Reference->Prefix.empty() || 308 !PreviousReference->DefaultImport.empty() || 309 !Reference->DefaultImport.empty() || Reference->Symbols.empty() || 310 PreviousReference->URL != Reference->URL) { 311 PreviousReference = Reference; 312 ++Reference; 313 continue; 314 } 315 // Merge symbols from identical imports. 316 PreviousReference->Symbols.append(Reference->Symbols); 317 PreviousReference->SymbolsMerged = true; 318 // Remove the merged import. 319 Reference = References.erase(Reference); 320 } 321 } 322 323 // Appends ``Reference`` to ``Buffer``. 324 void appendReference(std::string &Buffer, JsModuleReference &Reference) { 325 if (Reference.FormattingOff) { 326 Buffer += 327 getSourceText(Reference.Range.getBegin(), Reference.Range.getEnd()); 328 return; 329 } 330 // Sort the individual symbols within the import. 331 // E.g. `import {b, a} from 'x';` -> `import {a, b} from 'x';` 332 SmallVector<JsImportedSymbol, 1> Symbols = Reference.Symbols; 333 llvm::stable_sort( 334 Symbols, [&](const JsImportedSymbol &LHS, const JsImportedSymbol &RHS) { 335 return LHS.Symbol.compare_insensitive(RHS.Symbol) < 0; 336 }); 337 if (!Reference.SymbolsMerged && Symbols == Reference.Symbols) { 338 // Symbols didn't change, just emit the entire module reference. 339 StringRef ReferenceStmt = getSourceText(Reference.Range); 340 Buffer += ReferenceStmt; 341 return; 342 } 343 // Stitch together the module reference start... 344 Buffer += getSourceText(Reference.Range.getBegin(), Reference.SymbolsStart); 345 // ... then the references in order ... 346 if (!Symbols.empty()) { 347 Buffer += getSourceText(Symbols.front().Range); 348 for (const JsImportedSymbol &Symbol : llvm::drop_begin(Symbols)) { 349 Buffer += ","; 350 Buffer += getSourceText(Symbol.Range); 351 } 352 } 353 // ... followed by the module reference end. 354 Buffer += getSourceText(Reference.SymbolsEnd, Reference.Range.getEnd()); 355 } 356 357 // Parses module references in the given lines. Returns the module references, 358 // and a pointer to the first "main code" line if that is adjacent to the 359 // affected lines of module references, nullptr otherwise. 360 std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine *> 361 parseModuleReferences(const AdditionalKeywords &Keywords, 362 SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) { 363 SmallVector<JsModuleReference, 16> References; 364 SourceLocation Start; 365 AnnotatedLine *FirstNonImportLine = nullptr; 366 bool AnyImportAffected = false; 367 bool FormattingOff = false; 368 for (auto *Line : AnnotatedLines) { 369 assert(Line->First); 370 Current = Line->First; 371 LineEnd = Line->Last; 372 // clang-format comments toggle formatting on/off. 373 // This is tracked in FormattingOff here and on JsModuleReference. 374 while (Current && Current->is(tok::comment)) { 375 StringRef CommentText = Current->TokenText.trim(); 376 if (CommentText == "// clang-format off") { 377 FormattingOff = true; 378 } else if (CommentText == "// clang-format on") { 379 FormattingOff = false; 380 // Special case: consider a trailing "clang-format on" line to be part 381 // of the module reference, so that it gets moved around together with 382 // it (as opposed to the next module reference, which might get sorted 383 // around). 384 if (!References.empty()) { 385 References.back().Range.setEnd(Current->Tok.getEndLoc()); 386 Start = Current->Tok.getEndLoc().getLocWithOffset(1); 387 } 388 } 389 // Handle all clang-format comments on a line, e.g. for an empty block. 390 Current = Current->Next; 391 } 392 skipComments(); 393 if (Start.isInvalid() || References.empty()) 394 // After the first file level comment, consider line comments to be part 395 // of the import that immediately follows them by using the previously 396 // set Start. 397 Start = Line->First->Tok.getLocation(); 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.FormattingOff 419 << ", is_export: " << Reference.IsExport 420 << ", cat: " << Reference.Category 421 << ", url: " << Reference.URL 422 << ", 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-modules 439 // for grammar EBNF (production ModuleItem). 440 bool parseModuleReference(const AdditionalKeywords &Keywords, 441 JsModuleReference &Reference) { 442 if (!Current || !Current->isOneOf(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.startswith("..")) 467 Reference.Category = 468 JsModuleReference::ReferenceCategory::RELATIVE_PARENT; 469 else if (Reference.URL.startswith(".")) 470 Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE; 471 else 472 Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE; 473 } 474 return true; 475 } 476 477 bool parseModuleBindings(const AdditionalKeywords &Keywords, 478 JsModuleReference &Reference) { 479 if (parseStarBinding(Keywords, Reference)) 480 return true; 481 return parseNamedBindings(Keywords, Reference); 482 } 483 484 bool parseStarBinding(const AdditionalKeywords &Keywords, 485 JsModuleReference &Reference) { 486 // * as prefix from '...'; 487 if (Current->isNot(tok::star)) 488 return false; 489 nextToken(); 490 if (Current->isNot(Keywords.kw_as)) 491 return false; 492 nextToken(); 493 if (Current->isNot(tok::identifier)) 494 return false; 495 Reference.Prefix = Current->TokenText; 496 nextToken(); 497 return true; 498 } 499 500 bool parseNamedBindings(const AdditionalKeywords &Keywords, 501 JsModuleReference &Reference) { 502 // eat a potential "import X, " prefix. 503 if (Current->is(tok::identifier)) { 504 Reference.DefaultImport = Current->TokenText; 505 nextToken(); 506 if (Current->is(Keywords.kw_from)) 507 return true; 508 // import X = A.B.C; 509 if (Current->is(tok::equal)) { 510 Reference.Category = JsModuleReference::ReferenceCategory::ALIAS; 511 nextToken(); 512 while (Current->is(tok::identifier)) { 513 nextToken(); 514 if (Current->is(tok::semi)) { 515 return true; 516 } 517 if (!Current->is(tok::period)) 518 return false; 519 nextToken(); 520 } 521 } 522 if (Current->isNot(tok::comma)) 523 return false; 524 nextToken(); // eat comma. 525 } 526 if (Current->isNot(tok::l_brace)) 527 return false; 528 529 // {sym as alias, sym2 as ...} from '...'; 530 Reference.SymbolsStart = Current->Tok.getEndLoc(); 531 while (Current->isNot(tok::r_brace)) { 532 nextToken(); 533 if (Current->is(tok::r_brace)) 534 break; 535 if (!Current->isOneOf(tok::identifier, tok::kw_default)) 536 return false; 537 538 JsImportedSymbol Symbol; 539 Symbol.Symbol = Current->TokenText; 540 // Make sure to include any preceding comments. 541 Symbol.Range.setBegin( 542 Current->getPreviousNonComment()->Next->WhitespaceRange.getBegin()); 543 nextToken(); 544 545 if (Current->is(Keywords.kw_as)) { 546 nextToken(); 547 if (!Current->isOneOf(tok::identifier, tok::kw_default)) 548 return false; 549 Symbol.Alias = Current->TokenText; 550 nextToken(); 551 } 552 Symbol.Range.setEnd(Current->Tok.getLocation()); 553 Reference.Symbols.push_back(Symbol); 554 555 if (!Current->isOneOf(tok::r_brace, tok::comma)) 556 return false; 557 } 558 Reference.SymbolsEnd = Current->Tok.getLocation(); 559 // For named imports with a trailing comma ("import {X,}"), consider the 560 // comma to be the end of the import list, so that it doesn't get removed. 561 if (Current->Previous->is(tok::comma)) 562 Reference.SymbolsEnd = Current->Previous->Tok.getLocation(); 563 nextToken(); // consume r_brace 564 return true; 565 } 566 }; 567 568 tooling::Replacements sortJavaScriptImports(const FormatStyle &Style, 569 StringRef Code, 570 ArrayRef<tooling::Range> Ranges, 571 StringRef FileName) { 572 // FIXME: Cursor support. 573 auto Env = Environment::make(Code, FileName, Ranges); 574 if (!Env) 575 return {}; 576 return JavaScriptImportSorter(*Env, Style).process().first; 577 } 578 579 } // end namespace format 580 } // end namespace clang 581