path: root/contrib/libs/hyperscan/src/nfagraph/ng_som.cpp

/*
 * Copyright (c) 2015-2017, Intel Corporation
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *  * Neither the name of Intel Corporation nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 * \brief SOM ("Start of Match") analysis.
 */

#include "ng_som.h"

#include "ng.h"
#include "ng_dump.h"
#include "ng_equivalence.h"
#include "ng_execute.h"
#include "ng_haig.h"
#include "ng_limex.h"
#include "ng_literal_analysis.h"
#include "ng_prune.h"
#include "ng_redundancy.h"
#include "ng_region.h"
#include "ng_reports.h"
#include "ng_som_add_redundancy.h"
#include "ng_som_util.h"
#include "ng_split.h"
#include "ng_util.h"
#include "ng_violet.h"
#include "ng_width.h"
#include "grey.h"
#include "ue2common.h"
#include "compiler/compiler.h"
#include "nfa/goughcompile.h"
#include "nfa/nfa_internal.h" // for MO_INVALID_IDX
#include "parser/position.h"
#include "som/som.h"
#include "rose/rose_build.h"
#include "rose/rose_in_util.h"
#include "util/alloc.h"
#include "util/compare.h"
#include "util/compile_error.h"
#include "util/container.h"
#include "util/dump_charclass.h"
#include "util/graph_range.h"
#include "util/make_unique.h"

#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

namespace ue2 {

static const size_t MAX_SOM_PLANS = 10;
static const size_t MAX_SOMBE_CHAIN_VERTICES = 4000;

#define MAX_REV_NFA_PREFIX 80

namespace {
struct som_plan {
    som_plan(const shared_ptr<NGHolder> &p, const CharReach &e, bool i,
             u32 parent_in) : prefix(p), escapes(e), is_reset(i),
                              no_implement(false), parent(parent_in) { }
    shared_ptr<NGHolder> prefix;
    CharReach escapes;
    bool is_reset;
    bool no_implement;
    u32 parent; // index of parent plan in the vector.

    // Reporters: a list of vertices in the graph that must be have their
    // reports updated at implementation time to report this plan's
    // som_loc_out.
    vector<NFAVertex> reporters;

    // Similar, but these report the som_loc_in.
    vector<NFAVertex> reporters_in;
};
}

static
bool regionCanEstablishSom(const NGHolder &g,
                           const unordered_map<NFAVertex, u32> &regions,
                           const u32 region, const vector<NFAVertex> &r_exits,
                           const vector<DepthMinMax> &depths) {
    if (region == regions.at(g.accept) ||
        region == regions.at(g.acceptEod)) {
        DEBUG_PRINTF("accept in region\n");
        return false;
    }

    DEBUG_PRINTF("region %u\n", region);
    for (UNUSED auto v : r_exits) {
        DEBUG_PRINTF("    exit %zu\n", g[v].index);
    }

    /* simple if each region exit is at fixed distance from SOM. Note SOM does
       not include virtual starts */
    for (auto v : r_exits) {
        assert(regions.at(v) == region);
        const DepthMinMax &d = depths.at(g[v].index);
        if (d.min != d.max) {
            DEBUG_PRINTF("failing %zu as %s != %s\n", g[v].index,
                         d.min.str().c_str(), d.max.str().c_str());
            return false;
        }
    }
    DEBUG_PRINTF("region %u/%zu is good\n", regions.at(r_exits[0]),
                 g[r_exits[0]].index);

    return true;
}

namespace {

struct region_info {
    region_info() : optional(false), dag(false) {}
    vector<NFAVertex> enters;
    vector<NFAVertex> exits;
    vector<NFAVertex> full;
    bool optional; /* skip edges around region */
    bool dag; /* completely acyclic */
};

}

static
void buildRegionMapping(const NGHolder &g,
                        const unordered_map<NFAVertex, u32> &regions,
                        map<u32, region_info> &info,
                        bool include_region_0 = false) {
    for (auto v : vertices_range(g)) {
        u32 region = regions.at(v);
        if (!include_region_0 && (is_any_start(v, g) || region == 0)) {
            continue;
        }
        assert(!region || !is_any_start(v, g));

        if (is_any_accept(v, g)) {
            continue;
        }

        if (isRegionEntry(g, v, regions)) {
            info[region].enters.push_back(v);
        }
        if (isRegionExit(g, v, regions)) {
            info[region].exits.push_back(v);
        }
        info[region].full.push_back(v);
    }

    for (auto &m : info) {
        if (!m.second.enters.empty()
            && isOptionalRegion(g, m.second.enters.front(), regions)) {
            m.second.optional = true;
        }
        m.second.dag = true; /* will be cleared for cyclic regions later */
    }

    set<NFAEdge> be;
    BackEdges<set<NFAEdge> > backEdgeVisitor(be);
    boost::depth_first_search(g, visitor(backEdgeVisitor).root_vertex(g.start));

    for (const auto &e : be) {
        NFAVertex u = source(e, g);
        NFAVertex v = target(e, g);
        if (is_special(u, g) || is_special(v, g)) {
            assert(is_special(u, g) && is_special(v, g));
            continue;
        }
        u32 r = regions.at(v);
        assert(regions.at(u) == r);
        info[r].dag = false;
    }

    if (include_region_0) {
        info[0].dag = false;
    }

    #ifdef DEBUG
    for (const auto &m : info) {
        u32 r = m.first;
        const region_info &r_i = m.second;
        DEBUG_PRINTF("region %u:%s%s\n", r,
                     r_i.dag ? " (dag)" : "",
                     r_i.optional ? " (optional)" : "");
        DEBUG_PRINTF("  enters:");
        for (u32 i = 0; i < r_i.enters.size(); i++) {
            printf(" %zu", g[r_i.enters[i]].index);
        }
        printf("\n");
        DEBUG_PRINTF("  exits:");
        for (u32 i = 0; i < r_i.exits.size(); i++) {
            printf(" %zu", g[r_i.exits[i]].index);
        }
        printf("\n");
        DEBUG_PRINTF("  all:");
        for (u32 i = 0; i < r_i.full.size(); i++) {
            printf(" %zu", g[r_i.full[i]].index);
        }
        printf("\n");
    }
    #endif
}

static
bool validateXSL(const NGHolder &g,
                 const unordered_map<NFAVertex, u32> &regions,
                 const u32 region, const CharReach &escapes, u32 *bad_region) {
    /* need to check that the escapes escape all of the graph past region */
    u32 first_bad_region = ~0U;
    for (auto v : vertices_range(g)) {
        u32 v_region = regions.at(v);
        if (!is_special(v, g) && v_region > region &&
            (escapes & g[v].char_reach).any()) {
            DEBUG_PRINTF("problem with escapes for %zu\n", g[v].index);
            first_bad_region = MIN(first_bad_region, v_region);
        }
    }

    if (first_bad_region != ~0U) {
        *bad_region = first_bad_region;
        return false;
    }

    return true;
}

static
bool validateEXSL(const NGHolder &g,
                  const unordered_map<NFAVertex, u32> &regions,
                  const u32 region, const CharReach &escapes,
                  const NGHolder &prefix, u32 *bad_region) {
    /* EXSL: To be a valid EXSL with escapes e, we require that all states
     * go dead after /[e][^e]*{subsequent prefix match}/.
     */

    /* TODO: this is overly conservative as it allow partial matches from the
     * prefix to be considered even when the tail has processed some [^e] */

    u32 first_bad_region = ~0U;
    const vector<CharReach> escapes_vec(1, escapes);
    const vector<CharReach> notescapes_vec(1, ~escapes);

    flat_set<NFAVertex> states;
    /* turn on all states past the prefix */
    DEBUG_PRINTF("region %u is cutover\n", region);
    for (auto v : vertices_range(g)) {
        if (!is_special(v, g) && regions.at(v) > region) {
            states.insert(v);
        }
    }

    /* process the escapes */
    states = execute_graph(g, escapes_vec, states);

    /* flood with any number of not escapes */
    flat_set<NFAVertex> prev_states;
    while (prev_states != states) {
        prev_states = states;
        states = execute_graph(g, notescapes_vec, states);
        insert(&states, prev_states);
    }

    /* find input starts to use for when we are running the prefix through as
     * when the escape character arrives we may be in matching the prefix
     * already */
    flat_set<NFAVertex> prefix_start_states;
    for (auto v : vertices_range(prefix)) {
        if (v != prefix.accept && v != prefix.acceptEod
            /* and as we have already made it past the prefix once */
            && v != prefix.start) {
            prefix_start_states.insert(v);
        }
    }

    prefix_start_states =
        execute_graph(prefix, escapes_vec, prefix_start_states);

    assert(contains(prefix_start_states, prefix.startDs));
    /* see what happens after we feed it the prefix */
    states = execute_graph(g, prefix, prefix_start_states, states);

    for (auto v : states) {
        assert(v != g.accept && v != g.acceptEod); /* no cr -> should never be
                                                    * on */
        DEBUG_PRINTF("state still active\n");
        first_bad_region = MIN(first_bad_region, regions.at(v));
    }

    if (first_bad_region != ~0U) {
        *bad_region = first_bad_region;
        return false;
    }

    return true;
}

static
bool isPossibleLock(const NGHolder &g,
                    map<u32, region_info>::const_iterator region,
                    const map<u32, region_info> &info,
                    CharReach *escapes_out) {
    /* TODO: we could also check for self-loops on curr region */

    /* TODO: some straw-walking logic. lowish priority has we know there can
     * only be optional regions between us and the cyclic */

    assert(region != info.end());
    map<u32, region_info>::const_iterator next_region = region;
    ++next_region;
    if (next_region == info.end()) {
        assert(0); /* odd */
        return false;
    }

    const region_info &next_info = next_region->second;
    if (next_info.enters.empty()) {
        assert(0); /* odd */
        return false;
    }

    if (next_info.full.size() == 1 && !next_info.dag) {
       *escapes_out = ~g[next_info.full.front()].char_reach;
       return true;
    }

    return false;
}

static
unique_ptr<NGHolder>
makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> &regions,
           const region_info &curr, const region_info &next,
           bool renumber = true) {
    const vector<NFAVertex> &curr_exits = curr.exits;
    const vector<NFAVertex> &next_enters = next.enters;

    assert(!next_enters.empty());
    assert(!curr_exits.empty());

    unique_ptr<NGHolder> prefix_ptr = ue2::make_unique<NGHolder>();
    NGHolder &prefix = *prefix_ptr;

    deque<NFAVertex> lhs_verts;
    insert(&lhs_verts, lhs_verts.end(), vertices(g));

    unordered_map<NFAVertex, NFAVertex> lhs_map; // g -> prefix
    fillHolder(&prefix, g, lhs_verts, &lhs_map);
    prefix.kind = NFA_OUTFIX;

    // We need a reverse mapping to track regions.
    unordered_map<NFAVertex, NFAVertex> rev_map; // prefix -> g
    for (const auto &e : lhs_map) {
        rev_map.emplace(e.second, e.first);
    }

    clear_in_edges(prefix.accept, prefix);
    clear_in_edges(prefix.acceptEod, prefix);
    add_edge(prefix.accept, prefix.acceptEod, prefix);

    assert(!next_enters.empty());
    assert(next_enters.front() != NGHolder::null_vertex());
    u32 dead_region = regions.at(next_enters.front());
    DEBUG_PRINTF("curr_region %u, dead_region %u\n",
                 regions.at(curr_exits.front()), dead_region);
    for (auto v : inv_adjacent_vertices_range(next_enters.front(), g)) {
        if (regions.at(v) >= dead_region) {
            continue;
        }
        /* add edge to new accepts */
        NFAVertex p_v = lhs_map[v];
        add_edge(p_v, prefix.accept, prefix);
    }

    assert(in_degree(prefix.accept, prefix) != 0);

    /* prune everything past the picked region */
    vector<NFAVertex> to_clear;
    assert(contains(lhs_map, curr_exits.front()));
    NFAVertex p_u = lhs_map[curr_exits.front()];
    DEBUG_PRINTF("p_u: %zu\n", prefix[p_u].index);
    for (auto p_v : adjacent_vertices_range(p_u, prefix)) {
        auto v = rev_map.at(p_v);
        if (p_v == prefix.accept || regions.at(v) < dead_region) {
            continue;
        }
        to_clear.push_back(p_v);
    }

    for (auto v : to_clear) {
        DEBUG_PRINTF("clearing in_edges on %zu\n", prefix[v].index);
        clear_in_edges(v, prefix);
    }

    pruneUseless(prefix, renumber /* sometimes we want no renumber to keep
                                     depth map valid */);

    assert(num_vertices(prefix) > N_SPECIALS);
    return prefix_ptr;
}

static
void replaceTempSomSlot(ReportManager &rm, NGHolder &g, u32 real_slot) {
    const u32 temp_slot = UINT32_MAX;
    /* update the som slot on the prefix report */
    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
        auto &reports = g[v].reports;
        assert(reports.size() == 1);
        Report ir = rm.getReport(*reports.begin());
        if (ir.onmatch != temp_slot) {
            continue;
        }
        ir.onmatch = real_slot;
        ReportID rep = rm.getInternalId(ir);

        assert(reports.size() == 1);
        reports.clear();
        reports.insert(rep);
    }
}

