<|start_filename|>example/egg-lang/Makefile<|end_filename|>
egg: parser.h parser.o main.c
	cc -g -std=c99 -Os -o egg main.c parser.o

parser.o: parser.h parser.c
	cc -g -std=c99 -Os -c parser.c

parser.h: grammar.owl
	../../owl -c grammar.owl -o parser.h


<|start_filename|>src/grow-array.c<|end_filename|>
#include "grow-array.h"

#include "alloc.h"
#include <stdlib.h>
#include <string.h>

void *grow_array_using_realloc(void *a, uint32_t *size, size_t target_size)
{
    if (target_size > UINT32_MAX)
        abort();
    uint32_t n = *size;
    while (target_size > n) {
        uint32_t m = (n + 1) * 3 / 2;
        if (m < n)
            n = 0xffffffff;
        else
            n = m;
        if (n < 16)
            n = 16;
    }
    char *next_array = realloc(a, n);
    memset(next_array + *size, 0, n - *size);
    *size = n;
    return next_array;
}


<|start_filename|>example/calc/Makefile<|end_filename|>
calc: parser.h calc.c
	cc -g -std=c99 -Os -o calc calc.c -lreadline

parser.h: calc.owl
	../../owl -c calc.owl -o parser.h


<|start_filename|>src/automaton.c<|end_filename|>
#include "automaton.h"

#include "alloc.h"
#include "state-array.h"

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

static void state_add_transition(struct state *s, state_id target,
 symbol_id symbol, uint16_t action)
{
    if (s->number_of_transitions == 0xffff) {
        fprintf(stderr, "error: too many transitions for a single state\n");
        exit(-1);
    }
    uint16_t id = s->number_of_transitions++;
    s->transitions = grow_array(s->transitions, &s->transitions_allocated_bytes,
     (uint32_t)s->number_of_transitions * sizeof(struct transition));
    s->transitions[id] = (struct transition){
        .target = target,
        .symbol = symbol,
        .action = action,
    };
}

void automaton_add_transition(struct automaton *a, state_id source,
 state_id target, symbol_id symbol)
{
    automaton_add_transition_with_action(a, source, target, symbol, 0);
}

static void grow_states(struct automaton *a, uint32_t state)
{
    if (state < a->number_of_states)
        return;
    if (state >= 1UL << 31) {
        fprintf(stderr, "error: automaton has too many states\n");
        exit(-1);
    }
    a->number_of_states = (uint32_t)state + 1;
    a->states = grow_array(a->states, &a->states_allocated_bytes,
     a->number_of_states * sizeof(struct state));
}

void automaton_add_transition_with_action(struct automaton *a, state_id source,
 state_id target, symbol_id symbol, uint16_t action)
{
    automaton_invalidate_epsilon_closure(a);
    state_id max_state = source;
    if (target > source)
        max_state = target;
    grow_states(a, max_state);
    if (symbol != SYMBOL_EPSILON && symbol >= a->number_of_symbols)
        a->number_of_symbols = symbol + 1;
    state_add_transition(&a->states[source], target, symbol, action);
}

state_id automaton_create_state(struct automaton *a)
{
    state_id state = a->number_of_states;
    grow_states(a, state);
    return state;
}

void automaton_set_start_state(struct automaton *a, state_id state)
{
    grow_states(a, state);
    a->start_state = state;
}

void automaton_mark_accepting_state(struct automaton *a, state_id state)
{
    grow_states(a, state);
    a->states[state].accepting = true;
}

void automaton_reverse(struct automaton *a, struct automaton *reversed)
{
    state_id start_state = a->number_of_states;
    for (uint32_t i = 0; i < a->number_of_states; ++i) {
        struct state *s = &a->states[i];
        for (uint32_t j = 0; j < s->number_of_transitions; ++j) {
            struct transition *t = &s->transitions[j];
            automaton_add_transition_with_action(reversed, t->target, i,
             t->symbol, t->action);
        }
        if (s->accepting) {
            automaton_add_transition(reversed, start_state, i, SYMBOL_EPSILON);
            reversed->states[i].transition_symbol = s->transition_symbol;
        }
    }
    automaton_set_start_state(reversed, start_state);
    automaton_mark_accepting_state(reversed, a->start_state);
}

void automaton_print(struct automaton *a)
{
    printf("start = %u\n", a->start_state);
    for (uint32_t i = 0; i < a->number_of_states; ++i) {
        struct state *s = &a->states[i];
        if (s->accepting) {
            if (s->transition_symbol)
                printf("%4u   -- accept --> %x\n", i, s->transition_symbol);
            else
                printf("%4u   -- accept -->\n", i);
        }
        for (uint32_t j = 0; j < s->number_of_transitions; ++j) {
            struct transition *t = &s->transitions[j];
            if (t->symbol == SYMBOL_EPSILON)
                printf("%4u   ---------->%4u", i, t->target);
            else
                printf("%4u   - %4x   ->%4u", i, t->symbol, t->target);
            if (t->action != 0)
                printf(" (%x)\n", t->action);
            else
                printf("\n");
        }
    }
}

void automaton_copy(struct automaton *from, struct automaton *to)
{
    automaton_clear(to);
    automaton_set_start_state(to, from->start_state);
    for (uint32_t i = 0; i < from->number_of_states; ++i) {
        struct state *s = &from->states[i];
        grow_states(to, i);
        if (s->accepting)
            automaton_mark_accepting_state(to, i);
        to->states[i].transition_symbol = s->transition_symbol;
        for (uint32_t j = 0; j < s->number_of_transitions; ++j) {
            automaton_add_transition_with_action(to, i,
             s->transitions[j].target, s->transitions[j].symbol,
             s->transitions[j].action);
        }
    }

}

void automaton_move(struct automaton *from, struct automaton *to)
{
    automaton_destroy(to);
    *to = *from;
    memset(from, 0, sizeof(struct automaton));
}

void automaton_clear(struct automaton *a)
{
    automaton_invalidate_epsilon_closure(a);
    for (uint32_t i = 0; i < a->number_of_states; ++i)
        free(a->states[i].transitions);
    memset(a->states, 0, a->states_allocated_bytes);
    a->number_of_states = 0;
    a->number_of_symbols = 0;
    a->start_state = 0;
}

void automaton_destroy(struct automaton *a)
{
    automaton_clear(a);
    free(a->states);
    a->states = 0;
    a->states_allocated_bytes = 0;
}


<|start_filename|>src/6a-generate-output.c<|end_filename|>
#include "6a-generate-output.h"

#include "alloc.h"
#include "grow-array.h"
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

enum substitution_type {
    STRING,
    UNSIGNED_NUMBER,
    SIGNED_NUMBER,
};

struct substitution {
    // Zero-terminated.
    const char *variable;

    enum substitution_type type;
    uint32_t unsigned_number;
    int32_t signed_number;

    const char *value;
    size_t value_length;

    enum substitution_transform transform;
};

struct generator_output {
    void (*output)(const char *, size_t);

    struct substitution *substitutions;
    uint32_t substitutions_allocated_bytes;
    uint32_t number_of_substitutions;

    char *formatted_string;
    uint32_t formatted_string_allocated_bytes;
};

static void apply_transform(char *string, size_t length,
 enum substitution_transform transform);
static struct substitution *find_substitution(struct generator_output *output,
 const char *variable);

struct generator_output *output_create(void (*function)(const char *, size_t))
{
    struct generator_output *output = calloc(1, sizeof(*output));
    output->output = function;
    return output;
}

void output_destroy(struct generator_output *output)
{
    free(output->substitutions);
    free(output->formatted_string);
    free(output);
}

void output_string_length(struct generator_output *output, const char *string,
 size_t len)
{
    if (len == 0)
        return;
    size_t next_output_index = 0;
    char *format = output->formatted_string;
    uint32_t format_bytes = output->formatted_string_allocated_bytes;
    for (size_t i = 0; i < len - 1; ++i) {
        if (string[i] == '%' && string[i + 1] == '%') {
            struct substitution *s = find_substitution(output, string + i + 2);
            if (!s)
                abort();
            output->output(string + next_output_index, i - next_output_index);
            switch (s->type) {
            case UNSIGNED_NUMBER: {
                const char *f = "%u";
                if (s->unsigned_number > INT_MAX)
                    f = "%uU";
                int len = snprintf(0, 0, f, s->unsigned_number);
                format = grow_array(format, &format_bytes, (uint32_t)len + 1);
                snprintf(format, len + 1, f, s->unsigned_number);
                output->output(format, len);
                break;
            }
            case SIGNED_NUMBER: {
                int len = snprintf(0, 0, "%d", s->signed_number);
                format = grow_array(format, &format_bytes, (uint32_t)len + 1);
                snprintf(format, len + 1, "%d", s->signed_number);
                output->output(format, len);
                break;
            }
            case STRING:
                format = grow_array(format, &format_bytes, s->value_length);
                memcpy(format, s->value, s->value_length);
                apply_transform(format, s->value_length, s->transform);
                output->output(format, s->value_length);
                break;
            }
            next_output_index = i + 2 + strlen(s->variable);
        }
    }
    output->formatted_string = format;
    output->formatted_string_allocated_bytes = format_bytes;
    if (next_output_index < len)
        output->output(string + next_output_index, len - next_output_index);
}

void output_string(struct generator_output *output, const char *string)
{
    output_string_length(output, string, strlen(string));
}

void output_line(struct generator_output *output, const char *string)
{
    output_string(output, string);
    output_string(output, "\n");
}

void output_formatted_source(struct generator_output *output,
 const char *string)
{
    // This implements a very simple C source formatter.
    size_t next_output_index = 0;
    char quoted_string_char = 0;
    int indent = 0;
    size_t i = 0;
    for (; string[i]; ++i) {
        bool line_break_after = false;
        if (quoted_string_char) {
            if (string[i] == '\\') {
                i++;
                if (string[i] == '\0')
                    break;
            } else if (string[i] == quoted_string_char)
                quoted_string_char = 0;
            continue;
        }
        if (string[i] == ';' || string[i] == '{')
            line_break_after = true;
        else if (string[i] == '"' || string[i] == '\'')
            quoted_string_char = string[i];
        else if (string[i] == '}') {
            indent--;
            if (string[i + 1] != ';')
                line_break_after = true;
        } else if (string[i] == ':') {
            line_break_after = true;
            indent--;
        }
        if (line_break_after) {
            for (int j = 0; j < indent; ++j)
                output_string(output, "    ");
            output_string_length(output, string + next_output_index,
             i + 1 - next_output_index);
            output_string(output, "\n");
            if (string[i + 1] == ' ')
                next_output_index = i + 2;
            else
                next_output_index = i + 1;
        }
        if (string[i] == '{' || string[i] == ':')
            indent++;
    }
    output_string_length(output, string + next_output_index,
     i - next_output_index);
}

static uint32_t create_substitution(struct generator_output *output,
 const char *variable)
{
    uint32_t index = 0;
    for (; index < output->number_of_substitutions; ++index) {
        if (strcmp(variable, output->substitutions[index].variable) == 0)
            break;
    }
    if (index >= output->number_of_substitutions) {
        output->number_of_substitutions = index + 1;
        if (index == UINT32_MAX)
            abort();
        output->substitutions = grow_array(output->substitutions,
         &output->substitutions_allocated_bytes,
         output->number_of_substitutions * sizeof(struct substitution));
        output->substitutions[index].variable = variable;
    }
    return index;
}

void set_substitution(struct generator_output *output, const char *variable,
 const char *value, size_t value_length, enum substitution_transform transform)
{
    uint32_t index = create_substitution(output, variable);
    output->substitutions[index].type = STRING;
    output->substitutions[index].value = value;
    output->substitutions[index].value_length = value_length;
    output->substitutions[index].transform = transform;
}

void set_unsigned_number_substitution(struct generator_output *output,
 const char *variable, uint32_t value)
{
    uint32_t index = create_substitution(output, variable);
    output->substitutions[index].type = UNSIGNED_NUMBER;
    output->substitutions[index].unsigned_number = value;
}

void set_signed_number_substitution(struct generator_output *output,
 const char *variable, int32_t value)
{
    uint32_t index = create_substitution(output, variable);
    output->substitutions[index].type = SIGNED_NUMBER;
    output->substitutions[index].signed_number = value;
}

void set_literal_substitution(struct generator_output *output,
 const char *variable, const char *value)
{
    set_substitution(output, variable, value, strlen(value), NO_TRANSFORM);
}

static void apply_transform(char *string, size_t length,
 enum substitution_transform transform)
{
    if (transform == NO_TRANSFORM)
        return;
    for (size_t i = 0; i < length; ++i) {
        if (transform == UPPERCASE_WITH_UNDERSCORES && string[i] >= 'a'
         && string[i] <= 'z')
            string[i] = string[i] - 'a' + 'A';
        if (string[i] == '-')
            string[i] = '_';
    }
}

