// Port of tree-sitter lib/src/tree_cursor.h and lib/src/tree_cursor.c.

///|
pub(all) struct TreeCursorEntry {
  subtree : SubtreeSlot
  position : Length
  child_index : Int32
  structural_child_index : Int32
  descendant_index : UInt32
}

///|
pub struct TreeCursor {
  priv mut tree : Tree?
  priv mut stack : Array[TreeCursorEntry]
  priv mut root_alias_symbol : Int32
}

///|
pub(all) enum TreeCursorStep {
  StepNone
  StepHidden
  StepVisible
} derive(Eq, Debug)

///|
priv struct CursorChildIterator {
  parent : Subtree
  tree : Tree?
  mut position : Length
  mut child_index : Int32
  mut structural_child_index : Int32
  mut descendant_index : UInt32
  alias_sequence : Int32?
}

///|
fn TreeCursor::language(self : TreeCursor) -> @language.Language {
  self.tree.unwrap().language
}

///|
fn TreeCursor::is_entry_visible(self : TreeCursor, index : Int32) -> Bool {
  let entry = self.stack[index]
  let subtree = entry.subtree.get()
  if index == 0 || subtree.visible() {
    true
  } else if !subtree.extra() {
    let parent_entry = self.stack[index - 1]
    self
    .language()
    .alias_at(
      parent_entry.subtree.get().ptr().production_id,
      entry.structural_child_index,
    ) !=
    0
  } else {
    false
  }
}

///|
fn TreeCursor::iterate_children(self : TreeCursor) -> CursorChildIterator {
  let last_entry = self.stack[self.stack.length() - 1]
  let subtree = last_entry.subtree.get()
  if subtree.child_count() == 0 {
    return {
      parent: Null,
      tree: self.tree,
      position: length_zero(),
      child_index: 0,
      structural_child_index: 0,
      descendant_index: 0,
      alias_sequence: None,
    }
  }
  let alias_sequence = self
    .language()
    .alias_sequence(subtree.ptr().production_id)
  let mut descendant_index = last_entry.descendant_index
  if self.is_entry_visible(self.stack.length() - 1) {
    descendant_index += 1
  }
  {
    tree: self.tree,
    parent: subtree,
    position: last_entry.position,
    child_index: 0,
    structural_child_index: 0,
    descendant_index,
    alias_sequence,
  }
}

///|
/// `ts_tree_cursor_child_iterator_next`: the next entry and its visibility.
fn CursorChildIterator::next(
  self : CursorChildIterator,
) -> (TreeCursorEntry, Bool)? {
  if self.parent.is_null() || self.child_index == self.parent.child_count() {
    return None
  }
  let slot = self.parent.child_slot(self.child_index)
  let child = slot.get()
  let result : TreeCursorEntry = {
    subtree: slot,
    position: self.position,
    child_index: self.child_index,
    structural_child_index: self.structural_child_index,
    descendant_index: self.descendant_index,
  }
  let mut visible = child.visible()
  let extra = child.extra()
  if !extra {
    if self.alias_sequence is Some(offset) {
      let language = self.tree.unwrap().language
      if language.alias_sequence_value(offset + self.structural_child_index) !=
        0 {
        visible = true
      }
    }
    self.structural_child_index += 1
  }
  self.descendant_index += child.visible_descendant_count()
  if visible {
    self.descendant_index += 1
  }
  self.position = length_add(self.position, child.size())
  self.child_index += 1
  if self.child_index < self.parent.child_count() {
    let next_child = self.parent.children()[self.child_index]
    self.position = length_add(self.position, next_child.padding())
  }
  Some((result, visible))
}

///|
/// Return a position that, when `b` is added to it, yields `a`. This can
/// only be computed if `b` has zero rows. Otherwise, this function returns
/// `length_undefined`, and the caller needs to recompute the position some
/// other way.
fn length_backtrack(a : Length, b : Length) -> Length {
  if length_is_undefined(a) || b.extent.row != 0 {
    return length_undefined
  }
  {
    bytes: a.bytes - b.bytes,
    extent: { row: a.extent.row, column: a.extent.column - b.extent.column, },
  }
}

