// Port of tree-sitter lib/src/query.c: the `TSQuery` structure and its
// pattern map.

///|
/// A `[offset, offset + length)` slice of one of the query's arrays.
priv struct Slice {
  offset : Int
  length : Int
}

///|
/// PatternEntry - Information about the starting point for matching a
/// particular pattern. These entries are stored in a 'pattern map' - a sorted
/// array that makes it possible to efficiently lookup patterns based on the
/// symbol for their first step.
priv struct PatternEntry {
  step_index : Int
  pattern_index : Int
  is_rooted : Bool
}

///|
priv struct QueryPattern {
  steps : Slice
  predicate_steps : Slice
  start_byte : UInt
  end_byte : UInt
  mut is_non_local : Bool
}

///|
priv struct StepOffset {
  byte_offset : UInt
  step_index : Int
}

///|
/// `TSQueryPredicateStepType`.
pub(all) enum QueryPredicateStepType {
  Done
  Capture
  String
} derive(Eq, Debug)

///|
/// `TSQueryPredicateStep`.
pub(all) struct QueryPredicateStep {
  type_ : QueryPredicateStepType
  value_id : Int
} derive(Eq, Debug)

///|
/// `TSQueryError`.
pub(all) enum QueryErrorKind {
  Syntax
  NodeType
  Field
  Capture
  Structure
  Language
} derive(Eq, Debug)

///|
/// A query compilation error: its kind and the byte offset in the source.
pub suberror QueryError {
  QueryError(kind~ : QueryErrorKind, offset~ : UInt)
} derive(Debug)

///|
/// TSQuery - A tree query, compiled from a string of S-expressions. The query
/// itself is immutable. The mutable state used in the process of executing the
/// query is stored in a `QueryCursor`.
pub struct Query {
  priv captures : SymbolTable
  priv predicate_values : SymbolTable
  priv capture_quantifiers : Array[Array[Quantifier]]
  priv steps : Array[QueryStep]
  priv pattern_map : Array[PatternEntry]
  priv predicate_steps : Array[QueryPredicateStep]
  priv patterns : Array[QueryPattern]
  priv step_offsets : Array[StepOffset]
  priv negated_fields : Array[Int]
  priv mut string_buffer : Array[Byte]
  priv repeat_symbols_with_rootless_patterns : Array[Int]
  priv language : @language.Language
  priv mut wildcard_root_pattern_count : Int
}

///|
/// The `pattern_map` contains a mapping from symbol values to indices in the
/// `steps` array. For a given syntax node, the `pattern_map` makes it possible
/// to quickly find the starting steps of all of the patterns whose root
/// matches that node.
///
/// The entries are sorted by the patterns' root symbols, and lookups use a
/// binary search. Returns whether the symbol is present, and the index where
/// it is or should be inserted.
fn Query::pattern_map_search(self : Query, needle : Int) -> (Bool, Int) {
  let mut base_index = self.wildcard_root_pattern_count
  let mut size = self.pattern_map.length() - base_index
  if size == 0 {
    return (false, base_index)
  }
  while size > 1 {
    let half_size = size / 2
    let mid_index = base_index + half_size
    let mid_symbol = self.steps[self.pattern_map[mid_index].step_index].symbol
    if needle > mid_symbol {
      base_index = mid_index
    }
    size -= half_size
  }
  let mut symbol = self.steps[self.pattern_map[base_index].step_index].symbol
  if needle > symbol {
    base_index += 1
    if base_index < self.pattern_map.length() {
      symbol = self.steps[self.pattern_map[base_index].step_index].symbol
    }
  }
  (needle == symbol, base_index)
}

///|
/// Insert a new pattern's start index into the pattern map, maintaining the
/// pattern map's ordering invariant.
fn Query::pattern_map_insert(
  self : Query,
  symbol : Int,
  new_entry : PatternEntry,
) -> Unit {
  let (_, found_index) = self.pattern_map_search(symbol)
  let mut index = found_index
  // Ensure that the entries are sorted not only by symbol, but also by
  // pattern_index. This way, states for earlier patterns will be initiated
  // first, which allows the ordering of the states array to be maintained
  // more efficiently.
  while index < self.pattern_map.length() {
    let entry = self.pattern_map[index]
    if self.steps[entry.step_index].symbol == symbol &&
      entry.pattern_index < new_entry.pattern_index {
      index += 1
    } else {
      break
    }
  }
  self.pattern_map.insert(index, new_entry)
}

///|
/// `_array__search_sorted` with an integer key.
fn[T] search_sorted_by(
  array : Array[T],
  key : (T) -> Int,
  needle : Int,
) -> (Int, Bool) {
  search_sorted_with(array, item => key(item) - needle)
}

///|
/// `_array__search_sorted`: `compare(item)` compares an item with the needle.
fn[T] search_sorted_with(array : Array[T], compare : (T) -> Int) -> (Int, Bool) {
  let mut index = 0
  let mut size = array.length()
  if size == 0 {
    return (0, false)
  }
  while size > 1 {
    let half_size = size / 2
    let mid_index = index + half_size
    if compare(array[mid_index]) <= 0 {
      index = mid_index
    }
    size -= half_size
  }
  let comparison = compare(array[index])
  if comparison == 0 {
    (index, true)
  } else if comparison < 0 {
    (index + 1, false)
  } else {
    (index, false)
  }
}

///|
/// `array_insert_sorted_by` for an array of integers.
fn insert_sorted_int(array : Array[Int], value : Int) -> Unit {
  let (index, exists) = search_sorted_by(array, x => x, value)
  if !exists {
    array.insert(index, value)
  }
}