lib/Parse/SyntaxParsingCache.cpp

//===--- SyntaxParsingCache.cpp - Incremental syntax parsing lookup--------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "swift/Parse/SyntaxParsingCache.h"
#include "swift/Syntax/SyntaxVisitor.h"

using namespace swift;
using namespace swift::syntax;

void SyntaxParsingCache::addEdit(size_t Start, size_t End,
                                 size_t ReplacementLength) {
  assert((Edits.empty() || Edits.back().End <= Start) &&
         "'Start' must be greater than or equal to 'End' of the previous edit");
  Edits.emplace_back(Start, End, ReplacementLength);
}

bool SyntaxParsingCache::nodeCanBeReused(const Syntax &Node, size_t NodeStart,
                                         size_t Position,
                                         SyntaxKind Kind) const {
  // Computing the value of NodeStart on the fly is faster than determining a
  // node's absolute position, but make sure the values match in an assertion
  // build
  assert(NodeStart == Node.getAbsolutePositionBeforeLeadingTrivia().getOffset());

  if (NodeStart != Position)
    return false;
  if (Node.getKind() != Kind)
    return false;

  // Node can also not be reused if an edit has been made in the next token's
  // text, e.g. because `private struct Foo {}` parses as a CodeBlockItem with a
  // StructDecl inside and `private struc Foo {}` parses as two CodeBlockItems
  // one for `private` and one for `struc Foo {}`
  size_t NextLeafNodeLength = 0;
  if (auto NextNode = Node.getData().getNextNode()) {
    auto NextLeafNode = NextNode->getFirstToken();
    auto NextRawNode = NextLeafNode->getRaw();
    assert(NextRawNode->isPresent());
    NextLeafNodeLength += NextRawNode->getTokenText().size();
    for (auto TriviaPiece : NextRawNode->getLeadingTrivia()) {
      NextLeafNodeLength += TriviaPiece.getTextLength();
    }
  }

  auto NodeEnd = NodeStart + Node.getTextLength();
  for (auto Edit : Edits) {
    // Check if this node or the trivia of the next node has been edited. If it
    // has, we cannot reuse it.
    if (Edit.intersectsOrTouchesRange(NodeStart, NodeEnd + NextLeafNodeLength))
      return false;
  }

  return true;
}

llvm::Optional<Syntax> SyntaxParsingCache::lookUpFrom(const Syntax &Node,
                                                      size_t NodeStart,
                                                      size_t Position,
                                                      SyntaxKind Kind) {
  if (nodeCanBeReused(Node, NodeStart, Position, Kind)) {
    return Node;
  }

  // Compute the child's position on the fly
  size_t ChildStart = NodeStart;
  for (size_t I = 0, E = Node.getNumChildren(); I < E; ++I) {
    llvm::Optional<Syntax> Child = Node.getChild(I);
    if (!Child.hasValue() || Child->isMissing()) {
      continue;
    }
    auto ChildEnd = ChildStart + Child->getTextLength();
    if (ChildStart <= Position && Position < ChildEnd) {
      return lookUpFrom(Child.getValue(), ChildStart, Position, Kind);
    }
    // The next child starts where the previous child ended
    ChildStart = ChildEnd;
  }
  return llvm::None;
}

Optional<size_t>
SyntaxParsingCache::translateToPreEditPosition(size_t PostEditPosition,
                                               ArrayRef<SourceEdit> Edits) {
  size_t Position = PostEditPosition;
  for (auto &Edit : Edits) {
    if (Edit.Start > Position)
      // Remaining edits doesn't affect the position. (Edits are sorted)
      break;
    if (Edit.Start + Edit.ReplacementLength > Position)
      // This is a position inserted by the edit, and thus doesn't exist in the
      // pre-edit version of the file.
      return None;

    Position = Position - Edit.ReplacementLength + Edit.originalLength();
  }
  return Position;
}

llvm::Optional<Syntax> SyntaxParsingCache::lookUp(size_t NewPosition,
                                                  SyntaxKind Kind) {
  Optional<size_t> OldPosition = translateToPreEditPosition(NewPosition, Edits);
  if (!OldPosition.hasValue())
    return None;

  auto Node = lookUpFrom(OldSyntaxTree, /*NodeStart=*/0, *OldPosition, Kind);
  if (Node.hasValue()) {
    ReusedNodeIds.insert(Node->getId());
  }
  return Node;
}

std::vector<SyntaxReuseRegion>
SyntaxParsingCache::getReusedRegions(const SourceFileSyntax &SyntaxTree) const {
  /// Determines the reused source regions from reused syntax node IDs
  class ReusedRegionsCollector : public SyntaxVisitor {
    std::unordered_set<SyntaxNodeId> ReusedNodeIds;
    std::vector<SyntaxReuseRegion> ReusedRegions;

    bool didReuseNode(SyntaxNodeId NodeId) {
      return ReusedNodeIds.count(NodeId) > 0;
    }

  public:
    ReusedRegionsCollector(std::unordered_set<SyntaxNodeId> ReusedNodeIds)
        : ReusedNodeIds(ReusedNodeIds) {}

    const std::vector<SyntaxReuseRegion> &getReusedRegions() {
      std::sort(ReusedRegions.begin(), ReusedRegions.end(),
                [](const SyntaxReuseRegion &Lhs,
                   const SyntaxReuseRegion &Rhs) -> bool {
                  return Lhs.Start.getOffset() < Rhs.Start.getOffset();
                });
      return ReusedRegions;
    }

    void visit(Syntax Node) override {
      if (didReuseNode(Node.getId())) {
        // Node has been reused, add it to the list
        auto Start = Node.getAbsolutePositionBeforeLeadingTrivia();
        auto End = Node.getAbsoluteEndPositionAfterTrailingTrivia();
        ReusedRegions.push_back({Start, End});
      } else {
        SyntaxVisitor::visit(Node);
      }
    }

    void collectReusedRegions(SourceFileSyntax Node) {
      assert(ReusedRegions.empty() &&
             "ReusedRegionsCollector cannot be reused");
      Node.accept(*this);
    }
  };

  ReusedRegionsCollector ReuseRegionsCollector(getReusedNodeIds());
  ReuseRegionsCollector.collectReusedRegions(SyntaxTree);
  return ReuseRegionsCollector.getReusedRegions();
}