1#include "./alloc.h"
2#include "./language.h"
3#include "./subtree.h"
4#include "./array.h"
5#include "./stack.h"
6#include "./length.h"
7#include <assert.h>
8#include <inttypes.h>
9#include <stdio.h>
10
11#define MAX_LINK_COUNT 8
12#define MAX_NODE_POOL_SIZE 50
13#define MAX_ITERATOR_COUNT 64
14
15#if defined _WIN32 && !defined __GNUC__
16#define forceinline __forceinline
17#else
18#define forceinline static inline __attribute__((always_inline))
19#endif
20
21typedef struct StackNode StackNode;
22
23typedef struct {
24 StackNode *node;
25 Subtree subtree;
26 bool is_pending;
27} StackLink;
28
29struct StackNode {
30 TSStateId state;
31 Length position;
32 StackLink links[MAX_LINK_COUNT];
33 short unsigned int link_count;
34 uint32_t ref_count;
35 unsigned error_cost;
36 unsigned node_count;
37 int dynamic_precedence;
38};
39
40typedef struct {
41 StackNode *node;
42 SubtreeArray subtrees;
43 uint32_t subtree_count;
44 bool is_pending;
45} StackIterator;
46
47typedef Array(StackNode *) StackNodeArray;
48
49typedef enum {
50 StackStatusActive,
51 StackStatusPaused,
52 StackStatusHalted,
53} StackStatus;
54
55typedef struct {
56 StackNode *node;
57 StackSummary *summary;
58 unsigned node_count_at_last_error;
59 Subtree last_external_token;
60 Subtree lookahead_when_paused;
61 StackStatus status;
62} StackHead;
63
64struct Stack {
65 Array(StackHead) heads;
66 StackSliceArray slices;
67 Array(StackIterator) iterators;
68 StackNodeArray node_pool;
69 StackNode *base_node;
70 SubtreePool *subtree_pool;
71};
72
73typedef unsigned StackAction;
74enum {
75 StackActionNone,
76 StackActionStop = 1,
77 StackActionPop = 2,
78};
79
80typedef StackAction (*StackCallback)(void *, const StackIterator *);
81
82static void stack_node_retain(StackNode *self) {
83 if (!self)
84 return;
85 assert(self->ref_count > 0);
86 self->ref_count++;
87 assert(self->ref_count != 0);
88}
89
90static void stack_node_release(
91 StackNode *self,
92 StackNodeArray *pool,
93 SubtreePool *subtree_pool
94) {
95recur:
96 assert(self->ref_count != 0);
97 self->ref_count--;
98 if (self->ref_count > 0) return;
99
100 StackNode *first_predecessor = NULL;
101 if (self->link_count > 0) {
102 for (unsigned i = self->link_count - 1; i > 0; i--) {
103 StackLink link = self->links[i];
104 if (link.subtree.ptr) ts_subtree_release(subtree_pool, link.subtree);
105 stack_node_release(link.node, pool, subtree_pool);
106 }
107 StackLink link = self->links[0];
108 if (link.subtree.ptr) ts_subtree_release(subtree_pool, link.subtree);
109 first_predecessor = self->links[0].node;
110 }
111
112 if (pool->size < MAX_NODE_POOL_SIZE) {
113 array_push(pool, self);
114 } else {
115 ts_free(self);
116 }
117
118 if (first_predecessor) {
119 self = first_predecessor;
120 goto recur;
121 }
122}
123
124/// Get the number of nodes in the subtree, for the purpose of measuring
125/// how much progress has been made by a given version of the stack.
126static uint32_t stack__subtree_node_count(Subtree subtree) {
127 uint32_t count = ts_subtree_visible_descendant_count(subtree);
128 if (ts_subtree_visible(subtree)) count++;
129
130 // Count intermediate error nodes even though they are not visible,
131 // because a stack version's node count is used to check whether it
132 // has made any progress since the last time it encountered an error.
133 if (ts_subtree_symbol(subtree) == ts_builtin_sym_error_repeat) count++;
134
135 return count;
136}
137
138static StackNode *stack_node_new(
139 StackNode *previous_node,
140 Subtree subtree,
141 bool is_pending,
142 TSStateId state,
143 StackNodeArray *pool
144) {
145 StackNode *node = pool->size > 0
146 ? array_pop(pool)
147 : ts_malloc(sizeof(StackNode));
148 *node = (StackNode) {
149 .ref_count = 1,
150 .link_count = 0,
151 .state = state
152 };
153
154 if (previous_node) {
155 node->link_count = 1;
156 node->links[0] = (StackLink) {
157 .node = previous_node,
158 .subtree = subtree,
159 .is_pending = is_pending,
160 };
161
162 node->position = previous_node->position;
163 node->error_cost = previous_node->error_cost;
164 node->dynamic_precedence = previous_node->dynamic_precedence;
165 node->node_count = previous_node->node_count;
166
167 if (subtree.ptr) {
168 node->error_cost += ts_subtree_error_cost(subtree);
169 node->position = length_add(node->position, ts_subtree_total_size(subtree));
170 node->node_count += stack__subtree_node_count(subtree);
171 node->dynamic_precedence += ts_subtree_dynamic_precedence(subtree);
172 }
173 } else {
174 node->position = length_zero();
175 node->error_cost = 0;
176 }
177
178 return node;
179}
180
181static bool stack__subtree_is_equivalent(Subtree left, Subtree right) {
182 if (left.ptr == right.ptr) return true;
183 if (!left.ptr || !right.ptr) return false;
184
185 // Symbols must match
186 if (ts_subtree_symbol(left) != ts_subtree_symbol(right)) return false;
187
188 // If both have errors, don't bother keeping both.
189 if (ts_subtree_error_cost(left) > 0 && ts_subtree_error_cost(right) > 0) return true;
190
191 return (
192 ts_subtree_padding(left).bytes == ts_subtree_padding(right).bytes &&
193 ts_subtree_size(left).bytes == ts_subtree_size(right).bytes &&
194 ts_subtree_child_count(left) == ts_subtree_child_count(right) &&
195 ts_subtree_extra(left) == ts_subtree_extra(right) &&
196 ts_subtree_external_scanner_state_eq(left, right)
197 );
198}
199
200static void stack_node_add_link(
201 StackNode *self,
202 StackLink link,
203 SubtreePool *subtree_pool
204) {
205 if (link.node == self) return;
206
207 for (int i = 0; i < self->link_count; i++) {
208 StackLink *existing_link = &self->links[i];
209 if (stack__subtree_is_equivalent(existing_link->subtree, link.subtree)) {
210 // In general, we preserve ambiguities until they are removed from the stack
211 // during a pop operation where multiple paths lead to the same node. But in
212 // the special case where two links directly connect the same pair of nodes,
213 // we can safely remove the ambiguity ahead of time without changing behavior.
214 if (existing_link->node == link.node) {
215 if (
216 ts_subtree_dynamic_precedence(link.subtree) >
217 ts_subtree_dynamic_precedence(existing_link->subtree)
218 ) {
219 ts_subtree_retain(link.subtree);
220 ts_subtree_release(subtree_pool, existing_link->subtree);
221 existing_link->subtree = link.subtree;
222 self->dynamic_precedence =
223 link.node->dynamic_precedence + ts_subtree_dynamic_precedence(link.subtree);
224 }
225 return;
226 }
227
228 // If the previous nodes are mergeable, merge them recursively.
229 if (
230 existing_link->node->state == link.node->state &&
231 existing_link->node->position.bytes == link.node->position.bytes &&
232 existing_link->node->error_cost == link.node->error_cost
233 ) {
234 for (int j = 0; j < link.node->link_count; j++) {
235 stack_node_add_link(existing_link->node, link.node->links[j], subtree_pool);
236 }
237 int32_t dynamic_precedence = link.node->dynamic_precedence;
238 if (link.subtree.ptr) {
239 dynamic_precedence += ts_subtree_dynamic_precedence(link.subtree);
240 }
241 if (dynamic_precedence > self->dynamic_precedence) {
242 self->dynamic_precedence = dynamic_precedence;
243 }
244 return;
245 }
246 }
247 }
248
249 if (self->link_count == MAX_LINK_COUNT) return;
250
251 stack_node_retain(link.node);
252 unsigned node_count = link.node->node_count;
253 int dynamic_precedence = link.node->dynamic_precedence;
254 self->links[self->link_count++] = link;
255
256 if (link.subtree.ptr) {
257 ts_subtree_retain(link.subtree);
258 node_count += stack__subtree_node_count(link.subtree);
259 dynamic_precedence += ts_subtree_dynamic_precedence(link.subtree);
260 }
261
262 if (node_count > self->node_count) self->node_count = node_count;
263 if (dynamic_precedence > self->dynamic_precedence) self->dynamic_precedence = dynamic_precedence;
264}
265
266static void stack_head_delete(
267 StackHead *self,
268 StackNodeArray *pool,
269 SubtreePool *subtree_pool
270) {
271 if (self->node) {
272 if (self->last_external_token.ptr) {
273 ts_subtree_release(subtree_pool, self->last_external_token);
274 }
275 if (self->lookahead_when_paused.ptr) {
276 ts_subtree_release(subtree_pool, self->lookahead_when_paused);
277 }
278 if (self->summary) {
279 array_delete(self->summary);
280 ts_free(self->summary);
281 }
282 stack_node_release(self->node, pool, subtree_pool);
283 }
284}
285
286static StackVersion ts_stack__add_version(
287 Stack *self,
288 StackVersion original_version,
289 StackNode *node
290) {
291 StackHead head = {
292 .node = node,
293 .node_count_at_last_error = self->heads.contents[original_version].node_count_at_last_error,
294 .last_external_token = self->heads.contents[original_version].last_external_token,
295 .status = StackStatusActive,
296 .lookahead_when_paused = NULL_SUBTREE,
297 };
298 array_push(&self->heads, head);
299 stack_node_retain(node);
300 if (head.last_external_token.ptr) ts_subtree_retain(head.last_external_token);
301 return (StackVersion)(self->heads.size - 1);
302}
303
304static void ts_stack__add_slice(
305 Stack *self,
306 StackVersion original_version,
307 StackNode *node,
308 SubtreeArray *subtrees
309) {
310 for (uint32_t i = self->slices.size - 1; i + 1 > 0; i--) {
311 StackVersion version = self->slices.contents[i].version;
312 if (self->heads.contents[version].node == node) {
313 StackSlice slice = {*subtrees, version};
314 array_insert(&self->slices, i + 1, slice);
315 return;
316 }
317 }
318
319 StackVersion version = ts_stack__add_version(self, original_version, node);
320 StackSlice slice = { *subtrees, version };
321 array_push(&self->slices, slice);
322}
323
324static StackSliceArray stack__iter(
325 Stack *self,
326 StackVersion version,
327 StackCallback callback,
328 void *payload,
329 int goal_subtree_count
330) {
331 array_clear(&self->slices);
332 array_clear(&self->iterators);
333
334 StackHead *head = array_get(&self->heads, version);
335 StackIterator new_iterator = {
336 .node = head->node,
337 .subtrees = array_new(),
338 .subtree_count = 0,
339 .is_pending = true,
340 };
341
342 bool include_subtrees = false;
343 if (goal_subtree_count >= 0) {
344 include_subtrees = true;
345 array_reserve(&new_iterator.subtrees, (uint32_t)ts_subtree_alloc_size(goal_subtree_count) / sizeof(Subtree));
346 }
347
348 array_push(&self->iterators, new_iterator);
349
350 while (self->iterators.size > 0) {
351 for (uint32_t i = 0, size = self->iterators.size; i < size; i++) {
352 StackIterator *iterator = &self->iterators.contents[i];
353 StackNode *node = iterator->node;
354
355 StackAction action = callback(payload, iterator);
356 bool should_pop = action & StackActionPop;
357 bool should_stop = action & StackActionStop || node->link_count == 0;
358
359 if (should_pop) {
360 SubtreeArray subtrees = iterator->subtrees;
361 if (!should_stop) {
362 ts_subtree_array_copy(subtrees, &subtrees);
363 }
364 ts_subtree_array_reverse(&subtrees);
365 ts_stack__add_slice(
366 self,
367 version,
368 node,
369 &subtrees
370 );
371 }
372
373 if (should_stop) {
374 if (!should_pop) {
375 ts_subtree_array_delete(self->subtree_pool, &iterator->subtrees);
376 }
377 array_erase(&self->iterators, i);
378 i--, size--;
379 continue;
380 }
381
382 for (uint32_t j = 1; j <= node->link_count; j++) {
383 StackIterator *next_iterator;
384 StackLink link;
385 if (j == node->link_count) {
386 link = node->links[0];
387 next_iterator = &self->iterators.contents[i];
388 } else {
389 if (self->iterators.size >= MAX_ITERATOR_COUNT) continue;
390 link = node->links[j];
391 StackIterator current_iterator = self->iterators.contents[i];
392 array_push(&self->iterators, current_iterator);
393 next_iterator = array_back(&self->iterators);
394 ts_subtree_array_copy(next_iterator->subtrees, &next_iterator->subtrees);
395 }
396
397 next_iterator->node = link.node;
398 if (link.subtree.ptr) {
399 if (include_subtrees) {
400 array_push(&next_iterator->subtrees, link.subtree);
401 ts_subtree_retain(link.subtree);
402 }
403
404 if (!ts_subtree_extra(link.subtree)) {
405 next_iterator->subtree_count++;
406 if (!link.is_pending) {
407 next_iterator->is_pending = false;
408 }
409 }
410 } else {
411 next_iterator->subtree_count++;
412 next_iterator->is_pending = false;
413 }
414 }
415 }
416 }
417
418 return self->slices;
419}
420
421Stack *ts_stack_new(SubtreePool *subtree_pool) {
422 Stack *self = ts_calloc(1, sizeof(Stack));
423
424 array_init(&self->heads);
425 array_init(&self->slices);
426 array_init(&self->iterators);
427 array_init(&self->node_pool);
428 array_reserve(&self->heads, 4);
429 array_reserve(&self->slices, 4);
430 array_reserve(&self->iterators, 4);
431 array_reserve(&self->node_pool, MAX_NODE_POOL_SIZE);
432
433 self->subtree_pool = subtree_pool;
434 self->base_node = stack_node_new(NULL, NULL_SUBTREE, false, 1, &self->node_pool);
435 ts_stack_clear(self);
436
437 return self;
438}
439
440void ts_stack_delete(Stack *self) {
441 if (self->slices.contents)
442 array_delete(&self->slices);
443 if (self->iterators.contents)
444 array_delete(&self->iterators);
445 stack_node_release(self->base_node, &self->node_pool, self->subtree_pool);
446 for (uint32_t i = 0; i < self->heads.size; i++) {
447 stack_head_delete(&self->heads.contents[i], &self->node_pool, self->subtree_pool);
448 }
449 array_clear(&self->heads);
450 if (self->node_pool.contents) {
451 for (uint32_t i = 0; i < self->node_pool.size; i++)
452 ts_free(self->node_pool.contents[i]);
453 array_delete(&self->node_pool);
454 }
455 array_delete(&self->heads);
456 ts_free(self);
457}
458
459uint32_t ts_stack_version_count(const Stack *self) {
460 return self->heads.size;
461}
462
463TSStateId ts_stack_state(const Stack *self, StackVersion version) {
464 return array_get(&self->heads, version)->node->state;
465}
466
467Length ts_stack_position(const Stack *self, StackVersion version) {
468 return array_get(&self->heads, version)->node->position;
469}
470
471Subtree ts_stack_last_external_token(const Stack *self, StackVersion version) {
472 return array_get(&self->heads, version)->last_external_token;
473}
474
475void ts_stack_set_last_external_token(Stack *self, StackVersion version, Subtree token) {
476 StackHead *head = array_get(&self->heads, version);
477 if (token.ptr) ts_subtree_retain(token);
478 if (head->last_external_token.ptr) ts_subtree_release(self->subtree_pool, head->last_external_token);
479 head->last_external_token = token;
480}
481
482unsigned ts_stack_error_cost(const Stack *self, StackVersion version) {
483 StackHead *head = array_get(&self->heads, version);
484 unsigned result = head->node->error_cost;
485 if (
486 head->status == StackStatusPaused ||
487 (head->node->state == ERROR_STATE && !head->node->links[0].subtree.ptr)) {
488 result += ERROR_COST_PER_RECOVERY;
489 }
490 return result;
491}
492
493unsigned ts_stack_node_count_since_error(const Stack *self, StackVersion version) {
494 StackHead *head = array_get(&self->heads, version);
495 if (head->node->node_count < head->node_count_at_last_error) {
496 head->node_count_at_last_error = head->node->node_count;
497 }
498 return head->node->node_count - head->node_count_at_last_error;
499}
500
501void ts_stack_push(
502 Stack *self,
503 StackVersion version,
504 Subtree subtree,
505 bool pending,
506 TSStateId state
507) {
508 StackHead *head = array_get(&self->heads, version);
509 StackNode *new_node = stack_node_new(head->node, subtree, pending, state, &self->node_pool);
510 if (!subtree.ptr) head->node_count_at_last_error = new_node->node_count;
511 head->node = new_node;
512}
513
514forceinline StackAction pop_count_callback(void *payload, const StackIterator *iterator) {
515 unsigned *goal_subtree_count = payload;
516 if (iterator->subtree_count == *goal_subtree_count) {
517 return StackActionPop | StackActionStop;
518 } else {
519 return StackActionNone;
520 }
521}
522
523StackSliceArray ts_stack_pop_count(Stack *self, StackVersion version, uint32_t count) {
524 return stack__iter(self, version, pop_count_callback, &count, (int)count);
525}
526
527forceinline StackAction pop_pending_callback(void *payload, const StackIterator *iterator) {
528 (void)payload;
529 if (iterator->subtree_count >= 1) {
530 if (iterator->is_pending) {
531 return StackActionPop | StackActionStop;
532 } else {
533 return StackActionStop;
534 }
535 } else {
536 return StackActionNone;
537 }
538}
539
540StackSliceArray ts_stack_pop_pending(Stack *self, StackVersion version) {
541 StackSliceArray pop = stack__iter(self, version, pop_pending_callback, NULL, 0);
542 if (pop.size > 0) {
543 ts_stack_renumber_version(self, pop.contents[0].version, version);
544 pop.contents[0].version = version;
545 }
546 return pop;
547}
548
549forceinline StackAction pop_error_callback(void *payload, const StackIterator *iterator) {
550 if (iterator->subtrees.size > 0) {
551 bool *found_error = payload;
552 if (!*found_error && ts_subtree_is_error(iterator->subtrees.contents[0])) {
553 *found_error = true;
554 return StackActionPop | StackActionStop;
555 } else {
556 return StackActionStop;
557 }
558 } else {
559 return StackActionNone;
560 }
561}
562
563SubtreeArray ts_stack_pop_error(Stack *self, StackVersion version) {
564 StackNode *node = array_get(&self->heads, version)->node;
565 for (unsigned i = 0; i < node->link_count; i++) {
566 if (node->links[i].subtree.ptr && ts_subtree_is_error(node->links[i].subtree)) {
567 bool found_error = false;
568 StackSliceArray pop = stack__iter(self, version, pop_error_callback, &found_error, 1);
569 if (pop.size > 0) {
570 assert(pop.size == 1);
571 ts_stack_renumber_version(self, pop.contents[0].version, version);
572 return pop.contents[0].subtrees;
573 }
574 break;
575 }
576 }
577 return (SubtreeArray) {.size = 0};
578}
579
580forceinline StackAction pop_all_callback(void *payload, const StackIterator *iterator) {
581 (void)payload;
582 return iterator->node->link_count == 0 ? StackActionPop : StackActionNone;
583}
584
585StackSliceArray ts_stack_pop_all(Stack *self, StackVersion version) {
586 return stack__iter(self, version, pop_all_callback, NULL, 0);
587}
588
589typedef struct {
590 StackSummary *summary;
591 unsigned max_depth;
592} SummarizeStackSession;
593
594forceinline StackAction summarize_stack_callback(void *payload, const StackIterator *iterator) {
595 SummarizeStackSession *session = payload;
596 TSStateId state = iterator->node->state;
597 unsigned depth = iterator->subtree_count;
598 if (depth > session->max_depth) return StackActionStop;
599 for (unsigned i = session->summary->size - 1; i + 1 > 0; i--) {
600 StackSummaryEntry entry = session->summary->contents[i];
601 if (entry.depth < depth) break;
602 if (entry.depth == depth && entry.state == state) return StackActionNone;
603 }
604 array_push(session->summary, ((StackSummaryEntry) {
605 .position = iterator->node->position,
606 .depth = depth,
607 .state = state,
608 }));
609 return StackActionNone;
610}
611
612void ts_stack_record_summary(Stack *self, StackVersion version, unsigned max_depth) {
613 SummarizeStackSession session = {
614 .summary = ts_malloc(sizeof(StackSummary)),
615 .max_depth = max_depth
616 };
617 array_init(session.summary);
618 stack__iter(self, version, summarize_stack_callback, &session, -1);
619 StackHead *head = &self->heads.contents[version];
620 if (head->summary) {
621 array_delete(head->summary);
622 ts_free(head->summary);
623 }
624 head->summary = session.summary;
625}
626
627StackSummary *ts_stack_get_summary(Stack *self, StackVersion version) {
628 return array_get(&self->heads, version)->summary;
629}
630
631int ts_stack_dynamic_precedence(Stack *self, StackVersion version) {
632 return array_get(&self->heads, version)->node->dynamic_precedence;
633}
634
635bool ts_stack_has_advanced_since_error(const Stack *self, StackVersion version) {
636 const StackHead *head = array_get(&self->heads, version);
637 const StackNode *node = head->node;
638 if (node->error_cost == 0) return true;
639 while (node) {
640 if (node->link_count > 0) {
641 Subtree subtree = node->links[0].subtree;
642 if (subtree.ptr) {
643 if (ts_subtree_total_bytes(subtree) > 0) {
644 return true;
645 } else if (
646 node->node_count > head->node_count_at_last_error &&
647 ts_subtree_error_cost(subtree) == 0
648 ) {
649 node = node->links[0].node;
650 continue;
651 }
652 }
653 }
654 break;
655 }
656 return false;
657}
658
659void ts_stack_remove_version(Stack *self, StackVersion version) {
660 stack_head_delete(array_get(&self->heads, version), &self->node_pool, self->subtree_pool);
661 array_erase(&self->heads, version);
662}
663
664void ts_stack_renumber_version(Stack *self, StackVersion v1, StackVersion v2) {
665 if (v1 == v2) return;
666 assert(v2 < v1);
667 assert((uint32_t)v1 < self->heads.size);
668 StackHead *source_head = &self->heads.contents[v1];
669 StackHead *target_head = &self->heads.contents[v2];
670 if (target_head->summary && !source_head->summary) {
671 source_head->summary = target_head->summary;
672 target_head->summary = NULL;
673 }
674 stack_head_delete(target_head, &self->node_pool, self->subtree_pool);
675 *target_head = *source_head;
676 array_erase(&self->heads, v1);
677}
678
679void ts_stack_swap_versions(Stack *self, StackVersion v1, StackVersion v2) {
680 StackHead temporary_head = self->heads.contents[v1];
681 self->heads.contents[v1] = self->heads.contents[v2];
682 self->heads.contents[v2] = temporary_head;
683}
684
685StackVersion ts_stack_copy_version(Stack *self, StackVersion version) {
686 assert(version < self->heads.size);
687 array_push(&self->heads, self->heads.contents[version]);
688 StackHead *head = array_back(&self->heads);
689 stack_node_retain(head->node);
690 if (head->last_external_token.ptr) ts_subtree_retain(head->last_external_token);
691 head->summary = NULL;
692 return self->heads.size - 1;
693}
694
695bool ts_stack_merge(Stack *self, StackVersion version1, StackVersion version2) {
696 if (!ts_stack_can_merge(self, version1, version2)) return false;
697 StackHead *head1 = &self->heads.contents[version1];
698 StackHead *head2 = &self->heads.contents[version2];
699 for (uint32_t i = 0; i < head2->node->link_count; i++) {
700 stack_node_add_link(head1->node, head2->node->links[i], self->subtree_pool);
701 }
702 if (head1->node->state == ERROR_STATE) {
703 head1->node_count_at_last_error = head1->node->node_count;
704 }
705 ts_stack_remove_version(self, version2);
706 return true;
707}
708
709bool ts_stack_can_merge(Stack *self, StackVersion version1, StackVersion version2) {
710 StackHead *head1 = &self->heads.contents[version1];
711 StackHead *head2 = &self->heads.contents[version2];
712 return
713 head1->status == StackStatusActive &&
714 head2->status == StackStatusActive &&
715 head1->node->state == head2->node->state &&
716 head1->node->position.bytes == head2->node->position.bytes &&
717 head1->node->error_cost == head2->node->error_cost &&
718 ts_subtree_external_scanner_state_eq(head1->last_external_token, head2->last_external_token);
719}
720
721void ts_stack_halt(Stack *self, StackVersion version) {
722 array_get(&self->heads, version)->status = StackStatusHalted;
723}
724
725void ts_stack_pause(Stack *self, StackVersion version, Subtree lookahead) {
726 StackHead *head = array_get(&self->heads, version);
727 head->status = StackStatusPaused;
728 head->lookahead_when_paused = lookahead;
729 head->node_count_at_last_error = head->node->node_count;
730}
731
732bool ts_stack_is_active(const Stack *self, StackVersion version) {
733 return array_get(&self->heads, version)->status == StackStatusActive;
734}
735
736bool ts_stack_is_halted(const Stack *self, StackVersion version) {
737 return array_get(&self->heads, version)->status == StackStatusHalted;
738}
739
740bool ts_stack_is_paused(const Stack *self, StackVersion version) {
741 return array_get(&self->heads, version)->status == StackStatusPaused;
742}
743
744Subtree ts_stack_resume(Stack *self, StackVersion version) {
745 StackHead *head = array_get(&self->heads, version);
746 assert(head->status == StackStatusPaused);
747 Subtree result = head->lookahead_when_paused;
748 head->status = StackStatusActive;
749 head->lookahead_when_paused = NULL_SUBTREE;
750 return result;
751}
752
753void ts_stack_clear(Stack *self) {
754 stack_node_retain(self->base_node);
755 for (uint32_t i = 0; i < self->heads.size; i++) {
756 stack_head_delete(&self->heads.contents[i], &self->node_pool, self->subtree_pool);
757 }
758 array_clear(&self->heads);
759 array_push(&self->heads, ((StackHead) {
760 .node = self->base_node,
761 .status = StackStatusActive,
762 .last_external_token = NULL_SUBTREE,
763 .lookahead_when_paused = NULL_SUBTREE,
764 }));
765}
766
767bool ts_stack_print_dot_graph(Stack *self, const TSLanguage *language, FILE *f) {
768 array_reserve(&self->iterators, 32);
769 if (!f) f = stderr;
770
771 fprintf(f, "digraph stack {\n");
772 fprintf(f, "rankdir=\"RL\";\n");
773 fprintf(f, "edge [arrowhead=none]\n");
774
775 Array(StackNode *) visited_nodes = array_new();
776
777 array_clear(&self->iterators);
778 for (uint32_t i = 0; i < self->heads.size; i++) {
779 StackHead *head = &self->heads.contents[i];
780 if (head->status == StackStatusHalted) continue;
781
782 fprintf(f, "node_head_%u [shape=none, label=\"\"]\n", i);
783 fprintf(f, "node_head_%u -> node_%p [", i, (void *)head->node);
784
785 if (head->status == StackStatusPaused) {
786 fprintf(f, "color=red ");
787 }
788 fprintf(f,
789 "label=%u, fontcolor=blue, weight=10000, labeltooltip=\"node_count: %u\nerror_cost: %u",
790 i,
791 ts_stack_node_count_since_error(self, i),
792 ts_stack_error_cost(self, i)
793 );
794
795 if (head->summary) {
796 fprintf(f, "\nsummary:");
797 for (uint32_t j = 0; j < head->summary->size; j++) fprintf(f, " %u", head->summary->contents[j].state);
798 }
799
800 if (head->last_external_token.ptr) {
801 const ExternalScannerState *state = &head->last_external_token.ptr->external_scanner_state;
802 const char *data = ts_external_scanner_state_data(state);
803 fprintf(f, "\nexternal_scanner_state:");
804 for (uint32_t j = 0; j < state->length; j++) fprintf(f, " %2X", data[j]);
805 }
806
807 fprintf(f, "\"]\n");
808 array_push(&self->iterators, ((StackIterator) {
809 .node = head->node
810 }));
811 }
812
813 bool all_iterators_done = false;
814 while (!all_iterators_done) {
815 all_iterators_done = true;
816
817 for (uint32_t i = 0; i < self->iterators.size; i++) {
818 StackIterator iterator = self->iterators.contents[i];
819 StackNode *node = iterator.node;
820
821 for (uint32_t j = 0; j < visited_nodes.size; j++) {
822 if (visited_nodes.contents[j] == node) {
823 node = NULL;
824 break;
825 }
826 }
827
828 if (!node) continue;
829 all_iterators_done = false;
830
831 fprintf(f, "node_%p [", (void *)node);
832 if (node->state == ERROR_STATE) {
833 fprintf(f, "label=\"?\"");
834 } else if (
835 node->link_count == 1 &&
836 node->links[0].subtree.ptr &&
837 ts_subtree_extra(node->links[0].subtree)
838 ) {
839 fprintf(f, "shape=point margin=0 label=\"\"");
840 } else {
841 fprintf(f, "label=\"%d\"", node->state);
842 }
843
844 fprintf(
845 f,
846 " tooltip=\"position: %u,%u\nnode_count:%u\nerror_cost: %u\ndynamic_precedence: %d\"];\n",
847 node->position.extent.row + 1,
848 node->position.extent.column,
849 node->node_count,
850 node->error_cost,
851 node->dynamic_precedence
852 );
853
854 for (int j = 0; j < node->link_count; j++) {
855 StackLink link = node->links[j];
856 fprintf(f, "node_%p -> node_%p [", (void *)node, (void *)link.node);
857 if (link.is_pending) fprintf(f, "style=dashed ");
858 if (link.subtree.ptr && ts_subtree_extra(link.subtree)) fprintf(f, "fontcolor=gray ");
859
860 if (!link.subtree.ptr) {
861 fprintf(f, "color=red");
862 } else {
863 fprintf(f, "label=\"");
864 bool quoted = ts_subtree_visible(link.subtree) && !ts_subtree_named(link.subtree);
865 if (quoted) fprintf(f, "'");
866 ts_language_write_symbol_as_dot_string(language, f, ts_subtree_symbol(link.subtree));
867 if (quoted) fprintf(f, "'");
868 fprintf(f, "\"");
869 fprintf(
870 f,
871 "labeltooltip=\"error_cost: %u\ndynamic_precedence: %" PRId32 "\"",
872 ts_subtree_error_cost(link.subtree),
873 ts_subtree_dynamic_precedence(link.subtree)
874 );
875 }
876
877 fprintf(f, "];\n");
878
879 StackIterator *next_iterator;
880 if (j == 0) {
881 next_iterator = &self->iterators.contents[i];
882 } else {
883 array_push(&self->iterators, iterator);
884 next_iterator = array_back(&self->iterators);
885 }
886 next_iterator->node = link.node;
887 }
888
889 array_push(&visited_nodes, node);
890 }
891 }
892
893 fprintf(f, "}\n");
894
895 array_delete(&visited_nodes);
896 return true;
897}
898
899#undef forceinline