///|
/// `ts_tree_cursor_child_iterator_previous`.
fn CursorChildIterator::previous(
  self : CursorChildIterator,
) -> (TreeCursorEntry, Bool)? {
  // This is mostly a reverse `next` taking into account unsigned underflow.
  // Upstream compares `(int8_t)child_index == -1`, so the index is truncated
  // to 8 bits here too.
  if self.parent.is_null() || (self.child_index & 0xFF) == 0xFF {
    return None
  }
  let slot = self.parent.child_slot(self.child_index)
  let child = slot.get()
  let result : TreeCursorEntry = {
    subtree: slot,
    position: self.position,
    child_index: self.child_index,
    structural_child_index: self.structural_child_index,
    descendant_index: 0,
  }
  let mut visible = child.visible()
  let extra = child.extra()
  self.position = length_backtrack(self.position, child.padding())
  self.child_index -= 1
  if !extra && self.alias_sequence is Some(offset) {
    let language = self.tree.unwrap().language
    if language.alias_sequence_value(offset + self.structural_child_index) != 0 {
      visible = true
    }
    if self.structural_child_index > 0 {
      self.structural_child_index -= 1
    }
  }
  // unsigned can underflow so compare it to child_count
  if self.child_index >= 0 && self.child_index < self.parent.child_count() {
    let previous_child = self.parent.children()[self.child_index]
    let size = previous_child.size()
    self.position = length_backtrack(self.position, size)
  }
  Some((result, visible))
}

///|
/// `ts_tree_cursor_new`.
pub fn TreeCursor::new(node : Node) -> TreeCursor {
  let cursor = { tree: None, stack: [], root_alias_symbol: 0, }
  cursor.init(node)
  cursor
}

///|
/// `ts_tree_cursor_reset`.
pub fn TreeCursor::reset(self : TreeCursor, node : Node) -> Unit {
  self.init(node)
}

///|
/// `ts_tree_cursor_init`.
fn TreeCursor::init(self : TreeCursor, node : Node) -> Unit {
  self.tree = node.tree
  self.root_alias_symbol = node.alias
  self.stack = [
    {
      subtree: node.id.unwrap(),
      position: { bytes: node.start_byte(), extent: node.start_point(), },
      child_index: 0,
      structural_child_index: 0,
      descendant_index: 0,
    },
  ]
}

///|
pub fn TreeCursor::goto_first_child_internal(
  self : TreeCursor,
) -> TreeCursorStep {
  let iterator = self.iterate_children()
  while iterator.next() is Some((entry, visible)) {
    if visible {
      self.stack.push(entry)
      return StepVisible
    }
    if entry.subtree.get().visible_child_count() > 0 {
      self.stack.push(entry)
      return StepHidden
    }
  }
  StepNone
}

///|
/// `ts_tree_cursor_goto_first_child`.
pub fn TreeCursor::goto_first_child(self : TreeCursor) -> Bool {
  for ;; {
    match self.goto_first_child_internal() {
      StepHidden => continue
      StepVisible => return true
      StepNone => return false
    }
  }
}

///|
pub fn TreeCursor::goto_last_child_internal(
  self : TreeCursor,
) -> TreeCursorStep {
  let iterator = self.iterate_children()
  if iterator.parent.is_null() || iterator.parent.child_count() == 0 {
    return StepNone
  }
  let mut last_entry : TreeCursorEntry? = None
  let mut last_step = StepNone
  while iterator.next() is Some((entry, visible)) {
    if visible {
      last_entry = Some(entry)
      last_step = StepVisible
    } else if entry.subtree.get().visible_child_count() > 0 {
      last_entry = Some(entry)
      last_step = StepHidden
    }
  }
  if last_entry is Some(entry) {
    self.stack.push(entry)
    return last_step
  }
  StepNone
}

///|
/// `ts_tree_cursor_goto_last_child`.
pub fn TreeCursor::goto_last_child(self : TreeCursor) -> Bool {
  for ;; {
    match self.goto_last_child_internal() {
      StepHidden => continue
      StepVisible => return true
      StepNone => return false
    }
  }
}

