<commit_before>//
// chpeg: parser.c {
//

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#ifndef CHPEG_AMALGAMATION
#include "chpeg/mem.h"
#include "chpeg/util.h"
#include "chpeg/parser.h"
#endif

#ifndef CHPEG_MAX_TREE_DEPTH
#define CHPEG_MAX_TREE_DEPTH 256
#endif

#ifndef CHPEG_STACK_SIZE
#define CHPEG_STACK_SIZE 1024
#endif

#ifndef SANITY_CHECKS
#define SANITY_CHECKS 1
#endif

#ifndef DEBUG_ERRORS
#define DEBUG_ERRORS 0
#endif

// Set ERRORS to non-zero to enable error tracking. Without error tracking, errors are still detected, but it can't tell you where an error occurred.
#ifndef ERRORS
#define ERRORS 1
#endif

#ifndef ERRORS_PRED
#define ERRORS_PRED 1
#endif

#ifndef ERRORS_IDENT
#define ERRORS_IDENT 1
#endif

#ifndef ERRORS_TERMINALS
#define ERRORS_TERMINALS 1
#endif

#ifndef ERRORS_REFS
#define ERRORS_REFS 1
#endif

//
// ChpegNode
//

void ChpegNode_print(ChpegNode *self, ChpegParser *parser, const unsigned char *input, int depth, FILE *fp)
{
    char flags[CHPEG_FLAGS_DISPLAY_SIZE];
#if CHPEG_EXTENSION_TRIM
    char *data = chpeg_esc_bytes(&input[self->token_offset], self->token_length, 40);
#else
    char *data = chpeg_esc_bytes(&input[self->offset], self->length, 40);
#endif
    const char *def_name = ChpegByteCode_def_name(parser->bc, self->def);

    if (depth == 0) {
        fprintf(fp,
#if CHPEG_NODE_REF_COUNT && CHPEG_DEBUG_REFS
            "     "
#endif
            " OFFSET   LEN     ID NC FLG IDENT \"DATA\"\n");
    }

    fprintf(fp,
#if CHPEG_NODE_REF_COUNT && CHPEG_DEBUG_REFS
        "%4d "
#endif
        "%6zu %6zu %6d %2d %3s %*s%s \"%s\"\n",
#if CHPEG_NODE_REF_COUNT && CHPEG_DEBUG_REFS
        self->ref_count,
#endif
#if CHPEG_EXTENSION_TRIM
        self->token_offset,
        self->token_length,
#else
        self->offset,
        self->length,
#endif
        self->def,
        self->num_children,
        chpeg_flags(flags, self->flags),
        depth * 2, "",
        def_name ? def_name : "<N/A>",
        data ? data : "<NULL>"
        );

    if (data) { CHPEG_FREE(data); data = NULL; }
    for (ChpegNode *p = self->head; p; p = p->next) {
        ChpegNode_print(p, parser, input, depth + 1, fp);
    }
}

ChpegNode *ChpegNode_new(int def, size_t offset, size_t length, int flags)
{
    ChpegNode *self = (ChpegNode *)CHPEG_CALLOC(1, sizeof(ChpegNode));
    self->def = def;
    self->offset = offset;
    self->length = length;
    self->flags = flags;
#if CHPEG_NODE_REF_COUNT
    self->ref_count = 1;
#endif
    return self;
}

#if CHPEG_EXTENSION_REFS
static inline ChpegReferenceInfo *ChpegNode_alloc_refs(ChpegNode *self, int num_refs)
{
    if (num_refs) {
        self->refs = CHPEG_CALLOC(num_refs, sizeof(ChpegReferenceInfo));
        return self->refs;
    }
    return NULL;
}
#endif


#if 0
ChpegNode *ChpegNode_copy(ChpegNode *other)
{
    ChpegNode *self = (ChpegNode *)CHPEG_MALLOC(sizeof(ChpegNode));
    memcpy(self, other, sizeof(ChpegNode));
#if CHPEG_NODE_REF_COUNT
    self->ref_count = 1;
#endif
    self->next = NULL;
    return self;
}
#endif

void ChpegUndoAction_free(ChpegUndoAction *self)
{
#if CHPEG_NODE_REF_COUNT
        assert(self->ref_count > 0);
        if (--self->ref_count == 0) {
#endif
            if (self->data) {
                CHPEG_FREE(self->data);
            }
            CHPEG_FREE(self);
#if CHPEG_NODE_REF_COUNT
        }
#endif
}

// Actually free a node, ignoring reference count.
// Don't call this directly.
// Instead, call one of:
//   void ChpegNode_free(ChpegNode *self)
//   void ChpegNode_free_nr(ChpegNode *self)
void ChpegNode__free__(ChpegNode *self)
{
    if (self) {
#if CHPEG_UNDO
        ChpegUndoAction *action, *tmp;
        for (action = self->undo_action; action; action = tmp) {
            tmp = action->next;
            if (action->data) {
                CHPEG_FREE(action->data);
            }
            CHPEG_FREE(action);
        }
#endif
#if CHPEG_EXTENSION_REFS
        if (self->refs) {
            CHPEG_FREE(self->refs);
            self->refs = NULL;
        }
#endif
        CHPEG_FREE(self);
    }
}

// free entire sub-tree recursively
void ChpegNode_free(ChpegNode *self)
{
    if (self) {
        ChpegNode *tmp;
        for (ChpegNode *p = self->head; p; p = tmp) {
            tmp = p->next;
            ChpegNode_free(p);
        }
        self->head = NULL;

#if CHPEG_UNDO
        ChpegUndoAction *action, *atmp;
        for (action = self->undo_action; action; action = atmp) {
            atmp = action->next;
            ChpegUndoAction_free(action);
        }
        self->undo_action = NULL;
#endif

#if CHPEG_NODE_REF_COUNT
        assert(self->ref_count > 0);
        if (--self->ref_count == 0) {
#endif
            ChpegNode__free__(self);
#if CHPEG_NODE_REF_COUNT
        }
#endif
    }
}

// free one node, non-recursively
void ChpegNode_free_nr(ChpegNode *self)
{
    if (self) {
#if CHPEG_UNDO
        ChpegUndoAction *action, *atmp;
        for (action = self->undo_action; action; action = atmp) {
            atmp = action->next;
            ChpegUndoAction_free(action);
        }
        self->undo_action = NULL;
#endif

#if CHPEG_NODE_REF_COUNT
        assert(self->ref_count > 0);
        if (--self->ref_count == 0) {
#endif
            ChpegNode__free__(self);
#if CHPEG_NODE_REF_COUNT
        }
#endif
    }
}

ChpegNode *ChpegNode_push_child(ChpegNode *self, ChpegNode *node)
{
    node->parent = self;
    node->next = self->head;
    self->head = node;
    ++(self->num_children);
    return node;
}

void ChpegNode_pop_child(ChpegNode *self)
{
    if (self->head) {
        ChpegNode *tmp = self->head;
        self->head = self->head->next;
        ChpegNode_free(tmp);
        --(self->num_children);
    }
}

#if CHPEG_UNDO
void ChpegNode_add_undo(ChpegNode *self, ChpegUndoFunction func,
    void *data, size_t data_size)
{
    ChpegUndoAction *action = CHPEG_CALLOC(1, sizeof(ChpegUndoAction));
    assert(func);
#if CHPEG_NODE_REF_COUNT
    action->ref_count = 1;
#endif
    action->func = func;
    action->data = data;
    action->data_size = data_size;
    action->next = self->undo_action;
    self->undo_action = action;
    self->num_undo++;
}

// recursively perform undo actions in nodes, deepest first, then free nodes
void ChpegNode_undo_free(ChpegNode *self, int depth)
{
    if (self) {
        ChpegNode *tmp;
        for (ChpegNode *p = self->head; p; p = tmp) {
            tmp = p->next;
            ChpegNode_undo_free(p, depth + 1);
        }
        self->head = NULL;

#if 0
        fprintf(stderr, "ChpegNode_undo_free: UNDO depth=%d <d:%d o:%zu l:%zu f:%d>\n",
            depth, self->def, self->offset, self->length, self->flags);
#endif

        ChpegUndoAction *action;
        for (action = self->undo_action; action; action = action->next) {
            assert(action->func);
            action->func(self, action->data);
        }
        ChpegNode_free_nr(self);
    }
}

