Skip to content

armgit / laya

Public Imported from GitHub
0

Non-autoregressive System 1 decision engine. Typed choice, score and yes/no decisions over any text in a single forward pass, in 100+ languages, with a router that picks the right checkpoint per request.

71.7 KB
Raw Blame
// Port of laya-go/tokenizer. Internal failures are a private exception caught at the API boundary
// (Parse and the *Spec helpers); no exception crosses the public API.
#include "laya/tokenizer.hpp"

#include <algorithm>
#include <array>
#include <cstdio>
#include <fstream>
#include <functional>
#include <memory>
#include <queue>
#include <sstream>
#include <unordered_map>
#include <unordered_set>

#include "laya/pyvalue.hpp"
#include "laya/unicodedata.hpp"

namespace laya {
namespace tokenizer {

const char* const kUnsupported = "unsupported tokenizer component: ";
bool IsUnsupported(const std::string& e) { return e.rfind(kUnsupported, 0) == 0; }

namespace {
#include "tokenizer_tables.inc"

using pyvalue::Value;
namespace ud = unicodedata;

struct Fail {
  std::string msg;
};
[[noreturn]] void Refuse(const std::string& m) { throw Fail{m}; }
[[noreturn]] void Unsupported(const std::string& m) { throw Fail{std::string(kUnsupported) + m}; }

template <class T, size_t N>
constexpr size_t Len(const T (&)[N]) {
  return N;
}

// ------------------------------------------------------------------------------------------
// Character classes: the reference's, from the generated tables.
// ------------------------------------------------------------------------------------------
bool IsWhiteSpace(char32_t r) {
  switch (r) {
    case '\t': case '\n': case 0x0B: case '\f': case '\r': case ' ': case 0x85: case 0xA0:
    case 0x1680: case 0x2028: case 0x2029: case 0x202F: case 0x205F: case 0x3000:
      return true;
  }
  return r >= 0x2000 && r <= 0x200A;
}

template <size_t N>
bool InRanges(const uint32_t (&pairs)[N], char32_t r) {
  long lo = 0, hi = long(N / 2) - 1;
  while (lo <= hi) {
    long mid = (lo + hi) / 2;
    if (r < pairs[mid * 2]) hi = mid - 1;
    else if (r > pairs[mid * 2 + 1]) lo = mid + 1;
    else return true;
  }
  return false;
}
bool IsLetter(char32_t r) {
  if (r < 0x80) return 'a' <= (r | 0x20) && (r | 0x20) <= 'z';
  return InRanges(k_letter, r);
}
bool IsNumber(char32_t r) {
  if (r < 0x80) return '0' <= r && r <= '9';
  return InRanges(k_number, r);
}
bool IsWordChar(char32_t r) { return InRanges(k_word_char, r); }

// ------------------------------------------------------------------------------------------
// Lowercase (per character, no final sigma) and normalization (UAX #15) from the crate's tables.
// ------------------------------------------------------------------------------------------
void LowerOf(char32_t r, std::string& out) {
  if (r < 0x80) {
    out.push_back(char((r >= 'A' && r <= 'Z') ? r + 32 : r));
    return;
  }
  for (const auto& m : k_lower_multi) {
    if (m.from == r) {
      for (uint32_t i = 0; i < m.count; i++) ud::AppendRune(out, m.to[i]);
      return;
    }
  }
  const uint32_t* end = k_lower_from + Len(k_lower_from);
  const uint32_t* at = std::lower_bound(k_lower_from, end, uint32_t(r));
  if (at != end && *at == r) {
    ud::AppendRune(out, k_lower_to[at - k_lower_from]);
    return;
  }
  ud::AppendRune(out, r);
}

std::vector<char32_t> Runes(std::string_view s) {
  std::vector<char32_t> out;
  out.reserve(s.size());
  while (!s.empty()) {
    auto d = ud::DecodeRune(s);
    out.push_back(d.rune);
    s.remove_prefix(d.width);
  }
  return out;
}
std::string FromRunes(const std::vector<char32_t>& rs) {
  std::string out;
  out.reserve(rs.size());
  for (char32_t r : rs) ud::AppendRune(out, r);
  return out;
}

constexpr char32_t kSBase = 0xAC00, kLBase = 0x1100, kVBase = 0x1161, kTBase = 0x11A7;
constexpr char32_t kLCount = 19, kVCount = 21, kTCount = 28, kNCount = kVCount * kTCount,
                   kSCount = kLCount * kNCount;

bool LookupPool(const uint32_t* keys, size_t nkeys, const uint32_t* offsets, const uint32_t* pool,
                char32_t r, const uint32_t** begin, const uint32_t** end) {
  const uint32_t* at = std::lower_bound(keys, keys + nkeys, uint32_t(r));
  if (at == keys + nkeys || *at != r) return false;
  size_t i = size_t(at - keys);
  *begin = pool + offsets[i];
  *end = pool + offsets[i + 1];
  return true;
}

void Decompose(std::vector<char32_t>& dst, char32_t r, bool compat) {
  if (r < 0xA0 || (r < 0xC0 && !compat)) {
    dst.push_back(r);
    return;
  }
  if (r >= kSBase && r < kSBase + kSCount) {
    char32_t s = r - kSBase;
    dst.push_back(kLBase + s / kNCount);
    dst.push_back(kVBase + (s % kNCount) / kTCount);
    if (s % kTCount != 0) dst.push_back(kTBase + s % kTCount);
    return;
  }
  const uint32_t *b, *e;
  if (compat && LookupPool(k_compat_keys, Len(k_compat_keys), k_compat_offsets, k_compat_pool, r, &b, &e)) {
    dst.insert(dst.end(), b, e);
    return;
  }
  if (LookupPool(k_canon_keys, Len(k_canon_keys), k_canon_offsets, k_canon_pool, r, &b, &e)) {
    dst.insert(dst.end(), b, e);
    return;
  }
  dst.push_back(r);
}

uint8_t CombiningClass(char32_t r) {
  if (r < 0x300) return 0;
  size_t n = Len(k_ccc_ranges) / 3, lo = 0, hi = n;
  while (lo < hi) {  // first triple whose hi >= r
    size_t mid = (lo + hi) / 2;
    if (k_ccc_ranges[mid * 3 + 1] >= r) hi = mid;
    else lo = mid + 1;
  }
  if (lo < n && k_ccc_ranges[lo * 3] <= r) return uint8_t(k_ccc_ranges[lo * 3 + 2]);
  return 0;
}

void Reorder(std::vector<char32_t>& rs) {
  for (size_t i = 0; i < rs.size();) {
    if (CombiningClass(rs[i]) == 0) {
      i++;
      continue;
    }
    size_t j = i;
    while (j < rs.size() && CombiningClass(rs[j]) != 0) j++;
    std::stable_sort(rs.begin() + long(i), rs.begin() + long(j),
                     [](char32_t a, char32_t b) { return CombiningClass(a) < CombiningClass(b); });
    i = j;
  }
}

bool ComposePair(char32_t first, char32_t second, char32_t* out) {
  if (first >= kLBase && first < kLBase + kLCount && second >= kVBase && second < kVBase + kVCount) {
    *out = kSBase + ((first - kLBase) * kVCount + (second - kVBase)) * kTCount;
    return true;
  }
  if (first >= kSBase && first < kSBase + kSCount && (first - kSBase) % kTCount == 0 &&
      second > kTBase && second < kTBase + kTCount) {
    *out = first + (second - kTBase);
    return true;
  }
  uint64_t key = (uint64_t(first) << 32) | second;
  const uint64_t* end = k_compose_keys + Len(k_compose_keys);
  const uint64_t* at = std::lower_bound(k_compose_keys, end, key);
  if (at != end && *at == key) {
    *out = k_compose_values[at - k_compose_keys];
    return true;
  }
  return false;
}

void ComposeRunes(std::vector<char32_t>& rs) {
  std::vector<char32_t> out;
  out.reserve(rs.size());
  long starter = -1;
  uint8_t last = 0;
  for (char32_t r : rs) {
    uint8_t cc = CombiningClass(r);
    char32_t c;
    if (starter >= 0 && (last < cc || last == 0) && ComposePair(out[size_t(starter)], r, &c)) {
      out[size_t(starter)] = c;
      continue;
    }
    if (cc == 0) {
      starter = long(out.size());
      last = 0;
    } else {
      last = cc;
    }
    out.push_back(r);
  }
  rs.swap(out);
}

std::string NormalizeImpl(std::string_view s, Form f) {
  bool compat = f == Form::NFKC || f == Form::NFKD, compose = f == Form::NFC || f == Form::NFKC;
  bool ascii = true, below = true;
  for (char32_t r : Runes(s)) {
    if (r >= 0x80) ascii = false;
    if (r >= 0x300) {
      below = false;
      break;
    }
  }
  // ASCII has no decomposition in any form, and nothing below U+0300 combines with what precedes.
  if (ascii || (below && compose && !compat)) return std::string(s);
  std::vector<char32_t> rs;
  for (char32_t r : Runes(s)) Decompose(rs, r, compat);
  Reorder(rs);
  if (compose) ComposeRunes(rs);
  return FromRunes(rs);
}

std::string LowercaseImpl(std::string_view s) {
  std::string out;
  out.reserve(s.size());
  while (!s.empty()) {
    auto d = ud::DecodeRune(s);
    LowerOf(d.rune, out);
    s.remove_prefix(d.width);
  }
  return out;
}

std::string StripImpl(std::string_view s, bool left, bool right) {
  size_t a = 0, b = s.size();
  if (left) {
    while (a < b) {
      auto d = ud::DecodeRune(s.substr(a, b - a));
      if (!IsWhiteSpace(d.rune)) break;
      a += d.width;
    }
  }
  if (right) {
    while (b > a) {
      auto d = ud::DecodeLastRune(s.substr(a, b - a));
      if (!IsWhiteSpace(d.rune)) break;
      b -= d.width;
    }
  }
  return std::string(s.substr(a, b - a));
}

// ------------------------------------------------------------------------------------------
// A small regex for the Replace normalizer. The reference reads \s \d \w \b \p as Unicode, and a
// stand-in regex engine would read them its own way, so those are refused (as laya-go does); what
// is left is literals, classes of explicit ranges, ., ^, $, groups, | and the greedy and lazy
// repeats. Matching is a backtracker that remembers failed (pc, position) pairs, so it is linear.
// ------------------------------------------------------------------------------------------
class Regex {
 public:
  explicit Regex(const std::string& pattern) { Compile(pattern); }