static
void setPrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type,
                      u32 som_loc, const vector<DepthMinMax> &depths,
                      bool prefix_by_rev) {
    Report ir = makeCallback(0U, 0);
    ir.type = ir_type;
    ir.onmatch = som_loc;

    /* add report for storing in som location on new accepts */
    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
        if (prefix_by_rev) {
            ir.somDistance = MO_INVALID_IDX; /* will be populated properly
                                              * later */
        } else {
            const DepthMinMax &d = depths.at(g[v].index);
            assert(d.min == d.max);
            ir.somDistance = d.max;
        }
        ReportID rep = rm.getInternalId(ir);

        auto &reports = g[v].reports;
        reports.clear();
        reports.insert(rep);
    }
}

static
void updatePrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type) {
    /* update the som action on the prefix report */
    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
        auto &reports = g[v].reports;
        assert(reports.size() == 1);
        Report ir = rm.getReport(*reports.begin());
        ir.type = ir_type;
        ReportID rep = rm.getInternalId(ir);

        assert(reports.size() == 1);
        reports.clear();
        reports.insert(rep);
    }
}

static
void updatePrefixReportsRevNFA(ReportManager &rm, NGHolder &g,
                               u32 rev_comp_id) {
    /* update the action on the prefix report, to refer to a reverse nfa,
     * report type is also adjusted. */
    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
        auto &reports = g[v].reports;
        assert(reports.size() == 1);
        Report ir = rm.getReport(*reports.begin());
        switch (ir.type) {
        case INTERNAL_SOM_LOC_SET:
            ir.type = INTERNAL_SOM_LOC_SET_SOM_REV_NFA;
            break;
        case INTERNAL_SOM_LOC_SET_IF_UNSET:
            ir.type = INTERNAL_SOM_LOC_SET_SOM_REV_NFA_IF_UNSET;
            break;
        case INTERNAL_SOM_LOC_SET_IF_WRITABLE:
            ir.type = INTERNAL_SOM_LOC_SET_SOM_REV_NFA_IF_WRITABLE;
            break;
        default:
            assert(0);
            break;
        }

        ir.revNfaIndex = rev_comp_id;
        ReportID rep = rm.getInternalId(ir);

        assert(reports.size() == 1);
        reports.clear();
        reports.insert(rep);
    }
}

static
void setMidfixReports(ReportManager &rm, const som_plan &item,
                      const u32 som_slot_in, const u32 som_slot_out) {
    assert(item.prefix);
    NGHolder &g = *item.prefix;

    Report ir = makeCallback(0U, 0);
    ir.type = item.is_reset ? INTERNAL_SOM_LOC_COPY
                            : INTERNAL_SOM_LOC_COPY_IF_WRITABLE;
    ir.onmatch = som_slot_out;
    ir.somDistance = som_slot_in;
    ReportID rep = rm.getInternalId(ir);

    /* add report for storing in som location on new accepts */
    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
        auto &reports = g[v].reports;
        reports.clear();
        reports.insert(rep);
    }
}

static
bool finalRegion(const NGHolder &g,
                 const unordered_map<NFAVertex, u32> &regions,
                 NFAVertex v) {
    u32 region = regions.at(v);
    for (auto w : adjacent_vertices_range(v, g)) {
        if (w != g.accept && w != g.acceptEod && regions.at(w) != region) {
            return false;
        }
    }

    return true;
}

static
void replaceExternalReportsWithSomRep(ReportManager &rm, NGHolder &g,
                                      NFAVertex v, ReportType ir_type,
                                      u64a param) {
    assert(!g[v].reports.empty());

    flat_set<ReportID> r_new;

    for (const ReportID &report_id : g[v].reports) {
        Report ir = rm.getReport(report_id);

        if (ir.type != EXTERNAL_CALLBACK) {
            /* we must have already done whatever magic we needed to do to this
             * report */
            r_new.insert(report_id);
            continue;
        }

        ir.type = ir_type;
        ir.somDistance = param;
        ReportID rep = rm.getInternalId(ir);

        DEBUG_PRINTF("vertex %zu, replacing report %u with %u (type %u)\n",
                     g[v].index, report_id, rep, ir_type);
        r_new.insert(rep);
    }
    g[v].reports = r_new;
}

/* updates the reports on all vertices leading to the sink */
static
void makeSomRelReports(ReportManager &rm, NGHolder &g, NFAVertex sink,
                       const vector<DepthMinMax> &depths) {
    for (auto v : inv_adjacent_vertices_range(sink, g)) {
        if (v == g.accept) {
            continue;
        }

        const DepthMinMax &d = depths.at(g[v].index);
        assert(d.min == d.max);
        replaceExternalReportsWithSomRep(rm, g, v, EXTERNAL_CALLBACK_SOM_REL,
                                         d.min);
    }
}

/* updates the reports on all the provided vertices */
static
void makeSomRelReports(ReportManager &rm, NGHolder &g,
                       const vector<NFAVertex> &to_update,
                       const vector<DepthMinMax> &depths) {
    for (auto v : to_update) {
        const DepthMinMax &d = depths.at(g[v].index);
        assert(d.min == d.max);
        replaceExternalReportsWithSomRep(rm, g, v, EXTERNAL_CALLBACK_SOM_REL,
                                         d.min);
    }
}

static
void makeSomAbsReports(ReportManager &rm, NGHolder &g, NFAVertex sink) {
    for (auto v : inv_adjacent_vertices_range(sink, g)) {
        if (v == g.accept) {
            continue;
        }
        replaceExternalReportsWithSomRep(rm, g, v, EXTERNAL_CALLBACK_SOM_ABS,
                                         0);
    }
}

static
void updateReportToUseRecordedSom(ReportManager &rm, NGHolder &g, u32 som_loc) {
    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
        replaceExternalReportsWithSomRep(rm, g, v, EXTERNAL_CALLBACK_SOM_STORED,
                                         som_loc);
    }
    for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
        if (v == g.accept) {
            continue;
        }
        replaceExternalReportsWithSomRep(rm, g, v, EXTERNAL_CALLBACK_SOM_STORED,
                                         som_loc);
    }
}

static
void updateReportToUseRecordedSom(ReportManager &rm, NGHolder &g,
                                  const vector<NFAVertex> &to_update,
                                  u32 som_loc) {
    for (auto v : to_update) {
        replaceExternalReportsWithSomRep(rm, g, v, EXTERNAL_CALLBACK_SOM_STORED,
                                         som_loc);
    }
}

static
bool createEscaper(NG &ng, const NGHolder &prefix, const CharReach &escapes,
                   u32 som_loc) {
    ReportManager &rm = ng.rm;

    /* escaper = /prefix[^escapes]*[escapes]/ */
    DEBUG_PRINTF("creating escaper for %u\n", som_loc);
    NGHolder h;
    cloneHolder(h, prefix);
    assert(h.kind == NFA_OUTFIX);

    NFAVertex u = add_vertex(h);
    h[u].char_reach = ~escapes;

    NFAVertex v = add_vertex(h);
    h[v].char_reach = escapes;

    for (auto w : inv_adjacent_vertices_range(h.accept, h)) {
        add_edge(w, u, h);
        add_edge(w, v, h);
        h[w].reports.clear();
    }

    clear_in_edges(h.accept, h);

    add_edge(u, v, h);
    add_edge(u, u, h);
    add_edge(v, h.accept, h);

    Report ir = makeCallback(0U, 0);
    ir.type = INTERNAL_SOM_LOC_MAKE_WRITABLE;
    ir.onmatch = som_loc;
    h[v].reports.insert(rm.getInternalId(ir));
    return ng.addHolder(h);
}

static
void fillHolderForLockCheck(NGHolder *out, const NGHolder &g,
                            const map<u32, region_info> &info,
                            map<u32, region_info>::const_iterator picked) {
    /* NOTE: This is appropriate for firstMatchIsFirst */
    DEBUG_PRINTF("prepping for lock check\n");

    NGHolder &midfix = *out;

    map<NFAVertex, NFAVertex> v_map;
    v_map[g.start] = midfix.start;
    v_map[g.startDs] = midfix.startDs;

    /* include the lock region */
    assert(picked != info.end());
    auto graph_last = next(picked);

    assert(!graph_last->second.dag);
    assert(graph_last->second.full.size() == 1);

    for (auto jt = graph_last; ; --jt) {
        DEBUG_PRINTF("adding r %u to midfix\n", jt->first);

        /* add all vertices in region, create mapping */
        for (auto v : jt->second.full) {
            DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index);
            if (contains(v_map, v)) {
                continue;
            }

            /* treat all virtual starts as happening anywhere, so that the
             * virtual start is not counted as part of the SoM */
            if (is_virtual_start(v, g)) {
                v_map[v] = midfix.startDs;
                continue;
            }

            NFAVertex vnew = add_vertex(g[v], midfix);
            v_map[v] = vnew;
        }

        /* add edges leaving region verts based on mapping */
        for (auto v : jt->second.full) {
            NFAVertex u = v_map[v];
            for (auto w : adjacent_vertices_range(v, g)) {
                if (w == g.accept || w == g.acceptEod) {
                    add_edge_if_not_present(u, midfix.accept, midfix);
                    continue;
                }
                if (!contains(v_map, w)) {
                    add_edge_if_not_present(u, midfix.accept, midfix);
                } else {
                    add_edge_if_not_present(u, v_map[w], midfix);
                }
            }
        }

        if (jt == info.begin()) {
            break;
        }
    }

    /* add edges from startds to the enters of all the initial optional
     * regions and the first mandatory region. */
    for (auto jt = info.begin(); ; ++jt) {
        for (auto enter : jt->second.enters) {
            assert(contains(v_map, enter));
            NFAVertex v = v_map[enter];
            add_edge_if_not_present(midfix.startDs, v, midfix);
        }

        if (!jt->second.optional) {
            break;
        }

        if (jt == graph_last) {
            /* all regions are optional - add a direct edge to accept */
            add_edge_if_not_present(midfix.startDs, midfix.accept, midfix);
            break;
        }
    }

    assert(in_degree(midfix.accept, midfix));
    renumber_vertices(midfix);
}

static
void fillRoughMidfix(NGHolder *out, const NGHolder &g,
                     const unordered_map<NFAVertex, u32> &regions,
                     const map<u32, region_info> &info,
                     map<u32, region_info>::const_iterator picked) {
    /* as we are not the first prefix, we are probably not acyclic. We need to
     * generate an acyclic holder to acts a fake prefix to sentClearsTail.
     * This will result in a more conservative estimate. */
    /* NOTE: This is not appropriate for firstMatchIsFirst */
    NGHolder &midfix = *out;
    add_edge(midfix.startDs, midfix.accept, midfix);

    map<NFAVertex, NFAVertex> v_map;

    map<u32, region_info>::const_iterator jt = picked;
    for (; jt->second.dag; --jt) {
        DEBUG_PRINTF("adding r %u to midfix\n", jt->first);
        if (!jt->second.optional) {
            clear_out_edges(midfix.startDs, midfix);
            add_edge(midfix.startDs, midfix.startDs, midfix);
        }

        /* add all vertices in region, create mapping */
        for (auto v : jt->second.full) {
            DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index);
            NFAVertex vnew = add_vertex(g[v], midfix);
            v_map[v] = vnew;
        }

        /* add edges leaving region verts based on mapping */
        for (auto v : jt->second.full) {
            NFAVertex u = v_map[v];
            for (auto w : adjacent_vertices_range(v, g)) {
                if (w == g.accept || w == g.acceptEod) {
                    continue;
                }
                if (!contains(v_map, w)) {
                    add_edge_if_not_present(u, midfix.accept, midfix);
                } else {
                    add_edge_if_not_present(u, v_map[w], midfix);
                }
            }
        }

        /* add edges from startds to enters */
        for (auto enter : jt->second.enters) {
            assert(contains(v_map, enter));
            NFAVertex v = v_map[enter];
            add_edge(midfix.startDs, v, midfix);
        }

        if (jt == info.begin()) {
            break;
        }
    }

    /* we can include the exits of the regions leading in */
    if (!jt->second.dag) {
        u32 first_early_region = jt->first;
        clear_out_edges(midfix.startDs, midfix);
        add_edge(midfix.startDs, midfix.startDs, midfix);

        do {
            for (auto v : jt->second.exits) {
                DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index);
                NFAVertex vnew = add_vertex(g[v], midfix);
                v_map[v] = vnew;

                /* add edges from startds to new vertices */
                add_edge(midfix.startDs, vnew, midfix);
            }

            /* add edges leaving region verts based on mapping */
            for (auto v : jt->second.exits) {
                NFAVertex u = v_map[v];
                for (auto w : adjacent_vertices_range(v, g)) {
                    if (w == g.accept || w == g.acceptEod
                        || regions.at(w) <= first_early_region) {
                        continue;
                    }
                    if (!contains(v_map, w)) {
                        add_edge_if_not_present(u, midfix.accept, midfix);
                    } else {
                        add_edge_if_not_present(u, v_map[w], midfix);
                    }
                }
            }
        } while (jt->second.optional && jt != info.begin() && (jt--)->first);

        if (jt->second.optional) {
            assert(!jt->second.exits.empty());
            NFAVertex v = v_map[jt->second.exits.front()];
            for (auto w : adjacent_vertices_range(v, midfix)) {
                add_edge(midfix.startDs, w, midfix);
            }
        }
    }
}