static struct substitution *find_substitution(struct generator_output *output,
 const char *variable)
{
    uint32_t n = output->number_of_substitutions;
    size_t longest_match = 0;
    struct substitution *longest_match_substitution = 0;
    for (uint32_t i = 0; i < n; ++i) {
        struct substitution *s = &output->substitutions[i];
        for (size_t j = 0; ; ++j) {
            if (s->variable[j] == 0 && j > longest_match) {
                longest_match = j;
                longest_match_substitution = s;
            }
            if (!s->variable[j] || s->variable[j] != variable[j])
                break;
        }
    }
    return longest_match_substitution;
}


<|start_filename|>src/1-parse.c<|end_filename|>
#define OWL_PARSER_IMPLEMENTATION
#include "1-parse.h"


<|start_filename|>src/6b-interpret-output.c<|end_filename|>
#include "6b-interpret-output.h"

#include "alloc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct range {
    uint32_t start;
    uint32_t end;
};

struct line {
    struct range *row_ranges;
    struct range offset_range;
    size_t end_offset;
    size_t end_offset_buffer;

    // This array must always be non-empty.
    size_t *offsets;
    uint32_t *rows_of_offsets;
    uint32_t offsets_capacity;

    bool has_overflow;
    bool is_overflow;

    struct terminal_info terminal_info;
    int32_t color_offset;
};

// This is how many dots we leave at the end of wrapped lines.
#define ELLIPSIS_COUNT 2
// This is how much space we leave for the dots at the end of wrapped lines.
#define ELLIPSIS_LENGTH (ELLIPSIS_COUNT + 1)
// The minimum allowed spacing between adjacent labels.
#define LABEL_PADDING 1
// This is how much space we leave for the "." at the beginning of each line.
#define LINE_MARKER_LENGTH 2
// The amount of space to add before a wrapped line.
#define LINE_WRAP_MARGIN 2
// If a label overflows to the next line, leave a minimum amount of space so the
// "-" is guaranteed to appear.
#define OVERFLOW_INDICATOR_MARGIN 1

static void output_line(FILE *file, struct line *line,
 struct document *document);
static void output_spacing(FILE *file, struct line *line, uint32_t row,
 size_t offset, uint32_t start_index, uint32_t end_index);
static bool advance_line(struct line *line, struct document *document);
static bool advance_label(struct line *line, struct document *document,
 uint32_t row, uint32_t label_index);

static void init_line(struct line *line, struct document *document);
static void destroy_line(struct line *line);
static void break_line(struct line *line, struct document *document);
static void copy_line(struct line *from, struct line *to,
 struct document *document);

static void push_offsets(struct line *line, uint32_t index, size_t target);

#define BEFORE_START (SIZE_MAX - 2)
#define PAST_END (SIZE_MAX - 1)
static size_t offset_at(struct line *line, uint32_t index);
static void expand_offset_range(struct line *line, uint32_t index);
static void ensure_offsets_capacity(struct line *line, uint32_t capacity);

static void set_color(FILE *file, struct line *line, uint32_t color);

void output_document(FILE *file, struct document *document,
 struct terminal_info terminal_info)
{
    struct line line = {0};
    struct line next_line = {0};
    struct line last_fit_line = {0};
    init_line(&line, document);
    init_line(&next_line, document);
    init_line(&last_fit_line, document);
    line.terminal_info = terminal_info;
    next_line.terminal_info = terminal_info;
    line.color_offset = document->color_offset;
    next_line.color_offset = document->color_offset;
    bool can_break_line = false;
    long columns = terminal_info.columns;
    while (true) {
        copy_line(&next_line, &line, document);
        if (!advance_line(&next_line, document)) {
            output_line(file, &line, document);
            break;
        }
        if (!can_break_line) {
            copy_line(&next_line, &last_fit_line, document);
            can_break_line = true;
            continue;
        }
        struct label *last_token = 0;
        struct range token_range = next_line.row_ranges[0];
        if (token_range.end > token_range.start)
            last_token = &document->rows[0].labels[token_range.end - 1];
        if (last_token && last_token->starts_with_newline) {
            // Break a line at a newline.
            output_line(file, &line, document);
            fputs("\n", file);
            copy_line(&line, &next_line, document);
            break_line(&next_line, document);
            can_break_line = false;
            continue;
        }

        size_t end = next_line.end_offset;
        if (last_token) {
            size_t offset = offset_at(&next_line, last_token->end);
            if (offset < BEFORE_START && offset + ELLIPSIS_LENGTH > end)
                end = offset + ELLIPSIS_LENGTH;
        }
        if (end + LINE_MARKER_LENGTH <= columns) {
            copy_line(&next_line, &last_fit_line, document);
            continue;
        }
        if (next_line.end_offset + LINE_MARKER_LENGTH <= columns)
            continue;
        // Break a line in the middle.
        copy_line(&last_fit_line, &line, document);
        size_t offset = offset_at(&line, line.offset_range.end - 1);
        if (offset < BEFORE_START && offset + ELLIPSIS_LENGTH > line.end_offset)
            line.end_offset = offset + ELLIPSIS_LENGTH;
        if (line.end_offset + LINE_MARKER_LENGTH > columns)
            line.end_offset = columns - LINE_MARKER_LENGTH;
        line.has_overflow = true;
        output_line(file, &line, document);
        copy_line(&line, &next_line, document);
        break_line(&next_line, document);
        next_line.offsets[0] = LINE_WRAP_MARGIN;
        next_line.end_offset = LINE_WRAP_MARGIN;
        next_line.is_overflow = true;
        can_break_line = false;
    }
    destroy_line(&line);
    destroy_line(&next_line);
    destroy_line(&last_fit_line);
}

static void output_line(FILE *file, struct line *line,
 struct document *document)
{
    for (uint32_t i = 0; i < document->number_of_rows; ++i) {
        struct range rr = line->row_ranges[i];
        if (rr.start == rr.end)
            continue;
        if (i == 0) {
            if (line->terminal_info.line_indicator)
                fputs(line->terminal_info.line_indicator, file);
            if (line->is_overflow) {
                // The second dot is drawn by output_spacing.
                fputs(" .", file);
            } else
                fputs(". ", file);
        } else
            fputs("  ", file);
        struct range r = line->offset_range;
        uint32_t index = r.start;
        size_t offset = 0;
        for (uint32_t j = rr.start; j < rr.end; ++j) {
            struct label l = document->rows[i].labels[j];
            if (l.start >= r.end)
                continue;
            if (l.start >= r.start) {
                // Output the actual text for this label.
                output_spacing(file, line, i, offset, index, l.start);
                index = l.start;
                offset = offset_at(line, index);
                set_color(file, line, l.color ? l.color : i);
                fwrite(l.text, 1, l.length, file);
                offset += l.length;
            } else
                set_color(file, line, i);
            size_t end_offset = offset_at(line, l.end);
            if (end_offset == BEFORE_START)
                continue;
            if (end_offset == PAST_END)
                end_offset = line->end_offset;
            while (offset < end_offset) {
                fputs("-", file);
                offset++;
            }
            index = l.end;
        }
        output_spacing(file, line, i, offset, index, r.end);
        if (line->terminal_info.reset)
            fputs(line->terminal_info.reset, file);
        fputs("\n", file);
    }
}

static void output_spacing(FILE *file, struct line *line, uint32_t row,
 size_t offset, uint32_t start_index, uint32_t end_index)
{
    uint32_t offset_row = 0;
    struct range r = line->offset_range;
    for (uint32_t i = start_index; i <= end_index; ++i) {
        if (i < r.start)
            continue;
        size_t end_offset = line->end_offset;
        if (i < r.end)
            end_offset = line->offsets[i - r.start];
        for (size_t j = offset; j < end_offset; ++j) {
            if (row != 0 && offset_row != 0) {
                set_color(file, line, offset_row);
                fputs("|", file);
                offset_row = 0;
            } else if (row == 0 &&
             ((line->has_overflow && j + ELLIPSIS_COUNT >= line->end_offset) ||
             (line->is_overflow && j == 0))) {
                if (line->terminal_info.line_indicator)
                    fputs(line->terminal_info.line_indicator, file);
                fputs(".", file);
            } else
                fputs(" ", file);
        }
        offset = end_offset;
        if (i < r.end && line->rows_of_offsets[i - r.start] > row)
            offset_row = line->rows_of_offsets[i - r.start];
    }
}

static bool advance_line(struct line *line, struct document *document)
{
    bool advanced = false;
    for (uint32_t i = 0; i < document->number_of_rows; ++i) {
        struct range rr = line->row_ranges[i];
        if (rr.start != rr.end) {
            struct label l = document->rows[i].labels[rr.end - 1];
            // When a label extends past the end of offset_range, its layout is
            // incomplete -- the end offset won't appear in the offsets array.
            // Check to see if we've reached the end of the label, and if we
            // have, we complete the layout here.
            if (l.end <= line->offset_range.end)
                advance_label(line, document, i, rr.end - 1);
        }
        if (rr.end == document->rows[i].number_of_labels)
            continue;
        if (advance_label(line, document, i, rr.end)) {
            line->row_ranges[i].end++;
            advanced = true;
        }
    }
    return advanced;
}

static bool advance_label(struct line *line, struct document *document,
 uint32_t row, uint32_t label_index)
{
    struct label l = document->rows[row].labels[label_index];
    if (l.end == line->offset_range.end || row == 0)
        expand_offset_range(line, l.end);
    struct range r = line->offset_range;
    if (l.start >= r.end)
        return false;
    size_t end_offset = 0;
    if (l.start >= r.start) {
        if (row > 0 && label_index > line->row_ranges[row].start) {
            // Apply minimum inter-label spacing.
            struct label prev = document->rows[row].labels[label_index - 1];
            if (prev.end >= r.start && prev.end < r.end) {
                push_offsets(line, l.start, offset_at(line, prev.end) +
                 + LABEL_PADDING);
            }
        }
        end_offset = offset_at(line, l.start) + l.length;
        if (line->rows_of_offsets[l.start - r.start] == 0 || (row > 0 &&
         row < line->rows_of_offsets[l.start - r.start]))
            line->rows_of_offsets[l.start - r.start] = row;
    } else
        end_offset = line->offsets[0] + 1;
    push_offsets(line, l.end, end_offset);
    return true;
}

static void init_line(struct line *line, struct document *document)
{
    memset(line, 0, sizeof(*line));
    line->row_ranges = calloc(1, sizeof(struct range) *
     document->number_of_rows);
    line->offset_range.end = 1;
    line->offsets_capacity = 1;
    line->offsets = calloc(1, sizeof(size_t));
    line->rows_of_offsets = calloc(1, sizeof(uint32_t));
}

static void destroy_line(struct line *line)
{
    free(line->row_ranges);
    free(line->offsets);
    free(line->rows_of_offsets);
    memset(line, 0, sizeof(*line));
}

static void break_line(struct line *line, struct document *document)
{
    for (uint32_t i = 0; i < document->number_of_rows; ++i) {
        struct row *row = &document->rows[i];
        while (line->row_ranges[i].start < row->number_of_labels &&
         row->labels[line->row_ranges[i].start].end < line->offset_range.end)
            line->row_ranges[i].start++;
    }
    line->rows_of_offsets[0] = line->rows_of_offsets[line->offset_range.end -
     line->offset_range.start - 1];
    line->offset_range.start = line->offset_range.end - 1;
    line->offset_range.end = line->offset_range.end;
    line->offsets[0] = 0;
    line->end_offset = 0;
    line->end_offset_buffer = 0;
    line->has_overflow = false;
    line->is_overflow = false;
}

static void copy_line(struct line *from, struct line *to,
 struct document *document)
{
    memcpy(to->row_ranges, from->row_ranges,
     sizeof(struct range) * document->number_of_rows);
    to->end_offset = from->end_offset;
    to->end_offset_buffer = from->end_offset_buffer;

    struct range r = from->offset_range;
    to->offset_range = r;
    ensure_offsets_capacity(to, r.end - r.start);
    memcpy(to->offsets, from->offsets, sizeof(size_t) * (r.end - r.start));
    memcpy(to->rows_of_offsets, from->rows_of_offsets,
     sizeof(uint32_t) * (r.end - r.start));

    to->is_overflow = from->is_overflow;
    to->has_overflow = from->has_overflow;
}

static void push_offsets(struct line *line, uint32_t index, size_t target)
{
    struct range r = line->offset_range;
    if (index < r.start)
        return;
    if (index >= r.end) {
        target += OVERFLOW_INDICATOR_MARGIN;
        if (target > line->end_offset) {
            line->end_offset_buffer += target - line->end_offset;
            line->end_offset = target;
        }
        return;
    }
    size_t offset = offset_at(line, index);
    if (target <= offset)
        return;
    for (uint32_t i = index; i < r.end; ++i)
        line->offsets[i - r.start] += target - offset;
    if (target - offset > line->end_offset_buffer) {
        line->end_offset += target - offset - line->end_offset_buffer;
        line->end_offset_buffer = 0;
    } else
        line->end_offset_buffer -= target - offset;
}

static size_t offset_at(struct line *line, uint32_t index)
{
    if (index < line->offset_range.start)
        return BEFORE_START;
    else if (index >= line->offset_range.end)
        return PAST_END;
    else
        return line->offsets[index - line->offset_range.start];
}

