1 files changed, 483 insertions, 0 deletions
diff --git a/goldfishterm/internal/string_capability.re b/goldfishterm/internal/string_capability.re
new file mode 100644
index 0000000..6920066
--- /dev/null
+++ b/goldfishterm/internal/string_capability.re
@@ -0,0 +1,483 @@
+// 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