// drop-in replacement for ChpegNode_pop_child that calls undo actions
// (use only when something fails and we do backtrack)
void ChpegNode_pop_child_undo(ChpegNode *self)
{
    if (self->head) {
        ChpegNode *tmp = self->head;
        self->head = self->head->next;
        ChpegNode_undo_free(tmp, 0);
        --(self->num_children);
    }
}

// pop the undo stack and run the undo action; free action afterwards
void ChpegNode_pop_undo(ChpegNode *self)
{
    if (self->undo_action) {
        ChpegUndoAction *action = self->undo_action;
        self->undo_action = self->undo_action->next;
        assert(action->func);
        action->func(self, action->data);
        ChpegUndoAction_free(action);
    }
}
#endif

// replace first child with contents of first child
void ChpegNode_unpack_child(ChpegNode *self)
{
    ChpegNode *first_child = self->head; // first child
    // find last child of first child
    ChpegNode *last = first_child->head;
    for (;;) {
        last->parent = self;
        ++self->num_children;
        if (!last->next) break;
        last = last->next;
    }
    last->next = self->head->next; // link last item to second child
    self->head = first_child->head; // change first child (head) link
    ChpegNode_free_nr(first_child); // free the former first child
    --self->num_children;
}

// scans the child nodes to determine if we can simplify this node
int ChpegNode_can_simplify(ChpegNode *self)
{
    // STOP flag means no simplification (force a node capture)
    if (self->flags & CHPEG_FLAG_STOP) {
        return 0;
    }

    ChpegNode *p = NULL;

    size_t pos = self->offset + self->length; // start at end this node
    // scanning goes backwards since child order is reversed in tree as build while parsing

    int cnt = 0, text = 0;
    for (p = self->head; p;) {
#ifdef CHPEG_DEBUG_CAN_SIMPLIFY
        fprintf(stderr, "node: <d:%d o:%zu l:%zu f:%d>, pos=%zu, cnt=%d, text=%d\n",
            p->def, p->offset, p->length, p->flags, pos, cnt, text);
#endif
        assert(p->offset + p->length <= pos);
        if (p->offset + p->length < pos) {
            ++text;                             // a gap is considered a text node
        }
        pos = p->offset;
        if (!(p->flags & CHPEG_FLAG_IGNORE)) {
            ++cnt;                              // a non-ignore node is candidate
        }
        p = p->next;
    }
    assert(pos >= self->offset);
    if (pos > self->offset) {
        ++text;
    }
    // if we have one candidate node and no text nodes, we can simplify
    if (cnt == 1 && !text) {
#ifdef CHPEG_DEBUG_CAN_SIMPLIFY
        fprintf(stderr, "can simplify node: <d:%d o:%zu l:%zu f:%d>, cnt=%d, text=%d\n",
            self->def, self->offset, self->length, self->flags,
            cnt, text);
#endif
        return 1;
    }
#ifdef CHPEG_DEBUG_CAN_SIMPLIFY
    fprintf(stderr, "can't simplify node: <d:%d o:%zu l:%zu f:%d>, cnt=%d, text=%d\n",
        self->def, self->offset, self->length, self->flags,
        cnt, text);
#endif
    return 0;
}

// 'Unwrap' a ChpegNode, recursively removing unnecessary parent nodes containing only one child.
// In the process, this reverses the reverse node insertion used in tree building, so should only
// be called once on the tree root after a successful parse.
ChpegNode *ChpegNode_unwrap(ChpegNode *self)
{
    if (!(self->flags & (CHPEG_FLAG_STOP | CHPEG_FLAG_LEAF)) && self->num_children == 1) {
        ChpegNode *tmp = ChpegNode_unwrap(self->head);
        self->head = NULL;
        ChpegNode_free(self);
        return tmp;
    }
    ChpegNode *p = self->head; self->head = NULL;
    ChpegNode *tmp;
    for (; p; p=tmp) {
        tmp = p->next;
        p = ChpegNode_unwrap(p);
        p->next = self->head;
        self->head = p;
    }
    return self;
}

// reverse a tree
ChpegNode *ChpegNode_reverse(ChpegNode *self)
{
    ChpegNode *p = self->head; self->head = NULL;
    ChpegNode *tmp;
    for (; p; p=tmp) {
        tmp = p->next;
        p = ChpegNode_reverse(p);
        p->next = self->head;
        self->head = p;
    }
    return self;
}

// reverse a tree, deleting IGNORE nodes in the process
ChpegNode *ChpegNode_reverse_clean(ChpegNode *self)
{
    ChpegNode *p = self->head; self->head = NULL;
    ChpegNode *tmp;
    for (; p; p=tmp) {
        tmp = p->next;
        if (p->flags & CHPEG_FLAG_IGNORE) {
            ChpegNode_free(p);
            --self->num_children;
        }
        else {
            p = ChpegNode_reverse_clean(p);
            p->next = self->head;
            self->head = p;
        }
    }
    return self;
}


#if CHPEG_PACKRAT

#if CHPEG_UNDO
typedef struct _ChpegPUndoNode
{
    struct _ChpegPUndoNode *head;
    struct _ChpegPUndoNode *next;
    ChpegUndoAction *undo_action;
} ChpegPUndoNode;
#endif

typedef struct _ChpegPNode
{
    struct _ChpegPNode *head;
    struct _ChpegPNode *next;
    ChpegNode *node;
#if CHPEG_UNDO
    ChpegPUndoNode *undo;
#endif
} ChpegPNode;

static void ChpegPUndoNode_free(ChpegPUndoNode *self)
{
    if (self) {
        ChpegUndoAction_free(self->undo_action);
        CHPEG_FREE(self);
    }
}

static void ChpegPNode_free(ChpegPNode *self)
{
    if (self) {
        ChpegPNode *tmp;
        for (ChpegPNode *p = self->head; p; p = tmp) {
            tmp = p->next;
            ChpegPNode_free(p);
        }
        self->head = NULL;

        ChpegPUndoNode *utmp;
        for (ChpegPUndoNode *pu = self->undo; pu; pu = utmp) {
            utmp = pu->next;
            ChpegPUndoNode_free(pu);
        }
        self->undo = NULL;

        ChpegNode_free_nr(self->node);
        CHPEG_FREE(self);
    }
}


static ChpegPNode *ChpegPNode_push_child(ChpegPNode *self, ChpegPNode *child)
{
    child->next = self->head;
    self->head = child;
    return child;
}

#if CHPEG_UNDO
static ChpegPUndoNode *ChpegPNode_push_undo(ChpegPNode *self, ChpegPUndoNode *undo)
{
    undo->next = self->undo;
    self->undo = undo;
    return undo;
}
#endif


static int chpeg_packrat_node_count(ChpegNode *node, int *count, int depth, int limit, ChpegParser *parser)
{
    // 'unwrap' nodes except the top one (skip useless intermediate nodes with only one child)
    if (depth > 0 && parser->simplification == 1) {
        while (node->num_children == 1 && !(node->flags & (CHPEG_FLAG_STOP | CHPEG_FLAG_LEAF))) {
            node = node->head;
        }
    }

    for (ChpegNode *p = node->head; p; p = p->next) {
        chpeg_packrat_node_count(p, count, depth + 1, limit, parser);
        if (limit && *count >= limit) {
            return limit;
        }
    }
    if (limit && *count >= limit) {
        return limit;
    }
    ++(*count);
    return *count;
}


