// A compact serialization of `Language`, for embedding the tables of a
// grammar in MoonBit source (the grammar modules under grammars/ and the
// output of `tree-sitter build`). It has no upstream equivalent: C parsers
// embed the tables as array initializers in parser.c.
//
// Layers, outermost first:
//
// 1. Text (`to_compact_base64`, `from_compact_base64`): standard base64
//    (RFC 4648, with padding) of the container. The decoder ignores ASCII
//    whitespace, so the text may be split over the lines of a multi-line
//    string literal.
// 2. Container (`to_compact`, `from_compact`): the byte `compact_format_version`,
//    the length of the raw stream as an unsigned LEB128 varint, then the raw
//    stream compressed with a byte-oriented LZ77 (`lz_compress`).
// 3. Raw stream: the fields of `Language` in declaration order, as unsigned
//    LEB128 varints (`u`), zigzag-encoded signed varints (`s`) where a value
//    may be negative or is a difference, and the compositions below.
//
// Raw stream compositions:
// - `ints`: `u` length, then `u` per element.
// - `sparse`: `u` length, `u` number of non-zero elements, then per non-zero
//   element `u` (index - previous non-zero index - 1) and `u` value. Used for
//   the mostly-zero row-major tables (`parse_table`, `alias_sequences`).
// - `deltas`: `u` length, then `s` (element - previous element), the first
//   relative to 0 (`small_parse_table_map`, which increases).
// - `index deltas`: `u` length, then `s` (index - element)
//   (`public_symbol_map`, `primary_state_ids`, mostly the identity or close
//   to it).
// - `string`: `u` number of characters, then `u` per character code.
// - `bools`: `u` length, then one byte (0 or 1) per element.
// - `ParseActionEntry`: a tag byte, then: `Entry`: tag 0 (not reusable) or 1
//   (reusable), `u` count; `Shift`: tag 2 + extra + 2 * repetition, `u`
//   state; `Reduce`: tag 6, `u` symbol, `u` child count, `s` dynamic
//   precedence, `u` production id; `Accept`: tag 7; `Recover`: tag 8.
// - `FieldMapEntry`: `u` field id, `u` (child index * 2 + inherited).
// - `MapSlice`: `u` index, `u` length.
// - `SymbolMetadata`: `u` (visible + 2 * named + 4 * supertype).
// - `LexMode`: `u` lex state, `u` external lex state, `u` reserved word set.
// - ranges (a `CharacterRange` list): `u` count, then per range `s` (start -
//   previous range's end, the first relative to 0) and `u` (end - start).
// - `RangeCondition`: `u` (range count * 2 + is_included), then the ranges
//   as above without their count.
// - `LexProgram`: `u` state count; per state `u` flags (1: accept token,
//   2: eof advance), `u` accept token, `u` eof advance state (when
//   present), `u` advance map length and `u` (character, state) per entry,
//   `u` transition count and per transition `u` flags (1: skip, 2: large
//   set, 4: large set guarded by `!eof`, 8: asserted, 16: negated), `u`
//   state, `u` large set index, asserted and negated conditions (when
//   present); then `u` large character set count and the ranges of each.
// - `keyword_lex_fn`: a byte 0 (absent) or 1 followed by the program.
// - `metadata`: `u` major, minor and patch version.

///|
/// The version of the compact format written by `Language::to_compact`.
pub let compact_format_version : Int = 1

///|
/// A malformed or unsupported compact language.
pub(all) suberror CompactError {
  CompactError(String)
} derive(Debug)

///|
pub impl Show for CompactError with fn output(self, logger) {
  let CompactError(message) = self
  logger.write_string("invalid compact language: \{message}")
}

// ---------------------------------------------------------------------------
// Writing

///|
priv struct CompactWriter {
  buf : @buffer.Buffer
}

///|
fn CompactWriter::uint(self : CompactWriter, value : Int) -> Unit raise {
  if value < 0 {
    raise CompactError("negative value \{value} in an unsigned field")
  }
  let mut v = value
  while v >= 0x80 {
    self.buf.write_byte(((v & 0x7f) | 0x80).to_byte())
    v = v >> 7
  }
  self.buf.write_byte(v.to_byte())
}

