From 79bd8d2ab6cae1c0be3233a9a7551d0b7bcc5944 Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Sat, 28 Sep 2019 18:41:49 +0200 Subject: tree-sitter: update vendored tree-sitter runtime tree-sitter/tree-sitter commit edb569310005c66838b7d69fa60850acac6abeee Included files are: lib/include/tree-sitter/*.h lib/src/*.[ch] lib/src/unicode/* LICENSE --- src/tree_sitter/api.h | 241 +++++- src/tree_sitter/bits.h | 29 + src/tree_sitter/language.c | 102 ++- src/tree_sitter/language.h | 3 + src/tree_sitter/lexer.c | 334 +++++---- src/tree_sitter/lexer.h | 2 +- src/tree_sitter/lib.c | 5 +- src/tree_sitter/node.c | 10 +- src/tree_sitter/parser.c | 41 +- src/tree_sitter/parser.h | 5 +- src/tree_sitter/point.h | 1 + src/tree_sitter/query.c | 1450 ++++++++++++++++++++++++++++++++++++ src/tree_sitter/subtree.c | 13 +- src/tree_sitter/tree.c | 7 +- src/tree_sitter/tree_cursor.c | 79 +- src/tree_sitter/tree_cursor.h | 1 + src/tree_sitter/unicode.h | 50 ++ src/tree_sitter/unicode/ICU_SHA | 1 + src/tree_sitter/unicode/LICENSE | 414 ++++++++++ src/tree_sitter/unicode/README.md | 29 + src/tree_sitter/unicode/ptypes.h | 1 + src/tree_sitter/unicode/umachine.h | 448 +++++++++++ src/tree_sitter/unicode/urename.h | 1 + src/tree_sitter/unicode/utf.h | 1 + src/tree_sitter/unicode/utf16.h | 733 ++++++++++++++++++ src/tree_sitter/unicode/utf8.h | 881 ++++++++++++++++++++++ 26 files changed, 4653 insertions(+), 229 deletions(-) create mode 100644 src/tree_sitter/bits.h create mode 100644 src/tree_sitter/query.c create mode 100644 src/tree_sitter/unicode.h create mode 100644 src/tree_sitter/unicode/ICU_SHA create mode 100644 src/tree_sitter/unicode/LICENSE create mode 100644 src/tree_sitter/unicode/README.md create mode 100644 src/tree_sitter/unicode/ptypes.h create mode 100644 src/tree_sitter/unicode/umachine.h create mode 100644 src/tree_sitter/unicode/urename.h create mode 100644 src/tree_sitter/unicode/utf.h create mode 100644 src/tree_sitter/unicode/utf16.h create mode 100644 src/tree_sitter/unicode/utf8.h (limited to 'src') diff --git a/src/tree_sitter/api.h b/src/tree_sitter/api.h index d39d0521ee..40187e3db0 100644 --- a/src/tree_sitter/api.h +++ b/src/tree_sitter/api.h @@ -14,7 +14,19 @@ extern "C" { /* Section - ABI Versioning */ /****************************/ +/** + * The latest ABI version that is supported by the current version of the + * library. When Languages are generated by the Tree-sitter CLI, they are + * assigned an ABI version number that corresponds to the current CLI version. + * The Tree-sitter library is generally backwards-compatible with languages + * generated using older CLI versions, but is not forwards-compatible. + */ #define TREE_SITTER_LANGUAGE_VERSION 11 + +/** + * The earliest ABI version that is supported by the current version of the + * library. + */ #define TREE_SITTER_MIN_COMPATIBLE_LANGUAGE_VERSION 9 /*******************/ @@ -26,6 +38,8 @@ typedef uint16_t TSFieldId; typedef struct TSLanguage TSLanguage; typedef struct TSParser TSParser; typedef struct TSTree TSTree; +typedef struct TSQuery TSQuery; +typedef struct TSQueryCursor TSQueryCursor; typedef enum { TSInputEncodingUTF8, @@ -87,6 +101,37 @@ typedef struct { uint32_t context[2]; } TSTreeCursor; +typedef struct { + TSNode node; + uint32_t index; +} TSQueryCapture; + +typedef struct { + uint32_t id; + uint16_t pattern_index; + uint16_t capture_count; + const TSQueryCapture *captures; +} TSQueryMatch; + +typedef enum { + TSQueryPredicateStepTypeDone, + TSQueryPredicateStepTypeCapture, + TSQueryPredicateStepTypeString, +} TSQueryPredicateStepType; + +typedef struct { + TSQueryPredicateStepType type; + uint32_t value_id; +} TSQueryPredicateStep; + +typedef enum { + TSQueryErrorNone = 0, + TSQueryErrorSyntax, + TSQueryErrorNodeType, + TSQueryErrorField, + TSQueryErrorCapture, +} TSQueryError; + /********************/ /* Section - Parser */ /********************/ @@ -119,7 +164,7 @@ bool ts_parser_set_language(TSParser *self, const TSLanguage *language); const TSLanguage *ts_parser_language(const TSParser *self); /** - * Set the spans of text that the parser should include when parsing. + * Set the ranges of text that the parser should include when parsing. * * By default, the parser will always include entire documents. This function * allows you to parse only a *portion* of a document but still return a syntax @@ -226,14 +271,16 @@ TSTree *ts_parser_parse_string_encoding( * by default, it will resume where it left off on the next call to * `ts_parser_parse` or other parsing functions. If you don't want to resume, * and instead intend to use this parser to parse some other document, you must - * call this `ts_parser_reset` first. + * call `ts_parser_reset` first. */ void ts_parser_reset(TSParser *self); /** * Set the maximum duration in microseconds that parsing should be allowed to - * take before halting. If parsing takes longer than this, it will halt early, - * returning NULL. See `ts_parser_parse` for more information. + * take before halting. + * + * If parsing takes longer than this, it will halt early, returning NULL. + * See `ts_parser_parse` for more information. */ void ts_parser_set_timeout_micros(TSParser *self, uint64_t timeout); @@ -243,10 +290,11 @@ void ts_parser_set_timeout_micros(TSParser *self, uint64_t timeout); uint64_t ts_parser_timeout_micros(const TSParser *self); /** - * Set the parser's current cancellation flag pointer. If a non-null pointer is - * assigned, then the parser will periodically read from this pointer during - * parsing. If it reads a non-zero value, it will halt early, returning NULL. - * See `ts_parser_parse` for more information. + * Set the parser's current cancellation flag pointer. + * + * If a non-null pointer is assigned, then the parser will periodically read + * from this pointer during parsing. If it reads a non-zero value, it will + * halt early, returning NULL. See `ts_parser_parse` for more information. */ void ts_parser_set_cancellation_flag(TSParser *self, const size_t *flag); @@ -322,22 +370,22 @@ const TSLanguage *ts_tree_language(const TSTree *); void ts_tree_edit(TSTree *self, const TSInputEdit *edit); /** - * Compare a new syntax tree to a previous syntax tree representing the same + * Compare an old edited syntax tree to a new syntax tree representing the same * document, returning an array of ranges whose syntactic structure has changed. * * For this to work correctly, the old syntax tree must have been edited such * that its ranges match up to the new tree. Generally, you'll want to call - * this function right after calling one of the `ts_parser_parse` functions, - * passing in the new tree that was returned from `ts_parser_parse` and the old - * tree that was passed as a parameter. + * this function right after calling one of the `ts_parser_parse` functions. + * You need to pass the old tree that was passed to parse, as well as the new + * tree that was returned from that function. * * The returned array is allocated using `malloc` and the caller is responsible * for freeing it using `free`. The length of the array will be written to the * given `length` pointer. */ TSRange *ts_tree_get_changed_ranges( - const TSTree *self, const TSTree *old_tree, + const TSTree *new_tree, uint32_t *length ); @@ -409,8 +457,8 @@ bool ts_node_is_named(TSNode); bool ts_node_is_missing(TSNode); /** - * Check if the node is *missing*. Missing nodes are inserted by the parser in - * order to recover from certain kinds of syntax errors. + * Check if the node is *extra*. Extra nodes represent things like comments, + * which are not required the grammar, but can appear anywhere. */ bool ts_node_is_extra(TSNode); @@ -542,7 +590,7 @@ TSTreeCursor ts_tree_cursor_new(TSNode); void ts_tree_cursor_delete(TSTreeCursor *); /** - * Re-initialize a tree cursor to start at a different ndoe. + * Re-initialize a tree cursor to start at a different node. */ void ts_tree_cursor_reset(TSTreeCursor *, TSNode); @@ -584,7 +632,7 @@ bool ts_tree_cursor_goto_parent(TSTreeCursor *); bool ts_tree_cursor_goto_next_sibling(TSTreeCursor *); /** - * Move the cursor to the first schild of its current node. + * Move the cursor to the first child of its current node. * * This returns `true` if the cursor successfully moved, and returns `false` * if there were no children. @@ -592,7 +640,7 @@ bool ts_tree_cursor_goto_next_sibling(TSTreeCursor *); bool ts_tree_cursor_goto_first_child(TSTreeCursor *); /** - * Move the cursor to the first schild of its current node that extends beyond + * Move the cursor to the first child of its current node that extends beyond * the given byte offset. * * This returns the index of the child node if one was found, and returns -1 @@ -602,6 +650,156 @@ int64_t ts_tree_cursor_goto_first_child_for_byte(TSTreeCursor *, uint32_t); TSTreeCursor ts_tree_cursor_copy(const TSTreeCursor *); +/*******************/ +/* Section - Query */ +/*******************/ + +/** + * Create a new query from a string containing one or more S-expression + * patterns. The query is associated with a particular language, and can + * only be run on syntax nodes parsed with that language. + * + * If all of the given patterns are valid, this returns a `TSQuery`. + * If a pattern is invalid, this returns `NULL`, and provides two pieces + * of information about the problem: + * 1. The byte offset of the error is written to the `error_offset` parameter. + * 2. The type of error is written to the `error_type` parameter. + */ +TSQuery *ts_query_new( + const TSLanguage *language, + const char *source, + uint32_t source_len, + uint32_t *error_offset, + TSQueryError *error_type +); + +/** + * Delete a query, freeing all of the memory that it used. + */ +void ts_query_delete(TSQuery *); + +/** + * Get the number of patterns, captures, or string literals in the query. + */ +uint32_t ts_query_pattern_count(const TSQuery *); +uint32_t ts_query_capture_count(const TSQuery *); +uint32_t ts_query_string_count(const TSQuery *); + +/** + * Get the byte offset where the given pattern starts in the query's source. + * + * This can be useful when combining queries by concatenating their source + * code strings. + */ +uint32_t ts_query_start_byte_for_pattern(const TSQuery *, uint32_t); + +/** + * Get all of the predicates for the given pattern in the query. + * + * The predicates are represented as a single array of steps. There are three + * types of steps in this array, which correspond to the three legal values for + * the `type` field: + * - `TSQueryPredicateStepTypeCapture` - Steps with this type represent names + * of captures. Their `value_id` can be used with the + * `ts_query_capture_name_for_id` function to obtain the name of the capture. + * - `TSQueryPredicateStepTypeString` - Steps with this type represent literal + * strings. Their `value_id` can be used with the + * `ts_query_string_value_for_id` function to obtain their string value. + * - `TSQueryPredicateStepTypeDone` - Steps with this type are *sentinels* + * that represent the end of an individual predicate. If a pattern has two + * predicates, then there will be two steps with this `type` in the array. + */ +const TSQueryPredicateStep *ts_query_predicates_for_pattern( + const TSQuery *self, + uint32_t pattern_index, + uint32_t *length +); + +/** + * Get the name and length of one of the query's captures, or one of the + * query's string literals. Each capture and string is associated with a + * numeric id based on the order that it appeared in the query's source. + */ +const char *ts_query_capture_name_for_id( + const TSQuery *, + uint32_t id, + uint32_t *length +); +const char *ts_query_string_value_for_id( + const TSQuery *, + uint32_t id, + uint32_t *length +); + +/** + * Disable a certain capture within a query. This prevents the capture + * from being returned in matches, and also avoids any resource usage + * associated with recording the capture. + */ +void ts_query_disable_capture(TSQuery *, const char *, uint32_t); + +/** + * Create a new cursor for executing a given query. + * + * The cursor stores the state that is needed to iteratively search + * for matches. To use the query cursor, first call `ts_query_cursor_exec` + * to start running a given query on a given syntax node. Then, there are + * two options for consuming the results of the query: + * 1. Repeatedly call `ts_query_cursor_next_match` to iterate over all of the + * the *matches* in the order that they were found. Each match contains the + * index of the pattern that matched, and an array of captures. Because + * multiple patterns can match the same set of nodes, one match may contain + * captures that appear *before* some of the captures from a previous match. + * 2. Repeatedly call `ts_query_cursor_next_capture` to iterate over all of the + * individual *captures* in the order that they appear. This is useful if + * don't care about which pattern matched, and just want a single ordered + * sequence of captures. + * + * If you don't care about consuming all of the results, you can stop calling + * `ts_query_cursor_next_match` or `ts_query_cursor_next_capture` at any point. + * You can then start executing another query on another node by calling + * `ts_query_cursor_exec` again. + */ +TSQueryCursor *ts_query_cursor_new(void); + +/** + * Delete a query cursor, freeing all of the memory that it used. + */ +void ts_query_cursor_delete(TSQueryCursor *); + +/** + * Start running a given query on a given node. + */ +void ts_query_cursor_exec(TSQueryCursor *, const TSQuery *, TSNode); + +/** + * Set the range of bytes or (row, column) positions in which the query + * will be executed. + */ +void ts_query_cursor_set_byte_range(TSQueryCursor *, uint32_t, uint32_t); +void ts_query_cursor_set_point_range(TSQueryCursor *, TSPoint, TSPoint); + +/** + * Advance to the next match of the currently running query. + * + * If there is a match, write it to `*match` and return `true`. + * Otherwise, return `false`. + */ +bool ts_query_cursor_next_match(TSQueryCursor *, TSQueryMatch *match); +void ts_query_cursor_remove_match(TSQueryCursor *, uint32_t id); + +/** + * Advance to the next capture of the currently running query. + * + * If there is a capture, write its match to `*match` and its index within + * the matche's capture list to `*capture_index`. Otherwise, return `false`. + */ +bool ts_query_cursor_next_capture( + TSQueryCursor *, + TSQueryMatch *match, + uint32_t *capture_index +); + /**********************/ /* Section - Language */ /**********************/ @@ -619,7 +817,12 @@ const char *ts_language_symbol_name(const TSLanguage *, TSSymbol); /** * Get the numerical id for the given node type string. */ -TSSymbol ts_language_symbol_for_name(const TSLanguage *, const char *); +TSSymbol ts_language_symbol_for_name( + const TSLanguage *self, + const char *string, + uint32_t length, + bool is_named +); /** * Get the number of distinct field names in the language. diff --git a/src/tree_sitter/bits.h b/src/tree_sitter/bits.h new file mode 100644 index 0000000000..3bec455dd1 --- /dev/null +++ b/src/tree_sitter/bits.h @@ -0,0 +1,29 @@ +#ifndef TREE_SITTER_BITS_H_ +#define TREE_SITTER_BITS_H_ + +#include + +static inline uint32_t bitmask_for_index(uint16_t id) { + return (1u << (31 - id)); +} + +#ifdef _WIN32 + +#include + +static inline uint32_t count_leading_zeros(uint32_t x) { + if (x == 0) return 32; + uint32_t result; + _BitScanReverse(&result, x); + return 31 - result; +} + +#else + +static inline uint32_t count_leading_zeros(uint32_t x) { + if (x == 0) return 32; + return __builtin_clz(x); +} + +#endif +#endif // TREE_SITTER_BITS_H_ diff --git a/src/tree_sitter/language.c b/src/tree_sitter/language.c index 1bfb1a8d03..e240ef2a53 100644 --- a/src/tree_sitter/language.c +++ b/src/tree_sitter/language.c @@ -3,8 +3,28 @@ #include "./error_costs.h" #include -void ts_language_table_entry(const TSLanguage *self, TSStateId state, - TSSymbol symbol, TableEntry *result) { +uint32_t ts_language_symbol_count(const TSLanguage *self) { + return self->symbol_count + self->alias_count; +} + +uint32_t ts_language_version(const TSLanguage *self) { + return self->version; +} + +uint32_t ts_language_field_count(const TSLanguage *self) { + if (self->version >= TREE_SITTER_LANGUAGE_VERSION_WITH_FIELDS) { + return self->field_count; + } else { + return 0; + } +} + +void ts_language_table_entry( + const TSLanguage *self, + TSStateId state, + TSSymbol symbol, + TableEntry *result +) { if (symbol == ts_builtin_sym_error || symbol == ts_builtin_sym_error_repeat) { result->action_count = 0; result->is_reusable = false; @@ -19,48 +39,72 @@ void ts_language_table_entry(const TSLanguage *self, TSStateId state, } } -uint32_t ts_language_symbol_count(const TSLanguage *language) { - return language->symbol_count + language->alias_count; -} - -uint32_t ts_language_version(const TSLanguage *language) { - return language->version; -} - -TSSymbolMetadata ts_language_symbol_metadata(const TSLanguage *language, TSSymbol symbol) { +TSSymbolMetadata ts_language_symbol_metadata( + const TSLanguage *self, + TSSymbol symbol +) { if (symbol == ts_builtin_sym_error) { return (TSSymbolMetadata){.visible = true, .named = true}; } else if (symbol == ts_builtin_sym_error_repeat) { return (TSSymbolMetadata){.visible = false, .named = false}; } else { - return language->symbol_metadata[symbol]; + return self->symbol_metadata[symbol]; + } +} + +TSSymbol ts_language_public_symbol( + const TSLanguage *self, + TSSymbol symbol +) { + if (symbol == ts_builtin_sym_error) return symbol; + if (self->version >= TREE_SITTER_LANGUAGE_VERSION_WITH_SYMBOL_DEDUPING) { + return self->public_symbol_map[symbol]; + } else { + return symbol; } } -const char *ts_language_symbol_name(const TSLanguage *language, TSSymbol symbol) { +const char *ts_language_symbol_name( + const TSLanguage *self, + TSSymbol symbol +) { if (symbol == ts_builtin_sym_error) { return "ERROR"; } else if (symbol == ts_builtin_sym_error_repeat) { return "_ERROR"; } else { - return language->symbol_names[symbol]; + return self->symbol_names[symbol]; } } -TSSymbol ts_language_symbol_for_name(const TSLanguage *self, const char *name) { - if (!strcmp(name, "ERROR")) return ts_builtin_sym_error; - +TSSymbol ts_language_symbol_for_name( + const TSLanguage *self, + const char *string, + uint32_t length, + bool is_named +) { + if (!strncmp(string, "ERROR", length)) return ts_builtin_sym_error; uint32_t count = ts_language_symbol_count(self); for (TSSymbol i = 0; i < count; i++) { - if (!strcmp(self->symbol_names[i], name)) { - return i; + TSSymbolMetadata metadata = ts_language_symbol_metadata(self, i); + if (!metadata.visible || metadata.named != is_named) continue; + const char *symbol_name = self->symbol_names[i]; + if (!strncmp(symbol_name, string, length) && !symbol_name[length]) { + if (self->version >= TREE_SITTER_LANGUAGE_VERSION_WITH_SYMBOL_DEDUPING) { + return self->public_symbol_map[i]; + } else { + return i; + } } } return 0; } -TSSymbolType ts_language_symbol_type(const TSLanguage *language, TSSymbol symbol) { - TSSymbolMetadata metadata = ts_language_symbol_metadata(language, symbol); +TSSymbolType ts_language_symbol_type( + const TSLanguage *self, + TSSymbol symbol +) { + TSSymbolMetadata metadata = ts_language_symbol_metadata(self, symbol); if (metadata.named) { return TSSymbolTypeRegular; } else if (metadata.visible) { @@ -70,15 +114,10 @@ TSSymbolType ts_language_symbol_type(const TSLanguage *language, TSSymbol symbol } } -uint32_t ts_language_field_count(const TSLanguage *self) { - if (self->version >= TREE_SITTER_LANGUAGE_VERSION_WITH_FIELDS) { - return self->field_count; - } else { - return 0; - } -} - -const char *ts_language_field_name_for_id(const TSLanguage *self, TSFieldId id) { +const char *ts_language_field_name_for_id( + const TSLanguage *self, + TSFieldId id +) { uint32_t count = ts_language_field_count(self); if (count) { return self->field_names[id]; @@ -96,7 +135,8 @@ TSFieldId ts_language_field_id_for_name( for (TSSymbol i = 1; i < count + 1; i++) { switch (strncmp(name, self->field_names[i], name_length)) { case 0: - return i; + if (self->field_names[i][name_length] == 0) return i; + break; case -1: return 0; default: diff --git a/src/tree_sitter/language.h b/src/tree_sitter/language.h index 0741486a1b..d7e17c3d70 100644 --- a/src/tree_sitter/language.h +++ b/src/tree_sitter/language.h @@ -10,6 +10,7 @@ extern "C" { #define ts_builtin_sym_error_repeat (ts_builtin_sym_error - 1) #define TREE_SITTER_LANGUAGE_VERSION_WITH_FIELDS 10 +#define TREE_SITTER_LANGUAGE_VERSION_WITH_SYMBOL_DEDUPING 11 #define TREE_SITTER_LANGUAGE_VERSION_WITH_SMALL_STATES 11 typedef struct { @@ -22,6 +23,8 @@ void ts_language_table_entry(const TSLanguage *, TSStateId, TSSymbol, TableEntry TSSymbolMetadata ts_language_symbol_metadata(const TSLanguage *, TSSymbol); +TSSymbol ts_language_public_symbol(const TSLanguage *, TSSymbol); + static inline bool ts_language_is_symbol_external(const TSLanguage *self, TSSymbol symbol) { return 0 < symbol && symbol < self->external_token_count + 1; } diff --git a/src/tree_sitter/lexer.c b/src/tree_sitter/lexer.c index fdc127466f..e2ca851973 100644 --- a/src/tree_sitter/lexer.c +++ b/src/tree_sitter/lexer.c @@ -2,26 +2,58 @@ #include "./lexer.h" #include "./subtree.h" #include "./length.h" -#include "./utf16.h" -#include "utf8proc.h" - -#define LOG(...) \ - if (self->logger.log) { \ - snprintf(self->debug_buffer, TREE_SITTER_SERIALIZATION_BUFFER_SIZE, __VA_ARGS__); \ - self->logger.log(self->logger.payload, TSLogTypeLex, self->debug_buffer); \ +#include "./unicode.h" + +#define LOG(message, character) \ + if (self->logger.log) { \ + snprintf( \ + self->debug_buffer, \ + TREE_SITTER_SERIALIZATION_BUFFER_SIZE, \ + 32 <= character && character < 127 ? \ + message " character:'%c'" : \ + message " character:%d", \ + character \ + ); \ + self->logger.log( \ + self->logger.payload, \ + TSLogTypeLex, \ + self->debug_buffer \ + ); \ } -#define LOG_CHARACTER(message, character) \ - LOG( \ - 32 <= character && character < 127 ? \ - message " character:'%c'" : \ - message " character:%d", character \ - ) +static const int32_t BYTE_ORDER_MARK = 0xFEFF; -static const char empty_chunk[3] = { 0, 0 }; +static const TSRange DEFAULT_RANGE = { + .start_point = { + .row = 0, + .column = 0, + }, + .end_point = { + .row = UINT32_MAX, + .column = UINT32_MAX, + }, + .start_byte = 0, + .end_byte = UINT32_MAX +}; -static const int32_t BYTE_ORDER_MARK = 0xFEFF; +// Check if the lexer has reached EOF. This state is stored +// by setting the lexer's `current_included_range_index` such that +// it has consumed all of its available ranges. +static bool ts_lexer__eof(const TSLexer *_self) { + Lexer *self = (Lexer *)_self; + return self->current_included_range_index == self->included_range_count; +} + +// Clear the currently stored chunk of source code, because the lexer's +// position has changed. +static void ts_lexer__clear_chunk(Lexer *self) { + self->chunk = NULL; + self->chunk_size = 0; + self->chunk_start = 0; +} +// Call the lexer's input callback to obtain a new chunk of source code +// for the current position. static void ts_lexer__get_chunk(Lexer *self) { self->chunk_start = self->current_position.bytes; self->chunk = self->input.read( @@ -30,15 +62,15 @@ static void ts_lexer__get_chunk(Lexer *self) { self->current_position.extent, &self->chunk_size ); - if (!self->chunk_size) self->chunk = empty_chunk; + if (!self->chunk_size) { + self->current_included_range_index = self->included_range_count; + self->chunk = NULL; + } } -typedef utf8proc_ssize_t (*DecodeFunction)( - const utf8proc_uint8_t *, - utf8proc_ssize_t, - utf8proc_int32_t * -); - +// Decode the next unicode character in the current chunk of source code. +// This assumes that the lexer has already retrieved a chunk of source +// code that spans the current position. static void ts_lexer__get_lookahead(Lexer *self) { uint32_t position_in_chunk = self->current_position.bytes - self->chunk_start; const uint8_t *chunk = (const uint8_t *)self->chunk + position_in_chunk; @@ -50,29 +82,37 @@ static void ts_lexer__get_lookahead(Lexer *self) { return; } - DecodeFunction decode = - self->input.encoding == TSInputEncodingUTF8 ? utf8proc_iterate : utf16_iterate; + UnicodeDecodeFunction decode = self->input.encoding == TSInputEncodingUTF8 + ? ts_decode_utf8 + : ts_decode_utf16; self->lookahead_size = decode(chunk, size, &self->data.lookahead); // If this chunk ended in the middle of a multi-byte character, // try again with a fresh chunk. - if (self->data.lookahead == -1 && size < 4) { + if (self->data.lookahead == TS_DECODE_ERROR && size < 4) { ts_lexer__get_chunk(self); chunk = (const uint8_t *)self->chunk; size = self->chunk_size; self->lookahead_size = decode(chunk, size, &self->data.lookahead); } - if (self->data.lookahead == -1) { + if (self->data.lookahead == TS_DECODE_ERROR) { self->lookahead_size = 1; } } -static void ts_lexer__advance(TSLexer *payload, bool skip) { - Lexer *self = (Lexer *)payload; - if (self->chunk == empty_chunk) - return; +// Advance to the next character in the source code, retrieving a new +// chunk of source code if needed. +static void ts_lexer__advance(TSLexer *_self, bool skip) { + Lexer *self = (Lexer *)_self; + if (!self->chunk) return; + + if (skip) { + LOG("skip", self->data.lookahead); + } else { + LOG("consume", self->data.lookahead); + } if (self->lookahead_size) { self->current_position.bytes += self->lookahead_size; @@ -84,53 +124,65 @@ static void ts_lexer__advance(TSLexer *payload, bool skip) { } } - TSRange *current_range = &self->included_ranges[self->current_included_range_index]; - if (self->current_position.bytes == current_range->end_byte) { - self->current_included_range_index++; - if (self->current_included_range_index == self->included_range_count) { - self->data.lookahead = '\0'; - self->lookahead_size = 1; - return; - } else { - current_range++; - self->current_position = (Length) { - current_range->start_byte, - current_range->start_point, - }; + const TSRange *current_range = NULL; + if (self->current_included_range_index < self->included_range_count) { + current_range = &self->included_ranges[self->current_included_range_index]; + if (self->current_position.bytes == current_range->end_byte) { + self->current_included_range_index++; + if (self->current_included_range_index < self->included_range_count) { + current_range++; + self->current_position = (Length) { + current_range->start_byte, + current_range->start_point, + }; + } else { + current_range = NULL; + } } } - if (skip) { - LOG_CHARACTER("skip", self->data.lookahead); - self->token_start_position = self->current_position; - } else { - LOG_CHARACTER("consume", self->data.lookahead); - } + if (skip) self->token_start_position = self->current_position; - if (self->current_position.bytes >= self->chunk_start + self->chunk_size) { - ts_lexer__get_chunk(self); + if (current_range) { + if (self->current_position.bytes >= self->chunk_start + self->chunk_size) { + ts_lexer__get_chunk(self); + } + ts_lexer__get_lookahead(self); + } else { + ts_lexer__clear_chunk(self); + self->data.lookahead = '\0'; + self->lookahead_size = 1; } - - ts_lexer__get_lookahead(self); } -static void ts_lexer__mark_end(TSLexer *payload) { - Lexer *self = (Lexer *)payload; - TSRange *current_included_range = &self->included_ranges[self->current_included_range_index]; - if (self->current_included_range_index > 0 && - self->current_position.bytes == current_included_range->start_byte) { - TSRange *previous_included_range = current_included_range - 1; - self->token_end_position = (Length) { - previous_included_range->end_byte, - previous_included_range->end_point, - }; - } else { - self->token_end_position = self->current_position; +// Mark that a token match has completed. This can be called multiple +// times if a longer match is found later. +static void ts_lexer__mark_end(TSLexer *_self) { + Lexer *self = (Lexer *)_self; + if (!ts_lexer__eof(&self->data)) { + // If the lexer is right at the beginning of included range, + // then the token should be considered to end at the *end* of the + // previous included range, rather than here. + TSRange *current_included_range = &self->included_ranges[ + self->current_included_range_index + ]; + if ( + self->current_included_range_index > 0 && + self->current_position.bytes == current_included_range->start_byte + ) { + TSRange *previous_included_range = current_included_range - 1; + self->token_end_position = (Length) { + previous_included_range->end_byte, + previous_included_range->end_point, + }; + return; + } } + self->token_end_position = self->current_position; } -static uint32_t ts_lexer__get_column(TSLexer *payload) { - Lexer *self = (Lexer *)payload; +static uint32_t ts_lexer__get_column(TSLexer *_self) { + Lexer *self = (Lexer *)_self; uint32_t goal_byte = self->current_position.bytes; self->current_position.bytes -= self->current_position.extent.column; @@ -142,67 +194,69 @@ static uint32_t ts_lexer__get_column(TSLexer *payload) { uint32_t result = 0; while (self->current_position.bytes < goal_byte) { - ts_lexer__advance(payload, false); + ts_lexer__advance(&self->data, false); result++; } return result; } -static bool ts_lexer__is_at_included_range_start(TSLexer *payload) { - const Lexer *self = (const Lexer *)payload; - TSRange *current_range = &self->included_ranges[self->current_included_range_index]; - return self->current_position.bytes == current_range->start_byte; +// Is the lexer at a boundary between two disjoint included ranges of +// source code? This is exposed as an API because some languages' external +// scanners need to perform custom actions at these bounaries. +static bool ts_lexer__is_at_included_range_start(const TSLexer *_self) { + const Lexer *self = (const Lexer *)_self; + if (self->current_included_range_index < self->included_range_count) { + TSRange *current_range = &self->included_ranges[self->current_included_range_index]; + return self->current_position.bytes == current_range->start_byte; + } else { + return false; + } } -// The lexer's methods are stored as a struct field so that generated -// parsers can call them without needing to be linked against this library. - void ts_lexer_init(Lexer *self) { *self = (Lexer) { .data = { + // The lexer's methods are stored as struct fields so that generated + // parsers can call them without needing to be linked against this + // library. .advance = ts_lexer__advance, .mark_end = ts_lexer__mark_end, .get_column = ts_lexer__get_column, .is_at_included_range_start = ts_lexer__is_at_included_range_start, + .eof = ts_lexer__eof, .lookahead = 0, .result_symbol = 0, }, .chunk = NULL, + .chunk_size = 0, .chunk_start = 0, - .current_position = {UINT32_MAX, {0, 0}}, + .current_position = {0, {0, 0}}, .logger = { .payload = NULL, .log = NULL }, + .included_ranges = NULL, + .included_range_count = 0, .current_included_range_index = 0, }; - - self->included_ranges = NULL; ts_lexer_set_included_ranges(self, NULL, 0); - ts_lexer_reset(self, length_zero()); } void ts_lexer_delete(Lexer *self) { ts_free(self->included_ranges); } -void ts_lexer_set_input(Lexer *self, TSInput input) { - self->input = input; - self->data.lookahead = 0; - self->lookahead_size = 0; - self->chunk = 0; - self->chunk_start = 0; - self->chunk_size = 0; -} - static void ts_lexer_goto(Lexer *self, Length position) { + self->current_position = position; bool found_included_range = false; + + // Move to the first valid position at or after the given position. for (unsigned i = 0; i < self->included_range_count; i++) { TSRange *included_range = &self->included_ranges[i]; if (included_range->end_byte > position.bytes) { if (included_range->start_byte > position.bytes) { - position = (Length) { + self->current_position = (Length) { .bytes = included_range->start_byte, .extent = included_range->start_point, }; @@ -214,46 +268,61 @@ static void ts_lexer_goto(Lexer *self, Length position) { } } - if (!found_included_range) { + if (found_included_range) { + // If the current position is outside of the current chunk of text, + // then clear out the current chunk of text. + if (self->chunk && ( + position.bytes < self->chunk_start || + position.bytes >= self->chunk_start + self->chunk_size + )) { + ts_lexer__clear_chunk(self); + } + + self->lookahead_size = 0; + self->data.lookahead = '\0'; + } + + // If the given position is beyond any of included ranges, move to the EOF + // state - past the end of the included ranges. + else { + self->current_included_range_index = self->included_range_count; TSRange *last_included_range = &self->included_ranges[self->included_range_count - 1]; - position = (Length) { + self->current_position = (Length) { .bytes = last_included_range->end_byte, .extent = last_included_range->end_point, }; - self->chunk = empty_chunk; - self->chunk_start = position.bytes; - self->chunk_size = 2; - } - - self->token_start_position = position; - self->token_end_position = LENGTH_UNDEFINED; - self->current_position = position; - - if (self->chunk && (position.bytes < self->chunk_start || - position.bytes >= self->chunk_start + self->chunk_size)) { - self->chunk = 0; - self->chunk_start = 0; - self->chunk_size = 0; + ts_lexer__clear_chunk(self); + self->lookahead_size = 1; + self->data.lookahead = '\0'; } +} - self->lookahead_size = 0; - self->data.lookahead = 0; +void ts_lexer_set_input(Lexer *self, TSInput input) { + self->input = input; + ts_lexer__clear_chunk(self); + ts_lexer_goto(self, self->current_position); } +// Move the lexer to the given position. This doesn't do any work +// if the parser is already at the given position. void ts_lexer_reset(Lexer *self, Length position) { - if (position.bytes != self->current_position.bytes) ts_lexer_goto(self, position); + if (position.bytes != self->current_position.bytes) { + ts_lexer_goto(self, position); + } } void ts_lexer_start(Lexer *self) { self->token_start_position = self->current_position; self->token_end_position = LENGTH_UNDEFINED; self->data.result_symbol = 0; - if (!self->chunk) ts_lexer__get_chunk(self); - if (!self->lookahead_size) ts_lexer__get_lookahead(self); - if ( - self->current_position.bytes == 0 && - self->data.lookahead == BYTE_ORDER_MARK - ) ts_lexer__advance((TSLexer *)self, true); + if (!ts_lexer__eof(&self->data)) { + if (!self->chunk_size) ts_lexer__get_chunk(self); + if (!self->lookahead_size) ts_lexer__get_lookahead(self); + if ( + self->current_position.bytes == 0 && + self->data.lookahead == BYTE_ORDER_MARK + ) ts_lexer__advance(&self->data, true); + } } void ts_lexer_finish(Lexer *self, uint32_t *lookahead_end_byte) { @@ -267,7 +336,7 @@ void ts_lexer_finish(Lexer *self, uint32_t *lookahead_end_byte) { // the character decoding algorithm may have looked at the following byte. // Therefore, the next byte *after* the current (invalid) character // affects the interpretation of the current character. - if (self->data.lookahead == -1) { + if (self->data.lookahead == TS_DECODE_ERROR) { current_lookahead_end_byte++; } @@ -277,8 +346,8 @@ void ts_lexer_finish(Lexer *self, uint32_t *lookahead_end_byte) { } void ts_lexer_advance_to_end(Lexer *self) { - while (self->data.lookahead != 0) { - ts_lexer__advance((TSLexer *)self, false); + while (self->chunk) { + ts_lexer__advance(&self->data, false); } } @@ -286,30 +355,19 @@ void ts_lexer_mark_end(Lexer *self) { ts_lexer__mark_end(&self->data); } -static const TSRange DEFAULT_RANGES[] = { - { - .start_point = { - .row = 0, - .column = 0, - }, - .end_point = { - .row = UINT32_MAX, - .column = UINT32_MAX, - }, - .start_byte = 0, - .end_byte = UINT32_MAX - } -}; - -void ts_lexer_set_included_ranges(Lexer *self, const TSRange *ranges, uint32_t count) { - if (!ranges) { - ranges = DEFAULT_RANGES; +void ts_lexer_set_included_ranges( + Lexer *self, + const TSRange *ranges, + uint32_t count +) { + if (count == 0 || !ranges) { + ranges = &DEFAULT_RANGE; count = 1; } - size_t sz = count * sizeof(TSRange); - self->included_ranges = ts_realloc(self->included_ranges, sz); - memcpy(self->included_ranges, ranges, sz); + size_t size = count * sizeof(TSRange); + self->included_ranges = ts_realloc(self->included_ranges, size); + memcpy(self->included_ranges, ranges, size); self->included_range_count = count; ts_lexer_goto(self, self->current_position); } diff --git a/src/tree_sitter/lexer.h b/src/tree_sitter/lexer.h index f523d88f65..8cd9c26706 100644 --- a/src/tree_sitter/lexer.h +++ b/src/tree_sitter/lexer.h @@ -16,7 +16,7 @@ typedef struct { Length token_start_position; Length token_end_position; - TSRange * included_ranges; + TSRange *included_ranges; size_t included_range_count; size_t current_included_range_index; diff --git a/src/tree_sitter/lib.c b/src/tree_sitter/lib.c index fc5fbc9210..289d32f4c5 100644 --- a/src/tree_sitter/lib.c +++ b/src/tree_sitter/lib.c @@ -2,19 +2,16 @@ // // The following directories must be added to the include path: // - include -// - utf8proc #define _POSIX_C_SOURCE 200112L -#define UTF8PROC_STATIC #include "./get_changed_ranges.c" #include "./language.c" #include "./lexer.c" #include "./node.c" #include "./parser.c" +#include "./query.c" #include "./stack.c" #include "./subtree.c" #include "./tree_cursor.c" #include "./tree.c" -#include "./utf16.c" -#include "utf8proc.c" diff --git a/src/tree_sitter/node.c b/src/tree_sitter/node.c index 6b2be36ee5..b03e2fc979 100644 --- a/src/tree_sitter/node.c +++ b/src/tree_sitter/node.c @@ -415,13 +415,15 @@ TSPoint ts_node_end_point(TSNode self) { } TSSymbol ts_node_symbol(TSNode self) { - return ts_node__alias(&self) - ? ts_node__alias(&self) - : ts_subtree_symbol(ts_node__subtree(self)); + TSSymbol symbol = ts_node__alias(&self); + if (!symbol) symbol = ts_subtree_symbol(ts_node__subtree(self)); + return ts_language_public_symbol(self.tree->language, symbol); } const char *ts_node_type(TSNode self) { - return ts_language_symbol_name(self.tree->language, ts_node_symbol(self)); + TSSymbol symbol = ts_node__alias(&self); + if (!symbol) symbol = ts_subtree_symbol(ts_node__subtree(self)); + return ts_language_symbol_name(self.tree->language, symbol); } char *ts_node_string(TSNode self) { diff --git a/src/tree_sitter/parser.c b/src/tree_sitter/parser.c index 88b20845fd..f381afccab 100644 --- a/src/tree_sitter/parser.c +++ b/src/tree_sitter/parser.c @@ -351,6 +351,7 @@ static Subtree ts_parser__lex( Length start_position = ts_stack_position(self->stack, version); Subtree external_token = ts_stack_last_external_token(self->stack, version); TSLexMode lex_mode = self->language->lex_modes[parse_state]; + if (lex_mode.lex_state == (uint16_t)-1) return NULL_SUBTREE; const bool *valid_external_tokens = ts_language_enabled_external_tokens( self->language, lex_mode.external_lex_state @@ -438,7 +439,7 @@ static Subtree ts_parser__lex( } if (self->lexer.current_position.bytes == error_end_position.bytes) { - if (self->lexer.data.lookahead == 0) { + if (self->lexer.data.eof(&self->lexer.data)) { self->lexer.data.result_symbol = ts_builtin_sym_error; break; } @@ -748,7 +749,8 @@ static StackVersion ts_parser__reduce( uint32_t count, int dynamic_precedence, uint16_t production_id, - bool fragile + bool is_fragile, + bool is_extra ) { uint32_t initial_version_count = ts_stack_version_count(self->stack); uint32_t removed_version_count = 0; @@ -813,7 +815,8 @@ static StackVersion ts_parser__reduce( TSStateId state = ts_stack_state(self->stack, slice_version); TSStateId next_state = ts_language_next_state(self->language, state, symbol); - if (fragile || pop.size > 1 || initial_version_count > 1) { + if (is_extra) parent.ptr->extra = true; + if (is_fragile || pop.size > 1 || initial_version_count > 1) { parent.ptr->fragile_left = true; parent.ptr->fragile_right = true; parent.ptr->parse_state = TS_TREE_STATE_NONE; @@ -962,7 +965,7 @@ static bool ts_parser__do_all_potential_reductions( reduction_version = ts_parser__reduce( self, version, action.symbol, action.count, action.dynamic_precedence, action.production_id, - true + true, false ); } @@ -1366,8 +1369,17 @@ static bool ts_parser__advance( // Otherwise, re-run the lexer. if (!lookahead.ptr) { lookahead = ts_parser__lex(self, version, state); - ts_parser__set_cached_token(self, position, last_external_token, lookahead); - ts_language_table_entry(self->language, state, ts_subtree_symbol(lookahead), &table_entry); + if (lookahead.ptr) { + ts_parser__set_cached_token(self, position, last_external_token, lookahead); + ts_language_table_entry(self->language, state, ts_subtree_symbol(lookahead), &table_entry); + } + + // When parsing a non-terminal extra, a null lookahead indicates the + // end of the rule. The reduction is stored in the EOF table entry. + // After the reduction, the lexer needs to be run again. + else { + ts_language_table_entry(self->language, state, ts_builtin_sym_end, &table_entry); + } } for (;;) { @@ -1422,11 +1434,12 @@ static bool ts_parser__advance( case TSParseActionTypeReduce: { bool is_fragile = table_entry.action_count > 1; + bool is_extra = lookahead.ptr == NULL; LOG("reduce sym:%s, child_count:%u", SYM_NAME(action.params.symbol), action.params.child_count); StackVersion reduction_version = ts_parser__reduce( self, version, action.params.symbol, action.params.child_count, action.params.dynamic_precedence, action.params.production_id, - is_fragile + is_fragile, is_extra ); if (reduction_version != STACK_VERSION_NONE) { last_reduction_version = reduction_version; @@ -1459,6 +1472,15 @@ static bool ts_parser__advance( ts_stack_renumber_version(self->stack, last_reduction_version, version); LOG_STACK(); state = ts_stack_state(self->stack, version); + + // At the end of a non-terminal extra rule, the lexer will return a + // null subtree, because the parser needs to perform a fixed reduction + // regardless of the lookahead node. After performing that reduction, + // (and completing the non-terminal extra rule) run the lexer again based + // on the current parse state. + if (!lookahead.ptr) { + lookahead = ts_parser__lex(self, version, state); + } ts_language_table_entry( self->language, state, @@ -1655,6 +1677,7 @@ TSParser *ts_parser_new(void) { void ts_parser_delete(TSParser *self) { if (!self) return; + ts_parser_set_language(self, NULL); ts_stack_delete(self->stack); if (self->reduce_actions.contents) { array_delete(&self->reduce_actions); @@ -1670,7 +1693,6 @@ void ts_parser_delete(TSParser *self) { ts_parser__set_cached_token(self, 0, NULL_SUBTREE, NULL_SUBTREE); ts_subtree_pool_delete(&self->tree_pool); reusable_node_delete(&self->reusable_node); - ts_parser_set_language(self, NULL); ts_free(self); } @@ -1695,6 +1717,7 @@ bool ts_parser_set_language(TSParser *self, const TSLanguage *language) { } self->language = language; + ts_parser_reset(self); return true; } @@ -1747,7 +1770,7 @@ const TSRange *ts_parser_included_ranges(const TSParser *self, uint32_t *count) } void ts_parser_reset(TSParser *self) { - if (self->language->external_scanner.deserialize) { + if (self->language && self->language->external_scanner.deserialize) { self->language->external_scanner.deserialize(self->external_scanner_payload, NULL, 0); } diff --git a/src/tree_sitter/parser.h b/src/tree_sitter/parser.h index 974a7ca52f..9df91f8c3c 100644 --- a/src/tree_sitter/parser.h +++ b/src/tree_sitter/parser.h @@ -45,7 +45,8 @@ struct TSLexer { void (*advance)(TSLexer *, bool); void (*mark_end)(TSLexer *); uint32_t (*get_column)(TSLexer *); - bool (*is_at_included_range_start)(TSLexer *); + bool (*is_at_included_range_start)(const TSLexer *); + bool (*eof)(const TSLexer *); }; typedef enum { @@ -117,6 +118,7 @@ struct TSLanguage { uint32_t large_state_count; const uint16_t *small_parse_table; const uint32_t *small_parse_table_map; + const TSSymbol *public_symbol_map; }; /* @@ -126,6 +128,7 @@ struct TSLanguage { #define START_LEXER() \ bool result = false; \ bool skip = false; \ + bool eof = false; \ int32_t lookahead; \ goto start; \ next_state: \ diff --git a/src/tree_sitter/point.h b/src/tree_sitter/point.h index 4d0aed18ef..a50d20214b 100644 --- a/src/tree_sitter/point.h +++ b/src/tree_sitter/point.h @@ -3,6 +3,7 @@ #include "tree_sitter/api.h" +#define POINT_ZERO ((TSPoint) {0, 0}) #define POINT_MAX ((TSPoint) {UINT32_MAX, UINT32_MAX}) static inline TSPoint point__new(unsigned row, unsigned column) { diff --git a/src/tree_sitter/query.c b/src/tree_sitter/query.c new file mode 100644 index 0000000000..a5ce86032c --- /dev/null +++ b/src/tree_sitter/query.c @@ -0,0 +1,1450 @@ +#include "tree_sitter/api.h" +#include "./alloc.h" +#include "./array.h" +#include "./bits.h" +#include "./language.h" +#include "./point.h" +#include "./tree_cursor.h" +#include "./unicode.h" +#include + +/* + * Stream - A sequence of unicode characters derived from a UTF8 string. + * This struct is used in parsing queries from S-expressions. + */ +typedef struct { + const char *input; + const char *end; + int32_t next; + uint8_t next_size; +} Stream; + +/* + * QueryStep - A step in the process of matching a query. Each node within + * a query S-expression maps to one of these steps. An entire pattern is + * represented as a sequence of these steps. Fields: + * + * - `symbol` - The grammar symbol to match. A zero value represents the + * wildcard symbol, '*'. + * - `field` - The field name to match. A zero value means that a field name + * was not specified. + * - `capture_id` - An integer representing the name of the capture associated + * with this node in the pattern. A `NONE` value means this node is not + * captured in this pattern. + * - `depth` - The depth where this node occurs in the pattern. The root node + * of the pattern has depth zero. + */ +typedef struct { + TSSymbol symbol; + TSFieldId field; + uint16_t capture_id; + uint16_t depth: 15; + bool contains_captures: 1; +} QueryStep; + +/* + * Slice - A slice of an external array. Within a query, capture names, + * literal string values, and predicate step informations are stored in three + * contiguous arrays. Individual captures, string values, and predicates are + * represented as slices of these three arrays. + */ +typedef struct { + uint32_t offset; + uint32_t length; +} Slice; + +/* + * SymbolTable - a two-way mapping of strings to ids. + */ +typedef struct { + Array(char) characters; + Array(Slice) slices; +} SymbolTable; + +/* + * PatternEntry - The set of steps needed to match a particular pattern, + * represented as a slice of a shared array. These entries are stored in a + * 'pattern map' - a sorted array that makes it possible to efficiently lookup + * patterns based on the symbol for their first step. + */ +typedef struct { + uint16_t step_index; + uint16_t pattern_index; +} PatternEntry; + +/* + * QueryState - The state of an in-progress match of a particular pattern + * in a query. While executing, a `TSQueryCursor` must keep track of a number + * of possible in-progress matches. Each of those possible matches is + * represented as one of these states. + */ +typedef struct { + uint16_t start_depth; + uint16_t pattern_index; + uint16_t step_index; + uint16_t capture_count; + uint16_t capture_list_id; + uint16_t consumed_capture_count; + uint32_t id; +} QueryState; + +/* + * CaptureListPool - A collection of *lists* of captures. Each QueryState + * needs to maintain its own list of captures. They are all represented as + * slices of one shared array. The CaptureListPool keeps track of which + * parts of the shared array are currently in use by a QueryState. + */ +typedef struct { + Array(TSQueryCapture) list; + uint32_t usage_map; +} CaptureListPool; + +/* + * TSQuery - A tree query, compiled from a string of S-expressions. The query + * itself is immutable. The mutable state used in the process of executing the + * query is stored in a `TSQueryCursor`. + */ +struct TSQuery { + SymbolTable captures; + SymbolTable predicate_values; + Array(QueryStep) steps; + Array(PatternEntry) pattern_map; + Array(TSQueryPredicateStep) predicate_steps; + Array(Slice) predicates_by_pattern; + Array(uint32_t) start_bytes_by_pattern; + const TSLanguage *language; + uint16_t max_capture_count; + uint16_t wildcard_root_pattern_count; + TSSymbol *symbol_map; +}; + +/* + * TSQueryCursor - A stateful struct used to execute a query on a tree. + */ +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; + uint32_t next_state_id; + TSPoint start_point; + TSPoint end_point; + bool ascending; +}; + +static const TSQueryError PARENT_DONE = -1; +static const uint8_t PATTERN_DONE_MARKER = UINT8_MAX; +static const uint16_t NONE = UINT16_MAX; +static const TSSymbol WILDCARD_SYMBOL = 0; +static const uint16_t MAX_STATE_COUNT = 32; + +// #define LOG(...) fprintf(stderr, __VA_ARGS__) +#define LOG(...) + +/********** + * Stream + **********/ + +// Advance to the next unicode code point in the stream. +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; +} + +// Reset the stream to the given input position, represented as a pointer +// into the input string. +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, + .end = string + length, + }; + stream_advance(&self); + return self; +} + +static void stream_skip_whitespace(Stream *stream) { + for (;;) { + if (iswspace(stream->next)) { + stream_advance(stream); + } else if (stream->next == ';') { + // skip over comments + stream_advance(stream); + while (stream->next && stream->next != '\n') { + if (!stream_advance(stream)) break; + } + } else { + break; + } + } +} + +static bool stream_is_ident_start(Stream *stream) { + return iswalnum(stream->next) || stream->next == '_' || stream->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 == '!' + ); +} + +/****************** + * CaptureListPool + ******************/ + +static CaptureListPool capture_list_pool_new() { + return (CaptureListPool) { + .list = array_new(), + .usage_map = UINT32_MAX, + }; +} + +static void capture_list_pool_reset(CaptureListPool *self, uint16_t list_size) { + self->usage_map = UINT32_MAX; + uint32_t total_size = MAX_STATE_COUNT * list_size; + array_reserve(&self->list, total_size); + self->list.size = total_size; +} + +static void capture_list_pool_delete(CaptureListPool *self) { + array_delete(&self->list); +} + +static TSQueryCapture *capture_list_pool_get(CaptureListPool *self, uint16_t id) { + return &self->list.contents[id * (self->list.size / MAX_STATE_COUNT)]; +} + +static bool capture_list_pool_is_empty(const CaptureListPool *self) { + return self->usage_map == 0; +} + +static uint16_t capture_list_pool_acquire(CaptureListPool *self) { + // In the usage_map bitmask, ones represent free lists, and zeros represent + // lists that are in use. A free list id can quickly be found by counting + // the leading zeros in the usage map. An id of zero corresponds to the + // highest-order bit in the bitmask. + uint16_t id = count_leading_zeros(self->usage_map); + if (id == 32) return NONE; + self->usage_map &= ~bitmask_for_index(id); + return id; +} + +static void capture_list_pool_release(CaptureListPool *self, uint16_t id) { + self->usage_map |= bitmask_for_index(id); +} + +/************** + * SymbolTable + **************/ + +static SymbolTable symbol_table_new() { + 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; +} + +/********* + * Query + *********/ + +// The `pattern_map` contains a mapping from TSSymbol values to indices in the +// `steps` array. For a given syntax node, the `pattern_map` makes it possible +// to quickly find the starting steps of all of the patterns whose root matches +// that node. Each entry has two fields: a `pattern_index`, which identifies one +// of the patterns in the query, and a `step_index`, which indicates the start +// offset of that pattern's steps pattern within the `steps` array. +// +// The entries are sorted by the patterns' root symbols, and lookups use a +// binary search. This ensures that the cost of this initial lookup step +// scales logarithmically with the number of patterns in the query. +// +// This returns `true` if the symbol is present and `false` otherwise. +// If the symbol is not present `*result` is set to the index where the +// symbol should be inserted. +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; +} + +// Insert a new pattern's start index into the pattern map, maintaining +// the pattern map's ordering invariant. +static inline void ts_query__pattern_map_insert( + TSQuery *self, + TSSymbol symbol, + uint32_t start_step_index +) { + uint32_t index; + ts_query__pattern_map_search(self, symbol, &index); + array_insert(&self->pattern_map, index, ((PatternEntry) { + .step_index = start_step_index, + .pattern_index = self->pattern_map.size, + })); +} + +static void ts_query__finalize_steps(TSQuery *self) { + for (unsigned i = 0; i < self->steps.size; i++) { + QueryStep *step = &self->steps.contents[i]; + uint32_t depth = step->depth; + if (step->capture_id != NONE) { + step->contains_captures = true; + } else { + step->contains_captures = false; + for (unsigned j = i + 1; j < self->steps.size; j++) { + QueryStep *s = &self->steps.contents[j]; + if (s->depth == PATTERN_DONE_MARKER || s->depth <= depth) break; + if (s->capture_id != NONE) step->contains_captures = true; + } + } + } +} + +// Parse a single predicate associated with a pattern, adding it to the +// query's internal `predicate_steps` array. Predicates are arbitrary +// S-expressions associated with a pattern which are meant to be handled at +// a higher level of abstraction, such as the Rust/JavaScript bindings. They +// can contain '@'-prefixed capture names, double-quoted strings, and bare +// symbols, which also represent strings. +static TSQueryError ts_query__parse_predicate( + TSQuery *self, + Stream *stream +) { + if (stream->next == ')') return PARENT_DONE; + if (stream->next != '(') return TSQueryErrorSyntax; + stream_advance(stream); + stream_skip_whitespace(stream); + + unsigned step_count = 0; + for (;;) { + if (stream->next == ')') { + stream_advance(stream); + stream_skip_whitespace(stream); + array_back(&self->predicates_by_pattern)->length++; + array_push(&self->predicate_steps, ((TSQueryPredicateStep) { + .type = TSQueryPredicateStepTypeDone, + .value_id = 0, + })); + break; + } + + // Parse an '@'-prefixed capture name + else if (stream->next == '@') { + stream_advance(stream); + + // Parse the capture name + 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; + + // Add the capture id to the first step of the pattern + 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_back(&self->predicates_by_pattern)->length++; + array_push(&self->predicate_steps, ((TSQueryPredicateStep) { + .type = TSQueryPredicateStepTypeCapture, + .value_id = capture_id, + })); + } + + // Parse a string literal + else if (stream->next == '"') { + stream_advance(stream); + + // Parse the string content + const char *string_content = stream->input; + while (stream->next != '"') { + if (stream->next == '\n' || !stream_advance(stream)) { + stream_reset(stream, string_content - 1); + return TSQueryErrorSyntax; + } + } + uint32_t length = stream->input - string_content; + + // Add a step for the node + uint16_t id = symbol_table_insert_name( + &self->predicate_values, + string_content, + length + ); + array_back(&self->predicates_by_pattern)->length++; + array_push(&self->predicate_steps, ((TSQueryPredicateStep) { + .type = TSQueryPredicateStepTypeString, + .value_id = id, + })); + + if (stream->next != '"') return TSQueryErrorSyntax; + stream_advance(stream); + } + + // Parse a bare symbol + 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_back(&self->predicates_by_pattern)->length++; + array_push(&self->predicate_steps, ((TSQueryPredicateStep) { + .type = TSQueryPredicateStepTypeString, + .value_id = id, + })); + } + + else { + return TSQueryErrorSyntax; + } + + step_count++; + stream_skip_whitespace(stream); + } + + return 0; +} + +// Read one S-expression pattern from the stream, and incorporate it into +// the query's internal state machine representation. For nested patterns, +// this function calls itself recursively. +static TSQueryError ts_query__parse_pattern( + TSQuery *self, + Stream *stream, + uint32_t depth, + uint32_t *capture_count +) { + uint16_t starting_step_index = self->steps.size; + + if (stream->next == 0) return TSQueryErrorSyntax; + + // Finish the parent S-expression + if (stream->next == ')') { + return PARENT_DONE; + } + + // Parse a parenthesized node expression + else if (stream->next == '(') { + stream_advance(stream); + stream_skip_whitespace(stream); + + // Parse a nested list, which represents a pattern followed by + // zero-or-more predicates. + if (stream->next == '(' && depth == 0) { + TSQueryError e = ts_query__parse_pattern(self, stream, 0, capture_count); + if (e) return e; + + // Parse the predicates. + stream_skip_whitespace(stream); + for (;;) { + TSQueryError e = ts_query__parse_predicate(self, stream); + if (e == PARENT_DONE) { + stream_advance(stream); + stream_skip_whitespace(stream); + return 0; + } else if (e) { + return e; + } + } + } + + TSSymbol symbol; + + // Parse the wildcard symbol + if (stream->next == '*') { + symbol = WILDCARD_SYMBOL; + stream_advance(stream); + } + + // Parse a normal node name + else if (stream_is_ident_start(stream)) { + const char *node_name = stream->inpu