static void expand_offset_range(struct line *line, uint32_t index)
{
    struct range r = line->offset_range;
    if (index < r.end)
        return;
    ensure_offsets_capacity(line, index - r.start + 1);
    for (uint32_t i = line->offset_range.end; i < index + 1; ++i) {
        line->offsets[i - r.start] = line->offsets[i - r.start - 1];
        line->rows_of_offsets[i - r.start] = 0;
    }
    line->offset_range.end = index + 1;
}

void ensure_offsets_capacity(struct line *line, uint32_t capacity)
{
    if (capacity <= line->offsets_capacity)
        return;
    void *offsets = realloc(line->offsets,
     (size_t)capacity * sizeof(size_t) * 2);
    void *offset_rows = realloc(line->rows_of_offsets,
     (size_t)capacity * sizeof(uint32_t) * 2);
    line->offsets = offsets;
    line->rows_of_offsets = offset_rows;
    line->offsets_capacity = capacity * 2;
}

static void set_color(FILE *file, struct line *line, uint32_t color)
{
    const char **colors = line->terminal_info.row_colors;
    if (color == 0 || !colors)
        return;
    if (color == DEFAULT_COLOR) {
        if (line->terminal_info.reset) {
            fputs(line->terminal_info.reset, file);
            return;
        } else
            color = 1;
    }
    int32_t offset = line->color_offset;
    while (offset < 0)
        offset += line->terminal_info.number_of_row_colors;
    color += offset;
    fputs(colors[(color - 1) % line->terminal_info.number_of_row_colors], file);
}


<|start_filename|>src/5-determinize.c<|end_filename|>
#include "5-determinize.h"

#include "alloc.h"
#include "bitset.h"
#include "fnv.h"

// A subset_table is a hash table mapping subsets (represented as state arrays)
// to their state ids in the deterministic automaton.
struct subset_table {
    struct state_array **subsets;
    uint32_t *subset_hashes;
    state_id *subset_states;

    uint32_t available_size;
    uint32_t used_size;
};

// This function transfers ownership of the `subset` array to the subset table.
// If the array doesn't already appear in the table, it will be inserted.
// Returns the index of the subset in the table.
static uint32_t subset_table_adopt_subset(struct subset_table *table,
 struct state_array *subset, uint32_t hash, state_id subset_state);

static void subset_table_destroy(struct subset_table *table);

// The worklist stores a list of deterministic states (and their corresponding
// subsets) whose transitions have not yet been explored.
struct worklist {
    struct state_array **subsets;
    uint32_t subsets_allocated_bytes;

    state_id *subset_states;
    uint32_t subset_states_allocated_bytes;

    uint32_t number_of_subsets;
};

// Follows a single transition and (if `map` is nonzero) records the associated
// actions into the action map.
static void follow_subset_transition(struct automaton *a,
 state_id target_nfa_state, state_id nfa_state, state_id dfa_state,
 symbol_id nfa_symbol, symbol_id dfa_symbol, struct state_array *next_subset,
 struct action_map *map);

static void add_action_map_entry(struct action_map *map,
 struct action_map_entry entry);
static int compare_action_map_entries(const void *aa, const void *bb);

// Insert or look up the deterministic state id for a subset.  If a new state
// is created, `*next_state` will be incremented and the new state will be added
// to the worklist.
static state_id deterministic_state_for_subset(struct subset_table *table,
 struct worklist *worklist, struct state_array *states, state_id *next_state);

// Find the set of transition symbols corresponding to an accepting
// deterministic state.
static struct bitset transition_symbols_from_state(struct automaton *a,
 struct subset_table *subsets, uint32_t index);

static int compare_actions(const void *a, const void *b);
static int compare_entry_actions(const void *aa, const void *bb);

enum options {
    // We provide an option to ignore the start state in order to determinize
    // reversed automata -- otherwise Brzozowski's algorithm won't work.
    INCLUDE_START_STATE = 0,
    IGNORE_START_STATE = 1,

    // Mark the accepting states of a bracket automaton using the deterministic
    // transition symbols in `in_transitions`.
    MARK_ACCEPTING_BRACKET_STATES = 2,

    // Treat epsilon transitions with actions like symbols instead of like
    // epsilon transitions.  We use this when checking for ambiguity.
    DISAMBIGUATE = 4,
};

struct context {
    struct automaton *input;
    struct automaton *result;

    struct bracket_transitions in_transitions;
    struct bracket_transitions *out_transitions;
    symbol_id first_transition_symbol;

    struct action_map *action_map;

    enum options options;
};

static void determinize_automaton(struct context context)
{
    struct automaton *a = context.input;
    struct automaton *result = context.result;
    automaton_clear(result);
    struct bracket_transitions in_transitions = context.in_transitions;

    automaton_compute_epsilon_closure(a, (context.options & DISAMBIGUATE) ?
     IGNORE_ACTION_TRANSITIONS : FOLLOW_ACTION_TRANSITIONS);

    struct subset_table subsets = {0};
    struct worklist worklist = {0};

    state_id next_state = 0;
    struct state_array next_subset = {0};
    if (context.options & IGNORE_START_STATE) {
        // If we're producing an action map, we need to call
        // follow_subset_transition and include the start state.
        if (context.action_map)
            abort();
        state_array_push_array(&next_subset,
         &a->epsilon_closure_for_state[a->start_state].reachable);
    } else {
        follow_subset_transition(a, a->start_state, a->start_state, UINT32_MAX,
         SYMBOL_EPSILON, SYMBOL_EPSILON, &next_subset, context.action_map);
    }
    automaton_set_start_state(result, deterministic_state_for_subset(&subsets,
     &worklist, &next_subset, &next_state));

    symbol_id next_transition_symbol = context.first_transition_symbol;
    while (worklist.number_of_subsets > 0) {
#if 0
//        if (context.options & DISAMBIGUATE) {
        printf("worklist\n");
        for (uint32_t i = 0; i < worklist.number_of_subsets; ++i) {
            printf("%u (%p): ", worklist.subset_states[i], worklist.subsets[i]);
            for (uint32_t j = 0; j < worklist.subsets[i]->number_of_states; ++j) {
                printf("%u ", worklist.subsets[i]->states[j]);
            }
            printf("\n");
        }
        printf("end worklist\n");
//        }
#endif

        uint32_t worklist_index = --worklist.number_of_subsets;
        struct state_array *subset = worklist.subsets[worklist_index];
        state_id state = worklist.subset_states[worklist_index];

        for (state_id i = 0; i < subset->number_of_states; ++i) {
            if (a->states[subset->states[i]].accepting) {
                automaton_mark_accepting_state(result, state);
                break;
            }
        }

        // There are three kinds of transitions we potentially need to visit.
        // First, we visit normal symbol transitions.
        for (symbol_id symbol = 0; symbol < a->number_of_symbols; ++symbol) {
            if (symbol >= context.first_transition_symbol) {
                // We handle bracket symbols separately below.
                continue;
            }
            for (uint32_t i = 0; i < subset->number_of_states; ++i) {
                struct state s = a->states[subset->states[i]];
                for (uint32_t j = 0; j < s.number_of_transitions; ++j) {
                    struct transition transition = s.transitions[j];
                    if (transition.symbol != symbol)
                        continue;
                    follow_subset_transition(a, transition.target,
                     subset->states[i], state, symbol, symbol, &next_subset,
                     context.action_map);
                }
            }
            if (next_subset.number_of_states == 0)
                continue;
            state_id target = deterministic_state_for_subset(&subsets,
             &worklist, &next_subset, &next_state);
            automaton_add_transition(result, state, target, symbol);
        }

        // Next, we visit bracket symbol transitions.
        for (uint32_t n = 0; n < in_transitions.number_of_transitions; ++n) {
            struct bracket_transition t = in_transitions.transitions[n];
            for (uint32_t i = 0; i < subset->number_of_states; ++i) {
                struct state s = a->states[subset->states[i]];
                for (uint32_t j = 0; j < s.number_of_transitions; ++j) {
                    struct transition transition = s.transitions[j];
                    if (transition.symbol == SYMBOL_EPSILON)
                        continue;
                    if (!bitset_contains(&t.transition_symbols,
                     transition.symbol)) {
                        continue;
                    }
                    follow_subset_transition(a, transition.target,
                     subset->states[i], state, transition.symbol,
                     t.deterministic_transition_symbol, &next_subset,
                     context.action_map);
                }
            }
            if (next_subset.number_of_states == 0)
                continue;
            state_id target = deterministic_state_for_subset(&subsets,
             &worklist, &next_subset, &next_state);
            automaton_add_transition(result, state, target,
             t.deterministic_transition_symbol);
        }

        // Finally, if we're "disambiguating", we visit action transitions.
        if (context.options & DISAMBIGUATE) {
            // Collect all the actions that appear as successors.
            uint16_t *actions = 0;
            uint32_t actions_allocated_bytes = 0;
            uint32_t number_of_actions = 0;
            for (uint32_t i = 0; i < subset->number_of_states; ++i) {
                struct state s = a->states[subset->states[i]];
                for (uint32_t j = 0; j < s.number_of_transitions; ++j) {
                    struct transition transition = s.transitions[j];
                    if (transition.symbol != SYMBOL_EPSILON)
                        continue;
                    if (transition.action == 0)
                        continue;
                    uint32_t k = number_of_actions++;
                    if (k == UINT32_MAX)
                        abort();
                    actions = grow_array(actions, &actions_allocated_bytes,
                     sizeof(uint16_t) * number_of_actions);
                    actions[k] = transition.action;
                }
            }
            qsort(actions, number_of_actions, sizeof(uint16_t),
             compare_actions);
            // Traverse the list of actions, and build a transition for each
            // while ignoring duplicates.
            for (uint32_t n = 0; n < number_of_actions; ++n) {
                if (n > 0 && actions[n] == actions[n - 1])
                    continue;
                for (uint32_t i = 0; i < subset->number_of_states; ++i) {
                    struct state s = a->states[subset->states[i]];
                    for (uint32_t j = 0; j < s.number_of_transitions; ++j) {
                        struct transition transition = s.transitions[j];
                        if (transition.symbol != SYMBOL_EPSILON)
                            continue;
                        if (transition.action != actions[n])
                            continue;
                        follow_subset_transition(a, transition.target,
                         subset->states[i], state, transition.symbol,
                         transition.symbol, &next_subset, context.action_map);
                    }
                }
                if (next_subset.number_of_states == 0)
                    continue;
                state_id target = deterministic_state_for_subset(&subsets,
                 &worklist, &next_subset, &next_state);
                automaton_add_transition_with_action(result, state, target,
                 SYMBOL_EPSILON, actions[n]);
            }
            free(actions);
        }
    }

    for (uint32_t i = 0; i < subsets.available_size; ++i) {
        if (!subsets.subsets[i])
            continue;
        struct state *state = &result->states[subsets.subset_states[i]];
        if (!state->accepting)
            continue;

        if (context.out_transitions) {
            struct bracket_transitions *ts = context.out_transitions;
            uint32_t j = ts->number_of_transitions++;
            if (j == UINT32_MAX)
                abort();
            ts->transitions = grow_array(ts->transitions,
             &ts->transitions_allocated_bytes, ts->number_of_transitions *
             sizeof(struct bracket_transition));
            state->transition_symbol = next_transition_symbol++;
            ts->transitions[j].deterministic_transition_symbol =
             state->transition_symbol;
            ts->transitions[j].transition_symbols =
             transition_symbols_from_state(a, &subsets, i);
        }
        if (context.options & MARK_ACCEPTING_BRACKET_STATES) {
            struct bitset s = transition_symbols_from_state(a, &subsets, i);
            uint32_t j;
            for (j = 0; j < in_transitions.number_of_transitions; ++j) {
                struct bracket_transition t = in_transitions.transitions[j];
                if (bitset_compare(&t.transition_symbols, &s))
                    continue;
                state->transition_symbol = t.deterministic_transition_symbol;
                break;
            }
            bitset_destroy(&s);
        }
    }

    // Clean up memory.
    free(worklist.subsets);
    free(worklist.subset_states);
    memset(&worklist, 0, sizeof(worklist));
    state_array_destroy(&next_subset);
    subset_table_destroy(&subsets);

    // Remove unreachable action map transitions.
    if (context.action_map) {
        struct action_map *map = context.action_map;
        qsort(map->entries, map->number_of_entries,
         sizeof(struct action_map_entry), compare_action_map_entries);

        struct state_array worklist = {0};
        struct bitset reachable = bitset_create_empty(a->number_of_states);
        for (state_id i = 0; i < a->number_of_states; ++i) {
            if (!a->states[i].accepting)
                continue;
            bitset_add(&reachable, i);
            state_array_push(&worklist, i);
        }
        while (worklist.number_of_states > 0) {
            state_id state = worklist.states[--worklist.number_of_states];
            uint32_t n = map->number_of_entries;
            struct action_map_entry *end = map->entries + n;
            struct action_map_entry *entry = map->entries;
            struct action_map_entry target = { .target_nfa_state = state };
            while (n > 0) {
                struct action_map_entry *a = entry + n / 2;
                if (compare_action_map_entries(a, &target) < 0) {
                    entry = a + 1;
                    n -= n / 2 + 1;
                } else
                    n /= 2;
            }
            for (; entry < end && entry->target_nfa_state == state; ++entry) {
                if (bitset_contains(&reachable, entry->nfa_state))
                    continue;
                bitset_add(&reachable, entry->nfa_state);
                state_array_push(&worklist, entry->nfa_state);
            }
        }
        uint32_t n = map->number_of_entries;
        uint32_t removed = 0;
        for (uint32_t i = 0; i < n; ++i) {
            if (bitset_contains(&reachable, map->entries[i].target_nfa_state))
                map->entries[i - removed] = map->entries[i];
            else
                removed++;
        }
        map->number_of_entries -= removed;
        bitset_destroy(&reachable);
        state_array_destroy(&worklist);
    }
}

