src/developer/shell/parser/parse_result.h

// Copyright 2020 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef SRC_DEVELOPER_SHELL_PARSER_PARSE_RESULT_H_
#define SRC_DEVELOPER_SHELL_PARSER_PARSE_RESULT_H_

#include <set>
#include <string_view>

#include "lib/fit/function.h"
#include "src/developer/shell/parser/ast.h"

namespace shell::parser {

// The result of parsing.
class ParseResult {
  // Frame in a stack of parsed nodes.
  struct Frame {
    std::shared_ptr<ast::Node> node;
    std::shared_ptr<Frame> prev;

    bool is_marker_frame() const { return !node; }
    bool is_stack_bottom() const { return !prev; }
  };

 public:
  ParseResult(const ParseResult&) = default;
  explicit ParseResult(std::string_view text) : ParseResult(text, 0, 0, 0, nullptr, nullptr) {}

  bool is_end() const { return frame_ == nullptr; }
  size_t offset() const { return offset_; }
  size_t errors() const { return errors_; }
  const std::shared_ptr<ParseResult>& error_alternative() const { return error_alternative_; }
  size_t parsed_successfully() const { return parsed_successfully_; }
  std::string_view unit() const { return unit_; }
  std::string_view tail() const { return unit_.substr(offset_); }
  std::shared_ptr<ast::Node> node() const { return frame_ ? frame_->node : nullptr; }

  // Move parsing ahead by len bytes, and push a token of that length.
  template <typename T = ast::Terminal>
  ParseResult Advance(size_t size) {
    if (is_end()) {
      return kEnd;
    }

    return ParseResult(unit_, offset_ + size, parsed_successfully_ + size, errors_,
                       std::make_shared<T>(offset_, size, tail().substr(0, size)), frame_);
  }

  // Set an error alternative on this parse result.
  ParseResult WithAlternative(ParseResult alternative) {
    ParseResult ret(*this);

    if (!ret.error_alternative_ ||
        ret.error_alternative_->parsed_successfully() < alternative.parsed_successfully()) {
      ret.error_alternative_ = std::make_shared<ParseResult>(std::move(alternative));
    }

    return ret;
  }

  // Rewrite the node in the current frame. Essentially this is a Pop(), then the result is passed
  // to the given closure, then the return value of the closure is Push()ed.
  //
  // See the parser-modifying version of Token() for example usage.
  ParseResult MapNode(fit::function<std::shared_ptr<ast::Node>(std::shared_ptr<ast::Node>)> f) {
    if (is_end()) {
      return kEnd;
    }

    auto ret = ParseResult(unit_, offset_, parsed_successfully_, errors_, f(node()), frame_->prev);

    if (error_alternative_) {
      ret.error_alternative_ =
          std::make_shared<ParseResult>(error_alternative_->MapNode(std::move(f)));
    }

    return ret;
  }

  // Insert an error indicating some form was expected. The parse position does not change.
  ParseResult Expected(std::string_view message) {
    if (is_end()) {
      return kEnd;
    }

    return ParseResult(unit_, offset_, parsed_successfully_, errors_ + 1,
                       std::make_unique<ast::Error>(offset_, 0, message), frame_);
  }

  // Skip the given number of bytes and push an error token indicating they were skipped.
  ParseResult Skip(size_t size, std::string_view message) {
    if (is_end()) {
      return kEnd;
    }

    return ParseResult(unit_, offset_ + size, parsed_successfully_, errors_ + 1,
                       std::make_unique<ast::Error>(offset_, size, message), frame_);
  }

  // Push a marker frame onto the stack. The next Reduce() call will reduce up to here.
  ParseResult Mark() {
    if (is_end()) {
      return kEnd;
    }

    auto ret = ParseResult(unit_, offset_, parsed_successfully_, errors_, nullptr, frame_);

    if (error_alternative_) {
      if (auto result = error_alternative_->Mark()) {
        ret.error_alternative_ = std::make_shared<ParseResult>(result);
      }
    }

    return ret;
  }