static
bool beginsWithDotStar(const NGHolder &g) {
    bool hasDot = false;

    // We can ignore the successors of start, as matches that begin there will
    // necessarily have a SOM of 0.

    set<NFAVertex> succ;
    insert(&succ, adjacent_vertices(g.startDs, g));
    succ.erase(g.startDs);

    for (auto v : succ) {
        // We want 'dot' states that aren't virtual starts.
        if (g[v].char_reach.all() &&
                !g[v].assert_flags) {
            hasDot = true;
            set<NFAVertex> dotsucc;
            insert(&dotsucc, adjacent_vertices(v, g));
            if (dotsucc != succ) {
                DEBUG_PRINTF("failed dot-star succ check\n");
                return false;
            }
        }
    }

    if (hasDot) {
        DEBUG_PRINTF("begins with dot-star\n");
    }
    return hasDot;
}

static
bool buildMidfix(NG &ng, const som_plan &item, const u32 som_slot_in,
                 const u32 som_slot_out) {
    assert(item.prefix);
    assert(hasCorrectlyNumberedVertices(*item.prefix));

    /* setup escaper for second som_location if required */
    if (item.escapes.any()) {
        if (!createEscaper(ng, *item.prefix, item.escapes, som_slot_out)) {
            return false;
        }
    }

    /* ensure we copy som from prev loc */
    setMidfixReports(ng.rm, item, som_slot_in, som_slot_out);

    /* add second prefix/1st midfix */
    if (!ng.addHolder(*item.prefix)) {
        DEBUG_PRINTF("---addHolder failed---\n");
        return false;
    }

    return true;
}

static
bool isMandRegionBetween(map<u32, region_info>::const_iterator a,
                         map<u32, region_info>::const_iterator b) {
    while (b != a) {
        if (!b->second.optional) {
            return true;
        }
        --b;
    }

    return false;
}

// Attempts to advance the current plan. Returns true if we advance to the end
// (woot!); updates picked, plan and bad_region.
static
bool advancePlan(const NGHolder &g,
                 const unordered_map<NFAVertex, u32> &regions,
                 const NGHolder &prefix, bool stuck,
                 map<u32, region_info>::const_iterator &picked,
                 const map<u32, region_info>::const_iterator furthest,
                 const map<u32, region_info>::const_iterator furthest_lock,
                 const CharReach &next_escapes, som_plan &plan,
                 u32 *bad_region) {
    u32 bad_region_r = 0;
    u32 bad_region_x = 0;
    u32 bad_region_e = 0;
    DEBUG_PRINTF("curr %u\n", picked->first);

    if (sentClearsTail(g, regions, prefix, furthest->first, &bad_region_r)) {
        plan.is_reset = true;
        picked = furthest;
        DEBUG_PRINTF("Prefix clears tail, woot!\n");
        return true;
    } else {
        DEBUG_PRINTF("Reset failed, first bad region %u\n", bad_region_r);
    }

    if (stuck) {
        u32 to_region = furthest_lock->first;
        if (validateXSL(g, regions, to_region, next_escapes, &bad_region_x)) {
            DEBUG_PRINTF("XSL\n");
            picked = furthest_lock;
            plan.escapes = next_escapes;
            return true;
        } else {
            DEBUG_PRINTF("XSL failed, first bad region %u\n", bad_region_x);
        }

        if (validateEXSL(g, regions, to_region, next_escapes, prefix,
                         &bad_region_e)) {
            DEBUG_PRINTF("EXSL\n");
            picked = furthest_lock;
            plan.escapes = next_escapes;
            return true;
        } else {
            DEBUG_PRINTF("EXSL failed, first bad region %u\n", bad_region_e);
        }
    } else {
        DEBUG_PRINTF("!stuck, skipped XSL and EXSL\n");
    }

    assert(!plan.is_reset);

    *bad_region = max(bad_region_x, bad_region_e);
    if (bad_region_r >= *bad_region) {
        *bad_region = bad_region_r;
        plan.is_reset = true;
        plan.escapes.clear();
        picked = furthest;
    } else {
        picked = furthest_lock;
        plan.escapes = next_escapes;
    }

    DEBUG_PRINTF("first bad region now %u\n", *bad_region);
    return false;
}

static
bool addPlan(vector<som_plan> &plan, u32 parent) {
    DEBUG_PRINTF("adding plan %zu with parent %u\n", plan.size(),
                 parent);

    if (plan.size() >= MAX_SOM_PLANS) {
        DEBUG_PRINTF("too many plans!\n");
        return false;
    }

    plan.emplace_back(nullptr, CharReach(), false, parent);
    return true;
}

// Fetches all preds of {accept, acceptEod} for this graph.
static
void addReporterVertices(const NGHolder &g, vector<NFAVertex> &reporters) {
    set<NFAVertex> tmp;
    insert(&tmp, inv_adjacent_vertices(g.accept, g));
    insert(&tmp, inv_adjacent_vertices(g.acceptEod, g));
    tmp.erase(g.accept);

#ifdef DEBUG
    DEBUG_PRINTF("add reporters:");
    for (UNUSED auto v : tmp) {
        printf(" %zu", g[v].index);
    }
    printf("\n");
#endif

    reporters.insert(reporters.end(), tmp.begin(), tmp.end());
}

// Fetches all preds of {accept, acceptEod} in this region.
static
void addReporterVertices(const region_info &r, const NGHolder &g,
                         vector<NFAVertex> &reporters) {
    for (auto v : r.exits) {
        if (edge(v, g.accept, g).second || edge(v, g.acceptEod, g).second) {
            DEBUG_PRINTF("add reporter %zu\n", g[v].index);
            reporters.push_back(v);
        }
    }
}

// Fetches the mappings of all preds of {accept, acceptEod} in this region.
static
void addMappedReporterVertices(const region_info &r, const NGHolder &g,
                        const unordered_map<NFAVertex, NFAVertex> &mapping,
                        vector<NFAVertex> &reporters) {
    for (auto v : r.exits) {
        if (edge(v, g.accept, g).second || edge(v, g.acceptEod, g).second) {
            DEBUG_PRINTF("adding v=%zu\n", g[v].index);
            auto it = mapping.find(v);
            assert(it != mapping.end());
            reporters.push_back(it->second);
        }
    }
}

// Clone a version of the graph, but only including the in-edges of `enter'
// from earlier regions.
static
void cloneGraphWithOneEntry(NGHolder &out, const NGHolder &g,
                       const unordered_map<NFAVertex, u32> &regions,
                       NFAVertex entry, const vector<NFAVertex> &enters,
                       unordered_map<NFAVertex, NFAVertex> &orig_to_copy) {
    orig_to_copy.clear();
    cloneHolder(out, g, &orig_to_copy);

    assert(contains(orig_to_copy, entry));
    const u32 region = regions.at(entry);

    for (auto v : enters) {
        if (v == entry) {
            continue;
        }
        assert(contains(orig_to_copy, v));

        for (auto u : inv_adjacent_vertices_range(v, g)) {
            if (regions.at(u) < region) {
                assert(edge(orig_to_copy[u], orig_to_copy[v], out).second);
                remove_edge(orig_to_copy[u], orig_to_copy[v], out);
            }
        }
    }

    pruneUseless(out);
}

static
void expandGraph(NGHolder &g, unordered_map<NFAVertex, u32> &regions,
                 vector<NFAVertex> &enters) {
    assert(!enters.empty());
    const u32 split_region = regions.at(enters.front());

    vector<NFAVertex> new_enters;

    // Gather the list of vertices in the split region and subsequent regions.
    vector<NFAVertex> tail_vertices;
    for (auto v : vertices_range(g)) {
        if (is_special(v, g) || regions.at(v) < split_region) {
            continue;
        }
        tail_vertices.push_back(v);
    }

    for (auto enter : enters) {
        DEBUG_PRINTF("processing enter %zu\n", g[enter].index);
        map<NFAVertex, NFAVertex> orig_to_copy;

        // Make a copy of all of the tail vertices, storing region info along
        // the way.
        for (auto v : tail_vertices) {
            auto v2 = clone_vertex(g, v);
            orig_to_copy[v] = v2;
            regions[v2] = regions.at(v);
        }

        // Wire up the edges: edges from previous regions come from the
        // original vertices, while edges internal to and beyond the split
        // region go to the copies.

        for (const auto &m : orig_to_copy) {
            NFAVertex v = m.first, v2 = m.second;

            for (const auto &e : out_edges_range(v, g)) {
                NFAVertex t = target(e, g);
                u32 t_region = regions.at(t);
                if (t_region >= split_region && !is_special(t, g)) {
                    assert(contains(orig_to_copy, t));
                    t = orig_to_copy[t];
                }
                add_edge_if_not_present(v2, t, g[e], g);
            }

            for (const auto &e : in_edges_range(v, g)) {
                NFAVertex u = source(e, g);
                if (regions.at(u) >= split_region && !is_special(u, g)) {
                    assert(contains(orig_to_copy, u));
                    u = orig_to_copy[u];
                }
                add_edge_if_not_present(u, v2, g[e], g);
            }

        }

        // Clear the in-edges from earlier regions of the OTHER enters for this
        // copy of the split region.
        for (auto v : enters) {
            if (v == enter) {
                continue;
            }

            remove_in_edge_if(orig_to_copy[v],
                              [&](const NFAEdge &e) {
                                    NFAVertex u = source(e, g);
                                    return regions.at(u) < split_region;
                              }, g);
        }

        new_enters.push_back(orig_to_copy[enter]);
    }

    // Remove the original set of tail vertices.
    remove_vertices(tail_vertices, g);
    pruneUseless(g);
    regions = assignRegions(g);

    enters.swap(new_enters);
}

static
bool doTreePlanningIntl(NGHolder &g,
            const unordered_map<NFAVertex, u32> &regions,
            const map<u32, region_info> &info,
            map<u32, region_info>::const_iterator picked, u32 bad_region,
            u32 parent_plan,
            const unordered_map<NFAVertex, NFAVertex> &copy_to_orig,
            vector<som_plan> &plan, const Grey &grey) {
    assert(picked != info.end());

    DEBUG_PRINTF("picked=%u\n", picked->first);
    DEBUG_PRINTF("parent is %u\n", parent_plan);

    map<u32, region_info>::const_iterator furthest;

    bool to_end = false;
    while (!to_end) {
        DEBUG_PRINTF("picked is %u\n", picked->first);
        DEBUG_PRINTF("first bad region now %u\n", bad_region);

        furthest = info.find(bad_region); /* first bad */
        if (furthest == info.end()) {
            DEBUG_PRINTF("no partition\n");
            return false;
        }
        --furthest; /* last region we can establish som for */

        if (furthest->first <= picked->first) {
            DEBUG_PRINTF("failed to make any progress\n");
            return false;
        }

        map<u32, region_info>::const_iterator furthest_lock = furthest;
        CharReach next_escapes;
        bool lock_found;
        /* The last possible lock in the range that we examine should be the
         * best. If the previous plan is a lock, this follow as any early lock
         * must have a reach that is a subset of the last plan's lock. If the
         * last plan is a resetting plan ..., ?is this true? */
        do {
            lock_found = isPossibleLock(g, furthest_lock, info,
                                          &next_escapes);
        } while (!lock_found && (--furthest_lock)->first > picked->first);
        DEBUG_PRINTF("lock possible? %d\n", (int)lock_found);

        if (lock_found && !isMandRegionBetween(picked, furthest_lock)) {
            lock_found = false;
        }

        if (!isMandRegionBetween(picked, furthest)) {
            return false;
        }

        /* There is no certainty that the som at a reset location will always
         * go forward */
        if (plan[parent_plan].is_reset && lock_found) {
            NGHolder midfix;
            DEBUG_PRINTF("checking if midfix is suitable for lock\n");
            fillHolderForLockCheck(&midfix, g, info, furthest_lock);

            if (!firstMatchIsFirst(midfix)) {
                DEBUG_PRINTF("not stuck\n");
                lock_found = false;
            }
        }

        if (!addPlan(plan, parent_plan)) {
            return false;
        }

        to_end = false;

        if (lock_found && next_escapes.none()) {
            picked = furthest_lock;
            to_end = true;
        }

        if (!to_end) {
            NGHolder conservative_midfix; /* for use in reset, exsl analysis */
            fillRoughMidfix(&conservative_midfix, g, regions, info, furthest);
            dumpHolder(conservative_midfix, 15, "som_pathmidfix", grey);

            u32 old_bad_region = bad_region;
            to_end = advancePlan(g, regions, conservative_midfix, lock_found,
                                 picked, furthest, furthest_lock, next_escapes,
                                 plan.back(), &bad_region);
            if (!to_end
                && bad_region <= old_bad_region) { /* we failed to progress */
                DEBUG_PRINTF("failed to make any progress\n");
                return false;
            }
        }

        /* handle direct edge to accepts from region */
        if (edge(furthest->second.exits.front(), g.accept, g).second
                || edge(furthest->second.exits.front(), g.acceptEod, g).second) {
            map<u32, region_info>::const_iterator it = furthest;
            do {
                addMappedReporterVertices(it->second, g, copy_to_orig,
                                          plan.back().reporters_in);
            } while (it != info.begin() && it->second.optional && (it--)->first);
        }

        /* create second prefix */
        plan.back().prefix = makePrefix(g, regions, furthest->second,
                                        next(furthest)->second);
        parent_plan = plan.size() - 1;
    }

    // The last region contributes reporters. If it's optional, the regions
    // before it do as well.
    map<u32, region_info>::const_reverse_iterator it = info.rbegin();
    do {
        DEBUG_PRINTF("add mapped reporters for region %u\n", it->first);
        addMappedReporterVertices(it->second, g, copy_to_orig,
                                  plan.back().reporters);
    } while (it->second.optional && it != info.rend() &&
             (++it)->first > furthest->first);

    return true;
}

