// Port of `ts_subtree_get_changed_ranges` and its iterator from tree-sitter
// lib/src/get_changed_ranges.c, plus `ts_tree_get_changed_ranges`.

///|
priv struct ChangeIterator {
  stack : Array[TreeCursorEntry]
  language : @language.Language
  mut visible_depth : Int32
  mut in_padding : Bool
  mut prev_external_token : Subtree
}

///|
fn ChangeIterator::new(
  tree : SubtreeSlot,
  language : @language.Language,
) -> ChangeIterator {
  {
    stack: [
      {
        subtree: tree,
        position: length_zero(),
        child_index: 0,
        structural_child_index: 0,
        descendant_index: 0,
      },
    ],
    language,
    visible_depth: 1,
    in_padding: false,
    prev_external_token: Null,
  }
}

///|
fn ChangeIterator::done(self : ChangeIterator) -> Bool {
  self.stack.length() == 0
}

///|
fn ChangeIterator::back(self : ChangeIterator) -> TreeCursorEntry {
  self.stack[self.stack.length() - 1]
}

///|
fn ChangeIterator::start_position(self : ChangeIterator) -> Length {
  let entry = self.back()
  if self.in_padding {
    entry.position
  } else {
    length_add(entry.position, entry.subtree.get().padding())
  }
}

///|
fn ChangeIterator::end_position(self : ChangeIterator) -> Length {
  let entry = self.back()
  let result = length_add(entry.position, entry.subtree.get().padding())
  if self.in_padding {
    result
  } else {
    length_add(result, entry.subtree.get().size())
  }
}

///|
fn ChangeIterator::tree_is_visible(self : ChangeIterator) -> Bool {
  let entry = self.back()
  if entry.subtree.get().visible() {
    return true
  }
  if self.stack.length() > 1 {
    let parent = self.stack[self.stack.length() - 2].subtree.get()
    return self.language.alias_at(
        parent.ptr().production_id,
        entry.structural_child_index,
      ) !=
      0
  }
  false
}

///|
/// `iterator_get_visible_state`: `(tree, alias_symbol, start_byte)`.
fn ChangeIterator::get_visible_state(
  self : ChangeIterator,
) -> (Subtree, Int32, UInt32) {
  let mut tree = Subtree::Null
  let mut alias_symbol = 0
  let mut start_byte : UInt32 = 0
  let mut i = self.stack.length() - 1
  if self.in_padding {
    if i == 0 {
      return (tree, alias_symbol, start_byte)
    }
    i -= 1
  }
  while i >= 0 {
    let entry = self.stack[i]
    if i > 0 {
      let parent = self.stack[i - 1].subtree.get()
      alias_symbol = self.language.alias_at(
        parent.ptr().production_id,
        entry.structural_child_index,
      )
    }
    if entry.subtree.get().visible() || alias_symbol != 0 {
      tree = entry.subtree.get()
      start_byte = entry.position.bytes
      break
    }
    i -= 1
  }
  (tree, alias_symbol, start_byte)
}

///|
fn ChangeIterator::ascend(self : ChangeIterator) -> Unit {
  if self.done() {
    return
  }
  if self.tree_is_visible() && !self.in_padding {
    self.visible_depth -= 1
  }
  if self.back().child_index > 0 {
    self.in_padding = false
  }
  ignore(self.stack.pop())
}

///|
fn ChangeIterator::descend(
  self : ChangeIterator,
  goal_position : UInt32,
) -> Bool {
  if self.in_padding {
    return false
  }
  let mut did_descend = true
  while did_descend {
    did_descend = false
    let entry = self.back()
    let parent = entry.subtree.get()
    let mut position = entry.position
    let mut structural_child_index = 0
    for i in 0.. goal_position {
        self.stack.push({
          subtree: slot,
          position,
          child_index: i,
          structural_child_index,
          descendant_index: 0,
        })
        if self.tree_is_visible() {
          if child_left.bytes > goal_position {
            self.in_padding = true
          } else {
            self.visible_depth += 1
          }
          return true
        }
        did_descend = true
        break
      }
      position = child_right
      if !child.extra() {
        structural_child_index += 1
      }
      let last_external_token = child.last_external_token()
      if !last_external_token.is_null() {
        self.prev_external_token = last_external_token
      }
    }
  }
  false
}

///|
fn ChangeIterator::advance(self : ChangeIterator) -> Unit {
  if self.in_padding {
    self.in_padding = false
    if self.tree_is_visible() {
      self.visible_depth += 1
    } else {
      ignore(self.descend(0))
    }
    return
  }
  for ;; {
    if self.tree_is_visible() {
      self.visible_depth -= 1
    }
    let entry = self.stack.pop().unwrap()
    if self.done() {
      return
    }
    let parent = self.back().subtree.get()
    let child_index = entry.child_index + 1
    let entry_subtree = entry.subtree.get()
    let last_external_token = entry_subtree.last_external_token()
    if !last_external_token.is_null() {
      self.prev_external_token = last_external_token
    }
    if parent.child_count() > child_index {
      let position = length_add(entry.position, entry_subtree.total_size())
      let mut structural_child_index = entry.structural_child_index
      if !entry_subtree.extra() {
        structural_child_index += 1
      }
      let next_slot = parent.child_slot(child_index)
      self.stack.push({
        subtree: next_slot,
        position,
        child_index,
        structural_child_index,
        descendant_index: 0,
      })
      if self.tree_is_visible() {
        if next_slot.get().padding().bytes > 0 {
          self.in_padding = true
        } else {
          self.visible_depth += 1
        }
      } else {
        ignore(self.descend(0))
      }
      break
    }
  }
}

///|
priv enum IteratorComparison {
  Differs
  MayDiffer
  Matches
} derive(Eq)

