clang-format: [JS] sort ES6 imports.

Summary:
This change automatically sorts ES6 imports and exports into four groups:
absolute imports, parent imports, relative imports, and then exports. Exports
are sorted in the same order, but not grouped further.

To keep JS import sorting out of Format.cpp, this required extracting the
TokenAnalyzer infrastructure to separate header and implementation files.

Reviewers: djasper

Subscribers: cfe-commits, klimek

Differential Revision: http://reviews.llvm.org/D20198

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@270203 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 385 insertions, 0 deletions

diff --git a/lib/Format/SortJavaScriptImports.cpp b/lib/Format/SortJavaScriptImports.cpp
new file mode 100644
index 0000000000..62a836395d
--- /dev/null
+++ b/lib/Format/SortJavaScriptImports.cpp
@@ -0,0 +1,385 @@
+//===--- SortJavaScriptImports.h - Sort ES6 Imports -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file implements a sort operation for JavaScript ES6 imports.
+///
+//===----------------------------------------------------------------------===//
+
+#include "SortJavaScriptImports.h"
+#include "SortJavaScriptImports.h"
+#include "TokenAnalyzer.h"
+#include "TokenAnnotator.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/DiagnosticOptions.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Format/Format.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Debug.h"
+#include <string>
+
+#define DEBUG_TYPE "format-formatter"
+
+namespace clang {
+namespace format {
+
+class FormatTokenLexer;
+
+using clang::format::FormatStyle;
+
+// An imported symbol in a JavaScript ES6 import/export, possibly aliased.
+struct JsImportedSymbol {
+  StringRef Symbol;
+  StringRef Alias;
+};
+
+// An ES6 module reference.
+//
+// ES6 implements a module system, where individual modules (~= source files)
+// can reference other modules, either importing symbols from them, or exporting
+// symbols from them:
+//   import {foo} from 'foo';
+//   export {foo};
+//   export {bar} from 'bar';
+//
+// `export`s with URLs are syntactic sugar for an import of the symbol from the
+// URL, followed by an export of the symbol, allowing this code to treat both
+// statements more or less identically, with the exception being that `export`s
+// are sorted last.
+//
+// imports and exports support individual symbols, but also a wildcard syntax:
+//   import * as prefix from 'foo';
+//   export * from 'bar';
+//
+// This struct represents both exports and imports to build up the information
+// required for sorting module references.
+struct JsModuleReference {
+  bool IsExport = false;
+  // Module references are sorted into these categories, in order.
+  enum ReferenceCategory {
+    SIDE_EFFECT,     // "import 'something';"
+    ABSOLUTE,        // from 'something'
+    RELATIVE_PARENT, // from '../*'
+    RELATIVE,        // from './*'
+  };
+  ReferenceCategory Category = ReferenceCategory::SIDE_EFFECT;
+  // The URL imported, e.g. `import .. from 'url';`. Empty for `export {a, b};`.
+  StringRef URL;
+  // Prefix from "import * as prefix". Empty for symbol imports and `export *`.
+  // Implies an empty names list.
+  StringRef Prefix;
+  // Symbols from `import {SymbolA, SymbolB, ...} from ...;`.
+  SmallVector<JsImportedSymbol, 1> Symbols;
+  // Textual position of the import/export, including preceding and trailing
+  // comments.
+  SourceRange Range;
+};
+
+bool operator<(const JsModuleReference &LHS, const JsModuleReference &RHS) {
+  if (LHS.IsExport != RHS.IsExport)
+    return LHS.IsExport < RHS.IsExport;
+  if (LHS.Category != RHS.Category)
+    return LHS.Category < RHS.Category;
+  if (LHS.Category == JsModuleReference::ReferenceCategory::SIDE_EFFECT)
+    // Side effect imports might be ordering sensitive. Consider them equal so
+    // that they maintain their relative order in the stable sort below.
+    // This retains transitivity because LHS.Category == RHS.Category here.
+    return false;
+  // Empty URLs sort *last* (for export {...};).
+  if (LHS.URL.empty() != RHS.URL.empty())
+    return LHS.URL.empty() < RHS.URL.empty();
+  if (LHS.URL != RHS.URL)
+    return LHS.URL < RHS.URL;
+  // '*' imports (with prefix) sort before {a, b, ...} imports.
+  if (LHS.Prefix.empty() != RHS.Prefix.empty())
+    return LHS.Prefix.empty() < RHS.Prefix.empty();
+  if (LHS.Prefix != RHS.Prefix)
+    return LHS.Prefix > RHS.Prefix;
+  return false;
+}
+
+// JavaScriptImportSorter sorts JavaScript ES6 imports and exports. It is
+// implemented as a TokenAnalyzer because ES6 imports have substantial syntactic
+// structure, making it messy to sort them using regular expressions.
+class JavaScriptImportSorter : public TokenAnalyzer {
+public:
+  JavaScriptImportSorter(const Environment &Env, const FormatStyle &Style)
+      : TokenAnalyzer(Env, Style),
+        FileContents(Env.getSourceManager().getBufferData(Env.getFileID())) {}
+
+  tooling::Replacements
+  analyze(TokenAnnotator &Annotator,
+          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
+          FormatTokenLexer &Tokens, tooling::Replacements &Result) override {
+    AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
+                                          AnnotatedLines.end());
+
+    const AdditionalKeywords &Keywords = Tokens.getKeywords();
+    SmallVector<JsModuleReference, 16> References;
+    AnnotatedLine *FirstNonImportLine;
+    std::tie(References, FirstNonImportLine) =
+        parseModuleReferences(Keywords, AnnotatedLines);
+
+    if (References.empty())
+      return Result;
+
+    SmallVector<unsigned, 16> Indices;
+    for (unsigned i = 0, e = References.size(); i != e; ++i)
+      Indices.push_back(i);
+    std::stable_sort(Indices.begin(), Indices.end(),
+                     [&](unsigned LHSI, unsigned RHSI) {
+                       return References[LHSI] < References[RHSI];
+                     });
+    // FIXME: Pull this into a common function.
+    bool OutOfOrder = false;
+    for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
+      if (i != Indices[i]) {
+        OutOfOrder = true;
+        break;
+      }
+    }
+    if (!OutOfOrder)
+      return Result;
+
+    // Replace all existing import/export statements.
+    std::string ReferencesText;
+    for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
+      JsModuleReference Reference = References[Indices[i]];
+      StringRef ReferenceStmt = getSourceText(Reference.Range);
+      ReferencesText += ReferenceStmt;
+      if (i + 1 < e) {
+        // Insert breaks between imports and exports.
+        ReferencesText += "\n";
+        // Separate imports groups with two line breaks, but keep all exports
+        // in a single group.
+        if (!Reference.IsExport &&
+            (Reference.IsExport != References[Indices[i + 1]].IsExport ||
+             Reference.Category != References[Indices[i + 1]].Category))
+          ReferencesText += "\n";
+      }
+    }
+    // Separate references from the main code body of the file.
+    if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2)
+      ReferencesText += "\n";
+
+    SourceRange InsertionPoint = References[0].Range;
+    InsertionPoint.setEnd(References[References.size() - 1].Range.getEnd());
+    DEBUG(llvm::dbgs() << "Replacing imports:\n"
+                       << getSourceText(InsertionPoint) << "\nwith:\n"
+                       << ReferencesText << "\n");
+    Result.insert(tooling::Replacement(
+        Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),
+        ReferencesText));
+
+    return Result;
+  }
+
+private:
+  FormatToken *Current;
+  FormatToken *LineEnd;
+
+  FormatToken invalidToken;
+
+  StringRef FileContents;
+
+  void skipComments() { Current = skipComments(Current); }
+
+  FormatToken *skipComments(FormatToken *Tok) {
+    while (Tok && Tok->is(tok::comment))
+      Tok = Tok->Next;
+    return Tok;
+  }
+
+  void nextToken() {
+    Current = Current->Next;
+    skipComments();
+    if (!Current || Current == LineEnd->Next) {
+      // Set the current token to an invalid token, so that further parsing on
+      // this line fails.
+      invalidToken.Tok.setKind(tok::unknown);
+      Current = &invalidToken;
+    }
+  }
+
+  StringRef getSourceText(SourceRange Range) {
+    const SourceManager &SM = Env.getSourceManager();
+    return FileContents.substr(SM.getFileOffset(Range.getBegin()),
+                               SM.getFileOffset(Range.getEnd()) -
+                                   SM.getFileOffset(Range.getBegin()));
+  }
+
+  // Parses module references in the given lines. Returns the module references,
+  // and a pointer to the first "main code" line if that is adjacent to the
+  // affected lines of module references, nullptr otherwise.
+  std::pair<SmallVector<JsModuleReference, 16>, AnnotatedLine*>
+  parseModuleReferences(const AdditionalKeywords &Keywords,
+                        SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
+    SmallVector<JsModuleReference, 16> References;
+    SourceLocation Start;
+    bool FoundLines = false;
+    AnnotatedLine *FirstNonImportLine = nullptr;
+    for (auto Line : AnnotatedLines) {
+      if (!Line->Affected) {
+        // Only sort the first contiguous block of affected lines.
+        if (FoundLines)
+          break;
+        else
+          continue;
+      }
+      Current = Line->First;
+      LineEnd = Line->Last;
+      skipComments();
+      if (Start.isInvalid() || References.empty())
+        // After the first file level comment, consider line comments to be part
+        // of the import that immediately follows them by using the previously
+        // set Start.
+        Start = Line->First->Tok.getLocation();
+      if (!Current)
+        continue; // Only comments on this line.
+      FoundLines = true;
+      JsModuleReference Reference;
+      Reference.Range.setBegin(Start);
+      if (!parseModuleReference(Keywords, Reference)) {
+        FirstNonImportLine = Line;
+        break;
+      }
+      Reference.Range.setEnd(LineEnd->Tok.getEndLoc());
+      DEBUG({
+        llvm::dbgs() << "JsModuleReference: {"
+                     << "is_export: " << Reference.IsExport
+                     << ", cat: " << Reference.Category
+                     << ", url: " << Reference.URL
+                     << ", prefix: " << Reference.Prefix;
+        for (size_t i = 0; i < Reference.Symbols.size(); ++i)
+          llvm::dbgs() << ", " << Reference.Symbols[i].Symbol << " as "
+                       << Reference.Symbols[i].Alias;
+        llvm::dbgs() << ", text: " << getSourceText(Reference.Range);
+        llvm::dbgs() << "}\n";
+      });
+      References.push_back(Reference);
+      Start = SourceLocation();
+    }
+    return std::make_pair(References, FirstNonImportLine);
+  }
+
+  // Parses a JavaScript/ECMAScript 6 module reference.
+  // See http://www.ecma-international.org/ecma-262/6.0/#sec-scripts-and-modules
+  // for grammar EBNF (production ModuleItem).
+  bool parseModuleReference(const AdditionalKeywords &Keywords,
+                            JsModuleReference &Reference) {
+    if (!Current || !Current->isOneOf(Keywords.kw_import, tok::kw_export))
+      return false;
+    Reference.IsExport = Current->is(tok::kw_export);
+
+    nextToken();
+    if (Current->isStringLiteral() && !Reference.IsExport) {
+      // "import 'side-effect';"
+      Reference.Category = JsModuleReference::ReferenceCategory::SIDE_EFFECT;
+      Reference.URL =
+          Current->TokenText.substr(1, Current->TokenText.size() - 2);
+      return true;
+    }
+
+    if (!parseModuleBindings(Keywords, Reference))
+      return false;
+    nextToken();
+
+    if (Current->is(Keywords.kw_from)) {
+      // imports have a 'from' clause, exports might not.
+      nextToken();
+      if (!Current->isStringLiteral())
+        return false;
+      // URL = TokenText without the quotes.
+      Reference.URL =
+          Current->TokenText.substr(1, Current->TokenText.size() - 2);
+      if (Reference.URL.startswith(".."))
+        Reference.Category =
+            JsModuleReference::ReferenceCategory::RELATIVE_PARENT;
+      else if (Reference.URL.startswith("."))
+        Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
+      else
+        Reference.Category = JsModuleReference::ReferenceCategory::ABSOLUTE;
+    } else {
+      // w/o URL groups with "empty".
+      Reference.Category = JsModuleReference::ReferenceCategory::RELATIVE;
+    }
+    return true;
+  }
+
+  bool parseModuleBindings(const AdditionalKeywords &Keywords,
+                           JsModuleReference &Reference) {
+    if (parseStarBinding(Keywords, Reference))
+      return true;
+    return parseNamedBindings(Keywords, Reference);
+  }
+
+  bool parseStarBinding(const AdditionalKeywords &Keywords,
+                        JsModuleReference &Reference) {
+    // * as prefix from '...';
+    if (Current->isNot(tok::star))
+      return false;
+    nextToken();
+    if (Current->isNot(Keywords.kw_as))
+      return false;
+    nextToken();
+    if (Current->isNot(tok::identifier))
+      return false;
+    Reference.Prefix = Current->TokenText;
+    return true;
+  }
+
+  bool parseNamedBindings(const AdditionalKeywords &Keywords,
+                          JsModuleReference &Reference) {
+    if (Current->isNot(tok::l_brace))
+      return false;
+
+    // {sym as alias, sym2 as ...} from '...';
+    nextToken();
+    while (true) {
+      if (Current->isNot(tok::identifier))
+        return false;
+
+      JsImportedSymbol Symbol;
+      Symbol.Symbol = Current->TokenText;
+      nextToken();
+
+      if (Current->is(Keywords.kw_as)) {
+        nextToken();
+        if (Current->isNot(tok::identifier))
+          return false;
+        Symbol.Alias = Current->TokenText;
+        nextToken();
+      }
+      Reference.Symbols.push_back(Symbol);
+
+      if (Current->is(tok::r_brace))
+        return true;
+      if (Current->isNot(tok::comma))
+        return false;
+      nextToken();
+    }
+  }
+};
+
+tooling::Replacements sortJavaScriptImports(const FormatStyle &Style,
+                                            StringRef Code,
+                                            ArrayRef<tooling::Range> Ranges,
+                                            StringRef FileName) {
+  // FIXME: Cursor support.
+  std::unique_ptr<Environment> Env =
+      Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
+  JavaScriptImportSorter Sorter(*Env, Style);
+  return Sorter.process();
+}
+
+} // end namespace format
+} // end namespace clang