  // Replaces every non-overlapping match with the literal content.
  std::string ReplaceAll(const std::string& text, const std::string& content) const {
    std::string out;
    size_t copied = 0, from = 0;
    Memo memo(prog_.size(), text.size() + 1);
    while (from <= text.size()) {
      size_t ms, me;
      if (!Find(text, from, &ms, &me, memo)) break;
      out.append(text, copied, ms - copied);
      out += content;
      copied = me;
      from = me;  // matches are never empty: Compile refuses a pattern that can match nothing
    }
    out.append(text, copied, std::string::npos);
    return out;
  }
  bool MatchesEmpty() const {
    size_t s, e;
    Memo memo(prog_.size(), 1);
    return Find("", 0, &s, &e, memo);
  }

 private:
  enum Op { kChar, kAny, kSet, kSplit, kJmp, kBol, kEol, kMatch };
  struct Inst {
    Op op;
    char32_t c = 0;
    int x = 0, y = 0;
  };
  struct Set {
    std::vector<std::pair<char32_t, char32_t>> ranges;
    bool negate = false;
  };
  std::vector<Inst> prog_;
  std::vector<Set> sets_;

  static constexpr size_t kMaxProgram = 100000;  // instructions after repeats are expanded
  static constexpr int kMaxDepth = 256;          // nested groups
  static constexpr size_t kDenseBits = size_t(1) << 28;
  int depth_ = 0;

  // The (instruction, position) states already tried. Dense while the table is small, a hash set above
  // that. One table serves a whole ReplaceAll: a state that failed still fails for any later start, and
  // the states of a match lie at or before its end, which no later (non-empty) match revisits.
  class Memo {
   public:
    Memo(size_t insts, size_t positions) : insts_(insts), dense_(insts * positions <= kDenseBits) {
      if (dense_) bits_.assign((insts * positions + 63) / 64, 0);
    }
    bool Visit(int pc, size_t pos) {  // true the first time
      size_t key = pos * insts_ + size_t(pc);
      if (!dense_) return sparse_.insert(key).second;
      uint64_t& w = bits_[key / 64];
      uint64_t bit = uint64_t(1) << (key % 64);
      if (w & bit) return false;
      w |= bit;
      return true;
    }

   private:
    size_t insts_;
    bool dense_;
    std::vector<uint64_t> bits_;
    std::unordered_set<size_t> sparse_;
  };

  // --- parser: pattern -> instructions, emitted directly from a recursive descent -------------
  std::vector<char32_t> p_;
  size_t at_ = 0;
  bool icase_ = false;

  bool More() const { return at_ < p_.size(); }
  char32_t Peek() const { return p_[at_]; }
  int Emit(Op op, char32_t c = 0, int x = 0, int y = 0) {
    if (prog_.size() >= kMaxProgram) Refuse("a Replace regex that compiles to more than 100000 instructions");
    prog_.push_back(Inst{op, c, x, y});
    return int(prog_.size()) - 1;
  }

  void Compile(const std::string& pattern) {
    p_ = Runes(pattern);
    if (p_.size() >= 4 && p_[0] == '(' && p_[1] == '?' && p_[2] == 'i' && p_[3] == ')') {
      for (char32_t r : p_) {
        if (r >= 0x80) Unsupported("a case-insensitive Replace regex with a non-ASCII character is not implemented");
      }
      icase_ = true;
      at_ = 4;
    }
    Alternation();
    if (More()) Refuse("a Replace normalizer's regex: unexpected " + std::string(1, char(Peek())));
    Emit(kMatch);
    if (MatchesEmpty()) {
      Unsupported("this Replace regex can match the empty string, whose replacement rules differ between engines");
    }
  }

  // Each branch starts with a placeholder split (a plain jump for the last one), so no instruction is
  // ever inserted and every target stays valid.
  void Alternation() {
    std::vector<int> jumps;
    while (true) {
      int split = Emit(kSplit);
      Concatenation();
      if (More() && Peek() == '|') {
        at_++;
        jumps.push_back(Emit(kJmp));  // the finished branch jumps over the rest
        prog_[size_t(split)].x = split + 1;
        prog_[size_t(split)].y = int(prog_.size());
        continue;
      }
      prog_[size_t(split)] = Inst{kJmp, 0, split + 1, 0};
      break;
    }
    for (int j : jumps) prog_[size_t(j)].x = int(prog_.size());
  }

  void Concatenation() {
    while (More() && Peek() != '|' && Peek() != ')') Repeat();
  }

  void Repeat() {
    int start = int(prog_.size());
    Atom();
    int end = int(prog_.size());
    while (More()) {
      char32_t c = Peek();
      int lo, hi;  // hi < 0: unbounded
      if (c == '*') { lo = 0; hi = -1; at_++; }
      else if (c == '+') { lo = 1; hi = -1; at_++; }
      else if (c == '?') { lo = 0; hi = 1; at_++; }
      else if (c == '{') {
        size_t save = at_;
        if (!Counts(&lo, &hi)) { at_ = save; break; }
      } else break;
      bool lazy = More() && Peek() == '?';
      if (lazy) at_++;
      // Oniguruma (the crate's engine) ends a repeat whose body matched nothing; a backtracker
      // that remembers failed states would end it differently, so such a repeat is refused.
      if (!(lo == 0 && hi == 1) && Nullable(start, end)) {
        Unsupported("a Replace regex repeats a group that can match the empty string, whose repeat semantics differ between engines");
      }
      std::vector<Inst> body(prog_.begin() + start, prog_.begin() + end);
      for (Inst& in : body) {
        if (in.op == kSplit || in.op == kJmp) {
          in.x -= start;
          if (in.op == kSplit) in.y -= start;
        }
      }
      prog_.resize(size_t(start));
      if (lo > 1000 || hi > 1000) Refuse("a Replace regex repeat count above 1000");
      auto copy = [&]() {
        if (prog_.size() + body.size() > kMaxProgram) Refuse("a Replace regex that compiles to more than 100000 instructions");
        int base = int(prog_.size());
        for (Inst in : body) {
          if (in.op == kSplit || in.op == kJmp) {
            in.x += base;
            if (in.op == kSplit) in.y += base;
          }
          prog_.push_back(in);
        }
      };
      for (int i = 0; i < lo; i++) copy();
      if (hi < 0) {  // L: split(body, out); body; jmp L
        int l = int(prog_.size());
        int s = Emit(kSplit);
        copy();
        Emit(kJmp, 0, l);
        int out = int(prog_.size());
        prog_[size_t(s)].x = lazy ? out : s + 1;
        prog_[size_t(s)].y = lazy ? s + 1 : out;
      } else {
        std::vector<int> splits;
        for (int i = lo; i < hi; i++) {
          splits.push_back(Emit(kSplit));
          copy();
        }
        int out = int(prog_.size());
        for (int s : splits) {
          prog_[size_t(s)].x = lazy ? out : s + 1;
          prog_[size_t(s)].y = lazy ? s + 1 : out;
        }
      }
      end = int(prog_.size());
    }
  }

  // Can the instructions [start, end) reach `end` without consuming a character (anchors pass)?
  bool Nullable(int start, int end) const {
    std::vector<char> seen(size_t(end - start) + 1, 0);
    std::vector<int> todo{start};
    while (!todo.empty()) {
      int pc = todo.back();
      todo.pop_back();
      if (pc == end) return true;
      if (pc < start || pc > end || seen[size_t(pc - start)]) continue;
      seen[size_t(pc - start)] = 1;
      const Inst& in = prog_[size_t(pc)];
      if (in.op == kJmp) todo.push_back(in.x);
      else if (in.op == kSplit) { todo.push_back(in.x); todo.push_back(in.y); }
      else if (in.op == kBol || in.op == kEol) todo.push_back(pc + 1);
    }
    return false;
  }

  bool Counts(int* lo, int* hi) {  // at '{'; false when it is not a repeat count (then a literal)
    at_++;
    auto number = [&](int* v) {
      if (!More() || Peek() < '0' || Peek() > '9') return false;
      long n = 0;
      while (More() && Peek() >= '0' && Peek() <= '9') {
        n = n * 10 + long(Peek() - '0');
        if (n > 100000) n = 100000;
        at_++;
      }
      *v = int(n);
      return true;
    };
    if (!number(lo)) return false;
    *hi = *lo;
    if (More() && Peek() == ',') {
      at_++;
      if (More() && Peek() == '}') *hi = -1;
      else if (!number(hi)) return false;
    }
    if (!More() || Peek() != '}') return false;
    at_++;
    if (*hi >= 0 && *hi < *lo) Refuse("a Replace regex repeat count with its bounds reversed");
    return true;
  }

  void Atom() {
    char32_t c = Peek();
    if (c == '(') {
      at_++;
      if (More() && Peek() == '?') {
        if (at_ + 1 < p_.size() && p_[at_ + 1] == ':') at_ += 2;
        else Unsupported("this Replace regex group syntax (?...) is not implemented");
      }
      if (++depth_ > kMaxDepth) Refuse("a Replace regex nested more than 256 groups deep");
      Alternation();
      depth_--;
      if (!More() || Peek() != ')') Refuse("a Replace normalizer's regex: missing )");
      at_++;
    } else if (c == '[') {
      Class();
    } else if (c == '.') {
      at_++;
      Emit(kAny);
    } else if (c == '^') {
      at_++;
      Emit(kBol);
    } else if (c == '$') {
      at_++;
      Emit(kEol);
    } else if (c == '*' || c == '+' || c == '?') {
      Refuse("a Replace normalizer's regex: nothing to repeat");
    } else if (c == '\\') {
      Literal(Escape());
    } else {
      at_++;
      Literal(c);
    }
  }