///|
fn iterator_compare(
  old_iter : ChangeIterator,
  new_iter : ChangeIterator,
) -> IteratorComparison {
  let (old_tree, old_alias_symbol, old_start) = old_iter.get_visible_state()
  let (new_tree, new_alias_symbol, new_start) = new_iter.get_visible_state()
  if old_tree.is_null() && new_tree.is_null() {
    return Matches
  }
  if old_tree.is_null() || new_tree.is_null() {
    return Differs
  }
  let old_symbol = old_tree.symbol()
  let new_symbol = new_tree.symbol()
  if old_alias_symbol != new_alias_symbol || old_symbol != new_symbol {
    return Differs
  }
  let old_size = old_tree.size().bytes
  let new_size = new_tree.size().bytes
  let old_state = old_tree.parse_state()
  let new_state = new_tree.parse_state()
  let old_has_external_tokens = old_tree.has_external_tokens()
  let new_has_external_tokens = new_tree.has_external_tokens()
  let old_error_cost = old_tree.error_cost()
  let new_error_cost = new_tree.error_cost()
  if old_start != new_start ||
    old_symbol == @language.ts_builtin_sym_error ||
    old_size != new_size ||
    old_state == ts_tree_state_none ||
    new_state == ts_tree_state_none ||
    (old_state == error_state) != (new_state == error_state) ||
    old_error_cost != new_error_cost ||
    old_has_external_tokens != new_has_external_tokens ||
    old_tree.has_changes() ||
    (
      old_has_external_tokens &&
      !old_iter.prev_external_token.external_scanner_state_eq(
        new_iter.prev_external_token,
      )
    ) {
    return MayDiffer
  }
  Matches
}

///|
/// `ts_subtree_get_changed_ranges`.
pub fn subtree_get_changed_ranges(
  old_tree : SubtreeSlot,
  new_tree : SubtreeSlot,
  language : @language.Language,
  included_range_differences : Array[Range],
) -> Array[Range] {
  let results : Array[Range] = []
  let old_iter = ChangeIterator::new(old_tree, language)
  let new_iter = ChangeIterator::new(new_tree, language)
  let mut included_range_difference_index = 0
  let mut position = old_iter.start_position()
  let mut next_position = new_iter.start_position()
  if position.bytes < next_position.bytes {
    range_array_add(results, position, next_position)
    position = next_position
  } else if position.bytes > next_position.bytes {
    range_array_add(results, next_position, position)
    next_position = position
  }
  for ;; {
    // Compare the old and new subtrees.
    let mut comparison = iterator_compare(old_iter, new_iter)
    // Even if the two subtrees appear to be identical, they could differ
    // internally if they contain a range of text that was previously
    // excluded from the parse, and is now included, or vice-versa.
    if comparison == Matches &&
      range_array_intersects(
        included_range_differences,
        included_range_difference_index,
        position.bytes,
        old_iter.end_position().bytes,
      ) {
      comparison = MayDiffer
    }
    let mut is_changed = false
    match comparison {
      // If the subtrees are definitely identical, move to the end of both
      // subtrees.
      Matches => next_position = old_iter.end_position()
      // If the subtrees might differ internally, descend into both subtrees,
      // finding the first child that spans the current position.
      MayDiffer =>
        if old_iter.descend(position.bytes) {
          if !new_iter.descend(position.bytes) {
            is_changed = true
            next_position = old_iter.end_position()
          }
        } else if new_iter.descend(position.bytes) {
          is_changed = true
          next_position = new_iter.end_position()
        } else {
          next_position = length_min(
            old_iter.end_position(),
            new_iter.end_position(),
          )
        }
      // If the subtrees are different, record a change and then move to the
      // end of both subtrees.
      Differs => {
        is_changed = true
        next_position = length_min(
          old_iter.end_position(),
          new_iter.end_position(),
        )
      }
    }
    // Ensure that both iterators are caught up to the current position.
    while !old_iter.done() &&
          old_iter.end_position().bytes <= next_position.bytes {
      old_iter.advance()
    }
    while !new_iter.done() &&
          new_iter.end_position().bytes <= next_position.bytes {
      new_iter.advance()
    }
    // Ensure that both iterators are at the same depth in the tree.
    while old_iter.visible_depth > new_iter.visible_depth {
      old_iter.ascend()
    }
    while new_iter.visible_depth > old_iter.visible_depth {
      new_iter.ascend()
    }
    if is_changed {
      range_array_add(results, position, next_position)
    }
    position = next_position
    // Keep track of the current position in the included range differences
    // array in order to avoid scanning the entire array on each iteration.
    while included_range_difference_index < included_range_differences.length() {
      let range = included_range_differences[included_range_difference_index]
      if range.end_byte <= position.bytes {
        included_range_difference_index += 1
      } else {
        break
      }
    }
    if old_iter.done() || new_iter.done() {
      break
    }
  }
  let old_size = old_tree.get().total_size()
  let new_size = new_tree.get().total_size()
  if old_size.bytes < new_size.bytes {
    range_array_add(results, old_size, new_size)
  } else if new_size.bytes < old_size.bytes {
    range_array_add(results, new_size, old_size)
  }
  results
}

///|
/// `ts_tree_get_changed_ranges`.
pub fn Tree::changed_ranges(old_tree : Tree, new_tree : Tree) -> Array[Range] {
  let included_range_differences = []
  range_array_get_changed_ranges(
    old_tree.included_ranges,
    new_tree.included_ranges,
    included_range_differences,
  )
  subtree_get_changed_ranges(
    old_tree.root_ref(),
    new_tree.root_ref(),
    old_tree.language,
    included_range_differences,
  )
}