static
bool doTreePlanning(NGHolder &g,
                    map<u32, region_info>::const_iterator presplit,
                    map<u32, region_info>::const_iterator picked,
                    vector<som_plan> &plan, const Grey &grey) {
    DEBUG_PRINTF("picked is %u\n", picked->first);
    DEBUG_PRINTF("presplit is %u\n", presplit->first);

    map<u32, region_info>::const_iterator splitter = next(presplit);
    vector<NFAVertex> enters = splitter->second.enters; // mutable copy
    DEBUG_PRINTF("problem region has %zu entry vertices\n", enters.size());

    if (enters.size() <= 1) {
        // TODO: Splitting a region with one entry won't get us anywhere, but
        // it shouldn't create buggy analyses either. See UE-1892.
        DEBUG_PRINTF("nothing to split\n");
        return false;
    }

    if (plan.size() + enters.size() > MAX_SOM_PLANS) {
        DEBUG_PRINTF("splitting this tree would hit the plan limit.\n");
        return false;
    }

    assert(!plan.empty());
    const u32 parent_plan = plan.size() - 1;

    // Make a copy of the graph, with the subgraph under each enter vertex
    // duplicated without the edges into the other enter vertices.
    // NOTE WELL: this will invalidate 'info' from the split point, but it's
    // OK... we don't use it after this.
    auto g_regions = assignRegions(g);
    expandGraph(g, g_regions, enters);
    dumpHolder(g, g_regions, 14, "som_expandedtree", grey);

    for (auto v : enters) {
        DEBUG_PRINTF("enter %zu\n", g[v].index);

        // For this entry vertex, construct a version of the graph without the
        // other entries in this region (g_path), and calculate its depths and
        // regions.

        NGHolder g_path;
        unordered_map<NFAVertex, NFAVertex> orig_to_copy;
        cloneGraphWithOneEntry(g_path, g, g_regions, v, enters, orig_to_copy);
        auto regions = assignRegions(g_path);
        dumpHolder(g_path, regions, 14, "som_treepath", grey);

        map<u32, region_info> path_info;
        buildRegionMapping(g_path, regions, path_info);

        // Translate 'picked' to the corresponding region iterator over the
        // g_path graph. we can't trust the numbering, so we use a vertex
        // instead.
        NFAVertex picked_v = picked->second.enters.front();
        assert(contains(orig_to_copy, picked_v));
        u32 picked_region = regions.at(orig_to_copy[picked_v]);
        map<u32, region_info>::const_iterator path_pick =
            path_info.find(picked_region);
        if (path_pick == path_info.end()) {
            assert(0); // odd
            return false;
        }

        // Similarly, find our bad_region.
        assert(contains(orig_to_copy, v));
        u32 bad_region = regions.at(orig_to_copy[v]);

        // It's possible that the region may have grown to include its
        // successors, in which case we (currently) run screaming. Just
        // checking the size should be sufficient here.
        if (picked->second.full.size() != path_pick->second.full.size()) {
            DEBUG_PRINTF("picked region has grown, bailing\n");
            return false;
        }

        // Construct reverse mapping from vertices in g_path to g.
        unordered_map<NFAVertex, NFAVertex> copy_to_orig;
        for (const auto &m : orig_to_copy) {
            copy_to_orig.insert(make_pair(m.second, m.first));
        }

        bool to_end = doTreePlanningIntl(g_path, regions, path_info, path_pick,
                                         bad_region, parent_plan,
                                         copy_to_orig, plan, grey);
        if (!to_end) {
            return false;
        }
    }

    return true;
}

enum dsp_behaviour {
    ALLOW_MODIFY_HOLDER,
    DISALLOW_MODIFY_HOLDER /* say no to tree planning */
};

static
bool doSomPlanning(NGHolder &g, bool stuck_in,
                   const unordered_map<NFAVertex, u32> &regions,
                   const map<u32, region_info> &info,
                   map<u32, region_info>::const_iterator picked,
                   vector<som_plan> &plan,
                   const Grey &grey,
                   dsp_behaviour behaviour = ALLOW_MODIFY_HOLDER) {
    DEBUG_PRINTF("in picked is %u\n", picked->first);

    /* Need to verify how far the lock covers */
    u32 bad_region;
    NGHolder *ap_pref = plan.back().prefix.get();
    NGHolder ap_temp;
    if (hasBigCycles(*ap_pref)) {
        fillRoughMidfix(&ap_temp, g, regions, info, picked);
        ap_pref = &ap_temp;
    }

    bool to_end = advancePlan(g, regions, *ap_pref, stuck_in, picked,
                              picked, picked, plan.back().escapes,
                              plan.back(), &bad_region);

    if (to_end) {
        DEBUG_PRINTF("advanced through the whole graph in one go!\n");
        addReporterVertices(g, plan.back().reporters);
        return true;
    }

    map<u32, region_info>::const_iterator prev_furthest = picked;
    map<u32, region_info>::const_iterator furthest;

    furthest = info.find(bad_region); /* first bad */
    if (furthest == info.begin() || furthest == info.end()) {
        DEBUG_PRINTF("no partition\n");
        return false;
    }
    --furthest; /* last region we can establish som for */

    if (furthest->first <= picked->first) {
    do_tree:
        /* unable to establish SoM past the last picked region */
        if (behaviour == DISALLOW_MODIFY_HOLDER) {
            /* tree planning mutates the graph */
            return false;
        }

        DEBUG_PRINTF("failed to make any progress\n");
        assert(!plan.empty());
        if (plan.size() == 1) {
            DEBUG_PRINTF("not handling initial alternations yet\n");
            return false;
        }
        plan.pop_back();
        return doTreePlanning(g, furthest, prev_furthest, plan, grey);
    }

    furthest = picked;
    while (!to_end) {
        prev_furthest = furthest;

        DEBUG_PRINTF("prev further is %u\n", prev_furthest->first);
        DEBUG_PRINTF("first bad region now %u\n", bad_region);

        furthest = info.find(bad_region); /* first bad */
        if (furthest == info.begin() || furthest == info.end()) {
            DEBUG_PRINTF("no partition\n");
            return false;
        }
        --furthest; /* last region we can establish som for */

        map<u32, region_info>::const_iterator furthest_lock = furthest;
        CharReach next_escapes;
        bool stuck;
        do {
            stuck = isPossibleLock(g, furthest_lock, info, &next_escapes);
        } while (!stuck && (--furthest_lock)->first > prev_furthest->first);
        DEBUG_PRINTF("lock possible? %d\n", (int)stuck);
        DEBUG_PRINTF("furthest_lock=%u\n", furthest_lock->first);

        if (stuck && !isMandRegionBetween(prev_furthest, furthest_lock)) {
            stuck = false;
        }

        if (!isMandRegionBetween(prev_furthest, furthest)) {
            DEBUG_PRINTF("no mand region between %u and %u\n",
                         prev_furthest->first, furthest->first);
            return false;
        }

        /* There is no certainty that the som at a reset location will always
         * go forward */
        if (plan.back().is_reset && stuck) {
            NGHolder midfix;
            fillHolderForLockCheck(&midfix, g, info, furthest_lock);

            DEBUG_PRINTF("checking if midfix is suitable for lock\n");
            if (!firstMatchIsFirst(midfix)) {
                DEBUG_PRINTF("not stuck\n");
                stuck = false;
            }
        }

        assert(!plan.empty());
        if (!addPlan(plan, plan.size() - 1)) {
            return false;
        }

        to_end = false;

        if (stuck && next_escapes.none()) {
            picked = furthest_lock;
            to_end = true;
        }

        if (!to_end) {
            NGHolder conservative_midfix; /* for use in reset, exsl analysis */
            fillRoughMidfix(&conservative_midfix, g, regions, info, furthest);

            u32 old_bad_region = bad_region;
            to_end = advancePlan(g, regions, conservative_midfix, stuck, picked,
                                 furthest, furthest_lock, next_escapes,
                                 plan.back(), &bad_region);

            if (!to_end
                && bad_region <= old_bad_region) { /* we failed to progress */
                goto do_tree;
            }
        }

        /* handle direct edge to accepts from region */
        if (edge(furthest->second.exits.front(), g.accept, g).second
            || edge(furthest->second.exits.front(), g.acceptEod, g).second) {
            map<u32, region_info>::const_iterator it = furthest;
            do {
                DEBUG_PRINTF("direct edge to accept from region %u\n",
                             it->first);
                addReporterVertices(it->second, g, plan.back().reporters_in);
            } while (it != info.begin() && it->second.optional
                     && (it--)->first);
        }

        /* create second prefix */
        plan.back().prefix = makePrefix(g, regions, furthest->second,
                                        next(furthest)->second);
    }
    DEBUG_PRINTF("(final) picked is %u\n", picked->first);

    // The last region contributes reporters. If it's optional, the regions
    // before it do as well.
    map<u32, region_info>::const_reverse_iterator it = info.rbegin();
    do {
        DEBUG_PRINTF("region %u contributes reporters to last plan\n",
                     it->first);
        addReporterVertices(it->second, g, plan.back().reporters);
    } while (it->second.optional && it != info.rend() &&
             (++it)->first > furthest->first);

    DEBUG_PRINTF("done!\n");
    return true;
}

static
void dumpSomPlan(UNUSED const NGHolder &g, UNUSED const som_plan &p,
                 UNUSED size_t num) {
#if defined(DEBUG) || defined(DUMP_PLANS)
    DEBUG_PRINTF("plan %zu: prefix=%p, escapes=%s, is_reset=%d, "
                 "parent=%u\n",
                 num, p.prefix.get(),
                 describeClass(p.escapes, 20, CC_OUT_TEXT).c_str(),
                 p.is_reset, p.parent);
    printf("  reporters:");
    for (auto v : p.reporters) {
        printf(" %zu", g[v].index);
    }
    printf("\n");
    printf("  reporters_in:");
    for (auto v : p.reporters_in) {
        printf(" %zu", g[v].index);
    }
    printf("\n");
#endif
}

/**
 * Note: if we fail to build a midfix/ng.addHolder, we throw a pattern too
 * large exception as (1) if previous ng modification have been applied (other
 * midfixes have been applied), ng will be an undefined state on return and (2)
 * if the head of a pattern cannot be implemented we are generally unable to
 * implement the full pattern.
 */
static
void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id,
                      NGHolder &g, vector<som_plan> &plan,
                      const u32 first_som_slot) {
    ReportManager &rm = ng.rm;
    SomSlotManager &ssm = ng.ssm;

    DEBUG_PRINTF("%zu plans\n", plan.size());
    assert(plan.size() <= MAX_SOM_PLANS);
    assert(!plan.empty());

    vector<u32> som_slots(plan.size());
    som_slots[0] = first_som_slot;

    // Root plan, which already has a SOM slot assigned (first_som_slot).
    dumpSomPlan(g, plan.front(), 0);
    dumpSomSubComponent(*plan.front().prefix, "04_som", expr.index, comp_id, 0,
                        ng.cc.grey);
    assert(plan.front().prefix);
    if (plan.front().escapes.any() && !plan.front().is_reset) {
        /* setup escaper for first som location */
        if (!createEscaper(ng, *plan.front().prefix, plan.front().escapes,
                           first_som_slot)) {
            throw CompileError(expr.index, "Pattern is too large.");
        }
    }

    assert(plan.front().reporters_in.empty());
    updateReportToUseRecordedSom(rm, g, plan.front().reporters, first_som_slot);

    // Tree of plans, encoded in a vector.
    vector<som_plan>::const_iterator it = plan.begin();
    for (++it; it != plan.end(); ++it) {
        const u32 plan_num = it - plan.begin();
        dumpSomPlan(g, *it, plan_num);
        dumpSomSubComponent(*it->prefix, "04_som", expr.index, comp_id,
                            plan_num, ng.cc.grey);

        assert(it->parent < plan_num);
        u32 som_slot_in = som_slots[it->parent];
        u32 som_slot_out = ssm.getSomSlot(*it->prefix, it->escapes,
                                          it->is_reset, som_slot_in);
        som_slots[plan_num] = som_slot_out;

        assert(!it->no_implement);
        if (!buildMidfix(ng, *it, som_slot_in, som_slot_out)) {
            throw CompileError(expr.index, "Pattern is too large.");
        }
        updateReportToUseRecordedSom(rm, g, it->reporters_in, som_slot_in);
        updateReportToUseRecordedSom(rm, g, it->reporters, som_slot_out);
    }

    /* create prefix to set the som_loc */
    if (!plan.front().no_implement) {
        renumber_vertices(*plan.front().prefix);
        assert(plan.front().prefix->kind == NFA_OUTFIX);
        if (!ng.addHolder(*plan.front().prefix)) {
            throw CompileError(expr.index, "Pattern is too large.");
        }
    }
}

