// Port of tree-sitter lib/src/subtree.h and lib/src/subtree.c.
//
// C distinguishes small leaves stored inline in the `Subtree` word from
// heap-allocated subtrees. The distinction is observable (e.g. `.ptr`
// equality, which fields are stored, when `make_mut` copies), so it is kept:
// `Inline` holds a value, `Heap` a shared mutable record with an explicit
// reference count maintained exactly as upstream's retain/release calls do.

///|
let ts_tree_state_none : Int32 = 65535

///|
let ts_max_inline_tree_length : UInt32 = 255

///|
#valtype
pub(all) struct SubtreeInlineData {
  visible : Bool
  named : Bool
  extra : Bool
  has_changes : Bool
  is_missing : Bool
  is_keyword : Bool
  depends_on_column : Bool
  symbol : Int32
  parse_state : Int32
  padding_columns : UInt32
  padding_rows : UInt32
  lookahead_bytes : UInt32
  padding_bytes : UInt32
  size_bytes : UInt32
} derive(Eq, Debug)

///|
pub(all) struct SubtreeHeapData {
  mut ref_count : Int32
  mut padding : Length
  mut size : Length
  mut lookahead_bytes : UInt32
  mut error_cost : UInt32
  /// The children; `child_count` is its length. Leaves have none.
  mut children : Array[Subtree]
  mut symbol : Int32
  mut parse_state : Int32
  mut visible : Bool
  mut named : Bool
  mut extra : Bool
  mut fragile_left : Bool
  mut fragile_right : Bool
  mut has_changes : Bool
  mut has_external_tokens : Bool
  mut has_external_scanner_state_change : Bool
  mut depends_on_column : Bool
  mut is_missing : Bool
  mut is_keyword : Bool
  // Non-terminal subtrees (`child_count > 0`).
  mut visible_child_count : UInt32
  mut named_child_count : UInt32
  mut visible_descendant_count : UInt32
  mut dynamic_precedence : Int32
  mut repeat_depth : UInt32
  mut production_id : Int32
  mut first_leaf_symbol : Int32
  mut first_leaf_parse_state : Int32
  // External terminal subtrees (`child_count == 0 && has_external_tokens`).
  mut external_scanner_state : Bytes
  // Error terminal subtrees (`child_count == 0 && symbol == error`).
  mut lookahead_char : Int32
  /// Stands in for the C heap address: a unique, stable identity.
  address : Int32
}

///|
/// The fundamental building block of a syntax tree. `Null` is `NULL_SUBTREE`.
pub(all) enum Subtree {
  Null
  Inline(SubtreeInlineData)
  Heap(SubtreeHeapData)
}

///|
/// `MutableSubtree` has the same representation.
pub type MutableSubtree = Subtree

///|
let next_address : Ref[Int32] = Ref(1)

///|
fn fresh_address() -> Int32 {
  let address = next_address.val
  next_address.val += 1
  address
}

///|
/// The children of every leaf. Leaves never gain children in place (a node
/// is always created with its own array), so one empty array is shared
/// instead of allocating one per leaf.
let empty_children : Array[Subtree] = []

///|
fn SubtreeHeapData::empty() -> SubtreeHeapData {
  {
    ref_count: 1,
    padding: length_zero(),
    size: length_zero(),
    lookahead_bytes: 0,
    error_cost: 0,
    children: empty_children,
    symbol: 0,
    parse_state: 0,
    visible: false,
    named: false,
    extra: false,
    fragile_left: false,
    fragile_right: false,
    has_changes: false,
    has_external_tokens: false,
    has_external_scanner_state_change: false,
    depends_on_column: false,
    is_missing: false,
    is_keyword: false,
    visible_child_count: 0,
    named_child_count: 0,
    visible_descendant_count: 0,
    dynamic_precedence: 0,
    repeat_depth: 0,
    production_id: 0,
    first_leaf_symbol: 0,
    first_leaf_parse_state: 0,
    external_scanner_state: b"",
    lookahead_char: 0,
    address: fresh_address(),
  }
}