  char32_t Escape() {  // at '\\'
    at_++;
    if (!More()) Refuse("a Replace normalizer's regex ends in a backslash");
    char32_t c = Peek();
    at_++;
    switch (c) {
      case 't': return '\t';
      case 'n': return '\n';
      case 'r': return '\r';
      case 'f': return '\f';
      case 'v': return 0x0B;
      default: break;
    }
    if (c < 0x80 && !((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))) return c;
    Unsupported("the Replace regex escape \\" + std::string(1, char(c < 0x80 ? c : '?')) + " is not implemented");
  }

  // Oniguruma folds with full Unicode rules: K (Kelvin) is k, the long s and the sharp s are s/ss, and
  // the ligatures ff, fi, fl, ffi, ffl, st fold to letter pairs. An ASCII-only fold would differ.
  void FoldTrap(char32_t lo, char32_t hi) const {
    if (!icase_) return;
    for (char32_t t : {U'k', U'K', U's', U'S', U'f', U'F'}) {
      if (lo <= t && t <= hi) Unsupported("a case-insensitive Replace regex with k, s or f, whose Unicode case folding is not implemented");
    }
  }

  void Literal(char32_t c) {
    FoldTrap(c, c);
    if (icase_ && ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) {
      Set s;
      s.ranges = {{c | 0x20, c | 0x20}, {c & ~char32_t(0x20), c & ~char32_t(0x20)}};
      sets_.push_back(s);
      Emit(kSet, 0, int(sets_.size()) - 1);
    } else {
      Emit(kChar, c);
    }
  }

  void Class() {  // at '['
    at_++;
    Set s;
    if (More() && Peek() == '^') {
      s.negate = true;
      at_++;
    }
    bool first = true;
    while (true) {
      if (!More()) Refuse("a Replace normalizer's regex: missing ]");
      char32_t c = Peek();
      if (c == ']' && !first) { at_++; break; }
      first = false;
      if (c == '[') Unsupported("a nested [ or a POSIX class in a Replace regex is not implemented");
      char32_t lo = c == '\\' ? Escape() : (at_++, c);
      char32_t hi = lo;
      if (More() && Peek() == '-' && at_ + 1 < p_.size() && p_[at_ + 1] != ']') {
        at_++;
        char32_t h = Peek();
        if (h == '[') Unsupported("a nested [ in a Replace regex is not implemented");
        hi = h == '\\' ? Escape() : (at_++, h);
        if (hi < lo) Refuse("a Replace normalizer's regex: a range with its ends reversed");
      }
      FoldTrap(lo, hi);
      s.ranges.push_back({lo, hi});
    }
    if (icase_) {
      auto more = s.ranges;
      for (auto& r : s.ranges) {
        char32_t a = std::max<char32_t>(r.first, 'a'), b = std::min<char32_t>(r.second, 'z');
        if (a <= b) more.push_back({a & ~char32_t(0x20), b & ~char32_t(0x20)});
        a = std::max<char32_t>(r.first, 'A');
        b = std::min<char32_t>(r.second, 'Z');
        if (a <= b) more.push_back({a | 0x20, b | 0x20});
      }
      s.ranges = more;
    }
    sets_.push_back(s);
    Emit(kSet, 0, int(sets_.size()) - 1);
  }

  // --- matcher --------------------------------------------------------------------------------
  bool Find(const std::string& text, size_t from, size_t* ms, size_t* me, Memo& seen) const {
    std::vector<std::pair<int, size_t>> stack;
    for (size_t start = from; start <= text.size();) {
      stack.assign(1, {0, start});
      while (!stack.empty()) {
        auto [pc, pos] = stack.back();
        stack.pop_back();
        while (true) {
          if (!seen.Visit(pc, pos)) break;
          const Inst& in = prog_[size_t(pc)];
          if (in.op == kMatch) {
            *ms = start;
            *me = pos;
            return true;
          }
          if (in.op == kJmp) { pc = in.x; continue; }
          if (in.op == kSplit) {
            stack.push_back({in.y, pos});
            pc = in.x;
            continue;
          }
          if (in.op == kBol) { if (pos != 0 && text[pos - 1] != '\n') break; pc++; continue; }
          if (in.op == kEol) { if (pos != text.size() && text[pos] != '\n') break; pc++; continue; }
          if (pos >= text.size()) break;
          auto d = ud::DecodeRune(std::string_view(text).substr(pos));
          bool ok;
          if (in.op == kChar) ok = d.rune == in.c;
          else if (in.op == kAny) ok = d.rune != '\n';
          else {
            const Set& s = sets_[size_t(in.x)];
            bool hit = false;
            for (auto& r : s.ranges) hit = hit || (d.rune >= r.first && d.rune <= r.second);
            ok = hit != s.negate;
          }
          if (!ok) break;
          pos += d.width;
          pc++;
        }
      }
      start += start < text.size() ? ud::DecodeRune(std::string_view(text).substr(start)).width : 1;
    }
    return false;
  }
};

// ------------------------------------------------------------------------------------------
// Component sections of tokenizer.json.
// ------------------------------------------------------------------------------------------
using Normalizer = std::function<std::string(const std::string&)>;

const Value* Member(const Value& node, const char* key) {
  const Value* v = node.Find(key);
  return (v == nullptr || v->is_null()) ? nullptr : v;
}
std::string Str(const Value& n, const char* key, const std::string& def) {
  const Value* v = Member(n, key);
  if (v == nullptr) return def;
  if (v->kind() != Value::Kind::String) Refuse(std::string("\"") + key + "\" must be a string, found " + pyvalue::TypeName(*v));
  return v->as_string();
}
bool Bool(const Value& n, const char* key, bool def) {
  const Value* v = Member(n, key);
  if (v == nullptr) return def;
  if (v->kind() != Value::Kind::Bool) Refuse(std::string("\"") + key + "\" must be a boolean, found " + pyvalue::TypeName(*v));
  return v->as_bool();
}
int Int(const Value& n, const char* key, int def) {
  const Value* v = Member(n, key);
  if (v == nullptr) return def;
  if (v->kind() == Value::Kind::Int && v->as_int() >= -1000000000 && v->as_int() <= 1000000000) return int(v->as_int());
  if (v->kind() == Value::Kind::Float && v->as_float() >= -1e9 && v->as_float() <= 1e9 && v->as_float() == double(int(v->as_float()))) {
    return int(v->as_float());
  }
  Refuse(std::string("\"") + key + "\" must be an integer");
}
const Value& Object(const Value& n, const char* key) {
  const Value* v = n.Find(key);
  if (v == nullptr || v->kind() != Value::Kind::Object) Refuse(std::string("\"") + key + "\" must be an object");
  return *v;
}
const Value& Array(const Value& n, const char* key) {
  const Value* v = n.Find(key);
  if (v == nullptr || v->kind() != Value::Kind::Array) Refuse(std::string("\"") + key + "\" must be an array");
  return *v;
}
std::string TypeOf(const Value& n, const char* what) {
  if (n.kind() != Value::Kind::Object) Refuse(std::string(what) + " must be an object or null");
  std::string kind = Str(n, "type", "");
  if (kind.empty()) Refuse(std::string("a ") + what + " must declare a type");
  return kind;
}

bool DialectDiffers(const std::string& expr, char* which) {
  for (size_t i = 0; i + 1 < expr.size(); i++) {
    if (expr[i] != '\\') continue;
    i++;
    if (std::string("sSdDwWbBpP").find(expr[i]) != std::string::npos) {
      *which = expr[i];
      return true;
    }
  }
  return false;
}

std::string ReplaceAllLiteral(const std::string& s, const std::string& from, const std::string& to) {
  std::string out;
  size_t at = 0;
  while (true) {
    size_t hit = s.find(from, at);
    if (hit == std::string::npos) break;
    out.append(s, at, hit - at);
    out += to;
    at = hit + from.size();
  }
  out.append(s, at, std::string::npos);
  return out;
}

Normalizer ParseNormalizer(const Value* n, bool* may_drop = nullptr) {
  if (n == nullptr || n->is_null()) return [](const std::string& s) { return s; };
  std::string kind = TypeOf(*n, "normalizer");
  if (kind == "NFC") return [](const std::string& s) { return NormalizeImpl(s, Form::NFC); };
  if (kind == "NFD") return [](const std::string& s) { return NormalizeImpl(s, Form::NFD); };
  if (kind == "NFKC") return [](const std::string& s) { return NormalizeImpl(s, Form::NFKC); };
  if (kind == "NFKD") return [](const std::string& s) { return NormalizeImpl(s, Form::NFKD); };
  if (kind == "Lowercase") return [](const std::string& s) { return LowercaseImpl(s); };
  if (kind == "Prepend") {
    std::string prefix = Str(*n, "prepend", "");
    return [prefix](const std::string& s) { return s.empty() ? s : prefix + s; };  // non-empty text only
  }
  if (kind == "Strip") {
    bool l = Bool(*n, "strip_left", true), r = Bool(*n, "strip_right", true);
    if (l && may_drop != nullptr) *may_drop = true;
    return [l, r](const std::string& s) { return StripImpl(s, l, r); };
  }
  if (kind == "Replace") {
    if (may_drop != nullptr) *may_drop = true;
    const Value& pattern = Object(*n, "pattern");
    const Value* content = n->Find("content");
    if (content == nullptr || content->kind() != Value::Kind::String) Refuse("a Replace normalizer must declare content");
    std::string to = content->as_string();
    if (const Value* lit = pattern.Find("String"); lit != nullptr && lit->kind() == Value::Kind::String) {
      std::string from = lit->as_string();
      if (from.empty()) Refuse("a Replace normalizer cannot match the empty string");
      return [from, to](const std::string& s) { return ReplaceAllLiteral(s, from, to); };
    }
    const Value* rx = pattern.Find("Regex");
    if (rx == nullptr || rx->kind() != Value::Kind::String) {
      Refuse("a Replace normalizer's pattern must be {\"String\": ...} or {\"Regex\": ...}");
    }
    char which;
    if (DialectDiffers(rx->as_string(), &which)) {
      Unsupported(std::string("the Replace regex uses \\") + which +
                  ", whose meaning differs between the reference's regex engine (Unicode-aware) and "
                  "an ASCII one, so it would normalize differently; refusing to load");
    }
    auto re = std::make_shared<Regex>(rx->as_string());
    return [re, to](const std::string& s) { return re->ReplaceAll(s, to); };
  }
  if (kind == "Sequence") {
    std::vector<Normalizer> steps;
    for (const Value& child : Array(*n, "normalizers").items()) {
      if (child.kind() != Value::Kind::Object) Refuse("a normalizer in a Sequence must be an object");
      steps.push_back(ParseNormalizer(&child, may_drop));
    }
    return [steps](const std::string& s) {
      std::string cur = s;
      for (const auto& step : steps) cur = step(cur);
      return cur;
    };
  }
  Unsupported("the normalizer \"" + kind + "\" is not implemented; refusing to load rather than produce ids "
              "that are wrong in a way no answer-level test would localise");
}

// The byte-level stand-in alphabet: printable ASCII and Latin-1 bytes map to themselves, the other
// 68 to U+0100 upward.
struct Alphabet {
  char32_t to_rune[256];
  int16_t to_byte[0x144];
  Alphabet() {
    std::fill(std::begin(to_byte), std::end(to_byte), int16_t(-1));
    int lifted = 0;
    for (int b = 0; b < 256; b++) {
      if ((b >= '!' && b <= '~') || (b >= 0xA1 && b <= 0xAC) || (b >= 0xAE && b <= 0xFF)) to_rune[b] = char32_t(b);
      else to_rune[b] = char32_t(256 + lifted++);
      to_byte[to_rune[b]] = int16_t(b);
    }
  }
  int ByteFor(char32_t r) const { return r >= 0x144 ? -1 : to_byte[r]; }
  std::string Encode(std::string_view piece) const {
    std::string out;
    out.reserve(piece.size() + piece.size() / 4);
    for (unsigned char c : piece) ud::AppendRune(out, to_rune[c]);
    return out;
  }
};
const Alphabet& TheAlphabet() {
  static const Alphabet a;
  return a;
}

class PreTokenizer {
 public:
  virtual ~PreTokenizer() = default;
  // `origin`: the text starts where the input did (not after an added token).
  virtual void Split(std::string_view text, std::vector<std::string>& out, bool origin) const = 0;
  virtual bool PrependsFirstOnly() const { return false; }
};

class WholeText : public PreTokenizer {
 public:
  void Split(std::string_view text, std::vector<std::string>& out, bool) const override {
    if (!text.empty()) out.emplace_back(text);
  }
};

class ByteLevel : public PreTokenizer {
 public:
  ByteLevel(bool prefix, bool regex) : add_prefix_space_(prefix), use_regex_(regex) {}
  void Split(std::string_view text, std::vector<std::string>& out, bool) const override {
    if (text.empty()) return;
    std::string source(text);
    if (add_prefix_space_ && source[0] != ' ') source = " " + source;
    if (!use_regex_) {
      out.push_back(TheAlphabet().Encode(source));
      return;
    }
    for (size_t at = 0; at < source.size();) {
      size_t end = Cut(source, at);
      out.push_back(TheAlphabet().Encode(std::string_view(source).substr(at, end - at)));
      at = end;
    }
  }

