path: root/goldfishterm/internal/string_capability.re

// Copyright 2021 Benjamin Barenblat
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.

#include <math.h>

#include <functional>
#include <memory>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include "goldfishterm/internal/string_capability.h"
#include "third_party/abseil/absl/container/flat_hash_map.h"
#include "third_party/abseil/absl/strings/match.h"
#include "third_party/abseil/absl/strings/numbers.h"
#include "third_party/abseil/absl/strings/str_cat.h"
#include "third_party/abseil/absl/strings/str_format.h"
#include "third_party/abseil/absl/strings/string_view.h"
#include "third_party/abseil/absl/time/time.h"
#include "third_party/abseil/absl/types/variant.h"

namespace goldfishterm_internal {

namespace {

absl::string_view Slice(const char* start, const char* end) noexcept {
  return absl::string_view(start, end - start);
}

// The string capability interpreter, implemented as an re2c-generated DFA.
class Interpreter final {
 public:
  explicit Interpreter(InterpretStringCapabilityInput input) noexcept
      : input_(std::move(input)),
        chars_per_ms_(input_.baud / 1000.0 /
                      (8 * sizeof(char) + input_.extra_bits_per_character)) {
    result_.cost = 0;
  }

  void Run() {
    enum ConditionalEvaluationState {
      kNormal,
      kEvaluatingThen,
      kSkippingThen,
      kSkippingElse,
    } if_state = kNormal;

    const char* YYCURSOR = input_.capability.c_str();
    const char* YYMARKER;
    const char* a;
    const char* b;
    /*!stags:re2c format = "const char* @@;"; */

  loop:
    /*!re2c
      re2c:define:YYCTYPE = char;
      re2c:flags:tags = 1;
      re2c:yyfill:enable = 0;

      integer = [0-9]+;
      decimal = integer ("." integer)?;

      [\x00] { goto done; }

      "$<" @a ( "0"* [1-9] "0"* ("." "0"*)? | "0"* "." "0"* [1-9] "0"* ) @b "*"?
      "/"? ">" {
        if (if_state == kSkippingThen || if_state == kSkippingElse ||
            input_.baud < input_.padding_baud_rate) {
          goto loop;
        }

        float delay_ms;
        if (!absl::SimpleAtof(Slice(a, b), &delay_ms)) {
          throw std::logic_error(
              "goldfishterm: parser produced an invalid float");
        }
        bool per_line_pad = *b == '*';
        bool padding_mandatory = *(YYCURSOR - 2) == '/';
        if (per_line_pad) {
          delay_ms *= input_.lines_affected;
        }
        if (input_.has_xon_xoff && !padding_mandatory) {
          // Record that we expect a delay, but don't actually insert a delay.
          ExpectDelay(absl::Milliseconds(delay_ms));
        } else if (input_.pad_char.has_value()) {
          Bytes(std::string(ceilf(delay_ms * chars_per_ms_), *input_.pad_char));
        } else {
          Delay(absl::Milliseconds(delay_ms));
        }
        goto loop;
      }

      "%%" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        Bytes("%");
        goto loop;
      }

      "%" @a ((":"? [-+# ]+)? decimal? [doxX] | ":-"? integer? "c") {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        EmitPopped<int>(Slice(a, YYCURSOR));
        goto loop;
      }

      "%" @a ":-"? decimal? "s" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        EmitPopped<std::string>(Slice(a, YYCURSOR));
        goto loop;
      }

      "%p" [1-9] {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        int index = *(YYCURSOR - 1) - '0';
        try {
          stack_.push_back(input_.parameters.at(index - 1));
        } catch (const std::out_of_range& e) {
          throw std::runtime_error(
              absl::StrCat(absl::StrCat("invalid parameter ", index)));
        }
        goto loop;
      }

      "%P" [A-Za-z] {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        RequireNonempty();
        environment_[*(YYCURSOR - 1)] = std::move(stack_.back());
        stack_.pop_back();
        goto loop;
      }

      "%g" [A-Za-z] {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        char var = *(YYCURSOR - 1);
        auto it = environment_.find(var);
        if (it == environment_.end()) {
          throw std::runtime_error(absl::StrCat("undefined variable ",
                                   Slice(YYCURSOR - 1, YYCURSOR)));
        }
        stack_.push_back(it->second);
        goto loop;
      }

      "%'" [^\x00] "'" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        stack_.push_back(*(YYCURSOR - 2));
        goto loop;
      }

      "%{" @a integer "}" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        int value;
        if (!absl::SimpleAtoi(Slice(a, YYCURSOR - 1), &value)) {
          throw std::logic_error(
              "goldfishterm: parser produced an invalid int");
        }
        stack_.push_back(value);
        goto loop;
      }

      "%l" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        Unop<std::string, int>(
            [](const std::string& s) { return static_cast<int>(s.size()); });
        goto loop;
      }

      "%+" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::plus<int>());
        goto loop;
      }

      "%-" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::minus<int>());
        goto loop;
      }

      "%*" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::multiplies<int>());
        goto loop;
      }

      "%/" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::divides<int>());
        goto loop;
      }

      "%m" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::modulus<int>());
        goto loop;
      }

      "%&" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::bit_and<int>());
        goto loop;
      }

      "%|" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::bit_or<int>());
        goto loop;
      }

      "%^" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::bit_xor<int>());
        goto loop;
      }

      "%=" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::equal_to<int>());
        goto loop;
      }

      "%>" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::greater<int>());
        goto loop;
      }

      "%<" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::less<int>());
        goto loop;
      }

      "%A" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::logical_and<int>());
        goto loop;
      }

      "%O" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        BinopN(std::logical_or<int>());
        goto loop;
      }

      "%!" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        UnopN(std::logical_not<int>());
        goto loop;
      }

      "%~" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        UnopN(std::bit_not<int>());
        goto loop;
      }

      "%i" {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        if (input_.parameters.size() < 2) {
          throw std::runtime_error("%i requires at least two parameters");
        }
        auto* one = absl::get_if<int>(&input_.parameters[0]);
        auto* two = absl::get_if<int>(&input_.parameters[1]);
        RequireType<int>(one);
        RequireType<int>(two);
        ++*one;
        ++*two;
        goto loop;
      }

      "%?" {
        if (if_state != kNormal) {
          throw std::logic_error("goldfishterm: unexpected %?");
        }
        goto loop;
      }
      "%t" {
        if (if_state == kNormal) {
          RequireNonempty();
          int* condition_int = absl::get_if<int>(&stack_.back());
          // Strings are true, as are nonzero integers.
          bool condition = condition_int == nullptr || *condition_int;
          stack_.pop_back();
          if_state = condition ? kEvaluatingThen : kSkippingThen;
        } else if (if_state != kSkippingElse) {
          throw std::logic_error("goldfishterm: unexpected %t");
        }
        goto loop;
      }
      "%e" {
        switch (if_state) {
          case kNormal:
            throw std::logic_error("goldfishterm: unexpected %e");
            break;
          case kEvaluatingThen:
            if_state = kSkippingElse;
            break;
          case kSkippingThen:
            if_state = kNormal;
            break;
          case kSkippingElse:
            break;
        }
        goto loop;
      }
      "%;" {
        if_state = kNormal;
        goto loop;
      }

      * {
        if (if_state == kSkippingThen || if_state == kSkippingElse) goto loop;

        Bytes(Slice(YYCURSOR - 1, YYCURSOR));
        goto loop;
      }
     */

  done:
    Flush();
  }