///|
fn CompactWriter::sint(self : CompactWriter, value : Int) -> Unit {
  // Zigzag, computed in 64 bits so that every Int is representable.
  let v = value.to_int64()
  let mut z = ((v << 1) ^ (v >> 63)).reinterpret_as_uint64()
  while z >= 0x80UL {
    self.buf.write_byte(((z & 0x7fUL) | 0x80UL).to_byte())
    z = z >> 7
  }
  self.buf.write_byte(z.to_byte())
}

///|
fn CompactWriter::byte(self : CompactWriter, value : Int) -> Unit {
  self.buf.write_byte(value.to_byte())
}

///|
fn CompactWriter::bool(self : CompactWriter, value : Bool) -> Unit {
  self.byte(if value { 1 } else { 0 })
}

///|
fn CompactWriter::ints(
  self : CompactWriter,
  values : Array[Int],
) -> Unit raise {
  self.uint(values.length())
  for v in values {
    self.uint(v)
  }
}

///|
fn CompactWriter::sparse(
  self : CompactWriter,
  values : Array[Int],
) -> Unit raise {
  self.uint(values.length())
  let mut nonzero = 0
  for v in values {
    if v != 0 {
      nonzero += 1
    }
  }
  self.uint(nonzero)
  let mut previous = -1
  for i, v in values {
    if v != 0 {
      self.uint(i - previous - 1)
      self.uint(v)
      previous = i
    }
  }
}

///|
fn CompactWriter::deltas(
  self : CompactWriter,
  values : Array[Int],
) -> Unit raise {
  self.uint(values.length())
  let mut previous = 0
  for v in values {
    self.sint(v - previous)
    previous = v
  }
}

///|
fn CompactWriter::index_deltas(
  self : CompactWriter,
  values : Array[Int],
) -> Unit raise {
  self.uint(values.length())
  for i, v in values {
    self.sint(i - v)
  }
}

///|
fn CompactWriter::string(self : CompactWriter, value : String) -> Unit raise {
  let chars = value.to_array()
  self.uint(chars.length())
  for c in chars {
    self.uint(c.to_int())
  }
}

///|
fn CompactWriter::strings(
  self : CompactWriter,
  values : Array[String],
) -> Unit raise {
  self.uint(values.length())
  for v in values {
    self.string(v)
  }
}

///|
fn CompactWriter::bools(
  self : CompactWriter,
  values : Array[Bool],
) -> Unit raise {
  self.uint(values.length())
  for v in values {
    self.bool(v)
  }
}

///|
fn CompactWriter::map_slices(
  self : CompactWriter,
  values : Array[MapSlice],
) -> Unit raise {
  self.uint(values.length())
  for s in values {
    self.uint(s.index)
    self.uint(s.length)
  }
}

///|
fn CompactWriter::range_list(
  self : CompactWriter,
  ranges : Array[CharacterRange],
) -> Unit raise {
  let mut previous = 0
  for r in ranges {
    self.sint(r.start - previous)
    self.uint(r.end - r.start)
    previous = r.end
  }
}

///|
fn CompactWriter::range_condition(
  self : CompactWriter,
  condition : RangeCondition,
) -> Unit raise {
  self.uint(
    condition.ranges.length() * 2 + (if condition.is_included { 1 } else { 0 }),
  )
  self.range_list(condition.ranges)
}