 private:
  // The GPT-2 pattern  's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+
  // as a scanner: the pattern has a lookahead, and no standard regex has it with Unicode classes.
  static bool InClass(char32_t r, int branch) {
    if (branch == 0) return IsLetter(r);
    if (branch == 1) return IsNumber(r);
    return !IsWhiteSpace(r) && !IsLetter(r) && !IsNumber(r);
  }
  static size_t RunEnd(const std::string& s, size_t at, int branch) {
    while (at < s.size()) {
      auto d = ud::DecodeRune(std::string_view(s).substr(at));
      if (!InClass(d.rune, branch)) break;
      at += d.width;
    }
    return at;
  }
  static size_t Cut(const std::string& s, size_t from) {
    static const char* const kContractions[] = {"'s", "'t", "'re", "'ve", "'m", "'ll", "'d"};
    std::string_view rest = std::string_view(s).substr(from);
    for (const char* c : kContractions) {
      std::string_view cv(c);
      if (rest.substr(0, cv.size()) == cv) return from + cv.size();
    }
    auto first = ud::DecodeRune(rest);
    for (int branch = 0; branch < 3; branch++) {
      if (first.rune == ' ') {
        size_t after = from + 1;
        if (after < s.size() && InClass(ud::DecodeRune(std::string_view(s).substr(after)).rune, branch)) {
          return RunEnd(s, after, branch);
        }
      } else if (InClass(first.rune, branch)) {
        return RunEnd(s, from, branch);
      }
    }
    if (IsWhiteSpace(first.rune)) {
      size_t end = from;
      while (end < s.size()) {
        auto d = ud::DecodeRune(std::string_view(s).substr(end));
        if (!IsWhiteSpace(d.rune)) break;
        end += d.width;
      }
      if (end >= s.size()) return end;
      // \s+(?!\S) gives the last white-space character back to the next piece.
      size_t w = ud::DecodeLastRune(std::string_view(s).substr(0, end)).width;
      if (end - w > from) return end - w;
      return end;  // a single space: \s+(?!\S) fails and \s+ takes it
    }
    return from + first.width;
  }
  bool add_prefix_space_, use_regex_;
};

class Metaspace : public PreTokenizer {
 public:
  Metaspace(std::string replacement, bool prepend, bool first_only, bool split)
      : replacement_(std::move(replacement)), prepend_(prepend), first_only_(first_only), split_(split) {}
  bool PrependsFirstOnly() const override { return prepend_ && first_only_; }
  void Split(std::string_view text, std::vector<std::string>& out, bool origin) const override {
    if (text.empty()) return;
    std::string source = ReplaceAllLiteral(std::string(text), " ", replacement_);
    if (prepend_ && (origin || !first_only_) && source.compare(0, replacement_.size(), replacement_) != 0) source = replacement_ + source;
    if (!split_) {
      out.push_back(source);
      return;
    }
    size_t start = 0;
    size_t from = ud::DecodeRune(source).width;  // a marker at the very start does not split
    while (true) {
      size_t next = source.find(replacement_, from);
      if (next == std::string::npos) break;
      out.push_back(source.substr(start, next - start));
      start = next;
      from = next + replacement_.size();
    }
    if (start < source.size()) out.push_back(source.substr(start));
  }

 private:
  std::string replacement_;
  bool prepend_, first_only_, split_;
};

class SequencePre : public PreTokenizer {
 public:
  std::vector<std::unique_ptr<PreTokenizer>> steps;
  bool PrependsFirstOnly() const override {
    for (const auto& step : steps) {
      if (step->PrependsFirstOnly()) return true;
    }
    return false;
  }
  void Split(std::string_view text, std::vector<std::string>& out, bool origin) const override {
    std::vector<std::string> current{std::string(text)};
    for (const auto& step : steps) {
      std::vector<std::string> next;
      // Every pre-tokenizer here keeps the text whole, so only the first piece is still at the start.
      for (size_t i = 0; i < current.size(); i++) step->Split(current[i], next, origin && i == 0);
      current.swap(next);
    }
    out.insert(out.end(), current.begin(), current.end());
  }
};

std::unique_ptr<PreTokenizer> ParsePreTokenizer(const Value* n) {
  if (n == nullptr || n->is_null()) return std::make_unique<WholeText>();
  std::string kind = TypeOf(*n, "pre_tokenizer");
  if (kind == "ByteLevel") return std::make_unique<ByteLevel>(Bool(*n, "add_prefix_space", true), Bool(*n, "use_regex", true));
  if (kind == "Metaspace") {
    std::string replacement = Str(*n, "replacement", "\xE2\x96\x81");
    if (ud::RuneCount(replacement) != 1) Refuse("a Metaspace replacement must be exactly one code point");
    std::string scheme = Str(*n, "prepend_scheme", "always");
    bool split = Bool(*n, "split", true);
    // The legacy flag must agree with the scheme, as in the crate (true with "never" is accepted).
    if (!Bool(*n, "add_prefix_space", true) && scheme != "never") {
      Refuse("a Metaspace add_prefix_space does not match its declared prepend_scheme");
    }
    if (scheme == "always") return std::make_unique<Metaspace>(replacement, true, false, split);
    if (scheme == "first") return std::make_unique<Metaspace>(replacement, true, true, split);
    if (scheme == "never") return std::make_unique<Metaspace>(replacement, false, false, split);
    Refuse("unknown Metaspace prepend_scheme \"" + scheme + "\"");
  }
  if (kind == "Sequence") {
    auto seq = std::make_unique<SequencePre>();
    for (const Value& child : Array(*n, "pretokenizers").items()) {
      if (child.kind() != Value::Kind::Object) Refuse("a pre-tokenizer in a Sequence must be an object");
      seq->steps.push_back(ParsePreTokenizer(&child));
    }
    return seq;
  }
  Unsupported("the pre-tokenizer \"" + kind + "\" is not implemented; refusing to load rather than produce ids "
              "that are wrong in a way no answer-level test would localise");
}

// ------------------------------------------------------------------------------------------
// Decoders.
// ------------------------------------------------------------------------------------------
class Decoder {
 public:
  virtual ~Decoder() = default;
  virtual void Transform(std::vector<std::string>& tokens) const = 0;
};

class ByteLevelDecoder : public Decoder {
 public:
  // A token holding a character outside the alphabet is taken as plain text; the whole is then
  // decoded as lossy UTF-8.
  void Transform(std::vector<std::string>& tokens) const override {
    std::string raw;
    for (const auto& token : tokens) {
      std::string mapped;
      bool ok = true;
      std::string_view rest(token);
      while (!rest.empty()) {
        auto d = ud::DecodeRune(rest);
        int b = TheAlphabet().ByteFor(d.rune);
        if (b < 0) {
          ok = false;
          break;
        }
        mapped.push_back(char(b));
        rest.remove_prefix(d.width);
      }
      raw += ok ? mapped : token;
    }
    tokens.assign(1, ud::Lossy(raw));
  }
};

class ReplaceDecoder : public Decoder {
 public:
  ReplaceDecoder(std::string p, std::string c) : pattern_(std::move(p)), content_(std::move(c)) {}
  void Transform(std::vector<std::string>& tokens) const override {
    for (auto& t : tokens) t = ReplaceAllLiteral(t, pattern_, content_);
  }