// wraps Node sub-tree in PNodes; call with depth=0
static ChpegPNode *ChpegPNode_from_node(ChpegPNode *pnode, ChpegNode *node, int depth, ChpegParser *parser)
{
    if (depth == 0) {
        int count = 0;
        if (chpeg_packrat_node_count(node, &count, 0, CHPEG_PACKRAT_NODE_LIMIT, parser) >=
            CHPEG_PACKRAT_NODE_LIMIT)
        {
            return NULL;
        }
    }
    // 'unwrap' nodes except the top one (skip useless intermediate nodes with only one child)
    // this can lead to quite a performance increase by cutting down on nodes created in _node_copy()
    if (depth > 0 && parser->simplification == 1) {
        while (node->num_children == 1 && !(node->flags & (CHPEG_FLAG_STOP | CHPEG_FLAG_LEAF))) {
            node = node->head;
        }
    }

    if (!pnode) {
        pnode = CHPEG_CALLOC(1, sizeof(ChpegPNode));
    }

    pnode->node = node;
    ++node->ref_count;
    for (ChpegNode *p = node->head; p; p = p->next) {
        ChpegPNode *pchild = CHPEG_CALLOC(1, sizeof(ChpegPNode));
        ChpegPNode_from_node(pchild, p, depth + 1, parser);
        ChpegPNode_push_child(pnode, pchild);
    }

#if CHPEG_UNDO
    for (ChpegUndoAction *action = node->undo_action; action; action = action->next) {
        ChpegPUndoNode *pu = CHPEG_CALLOC(1, sizeof(ChpegPUndoNode));
        pu->undo_action = action;
        ++action->ref_count;
        ChpegPNode_push_undo(pnode, pu);
    }
#endif

    return pnode;
}

static ChpegNode *ChpegPNode_export(ChpegParser *parser, ChpegPNode *pnode)
{
    assert(pnode);
    ChpegNode *node = CHPEG_MALLOC(sizeof(ChpegNode));
    memcpy(node, pnode->node, sizeof(ChpegNode));
    node->next = NULL;
    node->head = NULL;
    node->num_children = 0;
    node->ref_count = 1;
    for (ChpegPNode *p = pnode->head; p; p = p->next) {
        ChpegNode *child = ChpegPNode_export(parser, p) ;
        ChpegNode_push_child(node, child);
    }
#if CHPEG_UNDO
    for (ChpegPUndoNode *pu = pnode->undo; pu; pu = pu->next) {
        void *action_data = CHPEG_MALLOC(pu->undo_action->data_size);
        memcpy(action_data, pu->undo_action->data, pu->undo_action->data_size);
        ChpegNode_add_undo(node, pu->undo_action->func, action_data, pu->undo_action->data_size);
    }
#endif
#if CHPEG_EXTENSION_REFS
    node->refs = CHPEG_MALLOC(parser->bc->num_refs * sizeof(ChpegReferenceInfo));
    memcpy(node->refs, pnode->node->refs, parser->bc->num_refs * sizeof(ChpegReferenceInfo));
#endif
    return node;
}

#if CHPEG_VM_TRACE
static void ChpegPNode_print(ChpegPNode *self, ChpegParser *parser,
    const unsigned char *input, int depth, FILE *fp)
{
    if (!self) return;

    char flags[CHPEG_FLAGS_DISPLAY_SIZE];
    char *data = chpeg_esc_bytes(&input[self->node->offset], self->node->length, 40);
    const char *def_name = ChpegByteCode_def_name(parser->bc, self->node->def);

    if (depth == 0) {
        fprintf(fp, "PNODE BEG ---------------------------------- \n");
        fprintf(fp, " OFFSET   LEN     ID NC DP FLG IDENT \"DATA\"\n");
    }

    fprintf(fp, "%6zu %6zu %6d %2d %2d %3s %*s%s \"%s\"\n",
        self->node->offset,
        self->node->length,
        self->node->def,
        self->node->num_children,
        depth,
        chpeg_flags(flags, self->node->flags),
        depth * 2, "",
        def_name ? def_name : "<N/A>",
        data ? data : "<NULL>"
        );

    if (data) { CHPEG_FREE(data); data = NULL; }
    for (ChpegPNode *p = self->head; p; p = p->next) {
        ChpegPNode_print(p, parser, input, depth + 1, fp);
    }

    if (depth == 0) {
        fprintf(fp, "PNODE END ---------------------------------- \n");
    }
}
#endif

#endif // #if CHPEG_PACKRAT

#if CHPEG_EXTENSION_REFS

#if CHPEG_UNDO
typedef struct _ChpegUndoMarkData {
    int ref_id;
    ChpegReferenceInfo value;
} ChpegUndoMarkData;

void chpeg_undo_mark(ChpegNode *node, void *_data)
{
    ChpegUndoMarkData *data = (ChpegUndoMarkData *)_data;
#if 0
    fprintf(stderr, "chpeg_undo_mark: <o:%zu l:%zu f:%d>\n",
        data->value.offset, data->value.length, data->value.flags);
#endif
    for (ChpegNode *p = node; p; p = p->parent) {
        if (p->flags & CHPEG_FLAG_REFSCOPE) {
            p->refs[data->ref_id] = data->value;
            break;
        }
    }
}

#endif
#endif

//
// ChpegParser
//

ChpegParser *ChpegParser_new(const ChpegByteCode *bc)
{
    ChpegParser *self = (ChpegParser *)CHPEG_CALLOC(1, sizeof(ChpegParser));

    self->bc = bc;
    self->tree_root = NULL;
    self->simplification = 1;
    self->max_tree_depth = CHPEG_MAX_TREE_DEPTH;
    self->max_stack_size = CHPEG_STACK_SIZE;
    self->error_offset = 0;
    self->errors = NULL;
    self->errors_size = 0;
    self->errors_capacity = 0;

#if CHPEG_VM_TRACE
    self->vm_trace = 0;
#endif
#if CHPEG_VM_PRINT_TREE
    self->vm_print_tree = 0;
#endif
#if CHPEG_VM_PROFILE
    self->vm_profile = 0;
    self->prof_inst_cnt = 0;
    self->prof_ident_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_isucc_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_ifail_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_choice_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_cisucc_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_cifail_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->farthest_backtrack = 0;
#endif
#if CHPEG_PACKRAT
    self->packrat = 0;
    self->packrat_window_size = 0;
#endif
    return self;
}

void ChpegParser_free(ChpegParser *self)
{
    if (self) {
        if (self->tree_root) {
            ChpegNode_free(self->tree_root);
            self->tree_root = NULL;
        }
#if ERRORS
        if (self->errors) {
            CHPEG_FREE(self->errors);
            self->errors = NULL;
            self->errors_capacity = 0;
            self->errors_size = 0;
        }
#endif
#if CHPEG_VM_PROFILE
        if (self->prof_ident_cnt) {
            CHPEG_FREE(self->prof_ident_cnt);
            self->prof_ident_cnt = NULL;
        }
        if (self->prof_isucc_cnt) {
            CHPEG_FREE(self->prof_isucc_cnt);
            self->prof_isucc_cnt = NULL;
        }
        if (self->prof_ifail_cnt) {
            CHPEG_FREE(self->prof_ifail_cnt);
            self->prof_ifail_cnt = NULL;
        }
        if (self->prof_choice_cnt) {
            CHPEG_FREE(self->prof_choice_cnt);
            self->prof_choice_cnt = NULL;
        }
        if (self->prof_cisucc_cnt) {
            CHPEG_FREE(self->prof_cisucc_cnt);
            self->prof_cisucc_cnt = NULL;
        }
        if (self->prof_cifail_cnt) {
            CHPEG_FREE(self->prof_cifail_cnt);
            self->prof_cifail_cnt = NULL;
        }
#endif
        CHPEG_FREE(self);
    }
}

void ChpegParser_print_tree(ChpegParser *self, const unsigned char *input, FILE *fp)
{
    ChpegNode_print(self->tree_root, self, input, 0, fp);
}