///|
/// `self.ptr` for a heap subtree. Aborts for inline/null subtrees, which C
/// would dereference as an invalid pointer.
pub fn Subtree::ptr(self : Subtree) -> SubtreeHeapData {
  match self {
    Heap(data) => data
    _ => abort("subtree is not heap allocated")
  }
}

///|
pub fn Subtree::is_inline(self : Subtree) -> Bool {
  self is Inline(_)
}

///|
pub fn Subtree::is_null(self : Subtree) -> Bool {
  self is Null
}

///|
/// `a.ptr == b.ptr`: identity for heap subtrees, bitwise equality for inline
/// subtrees (whose data occupies the pointer word).
pub fn Subtree::ptr_eq(self : Subtree, other : Subtree) -> Bool {
  match (self, other) {
    (Null, Null) => true
    (Inline(a), Inline(b)) => a == b
    (Heap(a), Heap(b)) => physical_equal(a, b)
    _ => false
  }
}

///|
/// A stable identity standing in for the pointer value (`ts_node_id`).
pub fn Subtree::address(self : Subtree) -> Int32 {
  match self {
    Null => 0
    Inline(_) => -1
    Heap(data) => data.address
  }
}

///|
pub fn Subtree::symbol(self : Subtree) -> Int32 {
  match self {
    Inline(d) => d.symbol
    Heap(d) => d.symbol
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::visible(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.visible
    Heap(d) => d.visible
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::named(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.named
    Heap(d) => d.named
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::extra(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.extra
    Heap(d) => d.extra
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::has_changes(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.has_changes
    Heap(d) => d.has_changes
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::missing(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.is_missing
    Heap(d) => d.is_missing
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::is_keyword(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.is_keyword
    Heap(d) => d.is_keyword
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::parse_state(self : Subtree) -> Int32 {
  match self {
    Inline(d) => d.parse_state
    Heap(d) => d.parse_state
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::lookahead_bytes(self : Subtree) -> UInt32 {
  match self {
    Inline(d) => d.lookahead_bytes
    Heap(d) => d.lookahead_bytes
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::children(self : Subtree) -> Array[Subtree] {
  match self {
    Heap(d) => d.children
    _ => empty_children
  }
}

///|
/// `ts_subtree_set_extra`.
pub fn Subtree::set_extra(self : Subtree, is_extra : Bool) -> Subtree {
  match self {
    Inline(d) => Inline({ ..d, extra: is_extra, })
    Heap(d) => {
      d.extra = is_extra
      self
    }
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::leaf_symbol(self : Subtree) -> Int32 {
  match self {
    Inline(d) => d.symbol
    Heap(d) =>
      if d.children.is_empty() {
        d.symbol
      } else {
        d.first_leaf_symbol
      }
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::leaf_parse_state(self : Subtree) -> Int32 {
  match self {
    Inline(d) => d.parse_state
    Heap(d) =>
      if d.children.is_empty() {
        d.parse_state
      } else {
        d.first_leaf_parse_state
      }
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::padding(self : Subtree) -> Length {
  match self {
    Inline(d) =>
      {
        bytes: d.padding_bytes,
        extent: { row: d.padding_rows, column: d.padding_columns, },
      }
    Heap(d) => d.padding
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::size(self : Subtree) -> Length {
  match self {
    Inline(d) =>
      { bytes: d.size_bytes, extent: { row: 0, column: d.size_bytes, }, }
    Heap(d) => d.size
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::total_size(self : Subtree) -> Length {
  length_add(self.padding(), self.size())
}

///|
pub fn Subtree::total_bytes(self : Subtree) -> UInt32 {
  self.total_size().bytes
}

///|
pub fn Subtree::child_count(self : Subtree) -> Int32 {
  match self {
    Heap(d) => d.children.length()
    _ => 0
  }
}

///|
/// The `repeat_depth` of an external leaf whose scanner state is `state`.
///
/// Upstream stores the state in a union with the fields of non-terminals:
/// `short_data[24]` (states of at most 24 bytes; longer ones are on the
/// heap) overlaps `repeat_depth`, a `uint16_t` at offset 16, and
/// `ts_subtree_repeat_depth` reads it for leaves too. `ts_subtree_new_leaf`
/// zeroes the union and `ts_external_scanner_state_init` copies the state
/// into it, so bytes 16 and 17 of a short state (little-endian, as on the
/// supported hosts) become the leaf's repeat depth.
fn external_scanner_state_repeat_depth(state : Bytes) -> UInt32 {
  let length = state.length()
  if length > 24 || length <= 16 {
    return 0
  }
  let low = state[16].to_uint()
  let high = if length > 17 { state[17].to_uint() } else { 0 }
  low | (high << 8)
}

///|
pub fn Subtree::repeat_depth(self : Subtree) -> UInt32 {
  match self {
    Heap(d) => d.repeat_depth
    _ => 0
  }
}

///|
pub fn Subtree::is_repetition(self : Subtree) -> Bool {
  match self {
    Heap(d) => !d.named && !d.visible && !d.children.is_empty()
    _ => false
  }
}

///|
pub fn Subtree::visible_descendant_count(self : Subtree) -> UInt32 {
  match self {
    Heap(d) if !d.children.is_empty() => d.visible_descendant_count
    _ => 0
  }
}

///|
pub fn Subtree::visible_child_count(self : Subtree) -> UInt32 {
  if self.child_count() > 0 {
    self.ptr().visible_child_count
  } else {
    0
  }
}

///|
pub fn Subtree::error_cost(self : Subtree) -> UInt32 {
  if self.missing() {
    error_cost_per_missing_tree + error_cost_per_recovery
  } else {
    match self {
      Heap(d) => d.error_cost
      _ => 0
    }
  }
}

///|
pub fn Subtree::dynamic_precedence(self : Subtree) -> Int32 {
  match self {
    Heap(d) if !d.children.is_empty() => d.dynamic_precedence
    _ => 0
  }
}

///|
pub fn Subtree::production_id(self : Subtree) -> Int32 {
  if self.child_count() > 0 {
    self.ptr().production_id
  } else {
    0
  }
}

///|
pub fn Subtree::fragile_left(self : Subtree) -> Bool {
  match self {
    Heap(d) => d.fragile_left
    _ => false
  }
}

///|
pub fn Subtree::fragile_right(self : Subtree) -> Bool {
  match self {
    Heap(d) => d.fragile_right
    _ => false
  }
}

///|
pub fn Subtree::has_external_tokens(self : Subtree) -> Bool {
  match self {
    Heap(d) => d.has_external_tokens
    _ => false
  }
}

///|
pub fn Subtree::has_external_scanner_state_change(self : Subtree) -> Bool {
  match self {
    Heap(d) => d.has_external_scanner_state_change
    _ => false
  }
}

///|
pub fn Subtree::depends_on_column(self : Subtree) -> Bool {
  match self {
    Inline(d) => d.depends_on_column
    Heap(d) => d.depends_on_column
    Null => abort("null subtree")
  }
}

///|
pub fn Subtree::is_fragile(self : Subtree) -> Bool {
  match self {
    Heap(d) => d.fragile_left || d.fragile_right
    _ => false
  }
}

///|
pub fn Subtree::is_error(self : Subtree) -> Bool {
  self.symbol() == @language.ts_builtin_sym_error
}

///|
pub fn Subtree::is_eof(self : Subtree) -> Bool {
  self.symbol() == @language.ts_builtin_sym_end
}

// ExternalScannerState: stored as `Bytes`; upstream's short/long storage is
// an allocation detail.

///|
/// `ts_external_scanner_state_eq`.
pub fn external_scanner_state_eq(state : Bytes, buffer : BytesView) -> Bool {
  state.length() == buffer.length() && state[:] == buffer
}

// SubtreeArray

///|
/// `ts_subtree_array_copy`.
pub fn subtree_array_copy(array : Array[Subtree]) -> Array[Subtree] {
  let dest = array.copy()
  for child in dest {
    child.retain()
  }
  dest
}

///|
/// `ts_subtree_array_clear`.
pub fn subtree_array_clear(array : Array[Subtree]) -> Unit {
  for child in array {
    child.release()
  }
  array.clear()
}

///|
/// `ts_subtree_array_delete`.
pub fn subtree_array_delete(array : Array[Subtree]) -> Unit {
  subtree_array_clear(array)
}

///|
/// `ts_subtree_array_remove_trailing_extras`.
pub fn subtree_array_remove_trailing_extras(
  array : Array[Subtree],
  destination : Array[Subtree],
) -> Unit {
  destination.clear()
  while array.length() > 0 {
    let last = array[array.length() - 1]
    if last.extra() {
      ignore(array.pop())
      destination.push(last)
    } else {
      break
    }
  }
  destination.rev_in_place()
}

///|
/// `ts_subtree_array_reverse`.
pub fn subtree_array_reverse(array : Array[Subtree]) -> Unit {
  array.rev_in_place()
}

// Subtree

///|
fn subtree_can_inline(
  padding : Length,
  size : Length,
  lookahead_bytes : UInt32,
) -> Bool {
  padding.bytes < ts_max_inline_tree_length &&
  padding.extent.row < 16 &&
  padding.extent.column < ts_max_inline_tree_length &&
  size.bytes < ts_max_inline_tree_length &&
  size.extent.row == 0 &&
  size.extent.column < ts_max_inline_tree_length &&
  lookahead_bytes < 16
}

///|
/// `ts_subtree_new_leaf`.
pub fn Subtree::new_leaf(
  symbol : Int32,
  padding : Length,
  size : Length,
  lookahead_bytes : UInt32,
  parse_state : Int32,
  has_external_tokens : Bool,
  depends_on_column : Bool,
  is_keyword : Bool,
  language : @language.Language,
) -> Subtree {
  let metadata = language.symbol_metadata_of(symbol)
  let extra = symbol == @language.ts_builtin_sym_end
  let is_inline = symbol <= 255 &&
    !has_external_tokens &&
    subtree_can_inline(padding, size, lookahead_bytes)
  if is_inline {
    Inline({
      parse_state,
      symbol,
      padding_bytes: padding.bytes,
      padding_rows: padding.extent.row,
      padding_columns: padding.extent.column,
      size_bytes: size.bytes,
      lookahead_bytes,
      visible: metadata.visible,
      named: metadata.named,
      extra,
      has_changes: false,
      is_missing: false,
      is_keyword,
      depends_on_column,
    })
  } else {
    let data = SubtreeHeapData::empty()
    data.padding = padding
    data.size = size
    data.lookahead_bytes = lookahead_bytes
    data.symbol = symbol
    data.parse_state = parse_state
    data.visible = metadata.visible
    data.named = metadata.named
    data.extra = extra
    data.has_external_tokens = has_external_tokens
    data.depends_on_column = depends_on_column
    data.is_keyword = is_keyword
    Heap(data)
  }
}

///|
/// `ts_subtree_set_symbol`.
pub fn Subtree::set_symbol(
  self : Subtree,
  symbol : Int32,
  language : @language.Language,
) -> Subtree {
  let metadata = language.symbol_metadata_of(symbol)
  match self {
    Inline(d) =>
      Inline({ ..d, symbol, named: metadata.named, visible: metadata.visible, })
    Heap(d) => {
      d.symbol = symbol
      d.named = metadata.named
      d.visible = metadata.visible
      self
    }
    Null => abort("null subtree")
  }
}

///|
/// `ts_subtree_new_error`.
pub fn Subtree::new_error(
  lookahead_char : Int32,
  padding : Length,
  size : Length,
  bytes_scanned : UInt32,
  parse_state : Int32,
  language : @language.Language,
) -> Subtree {
  let result = Subtree::new_leaf(
    @language.ts_builtin_sym_error, padding, size, bytes_scanned, parse_state, false,
    false, false, language,
  )
  let data = result.ptr()
  data.fragile_left = true
  data.fragile_right = true
  data.lookahead_char = lookahead_char
  result
}

///|
/// `ts_subtree_clone`.
pub fn Subtree::clone(self : Subtree) -> Subtree {
  let d = self.ptr()
  let result : SubtreeHeapData = { ..d, address: fresh_address(), }
  result.children = d.children.copy()
  if !d.children.is_empty() {
    for child in result.children {
      child.retain()
    }
  }
  result.ref_count = 1
  Heap(result)
}

///|
/// `ts_subtree_make_mut`: take ownership of the subtree. If it has only one
/// owner it is converted directly; otherwise it is copied.
pub fn Subtree::make_mut(self : Subtree) -> Subtree {
  match self {
    Inline(_) => self
    Heap(d) if d.ref_count == 1 => self
    _ => {
      let result = self.clone()
      self.release()
      result
    }
  }
}

///|
/// `ts_subtree_compress`.
pub fn Subtree::compress(
  self : Subtree,
  count : Int32,
  language : @language.Language,
  stack : Array[Subtree],
) -> Unit {
  let initial_stack_size = stack.length()
  let mut tree = self
  let symbol = tree.ptr().symbol
  for _ in 0.. 1 || t.children.length() < 2 {
      break
    }
    let child = t.children[0]
    guard child is Heap(c) &&
      c.children.length() >= 2 &&
      c.ref_count <= 1 &&
      c.symbol == symbol else {
      break
    }
    let grandchild = c.children[0]
    guard grandchild is Heap(g) &&
      g.children.length() >= 2 &&
      g.ref_count <= 1 &&
      g.symbol == symbol else {
      break
    }
    t.children[0] = grandchild
    c.children[0] = g.children[g.children.length() - 1]
    g.children[g.children.length() - 1] = child
    stack.push(tree)
    tree = grandchild
  }
  while stack.length() > initial_stack_size {
    tree = stack.pop().unwrap()
    let child = tree.ptr().children[0]
    let c = child.ptr()
    let grandchild = c.children[c.children.length() - 1]
    grandchild.summarize_children(language)
    child.summarize_children(language)
    tree.summarize_children(language)
  }
}

///|
/// The part of an error node's cost that penalizes the extent it spans, as
/// opposed to the cost of its contents.
fn subtree_error_extent_cost(size : Length) -> UInt32 {
  error_cost_per_recovery +
  error_cost_per_skipped_char * size.bytes +
  error_cost_per_skipped_line * size.extent.row
}

///|
/// `ts_subtree_summarize_children`: assign all of the node's properties that
/// depend on its children.
pub fn Subtree::summarize_children(
  self : Subtree,
  language : @language.Language,
) -> Unit {
  let s = self.ptr()
  s.named_child_count = 0
  s.visible_child_count = 0
  s.error_cost = 0
  s.repeat_depth = 0
  s.visible_descendant_count = 0
  s.has_external_tokens = false
  s.depends_on_column = false
  s.has_external_scanner_state_change = false
  s.dynamic_precedence = 0
  let mut structural_index = 0
  let alias_sequence = language.alias_sequence(s.production_id)
  let mut lookahead_end_byte : UInt32 = 0
  let children = s.children
  for i, child in children {
    if (i == 0 || s.size.extent.row == 0) && child.depends_on_column() {
      s.depends_on_column = true
    }
    if child.has_external_scanner_state_change() {
      s.has_external_scanner_state_change = true
    }
    if i == 0 {
      s.padding = child.padding()
      s.size = child.size()
    } else {
      s.size = length_add(s.size, child.total_size())
    }
    let child_lookahead_end_byte = s.padding.bytes +
      s.size.bytes +
      child.lookahead_bytes()
    if child_lookahead_end_byte > lookahead_end_byte {
      lookahead_end_byte = child_lookahead_end_byte
    }
    let grandchild_count = child.child_count()
    if child.symbol() == @language.ts_builtin_sym_error_repeat {
      // Refund an `_ERROR` child's extent penalty, which this node re-charges
      // as part of its own extent below, so that the grouping is cost-neutral.
      let extent_cost = subtree_error_extent_cost(child.size())
      s.error_cost += child.error_cost() - extent_cost
    } else {
      s.error_cost += child.error_cost()
      if s.symbol == @language.ts_builtin_sym_error ||
        s.symbol == @language.ts_builtin_sym_error_repeat {
        if !child.extra() && !(child.is_error() && grandchild_count == 0) {
          if child.visible() {
            s.error_cost += error_cost_per_skipped_tree
          } else if grandchild_count > 0 {
            s.error_cost += error_cost_per_skipped_tree *
              child.ptr().visible_child_count
          }
        }
      }
    }
    s.dynamic_precedence += child.dynamic_precedence()
    s.visible_descendant_count += child.visible_descendant_count()
    if !child.extra() &&
      child.symbol() != 0 &&
      alias_sequence is Some(offset) &&
      language.alias_sequence_value(offset + structural_index) != 0 {
      s.visible_descendant_count += 1
      s.visible_child_count += 1
      if language.symbol_metadata_of(
          language.alias_sequence_value(offset + structural_index),
        ).named {
        s.named_child_count += 1
      }
    } else if child.visible() {
      s.visible_descendant_count += 1
      s.visible_child_count += 1
      if child.named() {
        s.named_child_count += 1
      }
    } else if grandchild_count > 0 {
      s.visible_child_count += child.ptr().visible_child_count
      s.named_child_count += child.ptr().named_child_count
    }
    if child.has_external_tokens() {
      s.has_external_tokens = true
    }
    if child.is_error() {
      s.fragile_left = true
      s.fragile_right = true
      s.parse_state = ts_tree_state_none
    }
    if !child.extra() {
      structural_index += 1
    }
  }
  s.lookahead_bytes = lookahead_end_byte - s.size.bytes - s.padding.bytes
  if s.symbol == @language.ts_builtin_sym_error ||
    s.symbol == @language.ts_builtin_sym_error_repeat {
    s.error_cost += subtree_error_extent_cost(s.size)
  }
  if children.length() > 0 {
    let first_child = children[0]
    let last_child = children[children.length() - 1]
    s.first_leaf_symbol = first_child.leaf_symbol()
    s.first_leaf_parse_state = first_child.leaf_parse_state()
    if first_child.fragile_left() {
      s.fragile_left = true
    }
    if last_child.fragile_right() {
      s.fragile_right = true
    }
    if children.length() >= 2 &&
      !s.visible &&
      !s.named &&
      first_child.symbol() == s.symbol {
      // `repeat_depth` is a `uint16_t` upstream.
      if first_child.repeat_depth() > last_child.repeat_depth() {
        s.repeat_depth = (first_child.repeat_depth() + 1) & 0xFFFFU
      } else {
        s.repeat_depth = (last_child.repeat_depth() + 1) & 0xFFFFU
      }
    }
  }
}

///|
/// `ts_subtree_new_node`: create a new parent node with the given children.
/// This takes ownership of the children array.
pub fn Subtree::new_node(
  symbol : Int32,
  children : Array[Subtree],
  production_id : Int32,
  language : @language.Language,
) -> Subtree {
  let metadata = language.symbol_metadata_of(symbol)
  let fragile = symbol == @language.ts_builtin_sym_error ||
    symbol == @language.ts_builtin_sym_error_repeat
  let data = SubtreeHeapData::empty()
  data.symbol = symbol
  data.children = children
  data.visible = metadata.visible
  data.named = metadata.named
  data.fragile_left = fragile
  data.fragile_right = fragile
  data.production_id = production_id
  let result = Heap(data)
  result.summarize_children(language)
  result
}

///|
/// `ts_subtree_new_error_node`: this node is treated as 'extra'. Its children
/// are prevented from having any effect on the parse state.
pub fn Subtree::new_error_node(
  children : Array[Subtree],
  extra : Bool,
  language : @language.Language,
) -> Subtree {
  let result = Subtree::new_node(
    @language.ts_builtin_sym_error, children, 0, language,
  )
  result.ptr().extra = extra
  result
}

///|
/// `ts_subtree_new_missing_leaf`.
pub fn Subtree::new_missing_leaf(
  symbol : Int32,
  state : Int32,
  padding : Length,
  lookahead_bytes : UInt32,
  language : @language.Language,
) -> Subtree {
  let result = Subtree::new_leaf(
    symbol,
    padding,
    length_zero(),
    lookahead_bytes,
    state,
    false,
    false,
    false,
    language,
  )
  match result {
    Inline(d) => Inline({ ..d, is_missing: true, })
    Heap(d) => {
      d.is_missing = true
      result
    }
    Null => result
  }
}

///|
/// `ts_subtree_retain`.
pub fn Subtree::retain(self : Subtree) -> Unit {
  match self {
    Heap(d) => d.ref_count += 1
    _ => ()
  }
}

///|
/// `pool->tree_stack` of `ts_subtree_release`: scratch space that is always
/// empty between calls.
let release_stack : Array[SubtreeHeapData] = []

///|
/// `ts_subtree_release`. Memory is reclaimed by the GC; the counts are kept
/// so that `make_mut` and `compress` copy exactly when upstream does.
pub fn Subtree::release(self : Subtree) -> Unit {
  guard self is Heap(d) else { return }
  d.ref_count -= 1
  if d.ref_count != 0 {
    return
  }
  let stack = release_stack
  stack.push(d)
  while stack.pop() is Some(tree) {
    for child in tree.children {
      if child is Heap(c) {
        c.ref_count -= 1
        if c.ref_count == 0 {
          stack.push(c)
        }
      }
    }
  }
}

///|
/// `ts_subtree_compare`.
pub fn Subtree::compare_to(left : Subtree, right : Subtree) -> Int32 {
  let stack = [left, right]
  while stack.length() > 0 {
    let right = stack.pop().unwrap()
    let left = stack.pop().unwrap()
    let mut result = 0
    if left.symbol() < right.symbol() {
      result = -1
    } else if right.symbol() < left.symbol() {
      result = 1
    } else if left.child_count() < right.child_count() {
      result = -1
    } else if right.child_count() < left.child_count() {
      result = 1
    }
    if result != 0 {
      return result
    }
    for i = left.child_count(); i > 0; i = i - 1 {
      stack.push(left.children()[i - 1])
      stack.push(right.children()[i - 1])
    }
  }
  0
}

///|
fn Subtree::set_has_changes(self : Subtree) -> Subtree {
  match self {
    Inline(d) => Inline({ ..d, has_changes: true, })
    Heap(d) => {
      d.has_changes = true
      self
    }
    Null => self
  }
}

///|
priv struct Edit {
  start : Length
  old_end : Length
  new_end : Length
}

///|
/// `ts_subtree_edit`.
pub fn Subtree::edit(self : Subtree, input_edit : InputEdit) -> Subtree {
  let root = [self]
  let stack : Array[(SubtreeSlot, Edit)] = [
    (
      { array: root, index: 0, owner: 0, },
      {
        start: { bytes: input_edit.start_byte, extent: input_edit.start_point, },
        old_end: {
          bytes: input_edit.old_end_byte,
          extent: input_edit.old_end_point,
        },
        new_end: {
          bytes: input_edit.new_end_byte,
          extent: input_edit.new_end_point,
        },
      },
    ),
  ]
  while stack.pop() is Some((slot, edit0)) {
    let mut edit = edit0
    let tree = slot.array[slot.index]
    let is_noop = edit.old_end.bytes == edit.start.bytes &&
      edit.new_end.bytes == edit.start.bytes
    let is_pure_insertion = edit.old_end.bytes == edit.start.bytes
    let parent_depends_on_column = tree.depends_on_column()
    let column_shifted = edit.new_end.extent.column !=
      edit.old_end.extent.column
    let mut size = tree.size()
    let mut padding = tree.padding()
    let total_size = length_add(padding, size)
    let lookahead_bytes = tree.lookahead_bytes()
    let end_byte = total_size.bytes + lookahead_bytes
    if edit.start.bytes > end_byte || (is_noop && edit.start.bytes == end_byte) {
      continue
    }
    if edit.old_end.bytes <= padding.bytes {
      // If the edit is entirely within the space before this subtree, then
      // shift this subtree over according to the edit without changing its size.
      padding = length_add(edit.new_end, length_sub(padding, edit.old_end))
    } else if edit.start.bytes < padding.bytes {
      // If the edit starts in the space before this subtree and extends into
      // this subtree, shrink the subtree's content to compensate for the
      // change in the space before it.
      size = length_saturating_sub(size, length_sub(edit.old_end, padding))
      padding = edit.new_end
    } else if edit.start.bytes < total_size.bytes ||
      (edit.start.bytes == total_size.bytes && is_pure_insertion) {
      // If the edit is within this subtree, resize the subtree to reflect the edit.
      size = length_add(
        length_sub(edit.new_end, padding),
        length_saturating_sub(total_size, edit.old_end),
      )
    }
    let mut result = tree.make_mut()
    match result {
      Inline(d) =>
        if subtree_can_inline(padding, size, lookahead_bytes) {
          result = Inline({
            ..d,
            padding_bytes: padding.bytes,
            padding_rows: padding.extent.row,
            padding_columns: padding.extent.column,
            size_bytes: size.bytes,
          })
        } else {
          let data = SubtreeHeapData::empty()
          data.padding = padding
          data.size = size
          data.lookahead_bytes = lookahead_bytes
          data.symbol = d.symbol
          data.parse_state = d.parse_state
          data.visible = d.visible
          data.named = d.named
          data.extra = d.extra
          data.depends_on_column = d.depends_on_column
          data.is_missing = d.is_missing
          data.is_keyword = d.is_keyword
          result = Heap(data)
        }
      Heap(d) => {
        d.padding = padding
        d.size = size
      }
      Null => ()
    }
    result = result.set_has_changes()
    slot.array[slot.index] = result
    let mut child_left = length_zero()
    let mut child_right = length_zero()
    let children = result.children()
    for i in 0.. edit.old_end.bytes ||
          (
            child_left.bytes == edit.old_end.bytes &&
            child_size.bytes > 0 &&
            i > 0
          )
        ) &&
        (
          !parent_depends_on_column ||
          child_left.extent.row > padding.extent.row
        ) &&
        (
          !child.depends_on_column() ||
          !column_shifted ||
          child_left.extent.row > edit.old_end.extent.row
        ) {
        break
      }
      // Transform edit into the child's coordinate space.
      let mut child_edit : Edit = {
        start: length_saturating_sub(edit.start, child_left),
        old_end: length_saturating_sub(edit.old_end, child_left),
        new_end: length_saturating_sub(edit.new_end, child_left),
      }
      // Interpret all inserted text as applying to the *first* child that
      // touches the edit. Subsequent children never have any text inserted
      // into them; they are only shrunk to compensate for the edit.
      if child_right.bytes > edit.start.bytes ||
        (child_right.bytes == edit.start.bytes && is_pure_insertion) {
        edit = { ..edit, new_end: edit.start, }
      } else {
        // Children that occur before the edit are not reshaped by the edit.
        child_edit = {
          ..child_edit,
          old_end: child_edit.start,
          new_end: child_edit.start,
        }
      }
      // Queue processing of this child's subtree.
      stack.push(({ array: children, index: i, owner: 0, }, child_edit))
    }
  }
  root[0]
}

///|
/// `ts_subtree_last_external_token`.
pub fn Subtree::last_external_token(self : Subtree) -> Subtree {
  if !self.has_external_tokens() {
    return Null
  }
  let mut tree = self
  while tree.ptr().children.length() > 0 {
    let children = tree.ptr().children
    for i = children.length() - 1; i >= 0; i = i - 1 {
      let child = children[i]
      if child.has_external_tokens() {
        tree = child
        break
      }
    }
  }
  tree
}

///|
/// `ts_subtree_external_scanner_state`.
pub fn Subtree::external_scanner_state(self : Subtree) -> Bytes {
  match self {
    Heap(d) if d.has_external_tokens && d.children.is_empty() =>
      d.external_scanner_state
    _ => b""
  }
}

///|
/// `ts_subtree_external_scanner_state_eq`.
pub fn Subtree::external_scanner_state_eq(
  self : Subtree,
  other : Subtree,
) -> Bool {
  external_scanner_state_eq(
    self.external_scanner_state(),
    other.external_scanner_state(),
  )
}