 private:
  std::string pattern_, content_;
};

int HexValue(char c) {
  if (c >= '0' && c <= '9') return c - '0';
  if (c >= 'A' && c <= 'F') return c - 'A' + 10;
  if (c >= 'a' && c <= 'f') return c - 'a' + 10;
  return -1;
}
// "<0xNN>", read as Rust's from_str_radix does: lower-case digits, and a '+' on the high digit
// leaves only the low digit.
bool ByteToken(const std::string& t, unsigned char* out) {
  if (t.size() != 6 || t[0] != '<' || t[1] != '0' || t[2] != 'x' || t[5] != '>') return false;
  if (t[3] == '+') {
    int l = HexValue(t[4]);
    *out = (unsigned char)l;
    return l >= 0;
  }
  int h = HexValue(t[3]), l = HexValue(t[4]);
  if (h < 0 || l < 0) return false;
  *out = (unsigned char)(h << 4 | l);
  return true;
}

class ByteFallbackDecoder : public Decoder {
 public:
  void Transform(std::vector<std::string>& tokens) const override {
    std::vector<std::string> out;
    std::string run;
    auto flush = [&]() {
      if (run.empty()) return;
      if (ud::ValidUtf8(run)) out.push_back(run);
      else for (size_t i = 0; i < run.size(); i++) out.push_back("\xEF\xBF\xBD");
      run.clear();
    };
    for (const auto& token : tokens) {
      unsigned char b;
      if (ByteToken(token, &b)) {
        run.push_back(char(b));
        continue;
      }
      flush();
      out.push_back(token);
    }
    flush();
    tokens.swap(out);
  }
};

class FuseDecoder : public Decoder {
 public:
  void Transform(std::vector<std::string>& tokens) const override {
    std::string all;
    for (const auto& t : tokens) all += t;
    tokens.assign(1, all);
  }
};

class StripDecoder : public Decoder {
 public:
  StripDecoder(std::string c, int start, int stop) : c_(std::move(c)), start_(start), stop_(stop) {}
  void Transform(std::vector<std::string>& tokens) const override {
    for (auto& t : tokens) {
      for (int n = 0; n < start_ && t.compare(0, c_.size(), c_) == 0; n++) t.erase(0, c_.size());
      for (int n = 0; n < stop_ && t.size() >= c_.size() && t.compare(t.size() - c_.size(), c_.size(), c_) == 0; n++) {
        t.erase(t.size() - c_.size());
      }
    }
  }

 private:
  std::string c_;
  int start_, stop_;
};

class SequenceDecoder : public Decoder {
 public:
  std::vector<std::unique_ptr<Decoder>> steps;
  void Transform(std::vector<std::string>& tokens) const override {
    for (const auto& s : steps) s->Transform(tokens);
  }
};

std::unique_ptr<Decoder> ParseDecoder(const Value* n) {
  if (n == nullptr || n->is_null()) return nullptr;
  std::string kind = TypeOf(*n, "decoder");
  if (kind == "ByteLevel") return std::make_unique<ByteLevelDecoder>();
  if (kind == "ByteFallback") return std::make_unique<ByteFallbackDecoder>();
  if (kind == "Fuse") return std::make_unique<FuseDecoder>();
  if (kind == "Replace") {
    const Value* p = n->Find("pattern");
    std::string literal;
    if (p != nullptr && p->kind() == Value::Kind::Object) {
      const Value* s = p->Find("String");
      if (s == nullptr || s->kind() != Value::Kind::String) {
        if (p->Find("Regex") != nullptr) {
          Unsupported("only a literal String pattern is implemented in a Replace decoder; this checkpoint declares a Regex one");
        }
        Refuse("a Replace decoder needs a String pattern");
      }
      literal = s->as_string();
    } else if (p != nullptr && p->kind() == Value::Kind::String) {
      literal = p->as_string();
    } else {
      Refuse("a Replace decoder needs a String pattern");
    }
    if (literal.empty()) Refuse("a Replace decoder cannot match the empty string");
    return std::make_unique<ReplaceDecoder>(literal, Str(*n, "content", ""));
  }
  if (kind == "Strip") {
    std::string c = Str(*n, "content", " ");
    if (ud::RuneCount(c) != 1) Refuse("a Strip decoder's content must be one character");
    return std::make_unique<StripDecoder>(c, Int(*n, "start", 0), Int(*n, "stop", 0));
  }
  if (kind == "Sequence") {
    auto seq = std::make_unique<SequenceDecoder>();
    const Value* steps = n->Find("decoders");
    if (steps == nullptr || steps->kind() != Value::Kind::Array) Refuse("a Sequence decoder needs a decoders array");
    for (const Value& step : steps->items()) {
      if (step.kind() != Value::Kind::Object) Refuse("every Sequence decoder step must be an object");
      seq->steps.push_back(ParseDecoder(&step));
    }
    return seq;
  }
  Unsupported("the decoder \"" + kind + "\" is not implemented (ByteLevel, Replace, ByteFallback, Fuse, Strip and "
              "Sequence are); refusing to load rather than decode it wrongly");
}

// ------------------------------------------------------------------------------------------
// Added tokens.
// ------------------------------------------------------------------------------------------
struct AddedToken {
  std::string content;
  int32_t id;
  bool special, lstrip, rstrip, single_word, normalized;
};

struct Span {
  std::string text;
  int32_t id = 0;
  bool is_token = false;
  size_t offset = 0;  // byte offset of the span in the text that was cut
};

// The added tokens that start with one character, longest first (the reference's leftmost-longest
// match). `second` records which bytes follow that character in any of them, so the common miss is
// rejected without trying each token.
struct Bucket {
  std::vector<const AddedToken*> tokens;
  bool second[256] = {};
  bool whole = false;  // a token is that single character
  void Add(const AddedToken* t, size_t first_width) {
    tokens.push_back(t);
    if (t->content.size() == first_width) whole = true;
    else second[(unsigned char)t->content[first_width]] = true;
  }
};

class AddedVocab {
 public:
  bool empty = true;
  AddedVocab() = default;
  explicit AddedVocab(const std::vector<AddedToken>& tokens) : empty(tokens.empty()), store_(tokens) {
    for (const auto& t : store_) {
      if (t.content.empty()) Refuse("an added token cannot have empty content");
      auto d = ud::DecodeRune(t.content);
      if (d.rune < 0x80) ascii_[d.rune].Add(&t, d.width);
      else other_[d.rune].Add(&t, d.width);
    }
    auto longest_first = [](Bucket& b) {
      std::sort(b.tokens.begin(), b.tokens.end(), [](const AddedToken* x, const AddedToken* y) {
        if (x->content.size() != y->content.size()) return x->content.size() > y->content.size();
        return x->content < y->content;
      });
    };
    for (auto& b : ascii_) longest_first(b);
    for (auto& kv : other_) longest_first(kv.second);
  }

  // Cuts text around its added tokens; lstrip and rstrip tokens absorb the white space beside them.
  std::vector<Span> Split(const std::string& text) const {
    std::vector<Span> out;
    if (text.empty()) return out;
    if (empty) {
      out.push_back(Span{text, 0, false, 0});
      return out;
    }
    size_t plain_from = 0;
    for (size_t at = 0; at < text.size();) {
      auto d = ud::DecodeRune(std::string_view(text).substr(at));
      size_t skip = 0;
      const AddedToken* hit = LongestAt(text, at, d.rune, d.width, &skip);
      if (skip != 0) {  // the crate skips a longest hit that fails single_word, shorter tokens inside it too
        at += skip;
        continue;
      }
      if (hit == nullptr) {
        at += d.width;
        continue;
      }
      size_t start = at, stop = at + hit->content.size();
      if (hit->lstrip) {
        while (start > plain_from) {
          auto p = ud::DecodeLastRune(std::string_view(text).substr(0, start));
          if (!IsWhiteSpace(p.rune)) break;
          start -= p.width;
        }
      }
      if (hit->rstrip) {
        while (stop < text.size()) {
          auto nx = ud::DecodeRune(std::string_view(text).substr(stop));
          if (!IsWhiteSpace(nx.rune)) break;
          stop += nx.width;
        }
      }
      if (start > plain_from) out.push_back(Span{text.substr(plain_from, start - plain_from), 0, false, plain_from});
      out.push_back(Span{hit->content, hit->id, true, start});
      plain_from = at = stop;
    }
    if (plain_from < text.size()) out.push_back(Span{text.substr(plain_from), 0, false, plain_from});
    return out;
  }