#if CHPEG_VM_PROFILE
void ChpegParser_print_profile(ChpegParser *self,
    const unsigned char *input, size_t length, FILE *fp)
{
    fprintf(fp, "Instructions executed:\n");
    fprintf(fp, "%6s %8s %11s %6s\n", "OP-", "opcode", "count", "%");
    for (int i = 0; i < CHPEG_NUM_OPS; ++i) {
        fprintf(fp, "%6s %8s %11d %6.2f\n", "OP ",
            Chpeg_op_name(i), self->prof_op_cnt[i],
            100.0 * (float)self->prof_op_cnt[i] / (float)self->prof_inst_cnt);
    }
    fprintf(fp, "%6s %8s %11d %6.2f\n", "OP=", "Total", self->prof_inst_cnt, 100.0);

    int total_ident = self->prof_op_cnt[CHPEG_OP_IDENT];
    int total_isucc = self->prof_op_cnt[CHPEG_OP_ISUCC];
    int total_ifail = self->prof_op_cnt[CHPEG_OP_IFAIL];

    fprintf(fp, "\n");
    fprintf(fp, "Definition identifier calls:\n");
    fprintf(fp, "  DEF-   id       IDENT      %%       ISUCC       IFAIL  name\n");
    for (int i = 0; i < self->bc->num_defs; ++i) {
        fprintf(fp, "%6s %4d %11d %6.2f %11d %11d  %s\n", "DEF ", i,
            self->prof_ident_cnt[i],
            100.0 * (float)self->prof_ident_cnt[i] / (float)total_ident,
            self->prof_isucc_cnt[i],
            self->prof_ifail_cnt[i],
            ChpegByteCode_def_name(self->bc, i));
    }
    fprintf(fp, "%6s %4s %11d %6.2f %11d %11d  %s\n", "DEF=", "--",
        total_ident, 100.0, total_isucc, total_ifail, "--");

    int total_choice = self->prof_op_cnt[CHPEG_OP_CHOICE];
    int total_cisucc = self->prof_op_cnt[CHPEG_OP_CISUCC];
    int total_cifail = self->prof_op_cnt[CHPEG_OP_CIFAIL];

    fprintf(fp, "\n");
    fprintf(fp, "Choice calls per definition:\n");
    fprintf(fp, "  CHOICE-  def      CHOICE      %%      CISUCC      CIFAIL  def_name\n");
    for (int i = 0; i < self->bc->num_defs; ++i) {
        fprintf(fp, "%9s %4d %11d %6.2f %11d %11d  %s\n", "CHOICE ", i,
            self->prof_choice_cnt[i],
            100.0 * (float)self->prof_choice_cnt[i] / (float)total_choice,
            self->prof_cisucc_cnt[i],
            self->prof_cifail_cnt[i],
            ChpegByteCode_def_name(self->bc, i));
    }
    fprintf(fp, "%9s %4s %11d %6.2f %11d %11d  %s\n", "CHOICE=", "--",
        total_choice, 100.0, total_cisucc, total_cifail, "--");

    fprintf(fp, "\nFarthest backtrack: %zu\n", self->farthest_backtrack);

    fprintf(fp, "\nInstructions executed: %d, instructions per input byte: %.2f\n",
        self->prof_inst_cnt, (float)self->prof_inst_cnt / (float)length);
}
#endif

void ChpegParser_expected(ChpegParser *self, size_t offset, int depth, int def, int pc)
{
    if (offset >= self->error_offset) {
        if (offset > self->error_offset) {
            self->error_offset = offset;
            self->errors_size = 0;
        }
        if (self->errors_size + 1 > self->errors_capacity) {
            if (!self->errors) {
                self->errors_capacity = 1;
                self->errors = CHPEG_MALLOC(self->errors_capacity * sizeof(ChpegErrorInfo));
            }
            else {
                self->errors_capacity *= 2;
            }
            self->errors = CHPEG_REALLOC(self->errors, self->errors_capacity * sizeof(ChpegErrorInfo));
        }
        self->errors[self->errors_size++] = (ChpegErrorInfo)
        {
            .depth = depth,
            .def = def,
            .pc = pc,
        };
    }
}

void ChpegParser_print_errors(ChpegParser *self, const unsigned char *input, int all)
{
#if ERRORS
    if (self->errors_size == 0) {
        fprintf(stderr, "No errors detected / tracked.\n");
        return;
    }

    assert(self->errors_size > 0);
    for (int i = all ? 0 : self->errors_size - 1; i < self->errors_size; ++i) {
        ChpegErrorInfo *error = &self->errors[i];
        const char *def_name = ChpegByteCode_def_name(self->bc, error->def);
        int inst = self->bc->instructions[error->pc];
        int op = inst & 0xff;
        int arg = inst >> 8;

        char *esc = NULL;
        const char *str = NULL;
        int depth_indent = (error->depth - 1) *2;
        const char *expected = "Expected:";

        // if a predicate is followed by an instruction case we can display,
        // use that, switching to 'unexpected' for PREDN (predicate '!')
        // (otherwise, it'll fall through to the default 'syntax error' case below)
        if (op == CHPEG_OP_PREDN || op == CHPEG_OP_PREDA) {
            int next_inst = self->bc->instructions[error->pc + 1];
            switch (next_inst & 0xff) {
                case CHPEG_OP_IDENT:
                case CHPEG_OP_LIT:
                case CHPEG_OP_CHRCLS:
                case CHPEG_OP_DOT:
                    if (op == CHPEG_OP_PREDN) {
                        expected = "Unexpected:";
                    }
                    op = next_inst & 0xff;
                    arg = next_inst >> 8;
                    break;
            }
        }

        switch (op) {
            case CHPEG_OP_IDENT:
                str = ChpegByteCode_def_name(self->bc, arg);
                fprintf(stderr, "%11s %*s%s in %s at offset %lu\n",
                    expected,
                    depth_indent, "",
                    str ? str : "<N/A>>",
                    def_name ? def_name : "<N/A>",
                    self->error_offset);
                break;
            case CHPEG_OP_LIT:
                esc = chpeg_esc_bytes((unsigned char *)self->bc->strings[arg],
                    self->bc->str_len[arg], 20);
                fprintf(stderr, "%11s %*s\"%s\" in %s at offset %lu\n",
                    expected,
                    depth_indent, "",
                    esc ? esc : "<NULL>",
                    def_name ? def_name : "<N/A>",
                    self->error_offset);
                CHPEG_FREE(esc); esc = NULL;
                break;
            case CHPEG_OP_CHRCLS:
                esc = chpeg_esc_bytes((unsigned char *)self->bc->strings[arg],
                    self->bc->str_len[arg], 20);
                fprintf(stderr, "%11s %*s[%s] in %s at offset %lu\n",
                    expected,
                    depth_indent, "",
                    esc ? esc : "<NULL>",
                    def_name ? def_name : "<N/A>",
                    self->error_offset);
                CHPEG_FREE(esc); esc = NULL;
                break;
            case CHPEG_OP_DOT:
                fprintf(stderr, "%11s %*scharacter in %s at offset %lu\n",
                    expected,
                    depth_indent, "",
                    def_name ? def_name : "<N/A>",
                    self->error_offset);
                break;
            default: // unhandled op, show instruction in <> for debugging
                fprintf(stderr, "%11s %*sSyntax error in %s at offset %lu <%s,%d>\n",
                    "Error:",
                    depth_indent, "",
                    def_name ? def_name : "<N/A>",
                    self->error_offset,
                    Chpeg_op_name(op), arg);
                break;
        }
    }
#else
    fprintf(stderr, "Error tracking disabled at compile time.\n");
#endif
}

void ChpegParser_print_error(ChpegParser *self, const unsigned char *input)
{
    ChpegParser_print_errors(self, input, 0);
}<commit_msg>Display parser errors in input:line:col: format<commit_after>//
// chpeg: parser.c {
//

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#ifndef CHPEG_AMALGAMATION
#include "chpeg/mem.h"
#include "chpeg/util.h"
#include "chpeg/parser.h"
#endif