static
void anchorStarts(NGHolder &g) {
    vector<NFAEdge> dead;
    for (const auto &e : out_edges_range(g.startDs, g)) {
        NFAVertex v = target(e, g);
        if (v == g.startDs) {
            continue;
        }
        add_edge_if_not_present(g.start, v, g[e], g);
        dead.push_back(e);
    }
    remove_edges(dead, g);
}

static
void setZeroReports(NGHolder &g) {
    set<NFAVertex> acceptors;
    insert(&acceptors, inv_adjacent_vertices(g.accept, g));
    insert(&acceptors, inv_adjacent_vertices(g.acceptEod, g));
    acceptors.erase(g.accept);

    for (auto v : vertices_range(g)) {
        auto &reports = g[v].reports;
        reports.clear();

        if (!contains(acceptors, v)) {
            continue;
        }

        // We use the report ID to store the offset adjustment used for virtual
        // starts.

        if (g[v].assert_flags & POS_FLAG_VIRTUAL_START) {
            reports.insert(1);
        } else {
            reports.insert(0);
        }
    }
}

/* updates the reports on all vertices leading to the sink */
static
void makeSomRevNfaReports(ReportManager &rm, NGHolder &g, NFAVertex sink,
                          const ReportID report, const u32 comp_id) {
    // Construct replacement report.
    Report ir = rm.getReport(report);
    ir.type = EXTERNAL_CALLBACK_SOM_REV_NFA;
    ir.revNfaIndex = comp_id;
    ReportID new_report = rm.getInternalId(ir);

    for (auto v : inv_adjacent_vertices_range(sink, g)) {
        if (v == g.accept) {
            continue;
        }

        auto &r = g[v].reports;
        if (contains(r, report)) {
            r.erase(report);
            r.insert(new_report);
        }
    }
}

static
void clearProperInEdges(NGHolder &g, const NFAVertex sink) {
    vector<NFAEdge> dead;
    for (const auto &e : in_edges_range(sink, g)) {
        if (source(e, g) == g.accept) {
            continue;
        }
        dead.push_back(e);
    }

    if (dead.empty()) {
        return;
    }

    remove_edges(dead, g);
    pruneUseless(g, false);
}

namespace {
struct SomRevNfa {
    SomRevNfa(NFAVertex s, ReportID r, bytecode_ptr<NFA> n)
        : sink(s), report(r), nfa(move(n)) {}
    NFAVertex sink;
    ReportID report;
    bytecode_ptr<NFA> nfa;
};
}

static
bytecode_ptr<NFA> makeBareSomRevNfa(const NGHolder &g,
                                    const CompileContext &cc) {
    // Create a reversed anchored version of this NFA which fires a zero report
    // ID on accept.
    NGHolder g_rev;
    reverseHolder(g, g_rev);
    anchorStarts(g_rev);
    setZeroReports(g_rev);

    // Prep for actual construction.
    renumber_vertices(g_rev);
    g_rev.kind = NFA_REV_PREFIX;
    reduceGraphEquivalences(g_rev, cc);
    removeRedundancy(g_rev, SOM_NONE);

    DEBUG_PRINTF("building a rev NFA with %zu vertices\n", num_vertices(g_rev));

    auto nfa = constructReversedNFA(g_rev, cc);
    if (!nfa) {
        return nfa;
    }

    // Set some useful properties.
    depth maxWidth = findMaxWidth(g);
    if (maxWidth.is_finite()) {
        nfa->maxWidth = (u32)maxWidth;
    } else {
        nfa->maxWidth = 0;
    }
    depth minWidth = findMinWidth(g);
    nfa->minWidth = (u32)minWidth;

    return nfa;
}

static
bool makeSomRevNfa(vector<SomRevNfa> &som_nfas, const NGHolder &g,
                   const ReportID report, const NFAVertex sink,
                   const CompileContext &cc) {
    // Clone the graph with ONLY the given report vertices on the given sink.
    NGHolder g2;
    cloneHolder(g2, g);
    clearProperInEdges(g2, sink == g.accept ? g2.acceptEod : g2.accept);
    pruneAllOtherReports(g2, report);

    if (in_degree(g2.accept, g2) == 0 && in_degree(g2.acceptEod, g2) == 1) {
        DEBUG_PRINTF("no work to do for this sink\n");
        return true;
    }

    renumber_vertices(g2); // for findMinWidth, findMaxWidth.

    auto nfa = makeBareSomRevNfa(g2, cc);
    if (!nfa) {
        DEBUG_PRINTF("couldn't build rev nfa\n");
        return false;
    }

    som_nfas.emplace_back(sink, report, move(nfa));
    return true;
}

static
bool doSomRevNfa(NG &ng, NGHolder &g, const CompileContext &cc) {
    ReportManager &rm = ng.rm;

    // FIXME might want to work on a graph without extra redundancy?
    depth maxWidth = findMaxWidth(g);
    DEBUG_PRINTF("maxWidth=%s\n", maxWidth.str().c_str());

    if (maxWidth > depth(ng.maxSomRevHistoryAvailable)) {
        DEBUG_PRINTF("too wide\n");
        return false;
    }

    set<ReportID> reports = all_reports(g);
    DEBUG_PRINTF("%zu reports\n", reports.size());

    // We distinguish between reports and accept/acceptEod sinks in order to
    // correctly handle cases which do different things on eod/normal accepts.
    // Later, it might be more elegant to do this with a single NFA and
    // multi-tops.

    vector<SomRevNfa> som_nfas;

    for (auto report : reports) {
        if (!makeSomRevNfa(som_nfas, g, report, g.accept, cc)) {
            return false;
        }
        if (!makeSomRevNfa(som_nfas, g, report, g.acceptEod, cc)) {
            return false;
        }
    }

    for (auto &som_nfa : som_nfas) {
        assert(som_nfa.nfa);

        // Transfer ownership of the NFA to the SOM slot manager.
        u32 comp_id = ng.ssm.addRevNfa(move(som_nfa.nfa), maxWidth);

        // Replace this report on 'g' with a SOM_REV_NFA report pointing at our
        // new component.
        makeSomRevNfaReports(rm, g, som_nfa.sink, som_nfa.report, comp_id);
    }

    if (ng.cc.streaming) {
        assert(ng.ssm.somHistoryRequired() <=
               max(cc.grey.maxHistoryAvailable, ng.maxSomRevHistoryAvailable));
    }

    return true;
}

static
u32 doSomRevNfaPrefix(NG &ng, const ExpressionInfo &expr, NGHolder &g,
                      const CompileContext &cc) {
    depth maxWidth = findMaxWidth(g);

    assert(maxWidth <= depth(ng.maxSomRevHistoryAvailable));
    assert(all_reports(g).size() == 1);

    auto nfa = makeBareSomRevNfa(g, cc);
    if (!nfa) {
        throw CompileError(expr.index, "Pattern is too large.");
    }

    if (ng.cc.streaming) {
        assert(ng.ssm.somHistoryRequired() <=
               max(cc.grey.maxHistoryAvailable, ng.maxSomRevHistoryAvailable));
    }

    return ng.ssm.addRevNfa(move(nfa), maxWidth);
}

static
bool is_literable(const NGHolder &g, NFAVertex v) {
    const CharReach &cr = g[v].char_reach;
    return cr.count() == 1 || cr.isCaselessChar();
}

static
void append(ue2_literal &s, const CharReach &cr) {
    assert(cr.count() == 1 || cr.isCaselessChar());
    s.push_back(cr.find_first(), cr.isCaselessChar());
}

static
map<u32, region_info>::const_iterator findLaterLiteral(const NGHolder &g,
                            const map<u32, region_info> &info,
                            map<u32, region_info>::const_iterator lower_bound,
                            ue2_literal &s_out, const Grey &grey) {
#define MIN_LITERAL_LENGTH 3
    s_out.clear();
    bool past_lower = false;
    ue2_literal s;
    map<u32, region_info>::const_iterator it;
    for (it = info.begin(); it != info.end(); ++it) {
        if (it == lower_bound) {
            past_lower = true;
        }
        if (!it->second.optional && it->second.dag
            && it->second.full.size() == 1
            && is_literable(g, it->second.full.front())) {
            append(s, g[it->second.full.front()].char_reach);

            if (s.length() >= grey.maxHistoryAvailable && past_lower) {
                goto exit;
            }
        } else {
            if (past_lower && it != lower_bound
                && s.length() >= MIN_LITERAL_LENGTH) {
                --it;
                goto exit;
            }
            s.clear();
        }
    }

    if (past_lower && it != lower_bound && s.length() >= MIN_LITERAL_LENGTH) {
        --it;
        s_out = s;
        return it;
    }
 exit:
    if (s.length() > grey.maxHistoryAvailable) {
        ue2_literal::const_iterator jt = s.end() - grey.maxHistoryAvailable;
        for (; jt != s.end(); ++jt) {
            s_out.push_back(*jt);
        }
    } else {
        s_out = s;
    }
    return it;
}

static
bool attemptToBuildChainAfterSombe(SomSlotManager &ssm, NGHolder &g,
                  const unordered_map<NFAVertex, u32> &regions,
                  const map<u32, region_info> &info,
                  map<u32, region_info>::const_iterator picked,
                  const Grey &grey,
                  vector<som_plan> *plan) {
    DEBUG_PRINTF("trying to chain from %u\n", picked->first);
    const u32 numSomLocsBefore = ssm.numSomSlots(); /* for rollback */

    shared_ptr<NGHolder> prefix = makePrefix(g, regions, picked->second,
                                             next(picked)->second);

    // Quick check to stop us from trying this on huge graphs, which causes us
    // to spend forever in ng_execute looking at cases that will most like
    // fail. See UE-2078.
    size_t prefix_size = num_vertices(*prefix);
    size_t total_size = num_vertices(g);
    assert(total_size >= prefix_size);
    if (total_size - prefix_size > MAX_SOMBE_CHAIN_VERTICES) {
        DEBUG_PRINTF("suffix has %zu vertices, fail\n",
                     total_size - prefix_size);
        return false;
    }

    clearReports(*prefix);
    for (auto u : inv_adjacent_vertices_range(prefix->accept, *prefix)) {
        (*prefix)[u].reports.insert(0);
    }

    dumpHolder(*prefix, 0, "full_haiglit_prefix", grey);

    CharReach escapes;
    bool stuck = isPossibleLock(g, picked, info, &escapes);
    if (stuck) {
        NGHolder gg;
        fillHolderForLockCheck(&gg, g, info, picked);

        stuck = firstMatchIsFirst(gg);
    }

    DEBUG_PRINTF("stuck = %d\n", (int)stuck);

    // Note: no-one should ever pay attention to the root plan's som_loc_in.
    plan->emplace_back(prefix, escapes, false, 0);
    plan->back().no_implement = true;

    dumpHolder(*plan->back().prefix, 22, "som_prefix", grey);

    /* don't allow tree planning to mutate the graph */
    if (!doSomPlanning(g, stuck, regions, info, picked, *plan, grey,
                       DISALLOW_MODIFY_HOLDER)) {
        // Rollback SOM locations.
        ssm.rollbackSomTo(numSomLocsBefore);

        DEBUG_PRINTF("fail to chain\n");
        return false;
    }

    return true;
}

static
void setReportOnHaigPrefix(RoseBuild &rose, NGHolder &h) {
    ReportID haig_report_id = rose.getNewNfaReport();
    DEBUG_PRINTF("setting report id of %u\n", haig_report_id);

    clearReports(h);
    for (auto u : inv_adjacent_vertices_range(h.accept, h)) {
        h[u].reports.clear();
        h[u].reports.insert(haig_report_id);
    }
}

static
bool tryHaig(RoseBuild &rose, NGHolder &g,
             const unordered_map<NFAVertex, u32> &regions,
             som_type som, u32 somPrecision,
             map<u32, region_info>::const_iterator picked,
             shared_ptr<raw_som_dfa> *haig, shared_ptr<NGHolder> *haig_prefix,
             const Grey &grey) {
    DEBUG_PRINTF("trying to build a haig\n");
    shared_ptr<NGHolder> prefix = makePrefix(g, regions, picked->second,
                                             next(picked)->second);
    prefix->kind = NFA_PREFIX;
    setReportOnHaigPrefix(rose, *prefix);
    dumpHolder(*prefix, 0, "haig_prefix", grey);
    vector<vector<CharReach> > triggers; /* empty for prefix */
    *haig = attemptToBuildHaig(*prefix, som, somPrecision, triggers, grey);
    if (!*haig) {
        DEBUG_PRINTF("failed to haig\n");
        return false;
    }
    *haig_prefix = prefix;
    return true;
}

