pseudo/include/clang-pseudo/Forest.h

//===--- Forest.h - Parse forest, the output of the GLR parser ---*- C++-*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// A parse forest represents a set of possible parse trees efficiently, it is
// produced by the GLR parser.
//
// Despite the name, its data structure is a tree-like DAG with a single root.
// Multiple ways to parse the same tokens are presented as an ambiguous node
// with all possible interpretations as children.
// Common sub-parses are shared: if two interpretations both parse "1 + 1" as
// "expr := expr + expr", they will share a Sequence node representing the expr.
//
//===----------------------------------------------------------------------===//

#ifndef CLANG_PSEUDO_FOREST_H
#define CLANG_PSEUDO_FOREST_H

#include "clang-pseudo/Token.h"
#include "clang-pseudo/grammar/Grammar.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Allocator.h"
#include <cstdint>

namespace clang {
namespace pseudo {

// A node represents ways to parse a sequence of tokens, it interprets a fixed
// range of tokens as a fixed grammar symbol.
//
// There are different kinds of nodes, some nodes have "children" (stored in a
// trailing array) and have pointers to them. "Children" has different semantics
// depending on the node kinds. For an Ambiguous node, it means all
// possible interpretations; for a Sequence node, it means each symbol on the
// right hand side of the production rule.
//
// Since this is a node in a DAG, a node may have multiple parents. And a node
// doesn't have parent pointers.
class alignas(class ForestNode *) ForestNode {
public:
  class RecursiveIterator;
  enum Kind {
    // A Terminal node is a single terminal symbol bound to a token.
    Terminal,
    // A Sequence node is a nonterminal symbol parsed from a grammar rule,
    // elements() are the parses of each symbol on the RHS of the rule.
    // If the rule is A := X Y Z, the node is for nonterminal A, and elements()
    // are [X, Y, Z].
    Sequence,
    // An Ambiguous node exposes multiple ways to interpret the code as the
    // same symbol, alternatives() are all possible parses.
    Ambiguous,
    // An Opaque node is a placeholder. It asserts that tokens match a symbol,
    // without saying how.
    // It is used for lazy-parsing (not parsed yet), or error-recovery (invalid
    // code).
    Opaque,
  };
  Kind kind() const { return K; }

  SymbolID symbol() const { return Symbol; }

  // The start of the token range, it is a poistion within a token stream.
  Token::Index startTokenIndex() const { return StartIndex; }

  // Returns the corresponding grammar rule.
  // REQUIRES: this is a Sequence node.
  RuleID rule() const {
    assert(kind() == Sequence);
    return Data & ((1 << RuleBits) - 1);
  }
  // Returns the parses of each element on the RHS of the rule.
  // REQUIRES: this is a Sequence node;
  llvm::ArrayRef<const ForestNode *> elements() const {
    assert(kind() == Sequence);
    return children(Data >> RuleBits);
  }
  llvm::MutableArrayRef<ForestNode *> elements() {
    assert(kind() == Sequence);
    return children(Data >> RuleBits);
  }

  // Returns all possible interpretations of the code.
  // REQUIRES: this is an Ambiguous node.
  llvm::ArrayRef<const ForestNode *> alternatives() const {
    assert(kind() == Ambiguous);
    return children(Data);
  }
  llvm::MutableArrayRef<ForestNode *> alternatives() {
    assert(kind() == Ambiguous);
    return children(Data);
  }

  llvm::ArrayRef<const ForestNode *> children() const {
    switch (kind()) {
    case Sequence:
      return elements();
    case Ambiguous:
      return alternatives();
    case Terminal:
    case Opaque:
      return {};
    }
    llvm_unreachable("Bad kind");
  }

  // Iteration over all nodes in the forest, including this.
  llvm::iterator_range<RecursiveIterator> descendants() const;

  std::string dump(const Grammar &) const;
  std::string dumpRecursive(const Grammar &, bool Abbreviated = false) const;

private:
  friend class ForestArena;

  ForestNode(Kind K, SymbolID Symbol, Token::Index StartIndex, uint16_t Data)
      : StartIndex(StartIndex), K(K), Symbol(Symbol), Data(Data) {}

  ForestNode(const ForestNode &) = delete;
  ForestNode &operator=(const ForestNode &) = delete;
  ForestNode(ForestNode &&) = delete;
  ForestNode &operator=(ForestNode &&) = delete;