#ifndef CHPEG_MAX_TREE_DEPTH
#define CHPEG_MAX_TREE_DEPTH 256
#endif

#ifndef CHPEG_STACK_SIZE
#define CHPEG_STACK_SIZE 1024
#endif

#ifndef SANITY_CHECKS
#define SANITY_CHECKS 1
#endif

#ifndef DEBUG_ERRORS
#define DEBUG_ERRORS 0
#endif

// Set ERRORS to non-zero to enable error tracking. Without error tracking, errors are still detected, but it can't tell you where an error occurred.
#ifndef ERRORS
#define ERRORS 1
#endif

#ifndef ERRORS_PRED
#define ERRORS_PRED 1
#endif

#ifndef ERRORS_IDENT
#define ERRORS_IDENT 1
#endif

#ifndef ERRORS_TERMINALS
#define ERRORS_TERMINALS 1
#endif

#ifndef ERRORS_REFS
#define ERRORS_REFS 1
#endif

//
// ChpegNode
//

void ChpegNode_print(ChpegNode *self, ChpegParser *parser, const unsigned char *input, int depth, FILE *fp)
{
    char flags[CHPEG_FLAGS_DISPLAY_SIZE];
#if CHPEG_EXTENSION_TRIM
    char *data = chpeg_esc_bytes(&input[self->token_offset], self->token_length, 40);
#else
    char *data = chpeg_esc_bytes(&input[self->offset], self->length, 40);
#endif
    const char *def_name = ChpegByteCode_def_name(parser->bc, self->def);

    if (depth == 0) {
        fprintf(fp,
#if CHPEG_NODE_REF_COUNT && CHPEG_DEBUG_REFS
            "     "
#endif
            " OFFSET   LEN     ID NC FLG IDENT \"DATA\"\n");
    }

    fprintf(fp,
#if CHPEG_NODE_REF_COUNT && CHPEG_DEBUG_REFS
        "%4d "
#endif
        "%6zu %6zu %6d %2d %3s %*s%s \"%s\"\n",
#if CHPEG_NODE_REF_COUNT && CHPEG_DEBUG_REFS
        self->ref_count,
#endif
#if CHPEG_EXTENSION_TRIM
        self->token_offset,
        self->token_length,
#else
        self->offset,
        self->length,
#endif
        self->def,
        self->num_children,
        chpeg_flags(flags, self->flags),
        depth * 2, "",
        def_name ? def_name : "<N/A>",
        data ? data : "<NULL>"
        );

    if (data) { CHPEG_FREE(data); data = NULL; }
    for (ChpegNode *p = self->head; p; p = p->next) {
        ChpegNode_print(p, parser, input, depth + 1, fp);
    }
}

ChpegNode *ChpegNode_new(int def, size_t offset, size_t length, int flags)
{
    ChpegNode *self = (ChpegNode *)CHPEG_CALLOC(1, sizeof(ChpegNode));
    self->def = def;
    self->offset = offset;
    self->length = length;
    self->flags = flags;
#if CHPEG_NODE_REF_COUNT
    self->ref_count = 1;
#endif
    return self;
}

#if CHPEG_EXTENSION_REFS
static inline ChpegReferenceInfo *ChpegNode_alloc_refs(ChpegNode *self, int num_refs)
{
    if (num_refs) {
        self->refs = CHPEG_CALLOC(num_refs, sizeof(ChpegReferenceInfo));
        return self->refs;
    }
    return NULL;
}
#endif


#if 0
ChpegNode *ChpegNode_copy(ChpegNode *other)
{
    ChpegNode *self = (ChpegNode *)CHPEG_MALLOC(sizeof(ChpegNode));
    memcpy(self, other, sizeof(ChpegNode));
#if CHPEG_NODE_REF_COUNT
    self->ref_count = 1;
#endif
    self->next = NULL;
    return self;
}
#endif

void ChpegUndoAction_free(ChpegUndoAction *self)
{
#if CHPEG_NODE_REF_COUNT
        assert(self->ref_count > 0);
        if (--self->ref_count == 0) {
#endif
            if (self->data) {
                CHPEG_FREE(self->data);
            }
            CHPEG_FREE(self);
#if CHPEG_NODE_REF_COUNT
        }
#endif
}

// Actually free a node, ignoring reference count.
// Don't call this directly.
// Instead, call one of:
//   void ChpegNode_free(ChpegNode *self)
//   void ChpegNode_free_nr(ChpegNode *self)
void ChpegNode__free__(ChpegNode *self)
{
    if (self) {
#if CHPEG_UNDO
        ChpegUndoAction *action, *tmp;
        for (action = self->undo_action; action; action = tmp) {
            tmp = action->next;
            if (action->data) {
                CHPEG_FREE(action->data);
            }
            CHPEG_FREE(action);
        }
#endif
#if CHPEG_EXTENSION_REFS
        if (self->refs) {
            CHPEG_FREE(self->refs);
            self->refs = NULL;
        }
#endif
        CHPEG_FREE(self);
    }
}

// free entire sub-tree recursively
void ChpegNode_free(ChpegNode *self)
{
    if (self) {
        ChpegNode *tmp;
        for (ChpegNode *p = self->head; p; p = tmp) {
            tmp = p->next;
            ChpegNode_free(p);
        }
        self->head = NULL;

#if CHPEG_UNDO
        ChpegUndoAction *action, *atmp;
        for (action = self->undo_action; action; action = atmp) {
            atmp = action->next;
            ChpegUndoAction_free(action);
        }
        self->undo_action = NULL;
#endif

#if CHPEG_NODE_REF_COUNT
        assert(self->ref_count > 0);
        if (--self->ref_count == 0) {
#endif
            ChpegNode__free__(self);
#if CHPEG_NODE_REF_COUNT
        }
#endif
    }
}

// free one node, non-recursively
void ChpegNode_free_nr(ChpegNode *self)
{
    if (self) {
#if CHPEG_UNDO
        ChpegUndoAction *action, *atmp;
        for (action = self->undo_action; action; action = atmp) {
            atmp = action->next;
            ChpegUndoAction_free(action);
        }
        self->undo_action = NULL;
#endif

#if CHPEG_NODE_REF_COUNT
        assert(self->ref_count > 0);
        if (--self->ref_count == 0) {
#endif
            ChpegNode__free__(self);
#if CHPEG_NODE_REF_COUNT
        }
#endif
    }
}

ChpegNode *ChpegNode_push_child(ChpegNode *self, ChpegNode *node)
{
    node->parent = self;
    node->next = self->head;
    self->head = node;
    ++(self->num_children);
    return node;
}

void ChpegNode_pop_child(ChpegNode *self)
{
    if (self->head) {
        ChpegNode *tmp = self->head;
        self->head = self->head->next;
        ChpegNode_free(tmp);
        --(self->num_children);
    }
}

#if CHPEG_UNDO
void ChpegNode_add_undo(ChpegNode *self, ChpegUndoFunction func,
    void *data, size_t data_size)
{
    ChpegUndoAction *action = CHPEG_CALLOC(1, sizeof(ChpegUndoAction));
    assert(func);
#if CHPEG_NODE_REF_COUNT
    action->ref_count = 1;
#endif
    action->func = func;
    action->data = data;
    action->data_size = data_size;
    action->next = self->undo_action;
    self->undo_action = action;
    self->num_undo++;
}

// recursively perform undo actions in nodes, deepest first, then free nodes
void ChpegNode_undo_free(ChpegNode *self, int depth)
{
    if (self) {
        ChpegNode *tmp;
        for (ChpegNode *p = self->head; p; p = tmp) {
            tmp = p->next;
            ChpegNode_undo_free(p, depth + 1);
        }
        self->head = NULL;

#if 0
        fprintf(stderr, "ChpegNode_undo_free: UNDO depth=%d <d:%d o:%zu l:%zu f:%d>\n",
            depth, self->def, self->offset, self->length, self->flags);
#endif

        ChpegUndoAction *action;
        for (action = self->undo_action; action; action = action->next) {
            assert(action->func);
            action->func(self, action->data);
        }
        ChpegNode_free_nr(self);
    }
}