static int compare_state_ids(const void *aa, const void *bb);
static int compare_bracket_transitions(const void *aa, const void *bb);
static bool equal_bracket_transitions(struct bracket_transitions *a,
 struct bracket_transitions *b);
static void bracket_transitions_destroy(struct bracket_transitions *);

static void follow_subset_transition(struct automaton *a,
 state_id target_nfa_state, state_id nfa_state, state_id dfa_state,
 symbol_id nfa_symbol, symbol_id dfa_symbol, struct state_array *next_subset,
 struct action_map *map)
{
    struct epsilon_closure *closure;
    closure = &a->epsilon_closure_for_state[target_nfa_state];
    struct state_array *reachable = &closure->reachable;
    if (!map) {
        state_array_push(next_subset, target_nfa_state);
        state_array_push_array(next_subset, reachable);
        return;
    }

    state_array_push(next_subset, target_nfa_state);
    add_action_map_entry(map, (struct action_map_entry){
        .dfa_state = dfa_state,
        .nfa_state = nfa_state,
        .target_nfa_state = target_nfa_state,
        .dfa_symbol = dfa_symbol,
        .nfa_symbol = nfa_symbol,
    });
    for (uint32_t i = 0; i < reachable->number_of_states; ++i) {
        state_array_push(next_subset, closure->reachable.states[i]);
        add_action_map_entry(map, (struct action_map_entry){
            .dfa_state = dfa_state,
            .nfa_state = nfa_state,
            .target_nfa_state = closure->reachable.states[i],
            .dfa_symbol = dfa_symbol,
            .nfa_symbol = nfa_symbol,
            .actions = closure->actions + closure->action_indexes[i],
        });
    }
}

static void add_action_map_entry(struct action_map *map,
 struct action_map_entry entry)
{
    uint32_t index = map->number_of_entries++;
    if (index == UINT32_MAX)
        abort();
    map->entries = grow_array(map->entries, &map->entries_allocated_bytes,
     sizeof(struct action_map_entry) * map->number_of_entries);
    map->entries[index] = entry;
}

static int compare_action_map_entries(const void *aa, const void *bb)
{
    const struct action_map_entry *a = aa;
    const struct action_map_entry *b = bb;
#define COMPARE(field) \
    if (a->field < b->field) \
        return -1; \
    if (a->field > b->field) \
        return 1;
    COMPARE(target_nfa_state);
    COMPARE(dfa_state);
    COMPARE(dfa_symbol);
#undef COMPARE
    return 0;
}

static state_id deterministic_state_for_subset(struct subset_table *table,
 struct worklist *worklist, struct state_array *states, state_id *next_state)
{
    struct state_array *subset = calloc(1, sizeof(struct state_array));
    *subset = state_array_move(states);

    // Sort the state set and remove duplicates for hashing and comparison.
    uint32_t n = subset->number_of_states;
    qsort(subset->states, n, sizeof(state_id), compare_state_ids);
    uint32_t removed = 0;
    for (uint32_t i = 1; i < n; ++i) {
        if (subset->states[i] == subset->states[i - 1])
            removed++;
        else if (removed > 0)
            subset->states[i - removed] = subset->states[i];
    }
    subset->number_of_states -= removed;

    // Hash the subset and place it into the table.
    uint32_t hash = fnv(subset->states,
     subset->number_of_states * sizeof(state_id));
    uint32_t idx = subset_table_adopt_subset(table, subset, hash, *next_state);

    if (table->subset_states[idx] == *next_state) {
        // This is a brand new state: insert it into the worklist so we can
        // continue to add its successor states.
        uint32_t i = worklist->number_of_subsets++;
        if (i == UINT32_MAX)
            abort();
        worklist->subsets = grow_array(worklist->subsets,
         &worklist->subsets_allocated_bytes,
         worklist->number_of_subsets * sizeof(struct state_array *));
        worklist->subset_states = grow_array(worklist->subset_states,
         &worklist->subset_states_allocated_bytes,
         worklist->number_of_subsets * sizeof(state_id));
        worklist->subsets[i] = table->subsets[idx];
        worklist->subset_states[i] = *next_state;
        (*next_state)++;
    }
    return table->subset_states[idx];
}

static void find_bracket_transitions(struct context context,
 struct bracket_transitions *result)
{
    struct automaton a = {0};
    struct bracket_transitions transitions = {0};
    context.result = &a;
    context.out_transitions = result;
    while (true) {
        context.in_transitions = transitions;
        determinize_automaton(context);
        qsort(result->transitions, result->number_of_transitions,
         sizeof(struct bracket_transition), compare_bracket_transitions);
        if (equal_bracket_transitions(&transitions, result))
            break;
#if 0
        printf("-\n");
        for (uint32_t i = 0; i < result->number_of_transitions; ++i) {
            struct bracket_transition t = result->transitions[i];
            printf("%x: ", t.deterministic_transition_symbol);
            for (uint32_t j = 0; j < t.transition_symbols.number_of_elements; ++j) {
                if (bitset_contains(&t.transition_symbols, j))
                    printf("%x ", j);
            }
            printf("\n");
        }
#endif
        bracket_transitions_destroy(&transitions);
        transitions = *result;
        *result = (struct bracket_transitions){0};
    }
    bracket_transitions_destroy(&transitions);
    automaton_destroy(&a);
}

void disambiguate(struct automaton *input, struct automaton *input_bracket,
 struct automaton *result, struct automaton *result_bracket,
 symbol_id first_bracket_transition_symbol)
{
    struct bracket_transitions transitions = {0};
    find_bracket_transitions((struct context){
        .input = input_bracket,
        .first_transition_symbol = first_bracket_transition_symbol,
        .options = DISAMBIGUATE,
    }, &transitions);

    // FIXME: Minimize! (how?)
    determinize_automaton((struct context){
        .input = input,
        .result = result,
        .in_transitions = transitions,
        .first_transition_symbol = first_bracket_transition_symbol,
        .options = DISAMBIGUATE,
    });
    determinize_automaton((struct context){
        .input = input_bracket,
        .result = result_bracket,
        .in_transitions = transitions,
        .first_transition_symbol = first_bracket_transition_symbol,
        .options = MARK_ACCEPTING_BRACKET_STATES | DISAMBIGUATE,
    });
    bracket_transitions_destroy(&transitions);
}

void determinize(struct combined_grammar *grammar,
 struct deterministic_grammar *result)
{
    find_bracket_transitions((struct context){
        .input = &grammar->bracket_automaton,
        .first_transition_symbol = grammar->number_of_tokens,
    }, &result->transitions);
    struct action_map *action_map = &result->action_map;
    determinize_automaton((struct context){
        .input = &grammar->automaton,
        .result = &result->automaton,
        .in_transitions = result->transitions,
        .first_transition_symbol = grammar->number_of_tokens,
        .action_map = action_map,
    });
    struct action_map *bracket_action_map = &result->bracket_action_map;
    determinize_automaton((struct context){
        .input = &grammar->bracket_automaton,
        .result = &result->bracket_automaton,
        .in_transitions = result->transitions,
        .first_transition_symbol = grammar->number_of_tokens,
        .action_map = bracket_action_map,
        .options = MARK_ACCEPTING_BRACKET_STATES,
    });

    // De-duplicate actions and copy them into a single array.
    uint32_t number_of_entries = action_map->number_of_entries +
     bracket_action_map->number_of_entries;
    struct action_map_entry **entries = calloc(number_of_entries,
     sizeof(struct action_map_entry *));
    uint32_t *action_indexes = calloc(number_of_entries, sizeof(uint32_t));
    for (int i = 0; i < 2; ++i) {
        struct action_map *map = i == 0 ? action_map : bracket_action_map;
        uint32_t offset = i == 0 ? 0 : action_map->number_of_entries;
        for (uint32_t j = 0; j < map->number_of_entries; ++j)
            entries[offset + j] = &map->entries[j];
    }
    qsort(entries, number_of_entries, sizeof(struct action_map_entry *),
     compare_entry_actions);
    uint32_t result_actions_allocated_bytes = 0;
    result->number_of_actions = 1;
    result->actions = grow_array(result->actions,
     &result_actions_allocated_bytes, sizeof(uint16_t) *
     result->number_of_actions);
    result->actions[0] = 0;
    for (uint32_t i = 0; i < number_of_entries; ++i) {
        if (i > 0 && compare_entry_actions(&entries[i], &entries[i - 1]) == 0)
            action_indexes[i] = action_indexes[i - 1];
        else if (entries[i]->actions) {
            action_indexes[i] = result->number_of_actions;
            uint16_t *a = entries[i]->actions;
            uint32_t n = 0;
            for (; a[n]; n++);
            n++; // Include terminating zero.
            if (n == 0 || result->number_of_actions + n < n)
                abort();
            result->number_of_actions += n;
            result->actions = grow_array(result->actions,
             &result_actions_allocated_bytes, sizeof(uint16_t) *
             result->number_of_actions);
            memcpy(result->actions + action_indexes[i], entries[i]->actions,
             sizeof(uint16_t) * n);
        } else
            action_indexes[i] = 0;
    }
    for (uint32_t i = 0; i < number_of_entries; ++i)
        entries[i]->actions = result->actions + action_indexes[i];
    free(action_indexes);
    free(entries);

    // Fill in the bracket_reachability array.
    uint32_t n = result->bracket_automaton.number_of_states;
    result->bracket_reachability = calloc(n, sizeof(struct bitset));
    for (uint32_t i = 0; i < n; ++i) {
        result->bracket_reachability[i] =
         bitset_create_empty(result->transitions.number_of_transitions);
    }
    struct automaton reversed = {0};
    automaton_reverse(&result->bracket_automaton, &reversed);
    struct bracket_transitions ts = result->transitions;
    struct state_array worklist = {0};
    for (state_id i = 0; i < result->bracket_automaton.number_of_states; ++i) {
        if (!result->bracket_automaton.states[i].accepting)
            continue;
        for (uint32_t j = 0; j < ts.number_of_transitions; ++j) {
            if (ts.transitions[j].deterministic_transition_symbol !=
             result->bracket_automaton.states[i].transition_symbol)
                continue;
            bitset_add(&result->bracket_reachability[i], j);
            state_array_push(&worklist, i);
            break;
        }
    }
    while (worklist.number_of_states > 0) {
        state_id state = state_array_pop(&worklist);
        struct bitset set = result->bracket_reachability[state];
        struct state s = reversed.states[state];
        for (uint32_t i = 0; i < s.number_of_transitions; ++i) {
            state_id next = s.transitions[i].target;
            if (bitset_union_added(&result->bracket_reachability[next], &set))
                state_array_push(&worklist, next);
        }
    }
    state_array_destroy(&worklist);
    automaton_destroy(&reversed);
}

static void action_map_destroy(struct action_map *map)
{
    free(map->entries);
    memset(map, 0, sizeof(*map));
}

void deterministic_grammar_destroy(struct deterministic_grammar *grammar)
{
    for (uint32_t i = 0; i < grammar->bracket_automaton.number_of_states; ++i)
        bitset_destroy(&grammar->bracket_reachability[i]);
    free(grammar->bracket_reachability);
    free(grammar->actions);
    automaton_destroy(&grammar->automaton);
    automaton_destroy(&grammar->bracket_automaton);
    action_map_destroy(&grammar->action_map);
    action_map_destroy(&grammar->bracket_action_map);
    bracket_transitions_destroy(&grammar->transitions);
    memset(grammar, 0, sizeof(*grammar));
}

struct action_map_entry *action_map_find(struct action_map *map,
 state_id target_nfa_state, state_id dfa_state, symbol_id dfa_symbol)
{
    struct action_map_entry query = {
        .target_nfa_state = target_nfa_state,
        .dfa_state = dfa_state,
        .dfa_symbol = dfa_symbol,
    };
    return bsearch(&query, map->entries, map->number_of_entries,
     sizeof(struct action_map_entry), compare_action_map_entries);
}