///|
fn CompactWriter::lex_program(
  self : CompactWriter,
  program : LexProgram,
) -> Unit raise {
  self.uint(program.states.length())
  for state in program.states {
    let flags = (if state.accept_token is Some(_) { 1 } else { 0 }) |
      (if state.eof_advance is Some(_) { 2 } else { 0 })
    self.uint(flags)
    if state.accept_token is Some(symbol) {
      self.uint(symbol)
    }
    if state.eof_advance is Some(next) {
      self.uint(next)
    }
    self.uint(state.advance_map.length())
    for entry in state.advance_map {
      self.uint(entry.0)
      self.uint(entry.1)
    }
    self.uint(state.transitions.length())
    for t in state.transitions {
      let c = t.condition
      let flags = (if t.skip { 1 } else { 0 }) |
        (match c.large_set {
          Some((_, true)) => 2 | 4
          Some((_, false)) => 2
          None => 0
        }) |
        (if c.asserted is Some(_) { 8 } else { 0 }) |
        (if c.negated is Some(_) { 16 } else { 0 })
      self.uint(flags)
      self.uint(t.state)
      if c.large_set is Some((index, _)) {
        self.uint(index)
      }
      if c.asserted is Some(condition) {
        self.range_condition(condition)
      }
      if c.negated is Some(condition) {
        self.range_condition(condition)
      }
    }
  }
  self.uint(program.large_character_sets.length())
  for set in program.large_character_sets {
    self.uint(set.length())
    self.range_list(set)
  }
}

///|
fn CompactWriter::parse_action(
  self : CompactWriter,
  entry : ParseActionEntry,
) -> Unit raise {
  match entry {
    Entry(count~, reusable~) => {
      self.byte(if reusable { 1 } else { 0 })
      self.uint(count)
    }
    Shift(state~, extra~, repetition~) => {
      self.byte(
        2 + (if extra { 1 } else { 0 }) + (if repetition { 2 } else { 0 }),
      )
      self.uint(state)
    }
    Reduce(symbol~, child_count~, dynamic_precedence~, production_id~) => {
      self.byte(6)
      self.uint(symbol)
      self.uint(child_count)
      self.sint(dynamic_precedence)
      self.uint(production_id)
    }
    Accept => self.byte(7)
    Recover => self.byte(8)
  }
}

///|
/// The raw stream (layer 3) of a language.
fn write_raw(language : Language) -> Bytes raise {
  let w = CompactWriter::{ buf: @buffer.Buffer(size_hint=1 << 16), }
  let l = language
  w.uint(l.abi_version)
  w.uint(l.symbol_count)
  w.uint(l.alias_count)
  w.uint(l.token_count)
  w.uint(l.external_token_count)
  w.uint(l.state_count)
  w.uint(l.large_state_count)
  w.uint(l.production_id_count)
  w.uint(l.field_count)
  w.uint(l.max_alias_sequence_length)
  w.sparse(l.parse_table)
  w.ints(l.small_parse_table)
  w.deltas(l.small_parse_table_map)
  w.uint(l.parse_actions.length())
  for entry in l.parse_actions {
    w.parse_action(entry)
  }
  w.strings(l.symbol_names)
  w.strings(l.field_names)
  w.map_slices(l.field_map_slices)
  w.uint(l.field_map_entries.length())
  for e in l.field_map_entries {
    w.uint(e.field_id)
    w.uint(e.child_index * 2 + (if e.inherited { 1 } else { 0 }))
  }
  w.uint(l.symbol_metadata.length())
  for m in l.symbol_metadata {
    w.uint(
      (if m.visible { 1 } else { 0 }) |
      (if m.named { 2 } else { 0 }) |
      (if m.supertype { 4 } else { 0 }),
    )
  }
  w.index_deltas(l.public_symbol_map)
  w.ints(l.alias_map)
  w.sparse(l.alias_sequences)
  w.uint(l.lex_modes.length())
  for m in l.lex_modes {
    w.uint(m.lex_state)
    w.uint(m.external_lex_state)
    w.uint(m.reserved_word_set_id)
  }
  w.lex_program(l.lex_fn)
  match l.keyword_lex_fn {
    Some(program) => {
      w.byte(1)
      w.lex_program(program)
    }
    None => w.byte(0)
  }
  w.uint(l.keyword_capture_token)
  w.bools(l.external_scanner.states)
  w.ints(l.external_scanner.symbol_map)
  w.index_deltas(l.primary_state_ids)
  w.string(l.name)
  w.ints(l.reserved_words)
  w.uint(l.max_reserved_word_set_size)
  w.uint(l.supertype_count)
  w.ints(l.supertype_symbols)
  w.map_slices(l.supertype_map_slices)
  w.ints(l.supertype_map_entries)
  w.uint(l.metadata.major_version)
  w.uint(l.metadata.minor_version)
  w.uint(l.metadata.patch_version)
  w.buf.to_bytes()
}