///|
fn TreeCursor::goto_first_child_for_byte_and_point(
  self : TreeCursor,
  goal_byte : UInt32,
  goal_point : Point,
) -> Int64 {
  let initial_size = self.stack.length()
  let mut visible_child_index : UInt32 = 0
  let mut did_descend = true
  while did_descend {
    did_descend = false
    let iterator = self.iterate_children()
    while iterator.next() is Some((entry, visible)) {
      let subtree = entry.subtree.get()
      let entry_end = length_add(entry.position, subtree.size())
      let at_goal = entry_end.bytes > goal_byte &&
        point_gt(entry_end.extent, goal_point)
      let visible_child_count = subtree.visible_child_count()
      if at_goal {
        if visible {
          self.stack.push(entry)
          return visible_child_index.to_int64()
        }
        if visible_child_count > 0 {
          self.stack.push(entry)
          did_descend = true
          break
        }
      } else if visible {
        visible_child_index += 1
      } else {
        visible_child_index += visible_child_count
      }
    }
  }
  self.stack.truncate(initial_size)
  -1
}

///|
/// `ts_tree_cursor_goto_first_child_for_byte`.
pub fn TreeCursor::goto_first_child_for_byte(
  self : TreeCursor,
  goal_byte : UInt32,
) -> Int64 {
  self.goto_first_child_for_byte_and_point(goal_byte, point_zero)
}

///|
/// `ts_tree_cursor_goto_first_child_for_point`.
pub fn TreeCursor::goto_first_child_for_point(
  self : TreeCursor,
  goal_point : Point,
) -> Int64 {
  self.goto_first_child_for_byte_and_point(0, goal_point)
}

///|
fn TreeCursor::goto_sibling_internal(
  self : TreeCursor,
  forward : Bool,
) -> TreeCursorStep {
  let initial_size = self.stack.length()
  // Upstream restores `stack.size = initial_size` on failure, which brings
  // back the popped entries that are still in the buffer.
  let popped : Array[TreeCursorEntry] = []
  while self.stack.length() > 1 {
    let entry = self.stack.pop().unwrap()
    popped.push(entry)
    let iterator = self.iterate_children()
    iterator.child_index = entry.child_index
    iterator.structural_child_index = entry.structural_child_index
    iterator.position = entry.position
    iterator.descendant_index = entry.descendant_index
    let advance = () => {
      if forward {
        iterator.next()
      } else {
        iterator.previous()
      }
    }
    let mut visible = false
    if advance() is Some((_, v)) {
      visible = v
    }
    if visible && self.stack.length() + 1 < initial_size {
      break
    }
    while advance() is Some((entry, visible)) {
      if visible {
        self.stack.push(entry)
        return StepVisible
      }
      if entry.subtree.get().visible_child_count() > 0 {
        self.stack.push(entry)
        return StepHidden
      }
    }
  }
  while popped.pop() is Some(entry) {
    self.stack.push(entry)
  }
  ignore(initial_size)
  StepNone
}

///|
pub fn TreeCursor::goto_next_sibling_internal(
  self : TreeCursor,
) -> TreeCursorStep {
  self.goto_sibling_internal(true)
}

///|
/// `ts_tree_cursor_goto_next_sibling`.
pub fn TreeCursor::goto_next_sibling(self : TreeCursor) -> Bool {
  match self.goto_next_sibling_internal() {
    StepHidden => {
      ignore(self.goto_first_child())
      true
    }
    StepVisible => true
    StepNone => false
  }
}