// This is Brzozowski's algorithm.
static void determinize_minimize_with_options(struct automaton *input,
 struct automaton *result, enum options options)
{
    struct automaton reversed = {0};
    struct automaton dfa = {0};
    automaton_reverse(input, &reversed);
    determinize_automaton((struct context){ .input = &reversed, .result = &dfa,
     .first_transition_symbol = UINT32_MAX, .options = IGNORE_START_STATE |
     options });
    automaton_clear(&reversed);
    automaton_reverse(&dfa, &reversed);
    determinize_automaton((struct context){ .input = &reversed,
     .result = result, .first_transition_symbol = UINT32_MAX,
     .options = IGNORE_START_STATE | options });
    automaton_destroy(&reversed);
    automaton_destroy(&dfa);
}

void determinize_minimize(struct automaton *input, struct automaton *result)
{
    determinize_minimize_with_options(input, result, 0);
}

void disambiguate_minimize(struct automaton *input, struct automaton *result)
{
    determinize_minimize_with_options(input, result, DISAMBIGUATE);
}

static uint32_t subset_table_adopt_subset(struct subset_table *table,
 struct state_array *subset, uint32_t hash, state_id subset_state)
{
    if (3 * table->available_size <= 4 * (table->used_size + 1)) {
        // The table is too small to comfortably fit another element.  Double
        // its size and reinsert all entries at their new positions.
        struct subset_table old = *table;
        uint32_t n = old.available_size * 2;
        if (n == 0)
            n = 256;
        table->subsets = calloc(n, sizeof(struct state_array *));
        table->subset_hashes = calloc(n, sizeof(uint32_t));
        table->subset_states = calloc(n, sizeof(state_id));
        table->available_size = n;
        table->used_size = 0;
        for (uint32_t i = 0; i < old.available_size; ++i) {
            if (!old.subsets[i])
                continue;
            subset_table_adopt_subset(table, old.subsets[i],
             old.subset_hashes[i], old.subset_states[i]);
        }
        free(old.subsets);
        free(old.subset_hashes);
        free(old.subset_states);
    }

    // Find the index for our subset.  If the subset is already there, just
    // return the index.  Otherwise, insert it and return the index of the
    // newly-inserted subset.
    uint32_t mask = table->available_size - 1;
    uint32_t index = hash & mask;
    while (true) {
        if (table->subsets[index] == 0) {
            // We found an empty slot.  Insert the subset here.
            table->subsets[index] = subset;
            table->subset_hashes[index] = hash;
            table->subset_states[index] = subset_state;
            table->used_size++;
            return index;
        }

        // Check whether this slot contains our subset.
        if (table->subset_hashes[index] != hash)
            goto skip;
        struct state_array *key = table->subsets[index];
        if (subset->number_of_states != key->number_of_states)
            goto skip;
        uint32_t n = subset->number_of_states;
        for (uint32_t i = 0; i < n; ++i) {
            if (subset->states[i] != key->states[i])
                goto skip;
        }

        // If we got here, we've found the subset we're looking for.  This
        // function adopts the `subset` array, so we need to free it before
        // returning.
        state_array_destroy(subset);
        free(subset);
        return index;

    skip:
        index = (index + 1) & mask;

        // We've looped all the way around the hash table.  Abort instead of
        // continuing to loop indefinitely.
        if (index == (hash & mask))
            abort();
    }
}

static void subset_table_destroy(struct subset_table *table)
{
    for (uint32_t i = 0; i < table->available_size; ++i) {
        if (table->subsets[i]) {
            state_array_destroy(table->subsets[i]);
            free(table->subsets[i]);
        }
    }
    free(table->subsets);
    free(table->subset_hashes);
    free(table->subset_states);
    memset(table, 0, sizeof(*table));
}

static int compare_state_ids(const void *aa, const void *bb)
{
    state_id a = *(state_id *)aa;
    state_id b = *(state_id *)bb;
    if (a < b)
        return -1;
    if (a > b)
        return 1;
    return 0;
}

static struct bitset transition_symbols_from_state(struct automaton *a,
 struct subset_table *subsets, uint32_t index)
{
    struct bitset symbols = bitset_create_empty(a->number_of_symbols);
    struct state_array *subset = subsets->subsets[index];
    for (uint32_t i = 0; i < subset->number_of_states; ++i) {
        struct state s = a->states[subset->states[i]];
        if (!s.accepting)
            continue;
        bitset_add(&symbols, s.transition_symbol);
    }
    return symbols;
}

static int compare_actions(const void *a, const void *b)
{
    return *(const uint16_t *)a - *(const uint16_t *)b;
}

static int compare_entry_actions(const void *aa, const void *bb)
{
    uint16_t *a = (*(struct action_map_entry * const *)aa)->actions;
    uint16_t *b = (*(struct action_map_entry * const *)bb)->actions;
    if (a == b)
        return 0;
    if (!a && b)
        return -1;
    if (a && !b)
        return 1;
    while (*a && *b) {
        if (*a < *b)
            return -1;
        if (*a > *b)
            return 1;
        a++;
        b++;
    }
    if (!*a && *b)
        return -1;
    if (*a && !*b)
        return 1;
    return 0;
}

static int compare_bracket_transitions(const void *aa, const void *bb)
{
    struct bitset *a = &((struct bracket_transition *)aa)->transition_symbols;
    struct bitset *b = &((struct bracket_transition *)bb)->transition_symbols;
    return bitset_compare(a, b);
}

static bool equal_bracket_transitions(struct bracket_transitions *a,
 struct bracket_transitions *b)
{
    if (a->number_of_transitions != b->number_of_transitions)
        return false;
    uint32_t n = a->number_of_transitions;
    for (uint32_t i = 0; i < n; ++i) {
        if (compare_bracket_transitions(&a->transitions[i], &b->transitions[i]))
            return false;
    }
    return true;
}

static void bracket_transitions_destroy(struct bracket_transitions *transitions)
{
    for (uint32_t i = 0; i < transitions->number_of_transitions; ++i)
        bitset_destroy(&transitions->transitions[i].transition_symbols);
    free(transitions->transitions);
    memset(transitions, 0, sizeof(*transitions));
}


<|start_filename|>example/calc/calc.c<|end_filename|>
#define OWL_PARSER_IMPLEMENTATION
#include "parser.h"

#include <readline/history.h>
#include <readline/readline.h>
#include <stdio.h>

struct binding {
    struct binding *next;
    char *name;
    size_t name_length;
    double value;
};
static struct binding *bindings;
static double eval(struct owl_ref ref);
static struct binding *lookup(struct parsed_identifier id);

int main()
{
    while (true) {
        char *s = readline("> ");
        if (!s)
            break;
        if (*s)
            add_history(s);
        struct owl_tree *tree = owl_tree_create_from_string(s);
        if (owl_tree_get_error(tree, NULL) != ERROR_NONE) {
            printf("parse error.\n");
            owl_tree_destroy(tree);
            continue;
        }
        struct parsed_command cmd = owl_tree_get_parsed_command(tree);
        double n = eval(cmd.expression);
        if (cmd.type == PARSED_ASSIGN) {
            struct parsed_identifier id = parsed_identifier_get(cmd.identifier);
            struct binding *b = lookup(id);
            if (!b) {
                b = malloc(sizeof(struct binding));
                b->name = malloc(id.length);
                memcpy(b->name, id.identifier, id.length);
                b->name_length = id.length;
                b->next = bindings;
                bindings = b;
            } else
                printf("%g -> ", b->value);
            b->value = n;
        }
        printf("%g\n", n);
        owl_tree_destroy(tree);
    }
    return 0;
}

static double eval(struct owl_ref ref)
{
    struct parsed_expression expr = parsed_expression_get(ref);
    switch (expr.type) {
    case PARSED_VARIABLE: {
        struct parsed_identifier id = parsed_identifier_get(expr.identifier);
        struct binding *b = lookup(id);
        if (b)
            return b->value;
        printf("'%.*s' not set\n", (int)id.length, id.identifier);
        return 0;
    }
    case PARSED_NUMBER:
        return parsed_number_get(expr.number).number;
    case PARSED_PARENS:
        return eval(expr.expression);
    case PARSED_NEGATE:
        return -eval(expr.operand);
    case PARSED_MULTIPLY:
        return eval(expr.left) * eval(expr.right);
    case PARSED_DIVIDE:
        return eval(expr.left) / eval(expr.right);
    case PARSED_ADD:
        return eval(expr.left) + eval(expr.right);
    case PARSED_SUBTRACT:
        return eval(expr.left) - eval(expr.right);
    default:
        return 0;
    }
}

static struct binding *lookup(struct parsed_identifier id)
{
    for (struct binding *b = bindings; b; b = b->next) {
        if (b->name_length == id.length &&
         !memcmp(b->name, id.identifier, id.length))
            return b;
    }
    return NULL;
}


<|start_filename|>src/bitset.c<|end_filename|>
#include "bitset.h"

#include "alloc.h"

struct bitset bitset_create_empty(uint32_t number_of_elements)
{
    uint32_t number_of_groups = (number_of_elements + 63) / 64;
    return (struct bitset){
        .bit_groups = calloc(number_of_groups, sizeof(uint64_t)),
        .number_of_bit_groups = number_of_groups,
        .number_of_elements = number_of_elements,
    };
}

void bitset_clear(struct bitset *set)
{
    for (uint32_t i = 0; i < set->number_of_bit_groups; ++i)
        set->bit_groups[i] = 0;
}

void bitset_destroy(struct bitset *set)
{
    free(set->bit_groups);
}

void bitset_union(struct bitset *set, struct bitset *other)
{
    if (set->number_of_elements != other->number_of_elements)
        abort();
    for (uint32_t i = 0; i < set->number_of_bit_groups; ++i)
        set->bit_groups[i] |= other->bit_groups[i];
}

bool bitset_intersects(struct bitset *set, struct bitset *other)
{
    if (set->number_of_elements != other->number_of_elements)
        abort();
    uint32_t hits = 0;
    for (uint32_t i = 0; i < set->number_of_bit_groups; ++i) {
        if (set->bit_groups[i] & other->bit_groups[i])
            hits++;
    }
    return hits > 0;
}

bool bitset_union_added(struct bitset *set, struct bitset *other)
{
    if (set->number_of_elements != other->number_of_elements)
        abort();
    bool added = false;
    for (uint32_t i = 0; i < set->number_of_bit_groups; ++i) {
        uint64_t group = set->bit_groups[i];
        group |= other->bit_groups[i];
        if (group == set->bit_groups[i])
            continue;
        set->bit_groups[i] = group;
        added = true;
    }
    return added;
}

bool bitset_is_empty(struct bitset *set)
{
    for (uint32_t i = 0; i < set->number_of_bit_groups; ++i) {
        if (set->bit_groups[i] != 0)
            return false;
    }
    return true;
}

int bitset_compare(struct bitset *a, struct bitset *b)
{
    if (a->number_of_elements != b->number_of_elements)
        abort();
    uint32_t n = a->number_of_bit_groups;
    for (uint32_t i = 0; i < n; ++i) {
        if (a->bit_groups[i] < b->bit_groups[i])
            return -1;
        if (a->bit_groups[i] > b->bit_groups[i])
            return 1;
    }
    return 0;
}


<|start_filename|>src/4-check-for-ambiguity.c<|end_filename|>
#include "4-check-for-ambiguity.h"

#include "alloc.h"
#include "bitset.h"
#include "fnv.h"
#include <assert.h>

// The goal of ambiguity checking is to find one of two things:
// 1. An "intrinsically ambiguous" pair of paths between two states.  That is,
//  - two different epsilon-transition paths between the same two states,
//  - two different bracket transitions whose corresponding accepting states are
//    reachable along paths with the same symbols, or
//  - a single bracket transition whose accepting state is itself part of an
//    ambiguous path.
// or
// 2. A pair of distinct states which can be reached along paths following the
//    same input.
//
// We search the product automaton, looking for either of these two cases.  The
// "disambiguation" procedure we did in the combine step ensures that different
// paths through the automaton have distinguishable sequences of actions.  If we
// find a path in the product automaton with a pair of distinct states, we have
// two different paths in the original automaton, and therefore two
// distinguishable sequences of actions for the same input -- an ambiguity.

enum epsilon_state {
    ALLOW_EPSILON_SUCCESSORS,
    DISALLOW_EPSILON_SUCCESSORS,
};
// The `epsilon_state` field implements the "epsilon filtering" technique by
// Allauzen et al. (2011), simplified a little bit because we follow an entire
// path at once.
//
//  <NAME>., <NAME>., & <NAME>. (2011). General Algorithms for
//  Testing the Ambiguity of Finite Automata and the Double-Tape Ambiguity of
//  Finite-State Transducers. Int. J. Found. Comput. Sci., 22, 883-904.
struct state_pair {
    state_id b;
    state_id a:31;
    unsigned epsilon_state:1;
};

// Normalize state pairs so a is always less than or equal to b.
static struct state_pair state_pair_make(state_id a, state_id b,
 enum epsilon_state epsilon_state)
{
    struct state_pair p = { .a = a, .b = b, .epsilon_state = epsilon_state };
    if (a > b) {
        p.a = b;
        p.b = a;
    }
    return p;
}

