#include "tree_sitter/api.h"
#include "./alloc.h"
#include "./array.h"
#include "./language.h"
#include "./point.h"
#include "./tree_cursor.h"
#include "./unicode.h"
#include <wctype.h>
#define MAX_STEP_CAPTURE_COUNT 3
#define MAX_NEGATED_FIELD_COUNT 8
#define MAX_STATE_PREDECESSOR_COUNT 256
#define MAX_ANALYSIS_STATE_DEPTH 8
#define MAX_ANALYSIS_ITERATION_COUNT 256
typedef struct {
const char *input;
const char *start;
const char *end;
int32_t next;
uint8_t next_size;
} Stream;
typedef struct {
TSSymbol symbol;
TSSymbol supertype_symbol;
TSFieldId field;
uint16_t capture_ids[MAX_STEP_CAPTURE_COUNT];
uint16_t depth;
uint16_t alternative_index;
uint16_t negated_field_list_id;
bool is_named: 1;
bool is_immediate: 1;
bool is_last_child: 1;
bool is_pass_through: 1;
bool is_dead_end: 1;
bool alternative_is_immediate: 1;
bool contains_captures: 1;
bool root_pattern_guaranteed: 1;
bool parent_pattern_guaranteed: 1;
} QueryStep;
typedef struct {
uint32_t offset;
uint32_t length;
} Slice;
typedef struct {
Array(char) characters;
Array(Slice) slices;
} SymbolTable;
typedef Array(uint8_t) CaptureQuantifiers;
typedef struct {
uint16_t step_index;
uint16_t pattern_index;
bool is_rooted;
} PatternEntry;
typedef struct {
Slice steps;
Slice predicate_steps;
uint32_t start_byte;
bool is_non_local;
} QueryPattern;
typedef struct {
uint32_t byte_offset;
uint16_t step_index;
} StepOffset;
typedef struct {
uint32_t id;
uint32_t capture_list_id;
uint16_t start_depth;
uint16_t step_index;
uint16_t pattern_index;
uint16_t consumed_capture_count: 12;
bool seeking_immediate_match: 1;
bool has_in_progress_alternatives: 1;
bool dead: 1;
bool needs_parent: 1;
} QueryState;
typedef Array(TSQueryCapture) CaptureList;
typedef struct {
Array(CaptureList) list;
CaptureList empty_list;
uint32_t max_capture_list_count;
uint32_t free_capture_list_count;
} CaptureListPool;
typedef struct {
TSStateId parse_state;
TSSymbol parent_symbol;
uint16_t child_index;
TSFieldId field_id: 15;
bool done: 1;
} AnalysisStateEntry;
typedef struct {
AnalysisStateEntry stack[MAX_ANALYSIS_STATE_DEPTH];
uint16_t depth;
uint16_t step_index;
TSSymbol root_symbol;
} AnalysisState;
typedef Array(AnalysisState *) AnalysisStateSet;
typedef struct {
AnalysisStateSet states;
AnalysisStateSet next_states;
AnalysisStateSet deeper_states;
AnalysisStateSet state_pool;
Array(uint16_t) final_step_indices;
Array(TSSymbol) finished_parent_symbols;
bool did_abort;
} QueryAnalysis;
typedef struct {
TSStateId state;
uint16_t production_id;
uint8_t child_index: 7;
bool done: 1;
} AnalysisSubgraphNode;
typedef struct {
TSSymbol symbol;
Array(TSStateId) start_states;
Array(AnalysisSubgraphNode) nodes;
} AnalysisSubgraph;
typedef Array(AnalysisSubgraph) AnalysisSubgraphArray;
typedef struct {
TSStateId *contents;
} StatePredecessorMap;
struct TSQuery {
SymbolTable captures;
SymbolTable predicate_values;
Array(CaptureQuantifiers) capture_quantifiers;
Array(QueryStep) steps;
Array(PatternEntry) pattern_map;
Array(TSQueryPredicateStep) predicate_steps;
Array(QueryPattern) patterns;
Array(StepOffset) step_offsets;
Array(TSFieldId) negated_fields;
Array(char) string_buffer;
Array(TSSymbol) repeat_symbols_with_rootless_patterns;
const TSLanguage *language;
uint16_t wildcard_root_pattern_count;
};
struct TSQueryCursor {
const TSQuery *query;
TSTreeCursor cursor;
Array(QueryState) states;
Array(QueryState) finished_states;
CaptureListPool capture_list_pool;
uint32_t depth;
uint32_t start_byte;
uint32_t end_byte;
TSPoint start_point;
TSPoint end_point;
uint32_t next_state_id;
bool on_visible_node;
bool ascending;
bool halted;
bool did_exceed_match_limit;
};
static const TSQueryError PARENT_DONE = -1;
static const uint16_t PATTERN_DONE_MARKER = UINT16_MAX;
static const uint16_t NONE = UINT16_MAX;
static const TSSymbol WILDCARD_SYMBOL = 0;
static bool stream_advance(Stream *self) {
self->input += self->next_size;
if (self->input < self->end) {
uint32_t size = ts_decode_utf8(
(const uint8_t *)self->input,
self->end - self->input,
&self->next
);
if (size > 0) {
self->next_size = size;
return true;
}
} else {
self->next_size = 0;
self->next = '\0';
}
return false;
}
static void stream_reset(Stream *self, const char *input) {
self->input = input;
self->next_size = 0;
stream_advance(self);
}
static Stream stream_new(const char *string, uint32_t length) {
Stream self = {
.next = 0,
.input = string,
.start = string,
.end = string + length,
};
stream_advance(&self);
return self;
}
static void stream_skip_whitespace(Stream *self) {
for (;;) {
if (iswspace(self->next)) {
stream_advance(self);
} else if (self->next == ';') {
stream_advance(self);
while (self->next && self->next != '\n') {
if (!stream_advance(self)) break;
}
} else {
break;
}
}
}
static bool stream_is_ident_start(Stream *self) {
return iswalnum(self->next) || self->next == '_' || self->next == '-';
}
static void stream_scan_identifier(Stream *stream) {
do {
stream_advance(stream);
} while (
iswalnum(stream->next) ||
stream->next == '_' ||
stream->next == '-' ||
stream->next == '.' ||
stream->next == '?' ||
stream->next == '!'
);
}
static uint32_t stream_offset(Stream *self) {
return self->input - self->start;
}
static CaptureListPool capture_list_pool_new(void) {
return (CaptureListPool) {
.list = array_new(),
.empty_list = array_new(),
.max_capture_list_count = UINT32_MAX,
.free_capture_list_count = 0,
};
}
static void capture_list_pool_reset(CaptureListPool *self) {
for (uint16_t i = 0; i < self->list.size; i++) {
self->list.contents[i].size = UINT32_MAX;
}
self->free_capture_list_count = self->list.size;
}
static void capture_list_pool_delete(CaptureListPool *self) {
for (uint16_t i = 0; i < self->list.size; i++) {
array_delete(&self->list.contents[i]);
}
array_delete(&self->list);
}
static const CaptureList *capture_list_pool_get(const CaptureListPool *self, uint16_t id) {
if (id >= self->list.size) return &self->empty_list;
return &self->list.contents[id];
}
static CaptureList *capture_list_pool_get_mut(CaptureListPool *self, uint16_t id) {
assert(id < self->list.size);
return &self->list.contents[id];
}
static bool capture_list_pool_is_empty(const CaptureListPool *self) {
return self->free_capture_list_count == 0 && self->list.size >= self->max_capture_list_count;
}
static uint16_t capture_list_pool_acquire(CaptureListPool *self) {
if (self->free_capture_list_count > 0) {
for (uint16_t i = 0; i < self->list.size; i++) {
if (self->list.contents[i].size == UINT32_MAX) {
array_clear(&self->list.contents[i]);
self->free_capture_list_count--;
return i;
}
}
}
uint32_t i = self->list.size;
if (i >= self->max_capture_list_count) {
return NONE;
}
CaptureList list;
array_init(&list);
array_push(&self->list, list);
return i;
}
static void capture_list_pool_release(CaptureListPool *self, uint16_t id) {
if (id >= self->list.size) return;
self->list.contents[id].size = UINT32_MAX;
self->free_capture_list_count++;
}
static TSQuantifier quantifier_mul(
TSQuantifier left,
TSQuantifier right
) {
switch (left)
{
case TSQuantifierZero:
return TSQuantifierZero;
case TSQuantifierZeroOrOne:
switch (right) {
case TSQuantifierZero:
return TSQuantifierZero;
case TSQuantifierZeroOrOne:
case TSQuantifierOne:
return TSQuantifierZeroOrOne;
case TSQuantifierZeroOrMore:
case TSQuantifierOneOrMore:
return TSQuantifierZeroOrMore;
};
break;
case TSQuantifierZeroOrMore:
switch (right) {
case TSQuantifierZero:
return TSQuantifierZero;
case TSQuantifierZeroOrOne:
case TSQuantifierZeroOrMore:
case TSQuantifierOne:
case TSQuantifierOneOrMore:
return TSQuantifierZeroOrMore;
};
break;
case TSQuantifierOne:
return right;
case TSQuantifierOneOrMore:
switch (right) {
case TSQuantifierZero:
return TSQuantifierZero;
case TSQuantifierZeroOrOne:
case TSQuantifierZeroOrMore:
return TSQuantifierZeroOrMore;
case TSQuantifierOne:
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
};
break;
}
return TSQuantifierZero; }
static TSQuantifier quantifier_join(
TSQuantifier left,
TSQuantifier right
) {
switch (left)
{
case TSQuantifierZero:
switch (right) {
case TSQuantifierZero:
return TSQuantifierZero;
case TSQuantifierZeroOrOne:
case TSQuantifierOne:
return TSQuantifierZeroOrOne;
case TSQuantifierZeroOrMore:
case TSQuantifierOneOrMore:
return TSQuantifierZeroOrMore;
};
break;
case TSQuantifierZeroOrOne:
switch (right) {
case TSQuantifierZero:
case TSQuantifierZeroOrOne:
case TSQuantifierOne:
return TSQuantifierZeroOrOne;
break;
case TSQuantifierZeroOrMore:
case TSQuantifierOneOrMore:
return TSQuantifierZeroOrMore;
break;
};
break;
case TSQuantifierZeroOrMore:
return TSQuantifierZeroOrMore;
case TSQuantifierOne:
switch (right) {
case TSQuantifierZero:
case TSQuantifierZeroOrOne:
return TSQuantifierZeroOrOne;
case TSQuantifierZeroOrMore:
return TSQuantifierZeroOrMore;
case TSQuantifierOne:
return TSQuantifierOne;
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
};
break;
case TSQuantifierOneOrMore:
switch (right) {
case TSQuantifierZero:
case TSQuantifierZeroOrOne:
case TSQuantifierZeroOrMore:
return TSQuantifierZeroOrMore;
case TSQuantifierOne:
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
};
break;
}
return TSQuantifierZero; }
static TSQuantifier quantifier_add(
TSQuantifier left,
TSQuantifier right
) {
switch (left)
{
case TSQuantifierZero:
return right;
case TSQuantifierZeroOrOne:
switch (right) {
case TSQuantifierZero:
return TSQuantifierZeroOrOne;
case TSQuantifierZeroOrOne:
case TSQuantifierZeroOrMore:
return TSQuantifierZeroOrMore;
case TSQuantifierOne:
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
};
break;
case TSQuantifierZeroOrMore:
switch (right) {
case TSQuantifierZero:
return TSQuantifierZeroOrMore;
case TSQuantifierZeroOrOne:
case TSQuantifierZeroOrMore:
return TSQuantifierZeroOrMore;
case TSQuantifierOne:
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
};
break;
case TSQuantifierOne:
switch (right) {
case TSQuantifierZero:
return TSQuantifierOne;
case TSQuantifierZeroOrOne:
case TSQuantifierZeroOrMore:
case TSQuantifierOne:
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
};
break;
case TSQuantifierOneOrMore:
return TSQuantifierOneOrMore;
}
return TSQuantifierZero; }
static CaptureQuantifiers capture_quantifiers_new(void) {
return (CaptureQuantifiers) array_new();
}
static void capture_quantifiers_delete(
CaptureQuantifiers *self
) {
array_delete(self);
}
static void capture_quantifiers_clear(
CaptureQuantifiers *self
) {
array_clear(self);
}
static void capture_quantifiers_replace(
CaptureQuantifiers *self,
CaptureQuantifiers *quantifiers
) {
array_clear(self);
array_push_all(self, quantifiers);
}
static TSQuantifier capture_quantifier_for_id(
const CaptureQuantifiers *self,
uint16_t id
) {
return (self->size <= id) ? TSQuantifierZero : (TSQuantifier) *array_get(self, id);
}
static void capture_quantifiers_add_for_id(
CaptureQuantifiers *self,
uint16_t id,
TSQuantifier quantifier
) {
if (self->size <= id) {
array_grow_by(self, id + 1 - self->size);
}
uint8_t *own_quantifier = array_get(self, id);
*own_quantifier = (uint8_t) quantifier_add((TSQuantifier) *own_quantifier, quantifier);
}
static void capture_quantifiers_add_all(
CaptureQuantifiers *self,
CaptureQuantifiers *quantifiers
) {
if (self->size < quantifiers->size) {
array_grow_by(self, quantifiers->size - self->size);
}
for (uint16_t id = 0; id < quantifiers->size; id++) {
uint8_t *quantifier = array_get(quantifiers, id);
uint8_t *own_quantifier = array_get(self, id);
*own_quantifier = (uint8_t) quantifier_add((TSQuantifier) *own_quantifier, (TSQuantifier) *quantifier);
}
}
static void capture_quantifiers_mul(
CaptureQuantifiers *self,
TSQuantifier quantifier
) {
for (uint16_t id = 0; id < self->size; id++) {
uint8_t *own_quantifier = array_get(self, id);
*own_quantifier = (uint8_t) quantifier_mul((TSQuantifier) *own_quantifier, quantifier);
}
}
static void capture_quantifiers_join_all(
CaptureQuantifiers *self,
CaptureQuantifiers *quantifiers
) {
if (self->size < quantifiers->size) {
array_grow_by(self, quantifiers->size - self->size);
}
for (uint32_t id = 0; id < quantifiers->size; id++) {
uint8_t *quantifier = array_get(quantifiers, id);
uint8_t *own_quantifier = array_get(self, id);
*own_quantifier = (uint8_t) quantifier_join((TSQuantifier) *own_quantifier, (TSQuantifier) *quantifier);
}
for (uint32_t id = quantifiers->size; id < self->size; id++) {
uint8_t *own_quantifier = array_get(self, id);
*own_quantifier = (uint8_t) quantifier_join((TSQuantifier) *own_quantifier, TSQuantifierZero);
}
}
static SymbolTable symbol_table_new(void) {
return (SymbolTable) {
.characters = array_new(),
.slices = array_new(),
};
}
static void symbol_table_delete(SymbolTable *self) {
array_delete(&self->characters);
array_delete(&self->slices);
}
static int symbol_table_id_for_name(
const SymbolTable *self,
const char *name,
uint32_t length
) {
for (unsigned i = 0; i < self->slices.size; i++) {
Slice slice = self->slices.contents[i];
if (
slice.length == length &&
!strncmp(&self->characters.contents[slice.offset], name, length)
) return i;
}
return -1;
}
static const char *symbol_table_name_for_id(
const SymbolTable *self,
uint16_t id,
uint32_t *length
) {
Slice slice = self->slices.contents[id];
*length = slice.length;
return &self->characters.contents[slice.offset];
}
static uint16_t symbol_table_insert_name(
SymbolTable *self,
const char *name,
uint32_t length
) {
int id = symbol_table_id_for_name(self, name, length);
if (id >= 0) return (uint16_t)id;
Slice slice = {
.offset = self->characters.size,
.length = length,
};
array_grow_by(&self->characters, length + 1);
memcpy(&self->characters.contents[slice.offset], name, length);
self->characters.contents[self->characters.size - 1] = 0;
array_push(&self->slices, slice);
return self->slices.size - 1;
}
static QueryStep query_step__new(
TSSymbol symbol,
uint16_t depth,
bool is_immediate
) {
return (QueryStep) {
.symbol = symbol,
.depth = depth,
.field = 0,
.capture_ids = {NONE, NONE, NONE},
.alternative_index = NONE,
.negated_field_list_id = 0,
.contains_captures = false,
.is_last_child = false,
.is_named = false,
.is_pass_through = false,
.is_dead_end = false,
.root_pattern_guaranteed = false,
.is_immediate = is_immediate,
.alternative_is_immediate = false,
};
}
static void query_step__add_capture(QueryStep *self, uint16_t capture_id) {
for (unsigned i = 0; i < MAX_STEP_CAPTURE_COUNT; i++) {
if (self->capture_ids[i] == NONE) {
self->capture_ids[i] = capture_id;
break;
}
}
}
static void query_step__remove_capture(QueryStep *self, uint16_t capture_id) {
for (unsigned i = 0; i < MAX_STEP_CAPTURE_COUNT; i++) {
if (self->capture_ids[i] == capture_id) {
self->capture_ids[i] = NONE;
while (i + 1 < MAX_STEP_CAPTURE_COUNT) {
if (self->capture_ids[i + 1] == NONE) break;
self->capture_ids[i] = self->capture_ids[i + 1];
self->capture_ids[i + 1] = NONE;
i++;
}
break;
}
}
}
static inline StatePredecessorMap state_predecessor_map_new(
const TSLanguage *language
) {
return (StatePredecessorMap) {
.contents = ts_calloc(
(size_t)language->state_count * (MAX_STATE_PREDECESSOR_COUNT + 1),
sizeof(TSStateId)
),
};
}
static inline void state_predecessor_map_delete(StatePredecessorMap *self) {
ts_free(self->contents);
}
static inline void state_predecessor_map_add(
StatePredecessorMap *self,
TSStateId state,
TSStateId predecessor
) {
size_t index = (size_t)state * (MAX_STATE_PREDECESSOR_COUNT + 1);
TSStateId *count = &self->contents[index];
if (
*count == 0 ||
(*count < MAX_STATE_PREDECESSOR_COUNT && self->contents[index + *count] != predecessor)
) {
(*count)++;
self->contents[index + *count] = predecessor;
}
}
static inline const TSStateId *state_predecessor_map_get(
const StatePredecessorMap *self,
TSStateId state,
unsigned *count
) {
size_t index = (size_t)state * (MAX_STATE_PREDECESSOR_COUNT + 1);
*count = self->contents[index];
return &self->contents[index + 1];
}
static unsigned analysis_state__recursion_depth(const AnalysisState *self) {
unsigned result = 0;
for (unsigned i = 0; i < self->depth; i++) {
TSSymbol symbol = self->stack[i].parent_symbol;
for (unsigned j = 0; j < i; j++) {
if (self->stack[j].parent_symbol == symbol) {
result++;
break;
}
}
}
return result;
}
static inline int analysis_state__compare_position(
AnalysisState *const *self,
AnalysisState *const *other
) {
for (unsigned i = 0; i < (*self)->depth; i++) {
if (i >= (*other)->depth) return -1;
if ((*self)->stack[i].child_index < (*other)->stack[i].child_index) return -1;
if ((*self)->stack[i].child_index > (*other)->stack[i].child_index) return 1;
}
if ((*self)->depth < (*other)->depth) return 1;
if ((*self)->step_index < (*other)->step_index) return -1;
if ((*self)->step_index > (*other)->step_index) return 1;
return 0;
}
static inline int analysis_state__compare(
AnalysisState *const *self,
AnalysisState *const *other
) {
int result = analysis_state__compare_position(self, other);
if (result != 0) return result;
for (unsigned i = 0; i < (*self)->depth; i++) {
if ((*self)->stack[i].parent_symbol < (*other)->stack[i].parent_symbol) return -1;
if ((*self)->stack[i].parent_symbol > (*other)->stack[i].parent_symbol) return 1;
if ((*self)->stack[i].parse_state < (*other)->stack[i].parse_state) return -1;
if ((*self)->stack[i].parse_state > (*other)->stack[i].parse_state) return 1;
if ((*self)->stack[i].field_id < (*other)->stack[i].field_id) return -1;
if ((*self)->stack[i].field_id > (*other)->stack[i].field_id) return 1;
}
return 0;
}
static inline AnalysisStateEntry *analysis_state__top(AnalysisState *self) {
return &self->stack[self->depth - 1];
}
static inline bool analysis_state__has_supertype(AnalysisState *self, TSSymbol symbol) {
for (unsigned i = 0; i < self->depth; i++) {
if (self->stack[i].parent_symbol == symbol) return true;
}
return false;
}
static inline AnalysisState *analysis_state_pool__clone_or_reuse(
AnalysisStateSet *self,
AnalysisState *borrowed_item
) {
AnalysisState *new_item;
if (self->size) {
new_item = array_pop(self);
} else {
new_item = ts_malloc(sizeof(AnalysisState));
}
*new_item = *borrowed_item;
return new_item;
}
static inline void analysis_state_set__insert_sorted(
AnalysisStateSet *self,
AnalysisStateSet *pool,
AnalysisState *borrowed_item
) {
unsigned index, exists;
array_search_sorted_with(self, analysis_state__compare, &borrowed_item, &index, &exists);
if (!exists) {
AnalysisState *new_item = analysis_state_pool__clone_or_reuse(pool, borrowed_item);
array_insert(self, index, new_item);
}
}
static inline void analysis_state_set__push(
AnalysisStateSet *self,
AnalysisStateSet *pool,
AnalysisState *borrowed_item
) {
AnalysisState *new_item = analysis_state_pool__clone_or_reuse(pool, borrowed_item);
array_push(self, new_item);
}
static inline void analysis_state_set__clear(AnalysisStateSet *self, AnalysisStateSet *pool) {
array_push_all(pool, self);
array_clear(self);
}
static inline void analysis_state_set__delete(AnalysisStateSet *self) {
for (unsigned i = 0; i < self->size; i++) {
ts_free(self->contents[i]);
}
array_delete(self);
}
static inline QueryAnalysis query_analysis__new() {
return (QueryAnalysis) {
.states = array_new(),
.next_states = array_new(),
.deeper_states = array_new(),
.state_pool = array_new(),
.final_step_indices = array_new(),
.finished_parent_symbols = array_new(),
.did_abort = false,
};
}
static inline void query_analysis__delete(QueryAnalysis *self) {
analysis_state_set__delete(&self->states);
analysis_state_set__delete(&self->next_states);
analysis_state_set__delete(&self->deeper_states);
analysis_state_set__delete(&self->state_pool);
array_delete(&self->final_step_indices);
array_delete(&self->finished_parent_symbols);
}
static inline int analysis_subgraph_node__compare(const AnalysisSubgraphNode *self, const AnalysisSubgraphNode *other) {
if (self->state < other->state) return -1;
if (self->state > other->state) return 1;
if (self->child_index < other->child_index) return -1;
if (self->child_index > other->child_index) return 1;
if (self->done < other->done) return -1;
if (self->done > other->done) return 1;
if (self->production_id < other->production_id) return -1;
if (self->production_id > other->production_id) return 1;
return 0;
}
static inline bool ts_query__pattern_map_search(
const TSQuery *self,
TSSymbol needle,
uint32_t *result
) {
uint32_t base_index = self->wildcard_root_pattern_count;
uint32_t size = self->pattern_map.size - base_index;
if (size == 0) {
*result = base_index;
return false;
}
while (size > 1) {
uint32_t half_size = size / 2;
uint32_t mid_index = base_index + half_size;
TSSymbol mid_symbol = self->steps.contents[
self->pattern_map.contents[mid_index].step_index
].symbol;
if (needle > mid_symbol) base_index = mid_index;
size -= half_size;
}
TSSymbol symbol = self->steps.contents[
self->pattern_map.contents[base_index].step_index
].symbol;
if (needle > symbol) {
base_index++;
if (base_index < self->pattern_map.size) {
symbol = self->steps.contents[
self->pattern_map.contents[base_index].step_index
].symbol;
}
}
*result = base_index;
return needle == symbol;
}
static inline void ts_query__pattern_map_insert(
TSQuery *self,
TSSymbol symbol,
PatternEntry new_entry
) {
uint32_t index;
ts_query__pattern_map_search(self, symbol, &index);
while (index < self->pattern_map.size) {
PatternEntry *entry = &self->pattern_map.contents[index];
if (
self->steps.contents[entry->step_index].symbol == symbol &&
entry->pattern_index < new_entry.pattern_index
) {
index++;
} else {
break;
}
}
array_insert(&self->pattern_map, index, new_entry);
}
static void ts_query__perform_analysis(
TSQuery *self,
const AnalysisSubgraphArray *subgraphs,
QueryAnalysis *analysis
) {
unsigned recursion_depth_limit = 0;
unsigned prev_final_step_count = 0;
array_clear(&analysis->final_step_indices);
array_clear(&analysis->finished_parent_symbols);
for (unsigned iteration = 0;; iteration++) {
if (iteration == MAX_ANALYSIS_ITERATION_COUNT) {
analysis->did_abort = true;
break;
}
#ifdef DEBUG_ANALYZE_QUERY
printf("Iteration: %u. Final step indices:", iteration);
for (unsigned j = 0; j < analysis->final_step_indices.size; j++) {
printf(" %4u", analysis->final_step_indices.contents[j]);
}
printf("\n");
for (unsigned j = 0; j < analysis->states.size; j++) {
AnalysisState *state = analysis->states.contents[j];
printf(" %3u: step: %u, stack: [", j, state->step_index);
for (unsigned k = 0; k < state->depth; k++) {
printf(
" {%s, child: %u, state: %4u",
self->language->symbol_names[state->stack[k].parent_symbol],
state->stack[k].child_index,
state->stack[k].parse_state
);
if (state->stack[k].field_id) printf(", field: %s", self->language->field_names[state->stack[k].field_id]);
if (state->stack[k].done) printf(", DONE");
printf("}");
}
printf(" ]\n");
}
#endif
if (analysis->states.size == 0) {
if (
analysis->deeper_states.size > 0 &&
analysis->final_step_indices.size > prev_final_step_count
) {
#ifdef DEBUG_ANALYZE_QUERY
printf("Increase recursion depth limit to %u\n", recursion_depth_limit + 1);
#endif
prev_final_step_count = analysis->final_step_indices.size;
recursion_depth_limit++;
AnalysisStateSet _states = analysis->states;
analysis->states = analysis->deeper_states;
analysis->deeper_states = _states;
continue;
}
break;
}
analysis_state_set__clear(&analysis->next_states, &analysis->state_pool);
for (unsigned j = 0; j < analysis->states.size; j++) {
AnalysisState * const state = analysis->states.contents[j];
if (analysis->next_states.size > 0) {
int comparison = analysis_state__compare_position(
&state,
array_back(&analysis->next_states)
);
if (comparison == 0) {
analysis_state_set__insert_sorted(&analysis->next_states, &analysis->state_pool, state);
continue;
} else if (comparison > 0) {
#ifdef DEBUG_ANALYZE_QUERY
printf("Terminate iteration at state %u\n", j);
#endif
while (j < analysis->states.size) {
analysis_state_set__push(
&analysis->next_states,
&analysis->state_pool,
analysis->states.contents[j]
);
j++;
}
break;
}
}
const TSStateId parse_state = analysis_state__top(state)->parse_state;
const TSSymbol parent_symbol = analysis_state__top(state)->parent_symbol;
const TSFieldId parent_field_id = analysis_state__top(state)->field_id;
const unsigned child_index = analysis_state__top(state)->child_index;
const QueryStep * const step = &self->steps.contents[state->step_index];
unsigned subgraph_index, exists;
array_search_sorted_by(subgraphs, .symbol, parent_symbol, &subgraph_index, &exists);
if (!exists) continue;
const AnalysisSubgraph *subgraph = &subgraphs->contents[subgraph_index];
LookaheadIterator lookahead_iterator = ts_language_lookaheads(self->language, parse_state);
while (ts_lookahead_iterator_next(&lookahead_iterator)) {
TSSymbol sym = lookahead_iterator.symbol;
AnalysisSubgraphNode successor = {
.state = parse_state,
.child_index = child_index,
};
if (lookahead_iterator.action_count) {
const TSParseAction *action = &lookahead_iterator.actions[lookahead_iterator.action_count - 1];
if (action->type == TSParseActionTypeShift) {
if (!action->shift.extra) {
successor.state = action->shift.state;
successor.child_index++;
}
} else {
continue;
}
} else if (lookahead_iterator.next_state != 0) {
successor.state = lookahead_iterator.next_state;
successor.child_index++;
} else {
continue;
}
unsigned node_index;
array_search_sorted_with(
&subgraph->nodes,
analysis_subgraph_node__compare, &successor,
&node_index, &exists
);
while (node_index < subgraph->nodes.size) {
AnalysisSubgraphNode *node = &subgraph->nodes.contents[node_index++];
if (node->state != successor.state || node->child_index != successor.child_index) break;
TSSymbol alias = ts_language_alias_at(self->language, node->production_id, child_index);
TSSymbol visible_symbol = alias
? alias
: self->language->symbol_metadata[sym].visible
? self->language->public_symbol_map[sym]
: 0;
TSFieldId field_id = parent_field_id;
if (!field_id) {
const TSFieldMapEntry *field_map, *field_map_end;
ts_language_field_map(self->language, node->production_id, &field_map, &field_map_end);
for (; field_map != field_map_end; field_map++) {
if (!field_map->inherited && field_map->child_index == child_index) {
field_id = field_map->field_id;
break;
}
}
}
AnalysisState next_state = *state;
AnalysisStateEntry *next_state_top = analysis_state__top(&next_state);
next_state_top->child_index = successor.child_index;
next_state_top->parse_state = successor.state;
if (node->done) next_state_top->done = true;
bool does_match = false;
if (visible_symbol) {
does_match = true;
if (step->symbol == WILDCARD_SYMBOL) {
if (
step->is_named &&
!self->language->symbol_metadata[visible_symbol].named
) does_match = false;
} else if (step->symbol != visible_symbol) {
does_match = false;
}
if (step->field && step->field != field_id) {
does_match = false;
}
if (
step->supertype_symbol &&
!analysis_state__has_supertype(state, step->supertype_symbol)
) does_match = false;
}
else if (sym >= self->language->token_count) {
if (!next_state_top->done) {
if (next_state.depth + 1 >= MAX_ANALYSIS_STATE_DEPTH) {
#ifdef DEBUG_ANALYZE_QUERY
printf("Exceeded depth limit for state %u\n", j);
#endif
analysis->did_abort = true;
continue;
}
next_state.depth++;
next_state_top = analysis_state__top(&next_state);
}
*next_state_top = (AnalysisStateEntry) {
.parse_state = parse_state,
.parent_symbol = sym,
.child_index = 0,
.field_id = field_id,
.done = false,
};
if (analysis_state__recursion_depth(&next_state) > recursion_depth_limit) {
analysis_state_set__insert_sorted(
&analysis->deeper_states,
&analysis->state_pool,
&next_state
);
continue;
}
}
while (next_state.depth > 0 && next_state_top->done) {
next_state.depth--;
next_state_top = analysis_state__top(&next_state);
}
const QueryStep *next_step = step;
if (does_match) {
for (;;) {
next_state.step_index++;
next_step = &self->steps.contents[next_state.step_index];
if (
next_step->depth == PATTERN_DONE_MARKER ||
next_step->depth <= step->depth
) break;
}
} else if (successor.state == parse_state) {
continue;
}
for (;;) {
if (next_step->is_pass_through) {
next_state.step_index++;
next_step++;
continue;
}
if (!next_step->is_dead_end) {
bool did_finish_pattern = self->steps.contents[next_state.step_index].depth != step->depth;
if (did_finish_pattern) {
array_insert_sorted_by(&analysis->finished_parent_symbols, , state->root_symbol);
} else if (next_state.depth == 0) {
array_insert_sorted_by(&analysis->final_step_indices, , next_state.step_index);
} else {
analysis_state_set__insert_sorted(&analysis->next_states, &analysis->state_pool, &next_state);
}
}
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 = &self->steps.contents[next_state.step_index];
} else {
break;
}
}
}
}
}
AnalysisStateSet _states = analysis->states;
analysis->states = analysis->next_states;
analysis->next_states = _states;
}
}
static bool ts_query__analyze_patterns(TSQuery *self, unsigned *error_offset) {
Array(uint16_t) non_rooted_pattern_start_steps = array_new();
for (unsigned i = 0; i < self->pattern_map.size; i++) {
PatternEntry *pattern = &self->pattern_map.contents[i];
if (!pattern->is_rooted) {
QueryStep *step = &self->steps.contents[pattern->step_index];
if (step->symbol != WILDCARD_SYMBOL) {
array_push(&non_rooted_pattern_start_steps, i);
}
}
}
Array(uint32_t) parent_step_indices = array_new();
for (unsigned i = 0; i < self->steps.size; i++) {
QueryStep *step = &self->steps.contents[i];
if (step->depth == PATTERN_DONE_MARKER) {
step->parent_pattern_guaranteed = true;
step->root_pattern_guaranteed = true;
continue;
}
bool has_children = false;
bool is_wildcard = step->symbol == WILDCARD_SYMBOL;
step->contains_captures = step->capture_ids[0] != NONE;
for (unsigned j = i + 1; j < self->steps.size; j++) {
QueryStep *next_step = &self->steps.contents[j];
if (
next_step->depth == PATTERN_DONE_MARKER ||
next_step->depth <= step->depth
) break;
if (next_step->capture_ids[0] != NONE) {
step->contains_captures = true;
}
if (!is_wildcard) {
next_step->root_pattern_guaranteed = true;
next_step->parent_pattern_guaranteed = true;
}
has_children = true;
}
if (has_children && !is_wildcard) {
array_push(&parent_step_indices, i);
}
}
AnalysisSubgraphArray subgraphs = array_new();
for (unsigned i = 0; i < parent_step_indices.size; i++) {
uint32_t parent_step_index = parent_step_indices.contents[i];
TSSymbol parent_symbol = self->steps.contents[parent_step_index].symbol;
AnalysisSubgraph subgraph = { .symbol = parent_symbol };
array_insert_sorted_by(&subgraphs, .symbol, subgraph);
}
for (TSSymbol sym = self->language->token_count; sym < self->language->symbol_count; sym++) {
if (!ts_language_symbol_metadata(self->language, sym).visible) {
AnalysisSubgraph subgraph = { .symbol = sym };
array_insert_sorted_by(&subgraphs, .symbol, subgraph);
}
}
StatePredecessorMap predecessor_map = state_predecessor_map_new(self->language);
for (TSStateId state = 1; state < self->language->state_count; state++) {
unsigned subgraph_index, exists;
LookaheadIterator lookahead_iterator = ts_language_lookaheads(self->language, state);
while (ts_lookahead_iterator_next(&lookahead_iterator)) {
if (lookahead_iterator.action_count) {
for (unsigned i = 0; i < lookahead_iterator.action_count; i++) {
const TSParseAction *action = &lookahead_iterator.actions[i];
if (action->type == TSParseActionTypeReduce) {
const TSSymbol *aliases, *aliases_end;
ts_language_aliases_for_symbol(
self->language,
action->reduce.symbol,
&aliases,
&aliases_end
);
for (const TSSymbol *symbol = aliases; symbol < aliases_end; symbol++) {
array_search_sorted_by(
&subgraphs,
.symbol,
*symbol,
&subgraph_index,
&exists
);
if (exists) {
AnalysisSubgraph *subgraph = &subgraphs.contents[subgraph_index];
if (subgraph->nodes.size == 0 || array_back(&subgraph->nodes)->state != state) {
array_push(&subgraph->nodes, ((AnalysisSubgraphNode) {
.state = state,
.production_id = action->reduce.production_id,
.child_index = action->reduce.child_count,
.done = true,
}));
}
}
}
} else if (action->type == TSParseActionTypeShift && !action->shift.extra) {
TSStateId next_state = action->shift.state;
state_predecessor_map_add(&predecessor_map, next_state, state);
}
}
} else if (lookahead_iterator.next_state != 0) {
if (lookahead_iterator.next_state != state) {
state_predecessor_map_add(&predecessor_map, lookahead_iterator.next_state, state);
}
if (ts_language_state_is_primary(self->language, state)) {
const TSSymbol *aliases, *aliases_end;
ts_language_aliases_for_symbol(
self->language,
lookahead_iterator.symbol,
&aliases,
&aliases_end
);
for (const TSSymbol *symbol = aliases; symbol < aliases_end; symbol++) {
array_search_sorted_by(
&subgraphs,
.symbol,
*symbol,
&subgraph_index,
&exists
);
if (exists) {
AnalysisSubgraph *subgraph = &subgraphs.contents[subgraph_index];
if (
subgraph->start_states.size == 0 ||
*array_back(&subgraph->start_states) != state
)
array_push(&subgraph->start_states, state);
}
}
}
}
}
}
Array(AnalysisSubgraphNode) next_nodes = array_new();
for (unsigned i = 0; i < subgraphs.size; i++) {
AnalysisSubgraph *subgraph = &subgraphs.contents[i];
if (subgraph->nodes.size == 0) {
array_delete(&subgraph->start_states);
array_erase(&subgraphs, i);
i--;
continue;
}
array_assign(&next_nodes, &subgraph->nodes);
while (next_nodes.size > 0) {
AnalysisSubgraphNode node = array_pop(&next_nodes);
if (node.child_index > 1) {
unsigned predecessor_count;
const TSStateId *predecessors = state_predecessor_map_get(
&predecessor_map,
node.state,
&predecessor_count
);
for (unsigned j = 0; j < predecessor_count; j++) {
AnalysisSubgraphNode predecessor_node = {
.state = predecessors[j],
.child_index = node.child_index - 1,
.production_id = node.production_id,
.done = false,
};
unsigned index, exists;
array_search_sorted_with(
&subgraph->nodes, analysis_subgraph_node__compare, &predecessor_node,
&index, &exists
);
if (!exists) {
array_insert(&subgraph->nodes, index, predecessor_node);
array_push(&next_nodes, predecessor_node);
}
}
}
}
}
#ifdef DEBUG_ANALYZE_QUERY
printf("\nSubgraphs:\n");
for (unsigned i = 0; i < subgraphs.size; i++) {
AnalysisSubgraph *subgraph = &subgraphs.contents[i];
printf(" %u, %s:\n", subgraph->symbol, ts_language_symbol_name(self->language, subgraph->symbol));
for (unsigned j = 0; j < subgraph->start_states.size; j++) {
printf(
" {state: %u}\n",
subgraph->start_states.contents[j]
);
}
for (unsigned j = 0; j < subgraph->nodes.size; j++) {
AnalysisSubgraphNode *node = &subgraph->nodes.contents[j];
printf(
" {state: %u, child_index: %u, production_id: %u, done: %d}\n",
node->state, node->child_index, node->production_id, node->done
);
}
printf("\n");
}
#endif
bool all_patterns_are_valid = true;
QueryAnalysis analysis = query_analysis__new();
for (unsigned i = 0; i < parent_step_indices.size; i++) {
uint16_t parent_step_index = parent_step_indices.contents[i];
uint16_t parent_depth = self->steps.contents[parent_step_index].depth;
TSSymbol parent_symbol = self->steps.contents[parent_step_index].symbol;
if (parent_symbol == ts_builtin_sym_error) continue;
unsigned subgraph_index, exists;
array_search_sorted_by(&subgraphs, .symbol, parent_symbol, &subgraph_index, &exists);
if (!exists) {
unsigned first_child_step_index = parent_step_index + 1;
uint32_t i, exists;
array_search_sorted_by(&self->step_offsets, .step_index, first_child_step_index, &i, &exists);
assert(exists);
*error_offset = self->step_offsets.contents[i].byte_offset;
all_patterns_are_valid = false;
break;
}
AnalysisSubgraph *subgraph = &subgraphs.contents[subgraph_index];
analysis_state_set__clear(&analysis.states, &analysis.state_pool);
analysis_state_set__clear(&analysis.deeper_states, &analysis.state_pool);
for (unsigned j = 0; j < subgraph->start_states.size; j++) {
TSStateId parse_state = subgraph->start_states.contents[j];
analysis_state_set__push(&analysis.states, &analysis.state_pool, &((AnalysisState) {
.step_index = parent_step_index + 1,
.stack = {
[0] = {
.parse_state = parse_state,
.parent_symbol = parent_symbol,
.child_index = 0,
.field_id = 0,
.done = false,
},
},
.depth = 1,
.root_symbol = parent_symbol,
}));
}
#ifdef DEBUG_ANALYZE_QUERY
printf(
"\nWalk states for %s:\n",
ts_language_symbol_name(self->language, analysis.states.contents[0]->stack[0].parent_symbol)
);
#endif
analysis.did_abort = false;
ts_query__perform_analysis(self, &subgraphs, &analysis);
if (analysis.did_abort) {
for (unsigned j = parent_step_index + 1; j < self->steps.size; j++) {
QueryStep *step = &self->steps.contents[j];
if (
step->depth <= parent_depth ||
step->depth == PATTERN_DONE_MARKER
) break;
if (!step->is_dead_end) {
step->parent_pattern_guaranteed = false;
step->root_pattern_guaranteed = false;
}
}
continue;
}
if (analysis.finished_parent_symbols.size == 0) {
assert(analysis.final_step_indices.size > 0);
uint16_t impossible_step_index = *array_back(&analysis.final_step_indices);
uint32_t i, exists;
array_search_sorted_by(&self->step_offsets, .step_index, impossible_step_index, &i, &exists);
if (i >= self->step_offsets.size) i = self->step_offsets.size - 1;
*error_offset = self->step_offsets.contents[i].byte_offset;
all_patterns_are_valid = false;
break;
}
for (unsigned j = 0; j < analysis.final_step_indices.size; j++) {
uint32_t final_step_index = analysis.final_step_indices.contents[j];
QueryStep *step = &self->steps.contents[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;
}
}
}
Array(uint16_t) predicate_capture_ids = array_new();
for (unsigned i = 0; i < self->patterns.size; i++) {
QueryPattern *pattern = &self->patterns.contents[i];
array_clear(&predicate_capture_ids);
for (
unsigned start = pattern->predicate_steps.offset,
end = start + pattern->predicate_steps.length,
j = start; j < end; j++
) {
TSQueryPredicateStep *step = &self->predicate_steps.contents[j];
if (step->type == TSQueryPredicateStepTypeCapture) {
array_insert_sorted_by(&predicate_capture_ids, , step->value_id);
}
}
for (
unsigned start = pattern->steps.offset,
end = start + pattern->steps.length,
j = start; j < end; j++
) {
QueryStep *step = &self->steps.contents[j];
for (unsigned k = 0; k < MAX_STEP_CAPTURE_COUNT; k++) {
uint16_t capture_id = step->capture_ids[k];
if (capture_id == NONE) break;
unsigned index, exists;
array_search_sorted_by(&predicate_capture_ids, , capture_id, &index, &exists);
if (exists) {
step->root_pattern_guaranteed = false;
break;
}
}
}
}
bool done = self->steps.size == 0;
while (!done) {
done = true;
for (unsigned i = self->steps.size - 1; i > 0; i--) {
QueryStep *step = &self->steps.contents[i];
if (step->depth == PATTERN_DONE_MARKER) continue;
bool 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.contents[step->alternative_index];
}
if (!parent_pattern_guaranteed) {
QueryStep *prev_step = &self->steps.contents[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;
}
}
}
}
#ifdef DEBUG_ANALYZE_QUERY
printf("Steps:\n");
for (unsigned i = 0; i < self->steps.size; i++) {
QueryStep *step = &self->steps.contents[i];
if (step->depth == PATTERN_DONE_MARKER) {
printf(" %u: DONE\n", i);
} else {
printf(
" %u: {symbol: %s, field: %s, depth: %u, parent_pattern_guaranteed: %d, root_pattern_guaranteed: %d}\n",
i,
(step->symbol == WILDCARD_SYMBOL)
? "ANY"
: ts_language_symbol_name(self->language, step->symbol),
(step->field ? ts_language_field_name_for_id(self->language, step->field) : "-"),
step->depth,
step->parent_pattern_guaranteed,
step->root_pattern_guaranteed
);
}
}
#endif
analysis.did_abort = false;
for (uint32_t i = 0; i < non_rooted_pattern_start_steps.size; i++) {
uint16_t pattern_entry_index = non_rooted_pattern_start_steps.contents[i];
PatternEntry *pattern_entry = &self->pattern_map.contents[pattern_entry_index];
analysis_state_set__clear(&analysis.states, &analysis.state_pool);
analysis_state_set__clear(&analysis.deeper_states, &analysis.state_pool);
for (unsigned j = 0; j < subgraphs.size; j++) {
AnalysisSubgraph *subgraph = &subgraphs.contents[j];
TSSymbolMetadata metadata = ts_language_symbol_metadata(self->language, subgraph->symbol);
if (metadata.visible || metadata.named) continue;
for (uint32_t k = 0; k < subgraph->start_states.size; k++) {
TSStateId parse_state = subgraph->start_states.contents[k];
analysis_state_set__push(&analysis.states, &analysis.state_pool, &((AnalysisState) {
.step_index = pattern_entry->step_index,
.stack = {
[0] = {
.parse_state = parse_state,
.parent_symbol = subgraph->symbol,
.child_index = 0,
.field_id = 0,
.done = false,
},
},
.root_symbol = subgraph->symbol,
.depth = 1,
}));
}
}
#ifdef DEBUG_ANALYZE_QUERY
printf("\nWalk states for rootless pattern step %u:\n", step_index);
#endif
ts_query__perform_analysis(
self,
&subgraphs,
&analysis
);
if (analysis.finished_parent_symbols.size > 0) {
self->patterns.contents[pattern_entry->pattern_index].is_non_local = true;
}
for (unsigned k = 0; k < analysis.finished_parent_symbols.size; k++) {
TSSymbol symbol = analysis.finished_parent_symbols.contents[k];
array_insert_sorted_by(&self->repeat_symbols_with_rootless_patterns, , symbol);
}
}
#ifdef DEBUG_ANALYZE_QUERY
if (self->repeat_symbols_with_rootless_patterns.size > 0) {
printf("\nRepetition symbols with rootless patterns:\n");
printf("aborted analysis: %d\n", analysis.did_abort);
for (unsigned i = 0; i < self->repeat_symbols_with_rootless_patterns.size; i++) {
TSSymbol symbol = self->repeat_symbols_with_rootless_patterns.contents[i];
printf(" %u, %s\n", symbol, ts_language_symbol_name(self->language, symbol));
}
printf("\n");
}
#endif
for (unsigned i = 0; i < subgraphs.size; i++) {
array_delete(&subgraphs.contents[i].start_states);
array_delete(&subgraphs.contents[i].nodes);
}
array_delete(&subgraphs);
query_analysis__delete(&analysis);
array_delete(&next_nodes);
array_delete(&non_rooted_pattern_start_steps);
array_delete(&parent_step_indices);
array_delete(&predicate_capture_ids);
state_predecessor_map_delete(&predecessor_map);
return all_patterns_are_valid;
}
static void ts_query__add_negated_fields(
TSQuery *self,
uint16_t step_index,
TSFieldId *field_ids,
uint16_t field_count
) {
QueryStep *step = &self->steps.contents[step_index];
bool failed_match = false;
unsigned match_count = 0;
unsigned start_i = 0;
for (unsigned i = 0; i < self->negated_fields.size; i++) {
TSFieldId existing_field_id = self->negated_fields.contents[i];
if (existing_field_id == 0) {
if (match_count == field_count) {
step->negated_field_list_id = start_i;
return;
} else {
start_i = i + 1;
match_count = 0;
failed_match = false;
}
}
else if (
match_count < field_count &&
existing_field_id == field_ids[match_count] &&
!failed_match
) {
match_count++;
}
else {
match_count = 0;
failed_match = true;
}
}
step->negated_field_list_id = self->negated_fields.size;
array_extend(&self->negated_fields, field_count, field_ids);
array_push(&self->negated_fields, 0);
}
static TSQueryError ts_query__parse_string_literal(
TSQuery *self,
Stream *stream
) {
const char *string_start = stream->input;
if (stream->next != '"') return TSQueryErrorSyntax;
stream_advance(stream);
const char *prev_position = stream->input;
bool is_escaped = false;
array_clear(&self->string_buffer);
for (;;) {
if (is_escaped) {
is_escaped = false;
switch (stream->next) {
case 'n':
array_push(&self->string_buffer, '\n');
break;
case 'r':
array_push(&self->string_buffer, '\r');
break;
case 't':
array_push(&self->string_buffer, '\t');
break;
case '0':
array_push(&self->string_buffer, '\0');
break;
default:
array_extend(&self->string_buffer, stream->next_size, stream->input);
break;
}
prev_position = stream->input + stream->next_size;
} else {
if (stream->next == '\\') {
array_extend(&self->string_buffer, (uint32_t)(stream->input - prev_position), prev_position);
prev_position = stream->input + 1;
is_escaped = true;
} else if (stream->next == '"') {
array_extend(&self->string_buffer, (uint32_t)(stream->input - prev_position), prev_position);
stream_advance(stream);
return TSQueryErrorNone;
} else if (stream->next == '\n') {
stream_reset(stream, string_start);
return TSQueryErrorSyntax;
}
}
if (!stream_advance(stream)) {
stream_reset(stream, string_start);
return TSQueryErrorSyntax;
}
}
}
static TSQueryError ts_query__parse_predicate(
TSQuery *self,
Stream *stream
) {
if (!stream_is_ident_start(stream)) return TSQueryErrorSyntax;
const char *predicate_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - predicate_name;
uint16_t id = symbol_table_insert_name(
&self->predicate_values,
predicate_name,
length
);
array_push(&self->predicate_steps, ((TSQueryPredicateStep) {
.type = TSQueryPredicateStepTypeString,
.value_id = id,
}));
stream_skip_whitespace(stream);
for (;;) {
if (stream->next == ')') {
stream_advance(stream);
stream_skip_whitespace(stream);
array_push(&self->predicate_steps, ((TSQueryPredicateStep) {
.type = TSQueryPredicateStepTypeDone,
.value_id = 0,
}));
break;
}
else if (stream->next == '@') {
stream_advance(stream);
if (!stream_is_ident_start(stream)) return TSQueryErrorSyntax;
const char *capture_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - capture_name;
int capture_id = symbol_table_id_for_name(
&self->captures,
capture_name,
length
);
if (capture_id == -1) {
stream_reset(stream, capture_name);
return TSQueryErrorCapture;
}
array_push(&self->predicate_steps, ((TSQueryPredicateStep) {
.type = TSQueryPredicateStepTypeCapture,
.value_id = capture_id,
}));
}
else if (stream->next == '"') {
TSQueryError e = ts_query__parse_string_literal(self, stream);
if (e) return e;
uint16_t id = symbol_table_insert_name(
&self->predicate_values,
self->string_buffer.contents,
self->string_buffer.size
);
array_push(&self->predicate_steps, ((TSQueryPredicateStep) {
.type = TSQueryPredicateStepTypeString,
.value_id = id,
}));
}
else if (stream_is_ident_start(stream)) {
const char *symbol_start = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - symbol_start;
uint16_t id = symbol_table_insert_name(
&self->predicate_values,
symbol_start,
length
);
array_push(&self->predicate_steps, ((TSQueryPredicateStep) {
.type = TSQueryPredicateStepTypeString,
.value_id = id,
}));
}
else {
return TSQueryErrorSyntax;
}
stream_skip_whitespace(stream);
}
return 0;
}
static TSQueryError ts_query__parse_pattern(
TSQuery *self,
Stream *stream,
uint32_t depth,
bool is_immediate,
CaptureQuantifiers *capture_quantifiers
) {
if (stream->next == 0) return TSQueryErrorSyntax;
if (stream->next == ')' || stream->next == ']') return PARENT_DONE;
const uint32_t starting_step_index = self->steps.size;
if (
self->step_offsets.size == 0 ||
array_back(&self->step_offsets)->step_index != starting_step_index
) {
array_push(&self->step_offsets, ((StepOffset) {
.step_index = starting_step_index,
.byte_offset = stream_offset(stream),
}));
}
if (stream->next == '[') {
stream_advance(stream);
stream_skip_whitespace(stream);
Array(uint32_t) branch_step_indices = array_new();
CaptureQuantifiers branch_capture_quantifiers = capture_quantifiers_new();
for (;;) {
uint32_t start_index = self->steps.size;
TSQueryError e = ts_query__parse_pattern(
self,
stream,
depth,
is_immediate,
&branch_capture_quantifiers
);
if (e == PARENT_DONE) {
if (stream->next == ']' && branch_step_indices.size > 0) {
stream_advance(stream);
break;
}
e = TSQueryErrorSyntax;
}
if (e) {
capture_quantifiers_delete(&branch_capture_quantifiers);
array_delete(&branch_step_indices);
return e;
}
if (start_index == starting_step_index) {
capture_quantifiers_replace(capture_quantifiers, &branch_capture_quantifiers);
} else {
capture_quantifiers_join_all(capture_quantifiers, &branch_capture_quantifiers);
}
array_push(&branch_step_indices, start_index);
array_push(&self->steps, query_step__new(0, depth, false));
capture_quantifiers_clear(&branch_capture_quantifiers);
}
(void)array_pop(&self->steps);
for (unsigned i = 0; i < branch_step_indices.size - 1; i++) {
uint32_t step_index = branch_step_indices.contents[i];
uint32_t next_step_index = branch_step_indices.contents[i + 1];
QueryStep *start_step = &self->steps.contents[step_index];
QueryStep *end_step = &self->steps.contents[next_step_index - 1];
start_step->alternative_index = next_step_index;
end_step->alternative_index = self->steps.size;
end_step->is_dead_end = true;
}
capture_quantifiers_delete(&branch_capture_quantifiers);
array_delete(&branch_step_indices);
}
else if (stream->next == '(') {
stream_advance(stream);
stream_skip_whitespace(stream);
if (stream->next == '(' || stream->next == '"' || stream->next == '[') {
bool child_is_immediate = false;
CaptureQuantifiers child_capture_quantifiers = capture_quantifiers_new();
for (;;) {
if (stream->next == '.') {
child_is_immediate = true;
stream_advance(stream);
stream_skip_whitespace(stream);
}
TSQueryError e = ts_query__parse_pattern(
self,
stream,
depth,
child_is_immediate,
&child_capture_quantifiers
);
if (e == PARENT_DONE) {
if (stream->next == ')') {
stream_advance(stream);
break;
}
e = TSQueryErrorSyntax;
}
if (e) {
capture_quantifiers_delete(&child_capture_quantifiers);
return e;
}
capture_quantifiers_add_all(capture_quantifiers, &child_capture_quantifiers);
capture_quantifiers_clear(&child_capture_quantifiers);
child_is_immediate = false;
}
capture_quantifiers_delete(&child_capture_quantifiers);
}
else if (stream->next == '.' || stream->next == '#') {
stream_advance(stream);
return ts_query__parse_predicate(self, stream);
}
else {
TSSymbol symbol;
if (stream_is_ident_start(stream)) {
const char *node_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - node_name;
if (length > 0 && (node_name[length - 1] == '!' || node_name[length - 1] == '?')) {
stream_reset(stream, node_name);
return ts_query__parse_predicate(self, stream);
}
else if (length == 1 && node_name[0] == '_') {
symbol = WILDCARD_SYMBOL;
}
else {
symbol = ts_language_symbol_for_name(
self->language,
node_name,
length,
true
);
if (!symbol) {
stream_reset(stream, node_name);
return TSQueryErrorNodeType;
}
}
} else {
return TSQueryErrorSyntax;
}
array_push(&self->steps, query_step__new(symbol, depth, is_immediate));
QueryStep *step = array_back(&self->steps);
if (ts_language_symbol_metadata(self->language, symbol).supertype) {
step->supertype_symbol = step->symbol;
step->symbol = WILDCARD_SYMBOL;
}
if (symbol == WILDCARD_SYMBOL) {
step->is_named = true;
}
stream_skip_whitespace(stream);
if (stream->next == '/') {
stream_advance(stream);
if (!stream_is_ident_start(stream)) {
return TSQueryErrorSyntax;
}
const char *node_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - node_name;
step->symbol = ts_language_symbol_for_name(
self->language,
node_name,
length,
true
);
if (!step->symbol) {
stream_reset(stream, node_name);
return TSQueryErrorNodeType;
}
stream_skip_whitespace(stream);
}
bool child_is_immediate = false;
uint16_t last_child_step_index = 0;
uint16_t negated_field_count = 0;
TSFieldId negated_field_ids[MAX_NEGATED_FIELD_COUNT];
CaptureQuantifiers child_capture_quantifiers = capture_quantifiers_new();
for (;;) {
if (stream->next == '!') {
stream_advance(stream);
stream_skip_whitespace(stream);
if (!stream_is_ident_start(stream)) {
capture_quantifiers_delete(&child_capture_quantifiers);
return TSQueryErrorSyntax;
}
const char *field_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - field_name;
stream_skip_whitespace(stream);
TSFieldId field_id = ts_language_field_id_for_name(
self->language,
field_name,
length
);
if (!field_id) {
stream->input = field_name;
capture_quantifiers_delete(&child_capture_quantifiers);
return TSQueryErrorField;
}
if (negated_field_count < MAX_NEGATED_FIELD_COUNT) {
negated_field_ids[negated_field_count] = field_id;
negated_field_count++;
}
continue;
}
if (stream->next == '.') {
child_is_immediate = true;
stream_advance(stream);
stream_skip_whitespace(stream);
}
uint16_t step_index = self->steps.size;
TSQueryError e = ts_query__parse_pattern(
self,
stream,
depth + 1,
child_is_immediate,
&child_capture_quantifiers
);
if (e == PARENT_DONE) {
if (stream->next == ')') {
if (child_is_immediate) {
if (last_child_step_index == 0) {
capture_quantifiers_delete(&child_capture_quantifiers);
return TSQueryErrorSyntax;
}
self->steps.contents[last_child_step_index].is_last_child = true;
}
if (negated_field_count) {
ts_query__add_negated_fields(
self,
starting_step_index,
negated_field_ids,
negated_field_count
);
}
stream_advance(stream);
break;
}
e = TSQueryErrorSyntax;
}
if (e) {
capture_quantifiers_delete(&child_capture_quantifiers);
return e;
}
capture_quantifiers_add_all(capture_quantifiers, &child_capture_quantifiers);
last_child_step_index = step_index;
child_is_immediate = false;
capture_quantifiers_clear(&child_capture_quantifiers);
}
capture_quantifiers_delete(&child_capture_quantifiers);
}
}
else if (stream->next == '_') {
stream_advance(stream);
stream_skip_whitespace(stream);
array_push(&self->steps, query_step__new(WILDCARD_SYMBOL, depth, is_immediate));
}
else if (stream->next == '"') {
const char *string_start = stream->input;
TSQueryError e = ts_query__parse_string_literal(self, stream);
if (e) return e;
TSSymbol symbol = ts_language_symbol_for_name(
self->language,
self->string_buffer.contents,
self->string_buffer.size,
false
);
if (!symbol) {
stream_reset(stream, string_start + 1);
return TSQueryErrorNodeType;
}
array_push(&self->steps, query_step__new(symbol, depth, is_immediate));
}
else if (stream_is_ident_start(stream)) {
const char *field_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - field_name;
stream_skip_whitespace(stream);
if (stream->next != ':') {
stream_reset(stream, field_name);
return TSQueryErrorSyntax;
}
stream_advance(stream);
stream_skip_whitespace(stream);
CaptureQuantifiers field_capture_quantifiers = capture_quantifiers_new();
TSQueryError e = ts_query__parse_pattern(
self,
stream,
depth,
is_immediate,
&field_capture_quantifiers
);
if (e) {
capture_quantifiers_delete(&field_capture_quantifiers);
if (e == PARENT_DONE) e = TSQueryErrorSyntax;
return e;
}
TSFieldId field_id = ts_language_field_id_for_name(
self->language,
field_name,
length
);
if (!field_id) {
stream->input = field_name;
return TSQueryErrorField;
}
uint32_t step_index = starting_step_index;
QueryStep *step = &self->steps.contents[step_index];
for (;;) {
step->field = field_id;
if (
step->alternative_index != NONE &&
step->alternative_index > step_index &&
step->alternative_index < self->steps.size
) {
step_index = step->alternative_index;
step = &self->steps.contents[step_index];
} else {
break;
}
}
capture_quantifiers_add_all(capture_quantifiers, &field_capture_quantifiers);
capture_quantifiers_delete(&field_capture_quantifiers);
}
else {
return TSQueryErrorSyntax;
}
stream_skip_whitespace(stream);
TSQuantifier quantifier = TSQuantifierOne;
for (;;) {
if (stream->next == '+') {
quantifier = quantifier_join(TSQuantifierOneOrMore, quantifier);
stream_advance(stream);
stream_skip_whitespace(stream);
QueryStep repeat_step = query_step__new(WILDCARD_SYMBOL, depth, false);
repeat_step.alternative_index = starting_step_index;
repeat_step.is_pass_through = true;
repeat_step.alternative_is_immediate = true;
array_push(&self->steps, repeat_step);
}
else if (stream->next == '*') {
quantifier = quantifier_join(TSQuantifierZeroOrMore, quantifier);
stream_advance(stream);
stream_skip_whitespace(stream);
QueryStep repeat_step = query_step__new(WILDCARD_SYMBOL, depth, false);
repeat_step.alternative_index = starting_step_index;
repeat_step.is_pass_through = true;
repeat_step.alternative_is_immediate = true;
array_push(&self->steps, repeat_step);
QueryStep *step = &self->steps.contents[starting_step_index];
while (step->alternative_index != NONE) {
step = &self->steps.contents[step->alternative_index];
}
step->alternative_index = self->steps.size;
}
else if (stream->next == '?') {
quantifier = quantifier_join(TSQuantifierZeroOrOne, quantifier);
stream_advance(stream);
stream_skip_whitespace(stream);
QueryStep *step = &self->steps.contents[starting_step_index];
while (step->alternative_index != NONE) {
step = &self->steps.contents[step->alternative_index];
}
step->alternative_index = self->steps.size;
}
else if (stream->next == '@') {
stream_advance(stream);
if (!stream_is_ident_start(stream)) return TSQueryErrorSyntax;
const char *capture_name = stream->input;
stream_scan_identifier(stream);
uint32_t length = stream->input - capture_name;
stream_skip_whitespace(stream);
uint16_t capture_id = symbol_table_insert_name(
&self->captures,
capture_name,
length
);
capture_quantifiers_add_for_id(capture_quantifiers, capture_id, TSQuantifierOne);
uint32_t step_index = starting_step_index;
for (;;) {
QueryStep *step = &self->steps.contents[step_index];
query_step__add_capture(step, capture_id);
if (
step->alternative_index != NONE &&
step->alternative_index > step_index &&
step->alternative_index < self->steps.size
) {
step_index = step->alternative_index;
step = &self->steps.contents[step_index];
} else {
break;
}
}
}
else {
break;
}
}
capture_quantifiers_mul(capture_quantifiers, quantifier);
return 0;
}
TSQuery *ts_query_new(
const TSLanguage *language,
const char *source,
uint32_t source_len,
uint32_t *error_offset,
TSQueryError *error_type
) {
if (
!language ||
language->version > TREE_SITTER_LANGUAGE_VERSION ||
language->version < TREE_SITTER_MIN_COMPATIBLE_LANGUAGE_VERSION
) {
*error_type = TSQueryErrorLanguage;
return NULL;
}
TSQuery *self = ts_malloc(sizeof(TSQuery));
*self = (TSQuery) {
.steps = array_new(),
.pattern_map = array_new(),
.captures = symbol_table_new(),
.capture_quantifiers = array_new(),
.predicate_values = symbol_table_new(),
.predicate_steps = array_new(),
.patterns = array_new(),
.step_offsets = array_new(),
.string_buffer = array_new(),
.negated_fields = array_new(),
.repeat_symbols_with_rootless_patterns = array_new(),
.wildcard_root_pattern_count = 0,
.language = language,
};
array_push(&self->negated_fields, 0);
Stream stream = stream_new(source, source_len);
stream_skip_whitespace(&stream);
while (stream.input < stream.end) {
uint32_t pattern_index = self->patterns.size;
uint32_t start_step_index = self->steps.size;
uint32_t start_predicate_step_index = self->predicate_steps.size;
array_push(&self->patterns, ((QueryPattern) {
.steps = (Slice) {.offset = start_step_index},
.predicate_steps = (Slice) {.offset = start_predicate_step_index},
.start_byte = stream_offset(&stream),
.is_non_local = false,
}));
CaptureQuantifiers capture_quantifiers = capture_quantifiers_new();
*error_type = ts_query__parse_pattern(self, &stream, 0, false, &capture_quantifiers);
array_push(&self->steps, query_step__new(0, PATTERN_DONE_MARKER, false));
QueryPattern *pattern = array_back(&self->patterns);
pattern->steps.length = self->steps.size - start_step_index;
pattern->predicate_steps.length = self->predicate_steps.size - start_predicate_step_index;
if (*error_type) {
if (*error_type == PARENT_DONE) *error_type = TSQueryErrorSyntax;
*error_offset = stream_offset(&stream);
capture_quantifiers_delete(&capture_quantifiers);
ts_query_delete(self);
return NULL;
}
array_push(&self->capture_quantifiers, capture_quantifiers);
uint16_t wildcard_root_alternative_index = NONE;
for (;;) {
QueryStep *step = &self->steps.contents[start_step_index];
if (step->symbol == WILDCARD_SYMBOL && step->depth == 0 && !step->field) {
QueryStep *second_step = &self->steps.contents[start_step_index + 1];
if (second_step->symbol != WILDCARD_SYMBOL && second_step->depth == 1) {
wildcard_root_alternative_index = step->alternative_index;
start_step_index += 1;
step = second_step;
}
}
uint32_t start_depth = step->depth;
bool is_rooted = start_depth == 0;
for (uint32_t step_index = start_step_index + 1; step_index < self->steps.size; step_index++) {
QueryStep *step = &self->steps.contents[step_index];
if (step->is_dead_end) break;
if (step->depth == start_depth) {
is_rooted = false;
break;
}
}
ts_query__pattern_map_insert(self, step->symbol, (PatternEntry) {
.step_index = start_step_index,
.pattern_index = pattern_index,
.is_rooted = is_rooted
});
if (step->symbol == WILDCARD_SYMBOL) {
self->wildcard_root_pattern_count++;
}
if (step->alternative_index != NONE) {
start_step_index = step->alternative_index;
step->alternative_index = NONE;
} else if (wildcard_root_alternative_index != NONE) {
start_step_index = wildcard_root_alternative_index;
wildcard_root_alternative_index = NONE;
} else {
break;
}
}
}
if (!ts_query__analyze_patterns(self, error_offset)) {
*error_type = TSQueryErrorStructure;
ts_query_delete(self);
return NULL;
}
array_delete(&self->string_buffer);
return self;
}
void ts_query_delete(TSQuery *self) {
if (self) {
array_delete(&self->steps);
array_delete(&self->pattern_map);
array_delete(&self->predicate_steps);
array_delete(&self->patterns);
array_delete(&self->step_offsets);
array_delete(&self->string_buffer);
array_delete(&self->negated_fields);
array_delete(&self->repeat_symbols_with_rootless_patterns);
symbol_table_delete(&self->captures);
symbol_table_delete(&self->predicate_values);
for (uint32_t index = 0; index < self->capture_quantifiers.size; index++) {
CaptureQuantifiers *capture_quantifiers = array_get(&self->capture_quantifiers, index);
capture_quantifiers_delete(capture_quantifiers);
}
array_delete(&self->capture_quantifiers);
ts_free(self);
}
}
uint32_t ts_query_pattern_count(const TSQuery *self) {
return self->patterns.size;
}
uint32_t ts_query_capture_count(const TSQuery *self) {
return self->captures.slices.size;
}
uint32_t ts_query_string_count(const TSQuery *self) {
return self->predicate_values.slices.size;
}
const char *ts_query_capture_name_for_id(
const TSQuery *self,
uint32_t index,
uint32_t *length
) {
return symbol_table_name_for_id(&self->captures, index, length);
}
TSQuantifier ts_query_capture_quantifier_for_id(
const TSQuery *self,
uint32_t pattern_index,
uint32_t capture_index
) {
CaptureQuantifiers *capture_quantifiers = array_get(&self->capture_quantifiers, pattern_index);
return capture_quantifier_for_id(capture_quantifiers, capture_index);
}
const char *ts_query_string_value_for_id(
const TSQuery *self,
uint32_t index,
uint32_t *length
) {
return symbol_table_name_for_id(&self->predicate_values, index, length);
}
const TSQueryPredicateStep *ts_query_predicates_for_pattern(
const TSQuery *self,
uint32_t pattern_index,
uint32_t *step_count
) {
Slice slice = self->patterns.contents[pattern_index].predicate_steps;
*step_count = slice.length;
if (self->predicate_steps.contents == NULL) {
return NULL;
}
return &self->predicate_steps.contents[slice.offset];
}
uint32_t ts_query_start_byte_for_pattern(
const TSQuery *self,
uint32_t pattern_index
) {
return self->patterns.contents[pattern_index].start_byte;
}
bool ts_query_is_pattern_rooted(
const TSQuery *self,
uint32_t pattern_index
) {
for (unsigned i = 0; i < self->pattern_map.size; i++) {
PatternEntry *entry = &self->pattern_map.contents[i];
if (entry->pattern_index == pattern_index) {
if (!entry->is_rooted) return false;
}
}
return true;
}
bool ts_query_is_pattern_non_local(
const TSQuery *self,
uint32_t pattern_index
) {
if (pattern_index < self->patterns.size) {
return self->patterns.contents[pattern_index].is_non_local;
} else {
return false;
}
}
bool ts_query_is_pattern_guaranteed_at_step(
const TSQuery *self,
uint32_t byte_offset
) {
uint32_t step_index = UINT32_MAX;
for (unsigned i = 0; i < self->step_offsets.size; i++) {
StepOffset *step_offset = &self->step_offsets.contents[i];
if (step_offset->byte_offset > byte_offset) break;
step_index = step_offset->step_index;
}
if (step_index < self->steps.size) {
return self->steps.contents[step_index].root_pattern_guaranteed;
} else {
return false;
}
}
bool ts_query__step_is_fallible(
const TSQuery *self,
uint16_t step_index
) {
assert((uint32_t)step_index + 1 < self->steps.size);
QueryStep *step = &self->steps.contents[step_index];
QueryStep *next_step = &self->steps.contents[step_index + 1];
return (
next_step->depth != PATTERN_DONE_MARKER &&
next_step->depth > step->depth &&
!next_step->parent_pattern_guaranteed
);
}
void ts_query_disable_capture(
TSQuery *self,
const char *name,
uint32_t length
) {
int id = symbol_table_id_for_name(&self->captures, name, length);
if (id != -1) {
for (unsigned i = 0; i < self->steps.size; i++) {
QueryStep *step = &self->steps.contents[i];
query_step__remove_capture(step, id);
}
}
}
void ts_query_disable_pattern(
TSQuery *self,
uint32_t pattern_index
) {
for (unsigned i = 0; i < self->pattern_map.size; i++) {
PatternEntry *pattern = &self->pattern_map.contents[i];
if (pattern->pattern_index == pattern_index) {
array_erase(&self->pattern_map, i);
i--;
}
}
}
TSQueryCursor *ts_query_cursor_new(void) {
TSQueryCursor *self = ts_malloc(sizeof(TSQueryCursor));
*self = (TSQueryCursor) {
.did_exceed_match_limit = false,
.ascending = false,
.halted = false,
.states = array_new(),
.finished_states = array_new(),
.capture_list_pool = capture_list_pool_new(),
.start_byte = 0,
.end_byte = UINT32_MAX,
.start_point = {0, 0},
.end_point = POINT_MAX,
};
array_reserve(&self->states, 8);
array_reserve(&self->finished_states, 8);
return self;
}
void ts_query_cursor_delete(TSQueryCursor *self) {
array_delete(&self->states);
array_delete(&self->finished_states);
ts_tree_cursor_delete(&self->cursor);
capture_list_pool_delete(&self->capture_list_pool);
ts_free(self);
}
bool ts_query_cursor_did_exceed_match_limit(const TSQueryCursor *self) {
return self->did_exceed_match_limit;
}
uint32_t ts_query_cursor_match_limit(const TSQueryCursor *self) {
return self->capture_list_pool.max_capture_list_count;
}
void ts_query_cursor_set_match_limit(TSQueryCursor *self, uint32_t limit) {
self->capture_list_pool.max_capture_list_count = limit;
}
void ts_query_cursor_exec(
TSQueryCursor *self,
const TSQuery *query,
TSNode node
) {
array_clear(&self->states);
array_clear(&self->finished_states);
ts_tree_cursor_reset(&self->cursor, node);
capture_list_pool_reset(&self->capture_list_pool);
self->on_visible_node = true;
self->next_state_id = 0;
self->depth = 0;
self->ascending = false;
self->halted = false;
self->query = query;
self->did_exceed_match_limit = false;
}
void ts_query_cursor_set_byte_range(
TSQueryCursor *self,
uint32_t start_byte,
uint32_t end_byte
) {
if (end_byte == 0) {
end_byte = UINT32_MAX;
}
self->start_byte = start_byte;
self->end_byte = end_byte;
}
void ts_query_cursor_set_point_range(
TSQueryCursor *self,
TSPoint start_point,
TSPoint end_point
) {
if (end_point.row == 0 && end_point.column == 0) {
end_point = POINT_MAX;
}
self->start_point = start_point;
self->end_point = end_point;
}
static bool ts_query_cursor__first_in_progress_capture(
TSQueryCursor *self,
uint32_t *state_index,
uint32_t *byte_offset,
uint32_t *pattern_index,
bool *root_pattern_guaranteed
) {
bool result = false;
*state_index = UINT32_MAX;
*byte_offset = UINT32_MAX;
*pattern_index = UINT32_MAX;
for (unsigned i = 0; i < self->states.size; i++) {
QueryState *state = &self->states.contents[i];
if (state->dead) continue;
const CaptureList *captures = capture_list_pool_get(
&self->capture_list_pool,
state->capture_list_id
);
if (state->consumed_capture_count >= captures->size) {
continue;
}
TSNode node = captures->contents[state->consumed_capture_count].node;
if (
ts_node_end_byte(node) <= self->start_byte ||
point_lte(ts_node_end_point(node), self->start_point)
) {
state->consumed_capture_count++;
i--;
continue;
}
uint32_t node_start_byte = ts_node_start_byte(node);
if (
!result ||
node_start_byte < *byte_offset ||
(node_start_byte == *byte_offset && state->pattern_index < *pattern_index)
) {
QueryStep *step = &self->query->steps.contents[state->step_index];
if (root_pattern_guaranteed) {
*root_pattern_guaranteed = step->root_pattern_guaranteed;
} else if (step->root_pattern_guaranteed) {
continue;
}
result = true;
*state_index = i;
*byte_offset = node_start_byte;
*pattern_index = state->pattern_index;
}
}
return result;
}
int ts_query_cursor__compare_nodes(TSNode left, TSNode right) {
if (left.id != right.id) {
uint32_t left_start = ts_node_start_byte(left);
uint32_t right_start = ts_node_start_byte(right);
if (left_start < right_start) return -1;
if (left_start > right_start) return 1;
uint32_t left_node_count = ts_node_end_byte(left);
uint32_t right_node_count = ts_node_end_byte(right);
if (left_node_count > right_node_count) return -1;
if (left_node_count < right_node_count) return 1;
}
return 0;
}
void ts_query_cursor__compare_captures(
TSQueryCursor *self,
QueryState *left_state,
QueryState *right_state,
bool *left_contains_right,
bool *right_contains_left
) {
const CaptureList *left_captures = capture_list_pool_get(
&self->capture_list_pool,
left_state->capture_list_id
);
const CaptureList *right_captures = capture_list_pool_get(
&self->capture_list_pool,
right_state->capture_list_id
);
*left_contains_right = true;
*right_contains_left = true;
unsigned i = 0, j = 0;
for (;;) {
if (i < left_captures->size) {
if (j < right_captures->size) {
TSQueryCapture *left = &left_captures->contents[i];
TSQueryCapture *right = &right_captures->contents[j];
if (left->node.id == right->node.id && left->index == right->index) {
i++;
j++;
} else {
switch (ts_query_cursor__compare_nodes(left->node, right->node)) {
case -1:
*right_contains_left = false;
i++;
break;
case 1:
*left_contains_right = false;
j++;
break;
default:
*right_contains_left = false;
*left_contains_right = false;
i++;
j++;
break;
}
}
} else {
*right_contains_left = false;
break;
}
} else {
if (j < right_captures->size) {
*left_contains_right = false;
}
break;
}
}
}
#ifdef DEBUG_EXECUTE_QUERY
#define LOG(...) fprintf(stderr, __VA_ARGS__)
#else
#define LOG(...)
#endif
static void ts_query_cursor__add_state(
TSQueryCursor *self,
const PatternEntry *pattern
) {
QueryStep *step = &self->query->steps.contents[pattern->step_index];
uint32_t start_depth = self->depth - step->depth;
uint32_t index = self->states.size;
while (index > 0) {
QueryState *prev_state = &self->states.contents[index - 1];
if (prev_state->start_depth < start_depth) break;
if (prev_state->start_depth == start_depth) {
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--;
}
LOG(
" start state. pattern:%u, step:%u\n",
pattern->pattern_index,
pattern->step_index
);
array_insert(&self->states, index, ((QueryState) {
.id = UINT32_MAX,
.capture_list_id = NONE,
.step_index = pattern->step_index,
.pattern_index = pattern->pattern_index,
.start_depth = start_depth,
.consumed_capture_count = 0,
.seeking_immediate_match = true,
.has_in_progress_alternatives = false,
.needs_parent = step->depth == 1,
.dead = false,
}));
}
static CaptureList *ts_query_cursor__prepare_to_capture(
TSQueryCursor *self,
QueryState *state,
unsigned state_index_to_preserve
) {
if (state->capture_list_id == NONE) {
state->capture_list_id = capture_list_pool_acquire(&self->capture_list_pool);
if (state->capture_list_id == NONE) {
self->did_exceed_match_limit = true;
uint32_t state_index, byte_offset, pattern_index;
if (
ts_query_cursor__first_in_progress_capture(
self,
&state_index,
&byte_offset,
&pattern_index,
NULL
) &&
state_index != state_index_to_preserve
) {
LOG(
" abandon state. index:%u, pattern:%u, offset:%u.\n",
state_index, pattern_index, byte_offset
);
QueryState *other_state = &self->states.contents[state_index];
state->capture_list_id = other_state->capture_list_id;
other_state->capture_list_id = NONE;
other_state->dead = true;
CaptureList *list = capture_list_pool_get_mut(
&self->capture_list_pool,
state->capture_list_id
);
array_clear(list);
return list;
} else {
LOG(" ran out of capture lists");
return NULL;
}
}
}
return capture_list_pool_get_mut(&self->capture_list_pool, state->capture_list_id);
}
static void ts_query_cursor__capture(
TSQueryCursor *self,
QueryState *state,
QueryStep *step,
TSNode node
) {
if (state->dead) return;
CaptureList *capture_list = ts_query_cursor__prepare_to_capture(self, state, UINT32_MAX);
if (!capture_list) {
state->dead = true;
return;
}
for (unsigned j = 0; j < MAX_STEP_CAPTURE_COUNT; j++) {
uint16_t capture_id = step->capture_ids[j];
if (step->capture_ids[j] == NONE) break;
array_push(capture_list, ((TSQueryCapture) { node, capture_id }));
LOG(
" capture node. type:%s, pattern:%u, capture_id:%u, capture_count:%u\n",
ts_node_type(node),
state->pattern_index,
capture_id,
capture_list->size
);
}
}
static QueryState *ts_query_cursor__copy_state(
TSQueryCursor *self,
QueryState **state_ref
) {
const QueryState *state = *state_ref;
uint32_t state_index = state - self->states.contents;
QueryState copy = *state;
copy.capture_list_id = NONE;
if (state->capture_list_id != NONE) {
CaptureList *new_captures = ts_query_cursor__prepare_to_capture(self, ©, state_index);
if (!new_captures) return NULL;
const CaptureList *old_captures = capture_list_pool_get(
&self->capture_list_pool,
state->capture_list_id
);
array_push_all(new_captures, old_captures);
}
array_insert(&self->states, state_index + 1, copy);
*state_ref = &self->states.contents[state_index];
return &self->states.contents[state_index + 1];
}
static inline bool ts_query_cursor__should_descend_outside_of_range(
TSQueryCursor *self
) {
for (unsigned i = 0; i < self->states.size; i++) {
QueryState *state = &self->states.contents[i];;
QueryStep *next_step = &self->query->steps.contents[state->step_index];
if (
next_step->depth != PATTERN_DONE_MARKER &&
state->start_depth + next_step->depth > self->depth
) {
return true;
}
}
if (!self->on_visible_node) {
Subtree subtree = ts_tree_cursor_current_subtree(&self->cursor);
if (ts_subtree_is_repetition(subtree)) {
bool exists;
uint32_t index;
array_search_sorted_by(
&self->query->repeat_symbols_with_rootless_patterns,,
ts_subtree_symbol(subtree),
&index,
&exists
);
return exists;
}
return true;
}
return false;
}
static inline bool ts_query_cursor__advance(
TSQueryCursor *self,
bool stop_on_definite_step
) {
bool did_match = false;
for (;;) {
if (self->halted) {
while (self->states.size > 0) {
QueryState state = array_pop(&self->states);
capture_list_pool_release(
&self->capture_list_pool,
state.capture_list_id
);
}
}
if (did_match || self->halted) return did_match;
if (self->ascending) {
if (self->on_visible_node) {
LOG(
"leave node. depth:%u, type:%s\n",
self->depth,
ts_node_type(ts_tree_cursor_current_node(&self->cursor))
);
}
switch (ts_tree_cursor_goto_next_sibling_internal(&self->cursor)) {
case TreeCursorStepVisible:
if (!self->on_visible_node) {
self->depth++;
self->on_visible_node = true;
}
self->ascending = false;
break;
case TreeCursorStepHidden:
if (self->on_visible_node) {
self->depth--;
self->on_visible_node = false;
}
self->ascending = false;
break;
default:
if (ts_tree_cursor_goto_parent(&self->cursor)) {
self->depth--;
} else {
LOG("halt at root\n");
self->halted = true;
}
}
if (self->on_visible_node) {
uint32_t deleted_count = 0;
for (unsigned i = 0, n = self->states.size; i < n; i++) {
QueryState *state = &self->states.contents[i];
QueryStep *step = &self->query->steps.contents[state->step_index];
if (step->depth == PATTERN_DONE_MARKER) {
if (state->start_depth > self->depth || self->halted) {
LOG(" finish pattern %u\n", state->pattern_index);
array_push(&self->finished_states, *state);
did_match = true;
deleted_count++;
continue;
}
}
else if ((uint32_t)state->start_depth + (uint32_t)step->depth > self->depth) {
LOG(
" failed to match. pattern:%u, step:%u\n",
state->pattern_index,
state->step_index
);
capture_list_pool_release(
&self->capture_list_pool,
state->capture_list_id
);
deleted_count++;
continue;
}
if (deleted_count > 0) {
self->states.contents[i - deleted_count] = *state;
}
}
self->states.size -= deleted_count;
}
}
else {
TSNode node = ts_tree_cursor_current_node(&self->cursor);
TSNode parent_node = ts_tree_cursor_parent_node(&self->cursor);
bool parent_precedes_range = !ts_node_is_null(parent_node) && (
ts_node_end_byte(parent_node) <= self->start_byte ||
point_lte(ts_node_end_point(parent_node), self->start_point)
);
bool parent_follows_range = !ts_node_is_null(parent_node) && (
ts_node_start_byte(parent_node) >= self->end_byte ||
point_gte(ts_node_start_point(parent_node), self->end_point)
);
bool node_precedes_range = parent_precedes_range || (
ts_node_end_byte(node) <= self->start_byte ||
point_lte(ts_node_end_point(node), self->start_point)
);
bool node_follows_range = parent_follows_range || (
ts_node_start_byte(node) >= self->end_byte ||
point_gte(ts_node_start_point(node), self->end_point)
);
bool parent_intersects_range = !parent_precedes_range && !parent_follows_range;
bool node_intersects_range = !node_precedes_range && !node_follows_range;
if (self->on_visible_node) {
TSSymbol symbol = ts_node_symbol(node);
bool is_named = ts_node_is_named(node);
bool has_later_siblings;
bool has_later_named_siblings;
bool can_have_later_siblings_with_this_field;
TSFieldId field_id = 0;
TSSymbol supertypes[8] = {0};
unsigned supertype_count = 8;
ts_tree_cursor_current_status(
&self->cursor,
&field_id,
&has_later_siblings,
&has_later_named_siblings,
&can_have_later_siblings_with_this_field,
supertypes,
&supertype_count
);
LOG(
"enter node. depth:%u, type:%s, field:%s, row:%u state_count:%u, finished_state_count:%u\n",
self->depth,
ts_node_type(node),
ts_language_field_name_for_id(self->query->language, field_id),
ts_node_start_point(node).row,
self->states.size,
self->finished_states.size
);
bool node_is_error = symbol == ts_builtin_sym_error;
bool parent_is_error =
!ts_node_is_null(parent_node) &&
ts_node_symbol(parent_node) == ts_builtin_sym_error;
if (!node_is_error) {
for (unsigned i = 0; i < self->query->wildcard_root_pattern_count; i++) {
PatternEntry *pattern = &self->query->pattern_map.contents[i];
QueryStep *step = &self->query->steps.contents[pattern->step_index];
if (
(pattern->is_rooted ?
node_intersects_range :
(parent_intersects_range && !parent_is_error)) &&
(!step->field || field_id == step->field) &&
(!step->supertype_symbol || supertype_count > 0)
) {
ts_query_cursor__add_state(self, pattern);
}
}
}
unsigned i;
if (ts_query__pattern_map_search(self->query, symbol, &i)) {
PatternEntry *pattern = &self->query->pattern_map.contents[i];
QueryStep *step = &self->query->steps.contents[pattern->step_index];
do {
if (
(pattern->is_rooted ?
node_intersects_range :
(parent_intersects_range && !parent_is_error)) &&
(!step->field || field_id == step->field)
) {
ts_query_cursor__add_state(self, pattern);
}
i++;
if (i == self->query->pattern_map.size) break;
pattern = &self->query->pattern_map.contents[i];
step = &self->query->steps.contents[pattern->step_index];
} while (step->symbol == symbol);
}
for (unsigned i = 0, copy_count = 0; i < self->states.size; i += 1 + copy_count) {
QueryState *state = &self->states.contents[i];
QueryStep *step = &self->query->steps.contents[state->step_index];
state->has_in_progress_alternatives = false;
copy_count = 0;
if ((uint32_t)state->start_depth + (uint32_t)step->depth != self->depth) continue;
bool node_does_match = false;
if (step->symbol == WILDCARD_SYMBOL) {
node_does_match = !node_is_error && (is_named || !step->is_named);
} else {
node_does_match = symbol == step->symbol;
}
bool later_sibling_can_match = has_later_siblings;
if ((step->is_immediate && is_named) || 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) {
bool has_supertype = false;
for (unsigned j = 0; j < supertype_count; j++) {
if (supertypes[j] == step->supertype_symbol) {
has_supertype = true;
break;
}
}
if (!has_supertype) node_does_match = false;
}
if (step->field) {
if (step->field == field_id) {
if (!can_have_later_siblings_with_this_field) {
later_sibling_can_match = false;
}
} else {
node_does_match = false;
}
}
if (step->negated_field_list_id) {
TSFieldId *negated_field_ids = &self->query->negated_fields.contents[step->negated_field_list_id];
for (;;) {
TSFieldId negated_field_id = *negated_field_ids;
if (negated_field_id) {
negated_field_ids++;
if (ts_node_child_by_field_id(node, negated_field_id).id) {
node_does_match = false;
break;
}
} else {
break;
}
}
}
if (!node_does_match) {
if (!later_sibling_can_match) {
LOG(
" discard state. pattern:%u, step:%u\n",
state->pattern_index,
state->step_index
);
capture_list_pool_release(
&self->capture_list_pool,
state->capture_list_id
);
array_erase(&self->states, i);
i--;
}
continue;
}
if (later_sibling_can_match && (
step->contains_captures ||
ts_query__step_is_fallible(self->query, state->step_index)
)) {
if (ts_query_cursor__copy_state(self, &state)) {
LOG(
" split state for capture. pattern:%u, step:%u\n",
state->pattern_index,
state->step_index
);
copy_count++;
}
}
if (state->needs_parent) {
TSNode parent = ts_tree_cursor_parent_node(&self->cursor);
if (ts_node_is_null(parent)) {
LOG(" missing parent node\n");
state->dead = true;
} else {
state->needs_parent = false;
QueryStep *skipped_wildcard_step = step;
do {
skipped_wildcard_step--;
} while (
skipped_wildcard_step->is_dead_end ||
skipped_wildcard_step->is_pass_through ||
skipped_wildcard_step->depth > 0
);
if (skipped_wildcard_step->capture_ids[0] != NONE) {
LOG(" capture wildcard parent\n");
ts_query_cursor__capture(
self,
state,
skipped_wildcard_step,
parent
);
}
}
}
if (step->capture_ids[0] != NONE) {
ts_query_cursor__capture(self, state, step, node);
}
if (state->dead) {
array_erase(&self->states, i);
i--;
continue;
}
state->step_index++;
state->seeking_immediate_match = false;
LOG(
" advance state. pattern:%u, step:%u\n",
state->pattern_index,
state->step_index
);
QueryStep *next_step = &self->query->steps.contents[state->step_index];
if (stop_on_definite_step && next_step->root_pattern_guaranteed) did_match = true;
unsigned end_index = i + 1;
for (unsigned j = i; j < end_index; j++) {
QueryState *state = &self->states.contents[j];
QueryStep *next_step = &self->query->steps.contents[state->step_index];
if (next_step->alternative_index != NONE) {
if (next_step->is_dead_end) {
state->step_index = next_step->alternative_index;
j--;
continue;
}
if (next_step->is_pass_through) {
state->step_index++;
j--;
}
QueryState *copy = ts_query_cursor__copy_state(self, &state);
if (copy) {
LOG(
" split state for branch. pattern:%u, from_step:%u, to_step:%u, immediate:%d, capture_count: %u\n",
copy->pattern_index,
copy->step_index,
next_step->alternative_index,
next_step->alternative_is_immediate,
capture_list_pool_get(&self->capture_list_pool, copy->capture_list_id)->size
);
end_index++;
copy_count++;
copy->step_index = next_step->alternative_index;
if (next_step->alternative_is_immediate) {
copy->seeking_immediate_match = true;
}
}
}
}
}
for (unsigned i = 0; i < self->states.size; i++) {
QueryState *state = &self->states.contents[i];
if (state->dead) {
array_erase(&self->states, i);
i--;
continue;
}
bool did_remove = false;
for (unsigned j = i + 1; j < self->states.size; j++) {
QueryState *other_state = &self->states.contents[j];
if (
other_state->start_depth != state->start_depth ||
other_state->pattern_index != state->pattern_index
) break;
bool left_contains_right, right_contains_left;
ts_query_cursor__compare_captures(
self,
state,
other_state,
&left_contains_right,
&right_contains_left
);
if (left_contains_right) {
if (state->step_index == other_state->step_index) {
LOG(
" drop shorter state. pattern: %u, step_index: %u\n",
state->pattern_index,
state->step_index
);
capture_list_pool_release(&self->capture_list_pool, other_state->capture_list_id);
array_erase(&self->states, j);
j--;
continue;
}
other_state->has_in_progress_alternatives = true;
}
if (right_contains_left) {
if (state->step_index == other_state->step_index) {
LOG(
" drop shorter state. pattern: %u, step_index: %u\n",
state->pattern_index,
state->step_index
);
capture_list_pool_release(&self->capture_list_pool, state->capture_list_id);
array_erase(&self->states, i);
i--;
did_remove = true;
break;
}
state->has_in_progress_alternatives = true;
}
}
if (!did_remove) {
LOG(
" keep state. pattern: %u, start_depth: %u, step_index: %u, capture_count: %u\n",
state->pattern_index,
state->start_depth,
state->step_index,
capture_list_pool_get(&self->capture_list_pool, state->capture_list_id)->size
);
QueryStep *next_step = &self->query->steps.contents[state->step_index];
if (next_step->depth == PATTERN_DONE_MARKER) {
if (state->has_in_progress_alternatives) {
LOG(" defer finishing pattern %u\n", state->pattern_index);
} else {
LOG(" finish pattern %u\n", state->pattern_index);
array_push(&self->finished_states, *state);
array_erase(&self->states, (uint32_t)(state - self->states.contents));
did_match = true;
i--;
}
}
}
}
}
bool should_descend =
node_intersects_range ||
ts_query_cursor__should_descend_outside_of_range(self);
if (should_descend) {
switch (ts_tree_cursor_goto_first_child_internal(&self->cursor)) {
case TreeCursorStepVisible:
self->depth++;
self->on_visible_node = true;
continue;
case TreeCursorStepHidden:
self->on_visible_node = false;
continue;
default:
break;
}
}
self->ascending = true;
}
}
}
bool ts_query_cursor_next_match(
TSQueryCursor *self,
TSQueryMatch *match
) {
if (self->finished_states.size == 0) {
if (!ts_query_cursor__advance(self, false)) {
return false;
}
}
QueryState *state = &self->finished_states.contents[0];
if (state->id == UINT32_MAX) state->id = self->next_state_id++;
match->id = state->id;
match->pattern_index = state->pattern_index;
const CaptureList *captures = capture_list_pool_get(
&self->capture_list_pool,
state->capture_list_id
);
match->captures = captures->contents;
match->capture_count = captures->size;
capture_list_pool_release(&self->capture_list_pool, state->capture_list_id);
array_erase(&self->finished_states, 0);
return true;
}
void ts_query_cursor_remove_match(
TSQueryCursor *self,
uint32_t match_id
) {
for (unsigned i = 0; i < self->finished_states.size; i++) {
const QueryState *state = &self->finished_states.contents[i];
if (state->id == match_id) {
capture_list_pool_release(
&self->capture_list_pool,
state->capture_list_id
);
array_erase(&self->finished_states, i);
return;
}
}
for (unsigned i = 0; i < self->states.size; i++) {
const QueryState *state = &self->states.contents[i];
if (state->id == match_id) {
capture_list_pool_release(
&self->capture_list_pool,
state->capture_list_id
);
array_erase(&self->states, i);
return;
}
}
}
bool ts_query_cursor_next_capture(
TSQueryCursor *self,
TSQueryMatch *match,
uint32_t *capture_index
) {
for (;;) {
uint32_t first_unfinished_capture_byte;
uint32_t first_unfinished_pattern_index;
uint32_t first_unfinished_state_index;
bool first_unfinished_state_is_definite = false;
ts_query_cursor__first_in_progress_capture(
self,
&first_unfinished_state_index,
&first_unfinished_capture_byte,
&first_unfinished_pattern_index,
&first_unfinished_state_is_definite
);
QueryState *first_finished_state = NULL;
uint32_t first_finished_capture_byte = first_unfinished_capture_byte;
uint32_t first_finished_pattern_index = first_unfinished_pattern_index;
for (unsigned i = 0; i < self->finished_states.size;) {
QueryState *state = &self->finished_states.contents[i];
const CaptureList *captures = capture_list_pool_get(
&self->capture_list_pool,
state->capture_list_id
);
if (state->consumed_capture_count >= captures->size) {
capture_list_pool_release(
&self->capture_list_pool,
state->capture_list_id
);
array_erase(&self->finished_states, i);
continue;
}
TSNode node = captures->contents[state->consumed_capture_count].node;
if (ts_node_end_byte(node) <= self->start_byte) {
state->consumed_capture_count++;
continue;
}
uint32_t node_start_byte = ts_node_start_byte(node);
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 = state;
first_finished_capture_byte = node_start_byte;
first_finished_pattern_index = state->pattern_index;
}
i++;
}
QueryState *state;
if (first_finished_state) {
state = first_finished_state;
} else if (first_unfinished_state_is_definite) {
state = &self->states.contents[first_unfinished_state_index];
} else {
state = NULL;
}
if (state) {
if (state->id == UINT32_MAX) state->id = self->next_state_id++;
match->id = state->id;
match->pattern_index = state->pattern_index;
const CaptureList *captures = capture_list_pool_get(
&self->capture_list_pool,
state->capture_list_id
);
match->captures = captures->contents;
match->capture_count = captures->size;
*capture_index = state->consumed_capture_count;
state->consumed_capture_count++;
return true;
}
if (capture_list_pool_is_empty(&self->capture_list_pool)) {
LOG(
" abandon state. index:%u, pattern:%u, offset:%u.\n",
first_unfinished_state_index,
first_unfinished_pattern_index,
first_unfinished_capture_byte
);
capture_list_pool_release(
&self->capture_list_pool,
self->states.contents[first_unfinished_state_index].capture_list_id
);
array_erase(&self->states, first_unfinished_state_index);
}
if (
!ts_query_cursor__advance(self, true) &&
self->finished_states.size == 0
) return false;
}
}
#undef LOG