Don’t hard-code escape sequences

Instead of hard-coding VT100-compatible escape sequences, parse the
system terminfo database and read escape sequences from it. This is
both more flexible (it should work well on more terminals) and more
efficient (it won’t insert padding on terminals that don’t need it).

5 files changed, 1114 insertions, 0 deletions

diff --git a/goldfishterm/internal/emit.cc b/goldfishterm/internal/emit.cc
new file mode 100644
index 0000000..2cc7609
--- /dev/null
+++ b/goldfishterm/internal/emit.cc
@@ -0,0 +1,47 @@
+// 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 "goldfishterm/internal/emit.h"
+
+#include <errno.h>
+#include <stdint.h>
+#include <unistd.h>
+
+#include <memory>
+#include <system_error>
+#include <vector>
+
+#include "third_party/abseil/absl/strings/string_view.h"
+#include "third_party/abseil/absl/time/clock.h"
+#include "third_party/abseil/absl/types/span.h"
+
+namespace goldfishterm_internal {
+
+void EmitBytes::Emit(std::ostream& out) const {
+  out.write(bytes_.data(), bytes_.size());
+}
+
+void EmitDelay::Emit(std::ostream& out) const noexcept {
+  out.flush();
+  absl::SleepFor(delay_);
+}
+
+void Emit(absl::Span<const std::shared_ptr<const EmitTerm>> terms,
+          std::ostream& out) {
+  for (const auto& term : terms) {
+    term->Emit(out);
+  }
+}
+
+}  // namespace goldfishterm_internal
diff --git a/goldfishterm/internal/emit.h b/goldfishterm/internal/emit.h
new file mode 100644
index 0000000..371f6b0
--- /dev/null
+++ b/goldfishterm/internal/emit.h
@@ -0,0 +1,106 @@
+// 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.
+
+// An extremely simple EDSL for describing output to the terminal. It supports
+// exactly two instructions: "send some bytes to the terminal" and "sleep". The
+// string capability interpreter produces terms in this EDSL, which makes it
+// easier to test.
+
+#ifndef EC_GOLDFISHTERM_INTERNAL_EMIT_H_
+#define EC_GOLDFISHTERM_INTERNAL_EMIT_H_
+
+#include <stdint.h>
+
+#include <memory>
+#include <ostream>
+#include <string>
+#include <utility>
+
+#include "third_party/abseil/absl/strings/str_cat.h"
+#include "third_party/abseil/absl/strings/string_view.h"
+#include "third_party/abseil/absl/time/time.h"
+#include "third_party/abseil/absl/types/span.h"
+
+namespace goldfishterm_internal {
+
+class EmitTerm {
+ public:
+  virtual void Emit(std::ostream&) const = 0;
+
+  virtual ~EmitTerm() noexcept = default;
+};
+
+class EmitBytes final : public EmitTerm {
+ public:
+  explicit EmitBytes() noexcept = default;
+
+  explicit EmitBytes(absl::string_view bytes) noexcept : bytes_(bytes) {}
+
+  EmitBytes(const EmitBytes&) = default;
+  EmitBytes& operator=(const EmitBytes&) = default;
+  EmitBytes(EmitBytes&&) noexcept = default;
+  EmitBytes& operator=(EmitBytes&&) noexcept = default;
+
+  bool empty() const noexcept { return bytes_.empty(); }
+
+  void Append(absl::string_view more) noexcept {
+    absl::StrAppend(&bytes_, more);
+  }
+
+  void Emit(std::ostream&) const override;
+
+  bool operator==(const EmitBytes& other) const noexcept {
+    return bytes_ == other.bytes_;
+  }
+
+  friend std::ostream& operator<<(std::ostream& out,
+                                  const EmitBytes& emit) noexcept {
+    return out << "EmitBytes(" << emit.bytes_ << ')';
+  }
+
+ private:
+  std::string bytes_;
+};
+
+class EmitDelay final : public EmitTerm {
+ public:
+  explicit EmitDelay() noexcept = default;
+
+  explicit EmitDelay(absl::Duration delay) : delay_(std::move(delay)) {}
+
+  EmitDelay(const EmitDelay&) = default;
+  EmitDelay& operator=(const EmitDelay&) = default;
+  EmitDelay(EmitDelay&&) noexcept = default;
+  EmitDelay& operator=(EmitDelay&&) noexcept = default;
+
+  bool zero() const noexcept { return delay_ == absl::ZeroDuration(); }
+
+  void Increase(absl::Duration more) noexcept { delay_ += more; }
+
+  void Emit(std::ostream&) const noexcept override;
+
+  bool operator==(const EmitDelay& other) const noexcept {
+    return delay_ == other.delay_;
+  }
+
+ private:
+  absl::Duration delay_;
+};
+
+// Runs an entire program in the emitter EDSL.
+void Emit(absl::Span<const std::shared_ptr<const EmitTerm>>, std::ostream&);
+
+}  // namespace goldfishterm_internal
+
+#endif  // EC_GOLDFISHTERM_INTERNAL_EMIT_H_
diff --git a/goldfishterm/internal/string_capability.h b/goldfishterm/internal/string_capability.h
new file mode 100644
index 0000000..ddae964
--- /dev/null
+++ b/goldfishterm/internal/string_capability.h
@@ -0,0 +1,106 @@
+// 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.
+
+// Parses and interprets terminfo string capabilities. These are written in a
+// simple stack-based programming language whose semantics are documented in
+// terminfo(5).
+
+#ifndef EC_GOLDFISHTERM_INTERNAL_STRING_CAPABILITY_H_
+#define EC_GOLDFISHTERM_INTERNAL_STRING_CAPABILITY_H_
+
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "goldfishterm/internal/emit.h"
+#include "goldfishterm/terminfo.h"
+#include "third_party/abseil/absl/types/optional.h"
+#include "third_party/abseil/absl/types/variant.h"
+
+namespace goldfishterm_internal {
+
+using StringCapabilityParameter = absl::variant<int, std::string>;
+
+struct InterpretStringCapabilityInput {
+  std::string capability;
+  std::vector<StringCapabilityParameter> parameters;
+
+  // The number of lines affected by this operation.
+  int lines_affected;
+
+  // The minimum baud rate at which padding should be expanded.
+  int padding_baud_rate;
+
+  // The padding character, or absl::nullopt if the terminal doesn't support
+  // padding.
+  absl::optional<char> pad_char;
+
+  // True iff the terminal supports XON/XOFF handshaking.
+  bool has_xon_xoff;
+
+  // The baud rate of the terminal.
+  int baud;
+
+  // The number of extra bits sent per character. For a terminal emulator, this
+  // is generally 0; for an RS-232 line, it's generally 2 or 3 (one start bit,
+  // one stop bit, and possibly one parity bit).
+  int extra_bits_per_character;
+
+  // Constructs an InterpretStringCapabilityInput with fail-safe defaults.
+  explicit InterpretStringCapabilityInput() noexcept
+      : lines_affected(1),
+        padding_baud_rate(0),
+        pad_char('\0'),
+        has_xon_xoff(false),
+        baud(9600),
+        extra_bits_per_character(0) {}
+
+  // Constructs an InterpretStringCapabilityInput from a terminfo entry.
+  explicit InterpretStringCapabilityInput(
+      const goldfishterm::TerminfoEntry& terminfo, std::string capability_,
+      std::vector<StringCapabilityParameter> parameters_, int baud_,
+      int lines_affected_) noexcept
+      : capability(std::move(capability_)),
+        parameters(std::move(parameters_)),
+        lines_affected(lines_affected_),
+        padding_baud_rate(
+            terminfo.get(goldfishterm::NumericCapability::kPaddingBaudRate)
+                .value_or(0)),
+        pad_char(terminfo.get(goldfishterm::StringCapability::kCharPadding)
+                     .value_or(std::string(1, '\0'))[0]),
+        has_xon_xoff(terminfo.get(goldfishterm::BooleanCapability::kXonXoff)),
+        baud(baud_),
+        extra_bits_per_character(0) {}
+};
+
+struct InterpretStringCapabilityResult {
+  // Terms in the emitter EDSL (see emit.h).
+  std::vector<std::shared_ptr<const EmitTerm>> terms;
+
+  // The expected cost of emitting these terms. This is a unitless, arbitrarily
+  // scaled real number; it will be at least 0, but you should not rely on any
+  // absolute semantics.
+  float cost;
+};
+
+// Interprets a terminfo string capability, expanding parameters and inserting
+// padding and delays as appropriate. Throws std::runtime_error if parsing or
+// interpretation fails.
+InterpretStringCapabilityResult InterpretStringCapability(
+    const InterpretStringCapabilityInput&);
+
+}  // namespace goldfishterm_internal
+
+#endif  // EC_GOLDFISHTERM_INTERNAL_STRING_CAPABILITY_H_
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
diff --git a/goldfishterm/internal/string_capability_test.cc b/goldfishterm/internal/string_capability_test.cc
new file mode 100644
index 0000000..a821551
--- /dev/null
+++ b/goldfishterm/internal/string_capability_test.cc
@@ -0,0 +1,372 @@
+// 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 "goldfishterm/internal/string_capability.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+#include <string.h>
+
+#include <ostream>
+#include <stdexcept>
+#include <string>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+#include "goldfishterm/internal/emit.h"
+#include "third_party/abseil/absl/strings/str_cat.h"
+#include "third_party/abseil/absl/strings/string_view.h"
+#include "third_party/abseil/absl/time/time.h"
+#include "third_party/abseil/absl/types/optional.h"
+
+namespace goldfishterm_internal {
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::IsEmpty;
+using ::testing::Pointee;
+using ::testing::Property;
+using ::testing::StrEq;
+using ::testing::WhenDynamicCastTo;
+
+MATCHER_P(PointsToEmitBytes, s,
+          absl::StrCat("points to EmitBytes('", s, "')")) {
+  const char* start;
+  int length;
+  if constexpr (std::is_same_v<decltype(s), const char* const>) {
+    start = s;
+    length = strlen(s);
+  } else {
+    start = s.data();
+    length = s.size();
+  }
+  return ExplainMatchResult(Pointee(WhenDynamicCastTo<const EmitBytes&>(
+                                EmitBytes(absl::string_view(start, length)))),
+                            arg, result_listener);
+}
+
+MATCHER_P(PointsToEmitDelay, t,
+          absl::StrCat("points to EmitDelay('", absl::FormatDuration(t),
+                       "')")) {
+  return ExplainMatchResult(
+      Pointee(WhenDynamicCastTo<const EmitDelay&>(EmitDelay(t))), arg,
+      result_listener);
+}
+
+InterpretStringCapabilityResult Interpret(
+    std::string text, std::vector<StringCapabilityParameter> parameters = {}) {
+  InterpretStringCapabilityInput input;
+  input.capability = std::move(text);
+  input.parameters = std::move(parameters);
+  return InterpretStringCapability(input);
+}
+
+TEST(InterpretStringCapabilityTest, PadInteger) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<40>";
+  input.baud = 8'000;  // 1 character every millisecond
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms,
+              ElementsAre(PointsToEmitBytes(std::string(40, '\0'))));
+  EXPECT_EQ(result.cost, 40);
+}
+
+TEST(InterpretStringCapabilityTest, PadFractional) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<.9>";
+  input.baud = 80'000;  // 10 characters every millisecond
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms,
+              ElementsAre(PointsToEmitBytes(std::string(9, '\0'))));
+  EXPECT_EQ(result.cost, 9);
+}
+
+TEST(InterpretStringCapabilityTest, PadIgnoredIfMultipleSignificantFigures) {
+  EXPECT_THAT(Interpret("$<1.1>").terms,
+              ElementsAre(PointsToEmitBytes("$<1.1>")));
+}
+
+TEST(InterpretStringCapabilityTest, PerLinePad) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<4*>";
+  input.lines_affected = 10;
+  input.baud = 8'000;
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms,
+              ElementsAre(PointsToEmitBytes(std::string(40, '\0'))));
+  EXPECT_EQ(result.cost, 40);
+}
+
+TEST(InterpretStringCapabilityTest, PadIgnoredIfTerminalTooSlow) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<40>";
+  input.padding_baud_rate = 115200;
+  input.baud = 9600;
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms, IsEmpty());
+  EXPECT_EQ(result.cost, 0);
+}
+
+TEST(InterpretStringCapabilityTest, PadWithWeirdCharacter) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<.1>";
+  input.pad_char = 'a';
+  input.baud = 9600;
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms, ElementsAre(PointsToEmitBytes("a")));
+  EXPECT_EQ(result.cost, 1);
+}
+
+TEST(InterpretStringCapabilityTest, SleepIfPadUnsupported) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<40>";
+  input.pad_char = absl::nullopt;
+  input.baud = 16'000;
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms,
+              ElementsAre(PointsToEmitDelay(absl::Milliseconds(40))));
+  EXPECT_EQ(result.cost, 80);  // the equivalent of 80 characters
+}
+
+TEST(InterpretStringCapabilityTest, PadWith8N1) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<40>";
+  input.baud = 10'000;                 // 1 character every millisecond using
+  input.extra_bits_per_character = 2;  // one start and one stop bit
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms,
+              ElementsAre(PointsToEmitBytes(std::string(40, '\0'))));
+  EXPECT_EQ(result.cost, 40);
+}
+
+TEST(InterpretStringCapabilityTest, PadIgnoredIfXonXoffAvailable) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<40>";
+  input.has_xon_xoff = true;
+  input.baud = 8'000;
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms, IsEmpty());
+  EXPECT_EQ(result.cost, 40);
+}
+
+TEST(InterpretStringCapabilityTest, MandatoryPadSentEvenIfXonXoffAvailable) {
+  InterpretStringCapabilityInput input;
+  input.capability = "$<40/>";
+  input.has_xon_xoff = true;
+  input.baud = 8'000;
+  InterpretStringCapabilityResult result = InterpretStringCapability(input);
+  EXPECT_THAT(result.terms,
+              ElementsAre(PointsToEmitBytes(std::string(40, '\0'))));
+  EXPECT_EQ(result.cost, 40);
+}
+
+TEST(InterpretStringCapabilityTest, Empty) {
+  InterpretStringCapabilityResult result = Interpret("");
+  EXPECT_THAT(result.terms, IsEmpty());
+  EXPECT_EQ(result.cost, 0);
+}
+
+TEST(InterpretStringCapabilityTest, EmitLiteralPercent) {
+  InterpretStringCapabilityResult result = Interpret("%%");
+  EXPECT_THAT(result.terms, ElementsAre(PointsToEmitBytes("%")));
+  EXPECT_EQ(result.cost, 1);
+}
+
+TEST(InterpretStringCapabilityTest, EmitChar) {
+  InterpretStringCapabilityResult result = Interpret("a");
+  EXPECT_THAT(result.terms, ElementsAre(PointsToEmitBytes("a")));
+  EXPECT_EQ(result.cost, 1);
+}
+
+TEST(InterpretStringCapabilityTest, EmitText) {
+  InterpretStringCapabilityResult result = Interpret("hi");
+  EXPECT_THAT(result.terms, ElementsAre(PointsToEmitBytes("hi")));
+  EXPECT_EQ(result.cost, 2);
+}
+
+TEST(InterpretStringCapabilityTest, EmitNonprinting) {
+  InterpretStringCapabilityResult result = Interpret("\r\n");
+  EXPECT_THAT(result.terms, ElementsAre(PointsToEmitBytes("\r\n")));
+  EXPECT_EQ(result.cost, 2);
+}
+
+TEST(InterpretStringCapabilityTest, PushParameter) {
+  EXPECT_THAT(Interpret("%p2%d", {42, 96}).terms,
+              ElementsAre(PointsToEmitBytes("96")));
+}
+
+TEST(InterpretStringCapabilityTest, PopNumber) {
+  EXPECT_THAT(Interpret("%p1%:-10.5o", {42}).terms,
+              ElementsAre(PointsToEmitBytes("00052     ")));
+}
+
+TEST(InterpretStringCapabilityTest, PopString) {
+  EXPECT_THAT(Interpret("%p1%:-10s", {"foo"}).terms,
+              ElementsAre(PointsToEmitBytes("foo       ")));
+}
+
+TEST(InterpretStringCapabilityTest, PopChar) {
+  EXPECT_THAT(Interpret("%p1%:-10c", {'x'}).terms,
+              ElementsAre(PointsToEmitBytes("x         ")));
+}
+
+TEST(InterpretStringCapabilityTest, StoreRecall) {
+  EXPECT_THAT(Interpret("%p1%Pa%p2%Pb%gb%s,%ga%d", {1, "foo"}).terms,
+              ElementsAre(PointsToEmitBytes("foo,1")));
+}
+
+TEST(InterpretStringCapabilityTest, PushChar) {
+  EXPECT_THAT(Interpret("%'x'%'y'%c%c").terms,
+              ElementsAre(PointsToEmitBytes("yx")));
+}
+
+TEST(InterpretStringCapabilityTest, PushNumber) {
+  EXPECT_THAT(Interpret("%{123}%d").terms,
+              ElementsAre(PointsToEmitBytes("123")));
+}
+
+TEST(InterpretStringCapabilityTest, Strlen) {
+  EXPECT_THAT(Interpret("%p1%l%d", {"foobar"}).terms,
+              ElementsAre(PointsToEmitBytes("6")));
+}
+
+TEST(InterpretStringCapabilityTest, Add) {
+  EXPECT_THAT(Interpret("%{5}%{2}%+%d").terms,
+              ElementsAre(PointsToEmitBytes("7")));
+}
+
+TEST(InterpretStringCapabilityTest, Subtract) {
+  EXPECT_THAT(Interpret("%{5}%{2}%-%d").terms,
+              ElementsAre(PointsToEmitBytes("3")));
+}
+
+TEST(InterpretStringCapabilityTest, Multiply) {
+  EXPECT_THAT(Interpret("%{5}%{2}%*%d").terms,
+              ElementsAre(PointsToEmitBytes("10")));
+}
+
+TEST(InterpretStringCapabilityTest, Divide) {
+  EXPECT_THAT(Interpret("%{5}%{2}%/%d").terms,
+              ElementsAre(PointsToEmitBytes("2")));
+}
+
+TEST(InterpretStringCapabilityTest, Modulo) {
+  EXPECT_THAT(Interpret("%{5}%{2}%m%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+}
+
+TEST(InterpretStringCapabilityTest, BitwiseAnd) {
+  EXPECT_THAT(Interpret("%{3}%{15}%&%d").terms,
+              ElementsAre(PointsToEmitBytes("3")));
+}
+
+TEST(InterpretStringCapabilityTest, BitwiseOr) {
+  EXPECT_THAT(Interpret("%{2}%{1}%|%d").terms,
+              ElementsAre(PointsToEmitBytes("3")));
+}
+
+TEST(InterpretStringCapabilityTest, BitwiseXor) {
+  EXPECT_THAT(Interpret("%{15}%{10}%^%d").terms,
+              ElementsAre(PointsToEmitBytes("5")));
+}
+
+TEST(InterpretStringCapabilityTest, Equals) {
+  EXPECT_THAT(Interpret("%{15}%{15}%=%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+  EXPECT_THAT(Interpret("%{15}%{14}%=%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+}
+
+TEST(InterpretStringCapabilityTest, LessThan) {
+  EXPECT_THAT(Interpret("%{2}%{3}%<%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+  EXPECT_THAT(Interpret("%{2}%{2}%<%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+}
+
+TEST(InterpretStringCapabilityTest, GreaterThan) {
+  EXPECT_THAT(Interpret("%{3}%{2}%>%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+  EXPECT_THAT(Interpret("%{2}%{2}%>%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+}
+
+TEST(InterpretStringCapabilityTest, LogicalAnd) {
+  EXPECT_THAT(Interpret("%{0}%{0}%A%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+  EXPECT_THAT(Interpret("%{0}%{1}%A%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+  EXPECT_THAT(Interpret("%{1}%{0}%A%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+  EXPECT_THAT(Interpret("%{1}%{1}%A%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+}
+
+TEST(InterpretStringCapabilityTest, LogicalOr) {
+  EXPECT_THAT(Interpret("%{0}%{0}%O%d").terms,
+              ElementsAre(PointsToEmitBytes("0")));
+  EXPECT_THAT(Interpret("%{0}%{1}%O%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+  EXPECT_THAT(Interpret("%{1}%{0}%O%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+  EXPECT_THAT(Interpret("%{1}%{1}%O%d").terms,
+              ElementsAre(PointsToEmitBytes("1")));
+}
+
+TEST(InterpretStringCapabilityTest, LogicalNot) {
+  EXPECT_THAT(Interpret("%{0}%!%d").terms, ElementsAre(PointsToEmitBytes("1")));
+  EXPECT_THAT(Interpret("%{5}%!%d").terms, ElementsAre(PointsToEmitBytes("0")));
+}
+
+TEST(InterpretStringCapabilityTest, BitwiseNot) {
+  EXPECT_THAT(Interpret("%{8}%~%d").terms,
+              ElementsAre(PointsToEmitBytes("-9")));
+}
+
+TEST(InterpretStringCapabilityTest, IncrementParameters) {
+  EXPECT_THAT(Interpret("%i%p1%d,%p2%d", {6, 8}).terms,
+              ElementsAre(PointsToEmitBytes("7,9")));
+}
+
+TEST(InterpretStringCapabilityTest, IfThen) {
+  EXPECT_THAT(Interpret("%?%{0}%ttrue%;").terms, IsEmpty());
+  EXPECT_THAT(Interpret("%?%{1}%ttrue%;").terms,
+              ElementsAre(PointsToEmitBytes("true")));
+}
+
+TEST(InterpretStringCapabilityTest, IfThenElse) {
+  EXPECT_THAT(Interpret("%?%{0}%ttrue%efalse%;").terms,
+              ElementsAre(PointsToEmitBytes("false")));
+  EXPECT_THAT(Interpret("%?%{1}%ttrue%efalse%;").terms,
+              ElementsAre(PointsToEmitBytes("true")));
+}
+
+TEST(InterpretStringCapabilityTest, IfThenElseThen) {
+  EXPECT_THAT(Interpret("%?%{0}%t!%e%{1}%tgood%;").terms,
+              ElementsAre(PointsToEmitBytes("good")));
+}
+
+TEST(InterpretStringCapabilityTest, IfThenElseThenElse) {
+  EXPECT_THAT(Interpret("%?%{0}%t!%e%{0}%t!%egood%;").terms,
+              ElementsAre(PointsToEmitBytes("good")));
+}
+
+TEST(InterpretStringCapabilityTest, IfThenElseThenElseShortCircuit) {
+  EXPECT_THAT(Interpret("%?%{1}%tgood%e%{0}%t!%e!%;").terms,
+              ElementsAre(PointsToEmitBytes("good")));
+}
+
+}  // namespace
+}  // namespace goldfishterm_internal