// drop-in replacement for ChpegNode_pop_child that calls undo actions
// (use only when something fails and we do backtrack)
void ChpegNode_pop_child_undo(ChpegNode *self)
{
    if (self->head) {
        ChpegNode *tmp = self->head;
        self->head = self->head->next;
        ChpegNode_undo_free(tmp, 0);
        --(self->num_children);
    }
}

// pop the undo stack and run the undo action; free action afterwards
void ChpegNode_pop_undo(ChpegNode *self)
{
    if (self->undo_action) {
        ChpegUndoAction *action = self->undo_action;
        self->undo_action = self->undo_action->next;
        assert(action->func);
        action->func(self, action->data);
        ChpegUndoAction_free(action);
    }
}
#endif

// replace first child with contents of first child
void ChpegNode_unpack_child(ChpegNode *self)
{
    ChpegNode *first_child = self->head; // first child
    // find last child of first child
    ChpegNode *last = first_child->head;
    for (;;) {
        last->parent = self;
        ++self->num_children;
        if (!last->next) break;
        last = last->next;
    }
    last->next = self->head->next; // link last item to second child
    self->head = first_child->head; // change first child (head) link
    ChpegNode_free_nr(first_child); // free the former first child
    --self->num_children;
}

// scans the child nodes to determine if we can simplify this node
int ChpegNode_can_simplify(ChpegNode *self)
{
    // STOP flag means no simplification (force a node capture)
    if (self->flags & CHPEG_FLAG_STOP) {
        return 0;
    }

    ChpegNode *p = NULL;

    size_t pos = self->offset + self->length; // start at end this node
    // scanning goes backwards since child order is reversed in tree as build while parsing

    int cnt = 0, text = 0;
    for (p = self->head; p;) {
#ifdef CHPEG_DEBUG_CAN_SIMPLIFY
        fprintf(stderr, "node: <d:%d o:%zu l:%zu f:%d>, pos=%zu, cnt=%d, text=%d\n",
            p->def, p->offset, p->length, p->flags, pos, cnt, text);
#endif
        assert(p->offset + p->length <= pos);
        if (p->offset + p->length < pos) {
            ++text;                             // a gap is considered a text node
        }
        pos = p->offset;
        if (!(p->flags & CHPEG_FLAG_IGNORE)) {
            ++cnt;                              // a non-ignore node is candidate
        }
        p = p->next;
    }
    assert(pos >= self->offset);
    if (pos > self->offset) {
        ++text;
    }
    // if we have one candidate node and no text nodes, we can simplify
    if (cnt == 1 && !text) {
#ifdef CHPEG_DEBUG_CAN_SIMPLIFY
        fprintf(stderr, "can simplify node: <d:%d o:%zu l:%zu f:%d>, cnt=%d, text=%d\n",
            self->def, self->offset, self->length, self->flags,
            cnt, text);
#endif
        return 1;
    }
#ifdef CHPEG_DEBUG_CAN_SIMPLIFY
    fprintf(stderr, "can't simplify node: <d:%d o:%zu l:%zu f:%d>, cnt=%d, text=%d\n",
        self->def, self->offset, self->length, self->flags,
        cnt, text);
#endif
    return 0;
}

// 'Unwrap' a ChpegNode, recursively removing unnecessary parent nodes containing only one child.
// In the process, this reverses the reverse node insertion used in tree building, so should only
// be called once on the tree root after a successful parse.
ChpegNode *ChpegNode_unwrap(ChpegNode *self)
{
    if (!(self->flags & (CHPEG_FLAG_STOP | CHPEG_FLAG_LEAF)) && self->num_children == 1) {
        ChpegNode *tmp = ChpegNode_unwrap(self->head);
        self->head = NULL;
        ChpegNode_free(self);
        return tmp;
    }
    ChpegNode *p = self->head; self->head = NULL;
    ChpegNode *tmp;
    for (; p; p=tmp) {
        tmp = p->next;
        p = ChpegNode_unwrap(p);
        p->next = self->head;
        self->head = p;
    }
    return self;
}

// reverse a tree
ChpegNode *ChpegNode_reverse(ChpegNode *self)
{
    ChpegNode *p = self->head; self->head = NULL;
    ChpegNode *tmp;
    for (; p; p=tmp) {
        tmp = p->next;
        p = ChpegNode_reverse(p);
        p->next = self->head;
        self->head = p;
    }
    return self;
}

// reverse a tree, deleting IGNORE nodes in the process
ChpegNode *ChpegNode_reverse_clean(ChpegNode *self)
{
    ChpegNode *p = self->head; self->head = NULL;
    ChpegNode *tmp;
    for (; p; p=tmp) {
        tmp = p->next;
        if (p->flags & CHPEG_FLAG_IGNORE) {
            ChpegNode_free(p);
            --self->num_children;
        }
        else {
            p = ChpegNode_reverse_clean(p);
            p->next = self->head;
            self->head = p;
        }
    }
    return self;
}


#if CHPEG_PACKRAT

#if CHPEG_UNDO
typedef struct _ChpegPUndoNode
{
    struct _ChpegPUndoNode *head;
    struct _ChpegPUndoNode *next;
    ChpegUndoAction *undo_action;
} ChpegPUndoNode;
#endif

typedef struct _ChpegPNode
{
    struct _ChpegPNode *head;
    struct _ChpegPNode *next;
    ChpegNode *node;
#if CHPEG_UNDO
    ChpegPUndoNode *undo;
#endif
} ChpegPNode;

static void ChpegPUndoNode_free(ChpegPUndoNode *self)
{
    if (self) {
        ChpegUndoAction_free(self->undo_action);
        CHPEG_FREE(self);
    }
}

static void ChpegPNode_free(ChpegPNode *self)
{
    if (self) {
        ChpegPNode *tmp;
        for (ChpegPNode *p = self->head; p; p = tmp) {
            tmp = p->next;
            ChpegPNode_free(p);
        }
        self->head = NULL;

        ChpegPUndoNode *utmp;
        for (ChpegPUndoNode *pu = self->undo; pu; pu = utmp) {
            utmp = pu->next;
            ChpegPUndoNode_free(pu);
        }
        self->undo = NULL;

        ChpegNode_free_nr(self->node);
        CHPEG_FREE(self);
    }
}


static ChpegPNode *ChpegPNode_push_child(ChpegPNode *self, ChpegPNode *child)
{
    child->next = self->head;
    self->head = child;
    return child;
}

#if CHPEG_UNDO
static ChpegPUndoNode *ChpegPNode_push_undo(ChpegPNode *self, ChpegPUndoNode *undo)
{
    undo->next = self->undo;
    self->undo = undo;
    return undo;
}
#endif


static int chpeg_packrat_node_count(ChpegNode *node, int *count, int depth, int limit, ChpegParser *parser)
{
    // 'unwrap' nodes except the top one (skip useless intermediate nodes with only one child)
    if (depth > 0 && parser->simplification == 1) {
        while (node->num_children == 1 && !(node->flags & (CHPEG_FLAG_STOP | CHPEG_FLAG_LEAF))) {
            node = node->head;
        }
    }

    for (ChpegNode *p = node->head; p; p = p->next) {
        chpeg_packrat_node_count(p, count, depth + 1, limit, parser);
        if (limit && *count >= limit) {
            return limit;
        }
    }
    if (limit && *count >= limit) {
        return limit;
    }
    ++(*count);
    return *count;
}


