// Port of the query analysis in tree-sitter lib/src/query.c: walking the
// parse table to determine which pattern steps are guaranteed to match.

///|
/// AnalysisStateEntry. `field_id` is a 15-bit field upstream.
priv struct AnalysisStateEntry {
  parse_state : Int
  parent_symbol : Int
  child_index : Int
  field_id : Int
  done : Bool
} derive(Eq)

///|
let empty_analysis_entry : AnalysisStateEntry = {
  parse_state: 0,
  parent_symbol: 0,
  child_index: 0,
  field_id: 0,
  done: false,
}

///|
/// AnalysisState - The state needed for walking the parse table when
/// analyzing a query pattern, to determine at which steps the pattern might
/// fail to match.
priv struct AnalysisState {
  stack : FixedArray[AnalysisStateEntry]
  mut depth : Int
  mut step_index : Int
  root_symbol : Int
}

///|
fn AnalysisState::new(
  step_index : Int,
  entry : AnalysisStateEntry,
  root_symbol : Int,
) -> AnalysisState {
  let stack = FixedArray::make(max_analysis_state_depth, empty_analysis_entry)
  stack[0] = entry
  { stack, depth: 1, step_index, root_symbol }
}

///|
/// A value copy (`AnalysisState next_state = *state`).
fn AnalysisState::copy(self : AnalysisState) -> AnalysisState {
  { ..self, stack: self.stack.copy() }
}

///|
fn AnalysisState::recursion_depth(self : AnalysisState) -> Int {
  let mut result = 0
  for i in 0.. Int {
  if left.depth < other.depth {
    return 1
  }
  for i in 0..= other.depth {
      return -1
    }
    let s1 = left.stack[i]
    let s2 = other.stack[i]
    if s1.child_index < s2.child_index {
      return -1
    }
    if s1.child_index > s2.child_index {
      return 1
    }
    if s1.parent_symbol < s2.parent_symbol {
      return -1
    }
    if s1.parent_symbol > s2.parent_symbol {
      return 1
    }
    if s1.parse_state < s2.parse_state {
      return -1
    }
    if s1.parse_state > s2.parse_state {
      return 1
    }
    if s1.field_id < s2.field_id {
      return -1
    }
    if s1.field_id > s2.field_id {
      return 1
    }
  }
  if left.step_index < other.step_index {
    return -1
  }
  if left.step_index > other.step_index {
    return 1
  }
  0
}

///|
/// The index of `analysis_state__top`.
fn AnalysisState::top_index(self : AnalysisState) -> Int {
  if self.depth == 0 {
    0
  } else {
    self.depth - 1
  }
}

///|
fn AnalysisState::top(self : AnalysisState) -> AnalysisStateEntry {
  self.stack[self.top_index()]
}