  static uint16_t sequenceData(RuleID Rule,
                               llvm::ArrayRef<const ForestNode *> Elements) {
    assert(Rule < (1 << RuleBits));
    assert(Elements.size() < (1 << (16 - RuleBits)));
    return Rule | Elements.size() << RuleBits;
  }
  static uint16_t
  ambiguousData(llvm::ArrayRef<const ForestNode *> Alternatives) {
    return Alternatives.size();
  }

  // Retrieves the trailing array.
  llvm::ArrayRef<const ForestNode *> children(uint16_t Num) const {
    return llvm::ArrayRef(reinterpret_cast<ForestNode *const *>(this + 1), Num);
  }
  llvm::MutableArrayRef<ForestNode *> children(uint16_t Num) {
    return llvm::MutableArrayRef(reinterpret_cast<ForestNode **>(this + 1),
                                 Num);
  }

  Token::Index StartIndex;
  Kind K : 4;
  SymbolID Symbol : SymbolBits;
  // Sequence - child count : 4 | RuleID : RuleBits (12)
  // Ambiguous - child count : 16
  // Terminal, Opaque - unused
  uint16_t Data;
  // An array of ForestNode* following the object.
};
// ForestNode may not be destroyed (for BumpPtrAllocator).
static_assert(std::is_trivially_destructible<ForestNode>());

// A memory arena for the parse forest.
class ForestArena {
public:
  llvm::ArrayRef<ForestNode> createTerminals(const TokenStream &Code);
  ForestNode &createSequence(SymbolID SID, RuleID RID,
                             llvm::ArrayRef<const ForestNode *> Elements) {
    assert(!Elements.empty());
    return create(ForestNode::Sequence, SID,
                  Elements.front()->startTokenIndex(),
                  ForestNode::sequenceData(RID, Elements), Elements);
  }
  ForestNode &createAmbiguous(SymbolID SID,
                              llvm::ArrayRef<const ForestNode *> Alternatives) {
    assert(!Alternatives.empty());
    assert(llvm::all_of(Alternatives,
                        [SID](const ForestNode *Alternative) {
                          return SID == Alternative->symbol();
                        }) &&
           "Ambiguous alternatives must represent the same symbol!");
    return create(ForestNode::Ambiguous, SID,
                  Alternatives.front()->startTokenIndex(),
                  ForestNode::ambiguousData(Alternatives), Alternatives);
  }
  ForestNode &createOpaque(SymbolID SID, Token::Index Start) {
    return create(ForestNode::Opaque, SID, Start, 0, {});
  }

  ForestNode &createTerminal(tok::TokenKind TK, Token::Index Start) {
    return create(ForestNode::Terminal, tokenSymbol(TK), Start, 0, {});
  }

  size_t nodeCount() const { return NodeCount; }
  size_t bytes() const { return Arena.getBytesAllocated() + sizeof(*this); }

private:
  ForestNode &create(ForestNode::Kind K, SymbolID SID, Token::Index Start,
                     uint16_t Data,
                     llvm::ArrayRef<const ForestNode *> Elements) {
    ++NodeCount;
    ForestNode *New = new (Arena.Allocate(
        sizeof(ForestNode) + Elements.size() * sizeof(ForestNode *),
        alignof(ForestNode))) ForestNode(K, SID, Start, Data);
    if (!Elements.empty())
      llvm::copy(Elements, reinterpret_cast<const ForestNode **>(New + 1));
    return *New;
  }

  llvm::BumpPtrAllocator Arena;
  uint32_t NodeCount = 0;
};

class ForestNode::RecursiveIterator
    : public llvm::iterator_facade_base<ForestNode::RecursiveIterator,
                                        std::input_iterator_tag,
                                        const ForestNode> {
  llvm::DenseSet<const ForestNode *> Seen;
  struct StackFrame {
    const ForestNode *Parent;
    unsigned ChildIndex;
  };
  std::vector<StackFrame> Stack;
  const ForestNode *Cur;

public:
  RecursiveIterator(const ForestNode *N = nullptr) : Cur(N) {}

  const ForestNode &operator*() const { return *Cur; }
  void operator++();
  bool operator==(const RecursiveIterator &I) const { return Cur == I.Cur; }
  bool operator!=(const RecursiveIterator &I) const { return !(*this == I); }
};

} // namespace pseudo
} // namespace clang

#endif // CLANG_PSEUDO_FOREST_H