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