1#include <stdbool.h>
2#include "./subtree.h"
3#include "./tree.h"
4#include "./language.h"
5
6typedef struct {
7 Subtree parent;
8 const TSTree *tree;
9 Length position;
10 uint32_t child_index;
11 uint32_t structural_child_index;
12 const TSSymbol *alias_sequence;
13} NodeChildIterator;
14
15// TSNode - constructors
16
17TSNode ts_node_new(
18 const TSTree *tree,
19 const Subtree *subtree,
20 Length position,
21 TSSymbol alias
22) {
23 return (TSNode) {
24 {position.bytes, position.extent.row, position.extent.column, alias},
25 subtree,
26 tree,
27 };
28}
29
30static inline TSNode ts_node__null(void) {
31 return ts_node_new(NULL, NULL, length_zero(), 0);
32}
33
34// TSNode - accessors
35
36uint32_t ts_node_start_byte(TSNode self) {
37 return self.context[0];
38}
39
40TSPoint ts_node_start_point(TSNode self) {
41 return (TSPoint) {self.context[1], self.context[2]};
42}
43
44static inline uint32_t ts_node__alias(const TSNode *self) {
45 return self->context[3];
46}
47
48static inline Subtree ts_node__subtree(TSNode self) {
49 return *(const Subtree *)self.id;
50}
51
52// NodeChildIterator
53
54static inline NodeChildIterator ts_node_iterate_children(const TSNode *node) {
55 Subtree subtree = ts_node__subtree(*node);
56 if (ts_subtree_child_count(subtree) == 0) {
57 return (NodeChildIterator) {NULL_SUBTREE, node->tree, length_zero(), 0, 0, NULL};
58 }
59 const TSSymbol *alias_sequence = ts_language_alias_sequence(
60 node->tree->language,
61 subtree.ptr->production_id
62 );
63 return (NodeChildIterator) {
64 .tree = node->tree,
65 .parent = subtree,
66 .position = {ts_node_start_byte(*node), ts_node_start_point(*node)},
67 .child_index = 0,
68 .structural_child_index = 0,
69 .alias_sequence = alias_sequence,
70 };
71}
72
73static inline bool ts_node_child_iterator_done(NodeChildIterator *self) {
74 return self->child_index == self->parent.ptr->child_count;
75}
76
77static inline bool ts_node_child_iterator_next(
78 NodeChildIterator *self,
79 TSNode *result
80) {
81 if (!self->parent.ptr || ts_node_child_iterator_done(self)) return false;
82 const Subtree *child = &ts_subtree_children(self->parent)[self->child_index];
83 TSSymbol alias_symbol = 0;
84 if (!ts_subtree_extra(*child)) {
85 if (self->alias_sequence) {
86 alias_symbol = self->alias_sequence[self->structural_child_index];
87 }
88 self->structural_child_index++;
89 }
90 if (self->child_index > 0) {
91 self->position = length_add(self->position, ts_subtree_padding(*child));
92 }
93 *result = ts_node_new(
94 self->tree,
95 child,
96 self->position,
97 alias_symbol
98 );
99 self->position = length_add(self->position, ts_subtree_size(*child));
100 self->child_index++;
101 return true;
102}
103
104// TSNode - private
105
106static inline bool ts_node__is_relevant(TSNode self, bool include_anonymous) {
107 Subtree tree = ts_node__subtree(self);
108 if (include_anonymous) {
109 return ts_subtree_visible(tree) || ts_node__alias(&self);
110 } else {
111 TSSymbol alias = ts_node__alias(&self);
112 if (alias) {
113 return ts_language_symbol_metadata(self.tree->language, alias).named;
114 } else {
115 return ts_subtree_visible(tree) && ts_subtree_named(tree);
116 }
117 }
118}
119
120static inline uint32_t ts_node__relevant_child_count(
121 TSNode self,
122 bool include_anonymous
123) {
124 Subtree tree = ts_node__subtree(self);
125 if (ts_subtree_child_count(tree) > 0) {
126 if (include_anonymous) {
127 return tree.ptr->visible_child_count;
128 } else {
129 return tree.ptr->named_child_count;
130 }
131 } else {
132 return 0;
133 }
134}
135
136static inline TSNode ts_node__child(
137 TSNode self,
138 uint32_t child_index,
139 bool include_anonymous
140) {
141 TSNode result = self;
142 bool did_descend = true;
143
144 while (did_descend) {
145 did_descend = false;
146
147 TSNode child;
148 uint32_t index = 0;
149 NodeChildIterator iterator = ts_node_iterate_children(&result);
150 while (ts_node_child_iterator_next(&iterator, &child)) {
151 if (ts_node__is_relevant(child, include_anonymous)) {
152 if (index == child_index) {
153 return child;
154 }
155 index++;
156 } else {
157 uint32_t grandchild_index = child_index - index;
158 uint32_t grandchild_count = ts_node__relevant_child_count(child, include_anonymous);
159 if (grandchild_index < grandchild_count) {
160 did_descend = true;
161 result = child;
162 child_index = grandchild_index;
163 break;
164 }
165 index += grandchild_count;
166 }
167 }
168 }
169
170 return ts_node__null();
171}
172
173static bool ts_subtree_has_trailing_empty_descendant(
174 Subtree self,
175 Subtree other
176) {
177 for (unsigned i = ts_subtree_child_count(self) - 1; i + 1 > 0; i--) {
178 Subtree child = ts_subtree_children(self)[i];
179 if (ts_subtree_total_bytes(child) > 0) break;
180 if (child.ptr == other.ptr || ts_subtree_has_trailing_empty_descendant(child, other)) {
181 return true;
182 }
183 }
184 return false;
185}
186
187static inline TSNode ts_node__prev_sibling(TSNode self, bool include_anonymous) {
188 Subtree self_subtree = ts_node__subtree(self);
189 bool self_is_empty = ts_subtree_total_bytes(self_subtree) == 0;
190 uint32_t target_end_byte = ts_node_end_byte(self);
191
192 TSNode node = ts_node_parent(self);
193 TSNode earlier_node = ts_node__null();
194 bool earlier_node_is_relevant = false;
195
196 while (!ts_node_is_null(node)) {
197 TSNode earlier_child = ts_node__null();
198 bool earlier_child_is_relevant = false;
199 bool found_child_containing_target = false;
200
201 TSNode child;
202 NodeChildIterator iterator = ts_node_iterate_children(&node);
203 while (ts_node_child_iterator_next(&iterator, &child)) {
204 if (child.id == self.id) break;
205 if (iterator.position.bytes > target_end_byte) {
206 found_child_containing_target = true;
207 break;
208 }
209
210 if (iterator.position.bytes == target_end_byte &&
211 (!self_is_empty ||
212 ts_subtree_has_trailing_empty_descendant(ts_node__subtree(child), self_subtree))) {
213 found_child_containing_target = true;
214 break;
215 }
216
217 if (ts_node__is_relevant(child, include_anonymous)) {
218 earlier_child = child;
219 earlier_child_is_relevant = true;
220 } else if (ts_node__relevant_child_count(child, include_anonymous) > 0) {
221 earlier_child = child;
222 earlier_child_is_relevant = false;
223 }
224 }
225
226 if (found_child_containing_target) {
227 if (!ts_node_is_null(earlier_child)) {
228 earlier_node = earlier_child;
229 earlier_node_is_relevant = earlier_child_is_relevant;
230 }
231 node = child;
232 } else if (earlier_child_is_relevant) {
233 return earlier_child;
234 } else if (!ts_node_is_null(earlier_child)) {
235 node = earlier_child;
236 } else if (earlier_node_is_relevant) {
237 return earlier_node;
238 } else {
239 node = earlier_node;
240 earlier_node = ts_node__null();
241 earlier_node_is_relevant = false;
242 }
243 }
244
245 return ts_node__null();
246}
247
248static inline TSNode ts_node__next_sibling(TSNode self, bool include_anonymous) {
249 uint32_t target_end_byte = ts_node_end_byte(self);
250
251 TSNode node = ts_node_parent(self);
252 TSNode later_node = ts_node__null();
253 bool later_node_is_relevant = false;
254
255 while (!ts_node_is_null(node)) {
256 TSNode later_child = ts_node__null();
257 bool later_child_is_relevant = false;
258 TSNode child_containing_target = ts_node__null();
259
260 TSNode child;
261 NodeChildIterator iterator = ts_node_iterate_children(&node);
262 while (ts_node_child_iterator_next(&iterator, &child)) {
263 if (iterator.position.bytes < target_end_byte) continue;
264 if (ts_node_start_byte(child) <= ts_node_start_byte(self)) {
265 if (ts_node__subtree(child).ptr != ts_node__subtree(self).ptr) {
266 child_containing_target = child;
267 }
268 } else if (ts_node__is_relevant(child, include_anonymous)) {
269 later_child = child;
270 later_child_is_relevant = true;
271 break;
272 } else if (ts_node__relevant_child_count(child, include_anonymous) > 0) {
273 later_child = child;
274 later_child_is_relevant = false;
275 break;
276 }
277 }
278
279 if (!ts_node_is_null(child_containing_target)) {
280 if (!ts_node_is_null(later_child)) {
281 later_node = later_child;
282 later_node_is_relevant = later_child_is_relevant;
283 }
284 node = child_containing_target;
285 } else if (later_child_is_relevant) {
286 return later_child;
287 } else if (!ts_node_is_null(later_child)) {
288 node = later_child;
289 } else if (later_node_is_relevant) {
290 return later_node;
291 } else {
292 node = later_node;
293 }
294 }
295
296 return ts_node__null();
297}
298
299static inline TSNode ts_node__first_child_for_byte(
300 TSNode self,
301 uint32_t goal,
302 bool include_anonymous
303) {
304 TSNode node = self;
305 bool did_descend = true;
306
307 while (did_descend) {
308 did_descend = false;
309
310 TSNode child;
311 NodeChildIterator iterator = ts_node_iterate_children(&node);
312 while (ts_node_child_iterator_next(&iterator, &child)) {
313 if (ts_node_end_byte(child) > goal) {
314 if (ts_node__is_relevant(child, include_anonymous)) {
315 return child;
316 } else if (ts_node_child_count(child) > 0) {
317 did_descend = true;
318 node = child;
319 break;
320 }
321 }
322 }
323 }
324
325 return ts_node__null();
326}
327
328static inline TSNode ts_node__descendant_for_byte_range(
329 TSNode self,
330 uint32_t range_start,
331 uint32_t range_end,
332 bool include_anonymous
333) {
334 TSNode node = self;
335 TSNode last_visible_node = self;
336
337 bool did_descend = true;
338 while (did_descend) {
339 did_descend = false;
340
341 TSNode child;
342 NodeChildIterator iterator = ts_node_iterate_children(&node);
343 while (ts_node_child_iterator_next(&iterator, &child)) {
344 uint32_t node_end = iterator.position.bytes;
345
346 // The end of this node must extend far enough forward to touch
347 // the end of the range and exceed the start of the range.
348 if (node_end < range_end) continue;
349 if (node_end <= range_start) continue;
350
351 // The start of this node must extend far enough backward to
352 // touch the start of the range.
353 if (range_start < ts_node_start_byte(child)) break;
354
355 node = child;
356 if (ts_node__is_relevant(node, include_anonymous)) {
357 last_visible_node = node;
358 }
359 did_descend = true;
360 break;
361 }
362 }
363
364 return last_visible_node;
365}
366
367static inline TSNode ts_node__descendant_for_point_range(
368 TSNode self,
369 TSPoint range_start,
370 TSPoint range_end,
371 bool include_anonymous
372) {
373 TSNode node = self;
374 TSNode last_visible_node = self;
375
376 bool did_descend = true;
377 while (did_descend) {
378 did_descend = false;
379
380 TSNode child;
381 NodeChildIterator iterator = ts_node_iterate_children(&node);
382 while (ts_node_child_iterator_next(&iterator, &child)) {
383 TSPoint node_end = iterator.position.extent;
384
385 // The end of this node must extend far enough forward to touch
386 // the end of the range and exceed the start of the range.
387 if (point_lt(node_end, range_end)) continue;
388 if (point_lte(node_end, range_start)) continue;
389
390 // The start of this node must extend far enough backward to
391 // touch the start of the range.
392 if (point_lt(range_start, ts_node_start_point(child))) break;
393
394 node = child;
395 if (ts_node__is_relevant(node, include_anonymous)) {
396 last_visible_node = node;
397 }
398 did_descend = true;
399 break;
400 }
401 }
402
403 return last_visible_node;
404}
405
406// TSNode - public
407
408uint32_t ts_node_end_byte(TSNode self) {
409 return ts_node_start_byte(self) + ts_subtree_size(ts_node__subtree(self)).bytes;
410}
411
412TSPoint ts_node_end_point(TSNode self) {
413 return point_add(ts_node_start_point(self), ts_subtree_size(ts_node__subtree(self)).extent);
414}
415
416TSSymbol ts_node_symbol(TSNode self) {
417 TSSymbol symbol = ts_node__alias(&self);
418 if (!symbol) symbol = ts_subtree_symbol(ts_node__subtree(self));
419 return ts_language_public_symbol(self.tree->language, symbol);
420}
421
422const char *ts_node_type(TSNode self) {
423 TSSymbol symbol = ts_node__alias(&self);
424 if (!symbol) symbol = ts_subtree_symbol(ts_node__subtree(self));
425 return ts_language_symbol_name(self.tree->language, symbol);
426}
427
428const TSLanguage *ts_node_language(TSNode self) {
429 return self.tree->language;
430}
431
432TSSymbol ts_node_grammar_symbol(TSNode self) {
433 return ts_subtree_symbol(ts_node__subtree(self));
434}
435
436const char *ts_node_grammar_type(TSNode self) {
437 TSSymbol symbol = ts_subtree_symbol(ts_node__subtree(self));
438 return ts_language_symbol_name(self.tree->language, symbol);
439}
440
441char *ts_node_string(TSNode self) {
442 TSSymbol alias_symbol = ts_node__alias(&self);
443 return ts_subtree_string(
444 ts_node__subtree(self),
445 alias_symbol,
446 ts_language_symbol_metadata(self.tree->language, alias_symbol).visible,
447 self.tree->language,
448 false
449 );
450}
451
452bool ts_node_eq(TSNode self, TSNode other) {
453 return self.tree == other.tree && self.id == other.id;
454}
455
456bool ts_node_is_null(TSNode self) {
457 return self.id == 0;
458}
459
460bool ts_node_is_extra(TSNode self) {
461 return ts_subtree_extra(ts_node__subtree(self));
462}
463
464bool ts_node_is_named(TSNode self) {
465 TSSymbol alias = ts_node__alias(&self);
466 return alias
467 ? ts_language_symbol_metadata(self.tree->language, alias).named
468 : ts_subtree_named(ts_node__subtree(self));
469}
470
471bool ts_node_is_missing(TSNode self) {
472 return ts_subtree_missing(ts_node__subtree(self));
473}
474
475bool ts_node_has_changes(TSNode self) {
476 return ts_subtree_has_changes(ts_node__subtree(self));
477}
478
479bool ts_node_has_error(TSNode self) {
480 return ts_subtree_error_cost(ts_node__subtree(self)) > 0;
481}
482
483bool ts_node_is_error(TSNode self) {
484 TSSymbol symbol = ts_node_symbol(self);
485 return symbol == ts_builtin_sym_error;
486}
487
488uint32_t ts_node_descendant_count(TSNode self) {
489 return ts_subtree_visible_descendant_count(ts_node__subtree(self)) + 1;
490}
491
492TSStateId ts_node_parse_state(TSNode self) {
493 return ts_subtree_parse_state(ts_node__subtree(self));
494}
495
496TSStateId ts_node_next_parse_state(TSNode self) {
497 const TSLanguage *language = self.tree->language;
498 uint16_t state = ts_node_parse_state(self);
499 if (state == TS_TREE_STATE_NONE) {
500 return TS_TREE_STATE_NONE;
501 }
502 uint16_t symbol = ts_node_grammar_symbol(self);
503 return ts_language_next_state(language, state, symbol);
504}
505
506TSNode ts_node_parent(TSNode self) {
507 TSNode node = ts_tree_root_node(self.tree);
508 uint32_t end_byte = ts_node_end_byte(self);
509 if (node.id == self.id) return ts_node__null();
510
511 TSNode last_visible_node = node;
512 bool did_descend = true;
513 while (did_descend) {
514 did_descend = false;
515
516 TSNode child;
517 NodeChildIterator iterator = ts_node_iterate_children(&node);
518 while (ts_node_child_iterator_next(&iterator, &child)) {
519 if (
520 ts_node_start_byte(child) > ts_node_start_byte(self) ||
521 child.id == self.id
522 ) break;
523 if (iterator.position.bytes >= end_byte && ts_node_child_count(child) > 0) {
524 node = child;
525 if (ts_node__is_relevant(child, true)) {
526 last_visible_node = node;
527 }
528 did_descend = true;
529 break;
530 }
531 }
532 }
533
534 return last_visible_node;
535}
536
537TSNode ts_node_child(TSNode self, uint32_t child_index) {
538 return ts_node__child(self, child_index, true);
539}
540
541TSNode ts_node_named_child(TSNode self, uint32_t child_index) {
542 return ts_node__child(self, child_index, false);
543}
544
545TSNode ts_node_child_by_field_id(TSNode self, TSFieldId field_id) {
546recur:
547 if (!field_id || ts_node_child_count(self) == 0) return ts_node__null();
548
549 const TSFieldMapEntry *field_map, *field_map_end;
550 ts_language_field_map(
551 self.tree->language,
552 ts_node__subtree(self).ptr->production_id,
553 &field_map,
554 &field_map_end
555 );
556 if (field_map == field_map_end) return ts_node__null();
557
558 // The field mappings are sorted by their field id. Scan all
559 // the mappings to find the ones for the given field id.
560 while (field_map->field_id < field_id) {
561 field_map++;
562 if (field_map == field_map_end) return ts_node__null();
563 }
564 while (field_map_end[-1].field_id > field_id) {
565 field_map_end--;
566 if (field_map == field_map_end) return ts_node__null();
567 }
568
569 TSNode child;
570 NodeChildIterator iterator = ts_node_iterate_children(&self);
571 while (ts_node_child_iterator_next(&iterator, &child)) {
572 if (!ts_subtree_extra(ts_node__subtree(child))) {
573 uint32_t index = iterator.structural_child_index - 1;
574 if (index < field_map->child_index) continue;
575
576 // Hidden nodes' fields are "inherited" by their visible parent.
577 if (field_map->inherited) {
578
579 // If this is the *last* possible child node for this field,
580 // then perform a tail call to avoid recursion.
581 if (field_map + 1 == field_map_end) {
582 self = child;
583 goto recur;
584 }
585
586 // Otherwise, descend into this child, but if it doesn't contain
587 // the field, continue searching subsequent children.
588 else {
589 TSNode result = ts_node_child_by_field_id(child, field_id);
590 if (result.id) return result;
591 field_map++;
592 if (field_map == field_map_end) return ts_node__null();
593 }
594 }
595
596 else if (ts_node__is_relevant(child, true)) {
597 return child;
598 }
599
600 // If the field refers to a hidden node with visible children,
601 // return the first visible child.
602 else if (ts_node_child_count(child) > 0 ) {
603 return ts_node_child(child, 0);
604 }
605
606 // Otherwise, continue searching subsequent children.
607 else {
608 field_map++;
609 if (field_map == field_map_end) return ts_node__null();
610 }
611 }
612 }
613
614 return ts_node__null();
615}
616
617static inline const char *ts_node__field_name_from_language(TSNode self, uint32_t structural_child_index) {
618 const TSFieldMapEntry *field_map, *field_map_end;
619 ts_language_field_map(
620 self.tree->language,
621 ts_node__subtree(self).ptr->production_id,
622 &field_map,
623 &field_map_end
624 );
625 for (; field_map != field_map_end; field_map++) {
626 if (!field_map->inherited && field_map->child_index == structural_child_index) {
627 return self.tree->language->field_names[field_map->field_id];
628 }
629 }
630 return NULL;
631}
632
633const char *ts_node_field_name_for_child(TSNode self, uint32_t child_index) {
634 TSNode result = self;
635 bool did_descend = true;
636 const char *inherited_field_name = NULL;
637
638 while (did_descend) {
639 did_descend = false;
640
641 TSNode child;
642 uint32_t index = 0;
643 NodeChildIterator iterator = ts_node_iterate_children(&result);
644 while (ts_node_child_iterator_next(&iterator, &child)) {
645 if (ts_node__is_relevant(child, true)) {
646 if (index == child_index) {
647 const char *field_name = ts_node__field_name_from_language(result, iterator.structural_child_index - 1);
648 if (field_name) return field_name;
649 return inherited_field_name;
650 }
651 index++;
652 } else {
653 uint32_t grandchild_index = child_index - index;
654 uint32_t grandchild_count = ts_node__relevant_child_count(child, true);
655 if (grandchild_index < grandchild_count) {
656 const char *field_name = ts_node__field_name_from_language(result, iterator.structural_child_index - 1);
657 if (field_name) inherited_field_name = field_name;
658
659 did_descend = true;
660 result = child;
661 child_index = grandchild_index;
662 break;
663 }
664 index += grandchild_count;
665 }
666 }
667 }
668
669 return NULL;
670}
671
672TSNode ts_node_child_by_field_name(
673 TSNode self,
674 const char *name,
675 uint32_t name_length
676) {
677 TSFieldId field_id = ts_language_field_id_for_name(
678 self.tree->language,
679 name,
680 name_length
681 );
682 return ts_node_child_by_field_id(self, field_id);
683}
684
685uint32_t ts_node_child_count(TSNode self) {
686 Subtree tree = ts_node__subtree(self);
687 if (ts_subtree_child_count(tree) > 0) {
688 return tree.ptr->visible_child_count;
689 } else {
690 return 0;
691 }
692}
693
694uint32_t ts_node_named_child_count(TSNode self) {
695 Subtree tree = ts_node__subtree(self);
696 if (ts_subtree_child_count(tree) > 0) {
697 return tree.ptr->named_child_count;
698 } else {
699 return 0;
700 }
701}
702
703TSNode ts_node_next_sibling(TSNode self) {
704 return ts_node__next_sibling(self, true);
705}
706
707TSNode ts_node_next_named_sibling(TSNode self) {
708 return ts_node__next_sibling(self, false);
709}
710
711TSNode ts_node_prev_sibling(TSNode self) {
712 return ts_node__prev_sibling(self, true);
713}
714
715TSNode ts_node_prev_named_sibling(TSNode self) {
716 return ts_node__prev_sibling(self, false);
717}
718
719TSNode ts_node_first_child_for_byte(TSNode self, uint32_t byte) {
720 return ts_node__first_child_for_byte(self, byte, true);
721}
722
723TSNode ts_node_first_named_child_for_byte(TSNode self, uint32_t byte) {
724 return ts_node__first_child_for_byte(self, byte, false);
725}
726
727TSNode ts_node_descendant_for_byte_range(
728 TSNode self,
729 uint32_t start,
730 uint32_t end
731) {
732 return ts_node__descendant_for_byte_range(self, start, end, true);
733}
734
735TSNode ts_node_named_descendant_for_byte_range(
736 TSNode self,
737 uint32_t start,
738 uint32_t end
739) {
740 return ts_node__descendant_for_byte_range(self, start, end, false);
741}
742
743TSNode ts_node_descendant_for_point_range(
744 TSNode self,
745 TSPoint start,
746 TSPoint end
747) {
748 return ts_node__descendant_for_point_range(self, start, end, true);
749}
750
751TSNode ts_node_named_descendant_for_point_range(
752 TSNode self,
753 TSPoint start,
754 TSPoint end
755) {
756 return ts_node__descendant_for_point_range(self, start, end, false);
757}
758
759void ts_node_edit(TSNode *self, const TSInputEdit *edit) {
760 uint32_t start_byte = ts_node_start_byte(*self);
761 TSPoint start_point = ts_node_start_point(*self);
762
763 if (start_byte >= edit->old_end_byte) {
764 start_byte = edit->new_end_byte + (start_byte - edit->old_end_byte);
765 start_point = point_add(edit->new_end_point, point_sub(start_point, edit->old_end_point));
766 } else if (start_byte > edit->start_byte) {
767 start_byte = edit->new_end_byte;
768 start_point = edit->new_end_point;
769 }
770
771 self->context[0] = start_byte;
772 self->context[1] = start_point.row;
773 self->context[2] = start_point.column;
774}