static
void roseAddHaigLiteral(RoseBuild &tb, const shared_ptr<NGHolder> &prefix,
                        const shared_ptr<raw_som_dfa> &haig,
                        const ue2_literal &lit, const set<ReportID> &reports) {
    assert(prefix && haig);

    DEBUG_PRINTF("trying to build a sombe from %s\n", dumpString(lit).c_str());

    RoseInGraph ig;
    RoseInVertex s = add_vertex(RoseInVertexProps::makeStart(false), ig);
    RoseInVertex v = add_vertex(RoseInVertexProps::makeLiteral(lit), ig);

    add_edge(s, v, RoseInEdgeProps(prefix, haig, lit.length()), ig);

    assert(!reports.empty());
    RoseInVertex a = add_vertex(RoseInVertexProps::makeAccept(reports), ig);
    add_edge(v, a, RoseInEdgeProps(0U, 0U), ig);

    calcVertexOffsets(ig);

    UNUSED bool rv = tb.addSombeRose(ig);
    assert(rv); // TODO: recover from addRose failure
}

static
sombe_rv doHaigLitSom(NG &ng, NGHolder &g, const ExpressionInfo &expr,
                      u32 comp_id, som_type som,
                      const unordered_map<NFAVertex, u32> &regions,
                      const map<u32, region_info> &info,
                      map<u32, region_info>::const_iterator lower_bound) {
    DEBUG_PRINTF("entry\n");
    assert(g.kind == NFA_OUTFIX);
    const CompileContext &cc = ng.cc;
    ReportManager &rm = ng.rm;
    SomSlotManager &ssm = ng.ssm;

    if (!cc.grey.allowHaigLit) {
        return SOMBE_FAIL;
    }

    const u32 numSomLocsBefore = ssm.numSomSlots(); /* for rollback */
    u32 som_loc = ssm.getPrivateSomSlot();

    if (!checkViolet(rm, g, false, cc) && !isImplementableNFA(g, &rm, cc)) {
        // This is an optimisation: if we can't build a Haig from a portion of
        // the graph, then we won't be able to manage it as an outfix either
        // when we fall back.
        throw CompileError(expr.index, "Pattern is too large.");
    }

    while (1) {
        DEBUG_PRINTF("lower bound is %u\n", lower_bound->first);
        ue2_literal s;
        map<u32, region_info>::const_iterator lit
            = findLaterLiteral(g, info, lower_bound, s, cc.grey);
        if (lit == info.end()) {
            DEBUG_PRINTF("failed to find literal\n");
            ssm.rollbackSomTo(numSomLocsBefore);
            return SOMBE_FAIL;
        }
        DEBUG_PRINTF("test literal: %s [r=%u]\n", dumpString(s).c_str(),
                     lit->first);

        if (s.length() > MAX_MASK2_WIDTH && mixed_sensitivity(s)) {
            DEBUG_PRINTF("long & mixed-sensitivity, Rose can't handle this\n");
            lower_bound = lit;
            ++lower_bound;
            continue;
        }

        shared_ptr<raw_som_dfa> haig;
        shared_ptr<NGHolder> haig_prefix;
        map<u32, region_info>::const_iterator haig_reg = lit;

        if (edge(lit->second.exits.front(), g.acceptEod, g).second) {
            /* TODO: handle */
            ssm.rollbackSomTo(numSomLocsBefore);
            return SOMBE_FAIL;
        }

        advance(haig_reg, -(s32)s.length());

        if (!haig_reg->first && haig_reg->second.full.size() == 2) {
            /* just starts */

            /* TODO: make below assertion true, reset checks could be stronger
             * (12356)
             */
            /* assert(!attemptToBuildChainAfterSombe(ng, g, info, lit, cc.grey,
               &plan)); */

            lower_bound = lit;
            ++lower_bound;
            continue; /* somebody else should have been able to chain */
        }

        bool ok = true;
        set<ReportID> rep;
        if (next(lit) != info.end()) {
            /* non terminal literal */

            /* TODO: handle edges to accept ? */
            vector<som_plan> plan;
            if (edge(lit->second.exits.front(), g.accept, g).second) {
                insert(&rep, g[lit->second.exits.front()].reports);
                remove_edge(lit->second.exits.front(), g.accept, g);
                g[lit->second.exits.front()].reports.clear();

                /* Note: we can mess with the graph as this is the last literal
                 * we will find and on failure the graph will be thrown away */
            }

            ok = attemptToBuildChainAfterSombe(ssm, g, regions, info, lit,
                                               cc.grey, &plan);
            ok = ok && tryHaig(*ng.rose, g, regions, som, ssm.somPrecision(),
                               haig_reg, &haig, &haig_prefix, cc.grey);

            if (!ok) {
                DEBUG_PRINTF(":( going to next attempt\n");
                goto next_try;
            }

            implementSomPlan(ng, expr, comp_id, g, plan, som_loc);

            Report ir = makeCallback(0U, 0);
            assert(!plan.empty());
            if (plan.front().is_reset) {
                ir.type = INTERNAL_SOM_LOC_SET_FROM;
            } else {
                ir.type = INTERNAL_SOM_LOC_SET_FROM_IF_WRITABLE;
            }
            ir.onmatch = som_loc;
            rep.insert(rm.getInternalId(ir));
        } else {
            /* terminal literal */
            ok = tryHaig(*ng.rose, g, regions, som, ssm.somPrecision(), haig_reg,
                         &haig, &haig_prefix, cc.grey);

            /* find report */
            insert(&rep, g[lit->second.exits.front()].reports);

            /* TODO: som_loc is unused */
        }

        if (ok) {
            roseAddHaigLiteral(*ng.rose, haig_prefix, haig, s, rep);
            if (next(lit) != info.end()) {
                return SOMBE_HANDLED_INTERNAL;
            } else {
                ssm.rollbackSomTo(numSomLocsBefore);
                return SOMBE_HANDLED_ALL;
            }
        }
next_try:
        lower_bound = lit;
        ++lower_bound;
    }
    assert(0);
    return SOMBE_FAIL;
}

static
bool leadingLiterals(const NGHolder &g, set<ue2_literal> *lits,
                     set<NFAVertex> *terminals) {
    /* TODO: smarter (topo) */
#define MAX_LEADING_LITERALS 20
    set<NFAVertex> s_succ;
    insert(&s_succ, adjacent_vertices(g.start, g));

    set<NFAVertex> sds_succ;
    insert(&sds_succ, adjacent_vertices(g.startDs, g));

    if (!is_subset_of(s_succ, sds_succ)) {
        DEBUG_PRINTF("not floating\n");
        return false;
    }

    sds_succ.erase(g.startDs);

    map<NFAVertex, vector<ue2_literal> > curr;
    curr[g.startDs].push_back(ue2_literal());

    map<NFAVertex, set<NFAVertex> > seen;
    map<NFAVertex, vector<ue2_literal> > next;

    bool did_expansion = true;
    while (did_expansion) {
        did_expansion = false;
        u32 count = 0;
        assert(!curr.empty());
        for (const auto &m : curr) {
            const NFAVertex u = m.first;
            const vector<ue2_literal> &base = m.second;
            DEBUG_PRINTF("expanding from %zu\n", g[u].index);
            for (auto v : adjacent_vertices_range(u, g)) {
                if (v == g.startDs) {
                    continue;
                }
                if (contains(seen[u], v)) {
                    DEBUG_PRINTF("loop\n");
                    goto skip_to_next_terminal;
                }
                if (is_any_accept(v, g) || is_match_vertex(v, g)) {
                    DEBUG_PRINTF("match\n");
                    goto skip_to_next_terminal;
                }
                if (g[v].char_reach.count() > 2 * MAX_LEADING_LITERALS) {
                    DEBUG_PRINTF("wide\n");
                    goto skip_to_next_terminal;
                }
            }

            for (auto v : adjacent_vertices_range(u, g)) {
                assert(!contains(seen[u], v));
                if (v == g.startDs) {
                    continue;
                }
                insert(&seen[v], seen[u]);
                seen[v].insert(v);
                CharReach cr = g[v].char_reach;
                vector<ue2_literal> &out = next[v];

                DEBUG_PRINTF("expanding to %zu (|| = %zu)\n", g[v].index,
                             cr.count());
                for (size_t c = cr.find_first(); c != CharReach::npos;
                     c = cr.find_next(c)) {
                    bool nocase = ourisalpha(c) && cr.test(mytoupper(c))
                        && cr.test(mytolower(c));

                    if (nocase && (char)c == mytolower(c)) {
                        continue; /* uppercase already handled us */
                    }

                    for (const auto &lit : base) {
                        if (count >= MAX_LEADING_LITERALS) {
                            DEBUG_PRINTF("count %u\n", count);
                            goto exit;
                        }
                        did_expansion = true;
                        out.push_back(lit);
                        out.back().push_back(c, nocase);
                        count++;
                        if (out.back().length() > MAX_MASK2_WIDTH
                            && mixed_sensitivity(out.back())) {
                            goto exit;
                        }

                    }
                }
            }
            if (0) {
            skip_to_next_terminal:
                insert(&next[u], next[u].end(), base);
                count += base.size();
                if (count > MAX_LEADING_LITERALS) {
                    DEBUG_PRINTF("count %u\n", count);
                    goto exit;
                }
            }
        }

        curr.swap(next);
        next.clear();
    };
 exit:;
    for (const auto &m : curr) {
        NFAVertex t = m.first;
        if (t == g.startDs) {
            assert(curr.size() == 1);
            return false;
        }
        assert(!is_special(t, g));
        terminals->insert(t);
        insert(lits, m.second);
    }
    assert(lits->size() <= MAX_LEADING_LITERALS);
    return !lits->empty();
}

static
bool splitOffLeadingLiterals(const NGHolder &g, set<ue2_literal> *lit_out,
                             NGHolder *rhs) {
    DEBUG_PRINTF("looking for a leading literals\n");

    set<NFAVertex> terms;
    if (!leadingLiterals(g, lit_out, &terms)) {
        return false;
    }

    for (UNUSED const auto &lit : *lit_out) {
        DEBUG_PRINTF("literal is '%s' (len %zu)\n", dumpString(lit).c_str(),
                     lit.length());
    }

    /* need to validate that it is a clean split */
    assert(!terms.empty());
    set<NFAVertex> adj_term1;
    insert(&adj_term1, adjacent_vertices(*terms.begin(), g));
    for (auto v : terms) {
        DEBUG_PRINTF("term %zu\n", g[v].index);
        set<NFAVertex> temp;
        insert(&temp, adjacent_vertices(v, g));
        if (temp != adj_term1) {
            DEBUG_PRINTF("bad split\n");
            return false;
        }
    }

    unordered_map<NFAVertex, NFAVertex> rhs_map;
    vector<NFAVertex> pivots;
    insert(&pivots, pivots.end(), adj_term1);
    splitRHS(g, pivots, rhs, &rhs_map);

    assert(is_triggered(*rhs));
    return true;
}

static
void findBestLiteral(const NGHolder &g,
                     const unordered_map<NFAVertex, u32> &regions,
                     ue2_literal *lit_out, NFAVertex *v,
                     const CompileContext &cc) {
    map<u32, region_info> info;
    buildRegionMapping(g, regions, info, false);

    ue2_literal best;
    NFAVertex best_v = NGHolder::null_vertex();

    map<u32, region_info>::const_iterator lit = info.begin();
    while (1) {
        ue2_literal s;
        lit = findLaterLiteral(g, info, lit, s, cc.grey);
        if (lit == info.end()) {
            break;
        }
        DEBUG_PRINTF("test literal: %s [r=%u]\n", dumpString(s).c_str(),
                     lit->first);

        if (s.length() > MAX_MASK2_WIDTH && mixed_sensitivity(s)) {
            DEBUG_PRINTF("long & mixed-sensitivity, Rose can't handle this\n");
            ++lit;
            continue;
        }

        if (s.length() > best.length()) {
            best = s;
            assert(!lit->second.exits.empty());
            best_v = lit->second.exits[0];
        }

        ++lit;
    }

    lit_out->swap(best);
    *v = best_v;
}

static
bool splitOffBestLiteral(const NGHolder &g,
                         const unordered_map<NFAVertex, u32> &regions,
                         ue2_literal *lit_out, NGHolder *lhs, NGHolder *rhs,
                         const CompileContext &cc) {
    NFAVertex v = NGHolder::null_vertex();

    findBestLiteral(g, regions, lit_out, &v, cc);
    if (lit_out->empty()) {
        return false;
    }

    DEBUG_PRINTF("literal is '%s'\n", dumpString(*lit_out).c_str());

    unordered_map<NFAVertex, NFAVertex> lhs_map;
    unordered_map<NFAVertex, NFAVertex> rhs_map;

    splitGraph(g, v, lhs, &lhs_map, rhs, &rhs_map);

    DEBUG_PRINTF("v = %zu\n", g[v].index);

    return true;
}