///|
pub fn TreeCursor::goto_previous_sibling_internal(
  self : TreeCursor,
) -> TreeCursorStep {
  // Since subtracting across row loses column information, we may have to
  // restore it.
  let step = self.goto_sibling_internal(false)
  if step == StepNone {
    return step
  }
  // If length is already valid, there's no need to recompute it.
  let last = self.stack[self.stack.length() - 1]
  if !length_is_undefined(last.position) {
    return step
  }
  // Restore position from the parent node.
  let parent = self.stack[self.stack.length() - 2]
  let mut position = parent.position
  let child_index = last.child_index
  let children = parent.subtree.get().children()
  if child_index > 0 {
    // Skip first child padding since its position should match the position
    // of the parent.
    position = length_add(position, children[0].size())
    for i in 1.. Bool {
  match self.goto_previous_sibling_internal() {
    StepHidden => {
      ignore(self.goto_last_child())
      true
    }
    StepVisible => true
    StepNone => false
  }
}

///|
/// `ts_tree_cursor_goto_parent`.
pub fn TreeCursor::goto_parent(self : TreeCursor) -> Bool {
  for i = self.stack.length() - 2; i >= 0; i = i - 1 {
    if self.is_entry_visible(i) {
      self.stack.truncate(i + 1)
      return true
    }
  }
  false
}

///|
/// `ts_tree_cursor_goto_descendant`.
pub fn TreeCursor::goto_descendant(
  self : TreeCursor,
  goal_descendant_index : UInt32,
) -> Unit {
  // Ascend to the lowest ancestor that contains the goal node.
  for ;; {
    let i = self.stack.length() - 1
    let entry = self.stack[i]
    let next_descendant_index = entry.descendant_index +
      (if self.is_entry_visible(i) { 1 } else { 0 }) +
      entry.subtree.get().visible_descendant_count()
    if entry.descendant_index <= goal_descendant_index &&
      next_descendant_index > goal_descendant_index {
      break
    } else if self.stack.length() <= 1 {
      return
    } else {
      ignore(self.stack.pop())
    }
  }
  // Descend to the goal node.
  let mut did_descend = true
  while did_descend {
    did_descend = false
    let iterator = self.iterate_children()
    if iterator.descendant_index > goal_descendant_index {
      return
    }
    while iterator.next() is Some((entry, visible)) {
      if iterator.descendant_index > goal_descendant_index {
        self.stack.push(entry)
        if visible && entry.descendant_index == goal_descendant_index {
          return
        } else {
          did_descend = true
          break
        }
      }
    }
  }
}

///|
/// `ts_tree_cursor_current_descendant_index`.
pub fn TreeCursor::current_descendant_index(self : TreeCursor) -> UInt32 {
  self.stack[self.stack.length() - 1].descendant_index
}

///|
/// `ts_tree_cursor_current_node`.
pub fn TreeCursor::current_node(self : TreeCursor) -> Node {
  let last_entry = self.stack[self.stack.length() - 1]
  let is_extra = last_entry.subtree.get().extra()
  let mut alias_symbol = if is_extra { 0 } else { self.root_alias_symbol }
  if self.stack.length() > 1 && !is_extra {
    let parent_entry = self.stack[self.stack.length() - 2]
    alias_symbol = self
      .language()
      .alias_at(
        parent_entry.subtree.get().ptr().production_id,
        last_entry.structural_child_index,
      )
  }
  Node::new(
    self.tree,
    Some(last_entry.subtree),
    last_entry.position,
    alias_symbol,
  )
}

///|
pub fn TreeCursor::current_subtree(self : TreeCursor) -> Subtree {
  self.stack[self.stack.length() - 1].subtree.get()
}

///|
pub fn TreeCursor::entries(self : TreeCursor) -> Array[TreeCursorEntry] {
  self.stack
}

///|
/// The result of `ts_tree_cursor_current_status`.
pub(all) struct CursorStatus {
  field_id : Int32
  has_later_siblings : Bool
  has_later_named_siblings : Bool
  can_have_later_siblings_with_this_field : Bool
  supertypes : Array[Int32]
}

///|
/// `ts_tree_cursor_current_status`: facts about the current node that are
/// needed when executing tree queries. `can_have_later_siblings_with_this_field`
/// is never false when a later sibling has the current node's field, but can
/// be true when none does.
pub fn TreeCursor::current_status(
  self : TreeCursor,
  max_supertypes : Int32,
) -> CursorStatus {
  let language = self.language()
  let mut field_id = 0
  let supertypes = []
  let mut has_later_siblings = false
  let mut has_later_named_siblings = false
  let mut can_have_later_siblings_with_this_field = false
  // A later sibling with no field of its own may inherit one further up.
  let mut later_sibling_without_field = false
  // Walk up the tree, visiting the current node and its invisible ancestors,
  // because fields can refer to nodes through invisible *wrapper* nodes.
  let mut i = self.stack.length() - 1
  while i > 0 {
    let entry = self.stack[i]
    let parent_entry = self.stack[i - 1]
    let parent_subtree = parent_entry.subtree.get()
    let entry_subtree = entry.subtree.get()
    let alias_sequence = language.alias_sequence(
      parent_subtree.ptr().production_id,
    )
    let subtree_symbol = (subtree : Subtree, structural_child_index : Int32) => {
      match alias_sequence {
        Some(offset) if !subtree.extra() &&
          language.alias_sequence_value(offset + structural_child_index) != 0 =>
          language.alias_sequence_value(offset + structural_child_index)
        _ => subtree.symbol()
      }
    }
    // Stop walking up when a visible ancestor is found.
    let entry_symbol = subtree_symbol(
      entry_subtree,
      entry.structural_child_index,
    )
    let entry_metadata = language.symbol_metadata_of(entry_symbol)
    if i != self.stack.length() - 1 && entry_metadata.visible {
      break
    }
    // Record any supertypes
    if entry_metadata.supertype && supertypes.length() < max_supertypes {
      supertypes.push(entry_symbol)
    }
    let (field_map, field_map_end) = language.field_map(
      parent_subtree.ptr().production_id,
    )
    let mut find_later_sibling_without_field = false
    if !entry_subtree.extra() {
      // Look for a field name associated with this entry.
      let mut entry_field_id = 0
      for m in field_map.. entry.structural_child_index {
            can_have_later_siblings_with_this_field = true
            break
          }
        }
      }
      // A fieldless later sibling may inherit a field from its hidden parent.
      find_later_sibling_without_field = field_id != 0 &&
        !can_have_later_siblings_with_this_field &&
        !later_sibling_without_field &&
        !self.is_entry_visible(i - 1)
    }
    // Determine if the current node has later siblings. A later *anonymous*
    // sibling settles `has_later_siblings` but says nothing about later
    // *named* siblings. When needed, also look for one with no field of its
    // own.
    if !has_later_named_siblings || find_later_sibling_without_field {
      let sibling_count = parent_subtree.child_count()
      let mut structural_child_index = entry.structural_child_index
      if !entry_subtree.extra() {
        structural_child_index += 1
      }
      for j in (entry.child_index + 1).. 0 {
          is_visible = true
          is_named = sibling.ptr().named_child_count > 0
        }
        if is_visible {
          has_later_siblings = true
          if is_named {
            has_later_named_siblings = true
          }
          if find_later_sibling_without_field {
            let mut has_field = false
            if !sibling.extra() {
              for m in field_map.. UInt32 {
  let mut depth : UInt32 = 0
  for i in 1.. Node {
  for i = self.stack.length() - 2; i >= 0; i = i - 1 {
    let entry = self.stack[i]
    let mut is_visible = true
    let mut alias_symbol = 0
    if i > 0 {
      let parent_entry = self.stack[i - 1]
      alias_symbol = self
        .language()
        .alias_at(
          parent_entry.subtree.get().ptr().production_id,
          entry.structural_child_index,
        )
      is_visible = alias_symbol != 0 || entry.subtree.get().visible()
    }
    if is_visible {
      return Node::new(
        self.tree,
        Some(entry.subtree),
        entry.position,
        alias_symbol,
      )
    }
  }
  Node::new(None, None, length_zero(), 0)
}

///|
/// `ts_tree_cursor_current_field_id`.
pub fn TreeCursor::current_field_id(self : TreeCursor) -> Int32 {
  let language = self.language()
  // Walk up the tree, visiting the current node and its invisible ancestors.
  let mut i = self.stack.length() - 1
  while i > 0 {
    let entry = self.stack[i]
    let parent_entry = self.stack[i - 1]
    // Stop walking up when another visible node is found.
    if i != self.stack.length() - 1 && self.is_entry_visible(i) {
      break
    }
    if entry.subtree.get().extra() {
      break
    }
    let (field_map, field_map_end) = language.field_map(
      parent_entry.subtree.get().ptr().production_id,
    )
    for m in field_map.. String? {
  let id = self.current_field_id()
  if id != 0 {
    // `field_names[id]` is a C string.
    self.language().field_name_for_id(id)
  } else {
    None
  }
}

///|
/// `ts_tree_cursor_copy`.
pub fn TreeCursor::copy(self : TreeCursor) -> TreeCursor {
  {
    tree: self.tree,
    stack: self.stack.copy(),
    root_alias_symbol: self.root_alias_symbol,
  }
}

///|
/// `ts_tree_cursor_reset_to`.
pub fn TreeCursor::reset_to(self : TreeCursor, src : TreeCursor) -> Unit {
  self.tree = src.tree
  self.root_alias_symbol = src.root_alias_symbol
  self.stack = src.stack.copy()
}

///|
pub fn TreeCursor::tree(self : TreeCursor) -> Tree? {
  self.tree
}