// wraps Node sub-tree in PNodes; call with depth=0
static ChpegPNode *ChpegPNode_from_node(ChpegPNode *pnode, ChpegNode *node, int depth, ChpegParser *parser)
{
    if (depth == 0) {
        int count = 0;
        if (chpeg_packrat_node_count(node, &count, 0, CHPEG_PACKRAT_NODE_LIMIT, parser) >=
            CHPEG_PACKRAT_NODE_LIMIT)
        {
            return NULL;
        }
    }
    // 'unwrap' nodes except the top one (skip useless intermediate nodes with only one child)
    // this can lead to quite a performance increase by cutting down on nodes created in _node_copy()
    if (depth > 0 && parser->simplification == 1) {
        while (node->num_children == 1 && !(node->flags & (CHPEG_FLAG_STOP | CHPEG_FLAG_LEAF))) {
            node = node->head;
        }
    }

    if (!pnode) {
        pnode = CHPEG_CALLOC(1, sizeof(ChpegPNode));
    }

    pnode->node = node;
    ++node->ref_count;
    for (ChpegNode *p = node->head; p; p = p->next) {
        ChpegPNode *pchild = CHPEG_CALLOC(1, sizeof(ChpegPNode));
        ChpegPNode_from_node(pchild, p, depth + 1, parser);
        ChpegPNode_push_child(pnode, pchild);
    }

#if CHPEG_UNDO
    for (ChpegUndoAction *action = node->undo_action; action; action = action->next) {
        ChpegPUndoNode *pu = CHPEG_CALLOC(1, sizeof(ChpegPUndoNode));
        pu->undo_action = action;
        ++action->ref_count;
        ChpegPNode_push_undo(pnode, pu);
    }
#endif

    return pnode;
}

static ChpegNode *ChpegPNode_export(ChpegParser *parser, ChpegPNode *pnode)
{
    assert(pnode);
    ChpegNode *node = CHPEG_MALLOC(sizeof(ChpegNode));
    memcpy(node, pnode->node, sizeof(ChpegNode));
    node->next = NULL;
    node->head = NULL;
    node->num_children = 0;
    node->ref_count = 1;
    for (ChpegPNode *p = pnode->head; p; p = p->next) {
        ChpegNode *child = ChpegPNode_export(parser, p) ;
        ChpegNode_push_child(node, child);
    }
#if CHPEG_UNDO
    for (ChpegPUndoNode *pu = pnode->undo; pu; pu = pu->next) {
        void *action_data = CHPEG_MALLOC(pu->undo_action->data_size);
        memcpy(action_data, pu->undo_action->data, pu->undo_action->data_size);
        ChpegNode_add_undo(node, pu->undo_action->func, action_data, pu->undo_action->data_size);
    }
#endif
#if CHPEG_EXTENSION_REFS
    node->refs = CHPEG_MALLOC(parser->bc->num_refs * sizeof(ChpegReferenceInfo));
    memcpy(node->refs, pnode->node->refs, parser->bc->num_refs * sizeof(ChpegReferenceInfo));
#endif
    return node;
}

#if CHPEG_VM_TRACE
static void ChpegPNode_print(ChpegPNode *self, ChpegParser *parser,
    const unsigned char *input, int depth, FILE *fp)
{
    if (!self) return;

    char flags[CHPEG_FLAGS_DISPLAY_SIZE];
    char *data = chpeg_esc_bytes(&input[self->node->offset], self->node->length, 40);
    const char *def_name = ChpegByteCode_def_name(parser->bc, self->node->def);

    if (depth == 0) {
        fprintf(fp, "PNODE BEG ---------------------------------- \n");
        fprintf(fp, " OFFSET   LEN     ID NC DP FLG IDENT \"DATA\"\n");
    }

    fprintf(fp, "%6zu %6zu %6d %2d %2d %3s %*s%s \"%s\"\n",
        self->node->offset,
        self->node->length,
        self->node->def,
        self->node->num_children,
        depth,
        chpeg_flags(flags, self->node->flags),
        depth * 2, "",
        def_name ? def_name : "<N/A>",
        data ? data : "<NULL>"
        );

    if (data) { CHPEG_FREE(data); data = NULL; }
    for (ChpegPNode *p = self->head; p; p = p->next) {
        ChpegPNode_print(p, parser, input, depth + 1, fp);
    }

    if (depth == 0) {
        fprintf(fp, "PNODE END ---------------------------------- \n");
    }
}
#endif

#endif // #if CHPEG_PACKRAT

#if CHPEG_EXTENSION_REFS

#if CHPEG_UNDO
typedef struct _ChpegUndoMarkData {
    int ref_id;
    ChpegReferenceInfo value;
} ChpegUndoMarkData;

void chpeg_undo_mark(ChpegNode *node, void *_data)
{
    ChpegUndoMarkData *data = (ChpegUndoMarkData *)_data;
#if 0
    fprintf(stderr, "chpeg_undo_mark: <o:%zu l:%zu f:%d>\n",
        data->value.offset, data->value.length, data->value.flags);
#endif
    for (ChpegNode *p = node; p; p = p->parent) {
        if (p->flags & CHPEG_FLAG_REFSCOPE) {
            p->refs[data->ref_id] = data->value;
            break;
        }
    }
}

#endif
#endif

//
// ChpegParser
//

ChpegParser *ChpegParser_new(const ChpegByteCode *bc)
{
    ChpegParser *self = (ChpegParser *)CHPEG_CALLOC(1, sizeof(ChpegParser));

    self->bc = bc;
    self->tree_root = NULL;
    self->simplification = 1;
    self->max_tree_depth = CHPEG_MAX_TREE_DEPTH;
    self->max_stack_size = CHPEG_STACK_SIZE;
    self->error_offset = 0;
    self->errors = NULL;
    self->errors_size = 0;
    self->errors_capacity = 0;

#if CHPEG_VM_TRACE
    self->vm_trace = 0;
#endif
#if CHPEG_VM_PRINT_TREE
    self->vm_print_tree = 0;
#endif
#if CHPEG_VM_PROFILE
    self->vm_profile = 0;
    self->prof_inst_cnt = 0;
    self->prof_ident_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_isucc_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_ifail_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_choice_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_cisucc_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->prof_cifail_cnt = CHPEG_MALLOC(bc->num_defs * sizeof(int));
    self->farthest_backtrack = 0;
#endif
#if CHPEG_PACKRAT
    self->packrat = 0;
    self->packrat_window_size = 0;
#endif
    return self;
}

void ChpegParser_free(ChpegParser *self)
{
    if (self) {
        if (self->tree_root) {
            ChpegNode_free(self->tree_root);
            self->tree_root = NULL;
        }
#if ERRORS
        if (self->errors) {
            CHPEG_FREE(self->errors);
            self->errors = NULL;
            self->errors_capacity = 0;
            self->errors_size = 0;
        }
#endif
#if CHPEG_VM_PROFILE
        if (self->prof_ident_cnt) {
            CHPEG_FREE(self->prof_ident_cnt);
            self->prof_ident_cnt = NULL;
        }
        if (self->prof_isucc_cnt) {
            CHPEG_FREE(self->prof_isucc_cnt);
            self->prof_isucc_cnt = NULL;
        }
        if (self->prof_ifail_cnt) {
            CHPEG_FREE(self->prof_ifail_cnt);
            self->prof_ifail_cnt = NULL;
        }
        if (self->prof_choice_cnt) {
            CHPEG_FREE(self->prof_choice_cnt);
            self->prof_choice_cnt = NULL;
        }
        if (self->prof_cisucc_cnt) {
            CHPEG_FREE(self->prof_cisucc_cnt);
            self->prof_cisucc_cnt = NULL;
        }
        if (self->prof_cifail_cnt) {
            CHPEG_FREE(self->prof_cifail_cnt);
            self->prof_cifail_cnt = NULL;
        }
#endif
        CHPEG_FREE(self);
    }
}

void ChpegParser_print_tree(ChpegParser *self, const unsigned char *input, FILE *fp)
{
    ChpegNode_print(self->tree_root, self, input, 0, fp);
}