 private:
  const Bucket* BucketOf(char32_t r) const {
    if (r < 0x80) return &ascii_[r];
    auto it = other_.find(r);
    return it == other_.end() ? nullptr : &it->second;
  }
  // `skip` is set to the length of a longest hit that fails single_word.
  const AddedToken* LongestAt(const std::string& text, size_t at, char32_t first, size_t width, size_t* skip) const {
    const Bucket* b = BucketOf(first);
    if (b == nullptr || b->tokens.empty()) return nullptr;
    if (!b->whole) {
      size_t next = at + width;
      if (next >= text.size() || !b->second[(unsigned char)text[next]]) return nullptr;
    }
    for (const AddedToken* t : b->tokens) {
      if (text.compare(at, t->content.size(), t->content) != 0) continue;
      if (t->single_word && !StandsAlone(text, at, at + t->content.size())) {
        *skip = t->content.size();
        return nullptr;
      }
      return t;
    }
    return nullptr;
  }
  static bool StandsAlone(const std::string& text, size_t start, size_t stop) {
    if (start > 0 && IsWordChar(ud::DecodeLastRune(std::string_view(text).substr(0, start)).rune)) return false;
    if (stop < text.size() && IsWordChar(ud::DecodeRune(std::string_view(text).substr(stop)).rune)) return false;
    return true;
  }
  std::vector<AddedToken> store_;  // the buckets point into it; a moved vector keeps its buffer
  Bucket ascii_[128];
  std::unordered_map<char32_t, Bucket> other_;
};

// ------------------------------------------------------------------------------------------
// BPE with byte fallback.
// ------------------------------------------------------------------------------------------
constexpr size_t kHeapMinSymbols = 32;
constexpr int32_t kNoMerge = 1 << 30;
constexpr char32_t kSmallRunes = 0x180;

struct MergeRule {
  int32_t rank = kNoMerge;
  int32_t id = -1;
};
struct Symbol {
  int32_t start, end, id;  // id -1: a character the vocabulary lacks
};

uint64_t PairKey(int32_t l, int32_t r) { return (uint64_t(uint32_t(l)) << 32) | uint32_t(r); }

class Bpe {
 public:
  Bpe(const std::unordered_map<std::string, int32_t>& vocab, const std::vector<std::pair<std::string, std::string>>& merges,
      const std::string* unk, bool fuse_unk, bool ignore_merges, bool byte_fallback)
      : vocab_(&vocab), fuse_unk_(fuse_unk), ignore_merges_(ignore_merges) {
    for (char32_t r = 0; r < kSmallRunes; r++) {
      std::string s;
      ud::AppendRune(s, r);
      auto it = vocab.find(s);
      small_[r] = it == vocab.end() ? -1 : it->second;
    }
    if (unk != nullptr) {
      auto it = vocab.find(*unk);
      if (it == vocab.end()) {
        Refuse("the tokenizer names " + *unk + " as its unknown token, but neither the vocabulary nor the added-token "
               "table has an entry for it");
      }
      unk_id_ = it->second;
      has_unk_ = true;
    }
    merges_.reserve(merges.size());
    for (size_t rank = 0; rank < merges.size(); rank++) {
      const auto& pair = merges[rank];
      auto l = vocab.find(pair.first), r = vocab.find(pair.second);
      if (l == vocab.end() || r == vocab.end()) {
        Refuse("merge at rank " + std::to_string(rank) + " uses the symbol \"" + (l == vocab.end() ? pair.first : pair.second) +
               "\", which the vocabulary does not contain; merging on ids would be unsound");
      }
      auto merged = vocab.find(pair.first + pair.second);
      if (merged == vocab.end()) {
        Refuse("merge at rank " + std::to_string(rank) + " produces \"" + pair.first + pair.second +
               "\", which the vocabulary does not contain");
      }
      // The crate builds byte-fallback and unknown tokens before merging; this port applies them after.
      for (const std::string* name : {&pair.first, &pair.second, &merged->first}) {
        unsigned char b;
        if ((byte_fallback && ByteToken(*name, &b)) || (unk != nullptr && *name == *unk)) {
          Unsupported("merge at rank " + std::to_string(rank) + " names the byte or unknown token \"" + *name + "\"");
        }
      }
      merges_.emplace(PairKey(l->second, r->second), MergeRule{int32_t(rank), merged->second});  // the lowest rank wins
    }
    if (byte_fallback) {
      has_bytes_ = true;
      for (int v = 0; v < 256; v++) {
        char name[8];
        std::snprintf(name, sizeof name, "<0x%02X>", v);
        auto it = vocab.find(name);
        byte_ids_[v] = it == vocab.end() ? -1 : it->second;
      }
    }
  }

  bool has_unk() const { return has_unk_; }
  bool has_byte_fallback() const { return has_bytes_; }

  void EncodePiece(const std::string& piece, std::vector<int32_t>& out) const {
    if (piece.empty()) return;
    if (ignore_merges_) {
      auto it = vocab_->find(piece);
      if (it != vocab_->end()) {
        out.push_back(it->second);
        return;
      }
    }
    std::vector<Symbol> symbols = Initial(piece);
    if (symbols.size() >= kHeapMinSymbols) MergeWithHeap(symbols);
    else MergeByRescan(symbols);
    Emit(piece, symbols, out);
  }

  std::vector<Symbol> Initial(const std::string& piece) const {
    std::vector<Symbol> symbols;
  symbols.reserve(piece.size());
  for (size_t i = 0; i < piece.size();) {
    auto d = ud::DecodeRune(std::string_view(piece).substr(i));
    int32_t id;
    if (d.rune < kSmallRunes && d.rune != ud::kReplacement) {
      id = small_[d.rune];
    } else {
      auto it = vocab_->find(piece.substr(i, d.width));
      id = it == vocab_->end() ? -1 : it->second;
    }
    symbols.push_back(Symbol{int32_t(i), int32_t(i + d.width), id});
    i += d.width;
  }
    return symbols;
  }

  // The two merge strategies must give one answer; the test seam compares them on a piece.
  bool StrategiesAgree(const std::string& piece) const {
    std::vector<Symbol> a = Initial(piece), b = a;
    if (a.empty()) return true;
    MergeByRescan(a);
    MergeWithHeap(b);
    if (a.size() != b.size()) return false;
    for (size_t i = 0; i < a.size(); i++) {
      if (a[i].start != b[i].start || a[i].end != b[i].end || a[i].id != b[i].id) return false;
    }
    return true;
  }

  // Both strategies are public for the test that they agree.
  void MergeByRescan(std::vector<Symbol>& symbols) const {
    std::vector<MergeRule> rules(symbols.size());
    auto pair = [&](size_t i) { rules[i] = Rule(symbols[i], symbols[i + 1]); };
    for (size_t i = 0; i + 1 < symbols.size(); i++) pair(i);
    while (symbols.size() > 1) {
      int32_t best_rank = kNoMerge;
      long best_at = -1;
      for (size_t i = 0; i + 1 < symbols.size(); i++) {
        if (rules[i].rank < best_rank) {
          best_rank = rules[i].rank;
          best_at = long(i);
        }
      }
      if (best_at < 0) return;
      size_t b = size_t(best_at);
      symbols[b] = Symbol{symbols[b].start, symbols[b + 1].end, rules[b].id};
      symbols.erase(symbols.begin() + long(b) + 1);
      rules.erase(rules.begin() + long(b) + 1);
      if (b + 1 < symbols.size()) pair(b);
      if (b > 0) pair(b - 1);
    }
  }

  void MergeWithHeap(std::vector<Symbol>& symbols) const {
    struct Item {
      int32_t rank, slot, version;
      bool operator>(const Item& o) const { return rank != o.rank ? rank > o.rank : slot > o.slot; }
    };
    size_t n = symbols.size();
    std::vector<int32_t> next(n), prev(n), version(n, 0);
    std::vector<char> dead(n, 0);
    for (size_t i = 0; i < n; i++) {
      prev[i] = int32_t(i) - 1;
      next[i] = int32_t(i) + 1;
    }
    next[n - 1] = -1;
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> queue;
    auto offer = [&](int32_t slot) {
      int32_t right = next[size_t(slot)];
      if (right < 0) return;
      MergeRule r = Rule(symbols[size_t(slot)], symbols[size_t(right)]);
      if (r.rank != kNoMerge) queue.push(Item{r.rank, slot, version[size_t(slot)]});
    };
    for (size_t i = 0; i < n; i++) offer(int32_t(i));
    while (!queue.empty()) {
      Item item = queue.top();
      queue.pop();
      size_t slot = size_t(item.slot);
      if (dead[slot] || version[slot] != item.version) continue;
      int32_t right = next[slot];
      if (right < 0 || dead[size_t(right)]) continue;
      MergeRule r = Rule(symbols[slot], symbols[size_t(right)]);
      if (r.rank == kNoMerge) continue;
      symbols[slot] = Symbol{symbols[slot].start, symbols[size_t(right)].end, r.id};
      dead[size_t(right)] = 1;
      next[slot] = next[size_t(right)];
      if (next[size_t(right)] >= 0) prev[size_t(next[size_t(right)])] = int32_t(slot);
      version[slot]++;
      offer(int32_t(slot));
      if (prev[slot] >= 0) {
        version[size_t(prev[slot])]++;
        offer(prev[slot]);
      }
    }
    std::vector<Symbol> out;
    for (int32_t i = 0; i >= 0 && size_t(i) < n; i = next[size_t(i)]) {
      if (!dead[size_t(i)]) out.push_back(symbols[size_t(i)]);
    }
    symbols.swap(out);
  }

 private:
  MergeRule Rule(const Symbol& l, const Symbol& r) const {
    if (l.id < 0 || r.id < 0) return MergeRule{};
    auto it = merges_.find(PairKey(l.id, r.id));
    return it == merges_.end() ? MergeRule{} : it->second;
  }