  // Pops from the stack until a marker frame or the top of the stack is encountered, then produces
  // a single nonterminal from the results and pushes that.
  //
  // This is how all nonterminals are created:
  // 1) A marker frame is pushed onto the stack.
  // 2) Assorted parsers are run, pushing the children of the node onto the stack as they go.
  // 3) Reduce() is called and turns the nodes between the marker and the stack top into a new
  //    nonterminal.
  //
  // If pop_marker is false, we will not remove the marker frame when we pop. This is useful for
  // building multiple non-terminals from the same reduction point, as the LAssoc combinator will.
  template <typename T>
  ParseResult Reduce(bool pop_marker = true);

  // Remove the marker frame nearest the top of the stack without disturbing the rest of the stack.
  // This is useful if we call reduce with pop_marker = false.
  ParseResult DropMarker() {
    if (auto frame = DropMarkerFrame()) {
      ParseResult ret(unit_, offset_, parsed_successfully_, errors_);
      ret.frame_ = frame;

      if (error_alternative_) {
        if (auto result = error_alternative_->DropMarker()) {
          ret.error_alternative_ = std::make_shared<ParseResult>(result);
        }
      }
      return ret;
    }

    return kEnd;
  }

  explicit operator bool() const { return !is_end(); }

  // A null parse result indicating no further error alternatives.
  static const ParseResult kEnd;

 private:
  ParseResult(std::string_view unit, size_t offset, size_t parsed_successfully, size_t errors)
      : offset_(offset),
        parsed_successfully_(parsed_successfully),
        errors_(errors),
        unit_(unit),
        frame_(nullptr) {}

  ParseResult(std::string_view unit, size_t offset, size_t parsed_successfully, size_t errors,
              std::shared_ptr<ast::Node> node, std::shared_ptr<Frame> prev)
      : ParseResult(unit, offset, parsed_successfully, errors) {
    frame_ = std::make_shared<Frame>(Frame{.node = std::move(node), .prev = std::move(prev)});
  }

  // Implement the core of DropMarker by actually walking the stack and deleting the marker frame.
  std::shared_ptr<Frame> DropMarkerFrame(std::shared_ptr<Frame> frame = nullptr) {
    if (!frame) {
      frame = frame_;
    }

    if (!frame) {
      return nullptr;
    } else if (frame->is_stack_bottom()) {
      return frame;
    } else if (frame->is_marker_frame()) {
      return frame->prev;
    } else {
      return std::make_shared<Frame>(
          Frame{.node = frame->node, .prev = DropMarkerFrame(frame->prev)});
    }
  }

  // Position from the beginning of the parsed text.
  size_t offset_;

  // How many characters we've advanced past, not including characters skipped due to error.
  size_t parsed_successfully_;

  // Number of errors we've encountered.
  size_t errors_;

  // Text being parsed.
  std::string_view unit_;

  // Last node that was parsed at this position.
  std::shared_ptr<Frame> frame_;

  // An alternative to this parse result for error processing.
  std::shared_ptr<ParseResult> error_alternative_;
};

template <typename T>
ParseResult ParseResult::Reduce(bool pop_marker) {
  std::vector<std::shared_ptr<ast::Node>> children;
  std::shared_ptr<Frame> cur;

  if (!frame_) {
    return kEnd;
  }

  // We have a dummy marker frame at the bottom of the stack, so we'll always hit the end conditon
  // here.
  for (cur = frame_; !cur->is_marker_frame(); cur = cur->prev) {
    if (!cur->node->IsWhitespace()) {
      children.push_back(cur->node);
    }
  }

  // If we didn't arrive at the beginning of the stack, also pop the marker (unless we were told not
  // to by the caller).
  if (pop_marker && !cur->is_stack_bottom()) {
    cur = cur->prev;
  }

  std::reverse(children.begin(), children.end());

  auto start = offset_;

  if (!children.empty()) {
    start = children.front()->start();
  }

  auto node = std::make_shared<T>(start, std::move(children));

  auto ret = ParseResult(unit_, offset_, parsed_successfully_, errors_, node, cur);

  if (error_alternative_) {
    if (auto result = error_alternative_->Reduce<T>(pop_marker)) {
      ret.error_alternative_ = std::make_shared<ParseResult>(result);
    }
  }

  return ret;
}

}  // namespace shell::parser

#endif  // SRC_DEVELOPER_SHELL_PARSER_PARSE_RESULT_H_