  const InterpretStringCapabilityResult& result() noexcept { return result_; }

 private:
  void RequireNonempty() {
    if (stack_.empty()) {
      throw std::runtime_error("stack underflow");
    }
  }

  // A companion to absl::get_if: Requires that the passed pointer is nonnull
  // and throws an appropriate error if it's not.
  template <typename T>
  void RequireType(const void* v) {
    if (v == nullptr) {
      if constexpr (std::is_same_v<T, const int>) {
        throw std::runtime_error("type error: expected integer");
      } else if constexpr (std::is_same_v<T, const std::string>) {
        throw std::runtime_error("type error: expected string");
      } else {
        throw std::runtime_error("type error");
      }
    }
  }

  // Executes push(f(pop())).
  template <typename T, typename R>
  void Unop(std::function<R(T)> f) {
    RequireNonempty();
    T* v = absl::get_if<T>(&stack_.back());
    RequireType<int>(v);
    stack_.back() = f(*v);
  }

  // Executes x = pop(); push(f(pop(), x)).
  template <typename T1, typename T2, typename R>
  void Binop(std::function<R(T1, T2)> f) {
    if (stack_.size() < 2) {
      throw std::runtime_error("stack underflow during binary operation");
    }
    int target = stack_.size() - 2;
    T1* one = absl::get_if<T1>(&stack_[target]);
    T2* two = absl::get_if<T2>(&stack_.back());
    RequireType<T1>(one);
    RequireType<T2>(two);
    stack_[target] = f(*one, *two);
    stack_.pop_back();
  }

  // Convenience specializations for Unop and Binop over integers.
  void UnopN(std::function<int(int)> f) { Unop<int, int>(f); }
  void BinopN(std::function<int(int, int)> f) { Binop<int, int, int>(f); }

  template <typename T>
  void EmitPopped(absl::string_view format) {
    if (format[0] == ':') {
      // The colon is used by to disambiguate parsing. It isn't interesting to
      // absl::FormatUntyped.
      format = format.substr(1);
    }

    std::string out;
    auto* param = absl::get_if<T>(&stack_.back());
    RequireType<T>(param);
    if (!absl::FormatUntyped(&out,
                             absl::UntypedFormatSpec(absl::StrCat("%", format)),
                             {absl::FormatArg(*param)})) {
      throw std::logic_error(
          absl::StrCat("absl::FormatUntyped failed with format ", format));
    }
    Bytes(out);
    stack_.pop_back();
  }

  void ExpectDelay(absl::Duration delay) noexcept {
    result_.cost += absl::ToDoubleMilliseconds(delay) * chars_per_ms_;
  }

  void Delay(absl::Duration delay) noexcept {
    if (!pending_bytes_.empty()) {
      Flush();
    }
    pending_delay_.Increase(delay);
    ExpectDelay(delay);
  }

  void Bytes(absl::string_view bytes) noexcept {
    pending_bytes_.Append(bytes);
    result_.cost += bytes.size();
  }

  void Flush() noexcept {
    if (!pending_delay_.zero()) {
      result_.terms.push_back(
          std::make_shared<EmitDelay>(std::move(pending_delay_)));
    };
    if (!pending_bytes_.empty()) {
      result_.terms.push_back(
          std::make_shared<EmitBytes>(std::move(pending_bytes_)));
    };
  }

  InterpretStringCapabilityInput input_;
  double chars_per_ms_;

  std::vector<StringCapabilityParameter> stack_;
  absl::flat_hash_map<char, StringCapabilityParameter> environment_;

  EmitDelay pending_delay_;
  EmitBytes pending_bytes_;

  InterpretStringCapabilityResult result_;
};

}  // namespace

InterpretStringCapabilityResult InterpretStringCapability(
    const InterpretStringCapabilityInput& input) {
  Interpreter interp(input);
  interp.Run();
  return interp.result();
}

}  // namespace goldfishterm_internal