  // A symbol outside the vocabulary becomes its UTF-8 bytes when the checkpoint has byte fallback
  // and every byte resolves, else the unknown token (one per run with fuse_unk), else it is dropped.
  void Emit(const std::string& piece, const std::vector<Symbol>& symbols, std::vector<int32_t>& out) const {
    bool unknown_pending = false;
    for (const Symbol& s : symbols) {
      if (s.id >= 0) {
        unknown_pending = false;
        out.push_back(s.id);
        continue;
      }
      if (has_bytes_) {
        bool resolves = true;
        for (int32_t i = s.start; i < s.end; i++) resolves = resolves && byte_ids_[(unsigned char)piece[size_t(i)]] >= 0;
        if (resolves) {
          for (int32_t i = s.start; i < s.end; i++) out.push_back(byte_ids_[(unsigned char)piece[size_t(i)]]);
          unknown_pending = false;
          continue;
        }
      }
      if (!has_unk_) continue;
      if (fuse_unk_ && unknown_pending) continue;
      out.push_back(unk_id_);
      unknown_pending = true;
    }
  }

  int32_t small_[kSmallRunes];
  const std::unordered_map<std::string, int32_t>* vocab_;
  std::unordered_map<uint64_t, MergeRule> merges_;
  int32_t unk_id_ = 0;
  bool has_unk_ = false, fuse_unk_, ignore_merges_, has_bytes_ = false;
  int32_t byte_ids_[256];
};

}  // namespace

// ------------------------------------------------------------------------------------------
// Tokenizer.
// ------------------------------------------------------------------------------------------
struct Impl {
  Normalizer normalizer;
  std::unique_ptr<PreTokenizer> pre;
  std::unique_ptr<Decoder> decoder;
  AddedVocab raw_added, normal_added;
  std::unique_ptr<Bpe> bpe;
  std::unordered_map<std::string, int32_t> ids;
  std::vector<std::string> tokens;
  std::map<std::string, int32_t> specials;
  std::unordered_set<int32_t> is_special;
  std::map<std::string, int32_t> roles;
  std::string mask_token;
  bool byte_level_only = false;
};

namespace {

void ReadMerges(const Value& model, std::vector<std::pair<std::string, std::string>>& out) {
  const Value* merges = model.Find("merges");
  if (merges == nullptr || merges->is_null()) return;
  if (merges->kind() != Value::Kind::Array) Refuse("model.merges must be an array");
  out.reserve(merges->size());
  for (const Value& m : merges->items()) {
    if (m.kind() == Value::Kind::String) {
      const std::string& j = m.as_string();
      bool found = false;
      for (size_t i = 1; i + 1 < j.size(); i++) {
        if (j[i] == ' ') {
          out.emplace_back(j.substr(0, i), j.substr(i + 1));
          found = true;
          break;
        }
      }
      if (!found) Refuse("a space-joined merge must have two non-empty halves, got \"" + j + "\"");
    } else if (m.kind() == Value::Kind::Array && m.size() == 2 && m.items()[0].kind() == Value::Kind::String &&
               m.items()[1].kind() == Value::Kind::String) {
      out.emplace_back(m.items()[0].as_string(), m.items()[1].as_string());
    } else {
      Refuse("a merge must be two strings or one space-joined string");
    }
  }
}

std::shared_ptr<const Impl> Build(std::string_view tokenizer_json, const Value* config) {
  auto parsed = pyvalue::Parse(tokenizer_json);
  if (!parsed.ok()) Refuse("tokenizer.json: " + parsed.error());
  const Value& doc = parsed.value();
  if (doc.kind() != Value::Kind::Object) Refuse("tokenizer.json must be a JSON object");
  const Value* model_v = doc.Find("model");
  if (model_v == nullptr || model_v->kind() != Value::Kind::Object) Refuse("model must be an object");
  const Value& model = *model_v;
  std::string type = Str(model, "type", "");
  if (type != "BPE") {
    Unsupported("this library implements the BPE tokenizer model; the checkpoint declares \"" + type +
                "\". Refusing to load rather than mis-tokenize silently");
  }
  auto impl = std::make_shared<Impl>();
  bool normalizer_may_drop = false;
  impl->normalizer = ParseNormalizer(Member(doc, "normalizer"), &normalizer_may_drop);
  impl->pre = ParsePreTokenizer(Member(doc, "pre_tokenizer"));
  if (normalizer_may_drop && impl->pre->PrependsFirstOnly()) {
    // The crate decides "first" by the original offset of the normalized text, which this port does not track.
    Unsupported("a Metaspace prepend_scheme \"first\" after a normalizer that can delete leading text (Strip, Replace)");
  }
  impl->decoder = ParseDecoder(Member(doc, "decoder"));
  impl->byte_level_only = dynamic_cast<const ByteLevel*>(impl->pre.get()) != nullptr;

  // Added tokens.
  std::vector<AddedToken> added;
  if (const Value* at = Member(doc, "added_tokens")) {
    if (at->kind() != Value::Kind::Array) Refuse("added_tokens must be an array");
    std::map<int32_t, std::string> seen;
    for (const Value& r : at->items()) {
      if (r.kind() != Value::Kind::Object) Refuse("an added_tokens entry must be an object");
      std::string content = Str(r, "content", "");
      if (content.empty()) Refuse("an added_tokens entry must declare content");
      const Value* id = Member(r, "id");
      if (id == nullptr || id->kind() != Value::Kind::Int || id->as_int() < 0 || id->as_int() > INT32_MAX) {
        Refuse("added token \"" + content + "\" has no non-negative id");
      }
      int32_t i = int32_t(id->as_int());
      auto clash = seen.find(i);
      if (clash != seen.end() && clash->second != content) {
        Refuse("added token id " + std::to_string(i) + " is claimed by both \"" + clash->second + "\" and \"" + content + "\"");
      }
      seen[i] = content;
      for (const char* flag : {"special", "lstrip", "rstrip", "single_word", "normalized"}) {
        const Value* f = r.Find(flag);
        if (f == nullptr || f->kind() != Value::Kind::Bool) {
          Refuse("added token \"" + content + "\" must declare " + flag + " as a boolean");
        }
      }
      added.push_back(AddedToken{content, i, Bool(r, "special", false), Bool(r, "lstrip", false), Bool(r, "rstrip", false),
                                 Bool(r, "single_word", false), Bool(r, "normalized", false)});
    }
  }
  const Value* vocab_v = Member(model, "vocab");
  if (vocab_v == nullptr || vocab_v->kind() != Value::Kind::Object) Refuse("model.vocab must be an object");
  auto& vocab = impl->ids;
  vocab.reserve(vocab_v->size() + added.size());
  for (size_t i = 0; i < vocab_v->size(); i++) {
    const Value& v = vocab_v->value(i);
    if (v.kind() != Value::Kind::Int || v.as_int() > INT32_MAX) Refuse("the vocabulary holds an id that is not an integer");
    if (v.as_int() < 0) Refuse("the vocabulary holds a negative id " + std::to_string(v.as_int()));
    vocab[vocab_v->key(i)] = int32_t(v.as_int());
  }
  {
    int32_t next = int32_t(vocab.size());
    for (auto& tok : added) {
      auto known = vocab.find(tok.content);
      int32_t expect = known != vocab.end() ? known->second : next++;
      if (known == vocab.end()) vocab[tok.content] = expect;
      if (tok.id != expect) {
        Refuse("added token \"" + tok.content + "\" declares id " + std::to_string(tok.id) + ", but the reference gives it " +
               std::to_string(expect) + " (its vocabulary id, or the next free id in file order)");
      }
    }
  }
  for (const auto& tok : added) {
    if (tok.special) {
      impl->is_special.insert(tok.id);
      impl->specials[tok.content] = tok.id;
    }
    vocab[tok.content] = tok.id;  // the added-token id wins over the vocabulary's, as in the reference
  }
  int32_t highest = 0;
  for (const auto& kv : vocab) highest = std::max(highest, kv.second);
  // Ids may have gaps, but a dense table sized by a hostile id would be gigabytes.
  if (int64_t(highest) >= int64_t(vocab.size()) * 4 + (1 << 16)) {
    Refuse("the highest token id " + std::to_string(highest) + " is far beyond the " + std::to_string(vocab.size()) +
           " tokens; ids this sparse are refused rather than allocated");
  }
  impl->tokens.assign(size_t(highest) + 1, std::string());
  for (const auto& kv : vocab) {
    std::string& owner = impl->tokens[size_t(kv.second)];
    if (!owner.empty() && owner != kv.first) {
      Refuse("the vocabulary gives id " + std::to_string(kv.second) + " to both \"" + owner + "\" and \"" + kv.first + "\"");
    }
    owner = kv.first;
  }

  std::vector<std::pair<std::string, std::string>> merges;
  ReadMerges(model, merges);
  for (const char* key : {"end_of_word_suffix", "continuing_subword_prefix"}) {
    const Value* v = Member(model, key);
    if (v != nullptr && v->kind() == Value::Kind::String && !v->as_string().empty()) {
      Unsupported(std::string("model.") + key + " is not implemented");
    }
  }
  if (Member(model, "dropout") != nullptr) Unsupported("model.dropout is not implemented");
  std::string unk;
  const Value* unk_v = Member(model, "unk_token");
  if (unk_v != nullptr && unk_v->kind() != Value::Kind::String) Refuse("model.unk_token must be a string or null");
  if (unk_v != nullptr) unk = unk_v->as_string();
  impl->bpe = std::make_unique<Bpe>(vocab, merges, unk_v != nullptr ? &unk : nullptr, Bool(model, "fuse_unk", false),
                                    Bool(model, "ignore_merges", false), Bool(model, "byte_fallback", false));

  // Refuse a tokenizer that could drop text without trace.
  if (!impl->bpe->has_unk() && !impl->bpe->has_byte_fallback()) {
    if (!impl->byte_level_only) {
      Unsupported("this checkpoint declares no unk_token and no byte_fallback, and its pre-tokenizer is not byte-level, "
                  "so a character outside the vocabulary would be dropped without trace. Refusing to load");
    }
    int missing = 0, reachable = 0;
    std::string first;
    for (int b = 0; b < 256; b++) {
      if (b == 0xC0 || b == 0xC1 || b >= 0xF5) continue;  // bytes UTF-8 never contains
      reachable++;
      std::string symbol;
      ud::AppendRune(symbol, TheAlphabet().to_rune[b]);
      if (vocab.find(symbol) == vocab.end()) {
        if (missing == 0) first = symbol;
        missing++;
      }
    }
    if (missing > 0) {
      Refuse("this checkpoint declares no unk_token and no byte_fallback, and " + std::to_string(missing) + " of the " +
             std::to_string(reachable) + " byte-level alphabet symbols that text can reach are absent from its vocabulary "
             "(first: \"" + first + "\"), so some inputs would lose text silently. Refusing to load");
    }
  }

  std::vector<AddedToken> on_raw, on_normalized;
  for (const auto& tok : added) (tok.normalized ? on_normalized : on_raw).push_back(tok);
  impl->raw_added = AddedVocab(on_raw);
  impl->normal_added = AddedVocab(on_normalized);

  // Roles named by tokenizer_config.json.
  if (config != nullptr) {
    static const char* const kRoles[] = {"cls_token", "sep_token", "mask_token", "pad_token", "unk_token"};
    for (const char* key : kRoles) {
      const Value* v = Member(*config, key);
      if (v == nullptr) continue;
      std::string content;
      if (v->kind() == Value::Kind::String) {
        content = v->as_string();
      } else if (v->kind() == Value::Kind::Object && v->Find("content") != nullptr &&
                 v->Find("content")->kind() == Value::Kind::String) {
        content = v->Find("content")->as_string();
      } else {
        Refuse(std::string(key) + " in tokenizer_config.json must be a string or an object with a content field");
      }
      auto it = vocab.find(content);
      if (it == vocab.end()) {
        Refuse("tokenizer_config.json names " + content + " as " + key +
               ", but neither the vocabulary nor the added-token table has it");
      }
      impl->roles[key] = it->second;
      if (std::string(key) == "mask_token") impl->mask_token = content;
    }
  }
  return impl;
}

}  // namespace

Result<Tokenizer> Tokenizer::Parse(std::string_view tokenizer_json, std::optional<std::string_view> config_json) {
  try {
    Value config;
    const Value* cp = nullptr;
    if (config_json.has_value()) {
      auto c = pyvalue::Parse(*config_json);
      if (!c.ok() || c.value().kind() != Value::Kind::Object) {
        return Result<Tokenizer>::Fail("tokenizer_config.json must be a JSON object" + (c.ok() ? std::string() : ": " + c.error()));
      }
      config = std::move(c).value();
      cp = &config;
    }
    return Result<Tokenizer>::Ok(Tokenizer(Build(tokenizer_json, cp)));
  } catch (const Fail& f) {
    return Result<Tokenizer>::Fail(f.msg);
  } catch (const std::bad_alloc&) {
    return Result<Tokenizer>::Fail("out of memory loading the tokenizer");
  }
}

Result<Tokenizer> Tokenizer::LoadDir(const std::string& dir) {
  auto read = [](const std::string& path, std::string* out) {
    std::ifstream in(path, std::ios::binary);
    if (!in) return false;
    std::stringstream ss;
    ss << in.rdbuf();
    *out = ss.str();
    return true;
  };
  std::string where = dir, json, config;
  if (std::ifstream(dir + "/tokenizer/tokenizer.json").good()) where = dir + "/tokenizer";
  if (!read(where + "/tokenizer.json", &json)) return Result<Tokenizer>::Fail("cannot read " + where + "/tokenizer.json");
  bool has_config = read(where + "/tokenizer_config.json", &config);
  return Parse(json, has_config ? std::optional<std::string_view>(config) : std::nullopt);
}

std::vector<int32_t> Tokenizer::Encode(std::string_view text_in, int64_t limit) const {
  std::vector<int32_t> out;
  if (limit == 0) return out;
  const Impl& t = *impl_;
  std::string text = ud::ToValid(text_in);  // a Python str is always valid
  out.reserve(size_t(limit > 0 && limit < int64_t(text.size() / 3 + 16) ? limit : int64_t(text.size() / 3 + 16)));
  auto full = [&]() { return limit >= 0 && int64_t(out.size()) >= limit; };
  auto plain = [&](const std::string& s, bool origin) {
    std::vector<std::string> pieces;
    t.pre->Split(s, pieces, origin);
    for (const auto& piece : pieces) {
      if (full()) return;
      t.bpe->EncodePiece(piece, out);
    }
  };
  for (const Span& sp : t.raw_added.Split(text)) {
    if (full()) break;
    if (sp.is_token) {
      out.push_back(sp.id);
      continue;
    }
    std::string normalized = t.normalizer(sp.text);
    bool origin = sp.offset == 0;  // only the text at the start of the input is "first"
    if (t.normal_added.empty) {
      plain(normalized, origin);
      continue;
    }
    for (const Span& inner : t.normal_added.Split(normalized)) {
      if (full()) break;
      if (inner.is_token) out.push_back(inner.id);
      else plain(inner.text, origin && inner.offset == 0);
    }
  }
  if (limit >= 0 && int64_t(out.size()) > limit) out.resize(size_t(limit));
  return out;
}

std::string Tokenizer::Decode(const std::vector<int32_t>& ids, bool skip_special_tokens) const {
  const Impl& t = *impl_;
  std::vector<std::string> pieces;
  pieces.reserve(ids.size());
  for (int32_t id : ids) {
    if (skip_special_tokens && t.is_special.count(id) != 0) continue;
    if (id < 0 || size_t(id) >= t.tokens.size() || t.tokens[size_t(id)].empty()) continue;
    pieces.push_back(t.tokens[size_t(id)]);
  }
  std::string out;
  if (t.decoder == nullptr) {  // with no decoder section the reference joins tokens with a space
    for (size_t i = 0; i < pieces.size(); i++) out += (i ? " " : "") + pieces[i];
    return out;
  }
  t.decoder->Transform(pieces);
  for (const auto& p : pieces) out += p;
  return out;
}

size_t Tokenizer::VocabSize() const { return impl_->ids.size(); }
int32_t Tokenizer::HighestId() const { return int32_t(impl_->tokens.size()) - 1; }
std::optional<int32_t> Tokenizer::TokenToId(std::string_view token) const {
  auto it = impl_->ids.find(std::string(token));
  if (it == impl_->ids.end()) return std::nullopt;
  return it->second;
}
std::optional<std::string> Tokenizer::IdToToken(int32_t id) const {
  if (id < 0 || size_t(id) >= impl_->tokens.size() || impl_->tokens[size_t(id)].empty()) return std::nullopt;
  return impl_->tokens[size_t(id)];
}
std::optional<int32_t> Tokenizer::SpecialId(std::string_view content) const {
  auto it = impl_->specials.find(std::string(content));
  if (it == impl_->specials.end()) return std::nullopt;
  return it->second;
}
std::map<std::string, int32_t> Tokenizer::SpecialTokens() const { return impl_->specials; }
static std::optional<int32_t> Role(const Impl& i, const char* key) {
  auto it = i.roles.find(key);
  if (it == i.roles.end()) return std::nullopt;
  return it->second;
}
std::optional<int32_t> Tokenizer::Cls() const { return Role(*impl_, "cls_token"); }
std::optional<int32_t> Tokenizer::Sep() const { return Role(*impl_, "sep_token"); }
std::optional<int32_t> Tokenizer::Mask() const { return Role(*impl_, "mask_token"); }
std::optional<int32_t> Tokenizer::Pad() const { return Role(*impl_, "pad_token"); }
std::string Tokenizer::MaskToken() const { return impl_->mask_token; }

size_t Tokenizer::CountMergeDisagreements(std::string_view text, size_t* pieces_checked) const {
  size_t bad = 0;
  std::vector<std::string> pieces;
  impl_->pre->Split(impl_->normalizer(ud::ToValid(text)), pieces, true);
  for (const auto& p : pieces) {
    if (!impl_->bpe->StrategiesAgree(p)) bad++;
    if (pieces_checked != nullptr) (*pieces_checked)++;
  }
  return bad;
}

std::string Tokenizer::NormalizeForTest(std::string_view text) const { return impl_->normalizer(ud::ToValid(text)); }
std::vector<std::string> Tokenizer::PreTokenizeForTest(std::string_view normalized) const {
  std::vector<std::string> out;
  impl_->pre->Split(normalized, out, true);
  return out;
}

std::string Normalize(std::string_view text, Form form) { return NormalizeImpl(text, form); }
std::string Lowercase(std::string_view text) { return LowercaseImpl(text); }

Result<std::string> RunNormalizerSpec(std::string_view spec_json, std::string_view input) {
  try {
    auto v = pyvalue::Parse(spec_json);
    if (!v.ok()) return Result<std::string>::Fail(v.error());
    return Result<std::string>::Ok(ParseNormalizer(&v.value())(std::string(input)));
  } catch (const Fail& f) {
    return Result<std::string>::Fail(f.msg);
  }
}

Result<std::vector<std::string>> RunPreTokenizerSpec(std::string_view spec_json, std::string_view input) {
  try {
    auto v = pyvalue::Parse(spec_json);
    if (!v.ok()) return Result<std::vector<std::string>>::Fail(v.error());
    std::vector<std::string> out;
    ParsePreTokenizer(&v.value())->Split(input, out, true);
    return Result<std::vector<std::string>>::Ok(out);
  } catch (const Fail& f) {
    return Result<std::vector<std::string>>::Fail(f.msg);
  }
}

}  // namespace tokenizer
}  // namespace laya