///|
fn AnalysisState::has_supertype(self : AnalysisState, symbol : Int) -> Bool {
  for i in 0.. Unit {
  let (index, exists) = search_sorted_with(set, s => {
    analysis_state_compare(s, item)
  })
  if !exists {
    set.insert(index, item.copy())
  }
}

///|
/// Inserts a clone of the item at the end of this list.
fn analysis_state_set_push(
  set : Array[AnalysisState],
  item : AnalysisState,
) -> Unit {
  set.push(item.copy())
}

///|
priv struct QueryAnalysis {
  mut states : Array[AnalysisState]
  mut next_states : Array[AnalysisState]
  mut deeper_states : Array[AnalysisState]
  final_step_indices : Array[Int]
  finished_parent_symbols : Array[Int]
  mut did_abort : Bool
}

///|
fn QueryAnalysis::new() -> QueryAnalysis {
  {
    states: [],
    next_states: [],
    deeper_states: [],
    final_step_indices: [],
    finished_parent_symbols: [],
    did_abort: false,
  }
}

///|
/// AnalysisSubgraphNode. `child_index` is a 7-bit field upstream, so it is
/// kept truncated to 7 bits.
priv struct AnalysisSubgraphNode {
  state : Int
  production_id : Int
  child_index : Int
  done : Bool
}

///|
fn subgraph_node(
  state : Int,
  production_id : Int,
  child_index : Int,
  done : Bool,
) -> AnalysisSubgraphNode {
  { state, production_id, child_index: child_index & 0x7F, done }
}

///|
fn analysis_subgraph_node_compare(
  left : AnalysisSubgraphNode,
  other : AnalysisSubgraphNode,
) -> Int {
  if left.state < other.state {
    return -1
  }
  if left.state > other.state {
    return 1
  }
  if left.child_index < other.child_index {
    return -1
  }
  if left.child_index > other.child_index {
    return 1
  }
  if !left.done && other.done {
    return -1
  }
  if left.done && !other.done {
    return 1
  }
  if left.production_id < other.production_id {
    return -1
  }
  if left.production_id > other.production_id {
    return 1
  }
  0
}

///|
/// AnalysisSubgraph - A subset of the states in the parse table that are used
/// in constructing nodes with a certain symbol.
priv struct AnalysisSubgraph {
  symbol : Int
  start_states : Array[Int]
  nodes : Array[AnalysisSubgraphNode]
}

///|
/// Walk the subgraph for this non-terminal, tracking all of the possible
/// sequences of progress within the pattern.
fn Query::perform_analysis(
  self : Query,
  subgraphs : Array[AnalysisSubgraph],
  analysis : QueryAnalysis,
) -> Unit {
  let language = self.language
  let mut recursion_depth_limit = 0
  let mut prev_final_step_count = 0
  analysis.final_step_indices.clear()
  analysis.finished_parent_symbols.clear()
  let mut iteration = 0
  for ;; {
    if iteration == max_analysis_iteration_count {
      analysis.did_abort = true
      break
    }
    iteration += 1
    // If no further progress can be made within the current recursion depth
    // limit, then bump the depth limit by one, and continue to process the
    // states the exceeded the limit. But only allow this if progress has
    // been made since the last time the depth limit was increased.
    if analysis.states.length() == 0 {
      if analysis.deeper_states.length() > 0 &&
        analysis.final_step_indices.length() > prev_final_step_count {
        prev_final_step_count = analysis.final_step_indices.length()
        recursion_depth_limit += 1
        let states = analysis.states
        analysis.states = analysis.deeper_states
        analysis.deeper_states = states
        continue
      }
      break
    }
    analysis.next_states.clear()
    let mut j = 0
    while j < analysis.states.length() {
      let state = analysis.states[j]
      // For efficiency, it's important to avoid processing the same analysis
      // state more than once. To achieve this, keep the states in order of
      // ascending position within their hypothetical syntax trees. In each
      // iteration of this loop, start by advancing the states that have made
      // the least progress. Avoid advancing states that have already made
      // more progress.
      if analysis.next_states.length() > 0 {
        let comparison = analysis_state_compare(
          state,
          analysis.next_states[analysis.next_states.length() - 1],
        )
        if comparison == 0 {
          analysis_state_set_insert_sorted(analysis.next_states, state)
          j += 1
          continue
        } else if comparison > 0 {
          while j < analysis.states.length() {
            analysis_state_set_push(analysis.next_states, analysis.states[j])
            j += 1
          }
          break
        }
      }
      let top = state.top()
      let parse_state = top.parse_state
      let parent_symbol = top.parent_symbol
      let parent_field_id = top.field_id
      let child_index = top.child_index
      let step = self.steps[state.step_index]
      let (subgraph_index, exists) = search_sorted_by(
        subgraphs,
        s => s.symbol,
        parent_symbol,
      )
      if !exists {
        j += 1
        continue
      }
      let subgraph = subgraphs[subgraph_index]
      // Follow every possible path in the parse table, but only visit states
      // that are part of the subgraph for the current symbol.
      let lookahead_iterator = language.lookaheads(parse_state)
      while lookahead_iterator.next() {
        let sym = lookahead_iterator.current_symbol()
        let mut successor_state = parse_state
        let mut successor_child_index = child_index & 0x7F
        let actions = lookahead_iterator.actions()
        if actions.length() > 0 {
          match actions[actions.length() - 1] {
            Shift(state=shift_state, extra~, ..) =>
              if !extra {
                successor_state = shift_state
                successor_child_index = (successor_child_index + 1) & 0x7F
              }
            _ => continue
          }
        } else if lookahead_iterator.next_state() != 0 {
          successor_state = lookahead_iterator.next_state()
          successor_child_index = (successor_child_index + 1) & 0x7F
        } else {
          continue
        }
        let successor = subgraph_node(
          successor_state, 0, successor_child_index, false,
        )
        let (found_index, _) = search_sorted_with(subgraph.nodes, n => {
          analysis_subgraph_node_compare(n, successor)
        })
        let mut node_index = found_index
        while node_index < subgraph.nodes.length() {
          let node = subgraph.nodes[node_index]
          node_index += 1
          if node.state != successor.state ||
            node.child_index != successor.child_index {
            break
          }
          // Use the subgraph to determine what alias and field will
          // eventually be applied to this child node.
          let alias = language.alias_at(node.production_id, child_index)
          let visible_symbol = if alias != 0 {
            alias
          } else if language.symbol_metadata[sym].visible {
            language.public_symbol_map[sym]
          } else {
            0
          }
          let mut field_id = parent_field_id
          if field_id == 0 {
            let (field_map, field_map_end) = language.field_map(
              node.production_id,
            )
            for m in field_map..= language.token_count {
            // If this child is hidden, then descend into it and walk through
            // its children. If the top entry of the stack is at the end of its
            // rule, then that entry can be replaced. Otherwise, push a new
            // entry onto the stack.
            if !next_state.stack[top_index].done {
              if next_state.depth + 1 >= max_analysis_state_depth {
                analysis.did_abort = true
                continue
              }
              next_state.depth += 1
              top_index = next_state.top_index()
            }
            next_state.stack[top_index] = {
              parse_state,
              parent_symbol: sym,
              child_index: 0,
              field_id: field_id & 0x7FFF,
              done: false,
            }
            if next_state.recursion_depth() > recursion_depth_limit {
              analysis_state_set_insert_sorted(analysis.deeper_states, next_state)
              continue
            }
          }
          // Pop from the stack when this state reached the end of its current
          // syntax node.
          while next_state.depth > 0 && next_state.stack[top_index].done {
            next_state.depth -= 1
            top_index = next_state.top_index()
          }
          // If this hypothetical child did match the current step of the
          // query pattern, then advance to the next step at the current depth.
          // This involves skipping over any descendant steps of the current
          // child.
          // `next_state.step_index` is a `uint16_t`; `next_step_position`
          // tracks the `next_step` pointer, which upstream advances
          // separately for pass-through steps.
          let mut next_step = step
          let mut next_step_position = state.step_index
          if does_match {
            for ;; {
              next_state.step_index = (next_state.step_index + 1) & 0xFFFF
              next_step_position = next_state.step_index
              next_step = self.steps[next_step_position]
              if next_step.depth == pattern_done_marker ||
                next_step.depth <= step.depth {
                break
              }
            }
          } else if successor.state == parse_state {
            continue
          }
          for ;; {
            // Skip pass-through states. Although these states have
            // alternatives, they are only used to implement repetitions, and
            // query analysis does not need to process repetitions in order to
            // determine whether steps are possible and definite.
            if next_step.is_pass_through {
              next_state.step_index = (next_state.step_index + 1) & 0xFFFF
              next_step_position += 1
              next_step = self.steps[next_step_position]
              continue
            }
            // If the pattern is finished or hypothetical parent node is
            // complete, then record that matching can terminate at this step
            // of the pattern. Otherwise, add this state to the list of states
            // to process on the next iteration.
            if !next_step.is_dead_end {
              let did_finish_pattern = self.steps[next_state.step_index].depth !=
                step.depth
              if did_finish_pattern {
                insert_sorted_int(
                  analysis.finished_parent_symbols,
                  state.root_symbol,
                )
              } else if next_state.depth == 0 {
                insert_sorted_int(
                  analysis.final_step_indices,
                  next_state.step_index,
                )
              } else {
                analysis_state_set_insert_sorted(analysis.next_states, next_state)
              }
            }
            // If the state has advanced to a step with an alternative step,
            // then add another state at that alternative step. This process is
            // simpler than the process of actually matching a pattern during
            // query execution, because for the purposes of query analysis,
            // there is no need to process repetitions.
            if does_match &&
              next_step.alternative_index != none &&
              next_step.alternative_index > next_state.step_index {
              next_state.step_index = next_step.alternative_index
              next_step_position = next_state.step_index
              next_step = self.steps[next_step_position]
            } else {
              break
            }
          }
        }
      }
      j += 1
    }
    let states = analysis.states
    analysis.states = analysis.next_states
    analysis.next_states = states
  }
}

///|
/// `ts_query__analyze_patterns`: returns `None` if all patterns are valid,
/// or the byte offset of an impossible pattern step.
fn Query::analyze_patterns(self : Query) -> UInt? {
  let language = self.language
  let non_rooted_pattern_start_steps : Array[Int] = []
  for i, pattern in self.pattern_map {
    if !pattern.is_rooted {
      let step = self.steps[pattern.step_index]
      if step.symbol != wildcard_symbol {
        // An `Array(uint16_t)` upstream.
        non_rooted_pattern_start_steps.push(i & 0xFFFF)
      }
    }
  }
  // Walk forward through all of the steps in the query, computing some basic
  // information about each step. Mark all of the steps that contain captures,
  // and record the indices of all of the steps that have child steps.
  let parent_step_indices : Array[Int] = []
  for i in 0..= @language.language_version_with_reserved_words {
        // Look at the child steps to see if any aren't valid subtypes for
        // this supertype.
        let subtypes = language.subtypes(step.supertype_symbol)
        for j in (i + 1).. s == child_step.symbol)
            if !is_valid_subtype {
              for step_offset in self.step_offsets {
                if step_offset.step_index >= j {
                  return Some(step_offset.byte_offset)
                }
              }
            }
          }
        }
      }
    }
  }
  // For every parent symbol in the query, initialize an 'analysis subgraph'.
  // This subgraph lists all of the states in the parse table that are
  // directly involved in building subtrees for this symbol.
  //
  // In addition to the parent symbols in the query, construct subgraphs for
  // all of the hidden symbols in the grammar, because these might occur
  // within one of the parent nodes, such that their children appear to belong
  // to the parent.
  let subgraphs : Array[AnalysisSubgraph] = []
  let insert_subgraph = (symbol : Int) => {
    let (index, exists) = search_sorted_by(subgraphs, s => s.symbol, symbol)
    if !exists {
      subgraphs.insert(index, { symbol, start_states: [], nodes: [] })
    }
  }
  for parent_step_index in parent_step_indices {
    insert_subgraph(self.steps[parent_step_index].symbol)
  }
  for sym in (language.token_count & 0xFFFF)..<(language.symbol_count & 0xFFFF) {
    if !language.symbol_metadata_of(sym).visible {
      insert_subgraph(sym)
    }
  }
  // Scan the parse table to find the data needed to populate these
  // subgraphs. Collect three things during this scan:
  //   1) All of the parse states where one of these symbols can start.
  //   2) All of the parse states where one of these symbols can end, along
  //      with information about the node that would be created.
  //   3) A list of predecessor states for each state.
  let predecessor_map = StatePredecessorMap::new(language)
  for state in 1..<(language.state_count & 0xFFFF) {
    let lookahead_iterator = language.lookaheads(state)
    while lookahead_iterator.next() {
      let actions = lookahead_iterator.actions()
      if actions.length() > 0 {
        for action in actions {
          match action {
            Reduce(symbol~, child_count~, production_id~, ..) =>
              for alias in language.aliases_for_symbol(symbol) {
                let (subgraph_index, exists) = search_sorted_by(
                  subgraphs,
                  s => s.symbol,
                  alias,
                )
                if exists {
                  let subgraph = subgraphs[subgraph_index]
                  if subgraph.nodes.length() == 0 ||
                    subgraph.nodes[subgraph.nodes.length() - 1].state != state {
                    subgraph.nodes.push(
                      subgraph_node(state, production_id, child_count, true),
                    )
                  }
                }
              }
            Shift(state=next_state, extra=false, ..) =>
              predecessor_map.add(next_state, state)
            _ => ()
          }
        }
      } else if lookahead_iterator.next_state() != 0 {
        if lookahead_iterator.next_state() != state {
          predecessor_map.add(lookahead_iterator.next_state(), state)
        }
        if language.state_is_primary(state) {
          for alias in language.aliases_for_symbol(
            lookahead_iterator.current_symbol(),
          ) {
            let (subgraph_index, exists) = search_sorted_by(
              subgraphs,
              s => s.symbol,
              alias,
            )
            if exists {
              let subgraph = subgraphs[subgraph_index]
              if subgraph.start_states.length() == 0 ||
                subgraph.start_states[subgraph.start_states.length() - 1] !=
                state {
                subgraph.start_states.push(state)
              }
            }
          }
        }
      }
    }
  }
  // For each subgraph, compute the preceding states by walking backward from
  // the end states using the predecessor map.
  let mut i = 0
  while i < subgraphs.length() {
    let subgraph = subgraphs[i]
    if subgraph.nodes.length() == 0 {
      ignore(subgraphs.remove(i))
      continue
    }
    let next_nodes = subgraph.nodes.copy()
    while next_nodes.pop() is Some(node) {
      if node.child_index > 1 {
        for predecessor in predecessor_map.get(node.state) {
          let predecessor_node = subgraph_node(
            predecessor,
            node.production_id,
            node.child_index - 1,
            false,
          )
          let (index, exists) = search_sorted_with(subgraph.nodes, n => {
            analysis_subgraph_node_compare(n, predecessor_node)
          })
          if !exists {
            subgraph.nodes.insert(index, predecessor_node)
            next_nodes.push(predecessor_node)
          }
        }
      }
    }
    i += 1
  }
  // For each non-terminal pattern, determine if the pattern can successfully
  // match, and identify all of the possible children within the pattern
  // where matching could fail.
  let analysis = QueryAnalysis::new()
  for full_parent_step_index in parent_step_indices {
    // `uint16_t parent_step_index` upstream.
    let parent_step_index = full_parent_step_index & 0xFFFF
    let parent_depth = self.steps[parent_step_index].depth
    let parent_symbol = self.steps[parent_step_index].symbol
    if parent_symbol == @language.ts_builtin_sym_error {
      continue
    }
    // Find the subgraph that corresponds to this pattern's root symbol. If
    // the pattern's root symbol is a terminal, then return an error.
    let (subgraph_index, exists) = search_sorted_by(
      subgraphs,
      s => s.symbol,
      parent_symbol,
    )
    if !exists {
      let first_child_step_index = parent_step_index + 1
      let (j, _) = search_sorted_by(
        self.step_offsets,
        o => o.step_index,
        first_child_step_index,
      )
      return Some(self.step_offsets[j].byte_offset)
    }
    // Initialize an analysis state at every parse state in the table where
    // this parent symbol can occur.
    let subgraph = subgraphs[subgraph_index]
    analysis.states.clear()
    analysis.deeper_states.clear()
    for parse_state in subgraph.start_states {
      analysis_state_set_push(
        analysis.states,
        AnalysisState::new(
          (parent_step_index + 1) & 0xFFFF,
          { parse_state, parent_symbol, child_index: 0, field_id: 0, done: false },
          parent_symbol,
        ),
      )
    }
    analysis.did_abort = false
    self.perform_analysis(subgraphs, analysis)
    // If this pattern could not be fully analyzed, then every step should be
    // considered fallible.
    if analysis.did_abort {
      for j in (parent_step_index + 1).. 0 {
        analysis.final_step_indices[analysis.final_step_indices.length() - 1]
      } else {
        // If there isn't a final step, then that means the parent step itself
        // is unreachable.
        parent_step_index
      }
      let (found, _) = search_sorted_by(
        self.step_offsets,
        o => o.step_index,
        impossible_step_index,
      )
      let j = if found >= self.step_offsets.length() {
        self.step_offsets.length() - 1
      } else {
        found
      }
      return Some(self.step_offsets[j].byte_offset)
    }
    // Mark as fallible any step where a match terminated. Later, this
    // property will be propagated to all of the step's predecessors.
    for final_step_index in analysis.final_step_indices {
      let step = self.steps[final_step_index]
      if step.depth != pattern_done_marker &&
        step.depth > parent_depth &&
        !step.is_dead_end {
        step.parent_pattern_guaranteed = false
        step.root_pattern_guaranteed = false
      }
    }
  }
  // Mark as indefinite any step with captures that are used in predicates.
  let predicate_capture_ids : Array[Int] = []
  for pattern in self.patterns {
    // Gather all of the captures that are used in predicates for this
    // pattern.
    predicate_capture_ids.clear()
    let start = pattern.predicate_steps.offset
    for j in start..<(start + pattern.predicate_steps.length) {
      let step = self.predicate_steps[j]
      if step.type_ == Capture {
        // `uint16_t value_id = step->value_id`.
        insert_sorted_int(predicate_capture_ids, step.value_id & 0xFFFF)
      }
    }
    // Find all of the steps that have these captures.
    let start = pattern.steps.offset
    for j in start..<(start + pattern.steps.length) {
      let step = self.steps[j]
      for k in 0.. x, capture_id)
        if exists {
          step.root_pattern_guaranteed = false
          break
        }
      }
    }
  }
  // Propagate fallibility. If a pattern is fallible at a given step, then it
  // is fallible at all of its preceding steps.
  let mut done = self.steps.length() == 0
  while !done {
    done = true
    for i = self.steps.length() - 1; i > 0; i = i - 1 {
      let mut step = self.steps[i]
      if step.depth == pattern_done_marker {
        continue
      }
      // Determine if this step is definite or has definite alternatives.
      let mut parent_pattern_guaranteed = false
      for ;; {
        if step.root_pattern_guaranteed {
          parent_pattern_guaranteed = true
          break
        }
        if step.alternative_index == none || step.alternative_index < i {
          break
        }
        step = self.steps[step.alternative_index]
      }
      // If not, mark its predecessor as indefinite.
      if !parent_pattern_guaranteed {
        let prev_step = self.steps[i - 1]
        if !prev_step.is_dead_end &&
          prev_step.depth != pattern_done_marker &&
          prev_step.root_pattern_guaranteed {
          prev_step.root_pattern_guaranteed = false
          done = false
        }
      }
    }
  }
  // Determine which repetition symbols in this language have the possibility
  // of matching non-rooted patterns in this query. These repetition symbols
  // prevent certain optimizations with range restrictions.
  analysis.did_abort = false
  for pattern_entry_index in non_rooted_pattern_start_steps {
    let pattern_entry = self.pattern_map[pattern_entry_index]
    analysis.states.clear()
    analysis.deeper_states.clear()
    for subgraph in subgraphs {
      let metadata = language.symbol_metadata_of(subgraph.symbol)
      if metadata.visible || metadata.named {
        continue
      }
      for parse_state in subgraph.start_states {
        analysis_state_set_push(
          analysis.states,
          AnalysisState::new(
            pattern_entry.step_index,
            {
              parse_state,
              parent_symbol: subgraph.symbol,
              child_index: 0,
              field_id: 0,
              done: false,
            },
            subgraph.symbol,
          ),
        )
      }
    }
    self.perform_analysis(subgraphs, analysis)
    if analysis.finished_parent_symbols.length() > 0 {
      self.patterns[pattern_entry.pattern_index].is_non_local = true
    }
    for symbol in analysis.finished_parent_symbols {
      insert_sorted_int(self.repeat_symbols_with_rootless_patterns, symbol)
    }
  }
  None
}