enum {
    // Types of node data.
    INVALID_NODE = 0,
    BOUNDARY_NODE,
    ACTION_NODE,
    SYMBOL_NODE,
    BRACKET_SYMBOL_NODE,
    // Join nodes have one path going left and one going right.
    JOIN_NODE,
};
enum {
    // There's an intrinsic ambiguity along this transition.
    AMBIGUOUS_NODE = 1 << 0,

    // Uses next pointer rather than next_pair.
    COPIED_PATH = 1 << 1,

    // The paths swap places through this node due to pair normalization.
    SWAPPED_PATH = 1 << 2,

    // The paths swap places through this bracket transition due to pair
    // normalization.
    SWAPPED_BRACKET_PATH = 1 << 3,
};
struct path_offset {
    uint32_t symbols;
    uint32_t actions[2];
};
struct path_node {
    union {
        struct path_node *next;
        struct state_pair next_pair;
    };
    union {
        uint16_t *actions[2];
        symbol_id symbol;
        struct state_pair bracket_pair;
        struct path_node *join[2];
    };
    struct path_offset offset;
    uint8_t type;
    uint8_t flags;
};
static struct path_node boundary_node = { .type = BOUNDARY_NODE };

enum state_pair_status {
    EMPTY = 0,
    USED,

    // Locked state pairs shouldn't be modified.  They're used to keep track of
    // bracket automaton paths.
    LOCKED,
};
struct state_pair_table {
    struct state_pair *pairs;
    struct path_node *in_paths;
    struct path_node *out_paths;
    // "ain"-paths are ambiguous in-paths.  We need to store these separately to
    // keep track of them without creating cycles (an ain-path may need to
    // include the same node pair twice -- if there are epsilon-cycles, for
    // example).
    struct path_node *ain_paths;
    uint32_t *in_weights;
    uint8_t *status;

    // A state pair along an ambiguous path, if one has been found.
    bool has_ambiguity;
    struct state_pair ambiguity;
    uint32_t ambiguity_weight;

    uint32_t available_size;
    uint32_t used_size;
};

struct work_item {
    struct path_node node;
    struct state_pair pair;
    uint32_t weight;
};
struct worklist {
    struct work_item *items;
    uint32_t items_allocated_bytes;
    uint32_t number_of_items;
};

enum direction {
    FORWARD,
    BACKWARD,

    // Search from only accepting states which don't have an ambiguous path yet.
    BACKWARD_UNRESOLVED,
};

struct context {
    struct combined_grammar *combined;

    // The paths are stored in the table under pairs of accepting states.
    struct state_pair_table bracket_paths;

    // These are both arrays with one element for each bracket transition.
    struct path_node *ambiguous_bracket_paths;
    state_id *bracket_states;
};

static void search_state_pairs(struct context *context,
 struct state_pair_table *table, struct automaton *automaton,
 enum direction direction);
static void follow_state_pair_transition(struct path_node node, state_id a,
 state_id b, uint32_t weight, enum direction direction,
 struct state_pair_table *table, struct worklist *worklist);

static void build_ambiguity_path(struct context *context,
 struct ambiguity *ambiguity, struct path_offset offset, struct path_node *node,
 int32_t direction, bool swapped);

// Copying a node fills in the offset as well.
static void path_node_copy(struct context *context,
 struct state_pair_table *table, struct path_node *which_paths,
 struct path_node *node);
// Destroy a copied path node.
static void path_node_destroy(struct path_node *node);

static struct path_node *ambiguous_bracket_path(struct context *context,
 symbol_id symbol);

static uint32_t state_pair_table_add(struct state_pair_table *table,
 struct state_pair pair, uint32_t hash);
static uint32_t state_pair_table_lookup(struct state_pair_table *table,
 struct state_pair pair, uint32_t hash);
static void state_pair_table_clear(struct state_pair_table *table);
static void state_pair_table_destroy(struct state_pair_table *table);
static void state_pair_table_rehash(struct state_pair_table *table,
 uint32_t new_size);

void check_for_ambiguity(struct combined_grammar *combined,
 struct ambiguity *ambiguity)
{
    struct context context = {
        .combined = combined,
    };
    context.ambiguous_bracket_paths =
     calloc(combined->number_of_bracket_symbols, sizeof(struct path_node));
    context.bracket_states =
     calloc(combined->number_of_bracket_symbols, sizeof(state_id));
    struct automaton *bracket_automaton = &combined->bracket_automaton;
    for (state_id i = 0; i < bracket_automaton->number_of_states; ++i) {
        struct state s = bracket_automaton->states[i];
        if (s.accepting) {
            context.bracket_states[s.transition_symbol -
             combined->number_of_tokens] = i;
        }
    }

    // Phase one: collect paths through the bracket product automaton
    // (ambiguous or not).
    bool changed;
    do {
        changed = false;
        struct state_pair_table *table = &context.bracket_paths;
        search_state_pairs(&context, table, bracket_automaton, FORWARD);
        for (uint32_t i = 0; i < table->available_size; ++i) {
            if (table->status[i] == EMPTY || table->status[i] == LOCKED)
                continue;
            struct state_pair p = table->pairs[i];
            if (p.epsilon_state != DISALLOW_EPSILON_SUCCESSORS)
                continue;
            if (!bracket_automaton->states[p.a].accepting ||
             !bracket_automaton->states[p.b].accepting)
                continue;
            path_node_copy(&context, table, table->in_paths,
             &table->in_paths[i]);
            table->status[i] = LOCKED;
            changed = true;
        }
        for (uint32_t i = 0; i < table->available_size; ++i) {
            if (table->status[i] == EMPTY || table->status[i] == LOCKED)
                continue;
            table->status[i] = EMPTY;
            table->used_size--;
        }
        // We re-hash here after deleting entries to avoid gaps in the table.
        state_pair_table_rehash(table, table->available_size);
    } while (changed);

    // Phase two: look for ambiguity.
    struct automaton reversed = {0};
    automaton_reverse(&combined->automaton, &reversed);
    struct automaton bracket_reversed = {0};
    automaton_reverse(bracket_automaton, &bracket_reversed);
    struct state_pair_table table = {0};
    while (true) {
        // Look for ambiguities in the bracket product automaton (potentially
        // propagating ambiguities outward as we discover new ambiguous
        // transitions).
        state_pair_table_clear(&table);
        search_state_pairs(&context, &table, bracket_automaton, FORWARD);
        search_state_pairs(&context, &table, &bracket_reversed,
         BACKWARD_UNRESOLVED);
        if (!table.has_ambiguity) {
            // No more bracket paths exist.  Now we can look for the final path
            // in the main automaton.
            state_pair_table_clear(&table);
            search_state_pairs(&context, &table, &combined->automaton, FORWARD);
            search_state_pairs(&context, &table, &reversed, BACKWARD);
            break;
        }

        // We found an ambiguity in the bracket product automaton.
        uint32_t path_index = state_pair_table_lookup(&table, table.ambiguity,
         fnv(&table.ambiguity, sizeof(table.ambiguity)));
        uint32_t i = path_index;
        while (table.out_paths[i].type != BOUNDARY_NODE) {
            // Follow the path until we reach a pair of accepting states.  The
            // search needs to be able to find this ambiguous path using the
            // transition symbols of its final, accepting pair.
            struct state_pair p = table.out_paths[i].next_pair;
            i = state_pair_table_lookup(&table, p, fnv(&p, sizeof(p)));
        }
        struct state_pair p = table.pairs[i];
        assert(p.a == p.b);
        struct state s = combined->bracket_automaton.states[p.a];
        assert(s.accepting);

        // Copy the path and add it to the `ambiguous_bracket_paths` array as a
        // `JOIN_NODE`.
        struct path_node *in = malloc(sizeof(struct path_node));
        struct path_node *out = malloc(sizeof(struct path_node));
        *in = table.in_paths[path_index];
        *out = table.out_paths[path_index];
        if (table.ain_paths[path_index].type != INVALID_NODE)
            *in = table.ain_paths[path_index];
        path_node_copy(&context, &table, table.in_paths, in);
        path_node_copy(&context, &table, table.out_paths, out);
        *ambiguous_bracket_path(&context, s.transition_symbol) =
         (struct path_node){
            .type = JOIN_NODE,
            .flags = AMBIGUOUS_NODE,
            .join = { in, out },
         };

        // Clear the table and keep looping until we don't find any more
        // ambiguities in the bracket product automaton.
        state_pair_table_clear(&table);
    }

    ambiguity->has_ambiguity = table.has_ambiguity;
    if (table.has_ambiguity) {
        // We found an ambiguous path through the root automaton.  Write it to
        // the output ambiguity struct.
        uint32_t path_index = state_pair_table_lookup(&table, table.ambiguity,
         fnv(&table.ambiguity, sizeof(table.ambiguity)));
        struct path_node in = table.in_paths[path_index];
        struct path_node out = table.out_paths[path_index];
        if (table.ain_paths[path_index].type != INVALID_NODE)
            in = table.ain_paths[path_index];
        path_node_copy(&context, &table, table.in_paths, &in);
        path_node_copy(&context, &table, table.out_paths, &out);
        ambiguity->number_of_tokens = in.offset.symbols + out.offset.symbols;
        ambiguity->tokens = calloc(ambiguity->number_of_tokens,
         sizeof(symbol_id));
        for (int i = 0; i < 2; ++i) {
            uint32_t n = in.offset.actions[i] + out.offset.actions[i];
            ambiguity->paths[i].number_of_actions = n;
            ambiguity->paths[i].actions = calloc(n, sizeof(uint16_t));
            ambiguity->paths[i].offsets = calloc(n, sizeof(uint32_t));
        }
        build_ambiguity_path(&context, ambiguity, in.offset, &out, 1, false);
        build_ambiguity_path(&context, ambiguity, in.offset, &in, -1, false);
        path_node_destroy(in.next);
        path_node_destroy(out.next);
    }

    // Clean up.
    automaton_destroy(&reversed);
    automaton_destroy(&bracket_reversed);
    state_pair_table_destroy(&table);
    for (uint32_t i = 0; i < context.bracket_paths.available_size; ++i) {
        if (context.bracket_paths.status[i] == EMPTY)
            continue;
        if (context.bracket_paths.in_paths[i].flags & COPIED_PATH)
            path_node_destroy(context.bracket_paths.in_paths[i].next);
    }
    state_pair_table_destroy(&context.bracket_paths);
    for (uint32_t i = 0; i < combined->number_of_bracket_symbols; ++i) {
        path_node_destroy(context.ambiguous_bracket_paths[i].join[0]);
        path_node_destroy(context.ambiguous_bracket_paths[i].join[1]);
    }
    free(context.ambiguous_bracket_paths);
    free(context.bracket_states);
}

