extract_node_stack.h

/*
 * extract_node_stack.h — Growable TSNode stack for AST traversal.
 *
 * Replaces fixed-size TSNode stack[] arrays that silently drop AST subtrees
 * when the stack overflows (GitHub issue #199).
 *
 * The common capacity lives inline in the traversal's own stack frame. Only an
 * unusually broad AST spills into the result arena. Call-site capacities
 * historically mirrored fixed stack limits (usually 512, sometimes 4096), so
 * allocating every traversal there made temporary work survive with durable
 * extraction results across the whole repository. Inline storage preserves the
 * same traversal order and geometric growth without that lifetime inversion.
 */
#ifndef CBM_EXTRACT_NODE_STACK_H
#define CBM_EXTRACT_NODE_STACK_H

#include "arena.h"
#include "tree_sitter/api.h"
#include <string.h> /* memcpy */

typedef struct {
    TSNode *items;
    int count;
    int cap;
    TSNode inline_items[128];
} TSNodeStack;

enum { TS_NSTACK_INLINE_CAP = 128 };

/* Initialize with inline storage; arena is used only if the stack spills. */
static inline void ts_nstack_init(TSNodeStack *s, CBMArena *arena, int initial_cap) {
    (void)arena;
    (void)initial_cap;
    s->items = s->inline_items;
    s->count = 0;
    s->cap = TS_NSTACK_INLINE_CAP;
}

/* Push a node onto the stack, growing 2x if needed. */
static inline void ts_nstack_push(TSNodeStack *s, CBMArena *arena, TSNode node) {
    if (s->count >= s->cap) {
        int new_cap = s->cap ? s->cap * 2 : TS_NSTACK_INLINE_CAP;
        TSNode *new_items = (TSNode *)cbm_arena_alloc(arena, (size_t)new_cap * sizeof(TSNode));
        if (!new_items)
            return; /* OOM: best-effort, stop growing */
        if (s->items && s->count > 0) {
            memcpy(new_items, s->items, (size_t)s->count * sizeof(TSNode));
        }
        /* Old s->items is abandoned in the arena — freed on arena_destroy. */
        s->items = new_items;
        s->cap = new_cap;
    }
    s->items[s->count++] = node;
}

/* Pop a node from the stack. Caller must check s->count > 0. */
static inline TSNode ts_nstack_pop(TSNodeStack *s) {
    return s->items[--s->count];
}

/*
 * Push all children of `node` so they POP in forward (source) order — a drop-in
 * replacement for the common idiom:
 *     for (int i = (int)count - 1; i >= 0; i--) ts_nstack_push(s, a, ts_node_child(node, i));
 *
 * That idiom calls ts_node_child(node, i) once per index, and ts_node_child is
 * O(i) in tree-sitter (it walks the child iterator from the first child each
 * time). Over a node with N children that is O(N^2) — catastrophic on a program
 * root holding hundreds of thousands of top-level nodes (e.g. fixture/generated
 * files). This helper enumerates children in a single O(N) cursor pass, then
 * reverses the just-pushed segment so pop order is identical to the old idiom.
 */
static inline void ts_nstack_push_children(TSNodeStack *s, CBMArena *arena, TSNode node) {
    int base = s->count;
    TSTreeCursor cursor = ts_tree_cursor_new(node);
    if (ts_tree_cursor_goto_first_child(&cursor)) {
        do {
            ts_nstack_push(s, arena, ts_tree_cursor_current_node(&cursor));
        } while (ts_tree_cursor_goto_next_sibling(&cursor));
    }
    ts_tree_cursor_delete(&cursor);
    /* Reverse [base, count) so the first child pops first (forward order). */
    int lo = base, hi = s->count - 1;
    while (lo < hi) {
        TSNode tmp = s->items[lo];
        s->items[lo] = s->items[hi];
        s->items[hi] = tmp;
        lo++;
        hi--;
    }
}

#endif /* CBM_EXTRACT_NODE_STACK_H */