/**
 * Replace the given graph's EXTERNAL_CALLBACK reports with
 * EXTERNAL_CALLBACK_SOM_PASS reports.
 */
void makeReportsSomPass(ReportManager &rm, NGHolder &g) {
    for (const auto &v : vertices_range(g)) {
        const auto &reports = g[v].reports;
        if (reports.empty()) {
            continue;
        }

        flat_set<ReportID> new_reports;
        for (const ReportID &id : reports) {
            const Report &report = rm.getReport(id);
            if (report.type != EXTERNAL_CALLBACK) {
                new_reports.insert(id);
                continue;
            }
            Report report2 = report;
            report2.type = EXTERNAL_CALLBACK_SOM_PASS;
            new_reports.insert(rm.getInternalId(report2));
        }

        g[v].reports = new_reports;
    }
}

static
bool doLitHaigSom(NG &ng, NGHolder &g, som_type som) {
    ue2_literal lit;
    shared_ptr<NGHolder> rhs = make_shared<NGHolder>();
    if (!rhs) {
        assert(0);
        throw std::bad_alloc();
    }
    if (!ng.cc.grey.allowLitHaig) {
        return false;
    }

    dumpHolder(g, 90, "lithaig_full", ng.cc.grey);

    if (!splitOffLeadingLiteral(g, &lit, &*rhs)) {
        DEBUG_PRINTF("no literal\n");
        return false;
    }

    if (lit.length() < ng.cc.grey.minRoseLiteralLength) {
        DEBUG_PRINTF("lit too short\n");
        return false;
    }

    assert(lit.length() <= MAX_MASK2_WIDTH || !mixed_sensitivity(lit));

    makeReportsSomPass(ng.rm, *rhs);

    dumpHolder(*rhs, 91, "lithaig_rhs", ng.cc.grey);

    vector<vector<CharReach> > triggers;
    triggers.push_back(as_cr_seq(lit));

    assert(rhs->kind == NFA_SUFFIX);
    shared_ptr<raw_som_dfa> haig
        = attemptToBuildHaig(*rhs, som, ng.ssm.somPrecision(), triggers,
                             ng.cc.grey, false /* lit implies adv som */);
    if (!haig) {
        DEBUG_PRINTF("failed to haig\n");
        return false;
    }
    DEBUG_PRINTF("haig %p\n", haig.get());

    RoseInGraph ig;
    RoseInVertex s = add_vertex(RoseInVertexProps::makeStart(false), ig);
    RoseInVertex v = add_vertex(RoseInVertexProps::makeLiteral(lit), ig);
    add_edge(s, v, RoseInEdgeProps(0, ROSE_BOUND_INF), ig);

    RoseInVertex a
        = add_vertex(RoseInVertexProps::makeAccept(set<ReportID>()), ig);
    add_edge(v, a, RoseInEdgeProps(haig), ig);

    calcVertexOffsets(ig);

    return ng.rose->addSombeRose(ig);
}

static
bool doHaigLitHaigSom(NG &ng, NGHolder &g,
                      const unordered_map<NFAVertex, u32> &regions,
                      som_type som) {
    if (!ng.cc.grey.allowLitHaig) {
        return false;
    }

    // In streaming mode, we can only delay up to our max available history.
    const u32 max_delay =
        ng.cc.streaming ? ng.cc.grey.maxHistoryAvailable : MO_INVALID_IDX;

    ue2_literal lit;
    shared_ptr<NGHolder> rhs = make_shared<NGHolder>();
    shared_ptr<NGHolder> lhs = make_shared<NGHolder>();
    if (!rhs || !lhs) {
        assert(0);
        throw std::bad_alloc();
    }

    if (!splitOffBestLiteral(g, regions, &lit, &*lhs, &*rhs, ng.cc)) {
        return false;
    }

    DEBUG_PRINTF("split off best lit '%s' (len=%zu)\n", dumpString(lit).c_str(),
                 lit.length());

    if (lit.length() < ng.cc.grey.minRoseLiteralLength) {
        DEBUG_PRINTF("lit too short\n");
        return false;
    }

    assert(lit.length() <= MAX_MASK2_WIDTH || !mixed_sensitivity(lit));

    if (edge(rhs->start, rhs->acceptEod, *rhs).second) {
        return false; /* TODO: handle */
    }

    makeReportsSomPass(ng.rm, *rhs);

    dumpHolder(*lhs, 92, "haiglithaig_lhs", ng.cc.grey);
    dumpHolder(*rhs, 93, "haiglithaig_rhs", ng.cc.grey);

    u32 delay = removeTrailingLiteralStates(*lhs, lit, max_delay);

    RoseInGraph ig;
    RoseInVertex s
        = add_vertex(RoseInVertexProps::makeStart(false), ig);
    RoseInVertex v = add_vertex(RoseInVertexProps::makeLiteral(lit), ig);

    bool lhs_all_vac = true;
    NGHolder::adjacency_iterator ai, ae;
    for (tie(ai, ae) = adjacent_vertices(lhs->startDs, *lhs);
         ai != ae && lhs_all_vac; ++ai) {
        if (!is_special(*ai, *lhs)) {
            lhs_all_vac = false;
        }
    }
    for (tie(ai, ae) = adjacent_vertices(lhs->start, *lhs);
         ai != ae && lhs_all_vac; ++ai) {
        if (!is_special(*ai, *lhs)) {
            lhs_all_vac = false;
        }
    }

    if (lhs_all_vac) {
        /* lhs is completely vacuous --> no prefix needed */
        add_edge(s, v, RoseInEdgeProps(0, ROSE_BOUND_INF), ig);
    } else {
        assert(delay == lit.length());
        setReportOnHaigPrefix(*ng.rose, *lhs);
        vector<vector<CharReach> > prefix_triggers; /* empty for prefix */
        assert(lhs->kind == NFA_PREFIX);
        shared_ptr<raw_som_dfa> l_haig
            = attemptToBuildHaig(*lhs, som, ng.ssm.somPrecision(),
                                 prefix_triggers, ng.cc.grey);
        if (!l_haig) {
            DEBUG_PRINTF("failed to haig\n");
            return false;
        }
        DEBUG_PRINTF("lhs haig %p\n", l_haig.get());

        add_edge(s, v, RoseInEdgeProps(lhs, l_haig, delay), ig);
    }

    if (!edge(rhs->start, rhs->accept, *rhs).second) {
        assert(rhs->kind == NFA_SUFFIX);

        vector<vector<CharReach> > triggers;
        triggers.push_back(as_cr_seq(lit));

        ue2_literal lit2;
        if (getTrailingLiteral(g, &lit2)
            && lit2.length() >= ng.cc.grey.minRoseLiteralLength
            && minStringPeriod(lit2) >= 2) {

            /* TODO: handle delay */
            size_t overlap = maxOverlap(lit, lit2, 0);
            u32 delay2 = min((size_t)max_delay, lit2.length() - overlap);
            delay2 = removeTrailingLiteralStates(*rhs, lit2, delay2);
            rhs->kind = NFA_INFIX;
            assert(delay2 <= lit2.length());
            setReportOnHaigPrefix(*ng.rose, *rhs);

            shared_ptr<raw_som_dfa> m_haig
                = attemptToBuildHaig(*rhs, som, ng.ssm.somPrecision(),
                                     triggers, ng.cc.grey, true);
            DEBUG_PRINTF("mhs haig %p\n", m_haig.get());
            if (!m_haig) {
                DEBUG_PRINTF("failed to haig\n");
                return false;
            }

            RoseInVertex w
                = add_vertex(RoseInVertexProps::makeLiteral(lit2), ig);
            add_edge(v, w, RoseInEdgeProps(rhs, m_haig, delay2), ig);

            NFAVertex reporter = getSoleSourceVertex(g, g.accept);
            assert(reporter);
            const auto &reports = g[reporter].reports;
            RoseInVertex a =
                add_vertex(RoseInVertexProps::makeAccept(reports), ig);
            add_edge(w, a, RoseInEdgeProps(0U, 0U), ig);
        } else {
            /* TODO: analysis to see if som is in fact always increasing */
            shared_ptr<raw_som_dfa> r_haig
                = attemptToBuildHaig(*rhs, som, ng.ssm.somPrecision(),
                                     triggers, ng.cc.grey, true);
            DEBUG_PRINTF("rhs haig %p\n", r_haig.get());
            if (!r_haig) {
                DEBUG_PRINTF("failed to haig\n");
                return false;
            }
            RoseInVertex a
                = add_vertex(RoseInVertexProps::makeAccept(set<ReportID>()),
                             ig);
            add_edge(v, a, RoseInEdgeProps(r_haig), ig);
        }
    } else {
        DEBUG_PRINTF("has start->accept edge\n");
        if (in_degree(g.acceptEod, g) > 1) {
            DEBUG_PRINTF("also has a path to EOD\n");
            return false;
        }
        NFAVertex reporter = getSoleSourceVertex(g, g.accept);
        if (!reporter) {
            return false; /* TODO: later */
        }
        const auto &reports = g[reporter].reports;
        assert(!reports.empty());
        RoseInVertex a =
            add_vertex(RoseInVertexProps::makeAccept(reports), ig);
        add_edge(v, a, RoseInEdgeProps(0U, 0U), ig);
    }

    calcVertexOffsets(ig);

    return ng.rose->addSombeRose(ig);
}

static
bool doMultiLitHaigSom(NG &ng, NGHolder &g, som_type som) {
    set<ue2_literal> lits;
    shared_ptr<NGHolder> rhs = make_shared<NGHolder>();
    if (!ng.cc.grey.allowLitHaig) {
        return false;
    }

    dumpHolder(g, 90, "lithaig_full", ng.cc.grey);

    if (!splitOffLeadingLiterals(g, &lits, &*rhs)) {
        DEBUG_PRINTF("no literal\n");
        return false;
    }

    makeReportsSomPass(ng.rm, *rhs);

    dumpHolder(*rhs, 91, "lithaig_rhs", ng.cc.grey);

    vector<vector<CharReach>> triggers;
    for (const auto &lit : lits) {
        if (lit.length() < ng.cc.grey.minRoseLiteralLength) {
            DEBUG_PRINTF("lit too short\n");
            return false;
        }

        assert(lit.length() <= MAX_MASK2_WIDTH || !mixed_sensitivity(lit));
        triggers.push_back(as_cr_seq(lit));
    }

    bool unordered_som_triggers = true; /* TODO: check overlaps to ensure that
                                         * we can promise ordering */

    assert(rhs->kind == NFA_SUFFIX);
    shared_ptr<raw_som_dfa> haig
        = attemptToBuildHaig(*rhs, som, ng.ssm.somPrecision(), triggers,
                             ng.cc.grey, unordered_som_triggers);
    if (!haig) {
        DEBUG_PRINTF("failed to haig\n");
        return false;
    }
    DEBUG_PRINTF("haig %p\n", haig.get());

    RoseInGraph ig;
    RoseInVertex s = add_vertex(RoseInVertexProps::makeStart(false), ig);

    RoseInVertex a
        = add_vertex(RoseInVertexProps::makeAccept(set<ReportID>()), ig);

    for (const auto &lit : lits) {
        RoseInVertex v = add_vertex(RoseInVertexProps::makeLiteral(lit), ig);
        add_edge(s, v, RoseInEdgeProps(0, ROSE_BOUND_INF), ig);
        add_edge(v, a, RoseInEdgeProps(haig), ig);
    }

    calcVertexOffsets(ig);

    return ng.rose->addSombeRose(ig);
}

static
bool trySombe(NG &ng, NGHolder &g, som_type som) {
    if (doLitHaigSom(ng, g, som)) {
        return true;
    }

    auto regions = assignRegions(g);

    if (doHaigLitHaigSom(ng, g, regions, som)) {
        return true;
    }

    if (doMultiLitHaigSom(ng, g, som)) {
        return true;
    }

    return false;
}

static
map<u32, region_info>::const_iterator pickInitialSomCut(const NGHolder &g,
                        const unordered_map<NFAVertex, u32> &regions,
                        const map<u32, region_info> &info,
                        const vector<DepthMinMax> &depths) {
    map<u32, region_info>::const_iterator picked = info.end();
    for (map<u32, region_info>::const_iterator it = info.begin();
         it != info.end(); ++it) {
        if (it->second.exits.empty()) {
            assert(it == info.begin());
            continue;
        }

        if (!regionCanEstablishSom(g, regions, it->first, it->second.exits,
                                   depths)) {
            /* last region is as far as we can go */
            DEBUG_PRINTF("region %u is beyond the fixed region\n", it->first);
            break;
        }
        picked = it;
    }

    return picked;
}

