// Port of tree-sitter lib/src/query.c: streams, capture list pool, finished
// state heap, quantifiers, symbol tables, query steps and the state
// predecessor map.
///|
let max_step_capture_count : Int = 3
///|
let max_negated_field_count : Int = 8
///|
let max_state_predecessor_count : Int = 256
///|
let max_analysis_state_depth : Int = 8
///|
let max_analysis_iteration_count : Int = 256
///|
let pattern_done_marker : Int = 65535
///|
let none : Int = 65535
///|
let capture_list_none : UInt = 0xFFFFFFFFU
///|
let wildcard_symbol : Int = 0
///|
/// The cursor calls the progress callback once it has done this much work.
/// Entering or leaving a node costs one, plus one for each in-progress state,
/// because every step visits all of them.
let work_per_query_callback_check : Int = 1000
///|
let max_query_pattern_depth : Int = 100
///|
/// C `iswspace` in the "C" locale: ASCII only.
fn iswspace(c : Int) -> Bool {
(c >= 9 && c <= 13) || c == 32
}
///|
/// C `iswalnum` in the "C" locale: ASCII only.
fn iswalnum(c : Int) -> Bool {
(c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}
///|
/// Stream - A sequence of unicode characters derived from a UTF8 string. This
/// struct is used in parsing queries from S-expressions. Positions are byte
/// offsets into `source`.
priv struct Stream {
source : Bytes
mut input : Int
start : Int
end : Int
mut next : Int
mut next_size : Int
}
///|
/// Advance to the next unicode code point in the stream.
fn Stream::advance(self : Stream) -> Bool {
self.input += self.next_size
if self.input < self.end {
let (size, code_point) = @runtime.decode_utf8(
self.source[self.input:self.end],
)
self.next = code_point
if size > 0 {
self.next_size = size.reinterpret_as_int()
return true
}
} else {
self.next_size = 0
self.next = 0
}
false
}
///|
/// Reset the stream to the given input position.
fn Stream::reset(self : Stream, input : Int) -> Unit {
self.input = input
self.next_size = 0
ignore(self.advance())
}
///|
fn Stream::new(source : Bytes) -> Stream {
let stream = {
source,
next: 0,
next_size: 0,
input: 0,
start: 0,
end: source.length(),
}
ignore(stream.advance())
stream
}
///|
fn Stream::skip_whitespace(self : Stream) -> Unit {
for ;; {
if iswspace(self.next) {
ignore(self.advance())
} else if self.next == ';' {
// skip over comments
ignore(self.advance())
while self.next != 0 && self.next != '\n' {
if !self.advance() {
break
}
}
} else {
break
}
}
}
///|
fn Stream::is_ident_start(self : Stream) -> Bool {
iswalnum(self.next) || self.next == '_' || self.next == '-'
}
///|
fn Stream::scan_identifier(self : Stream) -> Unit {
ignore(self.advance())
while iswalnum(self.next) ||
self.next == '_' ||
self.next == '-' ||
self.next == '.' {
ignore(self.advance())
}
}
///|
fn Stream::offset(self : Stream) -> Int {
self.input - self.start
}
///|
/// `TSQueryCapture`.
pub(all) struct QueryCapture {
node : @runtime.Node
index : Int
}
///|
/// A capture list. `in_use == false` stands for upstream's `UINT32_MAX` size.
priv struct CaptureList {
items : Array[QueryCapture]
mut in_use : Bool
}
///|
/// Overwrites a capture list's elements before clearing it. Upstream's
/// captures hold non-owning node pointers, but a MoonBit `Node` keeps its
/// `Tree` alive, so lists that are cleared for reuse or no longer in use must
/// not keep referring to their previous nodes (capacity is retained).
fn clear_capture_list(items : Array[QueryCapture]) -> Unit {
if items.length() > 0 {
for i in 0.. CaptureListPool {
{
list: [],
empty_list: { items: [], in_use: true },
max_capture_list_count: 0xFFFFFFFFU,
free_id_stack: [],
}
}
///|
fn CaptureListPool::reset(self : CaptureListPool) -> Unit {
self.free_id_stack.clear()
for i, list in self.list {
// This invalid size means that the list is not in use.
list.in_use = false
clear_capture_list(list.items)
self.free_id_stack.push(i)
}
}
///|
fn CaptureListPool::get(self : CaptureListPool, id : UInt) -> Array[QueryCapture] {
if id >= self.list.length().reinterpret_as_uint() {
return self.empty_list.items
}
self.list[id.reinterpret_as_int()].items
}
///|
fn CaptureListPool::is_empty(self : CaptureListPool) -> Bool {
// The capture list pool is empty if all allocated lists are in use, and we
// have reached the maximum allowed number of allocated lists.
self.free_id_stack.length() == 0 &&
self.list.length().reinterpret_as_uint() >= self.max_capture_list_count
}
///|
fn CaptureListPool::acquire(self : CaptureListPool) -> UInt {
// First see if any already allocated capture list is currently unused.
if self.free_id_stack.pop() is Some(id) {
clear_capture_list(self.list[id].items)
self.list[id].in_use = true
return id.reinterpret_as_uint()
}
// Otherwise allocate and initialize a new capture list, as long as that
// doesn't put us over the requested maximum.
let i = self.list.length()
if i.reinterpret_as_uint() >= self.max_capture_list_count {
return capture_list_none
}
self.list.push({ items: [], in_use: true })
i.reinterpret_as_uint()
}
///|
fn CaptureListPool::release(self : CaptureListPool, id : UInt) -> Unit {
if id >= self.list.length().reinterpret_as_uint() {
return
}
let list = self.list[id.reinterpret_as_int()]
if !list.in_use {
return // Guard against releasing a list twice
}
list.in_use = false
clear_capture_list(list.items)
self.free_id_stack.push(id.reinterpret_as_int())
}
///|
/// QueryState - The state of an in-progress match of a particular pattern in
/// a query. `consumed_capture_count` is a 12-bit field upstream; it is kept
/// truncated to 12 bits here.
priv struct QueryState {
mut id : UInt
mut capture_list_id : UInt
mut heap_insert_order : UInt
start_depth : Int
mut step_index : Int
pattern_index : Int
mut consumed_capture_count : Int
mut seeking_immediate_match : Bool
mut has_in_progress_alternatives : Bool
mut dead : Bool
mut needs_parent : Bool
mut skipped_quantifier : Bool
}
///|
fn QueryState::copy(self : QueryState) -> QueryState {
{ ..self }
}
///|
fn QueryState::set_consumed_capture_count(self : QueryState, value : Int) -> Unit {
self.consumed_capture_count = value & 0xFFF
}
///|
/// Compare two finished states by (byte offset of next unconsumed capture,
/// pattern_index, insertion order).
fn finished_state_precedes(
a : QueryState,
b : QueryState,
pool : CaptureListPool,
) -> Bool {
let a_caps = pool.get(a.capture_list_id)
let b_caps = pool.get(b.capture_list_id)
if a.consumed_capture_count >= a_caps.length() {
return false
}
if b.consumed_capture_count >= b_caps.length() {
return true
}
let a_byte = a_caps[a.consumed_capture_count].node.start_byte()
let b_byte = b_caps[b.consumed_capture_count].node.start_byte()
if a_byte != b_byte {
return a_byte < b_byte
}
if a.pattern_index != b.pattern_index {
return a.pattern_index < b.pattern_index
}
a.heap_insert_order < b.heap_insert_order
}
///|
fn finished_state_swap(states : Array[QueryState], a : Int, b : Int) -> Unit {
let tmp = states[a]
states[a] = states[b]
states[b] = tmp
}
///|
fn finished_state_sift_down(
states : Array[QueryState],
index : Int,
pool : CaptureListPool,
) -> Unit {
let size = states.length()
let mut index = index
for ;; {
let mut smallest = index
let left = 2 * index + 1
let right = 2 * index + 2
if left < size && finished_state_precedes(states[left], states[smallest], pool) {
smallest = left
}
if right < size &&
finished_state_precedes(states[right], states[smallest], pool) {
smallest = right
}
if smallest == index {
break
}
finished_state_swap(states, index, smallest)
index = smallest
}
}
///|
fn finished_state_sift_up(
states : Array[QueryState],
index : Int,
pool : CaptureListPool,
) -> Unit {
let mut index = index
while index > 0 {
let parent = (index - 1) / 2
if finished_state_precedes(states[index], states[parent], pool) {
finished_state_swap(states, index, parent)
index = parent
} else {
break
}
}
}
///|
fn finished_state_pop(states : Array[QueryState], pool : CaptureListPool) -> Unit {
if states.length() > 1 {
states[0] = states[states.length() - 1]
}
ignore(states.pop())
if states.length() > 0 {
finished_state_sift_down(states, 0, pool)
}
}
///|
/// Remove an element at an arbitrary index and restore heap order.
fn finished_state_erase(
states : Array[QueryState],
index : Int,
pool : CaptureListPool,
) -> Unit {
if index == states.length() - 1 {
ignore(states.pop())
return
}
states[index] = states[states.length() - 1]
ignore(states.pop())
// The replacement element may need to go up or down.
if index > 0 &&
finished_state_precedes(states[index], states[(index - 1) / 2], pool) {
finished_state_sift_up(states, index, pool)
} else {
finished_state_sift_down(states, index, pool)
}
}
///|
/// `TSQuantifier`; declaration order matches the C enum values.
pub(all) enum Quantifier {
Zero
ZeroOrOne
ZeroOrMore
One
OneOrMore
} derive(Eq, Debug)
///|
fn quantifier_mul(left : Quantifier, right : Quantifier) -> Quantifier {
match left {
Zero => Zero
ZeroOrOne =>
match right {
Zero => Zero
ZeroOrOne | One => ZeroOrOne
ZeroOrMore | OneOrMore => ZeroOrMore
}
ZeroOrMore =>
match right {
Zero => Zero
_ => ZeroOrMore
}
One => right
OneOrMore =>
match right {
Zero => Zero
ZeroOrOne | ZeroOrMore => ZeroOrMore
One | OneOrMore => OneOrMore
}
}
}
///|
fn quantifier_join(left : Quantifier, right : Quantifier) -> Quantifier {
match left {
Zero =>
match right {
Zero => Zero
ZeroOrOne | One => ZeroOrOne
ZeroOrMore | OneOrMore => ZeroOrMore
}
ZeroOrOne =>
match right {
Zero | ZeroOrOne | One => ZeroOrOne
ZeroOrMore | OneOrMore => ZeroOrMore
}
ZeroOrMore => ZeroOrMore
One =>
match right {
Zero | ZeroOrOne => ZeroOrOne
ZeroOrMore => ZeroOrMore
One => One
OneOrMore => OneOrMore
}
OneOrMore =>
match right {
Zero | ZeroOrOne | ZeroOrMore => ZeroOrMore
One | OneOrMore => OneOrMore
}
}
}
///|
fn quantifier_add(left : Quantifier, right : Quantifier) -> Quantifier {
match left {
Zero => right
ZeroOrOne =>
match right {
Zero => ZeroOrOne
ZeroOrOne | ZeroOrMore => ZeroOrMore
One | OneOrMore => OneOrMore
}
ZeroOrMore =>
match right {
Zero | ZeroOrOne | ZeroOrMore => ZeroOrMore
One | OneOrMore => OneOrMore
}
One =>
match right {
Zero => One
_ => OneOrMore
}
OneOrMore => OneOrMore
}
}
///|
/// CaptureQuantifiers - the quantifiers of a pattern's captures, by capture id.
priv type CaptureQuantifiers = Array[Quantifier]
///|
fn capture_quantifiers_replace(
qs : Array[Quantifier],
quantifiers : Array[Quantifier],
) -> Unit {
qs.clear()
for q in quantifiers {
qs.push(q)
}
}
///|
fn capture_quantifier_for_id(qs : Array[Quantifier], id : Int) -> Quantifier {
let id = id & 0xFFFF // `uint16_t id`
if qs.length() <= id {
Zero
} else {
qs[id]
}
}
///|
fn capture_quantifiers_add_for_id(
qs : Array[Quantifier],
id : Int,
quantifier : Quantifier,
) -> Unit {
let id = id & 0xFFFF // `uint16_t id`
while qs.length() <= id {
qs.push(Zero)
}
qs[id] = quantifier_add(qs[id], quantifier)
}
///|
fn capture_quantifiers_add_all(
qs : Array[Quantifier],
quantifiers : Array[Quantifier],
) -> Unit {
while qs.length() < quantifiers.length() {
qs.push(Zero)
}
for id in 0..<(quantifiers.length() & 0xFFFF) {
qs[id] = quantifier_add(qs[id], quantifiers[id])
}
}
///|
fn capture_quantifiers_mul(
qs : Array[Quantifier],
quantifier : Quantifier,
) -> Unit {
for id in 0..<(qs.length() & 0xFFFF) {
qs[id] = quantifier_mul(qs[id], quantifier)
}
}
///|
fn capture_quantifiers_join_all(
qs : Array[Quantifier],
quantifiers : Array[Quantifier],
) -> Unit {
while qs.length() < quantifiers.length() {
qs.push(Zero)
}
for id in 0.. SymbolTable {
{ names: [] }
}
///|
/// `slice.length == length && !strncmp(characters + offset, name, length)`.
fn symbol_name_matches(existing : Bytes, name : BytesView) -> Bool {
if existing.length() != name.length() {
return false
}
for i in 0.. Int {
for i, existing in self.names {
if symbol_name_matches(existing, name) {
return i
}
}
-1
}
///|
fn SymbolTable::name_for_id(self : SymbolTable, id : Int) -> Bytes {
self.names[id & 0xFFFF] // `uint16_t id`
}
///|
fn SymbolTable::insert_name(self : SymbolTable, name : BytesView) -> Int {
let id = self.id_for_name(name)
if id >= 0 {
return id & 0xFFFF
}
self.names.push(name.to_owned())
(self.names.length() - 1) & 0xFFFF
}
///|
/// QueryStep - A step in the process of matching a query. Each node within a
/// query S-expression corresponds to one of these steps.
priv struct QueryStep {
mut symbol : Int
mut supertype_symbol : Int
mut field : Int
capture_ids : FixedArray[Int]
depth : Int
mut alternative_index : Int
mut negated_field_list_id : Int
mut is_named : Bool
is_immediate : Bool
mut is_last_child : Bool
mut is_pass_through : Bool
mut is_dead_end : Bool
mut is_inside_alternation : Bool
mut contains_captures : Bool
mut root_pattern_guaranteed : Bool
mut parent_pattern_guaranteed : Bool
mut is_missing : Bool
mut alternative_is_skip : Bool
}
///|
fn QueryStep::new(symbol : Int, depth : Int, is_immediate : Bool) -> QueryStep {
{
symbol,
supertype_symbol: 0,
field: 0,
capture_ids: FixedArray::make(max_step_capture_count, none),
depth,
alternative_index: none,
negated_field_list_id: 0,
is_named: false,
is_immediate,
is_last_child: false,
is_pass_through: false,
is_dead_end: false,
is_inside_alternation: false,
contains_captures: false,
root_pattern_guaranteed: false,
parent_pattern_guaranteed: false,
is_missing: false,
alternative_is_skip: false,
}
}
///|
/// A value copy of a step (steps are plain structs upstream).
fn QueryStep::copy(self : QueryStep) -> QueryStep {
{ ..self, capture_ids: self.capture_ids.copy() }
}
///|
fn QueryStep::add_capture(self : QueryStep, capture_id : Int) -> Unit {
let capture_id = capture_id & 0xFFFF // `uint16_t capture_id`
for i in 0.. Unit {
let capture_id = capture_id & 0xFFFF // `uint16_t capture_id`
for i in 0.. StatePredecessorMap {
{
contents: FixedArray::make(
language.state_count * (max_state_predecessor_count + 1),
0,
),
}
}
///|
fn StatePredecessorMap::add(
self : StatePredecessorMap,
state : Int,
predecessor : Int,
) -> Unit {
let index = state * (max_state_predecessor_count + 1)
let count = self.contents[index]
if count == 0 ||
(count < max_state_predecessor_count &&
self.contents[index + count] != predecessor) {
self.contents[index] = count + 1
self.contents[index + count + 1] = predecessor
}
}
///|
/// The predecessors of `state`.
fn StatePredecessorMap::get(
self : StatePredecessorMap,
state : Int,
) -> ArrayView[Int] {
let index = state * (max_state_predecessor_count + 1)
let count = self.contents[index]
self.contents[index + 1:index + 1 + count]
}