1 #include <stdbool.h>
2 #include "./subtree.h"
3 #include "./tree.h"
4 #include "./language.h"
5
6 typedef 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
ts_node_new(const TSTree * tree,const Subtree * subtree,Length position,TSSymbol alias)17 TSNode 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
ts_node__null(void)30 static inline TSNode ts_node__null(void) {
31 return ts_node_new(NULL, NULL, length_zero(), 0);
32 }
33
34 // TSNode - accessors
35
ts_node_start_byte(TSNode self)36 uint32_t ts_node_start_byte(TSNode self) {
37 return self.context[0];
38 }
39
ts_node_start_point(TSNode self)40 TSPoint ts_node_start_point(TSNode self) {
41 return (TSPoint) {self.context[1], self.context[2]};
42 }
43
ts_node__alias(const TSNode * self)44 static inline uint32_t ts_node__alias(const TSNode *self) {
45 return self->context[3];
46 }
47
ts_node__subtree(TSNode self)48 static inline Subtree ts_node__subtree(TSNode self) {
49 return *(const Subtree *)self.id;
50 }
51
52 // NodeChildIterator
53
ts_node_iterate_children(const TSNode * node)54 static 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
ts_node_child_iterator_done(NodeChildIterator * self)73 static inline bool ts_node_child_iterator_done(NodeChildIterator *self) {
74 return self->child_index == self->parent.ptr->child_count;
75 }
76
ts_node_child_iterator_next(NodeChildIterator * self,TSNode * result)77 static 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
ts_node__is_relevant(TSNode self,bool include_anonymous)106 static 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
ts_node__relevant_child_count(TSNode self,bool include_anonymous)120 static 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
ts_node__child(TSNode self,uint32_t child_index,bool include_anonymous)136 static 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 if (ts_node__is_relevant(self, true)) {
154 ts_tree_set_cached_parent(self.tree, &child, &self);
155 }
156 return child;
157 }
158 index++;
159 } else {
160 uint32_t grandchild_index = child_index - index;
161 uint32_t grandchild_count = ts_node__relevant_child_count(child, include_anonymous);
162 if (grandchild_index < grandchild_count) {
163 did_descend = true;
164 result = child;
165 child_index = grandchild_index;
166 break;
167 }
168 index += grandchild_count;
169 }
170 }
171 }
172
173 return ts_node__null();
174 }
175
ts_subtree_has_trailing_empty_descendant(Subtree self,Subtree other)176 static bool ts_subtree_has_trailing_empty_descendant(
177 Subtree self,
178 Subtree other
179 ) {
180 for (unsigned i = ts_subtree_child_count(self) - 1; i + 1 > 0; i--) {
181 Subtree child = ts_subtree_children(self)[i];
182 if (ts_subtree_total_bytes(child) > 0) break;
183 if (child.ptr == other.ptr || ts_subtree_has_trailing_empty_descendant(child, other)) {
184 return true;
185 }
186 }
187 return false;
188 }
189
ts_node__prev_sibling(TSNode self,bool include_anonymous)190 static inline TSNode ts_node__prev_sibling(TSNode self, bool include_anonymous) {
191 Subtree self_subtree = ts_node__subtree(self);
192 bool self_is_empty = ts_subtree_total_bytes(self_subtree) == 0;
193 uint32_t target_end_byte = ts_node_end_byte(self);
194
195 TSNode node = ts_node_parent(self);
196 TSNode earlier_node = ts_node__null();
197 bool earlier_node_is_relevant = false;
198
199 while (!ts_node_is_null(node)) {
200 TSNode earlier_child = ts_node__null();
201 bool earlier_child_is_relevant = false;
202 bool found_child_containing_target = false;
203
204 TSNode child;
205 NodeChildIterator iterator = ts_node_iterate_children(&node);
206 while (ts_node_child_iterator_next(&iterator, &child)) {
207 if (child.id == self.id) break;
208 if (iterator.position.bytes > target_end_byte) {
209 found_child_containing_target = true;
210 break;
211 }
212
213 if (iterator.position.bytes == target_end_byte &&
214 (!self_is_empty ||
215 ts_subtree_has_trailing_empty_descendant(ts_node__subtree(child), self_subtree))) {
216 found_child_containing_target = true;
217 break;
218 }
219
220 if (ts_node__is_relevant(child, include_anonymous)) {
221 earlier_child = child;
222 earlier_child_is_relevant = true;
223 } else if (ts_node__relevant_child_count(child, include_anonymous) > 0) {
224 earlier_child = child;
225 earlier_child_is_relevant = false;
226 }
227 }
228
229 if (found_child_containing_target) {
230 if (!ts_node_is_null(earlier_child)) {
231 earlier_node = earlier_child;
232 earlier_node_is_relevant = earlier_child_is_relevant;
233 }
234 node = child;
235 } else if (earlier_child_is_relevant) {
236 return earlier_child;
237 } else if (!ts_node_is_null(earlier_child)) {
238 node = earlier_child;
239 } else if (earlier_node_is_relevant) {
240 return earlier_node;
241 } else {
242 node = earlier_node;
243 }
244 }
245
246 return ts_node__null();
247 }
248
ts_node__next_sibling(TSNode self,bool include_anonymous)249 static inline TSNode ts_node__next_sibling(TSNode self, bool include_anonymous) {
250 uint32_t target_end_byte = ts_node_end_byte(self);
251
252 TSNode node = ts_node_parent(self);
253 TSNode later_node = ts_node__null();
254 bool later_node_is_relevant = false;
255
256 while (!ts_node_is_null(node)) {
257 TSNode later_child = ts_node__null();
258 bool later_child_is_relevant = false;
259 TSNode child_containing_target = ts_node__null();
260
261 TSNode child;
262 NodeChildIterator iterator = ts_node_iterate_children(&node);
263 while (ts_node_child_iterator_next(&iterator, &child)) {
264 if (iterator.position.bytes < target_end_byte) continue;
265 if (ts_node_start_byte(child) <= ts_node_start_byte(self)) {
266 if (ts_node__subtree(child).ptr != ts_node__subtree(self).ptr) {
267 child_containing_target = child;
268 }
269 } else if (ts_node__is_relevant(child, include_anonymous)) {
270 later_child = child;
271 later_child_is_relevant = true;
272 break;
273 } else if (ts_node__relevant_child_count(child, include_anonymous) > 0) {
274 later_child = child;
275 later_child_is_relevant = false;
276 break;
277 }
278 }
279
280 if (!ts_node_is_null(child_containing_target)) {
281 if (!ts_node_is_null(later_child)) {
282 later_node = later_child;
283 later_node_is_relevant = later_child_is_relevant;
284 }
285 node = child_containing_target;
286 } else if (later_child_is_relevant) {
287 return later_child;
288 } else if (!ts_node_is_null(later_child)) {
289 node = later_child;
290 } else if (later_node_is_relevant) {
291 return later_node;
292 } else {
293 node = later_node;
294 }
295 }
296
297 return ts_node__null();
298 }
299
ts_node__first_child_for_byte(TSNode self,uint32_t goal,bool include_anonymous)300 static inline TSNode ts_node__first_child_for_byte(
301 TSNode self,
302 uint32_t goal,
303 bool include_anonymous
304 ) {
305 TSNode node = self;
306 bool did_descend = true;
307
308 while (did_descend) {
309 did_descend = false;
310
311 TSNode child;
312 NodeChildIterator iterator = ts_node_iterate_children(&node);
313 while (ts_node_child_iterator_next(&iterator, &child)) {
314 if (ts_node_end_byte(child) > goal) {
315 if (ts_node__is_relevant(child, include_anonymous)) {
316 return child;
317 } else if (ts_node_child_count(child) > 0) {
318 did_descend = true;
319 node = child;
320 break;
321 }
322 }
323 }
324 }
325
326 return ts_node__null();
327 }
328
ts_node__descendant_for_byte_range(TSNode self,uint32_t range_start,uint32_t range_end,bool include_anonymous)329 static inline TSNode ts_node__descendant_for_byte_range(
330 TSNode self,
331 uint32_t range_start,
332 uint32_t range_end,
333 bool include_anonymous
334 ) {
335 TSNode node = self;
336 TSNode last_visible_node = self;
337
338 bool did_descend = true;
339 while (did_descend) {
340 did_descend = false;
341
342 TSNode child;
343 NodeChildIterator iterator = ts_node_iterate_children(&node);
344 while (ts_node_child_iterator_next(&iterator, &child)) {
345 uint32_t node_end = iterator.position.bytes;
346
347 // The end of this node must extend far enough forward to touch
348 // the end of the range and exceed the start of the range.
349 if (node_end < range_end) continue;
350 if (node_end <= range_start) continue;
351
352 // The start of this node must extend far enough backward to
353 // touch the start of the range.
354 if (range_start < ts_node_start_byte(child)) break;
355
356 node = child;
357 if (ts_node__is_relevant(node, include_anonymous)) {
358 ts_tree_set_cached_parent(self.tree, &child, &last_visible_node);
359 last_visible_node = node;
360 }
361 did_descend = true;
362 break;
363 }
364 }
365
366 return last_visible_node;
367 }
368
ts_node__descendant_for_point_range(TSNode self,TSPoint range_start,TSPoint range_end,bool include_anonymous)369 static inline TSNode ts_node__descendant_for_point_range(
370 TSNode self,
371 TSPoint range_start,
372 TSPoint range_end,
373 bool include_anonymous
374 ) {
375 TSNode node = self;
376 TSNode last_visible_node = self;
377
378 bool did_descend = true;
379 while (did_descend) {
380 did_descend = false;
381
382 TSNode child;
383 NodeChildIterator iterator = ts_node_iterate_children(&node);
384 while (ts_node_child_iterator_next(&iterator, &child)) {
385 TSPoint node_end = iterator.position.extent;
386
387 // The end of this node must extend far enough forward to touch
388 // the end of the range and exceed the start of the range.
389 if (point_lt(node_end, range_end)) continue;
390 if (point_lte(node_end, range_start)) continue;
391
392 // The start of this node must extend far enough backward to
393 // touch the start of the range.
394 if (point_lt(range_start, ts_node_start_point(child))) break;
395
396 node = child;
397 if (ts_node__is_relevant(node, include_anonymous)) {
398 ts_tree_set_cached_parent(self.tree, &child, &last_visible_node);
399 last_visible_node = node;
400 }
401 did_descend = true;
402 break;
403 }
404 }
405
406 return last_visible_node;
407 }
408
409 // TSNode - public
410
ts_node_end_byte(TSNode self)411 uint32_t ts_node_end_byte(TSNode self) {
412 return ts_node_start_byte(self) + ts_subtree_size(ts_node__subtree(self)).bytes;
413 }
414
ts_node_end_point(TSNode self)415 TSPoint ts_node_end_point(TSNode self) {
416 return point_add(ts_node_start_point(self), ts_subtree_size(ts_node__subtree(self)).extent);
417 }
418
ts_node_symbol(TSNode self)419 TSSymbol ts_node_symbol(TSNode self) {
420 TSSymbol symbol = ts_node__alias(&self);
421 if (!symbol) symbol = ts_subtree_symbol(ts_node__subtree(self));
422 return ts_language_public_symbol(self.tree->language, symbol);
423 }
424
ts_node_type(TSNode self)425 const char *ts_node_type(TSNode self) {
426 TSSymbol symbol = ts_node__alias(&self);
427 if (!symbol) symbol = ts_subtree_symbol(ts_node__subtree(self));
428 return ts_language_symbol_name(self.tree->language, symbol);
429 }
430
ts_node_string(TSNode self)431 char *ts_node_string(TSNode self) {
432 return ts_subtree_string(ts_node__subtree(self), self.tree->language, false);
433 }
434
ts_node_eq(TSNode self,TSNode other)435 bool ts_node_eq(TSNode self, TSNode other) {
436 return self.tree == other.tree && self.id == other.id;
437 }
438
ts_node_is_null(TSNode self)439 bool ts_node_is_null(TSNode self) {
440 return self.id == 0;
441 }
442
ts_node_is_extra(TSNode self)443 bool ts_node_is_extra(TSNode self) {
444 return ts_subtree_extra(ts_node__subtree(self));
445 }
446
ts_node_is_named(TSNode self)447 bool ts_node_is_named(TSNode self) {
448 TSSymbol alias = ts_node__alias(&self);
449 return alias
450 ? ts_language_symbol_metadata(self.tree->language, alias).named
451 : ts_subtree_named(ts_node__subtree(self));
452 }
453
ts_node_is_missing(TSNode self)454 bool ts_node_is_missing(TSNode self) {
455 return ts_subtree_missing(ts_node__subtree(self));
456 }
457
ts_node_has_changes(TSNode self)458 bool ts_node_has_changes(TSNode self) {
459 return ts_subtree_has_changes(ts_node__subtree(self));
460 }
461
ts_node_has_error(TSNode self)462 bool ts_node_has_error(TSNode self) {
463 return ts_subtree_error_cost(ts_node__subtree(self)) > 0;
464 }
465
ts_node_parent(TSNode self)466 TSNode ts_node_parent(TSNode self) {
467 TSNode node = ts_tree_get_cached_parent(self.tree, &self);
468 if (node.id) return node;
469
470 node = ts_tree_root_node(self.tree);
471 uint32_t end_byte = ts_node_end_byte(self);
472 if (node.id == self.id) return ts_node__null();
473
474 TSNode last_visible_node = node;
475 bool did_descend = true;
476 while (did_descend) {
477 did_descend = false;
478
479 TSNode child;
480 NodeChildIterator iterator = ts_node_iterate_children(&node);
481 while (ts_node_child_iterator_next(&iterator, &child)) {
482 if (
483 ts_node_start_byte(child) > ts_node_start_byte(self) ||
484 child.id == self.id
485 ) break;
486 if (iterator.position.bytes >= end_byte) {
487 node = child;
488 if (ts_node__is_relevant(child, true)) {
489 ts_tree_set_cached_parent(self.tree, &node, &last_visible_node);
490 last_visible_node = node;
491 }
492 did_descend = true;
493 break;
494 }
495 }
496 }
497
498 return last_visible_node;
499 }
500
ts_node_child(TSNode self,uint32_t child_index)501 TSNode ts_node_child(TSNode self, uint32_t child_index) {
502 return ts_node__child(self, child_index, true);
503 }
504
ts_node_named_child(TSNode self,uint32_t child_index)505 TSNode ts_node_named_child(TSNode self, uint32_t child_index) {
506 return ts_node__child(self, child_index, false);
507 }
508
ts_node_child_by_field_id(TSNode self,TSFieldId field_id)509 TSNode ts_node_child_by_field_id(TSNode self, TSFieldId field_id) {
510 recur:
511 if (!field_id || ts_node_child_count(self) == 0) return ts_node__null();
512
513 const TSFieldMapEntry *field_map, *field_map_end;
514 ts_language_field_map(
515 self.tree->language,
516 ts_node__subtree(self).ptr->production_id,
517 &field_map,
518 &field_map_end
519 );
520 if (field_map == field_map_end) return ts_node__null();
521
522 // The field mappings are sorted by their field id. Scan all
523 // the mappings to find the ones for the given field id.
524 while (field_map->field_id < field_id) {
525 field_map++;
526 if (field_map == field_map_end) return ts_node__null();
527 }
528 while (field_map_end[-1].field_id > field_id) {
529 field_map_end--;
530 if (field_map == field_map_end) return ts_node__null();
531 }
532
533 TSNode child;
534 NodeChildIterator iterator = ts_node_iterate_children(&self);
535 while (ts_node_child_iterator_next(&iterator, &child)) {
536 if (!ts_subtree_extra(ts_node__subtree(child))) {
537 uint32_t index = iterator.structural_child_index - 1;
538 if (index < field_map->child_index) continue;
539
540 // Hidden nodes' fields are "inherited" by their visible parent.
541 if (field_map->inherited) {
542
543 // If this is the *last* possible child node for this field,
544 // then perform a tail call to avoid recursion.
545 if (field_map + 1 == field_map_end) {
546 self = child;
547 goto recur;
548 }
549
550 // Otherwise, descend into this child, but if it doesn't contain
551 // the field, continue searching subsequent children.
552 else {
553 TSNode result = ts_node_child_by_field_id(child, field_id);
554 if (result.id) return result;
555 field_map++;
556 if (field_map == field_map_end) return ts_node__null();
557 }
558 }
559
560 else if (ts_node__is_relevant(child, true)) {
561 return child;
562 }
563
564 // If the field refers to a hidden node, return its first visible
565 // child.
566 else {
567 return ts_node_child(child, 0);
568 }
569 }
570 }
571
572 return ts_node__null();
573 }
574
ts_node_child_by_field_name(TSNode self,const char * name,uint32_t name_length)575 TSNode ts_node_child_by_field_name(
576 TSNode self,
577 const char *name,
578 uint32_t name_length
579 ) {
580 TSFieldId field_id = ts_language_field_id_for_name(
581 self.tree->language,
582 name,
583 name_length
584 );
585 return ts_node_child_by_field_id(self, field_id);
586 }
587
ts_node_child_count(TSNode self)588 uint32_t ts_node_child_count(TSNode self) {
589 Subtree tree = ts_node__subtree(self);
590 if (ts_subtree_child_count(tree) > 0) {
591 return tree.ptr->visible_child_count;
592 } else {
593 return 0;
594 }
595 }
596
ts_node_named_child_count(TSNode self)597 uint32_t ts_node_named_child_count(TSNode self) {
598 Subtree tree = ts_node__subtree(self);
599 if (ts_subtree_child_count(tree) > 0) {
600 return tree.ptr->named_child_count;
601 } else {
602 return 0;
603 }
604 }
605
ts_node_next_sibling(TSNode self)606 TSNode ts_node_next_sibling(TSNode self) {
607 return ts_node__next_sibling(self, true);
608 }
609
ts_node_next_named_sibling(TSNode self)610 TSNode ts_node_next_named_sibling(TSNode self) {
611 return ts_node__next_sibling(self, false);
612 }
613
ts_node_prev_sibling(TSNode self)614 TSNode ts_node_prev_sibling(TSNode self) {
615 return ts_node__prev_sibling(self, true);
616 }
617
ts_node_prev_named_sibling(TSNode self)618 TSNode ts_node_prev_named_sibling(TSNode self) {
619 return ts_node__prev_sibling(self, false);
620 }
621
ts_node_first_child_for_byte(TSNode self,uint32_t byte)622 TSNode ts_node_first_child_for_byte(TSNode self, uint32_t byte) {
623 return ts_node__first_child_for_byte(self, byte, true);
624 }
625
ts_node_first_named_child_for_byte(TSNode self,uint32_t byte)626 TSNode ts_node_first_named_child_for_byte(TSNode self, uint32_t byte) {
627 return ts_node__first_child_for_byte(self, byte, false);
628 }
629
ts_node_descendant_for_byte_range(TSNode self,uint32_t start,uint32_t end)630 TSNode ts_node_descendant_for_byte_range(
631 TSNode self,
632 uint32_t start,
633 uint32_t end
634 ) {
635 return ts_node__descendant_for_byte_range(self, start, end, true);
636 }
637
ts_node_named_descendant_for_byte_range(TSNode self,uint32_t start,uint32_t end)638 TSNode ts_node_named_descendant_for_byte_range(
639 TSNode self,
640 uint32_t start,
641 uint32_t end
642 ) {
643 return ts_node__descendant_for_byte_range(self, start, end, false);
644 }
645
ts_node_descendant_for_point_range(TSNode self,TSPoint start,TSPoint end)646 TSNode ts_node_descendant_for_point_range(
647 TSNode self,
648 TSPoint start,
649 TSPoint end
650 ) {
651 return ts_node__descendant_for_point_range(self, start, end, true);
652 }
653
ts_node_named_descendant_for_point_range(TSNode self,TSPoint start,TSPoint end)654 TSNode ts_node_named_descendant_for_point_range(
655 TSNode self,
656 TSPoint start,
657 TSPoint end
658 ) {
659 return ts_node__descendant_for_point_range(self, start, end, false);
660 }
661
ts_node_edit(TSNode * self,const TSInputEdit * edit)662 void ts_node_edit(TSNode *self, const TSInputEdit *edit) {
663 uint32_t start_byte = ts_node_start_byte(*self);
664 TSPoint start_point = ts_node_start_point(*self);
665
666 if (start_byte >= edit->old_end_byte) {
667 start_byte = edit->new_end_byte + (start_byte - edit->old_end_byte);
668 start_point = point_add(edit->new_end_point, point_sub(start_point, edit->old_end_point));
669 } else if (start_byte > edit->start_byte) {
670 start_byte = edit->new_end_byte;
671 start_point = edit->new_end_point;
672 }
673
674 self->context[0] = start_byte;
675 self->context[1] = start_point.row;
676 self->context[2] = start_point.column;
677 }
678