// Port of the `TSQueryCursor` in tree-sitter lib/src/query.c.
///|
/// `TSQueryCursorState`: what a progress callback can observe.
pub(all) struct QueryCursorState {
current_byte_offset : UInt
} derive(Eq, Debug)
///|
/// `TSQueryCursorOptions`.
pub(all) struct QueryCursorOptions {
progress_callback : ((QueryCursorState) -> Bool)?
}
///|
/// `TSQueryMatch`. `captures` is a copy of the match's capture list.
pub(all) struct QueryMatch {
id : UInt
pattern_index : Int
captures : Array[QueryCapture]
}
///|
let max_range : @runtime.Range = {
start_point: { row: 0, column: 0 },
end_point: @runtime.point_max,
start_byte: 0,
end_byte: 0xFFFFFFFFU,
}
///|
/// TSQueryCursor - A stateful struct used to execute a query on a tree.
pub struct QueryCursor {
priv mut query : Query?
priv mut cursor : @runtime.TreeCursor?
priv states : Array[QueryState]
priv finished_states : Array[QueryState]
// Tracks how much of finished_states is in heap order. Elements at indices
// < this value satisfy the min-heap property; elements >= this value are
// newly pushed and need to be sifted into place. Only used by
// `next_capture`.
priv mut finished_states_heap_size : Int
priv capture_list_pool : CaptureListPool
priv mut depth : UInt
priv mut max_start_depth : UInt
priv mut included_range : @runtime.Range
priv mut containing_range : @runtime.Range
priv mut next_state_id : UInt
priv mut next_finished_state_id : UInt
priv mut query_options : QueryCursorOptions?
priv mut query_state : QueryCursorState
priv mut work_count : Int
priv mut on_visible_node : Bool
priv mut ascending : Bool
priv mut halted : Bool
priv mut did_exceed_match_limit : Bool
}
///|
/// `ts_query_cursor_new`.
pub fn QueryCursor::new() -> QueryCursor {
{
query: None,
cursor: None,
did_exceed_match_limit: false,
ascending: false,
halted: false,
states: [],
finished_states: [],
finished_states_heap_size: 0,
capture_list_pool: CaptureListPool::new(),
depth: 0,
included_range: max_range,
containing_range: max_range,
max_start_depth: 0xFFFFFFFFU,
next_state_id: 0,
next_finished_state_id: 0,
query_options: None,
query_state: { current_byte_offset: 0 },
work_count: 0,
on_visible_node: false,
}
}
///|
fn QueryCursor::q(self : QueryCursor) -> Query {
self.query.unwrap()
}
///|
fn QueryCursor::tree_cursor(self : QueryCursor) -> @runtime.TreeCursor {
self.cursor.unwrap()
}
///|
/// `ts_query_cursor_did_exceed_match_limit`.
pub fn QueryCursor::did_exceed_match_limit(self : QueryCursor) -> Bool {
self.did_exceed_match_limit
}
///|
/// `ts_query_cursor_match_limit`.
pub fn QueryCursor::match_limit(self : QueryCursor) -> UInt {
self.capture_list_pool.max_capture_list_count
}
///|
/// `ts_query_cursor_set_match_limit`.
pub fn QueryCursor::set_match_limit(self : QueryCursor, limit : UInt) -> Unit {
self.capture_list_pool.max_capture_list_count = limit
}
///|
/// `ts_query_cursor_exec`.
pub fn QueryCursor::exec(
self : QueryCursor,
query : Query,
node : @runtime.Node,
) -> Unit {
self.states.clear()
self.finished_states.clear()
self.finished_states_heap_size = 0
match self.cursor {
Some(cursor) => cursor.reset(node)
None => self.cursor = Some(@runtime.TreeCursor::new(node))
}
self.capture_list_pool.reset()
self.on_visible_node = true
self.next_state_id = 0
self.next_finished_state_id = 0
self.depth = 0
self.ascending = false
self.halted = false
self.query = Some(query)
self.did_exceed_match_limit = false
self.work_count = 0
self.query_options = None
self.query_state = { current_byte_offset: 0 }
}
///|
/// `ts_query_cursor_exec_with_options`.
pub fn QueryCursor::exec_with_options(
self : QueryCursor,
query : Query,
node : @runtime.Node,
query_options : QueryCursorOptions?,
) -> Unit {
self.exec(query, node)
if query_options is Some(_) {
self.query_options = query_options
self.query_state = { current_byte_offset: 0 }
}
}
///|
/// `ts_query_cursor_set_byte_range`.
pub fn QueryCursor::set_byte_range(
self : QueryCursor,
start_byte : UInt,
end_byte : UInt,
) -> Bool {
let end_byte = if end_byte == 0 { 0xFFFFFFFFU } else { end_byte }
if start_byte > end_byte {
return false
}
self.included_range = { ..self.included_range, start_byte, end_byte }
true
}
///|
/// `ts_query_cursor_set_point_range`.
pub fn QueryCursor::set_point_range(
self : QueryCursor,
start_point : @runtime.Point,
end_point : @runtime.Point,
) -> Bool {
let end_point = if end_point.row == 0 && end_point.column == 0 {
@runtime.point_max
} else {
end_point
}
if @runtime.point_gt(start_point, end_point) {
return false
}
self.included_range = { ..self.included_range, start_point, end_point }
true
}
///|
/// `ts_query_cursor_set_containing_byte_range`.
pub fn QueryCursor::set_containing_byte_range(
self : QueryCursor,
start_byte : UInt,
end_byte : UInt,
) -> Bool {
let end_byte = if end_byte == 0 { 0xFFFFFFFFU } else { end_byte }
if start_byte > end_byte {
return false
}
self.containing_range = { ..self.containing_range, start_byte, end_byte }
true
}
///|
/// `ts_query_cursor_set_containing_point_range`.
pub fn QueryCursor::set_containing_point_range(
self : QueryCursor,
start_point : @runtime.Point,
end_point : @runtime.Point,
) -> Bool {
let end_point = if end_point.row == 0 && end_point.column == 0 {
@runtime.point_max
} else {
end_point
}
if @runtime.point_gt(start_point, end_point) {
return false
}
self.containing_range = { ..self.containing_range, start_point, end_point }
true
}
///|
/// `ts_query_cursor_set_max_start_depth`.
pub fn QueryCursor::set_max_start_depth(
self : QueryCursor,
max_start_depth : UInt,
) -> Unit {
self.max_start_depth = max_start_depth
}
///|
fn QueryCursor::push_finished_state(self : QueryCursor, state : QueryState) -> Unit {
state.heap_insert_order = self.next_finished_state_id
self.next_finished_state_id += 1
self.finished_states.push(state)
}
///|
fn QueryCursor::heapify_finished_states(self : QueryCursor) -> Unit {
while self.finished_states_heap_size < self.finished_states.length() {
finished_state_sift_up(
self.finished_states,
self.finished_states_heap_size,
self.capture_list_pool,
)
self.finished_states_heap_size += 1
}
}
///|
/// The result of `ts_query_cursor__first_in_progress_capture`.
priv struct InProgressCapture {
state_index : Int
byte_offset : UInt
pattern_index : Int
is_definite : Bool
}
///|
/// Search through all of the in-progress states, and find the captured node
/// that occurs earliest in the document. With `want_definite`, also report
/// whether the capture is definite; otherwise skip states whose next step is
/// guaranteed.
fn QueryCursor::first_in_progress_capture(
self : QueryCursor,
want_definite : Bool,
) -> (Bool, InProgressCapture) {
let mut result = false
let mut state_index = -1
let mut byte_offset = 0xFFFFFFFFU
let mut pattern_index = 0xFFFFFFFF
let mut is_definite = false
let mut i = 0
while i < self.states.length() {
let state = self.states[i]
if state.dead {
i += 1
continue
}
let captures = self.capture_list_pool.get(state.capture_list_id)
if state.consumed_capture_count >= captures.length() {
i += 1
continue
}
let node = captures[state.consumed_capture_count].node
if node.end_byte() <= self.included_range.start_byte ||
@runtime.point_lte(node.end_point(), self.included_range.start_point) {
state.set_consumed_capture_count(state.consumed_capture_count + 1)
continue
}
let node_start_byte = node.start_byte()
if !result ||
node_start_byte < byte_offset ||
(node_start_byte == byte_offset && state.pattern_index < pattern_index) {
let step = self.q().steps[state.step_index]
if want_definite {
// We're being a bit conservative here by asserting that the following
// step is not immediate, because this capture might end up being
// discarded if the following symbol in the tree isn't the required
// symbol for this step.
is_definite = step.root_pattern_guaranteed && !step.is_immediate
} else if step.root_pattern_guaranteed {
i += 1
continue
}
result = true
state_index = i
byte_offset = node_start_byte
pattern_index = state.pattern_index
}
i += 1
}
(result, { state_index, byte_offset, pattern_index, is_definite })
}
///|
/// Determine which node is first in a depth-first traversal.
fn compare_nodes(left : @runtime.Node, right : @runtime.Node) -> Int {
if !left.same_id(right) {
let left_start = left.start_byte()
let right_start = right.start_byte()
if left_start < right_start {
return -1
}
if left_start > right_start {
return 1
}
let left_node_count = left.end_byte()
let right_node_count = right.end_byte()
if left_node_count > right_node_count {
return -1
}
if left_node_count < right_node_count {
return 1
}
}
0
}
///|
/// Determine if either state contains a superset of the other state's
/// captures: `(left_contains_right, right_contains_left)`.
fn QueryCursor::compare_captures(
self : QueryCursor,
left_state : QueryState,
right_state : QueryState,
) -> (Bool, Bool) {
let left_captures = self.capture_list_pool.get(left_state.capture_list_id)
let right_captures = self.capture_list_pool.get(right_state.capture_list_id)
let mut left_contains_right = true
let mut right_contains_left = true
let mut i = 0
let mut j = 0
for ;; {
if i < left_captures.length() {
if j < right_captures.length() {
let left = left_captures[i]
let right = right_captures[j]
if left.node.same_id(right.node) && left.index == right.index {
i += 1
j += 1
} else {
match compare_nodes(left.node, right.node) {
-1 => {
right_contains_left = false
i += 1
}
1 => {
left_contains_right = false
j += 1
}
_ => {
right_contains_left = false
left_contains_right = false
i += 1
j += 1
}
}
}
} else {
right_contains_left = false
break
}
} else {
if j < right_captures.length() {
left_contains_right = false
}
break
}
}
(left_contains_right, right_contains_left)
}
///|
/// Order two in-progress states for the longest-match dedup pass. Within a
/// (start_depth, pattern_index) group, states with no captures sort first, as
/// they are a subset of every other state. The rest sort by the start byte of
/// their first capture.
fn QueryCursor::state_precedes(
self : QueryCursor,
a : QueryState,
b : QueryState,
) -> Bool {
if a.start_depth != b.start_depth {
return a.start_depth < b.start_depth
}
if a.pattern_index != b.pattern_index {
return a.pattern_index < b.pattern_index
}
let a_caps = self.capture_list_pool.get(a.capture_list_id)
let b_caps = self.capture_list_pool.get(b.capture_list_id)
if (a_caps.length() == 0) != (b_caps.length() == 0) {
return a_caps.length() == 0
}
if a_caps.length() == 0 {
return false
}
a_caps[0].node.start_byte() < b_caps[0].node.start_byte()
}
///|
/// Stable-sort the in-progress states with the order dictated by
/// `state_precedes` (insertion sort, as upstream).
fn QueryCursor::sort_states_by_capture(self : QueryCursor) -> Unit {
let states = self.states
for i in 1.. 0 && self.state_precedes(key, states[j - 1])) {
break
}
}
states[j] = key
}
}
///|
fn QueryCursor::add_state(self : QueryCursor, pattern : PatternEntry) -> Unit {
let step = self.q().steps[pattern.step_index]
let start_depth = (self.depth - step.depth.reinterpret_as_uint()).reinterpret_as_int() &
0xFFFF
// Keep the states array in ascending order of start_depth and
// pattern_index, so that it can be processed more efficiently elsewhere.
let mut index = self.states.length()
while index > 0 {
let prev_state = self.states[index - 1]
if prev_state.start_depth < start_depth {
break
}
if prev_state.start_depth == start_depth {
// Avoid inserting an unnecessary duplicate state, which would be
// immediately pruned by the longest-match criteria.
if prev_state.pattern_index == pattern.pattern_index &&
prev_state.step_index == pattern.step_index {
return
}
if prev_state.pattern_index <= pattern.pattern_index {
break
}
}
index -= 1
}
self.states.insert(index, {
id: 0xFFFFFFFFU,
capture_list_id: capture_list_none,
heap_insert_order: 0xFFFFFFFFU,
step_index: pattern.step_index,
pattern_index: pattern.pattern_index,
start_depth,
consumed_capture_count: 0,
seeking_immediate_match: true,
has_in_progress_alternatives: false,
needs_parent: step.depth == 1,
dead: false,
skipped_quantifier: false,
})
}
///|
/// Acquire a capture list for this state. If there are no capture lists left
/// in the pool, this will steal the capture list from another existing state,
/// and mark that other state as 'dead'.
fn QueryCursor::prepare_to_capture(
self : QueryCursor,
state : QueryState,
state_index_to_preserve : Int,
) -> Array[QueryCapture]? {
if state.capture_list_id == capture_list_none {
state.capture_list_id = self.capture_list_pool.acquire()
// If there are no capture lists left in the pool, then terminate
// whichever state has captured the earliest node in the document, and
// steal its capture list.
if state.capture_list_id == capture_list_none {
self.did_exceed_match_limit = true
let (found, first) = self.first_in_progress_capture(false)
if found && first.state_index != state_index_to_preserve {
let other_state = self.states[first.state_index]
state.capture_list_id = other_state.capture_list_id
other_state.capture_list_id = capture_list_none
other_state.dead = true
let list = self.capture_list_pool.get(state.capture_list_id)
clear_capture_list(list)
return Some(list)
} else {
return None
}
}
}
Some(self.capture_list_pool.get(state.capture_list_id))
}
///|
fn QueryCursor::capture(
self : QueryCursor,
state : QueryState,
step : QueryStep,
node : @runtime.Node,
) -> Unit {
if state.dead {
return
}
guard self.prepare_to_capture(state, -1) is Some(capture_list) else {
state.dead = true
return
}
for j in 0.. QueryState? {
let state = self.states[state_index]
let copy = state.copy()
copy.capture_list_id = capture_list_none
// If the state has captures, copy its capture list.
if state.capture_list_id != capture_list_none {
guard self.prepare_to_capture(copy, state_index) is Some(new_captures) else {
return None
}
let old_captures = self.capture_list_pool.get(state.capture_list_id)
for capture in old_captures {
new_captures.push(capture)
}
}
self.states.insert(state_index + 1, copy)
Some(copy)
}
///|
fn QueryCursor::should_descend(
self : QueryCursor,
node_intersects_range : Bool,
) -> Bool {
if node_intersects_range && self.depth < self.max_start_depth {
return true
}
// If there are in-progress matches whose remaining steps occur deeper in
// the tree, then descend.
for state in self.states {
let next_step = self.q().steps[state.step_index]
if next_step.depth != pattern_done_marker &&
(state.start_depth + next_step.depth).reinterpret_as_uint() > self.depth {
return true
}
}
if self.depth >= self.max_start_depth {
return false
}
// If the current node is hidden, then a non-rooted pattern might match one
// if its roots inside of this node, and match another of its roots as part
// of a sibling node, so we may need to descend.
if !self.on_visible_node {
// Descending into a repetition node outside of the range can be
// expensive, because these nodes can have many visible children. Avoid
// descending into repetition nodes unless we have already determined that
// this query can match rootless patterns inside of this type of
// repetition node.
let subtree = self.tree_cursor().current_subtree()
if subtree.is_repetition() {
let (_, exists) = search_sorted_by(
self.q().repeat_symbols_with_rootless_patterns,
x => x,
subtree.symbol(),
)
return exists
}
return true
}
false
}
///|
fn range_intersects(a : @runtime.Range, b : @runtime.Range) -> Bool {
let is_empty = a.start_byte == a.end_byte
(a.end_byte > b.start_byte || (is_empty && a.end_byte == b.start_byte)) &&
(@runtime.point_gt(a.end_point, b.start_point) ||
(is_empty && @runtime.point_eq(a.end_point, b.start_point))) &&
a.start_byte < b.end_byte &&
@runtime.point_lt(a.start_point, b.end_point)
}
///|
fn range_within(a : @runtime.Range, b : @runtime.Range) -> Bool {
a.start_byte >= b.start_byte &&
@runtime.point_gte(a.start_point, b.start_point) &&
a.end_byte <= b.end_byte &&
@runtime.point_lte(a.end_point, b.end_point)
}
///|
fn node_range(node : @runtime.Node) -> @runtime.Range {
{
start_point: node.start_point(),
end_point: node.end_point(),
start_byte: node.start_byte(),
end_byte: node.end_byte(),
}
}
///|
/// Walk the tree, processing patterns until at least one pattern finishes.
/// If one or more patterns finish, return `true` and store their states in the
/// `finished_states` array. Multiple patterns can finish on the same node. If
/// there are no more matches, return `false`.
fn QueryCursor::advance(self : QueryCursor, stop_on_definite_step : Bool) -> Bool {
let query = self.q()
let mut did_match = false
for ;; {
if self.halted {
while self.states.pop() is Some(state) {
self.capture_list_pool.release(state.capture_list_id)
}
}
if did_match || self.halted {
return did_match
}
// Consult the progress callback after a bounded amount of work. Only
// iterations that do work are charged.
self.work_count += 1 + self.states.length()
if self.work_count >= work_per_query_callback_check {
self.work_count = 0
if self.query_options is Some(options) &&
options.progress_callback is Some(callback) {
self.query_state = {
current_byte_offset: self.tree_cursor().current_node().start_byte(),
}
if callback(self.query_state) {
// Halt the same way reaching the end of the tree does. The next
// iteration discards the in-progress states, so only finished
// matches are returned.
self.halted = true
continue
}
}
}
if self.ascending {
// Exit the current node.
if self.on_visible_node {
// After leaving a node, remove any states that cannot make further
// progress.
let mut deleted_count = 0
let n = self.states.length()
for i in 0.. self.depth ||
self.depth == 0) {
// If a state completed its pattern inside of this node, but was
// deferred from finishing in order to search for longer matches,
// mark it as finished.
self.push_finished_state(state)
did_match = true
deleted_count += 1
} else if step.depth != pattern_done_marker &&
(state.start_depth + step.depth).reinterpret_as_uint() > self.depth {
// If a state needed to match something within this node, then
// remove that state as it has failed to match.
self.capture_list_pool.release(state.capture_list_id)
deleted_count += 1
} else if deleted_count > 0 {
self.states[i - deleted_count] = state
}
}
self.states.truncate(n - deleted_count)
}
// Leave this node by stepping to its next sibling or to its parent.
match self.tree_cursor().goto_next_sibling_internal() {
StepVisible => {
if !self.on_visible_node {
self.depth += 1
self.on_visible_node = true
}
self.ascending = false
}
StepHidden => {
if self.on_visible_node {
self.depth -= 1
self.on_visible_node = false
}
self.ascending = false
}
StepNone =>
if self.tree_cursor().goto_parent() {
self.depth -= 1
} else {
self.halted = true
}
}
} else {
// Enter a new node.
let cursor = self.tree_cursor()
let node = cursor.current_node()
let parent_node = cursor.parent_node()
let parent_intersects_range = parent_node.is_null() ||
range_intersects(node_range(parent_node), self.included_range)
let node_range = node_range(node)
let node_intersects_range = parent_intersects_range &&
range_intersects(node_range, self.included_range)
let node_intersects_containing_range = range_intersects(
node_range,
self.containing_range,
)
let node_within_containing_range = range_within(
node_range,
self.containing_range,
)
if node_within_containing_range && self.on_visible_node {
let symbol = node.symbol()
let is_named = node.is_named()
let is_missing = node.is_missing()
let status = cursor.current_status(8)
let field_id = status.field_id
let has_later_siblings = status.has_later_siblings
let has_later_named_siblings = status.has_later_named_siblings
let can_have_later_siblings_with_this_field = status.can_have_later_siblings_with_this_field
let supertypes = status.supertypes
let supertype_count = supertypes.length()
let node_is_error = symbol == @language.ts_builtin_sym_error
let parent_is_error = !parent_node.is_null() &&
parent_node.symbol() == @language.ts_builtin_sym_error
// Add new states for any patterns whose root node is a wildcard.
if !node_is_error {
for i in 0.. 0) &&
start_depth <= self.max_start_depth {
self.add_state(pattern)
}
}
}
// Add new states for any patterns whose root node matches this node.
let (found, first_index) = query.pattern_map_search(symbol)
if found {
let mut i = first_index
let mut pattern = query.pattern_map[i]
let mut step = query.steps[pattern.step_index]
let start_depth = self.depth - step.depth.reinterpret_as_uint()
for ;; {
// If this node matches the first step of the pattern, then add a
// new state at the start of this pattern.
if (if pattern.is_rooted {
node_intersects_range
} else {
parent_intersects_range && !parent_is_error
}) &&
(step.field == 0 || field_id == step.field) &&
start_depth <= self.max_start_depth {
self.add_state(pattern)
}
// Advance to the next pattern whose root node matches this node.
i += 1
if i == query.pattern_map.length() {
break
}
pattern = query.pattern_map[i]
step = query.steps[pattern.step_index]
if step.symbol != symbol {
break
}
}
}
// Update all of the in-progress states with current node.
let mut j = 0
let mut copy_count = 0
while j < self.states.length() {
let state = self.states[j]
let step = query.steps[state.step_index]
state.has_in_progress_alternatives = false
copy_count = 0
// Check that the node matches all of the criteria for the next step
// of the pattern.
if (state.start_depth + step.depth).reinterpret_as_uint() != self.depth {
j += 1 + copy_count
continue
}
// Determine if this node matches this step of the pattern, and also
// if this node can have later siblings that match this step of the
// pattern.
let mut node_does_match = false
if step.symbol == wildcard_symbol {
if step.is_missing {
node_does_match = is_missing
} else {
node_does_match = !node_is_error && (is_named || !step.is_named)
}
} else {
node_does_match = symbol == step.symbol &&
(!step.is_missing || is_missing)
}
let mut later_sibling_can_match = has_later_siblings
if (step.is_immediate && is_named && !state.skipped_quantifier) ||
state.seeking_immediate_match {
later_sibling_can_match = false
}
if step.is_last_child && has_later_named_siblings {
node_does_match = false
}
if step.supertype_symbol != 0 {
let mut has_supertype = false
for k in 0.. 0) {
break
}
}
let skipped_wildcard_step = query.steps[skipped_wildcard_index]
if skipped_wildcard_step.capture_ids[0] != none {
self.capture(state, skipped_wildcard_step, parent)
}
}
}
// If the current node is captured in this pattern, add it to the
// capture list.
if step.capture_ids[0] != none {
self.capture(state, step, node)
}
if state.dead {
ignore(self.states.remove(j))
j -= 1
j += 1 + copy_count
continue
}
// Advance this state to the next step of its pattern
// (`step_index` is a `uint16_t`).
state.step_index = (state.step_index + 1) & 0xFFFF
let next_step = query.steps[state.step_index]
// For a given step, if the current symbol is the wildcard symbol,
// `_`, and it is **not** named, meaning it should capture anonymous
// nodes, **and** the next step is immediate, we reuse the
// `seeking_immediate_match` flag to indicate that we are looking
// for an immediate match due to an unnamed wildcard symbol.
if step.symbol == wildcard_symbol &&
!step.is_named &&
next_step.is_immediate {
state.seeking_immediate_match = true
} else {
state.seeking_immediate_match = false
}
// The zero-skip's vacuous-anchor exemption only covers the immediate
// step it lands on. Once the state advances, a later anchor is
// normal.
state.skipped_quantifier = false
if stop_on_definite_step && next_step.root_pattern_guaranteed {
did_match = true
}
// If this state's next step has an alternative step, then copy the
// state in order to pursue both alternatives. The alternative step
// itself may have an alternative, so this is an interactive process.
let mut end_index = j + 1
let mut k = j
while k < end_index {
let child_state = self.states[k]
let child_step = query.steps[child_state.step_index]
if child_step.alternative_index != none {
// A "dead-end" step exists only to add a non-sequential jump
// into the step sequence, via its alternative index. When a
// state reaches a dead-end step, it jumps straight to the step's
// alternative.
if child_step.is_dead_end {
child_state.step_index = child_step.alternative_index
continue
}
// A "pass-through" step exists only to add a branch into the
// step sequence, via its alternative_index. When a state
// reaches a pass-through step, it splits in order to process the
// alternative step, and then it advances to the next step.
let mut revisit = false
if child_step.is_pass_through {
child_state.step_index = (child_state.step_index + 1) & 0xFFFF
revisit = true
}
// A `?`/`*` zero-skip past a step that carries a trailing
// last-child anchor transfers that requirement to the last
// matched node. The skip is only valid if that node really is
// the last named child.
if child_step.alternative_is_skip &&
child_step.is_last_child &&
has_later_named_siblings {
if !revisit {
k += 1
}
continue
}
if self.copy_state(k) is Some(copy) {
end_index += 1
copy_count += 1
copy.step_index = child_step.alternative_index
if child_step.is_pass_through {
copy.seeking_immediate_match = true
}
// Taking a `?`/`*` zero-skip means the quantified subpattern
// matched nothing. How an adjacent anchor behaves then depends
// on where it sat:
if child_step.alternative_is_skip {
if !child_step.is_immediate {
let skip_target = query.steps[child_step.alternative_index]
// No leading anchor on the skipped step, so an
// immediately-following anchor on the skip target is
// vacuous (`Q* . B` with zero `Q` lets `B` match
// anywhere).
copy.skipped_quantifier = skip_target.depth ==
child_step.depth
} else if query.steps[child_state.step_index - 1].depth <
child_step.depth {
// The skipped step was the parent's first child pattern
// and carried a leading *boundary* anchor (`(P . Q* Y)`).
// Transfer the first-child requirement to the skip target
// so it survives the empty run: `Y` must still be the
// parent's first named child.
copy.seeking_immediate_match = true
}
// Otherwise the skipped step carried a leading *between*
// anchor (`A . Q* ...`): with zero `Q` that adjacency
// vanishes, while the skip target's own anchor, if any,
// still applies (`A . Q* . B` stays adjacent).
}
}
if revisit {
continue
}
}
k += 1
}
j += 1 + copy_count
}
// Order states by capture position so the dedup pass below can stop
// scanning a group once the remaining states are disjoint from the
// current one.
self.sort_states_by_capture()
let mut j = 0
while j < self.states.length() {
let state = self.states[j]
if state.dead {
ignore(self.states.remove(j))
continue
}
// Enforce the longest-match criteria. When a query pattern contains
// optional or repeated nodes, this is necessary to avoid multiple
// redundant states, where one state has a strict subset of another
// state's captures.
let mut did_remove = false
let mut k = j + 1
while k < self.states.length() {
let other_state = self.states[k]
// Query states are kept in ascending order of start_depth and
// pattern_index, and in ascending order of first-capture position
// within each such group. Since the longest-match criteria is only
// used for deduping matches of the same pattern and root node, we
// only need to perform pairwise comparisons within a small slice
// of the states array.
if other_state.start_depth != state.start_depth ||
other_state.pattern_index != state.pattern_index {
break
}
// States in a group acquire their first capture in tree-traversal
// order. Once `other_state`'s captures begin at or after where
// `state`'s captures end, `other_state` (and every state after it
// in the group) is disjoint from `state`.
let state_captures = self.capture_list_pool.get(state.capture_list_id)
let other_captures = self.capture_list_pool.get(
other_state.capture_list_id,
)
if state_captures.length() > 0 &&
other_captures.length() > 0 &&
other_captures[0].node.start_byte() >=
state_captures[state_captures.length() - 1].node.end_byte() {
break
}
let (left_contains_right, right_contains_left) = self.compare_captures(
state, other_state,
)
if left_contains_right {
if state.step_index == other_state.step_index &&
(other_state.seeking_immediate_match ||
!state.seeking_immediate_match) {
self.capture_list_pool.release(other_state.capture_list_id)
ignore(self.states.remove(k))
continue
}
other_state.has_in_progress_alternatives = true
}
if right_contains_left {
if state.step_index == other_state.step_index &&
(state.seeking_immediate_match ||
!other_state.seeking_immediate_match) {
self.capture_list_pool.release(state.capture_list_id)
ignore(self.states.remove(j))
did_remove = true
break
}
state.has_in_progress_alternatives = true
}
k += 1
}
// If the state is at the end of its pattern, remove it from the list
// of in-progress states and add it to the list of finished states.
if !did_remove {
let next_step = query.steps[state.step_index]
if next_step.depth == pattern_done_marker {
if !state.has_in_progress_alternatives {
self.push_finished_state(state)
let index = self.index_of_state(state)
ignore(self.states.remove(index))
did_match = true
continue
}
}
j += 1
}
}
}
if node_intersects_containing_range &&
self.should_descend(node_intersects_range) {
match cursor.goto_first_child_internal() {
StepVisible => {
self.depth += 1
self.on_visible_node = true
continue
}
StepHidden => {
self.on_visible_node = false
continue
}
StepNone => ()
}
}
self.ascending = true
}
}
}
///|
/// `state - self->states.contents`.
fn QueryCursor::index_of_state(self : QueryCursor, state : QueryState) -> Int {
for i, s in self.states {
if physical_equal(s, state) {
return i
}
}
abort("state is not in the states array")
}
///|
/// The captures of a `TSQueryMatch`: its `capture_count` is a `uint16_t`, so
/// only the first `size & 0xFFFF` captures of the list are exposed.
fn match_captures(captures : Array[QueryCapture]) -> Array[QueryCapture] {
let count = captures.length() & 0xFFFF
if count == captures.length() {
captures.copy()
} else {
captures[:count].to_owned()
}
}
///|
/// `ts_query_cursor_next_match`.
pub fn QueryCursor::next_match(self : QueryCursor) -> QueryMatch? {
if self.finished_states.length() == 0 {
if !self.advance(false) {
return None
}
}
if self.finished_states_heap_size > 0 {
self.heapify_finished_states()
}
let mut state_index = 0
if self.finished_states_heap_size > 0 {
for i in 1.. 0 {
finished_state_erase(self.finished_states, state_index, self.capture_list_pool)
self.finished_states_heap_size = self.finished_states.length()
} else {
ignore(self.finished_states.remove(state_index))
}
Some(result)
}
///|
/// `ts_query_cursor_remove_match`.
pub fn QueryCursor::remove_match(self : QueryCursor, match_id : UInt) -> Unit {
if self.finished_states_heap_size > 0 {
self.heapify_finished_states()
}
for i, state in self.finished_states {
if state.id == match_id {
self.capture_list_pool.release(state.capture_list_id)
if self.finished_states_heap_size > 0 {
finished_state_erase(self.finished_states, i, self.capture_list_pool)
self.finished_states_heap_size = self.finished_states.length()
} else {
ignore(self.finished_states.remove(i))
}
return
}
}
// Remove unfinished query states as well to prevent future captures for a
// match being removed.
for i, state in self.states {
if state.id == match_id {
self.capture_list_pool.release(state.capture_list_id)
ignore(self.states.remove(i))
return
}
}
}
///|
/// `ts_query_cursor_next_capture`: the match and the index of the capture.
pub fn QueryCursor::next_capture(self : QueryCursor) -> (QueryMatch, Int)? {
// The goal here is to return captures in order, even though they may not be
// discovered in order, because patterns can overlap. Search for matches
// until there is a finished capture that is before any unfinished capture.
for ;; {
// Sift any newly pushed finished states into the heap.
self.heapify_finished_states()
// First, find the earliest capture in an unfinished match.
let (found_unfinished_state, first_unfinished) = self.first_in_progress_capture(
true,
)
let first_unfinished_state_is_definite = found_unfinished_state &&
first_unfinished.is_definite
// Then find the earliest capture in a finished match. The finished_states
// array is maintained as a min-heap, so the earliest is always at index 0.
// Clean up fully-consumed and out-of-range states from the heap root
// first.
let mut first_finished_state : QueryState? = None
let mut first_finished_capture_byte = first_unfinished.byte_offset
let mut first_finished_pattern_index = first_unfinished.pattern_index
while self.finished_states.length() > 0 {
let state = self.finished_states[0]
let captures = self.capture_list_pool.get(state.capture_list_id)
// Remove states whose captures are all consumed.
if state.consumed_capture_count >= captures.length() {
self.capture_list_pool.release(state.capture_list_id)
finished_state_pop(self.finished_states, self.capture_list_pool)
self.finished_states_heap_size = self.finished_states.length()
continue
}
let node = captures[state.consumed_capture_count].node
let node_precedes_range = node.end_byte() <=
self.included_range.start_byte ||
@runtime.point_lte(node.end_point(), self.included_range.start_point)
let node_follows_range = node.start_byte() >=
self.included_range.end_byte ||
@runtime.point_gte(node.start_point(), self.included_range.end_point)
let node_outside_of_range = node_precedes_range || node_follows_range
// Skip captures that are outside of the cursor's range.
if node_outside_of_range {
state.set_consumed_capture_count(state.consumed_capture_count + 1)
finished_state_sift_down(self.finished_states, 0, self.capture_list_pool)
continue
}
let node_start_byte = node.start_byte()
if node_start_byte < first_finished_capture_byte ||
(node_start_byte == first_finished_capture_byte &&
state.pattern_index < first_finished_pattern_index) {
first_finished_state = Some(state)
first_finished_capture_byte = node_start_byte
first_finished_pattern_index = state.pattern_index
}
break
}
// If there is finished capture that is clearly before any unfinished
// capture, then return its match, and its capture index. Internally record
// the fact that the capture has been 'consumed'.
let state = match first_finished_state {
Some(state) => Some(state)
None =>
if first_unfinished_state_is_definite {
Some(self.states[first_unfinished.state_index])
} else {
None
}
}
if state is Some(state) {
if state.id == 0xFFFFFFFFU {
state.id = self.next_state_id
self.next_state_id += 1
}
let captures = match_captures(self.capture_list_pool.get(state.capture_list_id))
let capture_index = state.consumed_capture_count
state.set_consumed_capture_count(state.consumed_capture_count + 1)
// If this state is in the finished_states heap, its sort key has
// changed (next capture is now later in the document). Restore heap
// order.
if first_finished_state is Some(first) && physical_equal(first, state) {
finished_state_sift_down(self.finished_states, 0, self.capture_list_pool)
}
return Some(
({ id: state.id, pattern_index: state.pattern_index, captures }, capture_index),
)
}
if self.capture_list_pool.is_empty() && found_unfinished_state {
self.capture_list_pool.release(
self.states[first_unfinished.state_index].capture_list_id,
)
ignore(self.states.remove(first_unfinished.state_index))
}
// If there are no finished matches that are ready to be returned, then
// continue finding more matches.
if !self.advance(true) && self.finished_states.length() == 0 {
return None
}
}
}