///|
/// Serialize this language in the compact binary format (layer 2: version
/// byte, raw length, LZ77-compressed raw stream). Raises if a field that the
/// format stores unsigned is negative, which a generated language never has.
pub fn Language::to_compact(self : Language) -> Bytes raise CompactError {
  let raw = write_raw(self) catch {
    CompactError(_) as e => raise e
    e => raise CompactError(e.to_string())
  }
  let w = CompactWriter::{ buf: @buffer.Buffer(size_hint=raw.length() / 4), }
  w.byte(compact_format_version)
  w.uint(raw.length()) catch {
    _ => ()
  }
  w.buf.write_bytes(lz_compress(raw))
  w.buf.to_bytes()
}

///|
/// `to_compact` as base64 text (layer 1), on a single line.
pub fn Language::to_compact_base64(
  self : Language,
) -> String raise CompactError {
  base64_encode(self.to_compact())
}

// ---------------------------------------------------------------------------
// Reading

///|
priv struct CompactReader {
  data : FixedArray[Byte]
  mut pos : Int
}

///|
fn CompactReader::byte(self : CompactReader) -> Int raise CompactError {
  if self.pos >= self.data.length() {
    raise CompactError("unexpected end of data")
  }
  let b = self.data[self.pos].to_int()
  self.pos += 1
  b
}

///|
fn CompactReader::uint(self : CompactReader) -> Int raise CompactError {
  let mut result = 0
  let mut shift = 0
  for ;; {
    let b = self.byte()
    if shift > 28 || (shift == 28 && (b & 0x7f) > 7) {
      raise CompactError("varint out of range")
    }
    result = result | ((b & 0x7f) << shift)
    if b < 0x80 {
      break
    }
    shift += 7
  }
  result
}

///|
fn CompactReader::sint(self : CompactReader) -> Int raise CompactError {
  let mut z = 0UL
  let mut shift = 0
  for ;; {
    let b = self.byte()
    if shift > 63 {
      raise CompactError("varint out of range")
    }
    z = z | ((b & 0x7f).to_uint64() << shift)
    if b < 0x80 {
      break
    }
    shift += 7
  }
  let v = (z >> 1).reinterpret_as_int64() ^ -(z & 1UL).reinterpret_as_int64()
  v.to_int()
}

///|
fn CompactReader::bool(self : CompactReader) -> Bool raise CompactError {
  match self.byte() {
    0 => false
    1 => true
    b => raise CompactError("invalid boolean \{b}")
  }
}

///|
/// A length, checked against the remaining data so that corrupt input cannot
/// request a huge allocation: each element takes at least `min_bytes` bytes.
fn CompactReader::length(
  self : CompactReader,
  min_bytes~ : Int = 1,
) -> Int raise CompactError {
  let n = self.uint()
  if min_bytes > 0 && n > (self.data.length() - self.pos) / min_bytes {
    raise CompactError("length \{n} exceeds the data")
  }
  n
}

///|
fn CompactReader::ints(self : CompactReader) -> Array[Int] raise CompactError {
  let n = self.length()
  let result = Array::make(n, 0)
  for i in 0.. Array[Int] raise CompactError {
  // A sparse array may be much longer than its encoding, so its length is
  // bounded by the declared size limit below instead of the data length.
  let n = self.length(min_bytes=0)
  if n > 1 << 28 {
    raise CompactError("sparse array length \{n} is too large")
  }
  let nonzero = self.length(min_bytes=2)
  let result = Array::make(n, 0)
  let mut index = -1
  for _ in 0..= n {
      raise CompactError("sparse index out of range")
    }
    result[index] = self.uint()
  }
  result
}