static void search_state_pairs(struct context *context,
 struct state_pair_table *table, struct automaton *automaton,
 enum direction direction)
{
    table->has_ambiguity = false;
    automaton_compute_epsilon_closure(automaton, FOLLOW_ACTION_TRANSITIONS);
    // The worklist is a binary min-heap of state pairs.  The heap is ordered by
    // a weight (currently, the number of symbols it takes to reach the state
    // pair), which lets us produce minimal paths which focus on the ambiguity
    // itself.
    struct worklist worklist = {0};
    if (direction == FORWARD) {
        follow_state_pair_transition(boundary_node, automaton->start_state,
         automaton->start_state, 0, direction, table, &worklist);
    } else {
        struct state s = automaton->states[automaton->start_state];
        for (uint32_t i = 0; i < s.number_of_transitions; ++i) {
            state_id target = s.transitions[i].target;
            // The BACKWARD_UNRESOLVED direction means we ignore accepting
            // states we already have an ambiguous path for.
            if (direction == BACKWARD_UNRESOLVED &&
             ambiguous_bracket_path(context, automaton->states[target].
             transition_symbol)->type != INVALID_NODE)
                continue;
            follow_state_pair_transition(boundary_node, target, target, 0,
             BACKWARD, table, &worklist);
        }
        // The logic above is the only place where the distinction between
        // BACKWARD_UNRESOLVED and BACKWARD matters.  Simplify `direction` to
        // BACKWARD for the rest of the function so we don't have to deal with
        // both.
        direction = BACKWARD;
    }
    while (worklist.number_of_items > 0) {
        struct work_item item = worklist.items[0];
        struct state_pair s = item.pair;

        // Rebalance the heap to ensure the minimum-weight item is at the top.
        struct work_item last = worklist.items[--worklist.number_of_items];
        uint32_t i = 0;
        while (2*i+1 < worklist.number_of_items) {
            uint32_t j = 2*i+1;
            if (2*i+2 < worklist.number_of_items &&
             worklist.items[2*i+2].weight < worklist.items[j].weight)
                j = 2*i+2;
            if (last.weight > worklist.items[j].weight)
                worklist.items[i] = worklist.items[j];
            else
                break;
            i = j;
        }
        worklist.items[i] = last;

        // Check if we've already visited this state pair and set the path field
        // if necessary (`in_paths` for FORWARD, `out_paths` for BACKWARD).
        uint32_t hash = fnv(&s, sizeof(s));
        uint32_t index = state_pair_table_add(table, s, hash);
        if (table->status[index] == LOCKED)
            continue;
        if (direction == FORWARD) {
            bool set_in_path = false;
            if (table->in_paths[index].type == INVALID_NODE) {
                table->in_paths[index] = item.node;
                table->in_weights[index] = item.weight;
                set_in_path = true;
            }
            if ((item.node.flags & AMBIGUOUS_NODE) &&
             table->ain_paths[index].type == INVALID_NODE) {
                table->ain_paths[index] = item.node;
                table->in_weights[index] = item.weight;
            }
            if (!set_in_path)
                continue;
        }
        if (direction == BACKWARD) {
            if (table->out_paths[index].type == INVALID_NODE) {
                table->out_paths[index] = item.node;
                // Check to see if either of our requirements are satisfied:
                // - a path that contains two distinct states, or
                // - a path that contains an intrinsically ambiguous edge.
                bool contains_distinct_states = s.a != s.b &&
                 table->in_paths[index].type != INVALID_NODE;
                bool contains_intrinsic_ambiguity =
                 table->ain_paths[index].type != INVALID_NODE;
                // If this is the lowest-weighted path that satisfies the
                // requirements, track the current node as the new ambiguity.
                if ((contains_distinct_states || contains_intrinsic_ambiguity)
                 && (!table->has_ambiguity || item.weight +
                 table->in_weights[index] < table->ambiguity_weight)) {
                    table->has_ambiguity = true;
                    table->ambiguity = s;
                    table->ambiguity_weight = item.weight +
                     table->in_weights[index];
                }
            } else
                continue;
        }

        // Add each successor of this state pair to the worklist.
        uint32_t w = item.weight;
        struct state a = automaton->states[s.a];
        struct state b = automaton->states[s.b];
        bool follow_epsilons = s.epsilon_state == ALLOW_EPSILON_SUCCESSORS;
        if (direction == BACKWARD)
            follow_epsilons = !follow_epsilons;
        if (follow_epsilons) {
            // Add action transitions by visiting the two states' epsilon
            // closures.  Since states aren't stored in their own epsilon
            // closures, this is a bit more code than it might otherwise be.
            struct epsilon_closure ac, bc;
            ac = automaton->epsilon_closure_for_state[s.a];
            bc = automaton->epsilon_closure_for_state[s.b];
            for (uint32_t i = 0; i < ac.reachable.number_of_states; ++i) {
                for (uint32_t j = 0; j < bc.reachable.number_of_states; ++j) {
                    follow_state_pair_transition((struct path_node){
                        .type = ACTION_NODE,
                        .next_pair = s,
                        .actions[0] = ac.actions + ac.action_indexes[i],
                        .actions[1] = bc.actions + bc.action_indexes[j],
                    }, ac.reachable.states[i], bc.reachable.states[j], w,
                     direction, table, &worklist);
                }
                follow_state_pair_transition((struct path_node){
                    .type = ACTION_NODE,
                    .next_pair = s,
                    .actions[0] = ac.actions + ac.action_indexes[i],
                }, ac.reachable.states[i], s.b, w, direction, table, &worklist);
                // Check `ambiguous_action_indexes` to see if there's a second
                // path between these two states.  If there is, we create a node
                // with both action lists and with the AMBIGUOUS_NODE flag set--
                // `follow_state_pair_transition` will add this node to
                // `ain_nodes` as an intrinsic ambiguity.
                if (direction == FORWARD && s.a == s.b &&
                 ac.ambiguous_action_indexes[i] != UINT32_MAX) {
                    follow_state_pair_transition((struct path_node){
                        .type = ACTION_NODE,
                        .next_pair = s,
                        .flags = AMBIGUOUS_NODE,
                        .actions[0] = ac.actions + ac.action_indexes[i],
                        .actions[1] = ac.actions +
                         ac.ambiguous_action_indexes[i],
                    }, ac.reachable.states[i], ac.reachable.states[i], w,
                     direction, table, &worklist);
                }
            }
            for (uint32_t j = 0; j < bc.reachable.number_of_states; ++j) {
                follow_state_pair_transition((struct path_node){
                    .type = ACTION_NODE,
                    .next_pair = s,
                    .actions[1] = bc.actions + bc.action_indexes[j],
                }, s.a, bc.reachable.states[j], w, direction, table, &worklist);
            }
            follow_state_pair_transition((struct path_node){
                .next_pair = s,
                .type = ACTION_NODE,
            }, s.a, s.b, w, direction, table, &worklist);
        } else {
            // Add successors of symbol and bracket transitions.
            for (uint32_t i = 0; i < a.number_of_transitions; ++i) {
                struct transition at = a.transitions[i];
                if (at.symbol == SYMBOL_EPSILON)
                    continue;
                bool bracket = at.symbol >= context->combined->number_of_tokens;
                for (uint32_t j = 0; j < b.number_of_transitions; ++j) {
                    struct transition bt = b.transitions[j];
                    if (!bracket) {
                        // This is a normal symbol transition.
                        if (at.symbol != bt.symbol)
                            continue;
                        follow_state_pair_transition((struct path_node){
                            .type = SYMBOL_NODE,
                            .next_pair = s,
                            .symbol = at.symbol,
                        }, at.target, bt.target, w + 1, direction, table,
                         &worklist);
                        continue;
                    }
                    if (bt.symbol == SYMBOL_EPSILON)
                        continue;
                    if (bt.symbol < context->combined->number_of_tokens)
                        continue;
                    // This is a bracket transition.

                    // Check the `bracket_paths` table to see if the accepting
                    // state pair corresponding to these two bracket transition
                    // symbols has an associated path.
                    state_id sa = context->bracket_states[at.symbol -
                     context->combined->number_of_tokens];
                    state_id sb = context->bracket_states[bt.symbol -
                     context->combined->number_of_tokens];
                    struct state_pair p = state_pair_make(sa, sb,
                     DISALLOW_EPSILON_SUCCESSORS);
                    uint32_t k;
                    k = state_pair_table_lookup(&context->bracket_paths, p,
                     fnv(&p, sizeof(p)));
                    if (context->bracket_paths.status[k] == LOCKED) {
                        // The "locked" flag indicates there's a path here.
                        // If we're moving along two different transition
                        // symbols, this is an intrinsic ambiguity -- mark it
                        // using the AMBIGUOUS_NODE flag.
                        follow_state_pair_transition((struct path_node){
                            .type = BRACKET_SYMBOL_NODE,
                            .next_pair = s,
                            .bracket_pair = p,
                            .flags = (at.symbol == bt.symbol ? 0 :
                             AMBIGUOUS_NODE) | (sa == p.a ? 0 :
                             SWAPPED_BRACKET_PATH),
                        }, at.target, bt.target, w +
                         context->bracket_paths.in_paths[k].offset.symbols,
                         direction, table, &worklist);
                    }

                    if (at.symbol == bt.symbol) {
                        // If this bracket transition already has an intrinsic
                        // ambiguity, track it using the JOIN_NODE node we
                        // stored in the `ambiguous_bracket_paths` array.
                        struct path_node n = *ambiguous_bracket_path(context,
                         at.symbol);
                        if (n.type != INVALID_NODE) {
                            n.next_pair = s;
                            follow_state_pair_transition(n, at.target,
                             bt.target, w + n.join[0]->offset.symbols +
                             n.join[1]->offset.symbols, direction, table,
                             &worklist);
                        }
                    }
                }
            }
        }
    }
    free(worklist.items);
}

static void follow_state_pair_transition(struct path_node node, state_id a,
 state_id b, uint32_t weight, enum direction direction,
 struct state_pair_table *table, struct worklist *worklist)
{
    struct state_pair pair;
    // Set the `epsilon_state` to ensure the path can't have two sequential
    // epsilon transitions.
    if (node.type == ACTION_NODE) {
        pair = state_pair_make(a, b, direction == FORWARD ?
         DISALLOW_EPSILON_SUCCESSORS : ALLOW_EPSILON_SUCCESSORS);
    } else {
        pair = state_pair_make(a, b, direction == FORWARD ?
         ALLOW_EPSILON_SUCCESSORS : DISALLOW_EPSILON_SUCCESSORS);
    }
    if (a != pair.a)
        node.flags |= SWAPPED_PATH;

    // Add the next pair to the worklist.
    uint32_t i = worklist->number_of_items++;
    if (i == UINT32_MAX)
        abort();
    worklist->items = grow_array(worklist->items,
     &worklist->items_allocated_bytes,
     sizeof(struct work_item) * worklist->number_of_items);
    // Setting i = (i-1)/2 moves up the binary min-heap.
    for(; i > 0 && weight < worklist->items[(i-1)/2].weight; i = (i-1)/2)
        worklist->items[i] = worklist->items[(i-1)/2];
    worklist->items[i] = (struct work_item){
        .node = node,
        .pair = pair,
        .weight = weight,
    };
}

static void build_ambiguity_path(struct context *context,
 struct ambiguity *ambiguity, struct path_offset offset, struct path_node *node,
 int32_t direction, bool swapped)
{
    // `build_ambiguity_path` fills in the ambiguity struct according to the
    // path described in `node`.  The offsets computed in `path_node_copy` are
    // used to figure out where to put each action and symbol.
    for (; node && node->type != BOUNDARY_NODE; node = node->next) {
        if (node->flags & SWAPPED_PATH)
            swapped = !swapped;
        switch (node->type) {
        case ACTION_NODE:
            for (int i = 0; i < 2; ++i) {
                uint16_t *actions = node->actions[swapped ? 1 - i : i];
                struct ambiguity_path *p = &ambiguity->paths[i];
                for (; actions && *actions; ++actions) {
                    if (direction == -1)
                        offset.actions[i]--;
                    p->actions[offset.actions[i]] = *actions;
                    p->offsets[offset.actions[i]] = offset.symbols;
                    if (direction == 1)
                        offset.actions[i]++;
                }
            }
            break;
        case SYMBOL_NODE:
            if (direction == -1)
                offset.symbols--;
            ambiguity->tokens[offset.symbols] = node->symbol;
            if (direction == 1)
                offset.symbols++;
            break;
        case BRACKET_SYMBOL_NODE: {
            struct state_pair p = node->bracket_pair;
            uint32_t i = state_pair_table_lookup(&context->bracket_paths, p,
             fnv(&p, sizeof(p)));
            assert(context->bracket_paths.status[i] == LOCKED);
            struct path_node in = context->bracket_paths.in_paths[i];
            assert(in.flags & COPIED_PATH);
            bool parity = swapped == !(node->flags & SWAPPED_BRACKET_PATH);
            if (direction == 1) {
                offset.symbols += in.offset.symbols;
                for (int i = 0; i < 2; ++i)
                    offset.actions[parity ? 1 - i : i] += in.offset.actions[i];
            }
            build_ambiguity_path(context, ambiguity, offset, &in, -1,
             node->flags & SWAPPED_BRACKET_PATH ? !swapped : swapped);
            if (direction == -1) {
                offset.symbols -= in.offset.symbols;
                for (int i = 0; i < 2; ++i)
                    offset.actions[parity ? 1 - i : i] -= in.offset.actions[i];
            }
            break;
        }
        case JOIN_NODE: {
            int j = direction == 1 ? 0 : 1;
            offset.symbols += node->join[j]->offset.symbols * direction;
            for (int i = 0; i < 2; ++i) {
                offset.actions[i] += direction *
                 node->join[j]->offset.actions[swapped ? 1 - i : i];
            }
            build_ambiguity_path(context, ambiguity, offset, node->join[1], 1,
             swapped);
            build_ambiguity_path(context, ambiguity, offset, node->join[0], -1,
             swapped);
            offset.symbols += node->join[1 - j]->offset.symbols * direction;
            for (int i = 0; i < 2; ++i) {
                offset.actions[i] += direction *
                 node->join[1 - j]->offset.actions[swapped ? 1 - i : i];
            }
            break;
        }
        default:
            break;
        }
    }
}

