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