
        if (ctx.state.empty() || sym == 0) break;
        make_one_step_simple(ctx, sym);
    }

    for (cconfiter_t i = ctx.state.begin(), e = ctx.state.end(); i!= e; ++i) {
        nfa_state_t *s = i->state;
        s->clos = NOCLOS;
        if (s->type == nfa_state_t::FIN) {
            ctx.marker = ctx.cursor;
            ctx.rule = 0;
        }
    }

    if (ctx.rule == Rule::NONE) {
        return REG_NOMATCH;
    }

    // 2nd pass, backward: find submatches

    const uint32_t len = static_cast<uint32_t>(ctx.marker - string) - 1;
    init(ctx, string);
    ctx.step = len;
    ctx.cursor = ctx.marker = string + len;

    const std::vector<Tag> &tags = ctx.nfa.tags;
    const size_t sz = tags.size() * ctx.nfa.size * 2;
    offsets4 = new regoff_t[sz];
    offsets5 = new regoff_t[sz];
    offsets6 = new regoff_t[sz];

    std::fill(offsets4, offsets4 + sz, -2);
    std::fill(offsets5, offsets5 + sz, -2);

    ctx.reach.push_back(conf_t(ctx.nfa.root, 0, 0));
    for (;;) {
        closure_posix(ctx);
        if (ctx.state.empty() || ctx.cursor == string) break;
        const uint32_t sym = static_cast<uint8_t>(*--ctx.cursor);
        make_one_step(ctx, sym);
        --ctx.step;
    }
    make_final_step(ctx);

    delete[] offsets6;
    delete[] offsets5;
    delete[] offsets4;

    if (ctx.rule == Rule::NONE) {
        return REG_NOMATCH;
    }

    const getoff_nfa_t fn = { ctx.offsets3 };
    tags_to_submatch(tags, nmatch, pmatch, static_cast<regoff_t>(len), fn);

    return 0;
}

static uint32_t index(const nfa_state_t *s, const nfa_t &nfa)
{
    return static_cast<uint32_t>(s - nfa.states);
}

void closure_simple(psimctx_t &ctx)
{
    psimctx_t::confset_t &state = ctx.state, &stack = ctx.reach;
    state.clear();

    for (;!stack.empty(); ) {
        const psimctx_t::conf_t x = stack.back();
        stack.pop_back();
        nfa_state_t *n = x.state;

        if (n->clos!= NOCLOS) continue;

        n->clos = static_cast<uint32_t>(state.size());
        state.push_back(x);

        switch (n->type) {
            case nfa_state_t::ALT:
                stack.push_back(psimctx_t::conf_t(x, n->alt.out2));
                stack.push_back(psimctx_t::conf_t(x, n->alt.out1));
                break;
            case nfa_state_t::TAG:
                stack.push_back(psimctx_t::conf_t(x, n->tag.out, 0));
                break;
            case nfa_state_t::RAN:
            case nfa_state_t::FIN:
                break;
        }
    }
}

void make_one_step_simple(psimctx_t &ctx, uint32_t sym)
{
    const confset_t &state = ctx.state;
    confset_t &reach = ctx.reach;
    DASSERT(reach.empty());

    for (rcconfiter_t i = state.rbegin(), e = state.rend(); i!= e; ++i) {
        nfa_state_t *s = i->state;
        s->clos = NOCLOS;

        if (s->type == nfa_state_t::RAN) {
            for (const Range *r = s->ran.ran; r; r = r->next()) {
                if (r->lower() <= sym && sym < r->upper()) {
                    conf_t c(s->ran.out, 0, 0);
                    reach.push_back(c);
                    break;
                }
            }
        }
        else if (s->type == nfa_state_t::FIN) {
            ctx.marker = ctx.cursor;
            ctx.rule = 0;
        }
    }

    ++ctx.step;
}

void closure_posix(psimctx_t &ctx)
{
    if (ctx.flags & REG_GTOP) {
        closure_posix_gtop(ctx);
    }
    else {
        closure_posix_gor1(ctx);
    }
}

static int32_t precedence(psimctx_t &ctx, const conf_t &x, const conf_t &y)
{
    DASSERT(x.state == y.state); (void)y;
    const uint32_t idx = index(x.state, ctx.nfa);

    const size_t ntags = ctx.nfa.tags.size();
    const regoff_t *ox = offsets5 + ntags * idx * 2;
    const regoff_t *oy = offsets4 + ntags * idx * 2;

    prtoff5(ctx, idx);
    prtoff4(ctx, idx);
    if (D) fprintf(stderr, "prec %u: ", idx);

    for (size_t t = 0; t < ctx.nfa.tags.size(); t += 2) {
        const regoff_t offx = ox[2 * (t + 1)];
        const regoff_t offy = oy[2 * (t + 1)];
        if (offx!= offy) {
            int cmp;
            if (offx == -2) {
                cmp = -1;
            }
            if (offy == -2) {
                cmp = 1;
            }
            else {
                cmp = offx > offy? -1 : 1;
            }
            if (D) fprintf(stderr, "%d\n", cmp);
            return cmp;
        }
    }
    if (D) fprintf(stderr, "0\n");
    return 0;
}

void closure_posix_gor1(psimctx_t &ctx)
{
    psimctx_t::confset_t &state = ctx.state, &reach = ctx.reach;
    std::vector<nfa_state_t*>
        &topsort = ctx.gor1_topsort,
        &linear = ctx.gor1_linear;
    const size_t ntags = ctx.nfa.tags.size();

    state.clear();
    memcpy(offsets6, offsets4, ctx.nfa.size * ntags * sizeof(regoff_t) * 2);

    // Reverse order happens to result in less test errors, but both orders
    // do not yield a correct algorithm (paths are still compared after
    // their join point sometimes).
    for (psimctx_t::rcconfiter_t c = reach.rbegin(); c!= reach.rend(); ++c) {
        regoff_t       *ox = offsets5 + ntags * index(c->state, ctx.nfa) * 2;
        const regoff_t *oy = offsets6 + ntags * c->origin * 2;
        memcpy(ox, oy, ntags * sizeof(regoff_t) * 2);

        if (D) fprintf(stderr, "restoring offsets %u to %u\n"
           , c->origin, index(c->state, ctx.nfa));

        relax_gor1(ctx, *c);
    }

    for (;!topsort.empty(); ) {

        // 1st pass: depth-first postorder traversal of admissible subgraph
        for (;!topsort.empty(); ) {
            nfa_state_t *q = topsort.back();
            if (q->status == GOR_LINEAR) {