///|
fn CompactReader::deltas(
  self : CompactReader,
) -> Array[Int] raise CompactError {
  let n = self.length()
  let result = Array::make(n, 0)
  let mut previous = 0
  for i in 0.. Array[Int] raise CompactError {
  let n = self.length()
  let result = Array::make(n, 0)
  for i in 0.. String raise CompactError {
  let n = self.length()
  let sb = StringBuilder(size_hint=n)
  for _ in 0.. 0x10FFFF {
      raise CompactError("invalid character code \{code}")
    }
    sb.write_char(code.unsafe_to_char())
  }
  sb.to_string()
}

///|
fn CompactReader::strings(
  self : CompactReader,
) -> Array[String] raise CompactError {
  let n = self.length()
  Array::makei(n, _ => self.string())
}

///|
fn CompactReader::bools(self : CompactReader) -> Array[Bool] raise CompactError {
  let n = self.length()
  Array::makei(n, _ => self.bool())
}

///|
fn CompactReader::map_slices(
  self : CompactReader,
) -> Array[MapSlice] raise CompactError {
  let n = self.length(min_bytes=2)
  Array::makei(n, _ => {
    let index = self.uint()
    let length = self.uint()
    { index, length, }
  })
}

///|
fn CompactReader::range_list(
  self : CompactReader,
  n : Int,
) -> Array[CharacterRange] raise CompactError {
  let mut previous = 0
  Array::makei(n, _ => {
    let start = previous + self.sint()
    let end = start + self.uint()
    previous = end
    { start, end, }
  })
}

///|
fn CompactReader::range_condition(
  self : CompactReader,
) -> RangeCondition raise CompactError {
  let header = self.uint()
  let n = header >> 1
  if n > (self.data.length() - self.pos) / 2 {
    raise CompactError("length \{n} exceeds the data")
  }
  let ranges = self.range_list(n)
  { ranges, is_included: (header & 1) == 1, }
}

///|
fn CompactReader::lex_program(
  self : CompactReader,
) -> LexProgram raise CompactError {
  let state_count = self.length(min_bytes=3)
  let states = Array::makei(state_count, _ => {
    let flags = self.uint()
    let accept_token = if (flags & 1) != 0 { Some(self.uint()) } else { None }
    let eof_advance = if (flags & 2) != 0 { Some(self.uint()) } else { None }
    let map_length = self.length(min_bytes=2)
    let advance_map = Array::makei(map_length, _ => {
      let c = self.uint()
      let s = self.uint()
      (c, s)
    })
    let transition_count = self.length(min_bytes=2)
    let transitions = Array::makei(transition_count, _ => {
      let flags = self.uint()
      let state = self.uint()
      let large_set = if (flags & 2) != 0 {
        Some((self.uint(), (flags & 4) != 0))
      } else {
        None
      }
      let asserted = if (flags & 8) != 0 {
        Some(self.range_condition())
      } else {
        None
      }
      let negated = if (flags & 16) != 0 {
        Some(self.range_condition())
      } else {
        None
      }
      LexTransition::{
        condition: { large_set, asserted, negated, },
        state,
        skip: (flags & 1) != 0,
      }
    })
    LexStateCode::{ accept_token, eof_advance, advance_map, transitions, }
  })
  let set_count = self.length()
  let large_character_sets = Array::makei(set_count, _ => {
    let n = self.length(min_bytes=2)
    self.range_list(n)
  })
  { states, large_character_sets, }
}

///|
fn CompactReader::parse_action(
  self : CompactReader,
) -> ParseActionEntry raise CompactError {
  match self.byte() {
    tag if tag <= 1 => Entry(count=self.uint(), reusable=tag == 1)
    tag if tag <= 5 =>
      Shift(
        state=self.uint(),
        extra=((tag - 2) & 1) != 0,
        repetition=((tag - 2) & 2) != 0,
      )
    6 => {
      let symbol = self.uint()
      let child_count = self.uint()
      let dynamic_precedence = self.sint()
      let production_id = self.uint()
      Reduce(symbol~, child_count~, dynamic_precedence~, production_id~)
    }
    7 => Accept
    8 => Recover
    tag => raise CompactError("invalid parse action tag \{tag}")
  }
}

///|
fn read_raw(data : FixedArray[Byte]) -> Language raise CompactError {
  let r = CompactReader::{ data, pos: 0, }
  let abi_version = r.uint()
  let symbol_count = r.uint()
  let alias_count = r.uint()
  let token_count = r.uint()
  let external_token_count = r.uint()
  let state_count = r.uint()
  let large_state_count = r.uint()
  let production_id_count = r.uint()
  let field_count = r.uint()
  let max_alias_sequence_length = r.uint()
  let parse_table = r.sparse()
  let small_parse_table = r.ints()
  let small_parse_table_map = r.deltas()
  let action_count = r.length()
  let parse_actions = Array::makei(action_count, _ => r.parse_action())
  let symbol_names = r.strings()
  let field_names = r.strings()
  let field_map_slices = r.map_slices()
  let entry_count = r.length(min_bytes=2)
  let field_map_entries = Array::makei(entry_count, _ => {
    let field_id = r.uint()
    let packed = r.uint()
    FieldMapEntry::{
      field_id,
      child_index: packed >> 1,
      inherited: (packed & 1) == 1,
    }
  })
  let metadata_count = r.length()
  let symbol_metadata = Array::makei(metadata_count, _ => {
    let bits = r.uint()
    SymbolMetadata::{
      visible: (bits & 1) != 0,
      named: (bits & 2) != 0,
      supertype: (bits & 4) != 0,
    }
  })
  let public_symbol_map = r.index_deltas()
  let alias_map = r.ints()
  let alias_sequences = r.sparse()
  let mode_count = r.length(min_bytes=3)
  let lex_modes = Array::makei(mode_count, _ => {
    let lex_state = r.uint()
    let external_lex_state = r.uint()
    let reserved_word_set_id = r.uint()
    LexMode::{ lex_state, external_lex_state, reserved_word_set_id, }
  })
  let lex_fn = r.lex_program()
  let keyword_lex_fn = if r.bool() { Some(r.lex_program()) } else { None }
  let keyword_capture_token = r.uint()
  let states = r.bools()
  let symbol_map = r.ints()
  let primary_state_ids = r.index_deltas()
  let name = r.string()
  let reserved_words = r.ints()
  let max_reserved_word_set_size = r.uint()
  let supertype_count = r.uint()
  let supertype_symbols = r.ints()
  let supertype_map_slices = r.map_slices()
  let supertype_map_entries = r.ints()
  let major_version = r.uint()
  let minor_version = r.uint()
  let patch_version = r.uint()
  if r.pos != data.length() {
    raise CompactError("\{data.length() - r.pos} trailing bytes")
  }
  {
    abi_version,
    symbol_count,
    alias_count,
    token_count,
    external_token_count,
    state_count,
    large_state_count,
    production_id_count,
    field_count,
    max_alias_sequence_length,
    parse_table,
    small_parse_table,
    small_parse_table_map,
    parse_actions,
    symbol_names,
    field_names,
    field_map_slices,
    field_map_entries,
    symbol_metadata,
    public_symbol_map,
    alias_map,
    alias_sequences,
    lex_modes,
    lex_fn,
    keyword_lex_fn,
    keyword_capture_token,
    external_scanner: { states, symbol_map, },
    primary_state_ids,
    name,
    reserved_words,
    max_reserved_word_set_size,
    supertype_count,
    supertype_symbols,
    supertype_map_slices,
    supertype_map_entries,
    metadata: { major_version, minor_version, patch_version, },
  }
}

///|
/// Decode a language serialized by `Language::to_compact`.
pub fn Language::from_compact(data : BytesView) -> Language raise CompactError {
  let header = CompactReader::{
    data: FixedArray::from_iter(data.iter()),
    pos: 0,
  }
  read_container(header)
}

///|
fn read_container(header : CompactReader) -> Language raise CompactError {
  let version = header.byte()
  if version != compact_format_version {
    raise CompactError("unsupported format version \{version}")
  }
  let raw_length = header.uint()
  if raw_length > 1 << 30 {
    raise CompactError("raw length \{raw_length} is too large")
  }
  read_raw(lz_decompress(header.data, header.pos, raw_length))
}

///|
/// Decode the base64 text written by `Language::to_compact_base64`; ASCII
/// whitespace (for example the line breaks of a multi-line string literal) is
/// ignored.
pub fn Language::from_compact_base64(
  text : StringView,
) -> Language raise CompactError {
  read_container(CompactReader::{ data: base64_decode(text), pos: 0, })
}