static void path_node_copy(struct context *context,
 struct state_pair_table *table, struct path_node *which_paths,
 struct path_node *node)
{
    // Copies a path from table storage into heap storage, filling in the
    // offset field according to how many actions and symbols the path contains.
    // The `build_ambiguity_path` function writes actions and symbols into the
    // final ambiguity path using this offset field as a guide -- that's why
    // these two functions have such a similar structure.
    if (node->flags & COPIED_PATH)
        return;
    struct path_offset *offset = &node->offset;
    bool swapped = false;
    for (; node && node->type != BOUNDARY_NODE; node = node->next) {
        if (node->flags & SWAPPED_PATH)
            swapped = !swapped;
        switch (node->type) {
        case ACTION_NODE:
            for (int i = 0; i < 2; ++i) {
                uint16_t *actions = node->actions[swapped ? 1 - i : i];
                for (; actions && *actions; ++actions)
                    offset->actions[i]++;
            }
            break;
        case SYMBOL_NODE:
            offset->symbols++;
            break;
        case BRACKET_SYMBOL_NODE: {
            struct state_pair p = node->bracket_pair;
            uint32_t i = state_pair_table_lookup(&context->bracket_paths, p,
             fnv(&p, sizeof(p)));
            assert(context->bracket_paths.status[i] == LOCKED);
            struct path_node in = context->bracket_paths.in_paths[i];
            assert(in.flags & COPIED_PATH);
            offset->symbols += in.offset.symbols;
            bool parity = swapped == !(node->flags & SWAPPED_BRACKET_PATH);
            for (int i = 0; i < 2; ++i)
                offset->actions[parity ? 1 - i : i] += in.offset.actions[i];
            break;
        }
        case JOIN_NODE:
            offset->symbols += node->join[0]->offset.symbols;
            offset->symbols += node->join[1]->offset.symbols;
            for (int i = 0; i < 2; ++i) {
                offset->actions[swapped ? 1 - i : i] +=
                 node->join[0]->offset.actions[i] +
                 node->join[1]->offset.actions[i];
            }
            break;
        default:
            break;
        }
        if (node->flags & COPIED_PATH)
            continue;
        struct state_pair p = node->next_pair;
        uint32_t i = state_pair_table_lookup(table, p, fnv(&p, sizeof(p)));
        if (table->status[i] == EMPTY || which_paths[i].type == BOUNDARY_NODE)
            node->next = 0;
        else {
            node->next = malloc(sizeof(struct path_node));
            *node->next = which_paths[i];
        }
        node->flags |= COPIED_PATH;
    }
}

static void path_node_destroy(struct path_node *node)
{
    while (node && (node->flags & COPIED_PATH)) {
        struct path_node *next = node->next;
        free(node);
        node = next;
    }
}

static struct path_node *ambiguous_bracket_path(struct context *context,
 symbol_id symbol)
{
    return &context->ambiguous_bracket_paths[symbol -
     context->combined->number_of_tokens];
}

static uint32_t state_pair_table_add(struct state_pair_table *table,
 struct state_pair pair, uint32_t hash)
{
    if (3 * table->available_size <= 4 * (table->used_size + 1)) {
        uint32_t n = table->available_size * 2;
        if (n <= 128)
            n = 128;
        state_pair_table_rehash(table, n);
    }
    uint32_t index = state_pair_table_lookup(table, pair, hash);
    if (table->status[index] == EMPTY) {
        table->status[index] = USED;
        table->pairs[index] = pair;
        table->in_paths[index].type = INVALID_NODE;
        table->out_paths[index].type = INVALID_NODE;
        table->ain_paths[index].type = INVALID_NODE;
        table->used_size++;
    }
    return index;
}

static uint32_t state_pair_table_lookup(struct state_pair_table *table,
 struct state_pair pair, uint32_t hash)
{
    uint32_t mask = table->available_size - 1;
    uint32_t index = hash & mask;
    while (true) {
        if (table->status[index] == EMPTY)
            return index;
        if (table->pairs[index].a == pair.a && table->pairs[index].b == pair.b
         && table->pairs[index].epsilon_state == pair.epsilon_state)
            return index;
        index = (index + 1) & mask;
        if (index == (hash & mask))
            abort();
    }
}

static void state_pair_table_clear(struct state_pair_table *table)
{
    memset(table->status, 0, sizeof(uint8_t) * table->available_size);
    table->used_size = 0;
}

static void state_pair_table_destroy(struct state_pair_table *table)
{
    free(table->pairs);
    free(table->in_paths);
    free(table->out_paths);
    free(table->ain_paths);
    free(table->in_weights);
    free(table->status);
    memset(table, 0, sizeof(*table));
}

static void state_pair_table_rehash(struct state_pair_table *table,
 uint32_t new_size)
{
    struct state_pair_table old = *table;
    table->pairs = calloc(new_size, sizeof(struct state_pair));
    table->in_paths = calloc(new_size, sizeof(struct path_node));
    table->out_paths = calloc(new_size, sizeof(struct path_node));
    table->ain_paths = calloc(new_size, sizeof(struct path_node));
    table->in_weights = calloc(new_size, sizeof(uint32_t));
    table->status = calloc(new_size, sizeof(uint8_t));
    table->available_size = new_size;
    table->used_size = 0;
    for (uint32_t i = 0; i < old.available_size; ++i) {
        if (old.status[i] == EMPTY)
            continue;
        uint32_t hash = fnv(&old.pairs[i], sizeof(old.pairs[i]));
        uint32_t index = state_pair_table_add(table, old.pairs[i], hash);
        table->in_paths[index] = old.in_paths[i];
        table->out_paths[index] = old.out_paths[i];
        table->ain_paths[index] = old.ain_paths[i];
        table->in_weights[index] = old.in_weights[i];
        table->status[index] = old.status[i];
    }
    free(old.pairs);
    free(old.in_paths);
    free(old.out_paths);
    free(old.ain_paths);
    free(old.in_weights);
    free(old.status);
}


<|start_filename|>src/automaton-epsilon-closure.c<|end_filename|>
#include "automaton.h"

#include "alloc.h"
#include "fnv.h"
#include <assert.h>

struct state_table {
    state_id *states;
    uint32_t *state_hashes;
    uint32_t *state_indexes;
    bool *used;

    uint32_t available_size;
    uint32_t used_size;
};

static uint32_t append_to_action_path(struct state_table *table,
 struct epsilon_closure *closure, uint32_t previous_action_indexes,
 uint16_t action);
static bool closure_entry_add(struct state_table *table,
 struct epsilon_closure *closure, state_id previous_state, state_id state,
 uint16_t action);
static void closure_action_add(struct epsilon_closure *, uint16_t action);
static uint32_t *state_table_add(struct state_table *table, state_id state);
static uint32_t state_table_lookup(struct state_table *table, state_id state,
 uint32_t hash);

void automaton_compute_epsilon_closure(struct automaton *a,
 enum automaton_epsilon_closure_mode mode)
{
    if (a->epsilon_closure_mode != mode) {
        a->epsilon_closure_mode = mode;
        automaton_invalidate_epsilon_closure(a);
    }
    if (a->epsilon_closure_for_state != 0)
        return;
    // Ensure we've actually created a start state.
    automaton_set_start_state(a, a->start_state);
    uint32_t n = a->number_of_states;
    a->epsilon_closure_for_state = calloc(n, sizeof(struct epsilon_closure));
    struct state_array worklist = {0};
    struct state_table visited = {0};
    bool ignore_action_transitions =
     a->epsilon_closure_mode == IGNORE_ACTION_TRANSITIONS;
    for (state_id i = 0; i < n; ++i) {
        struct epsilon_closure *closure = &a->epsilon_closure_for_state[i];
        state_array_push(&worklist, i);
        state_table_add(&visited, i);
        while (worklist.number_of_states > 0) {
            state_id id = state_array_pop(&worklist);
            struct state *state = &a->states[id];
            uint32_t number_of_transitions = state->number_of_transitions;
            for (uint32_t j = 0; j < number_of_transitions; ++j) {
                struct transition transition = state->transitions[j];
                if (transition.symbol != SYMBOL_EPSILON)
                    continue;
                if (ignore_action_transitions && transition.action != 0)
                    continue;
                state_id target = transition.target;
                state_id action = transition.action;
//                // Uncomment me to get ambiguous paths like "" vs "a" instead
//                // of "a" vs "a a"!
//                if (target == i)
//                    closure_entry_add(&visited, closure, UINT32_MAX, i, 0);
                if (closure_entry_add(&visited, closure, id, target, action))
                    state_array_push(&worklist, target);
            }
        }
        state_array_clear(&worklist);
        memset(visited.used, 0, visited.available_size * sizeof(bool));
        visited.used_size = 0;
    }
    state_array_destroy(&worklist);
    free(visited.states);
    free(visited.state_hashes);
    free(visited.state_indexes);
    free(visited.used);
}

static bool closure_entry_add(struct state_table *table,
 struct epsilon_closure *closure, state_id previous_state, state_id state,
 uint16_t action)
{
    uint32_t *state_index = state_table_add(table, state);
    if (*state_index == UINT32_MAX) {
        *state_index = closure->reachable.number_of_states;
        state_array_push(&closure->reachable, state);
        closure->action_indexes = grow_array(closure->action_indexes,
         &closure->action_indexes_allocated_bytes,
         sizeof(uint32_t) * closure->reachable.number_of_states);
        closure->ambiguous_action_indexes =
         grow_array(closure->ambiguous_action_indexes,
          &closure->ambiguous_action_indexes_allocated_bytes,
          sizeof(uint32_t) * closure->reachable.number_of_states);
        closure->action_indexes[*state_index] = UINT32_MAX;
        closure->ambiguous_action_indexes[*state_index] = UINT32_MAX;
    }
    if (closure->action_indexes[*state_index] != UINT32_MAX &&
     closure->ambiguous_action_indexes[*state_index] != UINT32_MAX)
        return false;
    bool first_visit = closure->action_indexes[*state_index] == UINT32_MAX;
    uint32_t previous = state_table_lookup(table, previous_state,
     fnv(&previous_state, sizeof(previous_state)));
    uint32_t previous_state_index = table->state_indexes[previous];
    if (!table->used[previous] || previous_state_index == UINT32_MAX) {
        // We'll visit this state twice in succession if there are two
        // transitions from a single state to this one.  So we have to handle
        // both cases.
        if (first_visit) {
            closure->action_indexes[*state_index] =
             append_to_action_path(table, closure, UINT32_MAX, action);
        } else {
            closure->ambiguous_action_indexes[*state_index] =
             append_to_action_path(table, closure, UINT32_MAX, action);
        }
        return true;
    }
    if (first_visit) {
        closure->action_indexes[*state_index] = append_to_action_path(table,
         closure, closure->action_indexes[previous_state_index], action);
    }
    if (closure->ambiguous_action_indexes[previous_state_index] != UINT32_MAX) {
        closure->ambiguous_action_indexes[*state_index] =
         append_to_action_path(table, closure,
         closure->ambiguous_action_indexes[previous_state_index], action);
    } else if (!first_visit) {
        closure->ambiguous_action_indexes[*state_index] =
         append_to_action_path(table, closure,
         closure->action_indexes[previous_state_index], action);
    }
    return true;
}

static uint32_t append_to_action_path(struct state_table *table,
 struct epsilon_closure *closure, uint32_t previous_action_indexes,
 uint16_t action)
{
    uint32_t action_index = closure->number_of_actions;
    if (action)
        closure_action_add(closure, action);
    if (previous_action_indexes != UINT32_MAX) {
        uint32_t i = previous_action_indexes;
        if (!action)
            return i;
        while (closure->actions[i]) {
            closure_action_add(closure, closure->actions[i]);
            i++;
        }
    }
    closure_action_add(closure, 0);
    return action_index;
}

static void closure_action_add(struct epsilon_closure *closure, uint16_t action)
{
    if (closure->number_of_actions == UINT32_MAX)
        abort();
    uint32_t index = closure->number_of_actions++;
    closure->actions = grow_array(closure->actions,
     &closure->actions_allocated_bytes,
     sizeof(uint16_t) * closure->number_of_actions);
    closure->actions[index] = action;
}

void automaton_invalidate_epsilon_closure(struct automaton *a)
{
    if (a->epsilon_closure_for_state == 0)
        return;
    for (uint32_t i = 0; i < a->number_of_states; ++i) {
        struct epsilon_closure *closure = &a->epsilon_closure_for_state[i];
        state_array_destroy(&closure->reachable);
        free(closure->ambiguous_action_indexes);
        free(closure->action_indexes);
        free(closure->actions);
    }
    free(a->epsilon_closure_for_state);
    a->epsilon_closure_for_state = 0;
}

static uint32_t *state_table_add(struct state_table *table, state_id state)
{
    if (3 * table->available_size <= 4 * (table->used_size + 1)) {
        struct state_table old = *table;
        uint32_t n = old.available_size * 2;
        if (n == 0)
            n = 4;
        table->states = calloc(n, sizeof(state_id));
        table->state_hashes = calloc(n, sizeof(uint32_t));
        table->state_indexes = calloc(n, sizeof(uint32_t));
        table->used = calloc(n, sizeof(bool));
        table->available_size = n;
        table->used_size = 0;
        for (uint32_t i = 0; i < old.available_size; ++i) {
            if (!old.used[i])
                continue;
            uint32_t *state_index = state_table_add(table, old.states[i]);
            *state_index = old.state_indexes[i];
        }
        free(old.states);
        free(old.state_hashes);
        free(old.state_indexes);
        free(old.used);
    }

    uint32_t hash = fnv(&state, sizeof(state));
    uint32_t index = state_table_lookup(table, state, hash);
    if (!table->used[index]) {
        table->states[index] = state;
        table->state_hashes[index] = hash;
        table->state_indexes[index] = UINT32_MAX;
        table->used[index] = true;
        table->used_size++;
    }
    return &table->state_indexes[index];
}

static uint32_t state_table_lookup(struct state_table *table, state_id state,
 uint32_t hash)
{
    uint32_t mask = table->available_size - 1;
    uint32_t index = hash & mask;
    while (true) {
        if (!table->used[index])
            return index;
        if (table->states[index] == state)
            return index;
        index = (index + 1) & mask;
        if (index == (hash & mask))
            abort();
    }
}