#if CHPEG_VM_PROFILE
void ChpegParser_print_profile(ChpegParser *self,
    const unsigned char *input, size_t length, FILE *fp)
{
    fprintf(fp, "Instructions executed:\n");
    fprintf(fp, "%6s %8s %11s %6s\n", "OP-", "opcode", "count", "%");
    for (int i = 0; i < CHPEG_NUM_OPS; ++i) {
        fprintf(fp, "%6s %8s %11d %6.2f\n", "OP ",
            Chpeg_op_name(i), self->prof_op_cnt[i],
            100.0 * (float)self->prof_op_cnt[i] / (float)self->prof_inst_cnt);
    }
    fprintf(fp, "%6s %8s %11d %6.2f\n", "OP=", "Total", self->prof_inst_cnt, 100.0);

    int total_ident = self->prof_op_cnt[CHPEG_OP_IDENT];
    int total_isucc = self->prof_op_cnt[CHPEG_OP_ISUCC];
    int total_ifail = self->prof_op_cnt[CHPEG_OP_IFAIL];

    fprintf(fp, "\n");
    fprintf(fp, "Definition identifier calls:\n");
    fprintf(fp, "  DEF-   id       IDENT      %%       ISUCC       IFAIL  name\n");
    for (int i = 0; i < self->bc->num_defs; ++i) {
        fprintf(fp, "%6s %4d %11d %6.2f %11d %11d  %s\n", "DEF ", i,
            self->prof_ident_cnt[i],
            100.0 * (float)self->prof_ident_cnt[i] / (float)total_ident,
            self->prof_isucc_cnt[i],
            self->prof_ifail_cnt[i],
            ChpegByteCode_def_name(self->bc, i));
    }
    fprintf(fp, "%6s %4s %11d %6.2f %11d %11d  %s\n", "DEF=", "--",
        total_ident, 100.0, total_isucc, total_ifail, "--");

    int total_choice = self->prof_op_cnt[CHPEG_OP_CHOICE];
    int total_cisucc = self->prof_op_cnt[CHPEG_OP_CISUCC];
    int total_cifail = self->prof_op_cnt[CHPEG_OP_CIFAIL];

    fprintf(fp, "\n");
    fprintf(fp, "Choice calls per definition:\n");
    fprintf(fp, "  CHOICE-  def      CHOICE      %%      CISUCC      CIFAIL  def_name\n");
    for (int i = 0; i < self->bc->num_defs; ++i) {
        fprintf(fp, "%9s %4d %11d %6.2f %11d %11d  %s\n", "CHOICE ", i,
            self->prof_choice_cnt[i],
            100.0 * (float)self->prof_choice_cnt[i] / (float)total_choice,
            self->prof_cisucc_cnt[i],
            self->prof_cifail_cnt[i],
            ChpegByteCode_def_name(self->bc, i));
    }
    fprintf(fp, "%9s %4s %11d %6.2f %11d %11d  %s\n", "CHOICE=", "--",
        total_choice, 100.0, total_cisucc, total_cifail, "--");

    fprintf(fp, "\nFarthest backtrack: %zu\n", self->farthest_backtrack);

    fprintf(fp, "\nInstructions executed: %d, instructions per input byte: %.2f\n",
        self->prof_inst_cnt, (float)self->prof_inst_cnt / (float)length);
}
#endif

void ChpegParser_expected(ChpegParser *self, size_t offset, int depth, int def, int pc)
{
    if (offset >= self->error_offset) {
        if (offset > self->error_offset) {
            self->error_offset = offset;
            self->errors_size = 0;
        }
        if (self->errors_size + 1 > self->errors_capacity) {
            if (!self->errors) {
                self->errors_capacity = 1;
                self->errors = CHPEG_MALLOC(self->errors_capacity * sizeof(ChpegErrorInfo));
            }
            else {
                self->errors_capacity *= 2;
            }
            self->errors = CHPEG_REALLOC(self->errors, self->errors_capacity * sizeof(ChpegErrorInfo));
        }
        self->errors[self->errors_size++] = (ChpegErrorInfo)
        {
            .depth = depth,
            .def = def,
            .pc = pc,
        };
    }
}

void ChpegParser_print_errors(ChpegParser *self, const unsigned char *input, int all)
{
#if ERRORS
    if (self->errors_size == 0) {
        fprintf(stderr, "No errors detected / tracked.\n");
        return;
    }

    assert(self->errors_size > 0);
    for (int i = all ? 0 : self->errors_size - 1; i < self->errors_size; ++i) {
        ChpegErrorInfo *error = &self->errors[i];
        const char *def_name = ChpegByteCode_def_name(self->bc, error->def);
        int inst = self->bc->instructions[error->pc];
        int op = inst & 0xff;
        int arg = inst >> 8;

        size_t line, col;
        char *esc = NULL;
        const char *str = NULL;
        int depth_indent = (error->depth - 1) *2;
        const char *expected = "Expected:";

        // if a predicate is followed by an instruction case we can display,
        // use that, switching to 'unexpected' for PREDN (predicate '!')
        // (otherwise, it'll fall through to the default 'syntax error' case below)
        if (op == CHPEG_OP_PREDN || op == CHPEG_OP_PREDA) {
            int next_inst = self->bc->instructions[error->pc + 1];
            switch (next_inst & 0xff) {
                case CHPEG_OP_IDENT:
                case CHPEG_OP_LIT:
                case CHPEG_OP_CHRCLS:
                case CHPEG_OP_DOT:
                    if (op == CHPEG_OP_PREDN) {
                        expected = "Unexpected:";
                    }
                    op = next_inst & 0xff;
                    arg = next_inst >> 8;
                    break;
            }
        }

        chpeg_line_col(input, self->error_offset, &line, &col);

        switch (op) {
            case CHPEG_OP_IDENT:
                str = ChpegByteCode_def_name(self->bc, arg);
                fprintf(stderr, "input:%zu:%zu: %11s %*s%s in %s\n",
                    line, col,
                    expected,
                    depth_indent, "",
                    str ? str : "<N/A>>",
                    def_name ? def_name : "<N/A>");
                break;
            case CHPEG_OP_LIT:
                esc = chpeg_esc_bytes((unsigned char *)self->bc->strings[arg],
                    self->bc->str_len[arg], 20);
                fprintf(stderr, "input:%zu:%zu: %11s %*s\"%s\" in %s\n",
                    line, col,
                    expected,
                    depth_indent, "",
                    esc ? esc : "<NULL>",
                    def_name ? def_name : "<N/A>");
                CHPEG_FREE(esc); esc = NULL;
                break;
            case CHPEG_OP_CHRCLS:
                esc = chpeg_esc_bytes((unsigned char *)self->bc->strings[arg],
                    self->bc->str_len[arg], 20);
                fprintf(stderr, "input:%zu:%zu: %11s %*s[%s] in %s\n",
                    line, col,
                    expected,
                    depth_indent, "",
                    esc ? esc : "<NULL>",
                    def_name ? def_name : "<N/A>");
                CHPEG_FREE(esc); esc = NULL;
                break;
            case CHPEG_OP_DOT:
                fprintf(stderr, "input:%zu:%zu: %11s %*scharacter in %s\n",
                    line, col,
                    expected,
                    depth_indent, "",
                    def_name ? def_name : "<N/A>");
                break;
            default: // unhandled op, show instruction in <> for debugging
                fprintf(stderr, "input:%zu:%zu: %11s %*sSyntax error in %s <%s,%d>\n",
                    line, col,
                    "Error:",
                    depth_indent, "",
                    def_name ? def_name : "<N/A>",
                    Chpeg_op_name(op), arg);
                break;
        }
    }
#else
    fprintf(stderr, "Error tracking disabled at compile time.\n");
#endif
}

void ChpegParser_print_error(ChpegParser *self, const unsigned char *input)
{
    ChpegParser_print_errors(self, input, 0);
}
{'fraction_non_alphanumeric': 0.13506737134508198, 'fraction_numerical': 0.007575894226086329, 'mean_word_length': 2.2970561998215877, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 817, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1719473', 'n_tokens_mistral': 19631, 'n_tokens_neox': 19102, 'n_words': 4305}