static
map<u32, region_info>::const_iterator tryForLaterRevNfaCut(const NGHolder &g,
                              const unordered_map<NFAVertex, u32> &regions,
                              const map<u32, region_info> &info,
                              const vector<DepthMinMax> &depths,
                              const map<u32, region_info>::const_iterator &orig,
                              const CompileContext &cc) {
    DEBUG_PRINTF("trying for later rev nfa cut\n");
    assert(orig != info.end());

    vector<map<u32, region_info>::const_iterator> cands;

    map<u32, region_info>::const_iterator it = orig;
    ++it;
    for (; it != info.end(); ++it) {
        /* for simplicity */
        if (it->second.exits.size() != 1 || it->second.optional) {
            continue;
        }
        NFAVertex v = *it->second.exits.begin();

        if (edge(v, g.accept, g).second || edge(v, g.acceptEod, g).second) {
            continue; /* for simplicity would require external som nfa reports
                       * as well. */
        }

        const depth &max_depth = depths[g[v].index].max;
        if (max_depth >
            depth(cc.grey.somMaxRevNfaLength - 1)) { /* virtual starts */
            continue;
        }

        if (max_depth > depth(MAX_REV_NFA_PREFIX)) {
            /* probably not a good idea, anyway */
            continue;
        }

        cands.push_back(it);
    }

    while (!cands.empty()) {
        map<u32, region_info>::const_iterator rv = cands.back();
        cands.pop_back();

        NFAVertex v = *rv->second.exits.begin();

        set<ue2_literal> lits = getLiteralSet(g, v);
        compressAndScore(lits);
        if (lits.empty()) {
        next_region:
            continue;
        }
        for (const auto &lit : lits) {
            if (lit.length() <= 3 || minStringPeriod(lit) < 2) {
                goto next_region;
            }
        }

        if (rv->second.enters.empty()
            || find(rv->second.full.begin(), rv->second.full.end(), g.startDs)
                    != rv->second.full.end()) {
            continue;
        }

        if (!isMandRegionBetween(info.begin(), rv)
            && info.begin()->second.optional) {
            continue;
        }

        /* check to see if it is a reasonable size */
        auto prefix =
            makePrefix(g, regions, rv->second, next(rv)->second, false);

        NGHolder g_rev;
        reverseHolder(*prefix, g_rev);
        anchorStarts(g_rev);

        renumber_vertices(g_rev);
        g_rev.kind = NFA_REV_PREFIX;
        reduceGraphEquivalences(g_rev, cc);
        removeRedundancy(g_rev, SOM_NONE);

        if (num_vertices(g_rev) > 128) { /* too big */
            continue;
        }

        return rv;
    }

    return info.end();
}

static
unique_ptr<NGHolder> makePrefixForChain(NGHolder &g,
                         const unordered_map<NFAVertex, u32> &regions,
                         const map<u32, region_info> &info,
                         const map<u32, region_info>::const_iterator &picked,
                         vector<DepthMinMax> *depths, bool prefix_by_rev,
                         ReportManager &rm) {
    DEBUG_PRINTF("making prefix for chain attempt\n");
    auto prefix =
        makePrefix(g, regions, picked->second, next(picked)->second, false);

    /* For the root SOM plan, we use a temporary SOM slot to start with so that
     * we don't have to do any complicated rollback operations if the call to
     * doSomPlanning() below fails. The temporary SOM slot is replaced with a
     * real one afterwards. */
    const u32 temp_som_loc = UINT32_MAX;
    setPrefixReports(rm, *prefix, INTERNAL_SOM_LOC_SET_IF_WRITABLE,
                     temp_som_loc, *depths, prefix_by_rev);

    /* handle direct edge to accepts from region */
    if (edge(picked->second.exits.front(), g.accept, g).second
            || edge(picked->second.exits.front(), g.acceptEod, g).second) {
        map<u32, region_info>::const_iterator it = picked;
        do {
            makeSomRelReports(rm, g, it->second.exits, *depths);
        } while (it != info.begin() && it->second.optional && (it--)->first);
    }

    depths->clear(); /* renumbering invalidates depths */
    renumber_vertices(*prefix);

    DEBUG_PRINTF("done\n");
    return prefix;
}

sombe_rv doSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, u32 comp_id,
               som_type som) {
    assert(som);
    DEBUG_PRINTF("som hello\n");
    ReportManager &rm = ng.rm;
    SomSlotManager &ssm = ng.ssm;
    const CompileContext &cc = ng.cc;

    // Special case: if g is completely anchored or begins with a dot-star, we
    // know that we have an absolute SOM of zero all the time.
    if (!proper_out_degree(g.startDs, g) || beginsWithDotStar(g)) {
        makeSomAbsReports(rm, g, g.accept);
        makeSomAbsReports(rm, g, g.acceptEod);
        return SOMBE_HANDLED_INTERNAL;
    }

    if (!cc.grey.allowSomChain) {
        return SOMBE_FAIL;
    }

    // A pristine copy of the input graph, which must be restored to in paths
    // that return false. Also used as the forward graph for som rev nfa
    // construction.
    NGHolder g_pristine;
    cloneHolder(g_pristine, g);

    vector<DepthMinMax> depths = getDistancesFromSOM(g);

    // try a redundancy pass.
    if (addSomRedundancy(g, depths)) {
        depths = getDistancesFromSOM(g); // recalc
    }

    auto regions = assignRegions(g);

    dumpHolder(g, regions, 11, "som_explode", cc.grey);

    map<u32, region_info> info;
    buildRegionMapping(g, regions, info);

    map<u32, region_info>::const_iterator picked
        = pickInitialSomCut(g, regions, info, depths);
    DEBUG_PRINTF("picked %u\n", picked->first);
    if (picked == info.end() || picked->second.exits.empty()) {
        DEBUG_PRINTF("no regions/no progress possible\n");
        clear_graph(g);
        cloneHolder(g, g_pristine);
        if (doSomRevNfa(ng, g, cc)) {
            return SOMBE_HANDLED_INTERNAL;
        } else {
            return SOMBE_FAIL;
        }
    }

    if (finalRegion(g, regions, picked->second.exits[0])) {
        makeSomRelReports(rm, g, g.accept, depths);
        makeSomRelReports(rm, g, g.acceptEod, depths);
        return SOMBE_HANDLED_INTERNAL;
    }

    if (doSomRevNfa(ng, g_pristine, cc)) {
        clear_graph(g);
        cloneHolder(g, g_pristine);
        return SOMBE_HANDLED_INTERNAL;
    }

    bool prefix_by_rev = false;
    map<u32, region_info>::const_iterator picked_old = picked;
    map<u32, region_info>::const_iterator rev_pick
        = tryForLaterRevNfaCut(g, regions, info, depths, picked, cc);
    if (rev_pick != info.end()) {
        DEBUG_PRINTF("found later rev prefix cut point\n");
        assert(rev_pick != picked);
        picked = rev_pick;
        prefix_by_rev = true;
    } else {
        /* sanity checks for picked region, these checks have already been done
         * if we are using a prefix reverse nfa. */
        if (picked->second.enters.empty()
            || find(picked->second.full.begin(), picked->second.full.end(),
                    g.startDs) != picked->second.full.end()) {
            clear_graph(g);
            cloneHolder(g, g_pristine);
            return SOMBE_FAIL;
        }

        if (!isMandRegionBetween(info.begin(), picked)
            && info.begin()->second.optional) {
            clear_graph(g);
            cloneHolder(g, g_pristine);
            return SOMBE_FAIL;
        }
    }

    DEBUG_PRINTF("region %u is the final\n", picked->first);

    shared_ptr<NGHolder> prefix = makePrefixForChain(
        g, regions, info, picked, &depths, prefix_by_rev, rm);
    /* note depths cleared as we have renumbered */

    CharReach escapes;
    bool stuck = isPossibleLock(g, picked, info, &escapes);
    if (stuck) {
        DEBUG_PRINTF("investigating potential lock\n");

        NGHolder gg;
        fillHolderForLockCheck(&gg, g, info, picked);

        stuck = firstMatchIsFirst(gg);
    }

    if (stuck && escapes.none()) {
        /* leads directly to .* --> woot */
        DEBUG_PRINTF("initial slot is full lock\n");
        u32 som_loc = ssm.getSomSlot(*prefix, escapes, false,
                                     SomSlotManager::NO_PARENT);
        replaceTempSomSlot(rm, *prefix, som_loc);

        /* update all reports on g to report the som_loc's som */
        updateReportToUseRecordedSom(rm, g, som_loc);

        /* create prefix to set the som_loc */
        updatePrefixReports(rm, *prefix, INTERNAL_SOM_LOC_SET_IF_UNSET);
        if (prefix_by_rev) {
            u32 rev_comp_id = doSomRevNfaPrefix(ng, expr, *prefix, cc);
            updatePrefixReportsRevNFA(rm, *prefix, rev_comp_id);
        }
        renumber_vertices(*prefix);
        if (!ng.addHolder(*prefix)) {
            DEBUG_PRINTF("failed to add holder\n");
            clear_graph(g);
            cloneHolder(g, g_pristine);
            return SOMBE_FAIL;
        }

        DEBUG_PRINTF("ok found initial lock\n");
        return SOMBE_HANDLED_INTERNAL;
    }

    vector<som_plan> plan;
 retry:
    // Note: no-one should ever pay attention to the root plan's parent.
    plan.push_back(som_plan(prefix, escapes, false, 0));
    dumpHolder(*plan.back().prefix, 12, "som_prefix", cc.grey);
    if (!prefix_by_rev) {
        if (!doSomPlanning(g, stuck, regions, info, picked, plan, cc.grey)) {
            DEBUG_PRINTF("failed\n");
            clear_graph(g);
            cloneHolder(g, g_pristine);
            return SOMBE_FAIL;
        }
    } else {
        DEBUG_PRINTF("trying for som plan\n");
        if (!doSomPlanning(g, stuck, regions, info, picked, plan, cc.grey,
                           DISALLOW_MODIFY_HOLDER)) {
            /* Note: the larger prefixes generated by reverse nfas may not
             * advance as fair as the original prefix - so we should retry
             * with a smaller prefix. */

            prefix_by_rev = false;
            stuck = false; /* if we reached a lock, then prefix_by_rev would not
                            * have advanced. */
            picked = picked_old;
            plan.clear();
            depths = getDistancesFromSOM(g); /* due to renumbering, need to
                                              * regenerate */
            prefix = makePrefixForChain(g, regions, info, picked, &depths,
                                        prefix_by_rev, rm);
            escapes.clear();
            DEBUG_PRINTF("retrying\n");
            goto retry;
        }
    }
    DEBUG_PRINTF("som planning ok\n");

    /* if the initial prefix is weak is if sombe approaches are better */
    if (findMinWidth(*prefix) <= depth(2)) {
        DEBUG_PRINTF("weak prefix... seeing if sombe can help out\n");
        NGHolder g2;
        cloneHolder(g2, g_pristine);
        if (trySombe(ng, g2, som)) {
            return SOMBE_HANDLED_ALL;
        }
    }

    /* From this point we know that we are going to succeed or die horribly with
     * a pattern too large. Anything done past this point can be considered
     * committed to the compile. */

    regions = assignRegions(g); // Update as g may have changed.

    DEBUG_PRINTF("-- get slot for initial plan\n");
    u32 som_loc;
    if (plan[0].is_reset) {
        som_loc = ssm.getInitialResetSomSlot(*prefix, g, regions,
                                picked->first, &plan[0].no_implement);
    } else {
        som_loc = ssm.getSomSlot(*prefix, escapes, false,
                                 SomSlotManager::NO_PARENT);
    }

    replaceTempSomSlot(rm, *prefix, som_loc);

    if (plan.front().is_reset) {
        updatePrefixReports(rm, *prefix, INTERNAL_SOM_LOC_SET);
    }
    if (prefix_by_rev && !plan.front().no_implement) {
        u32 rev_comp_id = doSomRevNfaPrefix(ng, expr, *prefix, cc);
        updatePrefixReportsRevNFA(rm, *prefix, rev_comp_id);
    }

    implementSomPlan(ng, expr, comp_id, g, plan, som_loc);

    DEBUG_PRINTF("success\n");
    return SOMBE_HANDLED_INTERNAL;
}

sombe_rv doSomWithHaig(NG &ng, NGHolder &g, const ExpressionInfo &expr,
                       u32 comp_id, som_type som) {
    assert(som);

    DEBUG_PRINTF("som+haig hello\n");

    // A pristine copy of the input graph, which must be restored to in paths
    // that return false. Also used as the forward graph for som rev nfa
    // construction.
    NGHolder g_pristine;
    cloneHolder(g_pristine, g);

    if (trySombe(ng, g, som)) {
        return SOMBE_HANDLED_ALL;
    }

    if (!ng.cc.grey.allowHaigLit || !ng.cc.grey.allowSomChain) {
        return SOMBE_FAIL;
    }

    // know that we have an absolute SOM of zero all the time.
    assert(edge(g.startDs, g.startDs, g).second);

    vector<DepthMinMax> depths = getDistancesFromSOM(g);

    // try a redundancy pass.
    if (addSomRedundancy(g, depths)) {
        depths = getDistancesFromSOM(g);
    }

    auto regions = assignRegions(g);

    dumpHolder(g, regions, 21, "som_explode", ng.cc.grey);

    map<u32, region_info> info;
    buildRegionMapping(g, regions, info, true);

    sombe_rv rv =
        doHaigLitSom(ng, g, expr, comp_id, som, regions, info, info.begin());
    if (rv == SOMBE_FAIL) {
        clear_graph(g);
        cloneHolder(g, g_pristine);
    }
    return rv;
}

} // namespace ue2